#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"
public:
static char ID;
explicit TailDuplicatePass(bool PreRA) :
- MachineFunctionPass(&ID), PreRegAlloc(PreRA) {}
+ MachineFunctionPass(ID), PreRegAlloc(PreRA) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual const char *getPassName() const { return "Tail Duplication"; }
SmallSetVector<MachineBasicBlock*, 8> &Succs);
bool TailDuplicateBlocks(MachineFunction &MF);
bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF,
- SmallVector<MachineBasicBlock*, 8> &TDBBs);
+ SmallVector<MachineBasicBlock*, 8> &TDBBs,
+ SmallVector<MachineInstr*, 16> &Copies);
void RemoveDeadBlock(MachineBasicBlock *MBB);
};
MMI = getAnalysisIfAvailable<MachineModuleInfo>();
bool MadeChange = false;
- bool MadeChangeThisIteration = true;
- while (MadeChangeThisIteration) {
- MadeChangeThisIteration = false;
- MadeChangeThisIteration |= TailDuplicateBlocks(MF);
- MadeChange |= MadeChangeThisIteration;
- }
+ while (TailDuplicateBlocks(MF))
+ MadeChange = true;
return MadeChange;
}
MBB->pred_end());
MachineBasicBlock::iterator MI = MBB->begin();
while (MI != MBB->end()) {
- if (MI->getOpcode() != TargetInstrInfo::PHI)
+ if (!MI->isPHI())
break;
for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),
PE = Preds.end(); PI != PE; ++PI) {
}
}
if (!Found) {
- errs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;
- errs() << " missing input from predecessor BB#"
+ dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;
+ dbgs() << " missing input from predecessor BB#"
<< PredBB->getNumber() << '\n';
llvm_unreachable(0);
}
MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB();
if (CheckExtra && !Preds.count(PHIBB)) {
// This is not a hard error.
- errs() << "Warning: malformed PHI in BB#" << MBB->getNumber()
+ dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber()
<< ": " << *MI;
- errs() << " extra input from predecessor BB#"
+ dbgs() << " extra input from predecessor BB#"
<< PHIBB->getNumber() << '\n';
}
if (PHIBB->getNumber() < 0) {
- errs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;
- errs() << " non-existing BB#" << PHIBB->getNumber() << '\n';
+ dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;
+ dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n';
llvm_unreachable(0);
}
}
bool MadeChange = false;
if (PreRegAlloc && TailDupVerify) {
- DEBUG(errs() << "\n*** Before tail-duplicating\n");
+ DEBUG(dbgs() << "\n*** Before tail-duplicating\n");
VerifyPHIs(MF, true);
}
MBB->succ_end());
SmallVector<MachineBasicBlock*, 8> TDBBs;
- if (TailDuplicate(MBB, MF, TDBBs)) {
+ SmallVector<MachineInstr*, 16> Copies;
+ if (TailDuplicate(MBB, MF, TDBBs, Copies)) {
++NumTails;
// TailBB's immediate successors are now successors of those predecessors
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 (PreRegAlloc && TailDupVerify)
VerifyPHIs(MF, false);
MadeChange = true;
MachineBasicBlock *PredBB,
MachineFunction &MF,
DenseMap<unsigned, unsigned> &LocalVRMap) {
- MachineInstr *NewMI = MF.CloneMachineInstr(MI);
+ 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 (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
+ if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
if (MO.isDef()) {
const TargetRegisterClass *RC = MRI->getRegClass(Reg);
MachineBasicBlock *SuccBB = *SI;
for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end();
II != EE; ++II) {
- if (II->getOpcode() != TargetInstrInfo::PHI)
+ if (!II->isPHI())
break;
unsigned Idx = 0;
for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) {
II->RemoveOperand(i);
}
}
- II->RemoveOperand(Idx+1);
- II->RemoveOperand(Idx);
- }
+ } 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;
unsigned SrcReg = LI->second[j].second;
- II->addOperand(MachineOperand::CreateReg(SrcReg, false));
- II->addOperand(MachineOperand::CreateMBB(SrcBB));
+ 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];
- II->addOperand(MachineOperand::CreateReg(Reg, false));
- II->addOperand(MachineOperand::CreateMBB(SrcBB));
+ 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);
+ }
}
}
}
/// of its predecessors.
bool
TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF,
- SmallVector<MachineBasicBlock*, 8> &TDBBs) {
- // Don't try to tail-duplicate single-block loops.
- if (TailBB->isSuccessor(TailBB))
- return false;
-
+ SmallVector<MachineBasicBlock*, 8> &TDBBs,
+ SmallVector<MachineInstr*, 16> &Copies) {
// Set the limit on the number of instructions to duplicate, with a default
// of one less than the tail-merge threshold. When optimizing for size,
// duplicate only one, because one branch instruction can be eliminated to
// compensate for the duplication.
unsigned MaxDuplicateCount;
- if (!TailBB->empty() && TailBB->back().getDesc().isIndirectBranch())
+ if (TailDuplicateSize.getNumOccurrences() == 0 &&
+ MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize))
+ MaxDuplicateCount = 1;
+ else
+ MaxDuplicateCount = TailDuplicateSize;
+
+ if (PreRegAlloc) {
+ if (TailBB->empty())
+ return false;
+ const TargetInstrDesc &TID = TailBB->back().getDesc();
+ // Pre-regalloc tail duplication hurts compile time and doesn't help
+ // much except for indirect branches and returns.
+ if (!TID.isIndirectBranch() && !TID.isReturn())
+ return false;
// 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.
+ // to allow undoing the effects of tail merging and other optimizations
+ // that rearrange the predecessors of the indirect branch.
MaxDuplicateCount = 20;
- else if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize))
- MaxDuplicateCount = 1;
- else
- MaxDuplicateCount = TailDuplicateSize;
+ }
+
+ // Don't try to tail-duplicate single-block loops.
+ if (TailBB->isSuccessor(TailBB))
+ return false;
// Check the instructions in the block to determine whether tail-duplication
// is invalid or unlikely to be profitable.
if (InstrCount == MaxDuplicateCount) return false;
// Remember if we saw a call.
if (I->getDesc().isCall()) HasCall = true;
- if (I->getOpcode() != TargetInstrInfo::PHI)
+ if (!I->isPHI() && !I->isDebugValue())
InstrCount += 1;
}
- // Heuristically, don't tail-duplicate calls if it would expand code size,
- // as it's less likely to be worth the extra cost.
- if (InstrCount > 1 && HasCall)
+ // Don't tail-duplicate calls before register allocation. Calls presents a
+ // barrier to register allocation so duplicating them may end up increasing
+ // spills.
+ if (InstrCount > 1 && (PreRegAlloc && HasCall))
return false;
- DEBUG(errs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n');
+ DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n');
// Iterate through all the unique predecessors and tail-duplicate this
// block into them, if possible. Copying the list ahead of time also
if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
continue;
- DEBUG(errs() << "\nTail-duplicating into PredBB: " << *PredBB
+ DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
<< "From Succ: " << *TailBB);
TDBBs.push_back(PredBB);
// Clone the contents of TailBB into PredBB.
DenseMap<unsigned, unsigned> LocalVRMap;
- SmallVector<std::pair<unsigned,unsigned>, 4> Copies;
+ SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos;
MachineBasicBlock::iterator I = TailBB->begin();
while (I != TailBB->end()) {
MachineInstr *MI = &*I;
++I;
- if (MI->getOpcode() == TargetInstrInfo::PHI) {
+ if (MI->isPHI()) {
// Replace the uses of the def of the PHI with the register coming
// from PredBB.
- ProcessPHI(MI, TailBB, PredBB, LocalVRMap, Copies);
+ ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos);
} else {
// Replace def of virtual registers with new registers, and update
// uses with PHI source register or the new registers.
}
}
MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator();
- for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
- const TargetRegisterClass *RC = MRI->getRegClass(Copies[i].first);
- TII->copyRegToReg(*PredBB, Loc, Copies[i].first, Copies[i].second, RC, RC);
+ 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));
}
NumInstrDups += TailBB->size() - 1; // subtract one for removed branch
if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB &&
TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 &&
!TailBB->hasAddressTaken()) {
- DEBUG(errs() << "\nMerging into block: " << *PrevBB
+ DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
<< "From MBB: " << *TailBB);
if (PreRegAlloc) {
DenseMap<unsigned, unsigned> LocalVRMap;
- SmallVector<std::pair<unsigned,unsigned>, 4> Copies;
+ SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos;
MachineBasicBlock::iterator I = TailBB->begin();
// Process PHI instructions first.
- while (I != TailBB->end() && I->getOpcode() == TargetInstrInfo::PHI) {
+ 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, Copies);
+ ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos);
if (MI->getParent())
MI->eraseFromParent();
}
MI->eraseFromParent();
}
MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator();
- for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
- const TargetRegisterClass *RC = MRI->getRegClass(Copies[i].first);
- TII->copyRegToReg(*PrevBB, Loc, Copies[i].first, Copies[i].second, RC, RC);
+ 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.
/// function, updating the CFG.
void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) {
assert(MBB->pred_empty() && "MBB must be dead!");
- DEBUG(errs() << "\nRemoving MBB: " << *MBB);
+ DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
// Remove all successors.
while (!MBB->succ_empty())
MBB->removeSuccessor(MBB->succ_end()-1);
- // If there are any labels in the basic block, unregister them from
- // MachineModuleInfo.
- if (MMI && !MBB->empty()) {
- for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
- I != E; ++I) {
- if (I->isLabel())
- // The label ID # is always operand #0, an immediate.
- MMI->InvalidateLabel(I->getOperand(0).getImm());
- }
- }
-
// Remove the block.
MBB->eraseFromParent();
}
projects / oota-llvm.git / blobdiff