1//===- HexagonCFGOptimizer.cpp - CFG optimizations ------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "Hexagon.h"
10#include "MCTargetDesc/HexagonMCTargetDesc.h"
11#include "llvm/CodeGen/MachineBasicBlock.h"
12#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
13#include "llvm/CodeGen/MachineFunction.h"
14#include "llvm/CodeGen/MachineFunctionPass.h"
15#include "llvm/CodeGen/MachineInstr.h"
16#include "llvm/CodeGen/MachineOperand.h"
17#include "llvm/CodeGen/TargetInstrInfo.h"
18#include "llvm/CodeGen/TargetSubtargetInfo.h"
19#include "llvm/Pass.h"
20#include "llvm/Support/ErrorHandling.h"
21#include <cassert>
22#include <vector>
23
24using namespace llvm;
25
26#define DEBUG_TYPE "hexagon_cfg"
27
28namespace llvm {
29
30FunctionPass *createHexagonCFGOptimizer();
31void initializeHexagonCFGOptimizerPass(PassRegistry&);
32
33} // end namespace llvm
34
35namespace {
36
37class HexagonCFGOptimizer : public MachineFunctionPass {
38private:
39 void InvertAndChangeJumpTarget(MachineInstr &, MachineBasicBlock *);
40 bool isOnFallThroughPath(MachineBasicBlock *MBB);
41
42public:
43 static char ID;
44
45 HexagonCFGOptimizer() : MachineFunctionPass(ID) {
46 initializeHexagonCFGOptimizerPass(*PassRegistry::getPassRegistry());
47 }
48
49 StringRef getPassName() const override { return "Hexagon CFG Optimizer"; }
50 bool runOnMachineFunction(MachineFunction &Fn) override;
51
52 MachineFunctionProperties getRequiredProperties() const override {
53 return MachineFunctionProperties().set(
54 MachineFunctionProperties::Property::NoVRegs);
55 }
56};
57
58} // end anonymous namespace
59
60char HexagonCFGOptimizer::ID = 0;
61
62static bool IsConditionalBranch(int Opc) {
63 switch (Opc) {
64 case Hexagon::J2_jumpt:
65 case Hexagon::J2_jumptpt:
66 case Hexagon::J2_jumpf:
67 case Hexagon::J2_jumpfpt:
68 case Hexagon::J2_jumptnew:
69 case Hexagon::J2_jumpfnew:
70 case Hexagon::J2_jumptnewpt:
71 case Hexagon::J2_jumpfnewpt:
72 return true;
73 }
74 return false;
75}
76
77static bool IsUnconditionalJump(int Opc) {
78 return (Opc == Hexagon::J2_jump);
79}
80
81void HexagonCFGOptimizer::InvertAndChangeJumpTarget(
82 MachineInstr &MI, MachineBasicBlock *NewTarget) {
83 const TargetInstrInfo *TII =
84 MI.getParent()->getParent()->getSubtarget().getInstrInfo();
85 int NewOpcode = 0;
86 switch (MI.getOpcode()) {
87 case Hexagon::J2_jumpt:
88 NewOpcode = Hexagon::J2_jumpf;
89 break;
90 case Hexagon::J2_jumpf:
91 NewOpcode = Hexagon::J2_jumpt;
92 break;
93 case Hexagon::J2_jumptnewpt:
94 NewOpcode = Hexagon::J2_jumpfnewpt;
95 break;
96 case Hexagon::J2_jumpfnewpt:
97 NewOpcode = Hexagon::J2_jumptnewpt;
98 break;
99 default:
100 llvm_unreachable("Cannot handle this case");
101 }
102
103 MI.setDesc(TII->get(Opcode: NewOpcode));
104 MI.getOperand(i: 1).setMBB(NewTarget);
105}
106
107bool HexagonCFGOptimizer::isOnFallThroughPath(MachineBasicBlock *MBB) {
108 if (MBB->canFallThrough())
109 return true;
110 for (MachineBasicBlock *PB : MBB->predecessors())
111 if (PB->isLayoutSuccessor(MBB) && PB->canFallThrough())
112 return true;
113 return false;
114}
115
116bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
117 if (skipFunction(F: Fn.getFunction()))
118 return false;
119
120 // Loop over all of the basic blocks.
121 for (MachineBasicBlock &MBB : Fn) {
122 // Traverse the basic block.
123 MachineBasicBlock::iterator MII = MBB.getFirstTerminator();
124 if (MII != MBB.end()) {
125 MachineInstr &MI = *MII;
126 int Opc = MI.getOpcode();
127 if (IsConditionalBranch(Opc)) {
128 // (Case 1) Transform the code if the following condition occurs:
129 // BB1: if (p0) jump BB3
130 // ...falls-through to BB2 ...
131 // BB2: jump BB4
132 // ...next block in layout is BB3...
133 // BB3: ...
134 //
135 // Transform this to:
136 // BB1: if (!p0) jump BB4
137 // Remove BB2
138 // BB3: ...
139 //
140 // (Case 2) A variation occurs when BB3 contains a JMP to BB4:
141 // BB1: if (p0) jump BB3
142 // ...falls-through to BB2 ...
143 // BB2: jump BB4
144 // ...other basic blocks ...
145 // BB4:
146 // ...not a fall-thru
147 // BB3: ...
148 // jump BB4
149 //
150 // Transform this to:
151 // BB1: if (!p0) jump BB4
152 // Remove BB2
153 // BB3: ...
154 // BB4: ...
155 unsigned NumSuccs = MBB.succ_size();
156 MachineBasicBlock::succ_iterator SI = MBB.succ_begin();
157 MachineBasicBlock* FirstSucc = *SI;
158 MachineBasicBlock* SecondSucc = *(++SI);
159 MachineBasicBlock* LayoutSucc = nullptr;
160 MachineBasicBlock* JumpAroundTarget = nullptr;
161
162 if (MBB.isLayoutSuccessor(MBB: FirstSucc)) {
163 LayoutSucc = FirstSucc;
164 JumpAroundTarget = SecondSucc;
165 } else if (MBB.isLayoutSuccessor(MBB: SecondSucc)) {
166 LayoutSucc = SecondSucc;
167 JumpAroundTarget = FirstSucc;
168 } else {
169 // Odd case...cannot handle.
170 }
171
172 // The target of the unconditional branch must be JumpAroundTarget.
173 // TODO: If not, we should not invert the unconditional branch.
174 MachineBasicBlock* CondBranchTarget = nullptr;
175 if (MI.getOpcode() == Hexagon::J2_jumpt ||
176 MI.getOpcode() == Hexagon::J2_jumpf) {
177 CondBranchTarget = MI.getOperand(i: 1).getMBB();
178 }
179
180 if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) {
181 continue;
182 }
183
184 if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) {
185 // Ensure that BB2 has one instruction -- an unconditional jump.
186 if ((LayoutSucc->size() == 1) &&
187 IsUnconditionalJump(Opc: LayoutSucc->front().getOpcode())) {
188 assert(JumpAroundTarget && "jump target is needed to process second basic block");
189 MachineBasicBlock* UncondTarget =
190 LayoutSucc->front().getOperand(i: 0).getMBB();
191 // Check if the layout successor of BB2 is BB3.
192 bool case1 = LayoutSucc->isLayoutSuccessor(MBB: JumpAroundTarget);
193 bool case2 = JumpAroundTarget->isSuccessor(MBB: UncondTarget) &&
194 !JumpAroundTarget->empty() &&
195 IsUnconditionalJump(Opc: JumpAroundTarget->back().getOpcode()) &&
196 JumpAroundTarget->pred_size() == 1 &&
197 JumpAroundTarget->succ_size() == 1;
198
199 if (case1 || case2) {
200 InvertAndChangeJumpTarget(MI, NewTarget: UncondTarget);
201 MBB.replaceSuccessor(Old: JumpAroundTarget, New: UncondTarget);
202
203 // Remove the unconditional branch in LayoutSucc.
204 LayoutSucc->erase(I: LayoutSucc->begin());
205 LayoutSucc->replaceSuccessor(Old: UncondTarget, New: JumpAroundTarget);
206
207 // This code performs the conversion for case 2, which moves
208 // the block to the fall-thru case (BB3 in the code above).
209 if (case2 && !case1) {
210 JumpAroundTarget->moveAfter(NewBefore: LayoutSucc);
211 // only move a block if it doesn't have a fall-thru. otherwise
212 // the CFG will be incorrect.
213 if (!isOnFallThroughPath(MBB: UncondTarget))
214 UncondTarget->moveAfter(NewBefore: JumpAroundTarget);
215 }
216
217 // Correct live-in information. Is used by post-RA scheduler
218 // The live-in to LayoutSucc is now all values live-in to
219 // JumpAroundTarget.
220 std::vector<MachineBasicBlock::RegisterMaskPair> OrigLiveIn(
221 LayoutSucc->livein_begin(), LayoutSucc->livein_end());
222 std::vector<MachineBasicBlock::RegisterMaskPair> NewLiveIn(
223 JumpAroundTarget->livein_begin(),
224 JumpAroundTarget->livein_end());
225 for (const auto &OrigLI : OrigLiveIn)
226 LayoutSucc->removeLiveIn(Reg: OrigLI.PhysReg);
227 for (const auto &NewLI : NewLiveIn)
228 LayoutSucc->addLiveIn(RegMaskPair: NewLI);
229 }
230 }
231 }
232 }
233 }
234 }
235 return true;
236}
237
238//===----------------------------------------------------------------------===//
239// Public Constructor Functions
240//===----------------------------------------------------------------------===//
241
242INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer",
243 false, false)
244
245FunctionPass *llvm::createHexagonCFGOptimizer() {
246 return new HexagonCFGOptimizer();
247}
248