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