Page MenuHomePhabricator
Differential D32776 Diff 110607 lib/Target/PowerPC/PPCBranchCoalescing.cpp

Changeset View

Standalone View

View Options

lib/Target/PowerPC/PPCBranchCoalescing.cpp

  • This file was added.
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​ DEBUG(dbgs() << "Op1 and Op2 are identical!\n");
347​ continue;
348​ }
349​
350​ // If the operands are not identical, but are registers, check to see if the
351​ // definition of the register produces the same value. If they produce the
352​ // same value, consider them to be identical.
353​ if (Op1.isReg() && Op2.isReg() &&
354​ TargetRegisterInfo::isVirtualRegister(Op1.getReg()) &&
355​ TargetRegisterInfo::isVirtualRegister(Op2.getReg())) {
356​ MachineInstr *Op1Def = MRI->getVRegDef(Op1.getReg());
357​ MachineInstr *Op2Def = MRI->getVRegDef(Op2.getReg());
358​ if (TII->produceSameValue(*Op1Def, *Op2Def, MRI)) {
359​ DEBUG(dbgs() << "Op1Def: " << *Op1Def << " and " << *Op2Def
360​ << " produce the same value!\n");
361​ } else {
362​ DEBUG(dbgs() << "Operands produce different values\n");
363​ return false;
364​ }
365​ } else {
366​ DEBUG(dbgs() << "The operands are not provably identical.\n");
367​ return false;
368​ }
369​ }
370​ return true;
371​}
372​
373​///
374​/// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
375​/// and update them to refer to the new block. PHI node ordering
376​/// cannot be assumed so it does not matter where the PHI instructions
377​/// are moved to in TargetMBB.
378​///
379​/// \param[in] SourceMBB block to move PHI instructions from
380​/// \param[in] TargetMBB block to move PHI instructions to
381​///
382​void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
383​ MachineBasicBlock *TargetMBB) {
384​
385​ MachineBasicBlock::iterator MI = SourceMBB->begin();
386​ MachineBasicBlock::iterator ME = SourceMBB->getFirstNonPHI();
387​
388​ if (MI == ME) {
389​ DEBUG(dbgs() << "SourceMBB contains no PHI instructions.\n");
390​ return;
391​ }
392​
393​ // Update all PHI instructions in SourceMBB and move to top of TargetMBB
394​ for (MachineBasicBlock::iterator Iter = MI; Iter != ME; Iter++) {
395​ MachineInstr &PHIInst = *Iter;
396​ for (unsigned i = 2, e = PHIInst.getNumOperands() + 1; i != e; i += 2) {
397​ MachineOperand &MO = PHIInst.getOperand(i);
398​ if (MO.getMBB() == SourceMBB)
399​ MO.setMBB(TargetMBB);
400​ }
401​ }
402​ TargetMBB->splice(TargetMBB->begin(), SourceMBB, MI, ME);
403​}
404​
405​///
406​/// This function checks if MI can be moved to the beginning of the TargetMBB
407​/// following PHI instructions. A MI instruction can be moved to beginning of
408​/// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
409​///
410​/// \param[in] MI the machine instruction to move.
411​/// \param[in] TargetMBB the machine basic block to move to
412​/// \return true if it is safe to move MI to beginning of TargetMBB,
413​/// false otherwise.
414​///
415​bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
416​ const MachineBasicBlock &TargetMBB
417​ ) const {
418​
419​ DEBUG(dbgs() << "Checking if " << MI << " can move to beginning of "
420​ << TargetMBB.getNumber() << "\n");
421​
422​ for (auto &Def : MI.defs()) { // Looking at Def
423​ for (auto &Use : MRI->use_instructions(Def.getReg())) {
424​ if (Use.isPHI() && Use.getParent() == &TargetMBB) {
425​ DEBUG(dbgs() << " *** used in a PHI -- cannot move ***\n");
426​ return false;
427​ }
428​ }
429​ }
430​
431​ DEBUG(dbgs() << " Safe to move to the beginning.\n");
432​ return true;
433​}
434​
435​///
436​/// This function checks if MI can be moved to the end of the TargetMBB,
437​/// immediately before the first terminator. A MI instruction can be moved
438​/// to then end of the TargetMBB if no PHI node defines what MI uses within
439​/// it's own MBB.
440​///
441​/// \param[in] MI the machine instruction to move.
442​/// \param[in] TargetMBB the machine basic block to move to
443​/// \return true if it is safe to move MI to end of TargetMBB,
444​/// false otherwise.
445​///
446​bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,
447​ const MachineBasicBlock &TargetMBB
448​ ) const {
449​
450​ DEBUG(dbgs() << "Checking if " << MI << " can move to end of "
451​ << TargetMBB.getNumber() << "\n");
452​
453​ for (auto &Use : MI.uses()) {
454​ if (Use.isReg() && TargetRegisterInfo::isVirtualRegister(Use.getReg())) {
455​ MachineInstr *DefInst = MRI->getVRegDef(Use.getReg());
456​ if (DefInst->isPHI() && DefInst->getParent() == MI.getParent()) {
457​ DEBUG(dbgs() << " *** Cannot move this instruction ***\n");
458​ return false;
459​ } else {
460​ DEBUG(dbgs() << " *** def is in another block -- safe to move!\n");
461​ }
462​ }
463​ }
464​
465​ DEBUG(dbgs() << " Safe to move to the end.\n");
466​ return true;
467​}
468​
469​///
470​/// This method checks to ensure the two coalescing candidates follows the
471​/// expected pattern required for coalescing.
472​///
473​/// \param[in] SourceRegion The candidate to move statements from
474​/// \param[in] TargetRegion The candidate to move statements to
475​/// \return true if all instructions in SourceRegion.BranchBlock can be merged
476​/// into a block in TargetRegion; false otherwise.
477​///
478​bool PPCBranchCoalescing::validateCandidates(
479​ CoalescingCandidateInfo &SourceRegion,
480​ CoalescingCandidateInfo &TargetRegion) const {
481​
482​ if (TargetRegion.BranchTargetBlock != SourceRegion.BranchBlock)
483​ llvm_unreachable("Expecting SourceRegion to immediately follow TargetRegion");
484​ else if (!MDT->dominates(TargetRegion.BranchBlock, SourceRegion.BranchBlock))
485​ llvm_unreachable("Expecting TargetRegion to dominate SourceRegion");
486​ else if (!MPDT->dominates(SourceRegion.BranchBlock, TargetRegion.BranchBlock))
487​ llvm_unreachable("Expecting SourceRegion to post-dominate TargetRegion");
488​ else if (!TargetRegion.FallThroughBlock->empty() ||
489​ !SourceRegion.FallThroughBlock->empty())
490​ llvm_unreachable("Expecting fall-through blocks to be empty");
491​
492​ return true;
493​}
494​
495​///
496​/// This method determines whether the two coalescing candidates can be merged.
497​/// In order to be merged, all instructions must be able to
498​/// 1. Move to the beginning of the SourceRegion.BranchTargetBlock;
499​/// 2. Move to the end of the TargetRegion.BranchBlock.
500​/// Merging involves moving the instructions in the
501​/// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
502​///
503​/// This function first try to move instructions from the
504​/// TargetRegion.BranchTargetBlock down, to the beginning of the
505​/// SourceRegion.BranchTargetBlock. This is not possible if any register defined
506​/// in TargetRegion.BranchTargetBlock is used in a PHI node in the
507​/// SourceRegion.BranchTargetBlock. In this case, check whether the statement
508​/// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
509​/// before the branch statement). If it cannot move, then these blocks cannot
510​/// be merged.
511​///
512​/// Note that there is no analysis for moving instructions past the fall-through
513​/// blocks because they are confirmed to be empty. An assert is thrown if they
514​/// are not.
515​///
516​/// \param[in] SourceRegion The candidate to move statements from
517​/// \param[in] TargetRegion The candidate to move statements to
518​/// \return true if all instructions in SourceRegion.BranchBlock can be merged
519​/// into a block in TargetRegion, false otherwise.
520​///
521​bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
522​ CoalescingCandidateInfo &TargetRegion) const {
523​ if (!validateCandidates(SourceRegion, TargetRegion))
524​ return false;
525​
526​ // Walk through PHI nodes first and see if they force the merge into the
527​ // SourceRegion.BranchTargetBlock.
528​ for (MachineBasicBlock::iterator
529​ I = SourceRegion.BranchBlock->instr_begin(),
530​ E = SourceRegion.BranchBlock->getFirstNonPHI();
531​ I != E; ++I) {
532​ for (auto &Def : I->defs())
533​ for (auto &Use : MRI->use_instructions(Def.getReg())) {
534​ if (Use.isPHI() && Use.getParent() == SourceRegion.BranchTargetBlock) {
535​ DEBUG(dbgs() << "PHI " << *I << " defines register used in another "
536​ "PHI within branch target block -- can't merge\n");
537​ NumPHINotMoved++;
538​ return false;
539​ }
540​ if (Use.getParent() == SourceRegion.BranchBlock) {
541​ DEBUG(dbgs() << "PHI " << *I
542​ << " defines register used in this "
543​ "block -- all must move down\n");
544​ SourceRegion.MustMoveDown = true;
545​ }
546​ }
547​ }
548​
549​ // Walk through the MI to see if they should be merged into
550​ // TargetRegion.BranchBlock (up) or SourceRegion.BranchTargetBlock (down)
551​ for (MachineBasicBlock::iterator
552​ I = SourceRegion.BranchBlock->getFirstNonPHI(),
553​ E = SourceRegion.BranchBlock->end();
554​ I != E; ++I) {
555​ if (!canMoveToBeginning(*I, *SourceRegion.BranchTargetBlock)) {
556​ DEBUG(dbgs() << "Instruction " << *I
557​ << " cannot move down - must move up!\n");
558​ SourceRegion.MustMoveUp = true;
559​ }
560​ if (!canMoveToEnd(*I, *TargetRegion.BranchBlock)) {
561​ DEBUG(dbgs() << "Instruction " << *I
562​ << " cannot move up - must move down!\n");
563​ SourceRegion.MustMoveDown = true;
564​ }
565​ }
566​
567​ return (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) ? false : true;
568​}
569​
570​/// Merge the instructions from SourceRegion.BranchBlock,
571​/// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
572​/// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
573​/// TargetRegion.FallThroughBlock respectively.
574​///
575​/// The successors for blocks in TargetRegion will be updated to use the
576​/// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
577​/// will be removed from the function.
578​///
579​/// A region consists of a BranchBlock, a FallThroughBlock, and a
580​/// BranchTargetBlock. Branch coalesce works on patterns where the
581​/// TargetRegion's BranchTargetBlock must also be the SourceRegions's
582​/// BranchBlock.
583​///
584​/// Before mergeCandidates:
585​///
586​/// +---------------------------+
587​/// | TargetRegion.BranchBlock |
588​/// +---------------------------+
589​/// / |
590​/// / +--------------------------------+
591​/// | | TargetRegion.FallThroughBlock |
592​/// \ +--------------------------------+
593​/// \ |
594​/// +----------------------------------+
595​/// | TargetRegion.BranchTargetBlock |
596​/// | SourceRegion.BranchBlock |
597​/// +----------------------------------+
598​/// / |
599​/// / +--------------------------------+
600​/// | | SourceRegion.FallThroughBlock |
601​/// \ +--------------------------------+
602​/// \ |
603​/// +----------------------------------+
604​/// | SourceRegion.BranchTargetBlock |
605​/// +----------------------------------+
606​///
607​/// After mergeCandidates:
608​///
609​/// +-----------------------------+
610​/// | TargetRegion.BranchBlock |
611​/// | SourceRegion.BranchBlock |
612​/// +-----------------------------+
613​/// / |
614​/// / +---------------------------------+
615​/// | | TargetRegion.FallThroughBlock |
616​/// | | SourceRegion.FallThroughBlock |
617​/// \ +---------------------------------+
618​/// \ |
619​/// +----------------------------------+
620​/// | SourceRegion.BranchTargetBlock |
621​/// +----------------------------------+
622​///
623​/// \param[in] SourceRegion The candidate to move blocks from
624​/// \param[in] TargetRegion The candidate to move blocks to
625​///
626​bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
627​ CoalescingCandidateInfo &TargetRegion) {
628​
629​ if (SourceRegion.MustMoveUp && SourceRegion.MustMoveDown) {
630​ llvm_unreachable("Cannot have both MustMoveDown and MustMoveUp set!");
631​ return false;
632​ }
633​
634​ if (!validateCandidates(SourceRegion, TargetRegion))
635​ return false;
636​
637​ // Start the merging process by first handling the BranchBlock.
638​ // Move any PHIs in SourceRegion.BranchBlock down to the branch-taken block
639​ moveAndUpdatePHIs(SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
640​
641​ // Move remaining instructions in SourceRegion.BranchBlock into
642​ // TargetRegion.BranchBlock
643​ MachineBasicBlock::iterator firstInstr =
644​ SourceRegion.BranchBlock->getFirstNonPHI();
645​ MachineBasicBlock::iterator lastInstr =
646​ SourceRegion.BranchBlock->getFirstTerminator();
647​
648​ MachineBasicBlock *Source = SourceRegion.MustMoveDown
649​ ? SourceRegion.BranchTargetBlock
650​ : TargetRegion.BranchBlock;
651​
652​ MachineBasicBlock::iterator Target =
653​ SourceRegion.MustMoveDown
654​ ? SourceRegion.BranchTargetBlock->getFirstNonPHI()
655​ : TargetRegion.BranchBlock->getFirstTerminator();
656​
657​ Source->splice(Target, SourceRegion.BranchBlock, firstInstr, lastInstr);
658​
659​ // Once PHI and instructions have been moved we need to clean up the
660​ // control flow.
661​
662​ // Remove SourceRegion.FallThroughBlock before transferring successors of
663​ // SourceRegion.BranchBlock to TargetRegion.BranchBlock.
664​ SourceRegion.BranchBlock->removeSuccessor(SourceRegion.FallThroughBlock);
665​ TargetRegion.BranchBlock->transferSuccessorsAndUpdatePHIs(
666​ SourceRegion.BranchBlock);
667​ // Update branch in TargetRegion.BranchBlock to jump to
668​ // SourceRegion.BranchTargetBlock
669​ // In this case, TargetRegion.BranchTargetBlock == SourceRegion.BranchBlock.
670​ TargetRegion.BranchBlock->ReplaceUsesOfBlockWith(
671​ SourceRegion.BranchBlock, SourceRegion.BranchTargetBlock);
672​ // Remove the branch statement(s) in SourceRegion.BranchBlock
673​ MachineBasicBlock::iterator I =
674​ SourceRegion.BranchBlock->terminators().begin();
675​ while (I != SourceRegion.BranchBlock->terminators().end()) {
676​ MachineInstr &CurrInst = *I;
677​ ++I;
678​ if (CurrInst.isBranch())
679​ CurrInst.eraseFromParent();
680​ }
681​
682​ // Fall-through block should be empty since this is part of the condition
683​ // to coalesce the branches.
684​ assert(TargetRegion.FallThroughBlock->empty() &&
685​ "FallThroughBlocks should be empty!");
686​
687​ // Transfer successor information and move PHIs down to the
688​ // branch-taken block.
689​ TargetRegion.FallThroughBlock->transferSuccessorsAndUpdatePHIs(
690​ SourceRegion.FallThroughBlock);
691​ TargetRegion.FallThroughBlock->removeSuccessor(SourceRegion.BranchBlock);
692​
693​ // Remove the blocks from the function.
694​ assert(SourceRegion.BranchBlock->empty() &&
695​ "Expecting branch block to be empty!");
696​ SourceRegion.BranchBlock->eraseFromParent();
697​
698​ assert(SourceRegion.FallThroughBlock->empty() &&
699​ "Expecting fall-through block to be empty!\n");
700​ SourceRegion.FallThroughBlock->eraseFromParent();
701​
702​ NumBlocksCoalesced++;
703​ return true;
704​}
705​
706​bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) {
707​
708​ if (skipFunction(*MF.getFunction()) || MF.empty())
709​ return false;
710​
711​ bool didSomething = false;
712​
713​ DEBUG(dbgs() << "******** Branch Coalescing ********\n");
714​ initialize(MF);
715​
716​ DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
717​
718​ CoalescingCandidateInfo Cand1, Cand2;
719​ // Walk over blocks and find candidates to merge
720​ // Continue trying to merge with the first candidate found, as long as merging
721​ // is successfull.
722​ for (MachineBasicBlock &MBB : MF) {
723​ bool MergedCandidates = false;
724​ do {
725​ MergedCandidates = false;
726​ Cand1.clear();
727​ Cand2.clear();
728​
729​ Cand1.BranchBlock = &MBB;
730​
731​ // If unable to coalesce the branch, then continue to next block
732​ if (!canCoalesceBranch(Cand1))
733​ break;
734​
735​ Cand2.BranchBlock = Cand1.BranchTargetBlock;
736​ if (!canCoalesceBranch(Cand2))
737​ break;
738​
739​ // Sanity check
740​ // The branch-taken block of the second candidate should post-dominate the
741​ // first candidate
742​ assert(MPDT->dominates(Cand2.BranchTargetBlock, Cand1.BranchBlock) &&
743​ "Branch-taken block should post-dominate first candidate");
744​
745​ if (!identicalOperands(Cand1.Cond, Cand2.Cond)) {
746​ DEBUG(dbgs() << "Blocks " << Cand1.BranchBlock->getNumber() << " and "
747​ << Cand2.BranchBlock->getNumber()
748​ << " have different branches\n");
749​ break;
750​ }
751​ if (!canMerge(Cand2, Cand1)) {
752​ DEBUG(dbgs() << "Cannot merge blocks " << Cand1.BranchBlock->getNumber()
753​ << " and " << Cand2.BranchBlock->getNumber() << "\n");
754​ NumBlocksNotCoalesced++;
755​ continue;
756​ }
757​ DEBUG(dbgs() << "Merging blocks " << Cand1.BranchBlock->getNumber()
758​ << " and " << Cand1.BranchTargetBlock->getNumber() << "\n");
759​ MergedCandidates = mergeCandidates(Cand2, Cand1);
760​ if (MergedCandidates)
761​ didSomething = true;
762​
763​ DEBUG(dbgs() << "Function after merging: "; MF.dump(); dbgs() << "\n");
764​ } while (MergedCandidates);
765​ }
766​
767​#ifndef NDEBUG
768​ // Verify MF is still valid after branch coalescing
769​ if (didSomething)
770​ MF.verify(nullptr, "Error in code produced by branch coalescing");
771​#endif // NDEBUG
772​
773​ DEBUG(dbgs() << "Finished Branch Coalescing\n");
774​ return didSomething;
775​}