1 //===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass duplicates basic blocks ending in unconditional branches into
11 // the tails of their predecessors.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "tailduplication"
16 #include "llvm/Function.h"
17 #include "llvm/CodeGen/Passes.h"
18 #include "llvm/CodeGen/MachineModuleInfo.h"
19 #include "llvm/CodeGen/MachineFunctionPass.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/MachineSSAUpdater.h"
23 #include "llvm/Target/TargetInstrInfo.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/SetVector.h"
30 #include "llvm/ADT/Statistic.h"
33 STATISTIC(NumTails
, "Number of tails duplicated");
34 STATISTIC(NumTailDups
, "Number of tail duplicated blocks");
35 STATISTIC(NumInstrDups
, "Additional instructions due to tail duplication");
36 STATISTIC(NumDeadBlocks
, "Number of dead blocks removed");
37 STATISTIC(NumAddedPHIs
, "Number of phis added");
39 // Heuristic for tail duplication.
40 static cl::opt
<unsigned>
41 TailDuplicateSize("tail-dup-size",
42 cl::desc("Maximum instructions to consider tail duplicating"),
43 cl::init(2), cl::Hidden
);
46 TailDupVerify("tail-dup-verify",
47 cl::desc("Verify sanity of PHI instructions during taildup"),
48 cl::init(false), cl::Hidden
);
50 static cl::opt
<unsigned>
51 TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden
);
53 typedef std::vector
<std::pair
<MachineBasicBlock
*,unsigned> > AvailableValsTy
;
56 /// TailDuplicatePass - Perform tail duplication.
57 class TailDuplicatePass
: public MachineFunctionPass
{
59 const TargetInstrInfo
*TII
;
60 MachineModuleInfo
*MMI
;
61 MachineRegisterInfo
*MRI
;
63 // SSAUpdateVRs - A list of virtual registers for which to update SSA form.
64 SmallVector
<unsigned, 16> SSAUpdateVRs
;
66 // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of
67 // source virtual registers.
68 DenseMap
<unsigned, AvailableValsTy
> SSAUpdateVals
;
72 explicit TailDuplicatePass(bool PreRA
) :
73 MachineFunctionPass(ID
), PreRegAlloc(PreRA
) {}
75 virtual bool runOnMachineFunction(MachineFunction
&MF
);
76 virtual const char *getPassName() const { return "Tail Duplication"; }
79 void AddSSAUpdateEntry(unsigned OrigReg
, unsigned NewReg
,
80 MachineBasicBlock
*BB
);
81 void ProcessPHI(MachineInstr
*MI
, MachineBasicBlock
*TailBB
,
82 MachineBasicBlock
*PredBB
,
83 DenseMap
<unsigned, unsigned> &LocalVRMap
,
84 SmallVector
<std::pair
<unsigned,unsigned>, 4> &Copies
,
85 const DenseSet
<unsigned> &UsedByPhi
);
86 void DuplicateInstruction(MachineInstr
*MI
,
87 MachineBasicBlock
*TailBB
,
88 MachineBasicBlock
*PredBB
,
90 DenseMap
<unsigned, unsigned> &LocalVRMap
,
91 const DenseSet
<unsigned> &UsedByPhi
);
92 void UpdateSuccessorsPHIs(MachineBasicBlock
*FromBB
, bool isDead
,
93 SmallVector
<MachineBasicBlock
*, 8> &TDBBs
,
94 SmallSetVector
<MachineBasicBlock
*, 8> &Succs
);
95 bool TailDuplicateBlocks(MachineFunction
&MF
);
96 bool shouldTailDuplicate(const MachineFunction
&MF
,
97 MachineBasicBlock
&TailBB
);
98 bool TailDuplicate(MachineBasicBlock
*TailBB
, MachineFunction
&MF
,
99 SmallVector
<MachineBasicBlock
*, 8> &TDBBs
,
100 SmallVector
<MachineInstr
*, 16> &Copies
);
101 void RemoveDeadBlock(MachineBasicBlock
*MBB
);
104 char TailDuplicatePass::ID
= 0;
107 FunctionPass
*llvm::createTailDuplicatePass(bool PreRegAlloc
) {
108 return new TailDuplicatePass(PreRegAlloc
);
111 bool TailDuplicatePass::runOnMachineFunction(MachineFunction
&MF
) {
112 TII
= MF
.getTarget().getInstrInfo();
113 MRI
= &MF
.getRegInfo();
114 MMI
= getAnalysisIfAvailable
<MachineModuleInfo
>();
116 bool MadeChange
= false;
117 while (TailDuplicateBlocks(MF
))
123 static void VerifyPHIs(MachineFunction
&MF
, bool CheckExtra
) {
124 for (MachineFunction::iterator I
= ++MF
.begin(), E
= MF
.end(); I
!= E
; ++I
) {
125 MachineBasicBlock
*MBB
= I
;
126 SmallSetVector
<MachineBasicBlock
*, 8> Preds(MBB
->pred_begin(),
128 MachineBasicBlock::iterator MI
= MBB
->begin();
129 while (MI
!= MBB
->end()) {
132 for (SmallSetVector
<MachineBasicBlock
*, 8>::iterator PI
= Preds
.begin(),
133 PE
= Preds
.end(); PI
!= PE
; ++PI
) {
134 MachineBasicBlock
*PredBB
= *PI
;
136 for (unsigned i
= 1, e
= MI
->getNumOperands(); i
!= e
; i
+= 2) {
137 MachineBasicBlock
*PHIBB
= MI
->getOperand(i
+1).getMBB();
138 if (PHIBB
== PredBB
) {
144 dbgs() << "Malformed PHI in BB#" << MBB
->getNumber() << ": " << *MI
;
145 dbgs() << " missing input from predecessor BB#"
146 << PredBB
->getNumber() << '\n';
151 for (unsigned i
= 1, e
= MI
->getNumOperands(); i
!= e
; i
+= 2) {
152 MachineBasicBlock
*PHIBB
= MI
->getOperand(i
+1).getMBB();
153 if (CheckExtra
&& !Preds
.count(PHIBB
)) {
154 // This is not a hard error.
155 dbgs() << "Warning: malformed PHI in BB#" << MBB
->getNumber()
157 dbgs() << " extra input from predecessor BB#"
158 << PHIBB
->getNumber() << '\n';
160 if (PHIBB
->getNumber() < 0) {
161 dbgs() << "Malformed PHI in BB#" << MBB
->getNumber() << ": " << *MI
;
162 dbgs() << " non-existing BB#" << PHIBB
->getNumber() << '\n';
171 /// TailDuplicateBlocks - Look for small blocks that are unconditionally
172 /// branched to and do not fall through. Tail-duplicate their instructions
173 /// into their predecessors to eliminate (dynamic) branches.
174 bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction
&MF
) {
175 bool MadeChange
= false;
177 if (PreRegAlloc
&& TailDupVerify
) {
178 DEBUG(dbgs() << "\n*** Before tail-duplicating\n");
179 VerifyPHIs(MF
, true);
182 SmallVector
<MachineInstr
*, 8> NewPHIs
;
183 MachineSSAUpdater
SSAUpdate(MF
, &NewPHIs
);
185 for (MachineFunction::iterator I
= ++MF
.begin(), E
= MF
.end(); I
!= E
; ) {
186 MachineBasicBlock
*MBB
= I
++;
188 if (NumTails
== TailDupLimit
)
191 // Save the successors list.
192 SmallSetVector
<MachineBasicBlock
*, 8> Succs(MBB
->succ_begin(),
195 SmallVector
<MachineBasicBlock
*, 8> TDBBs
;
196 SmallVector
<MachineInstr
*, 16> Copies
;
197 if (TailDuplicate(MBB
, MF
, TDBBs
, Copies
)) {
200 // TailBB's immediate successors are now successors of those predecessors
201 // which duplicated TailBB. Add the predecessors as sources to the PHI
203 bool isDead
= MBB
->pred_empty();
205 UpdateSuccessorsPHIs(MBB
, isDead
, TDBBs
, Succs
);
207 // If it is dead, remove it.
209 NumInstrDups
-= MBB
->size();
210 RemoveDeadBlock(MBB
);
215 if (!SSAUpdateVRs
.empty()) {
216 for (unsigned i
= 0, e
= SSAUpdateVRs
.size(); i
!= e
; ++i
) {
217 unsigned VReg
= SSAUpdateVRs
[i
];
218 SSAUpdate
.Initialize(VReg
);
220 // If the original definition is still around, add it as an available
222 MachineInstr
*DefMI
= MRI
->getVRegDef(VReg
);
223 MachineBasicBlock
*DefBB
= 0;
225 DefBB
= DefMI
->getParent();
226 SSAUpdate
.AddAvailableValue(DefBB
, VReg
);
229 // Add the new vregs as available values.
230 DenseMap
<unsigned, AvailableValsTy
>::iterator LI
=
231 SSAUpdateVals
.find(VReg
);
232 for (unsigned j
= 0, ee
= LI
->second
.size(); j
!= ee
; ++j
) {
233 MachineBasicBlock
*SrcBB
= LI
->second
[j
].first
;
234 unsigned SrcReg
= LI
->second
[j
].second
;
235 SSAUpdate
.AddAvailableValue(SrcBB
, SrcReg
);
238 // Rewrite uses that are outside of the original def's block.
239 MachineRegisterInfo::use_iterator UI
= MRI
->use_begin(VReg
);
240 while (UI
!= MRI
->use_end()) {
241 MachineOperand
&UseMO
= UI
.getOperand();
242 MachineInstr
*UseMI
= &*UI
;
244 if (UseMI
->getParent() == DefBB
&& !UseMI
->isPHI())
246 SSAUpdate
.RewriteUse(UseMO
);
250 SSAUpdateVRs
.clear();
251 SSAUpdateVals
.clear();
254 // Eliminate some of the copies inserted by tail duplication to maintain
256 for (unsigned i
= 0, e
= Copies
.size(); i
!= e
; ++i
) {
257 MachineInstr
*Copy
= Copies
[i
];
260 unsigned Dst
= Copy
->getOperand(0).getReg();
261 unsigned Src
= Copy
->getOperand(1).getReg();
262 MachineRegisterInfo::use_iterator UI
= MRI
->use_begin(Src
);
263 if (++UI
== MRI
->use_end()) {
264 // Copy is the only use. Do trivial copy propagation here.
265 MRI
->replaceRegWith(Dst
, Src
);
266 Copy
->eraseFromParent();
270 if (PreRegAlloc
&& TailDupVerify
)
271 VerifyPHIs(MF
, false);
275 NumAddedPHIs
+= NewPHIs
.size();
280 static bool isDefLiveOut(unsigned Reg
, MachineBasicBlock
*BB
,
281 const MachineRegisterInfo
*MRI
) {
282 for (MachineRegisterInfo::use_iterator UI
= MRI
->use_begin(Reg
),
283 UE
= MRI
->use_end(); UI
!= UE
; ++UI
) {
284 MachineInstr
*UseMI
= &*UI
;
285 if (UseMI
->getParent() != BB
)
291 static unsigned getPHISrcRegOpIdx(MachineInstr
*MI
, MachineBasicBlock
*SrcBB
) {
292 for (unsigned i
= 1, e
= MI
->getNumOperands(); i
!= e
; i
+= 2)
293 if (MI
->getOperand(i
+1).getMBB() == SrcBB
)
299 // Remember which registers are used by phis in this block. This is
300 // used to determine which registers are liveout while modifying the
301 // block (which is why we need to copy the information).
302 static void getRegsUsedByPHIs(const MachineBasicBlock
&BB
,
303 DenseSet
<unsigned> *UsedByPhi
) {
304 for(MachineBasicBlock::const_iterator I
= BB
.begin(), E
= BB
.end();
306 const MachineInstr
&MI
= *I
;
309 for (unsigned i
= 1, e
= MI
.getNumOperands(); i
!= e
; i
+= 2) {
310 unsigned SrcReg
= MI
.getOperand(i
).getReg();
311 UsedByPhi
->insert(SrcReg
);
316 /// AddSSAUpdateEntry - Add a definition and source virtual registers pair for
318 void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg
, unsigned NewReg
,
319 MachineBasicBlock
*BB
) {
320 DenseMap
<unsigned, AvailableValsTy
>::iterator LI
= SSAUpdateVals
.find(OrigReg
);
321 if (LI
!= SSAUpdateVals
.end())
322 LI
->second
.push_back(std::make_pair(BB
, NewReg
));
324 AvailableValsTy Vals
;
325 Vals
.push_back(std::make_pair(BB
, NewReg
));
326 SSAUpdateVals
.insert(std::make_pair(OrigReg
, Vals
));
327 SSAUpdateVRs
.push_back(OrigReg
);
331 /// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB.
332 /// Remember the source register that's contributed by PredBB and update SSA
334 void TailDuplicatePass::ProcessPHI(MachineInstr
*MI
,
335 MachineBasicBlock
*TailBB
,
336 MachineBasicBlock
*PredBB
,
337 DenseMap
<unsigned, unsigned> &LocalVRMap
,
338 SmallVector
<std::pair
<unsigned,unsigned>, 4> &Copies
,
339 const DenseSet
<unsigned> &RegsUsedByPhi
) {
340 unsigned DefReg
= MI
->getOperand(0).getReg();
341 unsigned SrcOpIdx
= getPHISrcRegOpIdx(MI
, PredBB
);
342 assert(SrcOpIdx
&& "Unable to find matching PHI source?");
343 unsigned SrcReg
= MI
->getOperand(SrcOpIdx
).getReg();
344 const TargetRegisterClass
*RC
= MRI
->getRegClass(DefReg
);
345 LocalVRMap
.insert(std::make_pair(DefReg
, SrcReg
));
347 // Insert a copy from source to the end of the block. The def register is the
348 // available value liveout of the block.
349 unsigned NewDef
= MRI
->createVirtualRegister(RC
);
350 Copies
.push_back(std::make_pair(NewDef
, SrcReg
));
351 if (isDefLiveOut(DefReg
, TailBB
, MRI
) || RegsUsedByPhi
.count(DefReg
))
352 AddSSAUpdateEntry(DefReg
, NewDef
, PredBB
);
354 // Remove PredBB from the PHI node.
355 MI
->RemoveOperand(SrcOpIdx
+1);
356 MI
->RemoveOperand(SrcOpIdx
);
357 if (MI
->getNumOperands() == 1)
358 MI
->eraseFromParent();
361 /// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update
362 /// the source operands due to earlier PHI translation.
363 void TailDuplicatePass::DuplicateInstruction(MachineInstr
*MI
,
364 MachineBasicBlock
*TailBB
,
365 MachineBasicBlock
*PredBB
,
367 DenseMap
<unsigned, unsigned> &LocalVRMap
,
368 const DenseSet
<unsigned> &UsedByPhi
) {
369 MachineInstr
*NewMI
= TII
->duplicate(MI
, MF
);
370 for (unsigned i
= 0, e
= NewMI
->getNumOperands(); i
!= e
; ++i
) {
371 MachineOperand
&MO
= NewMI
->getOperand(i
);
374 unsigned Reg
= MO
.getReg();
375 if (!TargetRegisterInfo::isVirtualRegister(Reg
))
378 const TargetRegisterClass
*RC
= MRI
->getRegClass(Reg
);
379 unsigned NewReg
= MRI
->createVirtualRegister(RC
);
381 LocalVRMap
.insert(std::make_pair(Reg
, NewReg
));
382 if (isDefLiveOut(Reg
, TailBB
, MRI
) || UsedByPhi
.count(Reg
))
383 AddSSAUpdateEntry(Reg
, NewReg
, PredBB
);
385 DenseMap
<unsigned, unsigned>::iterator VI
= LocalVRMap
.find(Reg
);
386 if (VI
!= LocalVRMap
.end())
387 MO
.setReg(VI
->second
);
390 PredBB
->insert(PredBB
->end(), NewMI
);
393 /// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor
394 /// blocks, the successors have gained new predecessors. Update the PHI
395 /// instructions in them accordingly.
397 TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock
*FromBB
, bool isDead
,
398 SmallVector
<MachineBasicBlock
*, 8> &TDBBs
,
399 SmallSetVector
<MachineBasicBlock
*,8> &Succs
) {
400 for (SmallSetVector
<MachineBasicBlock
*, 8>::iterator SI
= Succs
.begin(),
401 SE
= Succs
.end(); SI
!= SE
; ++SI
) {
402 MachineBasicBlock
*SuccBB
= *SI
;
403 for (MachineBasicBlock::iterator II
= SuccBB
->begin(), EE
= SuccBB
->end();
408 for (unsigned i
= 1, e
= II
->getNumOperands(); i
!= e
; i
+= 2) {
409 MachineOperand
&MO
= II
->getOperand(i
+1);
410 if (MO
.getMBB() == FromBB
) {
417 MachineOperand
&MO0
= II
->getOperand(Idx
);
418 unsigned Reg
= MO0
.getReg();
420 // Folded into the previous BB.
421 // There could be duplicate phi source entries. FIXME: Should sdisel
422 // or earlier pass fixed this?
423 for (unsigned i
= II
->getNumOperands()-2; i
!= Idx
; i
-= 2) {
424 MachineOperand
&MO
= II
->getOperand(i
+1);
425 if (MO
.getMBB() == FromBB
) {
426 II
->RemoveOperand(i
+1);
427 II
->RemoveOperand(i
);
433 // If Idx is set, the operands at Idx and Idx+1 must be removed.
434 // We reuse the location to avoid expensive RemoveOperand calls.
436 DenseMap
<unsigned,AvailableValsTy
>::iterator LI
=SSAUpdateVals
.find(Reg
);
437 if (LI
!= SSAUpdateVals
.end()) {
438 // This register is defined in the tail block.
439 for (unsigned j
= 0, ee
= LI
->second
.size(); j
!= ee
; ++j
) {
440 MachineBasicBlock
*SrcBB
= LI
->second
[j
].first
;
441 unsigned SrcReg
= LI
->second
[j
].second
;
443 II
->getOperand(Idx
).setReg(SrcReg
);
444 II
->getOperand(Idx
+1).setMBB(SrcBB
);
447 II
->addOperand(MachineOperand::CreateReg(SrcReg
, false));
448 II
->addOperand(MachineOperand::CreateMBB(SrcBB
));
452 // Live in tail block, must also be live in predecessors.
453 for (unsigned j
= 0, ee
= TDBBs
.size(); j
!= ee
; ++j
) {
454 MachineBasicBlock
*SrcBB
= TDBBs
[j
];
456 II
->getOperand(Idx
).setReg(Reg
);
457 II
->getOperand(Idx
+1).setMBB(SrcBB
);
460 II
->addOperand(MachineOperand::CreateReg(Reg
, false));
461 II
->addOperand(MachineOperand::CreateMBB(SrcBB
));
466 II
->RemoveOperand(Idx
+1);
467 II
->RemoveOperand(Idx
);
473 /// shouldTailDuplicate - Determine if it is profitable to duplicate this block.
475 TailDuplicatePass::shouldTailDuplicate(const MachineFunction
&MF
,
476 MachineBasicBlock
&TailBB
) {
477 // Only duplicate blocks that end with unconditional branches.
478 if (TailBB
.canFallThrough())
481 // Set the limit on the cost to duplicate. When optimizing for size,
482 // duplicate only one, because one branch instruction can be eliminated to
483 // compensate for the duplication.
484 unsigned MaxDuplicateCount
;
485 if (TailDuplicateSize
.getNumOccurrences() == 0 &&
486 MF
.getFunction()->hasFnAttr(Attribute::OptimizeForSize
))
487 MaxDuplicateCount
= 1;
489 MaxDuplicateCount
= TailDuplicateSize
;
494 const TargetInstrDesc
&TID
= TailBB
.back().getDesc();
495 // Pre-regalloc tail duplication hurts compile time and doesn't help
496 // much except for indirect branches.
497 if (!TID
.isIndirectBranch())
499 // If the target has hardware branch prediction that can handle indirect
500 // branches, duplicating them can often make them predictable when there
501 // are common paths through the code. The limit needs to be high enough
502 // to allow undoing the effects of tail merging and other optimizations
503 // that rearrange the predecessors of the indirect branch.
504 MaxDuplicateCount
= 20;
507 // Don't try to tail-duplicate single-block loops.
508 if (TailBB
.isSuccessor(&TailBB
))
511 // Check the instructions in the block to determine whether tail-duplication
512 // is invalid or unlikely to be profitable.
513 unsigned InstrCount
= 0;
514 bool HasCall
= false;
515 for (MachineBasicBlock::const_iterator I
= TailBB
.begin(); I
!= TailBB
.end();
517 // Non-duplicable things shouldn't be tail-duplicated.
518 if (I
->getDesc().isNotDuplicable()) return false;
519 // Do not duplicate 'return' instructions if this is a pre-regalloc run.
520 // A return may expand into a lot more instructions (e.g. reload of callee
521 // saved registers) after PEI.
522 if (PreRegAlloc
&& I
->getDesc().isReturn()) return false;
523 // Don't duplicate more than the threshold.
524 if (InstrCount
== MaxDuplicateCount
) return false;
525 // Remember if we saw a call.
526 if (I
->getDesc().isCall()) HasCall
= true;
527 if (!I
->isPHI() && !I
->isDebugValue())
530 // Don't tail-duplicate calls before register allocation. Calls presents a
531 // barrier to register allocation so duplicating them may end up increasing
533 if (InstrCount
> 1 && (PreRegAlloc
&& HasCall
))
539 /// TailDuplicate - If it is profitable, duplicate TailBB's contents in each
540 /// of its predecessors.
542 TailDuplicatePass::TailDuplicate(MachineBasicBlock
*TailBB
, MachineFunction
&MF
,
543 SmallVector
<MachineBasicBlock
*, 8> &TDBBs
,
544 SmallVector
<MachineInstr
*, 16> &Copies
) {
545 if (!shouldTailDuplicate(MF
, *TailBB
))
548 DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB
->getNumber() << '\n');
550 // Iterate through all the unique predecessors and tail-duplicate this
551 // block into them, if possible. Copying the list ahead of time also
552 // avoids trouble with the predecessor list reallocating.
553 bool Changed
= false;
554 SmallSetVector
<MachineBasicBlock
*, 8> Preds(TailBB
->pred_begin(),
556 DenseSet
<unsigned> UsedByPhi
;
557 getRegsUsedByPHIs(*TailBB
, &UsedByPhi
);
558 for (SmallSetVector
<MachineBasicBlock
*, 8>::iterator PI
= Preds
.begin(),
559 PE
= Preds
.end(); PI
!= PE
; ++PI
) {
560 MachineBasicBlock
*PredBB
= *PI
;
562 assert(TailBB
!= PredBB
&&
563 "Single-block loop should have been rejected earlier!");
564 if (PredBB
->succ_size() > 1) continue;
566 MachineBasicBlock
*PredTBB
, *PredFBB
;
567 SmallVector
<MachineOperand
, 4> PredCond
;
568 // EH edges are ignored by AnalyzeBranch.
569 if (PredBB
->succ_size() != 1)
571 if (TII
->AnalyzeBranch(*PredBB
, PredTBB
, PredFBB
, PredCond
, true))
573 if (!PredCond
.empty())
575 // Don't duplicate into a fall-through predecessor (at least for now).
576 if (PredBB
->isLayoutSuccessor(TailBB
) && PredBB
->canFallThrough())
579 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
580 << "From Succ: " << *TailBB
);
582 TDBBs
.push_back(PredBB
);
584 // Remove PredBB's unconditional branch.
585 TII
->RemoveBranch(*PredBB
);
587 // Clone the contents of TailBB into PredBB.
588 DenseMap
<unsigned, unsigned> LocalVRMap
;
589 SmallVector
<std::pair
<unsigned,unsigned>, 4> CopyInfos
;
590 MachineBasicBlock::iterator I
= TailBB
->begin();
591 while (I
!= TailBB
->end()) {
592 MachineInstr
*MI
= &*I
;
595 // Replace the uses of the def of the PHI with the register coming
597 ProcessPHI(MI
, TailBB
, PredBB
, LocalVRMap
, CopyInfos
, UsedByPhi
);
599 // Replace def of virtual registers with new registers, and update
600 // uses with PHI source register or the new registers.
601 DuplicateInstruction(MI
, TailBB
, PredBB
, MF
, LocalVRMap
, UsedByPhi
);
604 MachineBasicBlock::iterator Loc
= PredBB
->getFirstTerminator();
605 for (unsigned i
= 0, e
= CopyInfos
.size(); i
!= e
; ++i
) {
606 Copies
.push_back(BuildMI(*PredBB
, Loc
, DebugLoc(),
607 TII
->get(TargetOpcode::COPY
),
608 CopyInfos
[i
].first
).addReg(CopyInfos
[i
].second
));
610 NumInstrDups
+= TailBB
->size() - 1; // subtract one for removed branch
613 PredBB
->removeSuccessor(PredBB
->succ_begin());
614 assert(PredBB
->succ_empty() &&
615 "TailDuplicate called on block with multiple successors!");
616 for (MachineBasicBlock::succ_iterator I
= TailBB
->succ_begin(),
617 E
= TailBB
->succ_end(); I
!= E
; ++I
)
618 PredBB
->addSuccessor(*I
);
624 // If TailBB was duplicated into all its predecessors except for the prior
625 // block, which falls through unconditionally, move the contents of this
626 // block into the prior block.
627 MachineBasicBlock
*PrevBB
= prior(MachineFunction::iterator(TailBB
));
628 MachineBasicBlock
*PriorTBB
= 0, *PriorFBB
= 0;
629 SmallVector
<MachineOperand
, 4> PriorCond
;
630 // This has to check PrevBB->succ_size() because EH edges are ignored by
632 if (PrevBB
->succ_size() == 1 &&
633 !TII
->AnalyzeBranch(*PrevBB
, PriorTBB
, PriorFBB
, PriorCond
, true) &&
634 PriorCond
.empty() && !PriorTBB
&& TailBB
->pred_size() == 1 &&
635 !TailBB
->hasAddressTaken()) {
636 DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
637 << "From MBB: " << *TailBB
);
639 DenseMap
<unsigned, unsigned> LocalVRMap
;
640 SmallVector
<std::pair
<unsigned,unsigned>, 4> CopyInfos
;
641 MachineBasicBlock::iterator I
= TailBB
->begin();
642 // Process PHI instructions first.
643 while (I
!= TailBB
->end() && I
->isPHI()) {
644 // Replace the uses of the def of the PHI with the register coming
646 MachineInstr
*MI
= &*I
++;
647 ProcessPHI(MI
, TailBB
, PrevBB
, LocalVRMap
, CopyInfos
, UsedByPhi
);
649 MI
->eraseFromParent();
652 // Now copy the non-PHI instructions.
653 while (I
!= TailBB
->end()) {
654 // Replace def of virtual registers with new registers, and update
655 // uses with PHI source register or the new registers.
656 MachineInstr
*MI
= &*I
++;
657 DuplicateInstruction(MI
, TailBB
, PrevBB
, MF
, LocalVRMap
, UsedByPhi
);
658 MI
->eraseFromParent();
660 MachineBasicBlock::iterator Loc
= PrevBB
->getFirstTerminator();
661 for (unsigned i
= 0, e
= CopyInfos
.size(); i
!= e
; ++i
) {
662 Copies
.push_back(BuildMI(*PrevBB
, Loc
, DebugLoc(),
663 TII
->get(TargetOpcode::COPY
),
665 .addReg(CopyInfos
[i
].second
));
668 // No PHIs to worry about, just splice the instructions over.
669 PrevBB
->splice(PrevBB
->end(), TailBB
, TailBB
->begin(), TailBB
->end());
671 PrevBB
->removeSuccessor(PrevBB
->succ_begin());
672 assert(PrevBB
->succ_empty());
673 PrevBB
->transferSuccessors(TailBB
);
674 TDBBs
.push_back(PrevBB
);
681 /// RemoveDeadBlock - Remove the specified dead machine basic block from the
682 /// function, updating the CFG.
683 void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock
*MBB
) {
684 assert(MBB
->pred_empty() && "MBB must be dead!");
685 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB
);
687 // Remove all successors.
688 while (!MBB
->succ_empty())
689 MBB
->removeSuccessor(MBB
->succ_end()-1);
692 MBB
->eraseFromParent();