X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FIfConversion.cpp;h=8264d6dbab81873bdc3f34472ba27d2c1d1a4668;hb=1db3d0820f8057dd03ade1585bfa5f2bf53cfe33;hp=5c2a73b75aa0918e5a0a30771dd873a698feef94;hpb=8787c5f24e175a36f645784d533384f9f7cd86fc;p=oota-llvm.git diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp index 5c2a73b75aa..8264d6dbab8 100644 --- a/lib/CodeGen/IfConversion.cpp +++ b/lib/CodeGen/IfConversion.cpp @@ -12,24 +12,25 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "ifcvt" -#include "BranchFolding.h" -#include "llvm/Function.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/MachineModuleInfo.h" +#include "BranchFolding.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/MC/MCInstrItineraries.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetLowering.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetRegisterInfo.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/SmallSet.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetLowering.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" using namespace llvm; // Hidden options for help debugging. @@ -150,12 +151,14 @@ namespace { /// basic block number. std::vector BBAnalysis; - const TargetLowering *TLI; + const TargetLoweringBase *TLI; const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; const InstrItineraryData *InstrItins; const MachineBranchProbabilityInfo *MBPI; + MachineRegisterInfo *MRI; + bool PreRegAlloc; bool MadeChange; int FnNum; public: @@ -170,7 +173,6 @@ namespace { } virtual bool runOnMachineFunction(MachineFunction &MF); - virtual const char *getPassName() const { return "If Converter"; } private: bool ReverseBranchCondition(BBInfo &BBI); @@ -253,28 +255,34 @@ namespace { char IfConverter::ID = 0; } +char &llvm::IfConverterID = IfConverter::ID; + INITIALIZE_PASS_BEGIN(IfConverter, "if-converter", "If Converter", false, false) INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) INITIALIZE_PASS_END(IfConverter, "if-converter", "If Converter", false, false) -FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); } - bool IfConverter::runOnMachineFunction(MachineFunction &MF) { TLI = MF.getTarget().getTargetLowering(); TII = MF.getTarget().getInstrInfo(); TRI = MF.getTarget().getRegisterInfo(); MBPI = &getAnalysis(); + MRI = &MF.getRegInfo(); InstrItins = MF.getTarget().getInstrItineraryData(); if (!TII) return false; - // Tail merge tend to expose more if-conversion opportunities. - BranchFolder BF(true, false); - bool BFChange = BF.OptimizeFunction(MF, TII, + PreRegAlloc = MRI->isSSA(); + + bool BFChange = false; + if (!PreRegAlloc) { + // Tail merge tend to expose more if-conversion opportunities. + BranchFolder BF(true, false); + BFChange = BF.OptimizeFunction(MF, TII, MF.getTarget().getRegisterInfo(), getAnalysisIfAvailable()); + } DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'" - << MF.getFunction()->getName() << "\'"); + << MF.getName() << "\'"); if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) { DEBUG(dbgs() << " skipped\n"); @@ -315,8 +323,7 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { bool RetVal = false; switch (Kind) { - default: assert(false && "Unexpected!"); - break; + default: llvm_unreachable("Unexpected!"); case ICSimple: case ICSimpleFalse: { bool isFalse = Kind == ICSimpleFalse; @@ -623,7 +630,7 @@ void IfConverter::ScanInstructions(BBInfo &BBI) { if (BBI.IsDone) return; - bool AlreadyPredicated = BBI.Predicate.size() > 0; + bool AlreadyPredicated = !BBI.Predicate.empty(); // First analyze the end of BB branches. BBI.TrueBB = BBI.FalseBB = NULL; BBI.BrCond.clear(); @@ -788,8 +795,8 @@ IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB, unsigned Dups = 0; unsigned Dups2 = 0; - bool TNeedSub = TrueBBI.Predicate.size() > 0; - bool FNeedSub = FalseBBI.Predicate.size() > 0; + bool TNeedSub = !TrueBBI.Predicate.empty(); + bool FNeedSub = !FalseBBI.Predicate.empty(); bool Enqueued = false; BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB); @@ -964,9 +971,8 @@ static void InitPredRedefs(MachineBasicBlock *BB, SmallSet &Redefs, E = BB->livein_end(); I != E; ++I) { unsigned Reg = *I; Redefs.insert(Reg); - for (const unsigned *Subreg = TRI->getSubRegisters(Reg); - *Subreg; ++Subreg) - Redefs.insert(*Subreg); + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + Redefs.insert(*SubRegs); } } @@ -985,21 +991,20 @@ static void UpdatePredRedefs(MachineInstr *MI, SmallSet &Redefs, Defs.push_back(Reg); else if (MO.isKill()) { Redefs.erase(Reg); - for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) - Redefs.erase(*SR); + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + Redefs.erase(*SubRegs); } } + MachineInstrBuilder MIB(*MI->getParent()->getParent(), MI); for (unsigned i = 0, e = Defs.size(); i != e; ++i) { unsigned Reg = Defs[i]; - if (Redefs.count(Reg)) { + if (!Redefs.insert(Reg)) { if (AddImpUse) // Treat predicated update as read + write. - MI->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, - true/*IsImp*/,false/*IsKill*/)); + MIB.addReg(Reg, RegState::Implicit | RegState::Undef); } else { - Redefs.insert(Reg); - for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) - Redefs.insert(*SR); + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + Redefs.insert(*SubRegs); } } } @@ -1034,9 +1039,13 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { return false; } + if (CvtBBI->BB->hasAddressTaken()) + // Conservatively abort if-conversion if BB's address is taken. + return false; + if (Kind == ICSimpleFalse) if (TII->ReverseBranchCondition(Cond)) - assert(false && "Unable to reverse branch condition!"); + llvm_unreachable("Unable to reverse branch condition!"); // Initialize liveins to the first BB. These are potentiall redefined by // predicated instructions. @@ -1049,6 +1058,10 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { // Copy instructions in the true block, predicate them, and add them to // the entry block. CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs); + + // RemoveExtraEdges won't work if the block has an unanalyzable branch, so + // explicitly remove CvtBBI as a successor. + BBI.BB->removeSuccessor(CvtBBI->BB); } else { PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs); @@ -1107,9 +1120,13 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { return false; } + if (CvtBBI->BB->hasAddressTaken()) + // Conservatively abort if-conversion if BB's address is taken. + return false; + if (Kind == ICTriangleFalse || Kind == ICTriangleFRev) if (TII->ReverseBranchCondition(Cond)) - assert(false && "Unable to reverse branch condition!"); + llvm_unreachable("Unable to reverse branch condition!"); if (Kind == ICTriangleRev || Kind == ICTriangleFRev) { if (ReverseBranchCondition(*CvtBBI)) { @@ -1141,6 +1158,10 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { // Copy instructions in the true block, predicate them, and add them to // the entry block. CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs, true); + + // RemoveExtraEdges won't work if the block has an unanalyzable branch, so + // explicitly remove CvtBBI as a successor. + BBI.BB->removeSuccessor(CvtBBI->BB); } else { // Predicate the 'true' block after removing its branch. CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB); @@ -1156,7 +1177,7 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { SmallVector RevCond(CvtBBI->BrCond.begin(), CvtBBI->BrCond.end()); if (TII->ReverseBranchCondition(RevCond)) - assert(false && "Unable to reverse branch condition!"); + llvm_unreachable("Unable to reverse branch condition!"); TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl); BBI.BB->addSuccessor(CvtBBI->FalseBB); } @@ -1171,7 +1192,8 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { // block. By not merging them, we make it possible to iteratively // ifcvt the blocks. if (!HasEarlyExit && - NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough) { + NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough && + !NextBBI->BB->hasAddressTaken()) { MergeBlocks(BBI, *NextBBI); FalseBBDead = true; } else { @@ -1221,6 +1243,10 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, return false; } + if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken()) + // Conservatively abort if-conversion if either BB has its address taken. + return false; + // Put the predicated instructions from the 'true' block before the // instructions from the 'false' block, unless the true block would clobber // the predicate, in which case, do the opposite. @@ -1228,7 +1254,7 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, BBInfo *BBI2 = &FalseBBI; SmallVector RevCond(BBI.BrCond.begin(), BBI.BrCond.end()); if (TII->ReverseBranchCondition(RevCond)) - assert(false && "Unable to reverse branch condition!"); + llvm_unreachable("Unable to reverse branch condition!"); SmallVector *Cond1 = &BBI.BrCond; SmallVector *Cond2 = &RevCond; @@ -1337,8 +1363,8 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, // These are defined before ctrl flow reach the 'false' instructions. // They cannot be modified by the 'true' instructions. ExtUses.insert(Reg); - for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) - ExtUses.insert(*SR); + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + ExtUses.insert(*SubRegs); } } @@ -1346,8 +1372,8 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, unsigned Reg = Defs[i]; if (!ExtUses.count(Reg)) { RedefsByFalse.insert(Reg); - for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) - RedefsByFalse.insert(*SR); + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + RedefsByFalse.insert(*SubRegs); } } } @@ -1369,7 +1395,8 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind, // tail, add a unconditional branch to it. if (TailBB) { BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()]; - bool CanMergeTail = !TailBBI.HasFallThrough; + bool CanMergeTail = !TailBBI.HasFallThrough && + !TailBBI.BB->hasAddressTaken(); // There may still be a fall-through edge from BBI1 or BBI2 to TailBB; // check if there are any other predecessors besides those. unsigned NumPreds = TailBB->pred_size(); @@ -1538,6 +1565,9 @@ void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, /// i.e., when FromBBI's branch is being moved, add those successor edges to /// ToBBI. void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { + assert(!FromBBI.BB->hasAddressTaken() && + "Removing a BB whose address is taken!"); + ToBBI.BB->splice(ToBBI.BB->end(), FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end()); @@ -1552,7 +1582,7 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { if (Succ == FallThrough) continue; FromBBI.BB->removeSuccessor(Succ); - if (AddEdges) + if (AddEdges && !ToBBI.BB->isSuccessor(Succ)) ToBBI.BB->addSuccessor(Succ); }