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
24 using namespace llvm;
25
26 #define DEBUG_TYPE "hexagon_cfg"
27
28 namespace llvm {
29
30 FunctionPass *createHexagonCFGOptimizer();
31 void initializeHexagonCFGOptimizerPass(PassRegistry&);
32
33 } // end namespace llvm
34
35 namespace {
36
37 class HexagonCFGOptimizer : public MachineFunctionPass {
38 private:
39 void InvertAndChangeJumpTarget(MachineInstr &, MachineBasicBlock *);
40 bool isOnFallThroughPath(MachineBasicBlock *MBB);
41
42 public:
43 static char ID;
44
HexagonCFGOptimizer()45 HexagonCFGOptimizer() : MachineFunctionPass(ID) {
46 initializeHexagonCFGOptimizerPass(*PassRegistry::getPassRegistry());
47 }
48
getPassName() const49 StringRef getPassName() const override { return "Hexagon CFG Optimizer"; }
50 bool runOnMachineFunction(MachineFunction &Fn) override;
51
getRequiredProperties() const52 MachineFunctionProperties getRequiredProperties() const override {
53 return MachineFunctionProperties().set(
54 MachineFunctionProperties::Property::NoVRegs);
55 }
56 };
57
58 } // end anonymous namespace
59
60 char HexagonCFGOptimizer::ID = 0;
61
IsConditionalBranch(int Opc)62 static 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
IsUnconditionalJump(int Opc)77 static bool IsUnconditionalJump(int Opc) {
78 return (Opc == Hexagon::J2_jump);
79 }
80
InvertAndChangeJumpTarget(MachineInstr & MI,MachineBasicBlock * NewTarget)81 void 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(NewOpcode));
104 MI.getOperand(1).setMBB(NewTarget);
105 }
106
isOnFallThroughPath(MachineBasicBlock * MBB)107 bool 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
runOnMachineFunction(MachineFunction & Fn)116 bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
117 if (skipFunction(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(FirstSucc)) {
163 LayoutSucc = FirstSucc;
164 JumpAroundTarget = SecondSucc;
165 } else if (MBB.isLayoutSuccessor(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(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(LayoutSucc->front().getOpcode())) {
188 assert(JumpAroundTarget && "jump target is needed to process second basic block");
189 MachineBasicBlock* UncondTarget =
190 LayoutSucc->front().getOperand(0).getMBB();
191 // Check if the layout successor of BB2 is BB3.
192 bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget);
193 bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) &&
194 !JumpAroundTarget->empty() &&
195 IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) &&
196 JumpAroundTarget->pred_size() == 1 &&
197 JumpAroundTarget->succ_size() == 1;
198
199 if (case1 || case2) {
200 InvertAndChangeJumpTarget(MI, UncondTarget);
201 MBB.replaceSuccessor(JumpAroundTarget, UncondTarget);
202
203 // Remove the unconditional branch in LayoutSucc.
204 LayoutSucc->erase(LayoutSucc->begin());
205 LayoutSucc->replaceSuccessor(UncondTarget, 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(LayoutSucc);
211 // only move a block if it doesn't have a fall-thru. otherwise
212 // the CFG will be incorrect.
213 if (!isOnFallThroughPath(UncondTarget))
214 UncondTarget->moveAfter(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(OrigLI.PhysReg);
227 for (const auto &NewLI : NewLiveIn)
228 LayoutSucc->addLiveIn(NewLI);
229 }
230 }
231 }
232 }
233 }
234 }
235 return true;
236 }
237
238 //===----------------------------------------------------------------------===//
239 // Public Constructor Functions
240 //===----------------------------------------------------------------------===//
241
242 INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer",
243 false, false)
244
createHexagonCFGOptimizer()245 FunctionPass *llvm::createHexagonCFGOptimizer() {
246 return new HexagonCFGOptimizer();
247 }
248