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