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