|
121
|
1 //===-- CoalesceBranches.cpp - Coalesce blocks with the same condition ---===//
|
|
|
2 //
|
|
|
3 // The LLVM Compiler Infrastructure
|
|
|
4 //
|
|
|
5 // This file is distributed under the University of Illinois Open Source
|
|
|
6 // License. See LICENSE.TXT for details.
|
|
|
7 //
|
|
|
8 //===----------------------------------------------------------------------===//
|
|
|
9 ///
|
|
|
10 /// \file
|
|
|
11 /// Coalesce basic blocks guarded by the same branch condition into a single
|
|
|
12 /// basic block.
|
|
|
13 ///
|
|
|
14 //===----------------------------------------------------------------------===//
|
|
|
15
|
|
|
16 #include "PPC.h"
|
|
|
17 #include "llvm/ADT/BitVector.h"
|
|
|
18 #include "llvm/ADT/Statistic.h"
|
|
|
19 #include "llvm/CodeGen/MachineDominators.h"
|
|
|
20 #include "llvm/CodeGen/MachineFunctionPass.h"
|
|
|
21 #include "llvm/CodeGen/MachinePostDominators.h"
|
|
|
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
|
|
|
23 #include "llvm/CodeGen/Passes.h"
|
|
|
24 #include "llvm/Support/Debug.h"
|
|
|
25 #include "llvm/Target/TargetFrameLowering.h"
|
|
|
26 #include "llvm/Target/TargetInstrInfo.h"
|
|
|
27 #include "llvm/Target/TargetSubtargetInfo.h"
|
|
|
28
|
|
|
29 using namespace llvm;
|
|
|
30
|
|
|
31 #define DEBUG_TYPE "ppc-branch-coalescing"
|
|
|
32
|
|
|
33 STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");
|
|
|
34 STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");
|
|
|
35 STATISTIC(NumBlocksNotCoalesced, "Number of blocks not coalesced");
|
|
|
36
|
|
|
37 namespace llvm {
|
|
|
38 void initializePPCBranchCoalescingPass(PassRegistry&);
|
|
|
39 }
|
|
|
40
|
|
|
41 //===----------------------------------------------------------------------===//
|
|
|
42 // PPCBranchCoalescing
|
|
|
43 //===----------------------------------------------------------------------===//
|
|
|
44 ///
|
|
|
45 /// Improve scheduling by coalescing branches that depend on the same condition.
|
|
|
46 /// This pass looks for blocks that are guarded by the same branch condition
|
|
|
47 /// and attempts to merge the blocks together. Such opportunities arise from
|
|
|
48 /// the expansion of select statements in the IR.
|
|
|
49 ///
|
|
|
50 /// This pass does not handle implicit operands on branch statements. In order
|
|
|
51 /// to run on targets that use implicit operands, changes need to be made in the
|
|
|
52 /// canCoalesceBranch and canMerge methods.
|
|
|
53 ///
|
|
|
54 /// Example: the following LLVM IR
|
|
|
55 ///
|
|
|
56 /// %test = icmp eq i32 %x 0
|
|
|
57 /// %tmp1 = select i1 %test, double %a, double 2.000000e-03
|
|
|
58 /// %tmp2 = select i1 %test, double %b, double 5.000000e-03
|
|
|
59 ///
|
|
|
60 /// expands to the following machine code:
|
|
|
61 ///
|
|
|
62 /// BB#0: derived from LLVM BB %entry
|
|
|
63 /// Live Ins: %F1 %F3 %X6
|
|
|
64 /// <SNIP1>
|
|
|
65 /// %vreg0<def> = COPY %F1; F8RC:%vreg0
|
|
|
66 /// %vreg5<def> = CMPLWI %vreg4<kill>, 0; CRRC:%vreg5 GPRC:%vreg4
|
|
|
67 /// %vreg8<def> = LXSDX %ZERO8, %vreg7<kill>, %RM<imp-use>;
|
|
|
68 /// mem:LD8[ConstantPool] F8RC:%vreg8 G8RC:%vreg7
|
|
|
69 /// BCC 76, %vreg5, <BB#2>; CRRC:%vreg5
|
|
|
70 /// Successors according to CFG: BB#1(?%) BB#2(?%)
|
|
|
71 ///
|
|
|
72 /// BB#1: derived from LLVM BB %entry
|
|
|
73 /// Predecessors according to CFG: BB#0
|
|
|
74 /// Successors according to CFG: BB#2(?%)
|
|
|
75 ///
|
|
|
76 /// BB#2: derived from LLVM BB %entry
|
|
|
77 /// Predecessors according to CFG: BB#0 BB#1
|
|
|
78 /// %vreg9<def> = PHI %vreg8, <BB#1>, %vreg0, <BB#0>;
|
|
|
79 /// F8RC:%vreg9,%vreg8,%vreg0
|
|
|
80 /// <SNIP2>
|
|
|
81 /// BCC 76, %vreg5, <BB#4>; CRRC:%vreg5
|
|
|
82 /// Successors according to CFG: BB#3(?%) BB#4(?%)
|
|
|
83 ///
|
|
|
84 /// BB#3: derived from LLVM BB %entry
|
|
|
85 /// Predecessors according to CFG: BB#2
|
|
|
86 /// Successors according to CFG: BB#4(?%)
|
|
|
87 ///
|
|
|
88 /// BB#4: derived from LLVM BB %entry
|
|
|
89 /// Predecessors according to CFG: BB#2 BB#3
|
|
|
90 /// %vreg13<def> = PHI %vreg12, <BB#3>, %vreg2, <BB#2>;
|
|
|
91 /// F8RC:%vreg13,%vreg12,%vreg2
|
|
|
92 /// <SNIP3>
|
|
|
93 /// BLR8 %LR8<imp-use>, %RM<imp-use>, %F1<imp-use>
|
|
|
94 ///
|
|
|
95 /// When this pattern is detected, branch coalescing will try to collapse
|
|
|
96 /// it by moving code in BB#2 to BB#0 and/or BB#4 and removing BB#3.
|
|
|
97 ///
|
|
|
98 /// If all conditions are meet, IR should collapse to:
|
|
|
99 ///
|
|
|
100 /// BB#0: derived from LLVM BB %entry
|
|
|
101 /// Live Ins: %F1 %F3 %X6
|
|
|
102 /// <SNIP1>
|
|
|
103 /// %vreg0<def> = COPY %F1; F8RC:%vreg0
|
|
|
104 /// %vreg5<def> = CMPLWI %vreg4<kill>, 0; CRRC:%vreg5 GPRC:%vreg4
|
|
|
105 /// %vreg8<def> = LXSDX %ZERO8, %vreg7<kill>, %RM<imp-use>;
|
|
|
106 /// mem:LD8[ConstantPool] F8RC:%vreg8 G8RC:%vreg7
|
|
|
107 /// <SNIP2>
|
|
|
108 /// BCC 76, %vreg5, <BB#4>; CRRC:%vreg5
|
|
|
109 /// Successors according to CFG: BB#1(0x2aaaaaaa / 0x80000000 = 33.33%)
|
|
|
110 /// BB#4(0x55555554 / 0x80000000 = 66.67%)
|
|
|
111 ///
|
|
|
112 /// BB#1: derived from LLVM BB %entry
|
|
|
113 /// Predecessors according to CFG: BB#0
|
|
|
114 /// Successors according to CFG: BB#4(0x40000000 / 0x80000000 = 50.00%)
|
|
|
115 ///
|
|
|
116 /// BB#4: derived from LLVM BB %entry
|
|
|
117 /// Predecessors according to CFG: BB#0 BB#1
|
|
|
118 /// %vreg9<def> = PHI %vreg8, <BB#1>, %vreg0, <BB#0>;
|
|
|
119 /// F8RC:%vreg9,%vreg8,%vreg0
|
|
|
120 /// %vreg13<def> = PHI %vreg12, <BB#1>, %vreg2, <BB#0>;
|
|
|
121 /// F8RC:%vreg13,%vreg12,%vreg2
|
|
|
122 /// <SNIP3>
|
|
|
123 /// BLR8 %LR8<imp-use>, %RM<imp-use>, %F1<imp-use>
|
|
|
124 ///
|
|
|
125 /// Branch Coalescing does not split blocks, it moves everything in the same
|
|
|
126 /// direction ensuring it does not break use/definition semantics.
|
|
|
127 ///
|
|
|
128 /// PHI nodes and its corresponding use instructions are moved to its successor
|
|
|
129 /// block if there are no uses within the successor block PHI nodes. PHI
|
|
|
130 /// node ordering cannot be assumed.
|
|
|
131 ///
|
|
|
132 /// Non-PHI can be moved up to the predecessor basic block or down to the
|
|
|
133 /// successor basic block following any PHI instructions. Whether it moves
|
|
|
134 /// up or down depends on whether the register(s) defined in the instructions
|
|
|
135 /// are used in current block or in any PHI instructions at the beginning of
|
|
|
136 /// the successor block.
|
|
|
137
|
|
|
138 namespace {
|
|
|
139
|
|
|
140 class PPCBranchCoalescing : public MachineFunctionPass {
|
|
|
141 struct CoalescingCandidateInfo {
|
|
|
142 MachineBasicBlock *BranchBlock; // Block containing the branch
|
|
|
143 MachineBasicBlock *BranchTargetBlock; // Block branched to
|
|
|
144 MachineBasicBlock *FallThroughBlock; // Fall-through if branch not taken
|
|
|
145 SmallVector<MachineOperand, 4> Cond;
|
|
|
146 bool MustMoveDown;
|
|
|
147 bool MustMoveUp;
|
|
|
148
|
|
|
149 CoalescingCandidateInfo();
|
|
|
150 void clear();
|
|
|
151 };
|
|
|
152
|
|
|
153 MachineDominatorTree *MDT;
|
|
|
154 MachinePostDominatorTree *MPDT;
|
|
|
155 const TargetInstrInfo *TII;
|
|
|
156 MachineRegisterInfo *MRI;
|
|
|
157
|
|
|
158 void initialize(MachineFunction &F);
|
|
|
159 bool canCoalesceBranch(CoalescingCandidateInfo &Cand);
|
|
|
160 bool identicalOperands(ArrayRef<MachineOperand> OperandList1,
|
|
|
161 ArrayRef<MachineOperand> OperandList2) const;
|
|
|
162 bool validateCandidates(CoalescingCandidateInfo &SourceRegion,
|
|
|
163 CoalescingCandidateInfo &TargetRegion) const;
|
|
|
164
|
|
|
165 public:
|
|
|
166 static char ID;
|
|
|
167
|
|
|
168 PPCBranchCoalescing() : MachineFunctionPass(ID) {
|
|
|
169 initializePPCBranchCoalescingPass(*PassRegistry::getPassRegistry());
|
|
|
170 }
|
|
|
171
|
|
|
172 void getAnalysisUsage(AnalysisUsage &AU) const override {
|
|
|
173 AU.addRequired<MachineDominatorTree>();
|
|
|
174 AU.addRequired<MachinePostDominatorTree>();
|
|
|
175 MachineFunctionPass::getAnalysisUsage(AU);
|
|
|
176 }
|
|
|
177
|
|
|
178 StringRef getPassName() const override { return "Branch Coalescing"; }
|
|
|
179
|
|
|
180 bool mergeCandidates(CoalescingCandidateInfo &SourceRegion,
|
|
|
181 CoalescingCandidateInfo &TargetRegion);
|
|
|
182 bool canMoveToBeginning(const MachineInstr &MI,
|
|
|
183 const MachineBasicBlock &MBB) const;
|
|
|
184 bool canMoveToEnd(const MachineInstr &MI,
|
|
|
185 const MachineBasicBlock &MBB) const;
|
|
|
186 bool canMerge(CoalescingCandidateInfo &SourceRegion,
|
|
|
187 CoalescingCandidateInfo &TargetRegion) const;
|
|
|
188 void moveAndUpdatePHIs(MachineBasicBlock *SourceRegionMBB,
|
|
|
189 MachineBasicBlock *TargetRegionMBB);
|
|
|
190 bool runOnMachineFunction(MachineFunction &MF) override;
|
|
|
191 };
|
|
|
192 } // End anonymous namespace.
|
|
|
193
|
|
|
194 char PPCBranchCoalescing::ID = 0;
|
|
|
195 /// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing
|
|
|
196 /// Pass
|
|
|
197 FunctionPass *llvm::createPPCBranchCoalescingPass() {
|
|
|
198 return new PPCBranchCoalescing();
|
|
|
199 }
|
|
|
200
|
|
|
201 INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE,
|
|
|
202 "Branch Coalescing", false, false)
|
|
|
203 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
|
|
|
204 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
|
|
|
205 INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing",
|
|
|
206 false, false)
|
|
|
207
|
|
|
208 PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
|
|
|
209 : BranchBlock(nullptr), BranchTargetBlock(nullptr),
|
|
|
210 FallThroughBlock(nullptr), MustMoveDown(false), MustMoveUp(false) {}
|
|
|
211
|
|
|
212 void PPCBranchCoalescing::CoalescingCandidateInfo::clear() {
|
|
|
213 BranchBlock = nullptr;
|
|
|
214 BranchTargetBlock = nullptr;
|
|
|
215 FallThroughBlock = nullptr;
|
|
|
216 Cond.clear();
|
|
|
217 MustMoveDown = false;
|
|
|
218 MustMoveUp = false;
|
|
|
219 }
|
|
|
220
|
|
|
221 void PPCBranchCoalescing::initialize(MachineFunction &MF) {
|
|
|
222 MDT = &getAnalysis<MachineDominatorTree>();
|
|
|
223 MPDT = &getAnalysis<MachinePostDominatorTree>();
|
|
|
224 TII = MF.getSubtarget().getInstrInfo();
|
|
|
225 MRI = &MF.getRegInfo();
|
|
|
226 }
|
|
|
227
|
|
|
228 ///
|
|
|
229 /// Analyze the branch statement to determine if it can be coalesced. This
|
|
|
230 /// method analyses the branch statement for the given candidate to determine
|
|
|
231 /// if it can be coalesced. If the branch can be coalesced, then the
|
|
|
232 /// BranchTargetBlock and the FallThroughBlock are recorded in the specified
|
|
|
233 /// Candidate.
|
|
|
234 ///
|
|
|
235 ///\param[in,out] Cand The coalescing candidate to analyze
|
|
|
236 ///\return true if and only if the branch can be coalesced, false otherwise
|
|
|
237 ///
|
|
|
238 bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) {
|
|
|
239 DEBUG(dbgs() << "Determine if branch block " << Cand.BranchBlock->getNumber()
|
|
|
240 << " can be coalesced:");
|
|
|
241 MachineBasicBlock *FalseMBB = nullptr;
|
|
|
242
|
|
|
243 if (TII->analyzeBranch(*Cand.BranchBlock, Cand.BranchTargetBlock, FalseMBB,
|
|
|
244 Cand.Cond)) {
|
|
|
245 DEBUG(dbgs() << "TII unable to Analyze Branch - skip\n");
|
|
|
246 return false;
|
|
|
247 }
|
|
|
248
|
|
|
249 for (auto &I : Cand.BranchBlock->terminators()) {
|
|
|
250 DEBUG(dbgs() << "Looking at terminator : " << I << "\n");
|
|
|
251 if (!I.isBranch())
|
|
|
252 continue;
|
|
|
253
|
|
|
254 // The analyzeBranch method does not include any implicit operands.
|
|
|
255 // This is not an issue on PPC but must be handled on other targets.
|
|
|
256 // For this pass to be made target-independent, the analyzeBranch API
|
|
|
257 // need to be updated to support implicit operands and there would
|
|
|
258 // need to be a way to verify that any implicit operands would not be
|
|
|
259 // clobbered by merging blocks. This would include identifying the
|
|
|
260 // implicit operands as well as the basic block they are defined in.
|
|
|
261 // This could be done by changing the analyzeBranch API to have it also
|
|
|
262 // record and return the implicit operands and the blocks where they are
|
|
|
263 // defined. Alternatively, the BranchCoalescing code would need to be
|
|
|
264 // extended to identify the implicit operands. The analysis in canMerge
|
|
|
265 // must then be extended to prove that none of the implicit operands are
|
|
|
266 // changed in the blocks that are combined during coalescing.
|
|
|
267 if (I.getNumOperands() != I.getNumExplicitOperands()) {
|
|
|
268 DEBUG(dbgs() << "Terminator contains implicit operands - skip : " << I
|
|
|
269 << "\n");
|
|
|
270 return false;
|
|
|
271 }
|
|
|
272 }
|
|
|
273
|
|
|
274 if (Cand.BranchBlock->isEHPad() || Cand.BranchBlock->hasEHPadSuccessor()) {
|
|
|
275 DEBUG(dbgs() << "EH Pad - skip\n");
|
|
|
276 return false;
|
|
|
277 }
|
|
|
278
|
|
|
279 // For now only consider triangles (i.e, BranchTargetBlock is set,
|
|
|
280 // FalseMBB is null, and BranchTargetBlock is a successor to BranchBlock)
|
|
|
281 if (!Cand.BranchTargetBlock || FalseMBB ||
|
|
|
282 !Cand.BranchBlock->isSuccessor(Cand.BranchTargetBlock)) {
|
|
|
283 DEBUG(dbgs() << "Does not form a triangle - skip\n");
|
|
|
284 return false;
|
|
|
285 }
|
|
|
286
|
|
|
287 // Ensure there are only two successors
|
|
|
288 if (Cand.BranchBlock->succ_size() != 2) {
|
|
|
289 DEBUG(dbgs() << "Does not have 2 successors - skip\n");
|
|
|
290 return false;
|
|
|
291 }
|
|
|
292
|
|
|
293 // Sanity check - the block must be able to fall through
|
|
|
294 assert(Cand.BranchBlock->canFallThrough() &&
|
|
|
295 "Expecting the block to fall through!");
|
|
|
296
|
|
|
297 // We have already ensured there are exactly two successors to
|
|
|
298 // BranchBlock and that BranchTargetBlock is a successor to BranchBlock.
|
|
|
299 // Ensure the single fall though block is empty.
|
|
|
300 MachineBasicBlock *Succ =
|
|
|
301 (*Cand.BranchBlock->succ_begin() == Cand.BranchTargetBlock)
|
|
|
302 ? *Cand.BranchBlock->succ_rbegin()
|
|
|
303 : *Cand.BranchBlock->succ_begin();
|
|
|
304
|
|
|
305 assert(Succ && "Expecting a valid fall-through block\n");
|
|
|
306
|
|
|
307 if (!Succ->empty()) {
|
|
|
308 DEBUG(dbgs() << "Fall-through block contains code -- skip\n");
|
|
|
309 return false;
|
|
|
310 }
|
|
|
311
|
|
|
312 if (!Succ->isSuccessor(Cand.BranchTargetBlock)) {
|
|
|
313 DEBUG(dbgs()
|
|
|
314 << "Successor of fall through block is not branch taken block\n");
|
|
|
315 return false;
|
|
|
316 }
|
|
|
317
|
|
|
318 Cand.FallThroughBlock = Succ;
|
|
|
319 DEBUG(dbgs() << "Valid Candidate\n");
|
|
|
320 return true;
|
|
|
321 }
|
|
|
322
|
|
|
323 ///
|
|
|
324 /// Determine if the two operand lists are identical
|
|
|
325 ///
|
|
|
326 /// \param[in] OpList1 operand list
|
|
|
327 /// \param[in] OpList2 operand list
|
|
|
328 /// \return true if and only if the operands lists are identical
|
|
|
329 ///
|
|
|
330 bool PPCBranchCoalescing::identicalOperands(
|
|
|
331 ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const {
|
|
|
332
|
|
|
333 if (OpList1.size() != OpList2.size()) {
|
|
|
334 DEBUG(dbgs() << "Operand list is different size\n");
|
|
|
335 return false;
|
|
|
336 }
|
|
|
337
|
|
|
338 for (unsigned i = 0; i < OpList1.size(); ++i) {
|
|
|
339 const MachineOperand &Op1 = OpList1[i];
|
|
|
340 const MachineOperand &Op2 = OpList2[i];
|
|
|
341
|
|
|
342 DEBUG(dbgs() << "Op1: " << Op1 << "\n"
|
|
|
343 << "Op2: " << Op2 << "\n");
|
|
|
344
|
|
|
345 if (Op1.isIdenticalTo(Op2)) {
|
|
|
346 // filter out instructions with physical-register uses
|
|
|
347 if (Op1.isReg() && TargetRegisterInfo::isPhysicalRegister(Op1.getReg())
|
|
|
348 // If the physical register is constant then we can assume the value
|
|
|
349 // has not changed between uses.
|
|
|
350 && !(Op1.isUse() && MRI->isConstantPhysReg(Op1.getReg()))) {
|
|
|
351 DEBUG(dbgs() << "The operands are not provably identical.\n");
|
|
|
352 return false;
|
|
|
353 }
|
|
|
354 DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
|
|
|
355 continue;
|
|
|
356 }
|
|
|
357
|
|
|
358 // If the operands are not identical, but are registers, check to see if the
|
|
|
359 // definition of the register produces the same value. If they produce the
|
|
|
360 // same value, consider them to be identical.
|
|
|
361 if (Op1.isReg() && Op2.isReg() &&
|
|
|
362 TargetRegisterInfo::isVirtualRegister(Op1.getReg()) &&
|
|
|
363 TargetRegisterInfo::isVirtualRegister(Op2.getReg())) {
|
|
|
364 MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg());
|
|
|
365 MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());
|
|
|
366 if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) {
|
|
|
367 DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def
|
|
|
368 << " produce the same value!\n");
|
|
|
369 } else {
|
|
|
370 DEBUG(dbgs() << "Operands produce different values\n");
|
|
|
371 return false;
|
|
|
372 }
|
|
|
373 } else {
|
|
|
374 DEBUG(dbgs() << "The operands are not provably identical.\n");
|
|
|
375 return false;
|
|
|
376 }
|
|
|
377 }
|
|
|
378
|
|
|
379 return true;
|
|
|
380 }
|
|
|
381
|
|
|
382 ///
|
|
|
383 /// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
|
|
|
384 /// and update them to refer to the new block. PHI node ordering
|
|
|
385 /// cannot be assumed so it does not matter where the PHI instructions
|
|
|
386 /// are moved to in TargetMBB.
|
|
|
387 ///
|
|
|
388 /// \param[in] SourceMBB block to move PHI instructions from
|
|
|
389 /// \param[in] TargetMBB block to move PHI instructions to
|
|
|
390 ///
|
|
|
391 void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
|
|
|
392 MachineBasicBlock *TargetMBB) {
|
|
|
393
|
|
|
394 MachineBasicBlock::iterator MI = SourceMBB->begin();
|
|
|
395 MachineBasicBlock::iterator ME = SourceMBB->getFirstNonPHI();
|
|
|
396
|
|
|
397 if (MI == ME) {
|
|
|
398 DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");
|
|
|
399 return;
|
|
|
400 }
|
|
|
401
|
|
|
402 // Update all PHI instructions in SourceMBB and move to top of TargetMBB
|
|
|
403 for (MachineBasicBlock::iterator Iter = MI; Iter != ME; Iter++) {
|
|
|
404 MachineInstr &PHIInst = *Iter;
|
|
|
405 for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) {
|
|
|
406 MachineOperand &MO = PHIInst.getOperand(i);
|
|
|
407 if (MO.getMBB() == SourceMBB)
|
|
|
408 MO.setMBB(TargetMBB);
|
|
|
409 }
|
|
|
410 }
|
|
|
411 TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME);
|
|
|
412 }
|
|
|
413
|
|
|
414 ///
|
|
|
415 /// This function checks if MI can be moved to the beginning of the TargetMBB
|
|
|
416 /// following PHI instructions. A MI instruction can be moved to beginning of
|
|
|
417 /// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
|
|
|
418 ///
|
|
|
419 /// \param[in] MI the machine instruction to move.
|
|
|
420 /// \param[in] TargetMBB the machine basic block to move to
|
|
|
421 /// \return true if it is safe to move MI to beginning of TargetMBB,
|
|
|
422 /// false otherwise.
|
|
|
423 ///
|
|
|
424 bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
|
|
|
425 const MachineBasicBlock &TargetMBB
|
|
|
426 ) const {
|
|
|
427
|
|
|
428 DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "
|
|
|
429 << TargetMBB.getNumber() << "\n");
|
|
|
430
|
|
|
431 for (auto &Def : MI.defs()) { // Looking at Def
|
|
|
432 for (auto &Use : MRI->use_instructions(Def.getReg())) {
|
|
|
433 if (Use.isPHI() && Use.getParent() == &TargetMBB) {
|
|
|
434 DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n");
|
|
|
435 return false;
|
|
|
436 }
|
|
|
437 }
|
|
|
438 }
|
|
|
439
|
|
|
440 DEBUG(dbgs() << " Safe to move to the beginning.\n");
|
|
|
441 return true;
|
|
|
442 }
|
|
|
443
|
|
|
444 ///
|
|
|
445 /// This function checks if MI can be moved to the end of the TargetMBB,
|
|
|
446 /// immediately before the first terminator. A MI instruction can be moved
|
|
|
447 /// to then end of the TargetMBB if no PHI node defines what MI uses within
|
|
|
448 /// it's own MBB.
|
|
|
449 ///
|
|
|
450 /// \param[in] MI the machine instruction to move.
|
|
|
451 /// \param[in] TargetMBB the machine basic block to move to
|
|
|
452 /// \return true if it is safe to move MI to end of TargetMBB,
|
|
|
453 /// false otherwise.
|
|
|
454 ///
|
|
|
455 bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,
|
|
|
456 const MachineBasicBlock &TargetMBB
|
|
|
457 ) const {
|
|
|
458
|
|
|
459 DEBUG(dbgs() << "Checking if " << MI << " can move to end of "
|
|
|
460 << TargetMBB.getNumber() << "\n");
|
|
|
461
|
|
|
462 for (auto &Use : MI.uses()) {
|
|
|
463 if (Use.isReg() && TargetRegisterInfo::isVirtualRegister(Use.getReg())) {
|
|
|
464 MachineInstr *DefInst = MRI->getVRegDef(Use.getReg());
|
|
|
465 if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {
|
|
|
466 DEBUG(dbgs() << " *** Cannot move this instruction ***\n");
|
|
|
467 return false;
|
|
|
468 } else {
|
|
|
469 DEBUG(dbgs() << " *** def is in another block -- safe to move!\n");
|
|
|
470 }
|
|
|
471 }
|
|
|
472 }
|
|
|
473
|
|
|
474 DEBUG(dbgs() << " Safe to move to the end.\n");
|
|
|
475 return true;
|
|
|
476 }
|
|
|
477
|
|
|
478 ///
|
|
|
479 /// This method checks to ensure the two coalescing candidates follows the
|
|
|
480 /// expected pattern required for coalescing.
|
|
|
481 ///
|
|
|
482 /// \param[in] SourceRegion The candidate to move statements from
|
|
|
483 /// \param[in] TargetRegion The candidate to move statements to
|
|
|
484 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
|
|
|
485 /// into a block in TargetRegion; false otherwise.
|
|
|
486 ///
|
|
|
487 bool PPCBranchCoalescing::validateCandidates(
|
|
|
488 CoalescingCandidateInfo &SourceRegion,
|
|
|
489 CoalescingCandidateInfo &TargetRegion) const {
|
|
|
490
|
|
|
491 if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
|
|
|
492 llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion");
|
|
|
493 else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
|
|
|
494 llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");
|
|
|
495 else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
|
|
|
496 llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion");
|
|
|
497 else if (!TargetRegion.FallThroughBlock->empty() ||
|
|
|
498 !SourceRegion.FallThroughBlock->empty())
|
|
|
499 llvm_unreachable("Expecting fall-through blocks to be empty");
|
|
|
500
|
|
|
501 return true;
|
|
|
502 }
|
|
|
503
|
|
|
504 ///
|
|
|
505 /// This method determines whether the two coalescing candidates can be merged.
|
|
|
506 /// In order to be merged, all instructions must be able to
|
|
|
507 /// 1. Move to the beginning of the SourceRegion.BranchTargetBlock;
|
|
|
508 /// 2. Move to the end of the TargetRegion.BranchBlock.
|
|
|
509 /// Merging involves moving the instructions in the
|
|
|
510 /// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
|
|
|
511 ///
|
|
|
512 /// This function first try to move instructions from the
|
|
|
513 /// TargetRegion.BranchTargetBlock down, to the beginning of the
|
|
|
514 /// SourceRegion.BranchTargetBlock. This is not possible if any register defined
|
|
|
515 /// in TargetRegion.BranchTargetBlock is used in a PHI node in the
|
|
|
516 /// SourceRegion.BranchTargetBlock. In this case, check whether the statement
|
|
|
517 /// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
|
|
|
518 /// before the branch statement). If it cannot move, then these blocks cannot
|
|
|
519 /// be merged.
|
|
|
520 ///
|
|
|
521 /// Note that there is no analysis for moving instructions past the fall-through
|
|
|
522 /// blocks because they are confirmed to be empty. An assert is thrown if they
|
|
|
523 /// are not.
|
|
|
524 ///
|
|
|
525 /// \param[in] SourceRegion The candidate to move statements from
|
|
|
526 /// \param[in] TargetRegion The candidate to move statements to
|
|
|
527 /// \return true if all instructions in SourceRegion.BranchBlock can be merged
|
|
|
528 /// into a block in TargetRegion, false otherwise.
|
|
|
529 ///
|
|
|
530 bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
|
|
|
531 CoalescingCandidateInfo &TargetRegion) const {
|
|
|
532 if (!validateCandidates(SourceRegion, TargetRegion))
|
|
|
533 return false;
|
|
|
534
|
|
|
535 // Walk through PHI nodes first and see if they force the merge into the
|
|
|
536 // SourceRegion.BranchTargetBlock.
|
|
|
537 for (MachineBasicBlock::iterator
|
|
|
538 I = SourceRegion.BranchBlock->instr_begin(),
|
|
|
539 E = SourceRegion.BranchBlock->getFirstNonPHI();
|
|
|
540 I != E; ++I) {
|
|
|
541 for (auto &Def : I->defs())
|
|
|
542 for (auto &Use : MRI->use_instructions(Def.getReg())) {
|
|
|
543 if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {
|
|
|
544 DEBUG(dbgs() << "PHI " << *I << " defines register used in another "
|
|
|
545 "PHI within branch target block -- can't merge\n");
|
|
|
546 NumPHINotMoved++;
|
|
|
547 return false;
|
|
|
548 }
|
|
|
549 if (Use.getParent() == SourceRegion.BranchBlock) {
|
|
|
550 DEBUG(dbgs() << "PHI " << *I
|
|
|
551 << " defines register used in this "
|
|
|
552 "block -- all must move down\n");
|
|
|
553 SourceRegion.MustMoveDown = true;
|
|
|
554 }
|
|
|
555 }
|
|
|
556 }
|
|
|
557
|
|
|
558 // Walk through the MI to see if they should be merged into
|
|
|
559 // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)
|
|
|
560 for (MachineBasicBlock::iterator
|
|
|
561 I = SourceRegion.BranchBlock->getFirstNonPHI(),
|
|
|
562 E = SourceRegion.BranchBlock->end();
|
|
|
563 I != E; ++I) {
|
|
|
564 if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {
|
|
|
565 DEBUG(dbgs() << "Instruction " << *I
|
|
|
566 << " cannot move down - must move up!\n");
|
|
|
567 SourceRegion.MustMoveUp = true;
|
|
|
568 }
|
|
|
569 if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {
|
|
|
570 DEBUG(dbgs() << "Instruction " << *I
|
|
|
571 << " cannot move up - must move down!\n");
|
|
|
572 SourceRegion.MustMoveDown = true;
|
|
|
573 }
|
|
|
574 }
|
|
|
575
|
|
|
576 return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true;
|
|
|
577 }
|
|
|
578
|
|
|
579 /// Merge the instructions from SourceRegion.BranchBlock,
|
|
|
580 /// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
|
|
|
581 /// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
|
|
|
582 /// TargetRegion.FallThroughBlock respectively.
|
|
|
583 ///
|
|
|
584 /// The successors for blocks in TargetRegion will be updated to use the
|
|
|
585 /// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
|
|
|
586 /// will be removed from the function.
|
|
|
587 ///
|
|
|
588 /// A region consists of a BranchBlock, a FallThroughBlock, and a
|
|
|
589 /// BranchTargetBlock. Branch coalesce works on patterns where the
|
|
|
590 /// TargetRegion's BranchTargetBlock must also be the SourceRegions's
|
|
|
591 /// BranchBlock.
|
|
|
592 ///
|
|
|
593 /// Before mergeCandidates:
|
|
|
594 ///
|
|
|
595 /// +---------------------------+
|
|
|
596 /// | TargetRegion.BranchBlock |
|
|
|
597 /// +---------------------------+
|
|
|
598 /// / |
|
|
|
599 /// / +--------------------------------+
|
|
|
600 /// | | TargetRegion.FallThroughBlock |
|
|
|
601 /// \ +--------------------------------+
|
|
|
602 /// \ |
|
|
|
603 /// +----------------------------------+
|
|
|
604 /// | TargetRegion.BranchTargetBlock |
|
|
|
605 /// | SourceRegion.BranchBlock |
|
|
|
606 /// +----------------------------------+
|
|
|
607 /// / |
|
|
|
608 /// / +--------------------------------+
|
|
|
609 /// | | SourceRegion.FallThroughBlock |
|
|
|
610 /// \ +--------------------------------+
|
|
|
611 /// \ |
|
|
|
612 /// +----------------------------------+
|
|
|
613 /// | SourceRegion.BranchTargetBlock |
|
|
|
614 /// +----------------------------------+
|
|
|
615 ///
|
|
|
616 /// After mergeCandidates:
|
|
|
617 ///
|
|
|
618 /// +-----------------------------+
|
|
|
619 /// | TargetRegion.BranchBlock |
|
|
|
620 /// | SourceRegion.BranchBlock |
|
|
|
621 /// +-----------------------------+
|
|
|
622 /// / |
|
|
|
623 /// / +---------------------------------+
|
|
|
624 /// | | TargetRegion.FallThroughBlock |
|
|
|
625 /// | | SourceRegion.FallThroughBlock |
|
|
|
626 /// \ +---------------------------------+
|
|
|
627 /// \ |
|
|
|
628 /// +----------------------------------+
|
|
|
629 /// | SourceRegion.BranchTargetBlock |
|
|
|
630 /// +----------------------------------+
|
|
|
631 ///
|
|
|
632 /// \param[in] SourceRegion The candidate to move blocks from
|
|
|
633 /// \param[in] TargetRegion The candidate to move blocks to
|
|
|
634 ///
|
|
|
635 bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
|
|
|
636 CoalescingCandidateInfo &TargetRegion) {
|
|
|
637
|
|
|
638 if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
|
|
|
639 llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");
|
|
|
640 return false;
|
|
|
641 }
|
|
|
642
|
|
|
643 if (!validateCandidates(SourceRegion, TargetRegion))
|
|
|
644 return false;
|
|
|
645
|
|
|
646 // Start the merging process by first handling the BranchBlock.
|
|
|
647 // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block
|
|
|
648 moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
|
|
|
649
|
|
|
650 // Move remaining instructions in SourceRegion.BranchBlock into
|
|
|
651 // TargetRegion.BranchBlock
|
|
|
652 MachineBasicBlock::iterator firstInstr =
|
|
|
653 SourceRegion.BranchBlock->getFirstNonPHI();
|
|
|
654 MachineBasicBlock::iterator lastInstr =
|
|
|
655 SourceRegion.BranchBlock->getFirstTerminator();
|
|
|
656
|
|
|
657 MachineBasicBlock *Source = SourceRegion.MustMoveDown
|
|
|
658 ? SourceRegion.BranchTargetBlock
|
|
|
659 : TargetRegion.BranchBlock;
|
|
|
660
|
|
|
661 MachineBasicBlock::iterator Target =
|
|
|
662 SourceRegion.MustMoveDown
|
|
|
663 ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
|
|
|
664 : TargetRegion.BranchBlock->getFirstTerminator();
|
|
|
665
|
|
|
666 Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
|
|
|
667
|
|
|
668 // Once PHI and instructions have been moved we need to clean up the
|
|
|
669 // control flow.
|
|
|
670
|
|
|
671 // Remove SourceRegion.FallThroughBlock before transferring successors of
|
|
|
672 // SourceRegion.BranchBlock to TargetRegion.BranchBlock.
|
|
|
673 SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
|
|
|
674 TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
|
|
|
675 SourceRegion.BranchBlock);
|
|
|
676 // Update branch in TargetRegion.BranchBlock to jump to
|
|
|
677 // SourceRegion.BranchTargetBlock
|
|
|
678 // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.
|
|
|
679 TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
|
|
|
680 SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
|
|
|
681 // Remove the branch statement(s) in SourceRegion.BranchBlock
|
|
|
682 MachineBasicBlock::iterator I =
|
|
|
683 SourceRegion.BranchBlock->terminators().begin();
|
|
|
684 while (I != SourceRegion.BranchBlock->terminators().end()) {
|
|
|
685 MachineInstr &CurrInst = *I;
|
|
|
686 ++I;
|
|
|
687 if (CurrInst.isBranch())
|
|
|
688 CurrInst.eraseFromParent();
|
|
|
689 }
|
|
|
690
|
|
|
691 // Fall-through block should be empty since this is part of the condition
|
|
|
692 // to coalesce the branches.
|
|
|
693 assert(TargetRegion.FallThroughBlock->empty() &&
|
|
|
694 "FallThroughBlocks should be empty!");
|
|
|
695
|
|
|
696 // Transfer successor information and move PHIs down to the
|
|
|
697 // branch-taken block.
|
|
|
698 TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
|
|
|
699 SourceRegion.FallThroughBlock);
|
|
|
700 TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
|
|
|
701
|
|
|
702 // Remove the blocks from the function.
|
|
|
703 assert(SourceRegion.BranchBlock->empty() &&
|
|
|
704 "Expecting branch block to be empty!");
|
|
|
705 SourceRegion.BranchBlock->eraseFromParent();
|
|
|
706
|
|
|
707 assert(SourceRegion.FallThroughBlock->empty() &&
|
|
|
708 "Expecting fall-through block to be empty!\n");
|
|
|
709 SourceRegion.FallThroughBlock->eraseFromParent();
|
|
|
710
|
|
|
711 NumBlocksCoalesced++;
|
|
|
712 return true;
|
|
|
713 }
|
|
|
714
|
|
|
715 bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
|
|
|
716
|
|
|
717 if (skipFunction(*MF.getFunction()) || MF.empty())
|
|
|
718 return false;
|
|
|
719
|
|
|
720 bool didSomething = false;
|
|
|
721
|
|
|
722 DEBUG(dbgs() << "******** Branch Coalescing ********\n");
|
|
|
723 initialize(MF);
|
|
|
724
|
|
|
725 DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
|
|
|
726
|
|
|
727 CoalescingCandidateInfo Cand1, Cand2;
|
|
|
728 // Walk over blocks and find candidates to merge
|
|
|
729 // Continue trying to merge with the first candidate found, as long as merging
|
|
|
730 // is successfull.
|
|
|
731 for (MachineBasicBlock &MBB : MF) {
|
|
|
732 bool MergedCandidates = false;
|
|
|
733 do {
|
|
|
734 MergedCandidates = false;
|
|
|
735 Cand1.clear();
|
|
|
736 Cand2.clear();
|
|
|
737
|
|
|
738 Cand1.BranchBlock = &MBB;
|
|
|
739
|
|
|
740 // If unable to coalesce the branch, then continue to next block
|
|
|
741 if (!canCoalesceBranch(Cand1))
|
|
|
742 break;
|
|
|
743
|
|
|
744 Cand2.BranchBlock = Cand1.BranchTargetBlock;
|
|
|
745 if (!canCoalesceBranch(Cand2))
|
|
|
746 break;
|
|
|
747
|
|
|
748 // Sanity check
|
|
|
749 // The branch-taken block of the second candidate should post-dominate the
|
|
|
750 // first candidate
|
|
|
751 assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
|
|
|
752 "Branch-taken block should post-dominate first candidate");
|
|
|
753
|
|
|
754 if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
|
|
|
755 DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber() << " and "
|
|
|
756 << Cand2.BranchBlock->getNumber()
|
|
|
757 << " have different branches\n");
|
|
|
758 break;
|
|
|
759 }
|
|
|
760 if (!canMerge(Cand2, Cand1)) {
|
|
|
761 DEBUG(dbgs() << "Cannot merge blocks " << Cand1.BranchBlock->getNumber()
|
|
|
762 << " and " << Cand2.BranchBlock->getNumber() << "\n");
|
|
|
763 NumBlocksNotCoalesced++;
|
|
|
764 continue;
|
|
|
765 }
|
|
|
766 DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
|
|
|
767 << " and " << Cand1.BranchTargetBlock->getNumber() << "\n");
|
|
|
768 MergedCandidates = mergeCandidates(Cand2, Cand1);
|
|
|
769 if (MergedCandidates)
|
|
|
770 didSomething = true;
|
|
|
771
|
|
|
772 DEBUG(dbgs() << "Function after merging: "; MF.dump(); dbgs() << "\n");
|
|
|
773 } while (MergedCandidates);
|
|
|
774 }
|
|
|
775
|
|
|
776 #ifndef NDEBUG
|
|
|
777 // Verify MF is still valid after branch coalescing
|
|
|
778 if (didSomething)
|
|
|
779 MF.verify(nullptr, "Error in code produced by branch coalescing");
|
|
|
780 #endif // NDEBUG
|
|
|
781
|
|
|
782 DEBUG(dbgs() << "Finished Branch Coalescing\n");
|
|
|
783 return didSomething;
|
|
|
784 }
|
