| //===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This pass duplicates basic blocks ending in unconditional branches into |
| // the tails of their predecessors. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "tailduplication" |
| #include "llvm/Function.h" |
| #include "llvm/CodeGen/Passes.h" |
| #include "llvm/CodeGen/MachineModuleInfo.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/MachineRegisterInfo.h" |
| #include "llvm/CodeGen/MachineSSAUpdater.h" |
| #include "llvm/Target/TargetInstrInfo.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/ErrorHandling.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include "llvm/ADT/DenseSet.h" |
| #include "llvm/ADT/SmallSet.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/ADT/Statistic.h" |
| using namespace llvm; |
| |
| STATISTIC(NumTails , "Number of tails duplicated"); |
| STATISTIC(NumTailDups , "Number of tail duplicated blocks"); |
| STATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); |
| STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); |
| STATISTIC(NumAddedPHIs , "Number of phis added"); |
| |
| // Heuristic for tail duplication. |
| static cl::opt<unsigned> |
| TailDuplicateSize("tail-dup-size", |
| cl::desc("Maximum instructions to consider tail duplicating"), |
| cl::init(2), cl::Hidden); |
| |
| static cl::opt<bool> |
| TailDupVerify("tail-dup-verify", |
| cl::desc("Verify sanity of PHI instructions during taildup"), |
| cl::init(false), cl::Hidden); |
| |
| static cl::opt<unsigned> |
| TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); |
| |
| typedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; |
| |
| namespace { |
| /// TailDuplicatePass - Perform tail duplication. |
| class TailDuplicatePass : public MachineFunctionPass { |
| bool PreRegAlloc; |
| const TargetInstrInfo *TII; |
| MachineModuleInfo *MMI; |
| MachineRegisterInfo *MRI; |
| |
| // SSAUpdateVRs - A list of virtual registers for which to update SSA form. |
| SmallVector<unsigned, 16> SSAUpdateVRs; |
| |
| // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of |
| // source virtual registers. |
| DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; |
| |
| public: |
| static char ID; |
| explicit TailDuplicatePass(bool PreRA) : |
| MachineFunctionPass(ID), PreRegAlloc(PreRA) {} |
| |
| virtual bool runOnMachineFunction(MachineFunction &MF); |
| virtual const char *getPassName() const { return "Tail Duplication"; } |
| |
| private: |
| void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, |
| MachineBasicBlock *BB); |
| void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, |
| MachineBasicBlock *PredBB, |
| DenseMap<unsigned, unsigned> &LocalVRMap, |
| SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, |
| const DenseSet<unsigned> &UsedByPhi, |
| bool Remove); |
| void DuplicateInstruction(MachineInstr *MI, |
| MachineBasicBlock *TailBB, |
| MachineBasicBlock *PredBB, |
| MachineFunction &MF, |
| DenseMap<unsigned, unsigned> &LocalVRMap, |
| const DenseSet<unsigned> &UsedByPhi); |
| void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, |
| SmallVector<MachineBasicBlock*, 8> &TDBBs, |
| SmallSetVector<MachineBasicBlock*, 8> &Succs); |
| bool TailDuplicateBlocks(MachineFunction &MF); |
| bool shouldTailDuplicate(const MachineFunction &MF, |
| bool IsSimple, MachineBasicBlock &TailBB); |
| bool isSimpleBB(MachineBasicBlock *TailBB); |
| bool canCompletelyDuplicateBB(MachineBasicBlock &BB); |
| bool duplicateSimpleBB(MachineBasicBlock *TailBB, |
| SmallVector<MachineBasicBlock*, 8> &TDBBs, |
| const DenseSet<unsigned> &RegsUsedByPhi, |
| SmallVector<MachineInstr*, 16> &Copies); |
| bool TailDuplicate(MachineBasicBlock *TailBB, |
| bool IsSimple, |
| MachineFunction &MF, |
| SmallVector<MachineBasicBlock*, 8> &TDBBs, |
| SmallVector<MachineInstr*, 16> &Copies); |
| bool TailDuplicateAndUpdate(MachineBasicBlock *MBB, |
| bool IsSimple, |
| MachineFunction &MF); |
| |
| void RemoveDeadBlock(MachineBasicBlock *MBB); |
| }; |
| |
| char TailDuplicatePass::ID = 0; |
| } |
| |
| FunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { |
| return new TailDuplicatePass(PreRegAlloc); |
| } |
| |
| bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { |
| TII = MF.getTarget().getInstrInfo(); |
| MRI = &MF.getRegInfo(); |
| MMI = getAnalysisIfAvailable<MachineModuleInfo>(); |
| |
| bool MadeChange = false; |
| while (TailDuplicateBlocks(MF)) |
| MadeChange = true; |
| |
| return MadeChange; |
| } |
| |
| static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { |
| for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { |
| MachineBasicBlock *MBB = I; |
| SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), |
| MBB->pred_end()); |
| MachineBasicBlock::iterator MI = MBB->begin(); |
| while (MI != MBB->end()) { |
| if (!MI->isPHI()) |
| break; |
| for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), |
| PE = Preds.end(); PI != PE; ++PI) { |
| MachineBasicBlock *PredBB = *PI; |
| bool Found = false; |
| for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { |
| MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); |
| if (PHIBB == PredBB) { |
| Found = true; |
| break; |
| } |
| } |
| if (!Found) { |
| dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; |
| dbgs() << " missing input from predecessor BB#" |
| << PredBB->getNumber() << '\n'; |
| llvm_unreachable(0); |
| } |
| } |
| |
| for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { |
| MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); |
| if (CheckExtra && !Preds.count(PHIBB)) { |
| dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() |
| << ": " << *MI; |
| dbgs() << " extra input from predecessor BB#" |
| << PHIBB->getNumber() << '\n'; |
| llvm_unreachable(0); |
| } |
| if (PHIBB->getNumber() < 0) { |
| dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; |
| dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; |
| llvm_unreachable(0); |
| } |
| } |
| ++MI; |
| } |
| } |
| } |
| |
| /// TailDuplicateAndUpdate - Tail duplicate the block and cleanup. |
| bool |
| TailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB, |
| bool IsSimple, |
| MachineFunction &MF) { |
| // Save the successors list. |
| SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), |
| MBB->succ_end()); |
| |
| SmallVector<MachineBasicBlock*, 8> TDBBs; |
| SmallVector<MachineInstr*, 16> Copies; |
| if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies)) |
| return false; |
| |
| ++NumTails; |
| |
| SmallVector<MachineInstr*, 8> NewPHIs; |
| MachineSSAUpdater SSAUpdate(MF, &NewPHIs); |
| |
| // TailBB's immediate successors are now successors of those predecessors |
| // which duplicated TailBB. Add the predecessors as sources to the PHI |
| // instructions. |
| bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); |
| if (PreRegAlloc) |
| UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); |
| |
| // If it is dead, remove it. |
| if (isDead) { |
| NumInstrDups -= MBB->size(); |
| RemoveDeadBlock(MBB); |
| ++NumDeadBlocks; |
| } |
| |
| // Update SSA form. |
| if (!SSAUpdateVRs.empty()) { |
| for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { |
| unsigned VReg = SSAUpdateVRs[i]; |
| SSAUpdate.Initialize(VReg); |
| |
| // If the original definition is still around, add it as an available |
| // value. |
| MachineInstr *DefMI = MRI->getVRegDef(VReg); |
| MachineBasicBlock *DefBB = 0; |
| if (DefMI) { |
| DefBB = DefMI->getParent(); |
| SSAUpdate.AddAvailableValue(DefBB, VReg); |
| } |
| |
| // Add the new vregs as available values. |
| DenseMap<unsigned, AvailableValsTy>::iterator LI = |
| SSAUpdateVals.find(VReg); |
| for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { |
| MachineBasicBlock *SrcBB = LI->second[j].first; |
| unsigned SrcReg = LI->second[j].second; |
| SSAUpdate.AddAvailableValue(SrcBB, SrcReg); |
| } |
| |
| // Rewrite uses that are outside of the original def's block. |
| MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); |
| while (UI != MRI->use_end()) { |
| MachineOperand &UseMO = UI.getOperand(); |
| MachineInstr *UseMI = &*UI; |
| ++UI; |
| if (UseMI->isDebugValue()) { |
| // SSAUpdate can replace the use with an undef. That creates |
| // a debug instruction that is a kill. |
| // FIXME: Should it SSAUpdate job to delete debug instructions |
| // instead of replacing the use with undef? |
| UseMI->eraseFromParent(); |
| continue; |
| } |
| if (UseMI->getParent() == DefBB && !UseMI->isPHI()) |
| continue; |
| SSAUpdate.RewriteUse(UseMO); |
| } |
| } |
| |
| SSAUpdateVRs.clear(); |
| SSAUpdateVals.clear(); |
| } |
| |
| // Eliminate some of the copies inserted by tail duplication to maintain |
| // SSA form. |
| for (unsigned i = 0, e = Copies.size(); i != e; ++i) { |
| MachineInstr *Copy = Copies[i]; |
| if (!Copy->isCopy()) |
| continue; |
| unsigned Dst = Copy->getOperand(0).getReg(); |
| unsigned Src = Copy->getOperand(1).getReg(); |
| MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); |
| if (++UI == MRI->use_end()) { |
| // Copy is the only use. Do trivial copy propagation here. |
| MRI->replaceRegWith(Dst, Src); |
| Copy->eraseFromParent(); |
| } |
| } |
| |
| if (NewPHIs.size()) |
| NumAddedPHIs += NewPHIs.size(); |
| |
| return true; |
| } |
| |
| /// TailDuplicateBlocks - Look for small blocks that are unconditionally |
| /// branched to and do not fall through. Tail-duplicate their instructions |
| /// into their predecessors to eliminate (dynamic) branches. |
| bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { |
| bool MadeChange = false; |
| |
| if (PreRegAlloc && TailDupVerify) { |
| DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); |
| VerifyPHIs(MF, true); |
| } |
| |
| for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { |
| MachineBasicBlock *MBB = I++; |
| |
| if (NumTails == TailDupLimit) |
| break; |
| |
| bool IsSimple = isSimpleBB(MBB); |
| |
| if (!shouldTailDuplicate(MF, IsSimple, *MBB)) |
| continue; |
| |
| MadeChange |= TailDuplicateAndUpdate(MBB, IsSimple, MF); |
| } |
| |
| if (PreRegAlloc && TailDupVerify) |
| VerifyPHIs(MF, false); |
| |
| return MadeChange; |
| } |
| |
| static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, |
| const MachineRegisterInfo *MRI) { |
| for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), |
| UE = MRI->use_end(); UI != UE; ++UI) { |
| MachineInstr *UseMI = &*UI; |
| if (UseMI->isDebugValue()) |
| continue; |
| if (UseMI->getParent() != BB) |
| return true; |
| } |
| return false; |
| } |
| |
| static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { |
| for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) |
| if (MI->getOperand(i+1).getMBB() == SrcBB) |
| return i; |
| return 0; |
| } |
| |
| |
| // Remember which registers are used by phis in this block. This is |
| // used to determine which registers are liveout while modifying the |
| // block (which is why we need to copy the information). |
| static void getRegsUsedByPHIs(const MachineBasicBlock &BB, |
| DenseSet<unsigned> *UsedByPhi) { |
| for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end(); |
| I != E; ++I) { |
| const MachineInstr &MI = *I; |
| if (!MI.isPHI()) |
| break; |
| for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { |
| unsigned SrcReg = MI.getOperand(i).getReg(); |
| UsedByPhi->insert(SrcReg); |
| } |
| } |
| } |
| |
| /// AddSSAUpdateEntry - Add a definition and source virtual registers pair for |
| /// SSA update. |
| void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, |
| MachineBasicBlock *BB) { |
| DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); |
| if (LI != SSAUpdateVals.end()) |
| LI->second.push_back(std::make_pair(BB, NewReg)); |
| else { |
| AvailableValsTy Vals; |
| Vals.push_back(std::make_pair(BB, NewReg)); |
| SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); |
| SSAUpdateVRs.push_back(OrigReg); |
| } |
| } |
| |
| /// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. |
| /// Remember the source register that's contributed by PredBB and update SSA |
| /// update map. |
| void TailDuplicatePass::ProcessPHI(MachineInstr *MI, |
| MachineBasicBlock *TailBB, |
| MachineBasicBlock *PredBB, |
| DenseMap<unsigned, unsigned> &LocalVRMap, |
| SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, |
| const DenseSet<unsigned> &RegsUsedByPhi, |
| bool Remove) { |
| unsigned DefReg = MI->getOperand(0).getReg(); |
| unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); |
| assert(SrcOpIdx && "Unable to find matching PHI source?"); |
| unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); |
| const TargetRegisterClass *RC = MRI->getRegClass(DefReg); |
| LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); |
| |
| // Insert a copy from source to the end of the block. The def register is the |
| // available value liveout of the block. |
| unsigned NewDef = MRI->createVirtualRegister(RC); |
| Copies.push_back(std::make_pair(NewDef, SrcReg)); |
| if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) |
| AddSSAUpdateEntry(DefReg, NewDef, PredBB); |
| |
| if (!Remove) |
| return; |
| |
| // Remove PredBB from the PHI node. |
| MI->RemoveOperand(SrcOpIdx+1); |
| MI->RemoveOperand(SrcOpIdx); |
| if (MI->getNumOperands() == 1) |
| MI->eraseFromParent(); |
| } |
| |
| /// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update |
| /// the source operands due to earlier PHI translation. |
| void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, |
| MachineBasicBlock *TailBB, |
| MachineBasicBlock *PredBB, |
| MachineFunction &MF, |
| DenseMap<unsigned, unsigned> &LocalVRMap, |
| const DenseSet<unsigned> &UsedByPhi) { |
| MachineInstr *NewMI = TII->duplicate(MI, MF); |
| for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { |
| MachineOperand &MO = NewMI->getOperand(i); |
| if (!MO.isReg()) |
| continue; |
| unsigned Reg = MO.getReg(); |
| if (!TargetRegisterInfo::isVirtualRegister(Reg)) |
| continue; |
| if (MO.isDef()) { |
| const TargetRegisterClass *RC = MRI->getRegClass(Reg); |
| unsigned NewReg = MRI->createVirtualRegister(RC); |
| MO.setReg(NewReg); |
| LocalVRMap.insert(std::make_pair(Reg, NewReg)); |
| if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) |
| AddSSAUpdateEntry(Reg, NewReg, PredBB); |
| } else { |
| DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); |
| if (VI != LocalVRMap.end()) |
| MO.setReg(VI->second); |
| } |
| } |
| PredBB->insert(PredBB->end(), NewMI); |
| } |
| |
| /// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor |
| /// blocks, the successors have gained new predecessors. Update the PHI |
| /// instructions in them accordingly. |
| void |
| TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, |
| SmallVector<MachineBasicBlock*, 8> &TDBBs, |
| SmallSetVector<MachineBasicBlock*,8> &Succs) { |
| for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), |
| SE = Succs.end(); SI != SE; ++SI) { |
| MachineBasicBlock *SuccBB = *SI; |
| for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); |
| II != EE; ++II) { |
| if (!II->isPHI()) |
| break; |
| unsigned Idx = 0; |
| for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { |
| MachineOperand &MO = II->getOperand(i+1); |
| if (MO.getMBB() == FromBB) { |
| Idx = i; |
| break; |
| } |
| } |
| |
| assert(Idx != 0); |
| MachineOperand &MO0 = II->getOperand(Idx); |
| unsigned Reg = MO0.getReg(); |
| if (isDead) { |
| // Folded into the previous BB. |
| // There could be duplicate phi source entries. FIXME: Should sdisel |
| // or earlier pass fixed this? |
| for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { |
| MachineOperand &MO = II->getOperand(i+1); |
| if (MO.getMBB() == FromBB) { |
| II->RemoveOperand(i+1); |
| II->RemoveOperand(i); |
| } |
| } |
| } else |
| Idx = 0; |
| |
| // If Idx is set, the operands at Idx and Idx+1 must be removed. |
| // We reuse the location to avoid expensive RemoveOperand calls. |
| |
| DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); |
| if (LI != SSAUpdateVals.end()) { |
| // This register is defined in the tail block. |
| for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { |
| MachineBasicBlock *SrcBB = LI->second[j].first; |
| // If we didn't duplicate a bb into a particular predecessor, we |
| // might still have added an entry to SSAUpdateVals to correcly |
| // recompute SSA. If that case, avoid adding a dummy extra argument |
| // this PHI. |
| if (!SrcBB->isSuccessor(SuccBB)) |
| continue; |
| |
| unsigned SrcReg = LI->second[j].second; |
| if (Idx != 0) { |
| II->getOperand(Idx).setReg(SrcReg); |
| II->getOperand(Idx+1).setMBB(SrcBB); |
| Idx = 0; |
| } else { |
| II->addOperand(MachineOperand::CreateReg(SrcReg, false)); |
| II->addOperand(MachineOperand::CreateMBB(SrcBB)); |
| } |
| } |
| } else { |
| // Live in tail block, must also be live in predecessors. |
| for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { |
| MachineBasicBlock *SrcBB = TDBBs[j]; |
| if (Idx != 0) { |
| II->getOperand(Idx).setReg(Reg); |
| II->getOperand(Idx+1).setMBB(SrcBB); |
| Idx = 0; |
| } else { |
| II->addOperand(MachineOperand::CreateReg(Reg, false)); |
| II->addOperand(MachineOperand::CreateMBB(SrcBB)); |
| } |
| } |
| } |
| if (Idx != 0) { |
| II->RemoveOperand(Idx+1); |
| II->RemoveOperand(Idx); |
| } |
| } |
| } |
| } |
| |
| /// shouldTailDuplicate - Determine if it is profitable to duplicate this block. |
| bool |
| TailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF, |
| bool IsSimple, |
| MachineBasicBlock &TailBB) { |
| // Only duplicate blocks that end with unconditional branches. |
| if (TailBB.canFallThrough()) |
| return false; |
| |
| // Don't try to tail-duplicate single-block loops. |
| if (TailBB.isSuccessor(&TailBB)) |
| return false; |
| |
| // Set the limit on the cost to duplicate. When optimizing for size, |
| // duplicate only one, because one branch instruction can be eliminated to |
| // compensate for the duplication. |
| unsigned MaxDuplicateCount; |
| if (TailDuplicateSize.getNumOccurrences() == 0 && |
| MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) |
| MaxDuplicateCount = 1; |
| else |
| MaxDuplicateCount = TailDuplicateSize; |
| |
| // If the target has hardware branch prediction that can handle indirect |
| // branches, duplicating them can often make them predictable when there |
| // are common paths through the code. The limit needs to be high enough |
| // to allow undoing the effects of tail merging and other optimizations |
| // that rearrange the predecessors of the indirect branch. |
| |
| bool HasIndirectbr = false; |
| if (!TailBB.empty()) |
| HasIndirectbr = TailBB.back().getDesc().isIndirectBranch(); |
| |
| if (HasIndirectbr && PreRegAlloc) |
| MaxDuplicateCount = 20; |
| |
| // Check the instructions in the block to determine whether tail-duplication |
| // is invalid or unlikely to be profitable. |
| unsigned InstrCount = 0; |
| for (MachineBasicBlock::const_iterator I = TailBB.begin(); I != TailBB.end(); |
| ++I) { |
| // Non-duplicable things shouldn't be tail-duplicated. |
| if (I->getDesc().isNotDuplicable()) |
| return false; |
| |
| // Do not duplicate 'return' instructions if this is a pre-regalloc run. |
| // A return may expand into a lot more instructions (e.g. reload of callee |
| // saved registers) after PEI. |
| if (PreRegAlloc && I->getDesc().isReturn()) |
| return false; |
| |
| // Avoid duplicating calls before register allocation. Calls presents a |
| // barrier to register allocation so duplicating them may end up increasing |
| // spills. |
| if (PreRegAlloc && I->getDesc().isCall()) |
| return false; |
| |
| if (!I->isPHI() && !I->isDebugValue()) |
| InstrCount += 1; |
| |
| if (InstrCount > MaxDuplicateCount) |
| return false; |
| } |
| |
| if (HasIndirectbr && PreRegAlloc) |
| return true; |
| |
| if (IsSimple) |
| return true; |
| |
| if (!PreRegAlloc) |
| return true; |
| |
| return canCompletelyDuplicateBB(TailBB); |
| } |
| |
| /// isSimpleBB - True if this BB has only one unconditional jump. |
| bool |
| TailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) { |
| if (TailBB->succ_size() != 1) |
| return false; |
| if (TailBB->pred_empty()) |
| return false; |
| MachineBasicBlock::iterator I = TailBB->begin(); |
| MachineBasicBlock::iterator E = TailBB->end(); |
| while (I != E && I->isDebugValue()) |
| ++I; |
| if (I == E) |
| return true; |
| return I->getDesc().isUnconditionalBranch(); |
| } |
| |
| static bool |
| bothUsedInPHI(const MachineBasicBlock &A, |
| SmallPtrSet<MachineBasicBlock*, 8> SuccsB) { |
| for (MachineBasicBlock::const_succ_iterator SI = A.succ_begin(), |
| SE = A.succ_end(); SI != SE; ++SI) { |
| MachineBasicBlock *BB = *SI; |
| if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| bool |
| TailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) { |
| SmallPtrSet<MachineBasicBlock*, 8> Succs(BB.succ_begin(), BB.succ_end()); |
| |
| for (MachineBasicBlock::pred_iterator PI = BB.pred_begin(), |
| PE = BB.pred_end(); PI != PE; ++PI) { |
| MachineBasicBlock *PredBB = *PI; |
| |
| if (PredBB->succ_size() > 1) |
| return false; |
| |
| MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; |
| SmallVector<MachineOperand, 4> PredCond; |
| if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) |
| return false; |
| |
| if (!PredCond.empty()) |
| return false; |
| } |
| return true; |
| } |
| |
| bool |
| TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB, |
| SmallVector<MachineBasicBlock*, 8> &TDBBs, |
| const DenseSet<unsigned> &UsedByPhi, |
| SmallVector<MachineInstr*, 16> &Copies) { |
| SmallPtrSet<MachineBasicBlock*, 8> Succs(TailBB->succ_begin(), |
| TailBB->succ_end()); |
| SmallVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), |
| TailBB->pred_end()); |
| bool Changed = false; |
| for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), |
| PE = Preds.end(); PI != PE; ++PI) { |
| MachineBasicBlock *PredBB = *PI; |
| |
| if (PredBB->getLandingPadSuccessor()) |
| continue; |
| |
| if (bothUsedInPHI(*PredBB, Succs)) |
| continue; |
| |
| MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; |
| SmallVector<MachineOperand, 4> PredCond; |
| if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) |
| continue; |
| |
| Changed = true; |
| DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB |
| << "From simple Succ: " << *TailBB); |
| |
| MachineBasicBlock *NewTarget = *TailBB->succ_begin(); |
| MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(PredBB)); |
| |
| // Make PredFBB explicit. |
| if (PredCond.empty()) |
| PredFBB = PredTBB; |
| |
| // Make fall through explicit. |
| if (!PredTBB) |
| PredTBB = NextBB; |
| if (!PredFBB) |
| PredFBB = NextBB; |
| |
| // Redirect |
| if (PredFBB == TailBB) |
| PredFBB = NewTarget; |
| if (PredTBB == TailBB) |
| PredTBB = NewTarget; |
| |
| // Make the branch unconditional if possible |
| if (PredTBB == PredFBB) { |
| PredCond.clear(); |
| PredFBB = NULL; |
| } |
| |
| // Avoid adding fall through branches. |
| if (PredFBB == NextBB) |
| PredFBB = NULL; |
| if (PredTBB == NextBB && PredFBB == NULL) |
| PredTBB = NULL; |
| |
| TII->RemoveBranch(*PredBB); |
| |
| if (PredTBB) |
| TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc()); |
| |
| PredBB->removeSuccessor(TailBB); |
| unsigned NumSuccessors = PredBB->succ_size(); |
| assert(NumSuccessors <= 1); |
| if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget) |
| PredBB->addSuccessor(NewTarget); |
| |
| TDBBs.push_back(PredBB); |
| } |
| return Changed; |
| } |
| |
| /// TailDuplicate - If it is profitable, duplicate TailBB's contents in each |
| /// of its predecessors. |
| bool |
| TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, |
| bool IsSimple, |
| MachineFunction &MF, |
| SmallVector<MachineBasicBlock*, 8> &TDBBs, |
| SmallVector<MachineInstr*, 16> &Copies) { |
| DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); |
| |
| DenseSet<unsigned> UsedByPhi; |
| getRegsUsedByPHIs(*TailBB, &UsedByPhi); |
| |
| if (IsSimple) |
| return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); |
| |
| // Iterate through all the unique predecessors and tail-duplicate this |
| // block into them, if possible. Copying the list ahead of time also |
| // avoids trouble with the predecessor list reallocating. |
| bool Changed = false; |
| SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), |
| TailBB->pred_end()); |
| for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), |
| PE = Preds.end(); PI != PE; ++PI) { |
| MachineBasicBlock *PredBB = *PI; |
| |
| assert(TailBB != PredBB && |
| "Single-block loop should have been rejected earlier!"); |
| // EH edges are ignored by AnalyzeBranch. |
| if (PredBB->succ_size() > 1) |
| continue; |
| |
| MachineBasicBlock *PredTBB, *PredFBB; |
| SmallVector<MachineOperand, 4> PredCond; |
| if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) |
| continue; |
| if (!PredCond.empty()) |
| continue; |
| // Don't duplicate into a fall-through predecessor (at least for now). |
| if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) |
| continue; |
| |
| DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB |
| << "From Succ: " << *TailBB); |
| |
| TDBBs.push_back(PredBB); |
| |
| // Remove PredBB's unconditional branch. |
| TII->RemoveBranch(*PredBB); |
| |
| // Clone the contents of TailBB into PredBB. |
| DenseMap<unsigned, unsigned> LocalVRMap; |
| SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; |
| MachineBasicBlock::iterator I = TailBB->begin(); |
| while (I != TailBB->end()) { |
| MachineInstr *MI = &*I; |
| ++I; |
| if (MI->isPHI()) { |
| // Replace the uses of the def of the PHI with the register coming |
| // from PredBB. |
| ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); |
| } else { |
| // Replace def of virtual registers with new registers, and update |
| // uses with PHI source register or the new registers. |
| DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); |
| } |
| } |
| MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); |
| for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { |
| Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), |
| TII->get(TargetOpcode::COPY), |
| CopyInfos[i].first).addReg(CopyInfos[i].second)); |
| } |
| |
| // Simplify |
| TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true); |
| |
| NumInstrDups += TailBB->size() - 1; // subtract one for removed branch |
| |
| // Update the CFG. |
| PredBB->removeSuccessor(PredBB->succ_begin()); |
| assert(PredBB->succ_empty() && |
| "TailDuplicate called on block with multiple successors!"); |
| for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), |
| E = TailBB->succ_end(); I != E; ++I) |
| PredBB->addSuccessor(*I); |
| |
| Changed = true; |
| ++NumTailDups; |
| } |
| |
| // If TailBB was duplicated into all its predecessors except for the prior |
| // block, which falls through unconditionally, move the contents of this |
| // block into the prior block. |
| MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); |
| MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; |
| SmallVector<MachineOperand, 4> PriorCond; |
| // This has to check PrevBB->succ_size() because EH edges are ignored by |
| // AnalyzeBranch. |
| if (PrevBB->succ_size() == 1 && |
| !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && |
| PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && |
| !TailBB->hasAddressTaken()) { |
| DEBUG(dbgs() << "\nMerging into block: " << *PrevBB |
| << "From MBB: " << *TailBB); |
| if (PreRegAlloc) { |
| DenseMap<unsigned, unsigned> LocalVRMap; |
| SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; |
| MachineBasicBlock::iterator I = TailBB->begin(); |
| // Process PHI instructions first. |
| while (I != TailBB->end() && I->isPHI()) { |
| // Replace the uses of the def of the PHI with the register coming |
| // from PredBB. |
| MachineInstr *MI = &*I++; |
| ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); |
| if (MI->getParent()) |
| MI->eraseFromParent(); |
| } |
| |
| // Now copy the non-PHI instructions. |
| while (I != TailBB->end()) { |
| // Replace def of virtual registers with new registers, and update |
| // uses with PHI source register or the new registers. |
| MachineInstr *MI = &*I++; |
| DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); |
| MI->eraseFromParent(); |
| } |
| MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); |
| for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { |
| Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), |
| TII->get(TargetOpcode::COPY), |
| CopyInfos[i].first) |
| .addReg(CopyInfos[i].second)); |
| } |
| } else { |
| // No PHIs to worry about, just splice the instructions over. |
| PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); |
| } |
| PrevBB->removeSuccessor(PrevBB->succ_begin()); |
| assert(PrevBB->succ_empty()); |
| PrevBB->transferSuccessors(TailBB); |
| TDBBs.push_back(PrevBB); |
| Changed = true; |
| } |
| |
| // If this is after register allocation, there are no phis to fix. |
| if (!PreRegAlloc) |
| return Changed; |
| |
| // If we made no changes so far, we are safe. |
| if (!Changed) |
| return Changed; |
| |
| |
| // Handle the nasty case in that we duplicated a block that is part of a loop |
| // into some but not all of its predecessors. For example: |
| // 1 -> 2 <-> 3 | |
| // \ | |
| // \---> rest | |
| // if we duplicate 2 into 1 but not into 3, we end up with |
| // 12 -> 3 <-> 2 -> rest | |
| // \ / | |
| // \----->-----/ | |
| // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced |
| // with a phi in 3 (which now dominates 2). |
| // What we do here is introduce a copy in 3 of the register defined by the |
| // phi, just like when we are duplicating 2 into 3, but we don't copy any |
| // real instructions or remove the 3 -> 2 edge from the phi in 2. |
| for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), |
| PE = Preds.end(); PI != PE; ++PI) { |
| MachineBasicBlock *PredBB = *PI; |
| if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) |
| continue; |
| |
| // EH edges |
| if (PredBB->succ_size() != 1) |
| continue; |
| |
| DenseMap<unsigned, unsigned> LocalVRMap; |
| SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; |
| MachineBasicBlock::iterator I = TailBB->begin(); |
| // Process PHI instructions first. |
| while (I != TailBB->end() && I->isPHI()) { |
| // Replace the uses of the def of the PHI with the register coming |
| // from PredBB. |
| MachineInstr *MI = &*I++; |
| ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); |
| } |
| MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); |
| for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { |
| Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), |
| TII->get(TargetOpcode::COPY), |
| CopyInfos[i].first).addReg(CopyInfos[i].second)); |
| } |
| } |
| |
| return Changed; |
| } |
| |
| /// RemoveDeadBlock - Remove the specified dead machine basic block from the |
| /// function, updating the CFG. |
| void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { |
| assert(MBB->pred_empty() && "MBB must be dead!"); |
| DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); |
| |
| // Remove all successors. |
| while (!MBB->succ_empty()) |
| MBB->removeSuccessor(MBB->succ_end()-1); |
| |
| // Remove the block. |
| MBB->eraseFromParent(); |
| } |
