X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FTailDuplication.cpp;h=3223e53d5dace53b72a8e17054c91a357602465d;hb=165e96bd25200ccabe4539aaf29a249b61074d11;hp=b53ebecf19188c4aebffa1384aec437348a70633;hpb=80564f761aafad4b5630d04dce6eb65499d5a01e;p=oota-llvm.git diff --git a/lib/CodeGen/TailDuplication.cpp b/lib/CodeGen/TailDuplication.cpp index b53ebecf191..3223e53d5da 100644 --- a/lib/CodeGen/TailDuplication.cpp +++ b/lib/CodeGen/TailDuplication.cpp @@ -90,7 +90,8 @@ namespace { SmallSetVector &Succs); bool TailDuplicateBlocks(MachineFunction &MF); bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, - SmallVector &TDBBs); + SmallVector &TDBBs, + SmallVector &Copies); void RemoveDeadBlock(MachineBasicBlock *MBB); }; @@ -107,12 +108,8 @@ bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { MMI = getAnalysisIfAvailable(); bool MadeChange = false; - bool MadeChangeThisIteration = true; - while (MadeChangeThisIteration) { - MadeChangeThisIteration = false; - MadeChangeThisIteration |= TailDuplicateBlocks(MF); - MadeChange |= MadeChangeThisIteration; - } + while (TailDuplicateBlocks(MF)) + MadeChange = true; return MadeChange; } @@ -124,7 +121,7 @@ static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { MBB->pred_end()); MachineBasicBlock::iterator MI = MBB->begin(); while (MI != MBB->end()) { - if (MI->getOpcode() != TargetInstrInfo::PHI) + if (!MI->isPHI()) break; for (SmallSetVector::iterator PI = Preds.begin(), PE = Preds.end(); PI != PE; ++PI) { @@ -138,8 +135,8 @@ static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { } } 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); } @@ -149,14 +146,14 @@ static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 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); } } @@ -172,7 +169,7 @@ bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { bool MadeChange = false; if (PreRegAlloc && TailDupVerify) { - DEBUG(errs() << "\n*** Before tail-duplicating\n"); + DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); VerifyPHIs(MF, true); } @@ -194,7 +191,8 @@ bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { MBB->succ_end()); SmallVector TDBBs; - if (TailDuplicate(MBB, MF, TDBBs)) { + SmallVector Copies; + if (TailDuplicate(MBB, MF, TDBBs, Copies)) { ++NumTails; // TailBB's immediate successors are now successors of those predecessors @@ -251,6 +249,21 @@ bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 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]; + unsigned Src, Dst, SrcSR, DstSR; + if (TII->isMoveInstr(*Copy, Src, Dst, SrcSR, DstSR)) { + 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; @@ -329,7 +342,7 @@ void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, MachineBasicBlock *PredBB, MachineFunction &MF, DenseMap &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()) @@ -365,7 +378,7 @@ TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 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) { @@ -390,26 +403,45 @@ TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 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::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); + } } } } @@ -418,26 +450,34 @@ TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, /// of its predecessors. bool TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, - SmallVector &TDBBs) { - // Don't try to tail-duplicate single-block loops. - if (TailBB->isSuccessor(TailBB)) - return false; - + SmallVector &TDBBs, + SmallVector &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 (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) + MaxDuplicateCount = 1; + else + MaxDuplicateCount = TailDuplicateSize; + + if (PreRegAlloc) { + // Pre-regalloc tail duplication hurts compile time and doesn't help + // much except for indirect branches. + if (TailBB->empty() || !TailBB->back().getDesc().isIndirectBranch()) + 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. @@ -455,7 +495,7 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 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()) InstrCount += 1; } // Heuristically, don't tail-duplicate calls if it would expand code size, @@ -463,7 +503,7 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, if (InstrCount > 1 && 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 @@ -492,7 +532,7 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 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); @@ -502,15 +542,15 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, // Clone the contents of TailBB into PredBB. DenseMap LocalVRMap; - SmallVector, 4> Copies; + SmallVector, 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. @@ -518,9 +558,12 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, } } 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) { + const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first); + TII->copyRegToReg(*PredBB, Loc, CopyInfos[i].first, + CopyInfos[i].second, RC,RC); + MachineInstr *CopyMI = prior(Loc); + Copies.push_back(CopyMI); } NumInstrDups += TailBB->size() - 1; // subtract one for removed branch @@ -549,18 +592,18 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 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 LocalVRMap; - SmallVector, 4> Copies; + SmallVector, 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(); } @@ -574,9 +617,12 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 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) { + const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first); + TII->copyRegToReg(*PrevBB, Loc, CopyInfos[i].first, + CopyInfos[i].second, RC, RC); + MachineInstr *CopyMI = prior(Loc); + Copies.push_back(CopyMI); } } else { // No PHIs to worry about, just splice the instructions over. @@ -596,7 +642,7 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, /// 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())