X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FEarlyIfConversion.cpp;h=f3536d74111e5dac8d2261a322060232028b571f;hb=a79baf560c40745a008bc8a3584efa6b14201ee5;hp=ab64c80cb8e6bd7652d8c2b85fa69f18112b884c;hpb=eb74c08192d9c9425b2d8cf08852e9e787a87881;p=oota-llvm.git diff --git a/lib/CodeGen/EarlyIfConversion.cpp b/lib/CodeGen/EarlyIfConversion.cpp index ab64c80cb8e..f3536d74111 100644 --- a/lib/CodeGen/EarlyIfConversion.cpp +++ b/lib/CodeGen/EarlyIfConversion.cpp @@ -16,30 +16,31 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "early-ifcvt" -#include "MachineTraceMetrics.h" -#include "llvm/Function.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SparseSet.h" +#include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/MachineTraceMetrics.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/MC/MCInstrItineraries.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; +#define DEBUG_TYPE "early-ifcvt" + // Absolute maximum number of instructions allowed per speculated block. // This bypasses all other heuristics, so it should be set fairly high. static cl::opt @@ -50,7 +51,10 @@ BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden, static cl::opt Stress("stress-early-ifcvt", cl::Hidden, cl::desc("Turn all knobs to 11")); -typedef SmallSetVector BlockSetVector; +STATISTIC(NumDiamondsSeen, "Number of diamonds"); +STATISTIC(NumDiamondsConv, "Number of diamonds converted"); +STATISTIC(NumTrianglesSeen, "Number of triangles"); +STATISTIC(NumTrianglesConv, "Number of triangles converted"); //===----------------------------------------------------------------------===// // SSAIfConv @@ -140,11 +144,17 @@ private: /// Find a valid insertion point in Head. bool findInsertionPoint(); + /// Replace PHI instructions in Tail with selects. + void replacePHIInstrs(); + + /// Insert selects and rewrite PHI operands to use them. + void rewritePHIOperands(); + public: /// runOnMachineFunction - Initialize per-function data structures. void runOnMachineFunction(MachineFunction &MF) { - TII = MF.getTarget().getInstrInfo(); - TRI = MF.getTarget().getRegisterInfo(); + TII = MF.getSubtarget().getInstrInfo(); + TRI = MF.getSubtarget().getRegisterInfo(); MRI = &MF.getRegInfo(); LiveRegUnits.clear(); LiveRegUnits.setUniverse(TRI->getNumRegUnits()); @@ -210,32 +220,32 @@ bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) { // We never speculate stores, so an AA pointer isn't necessary. bool DontMoveAcrossStore = true; - if (!I->isSafeToMove(TII, 0, DontMoveAcrossStore)) { + if (!I->isSafeToMove(nullptr, DontMoveAcrossStore)) { DEBUG(dbgs() << "Can't speculate: " << *I); return false; } // Check for any dependencies on Head instructions. - for (MIOperands MO(I); MO.isValid(); ++MO) { - if (MO->isRegMask()) { + for (const MachineOperand &MO : I->operands()) { + if (MO.isRegMask()) { DEBUG(dbgs() << "Won't speculate regmask: " << *I); return false; } - if (!MO->isReg()) + if (!MO.isReg()) continue; - unsigned Reg = MO->getReg(); + unsigned Reg = MO.getReg(); // Remember clobbered regunits. - if (MO->isDef() && TargetRegisterInfo::isPhysicalRegister(Reg)) + if (MO.isDef() && TargetRegisterInfo::isPhysicalRegister(Reg)) for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) ClobberedRegUnits.set(*Units); - if (!MO->readsReg() || !TargetRegisterInfo::isVirtualRegister(Reg)) + if (!MO.readsReg() || !TargetRegisterInfo::isVirtualRegister(Reg)) continue; MachineInstr *DefMI = MRI->getVRegDef(Reg); if (!DefMI || DefMI->getParent() != Head) continue; - if (InsertAfter.insert(DefMI)) + if (InsertAfter.insert(DefMI).second) DEBUG(dbgs() << "BB#" << MBB->getNumber() << " depends on " << *DefMI); if (DefMI->isTerminator()) { DEBUG(dbgs() << "Can't insert instructions below terminator.\n"); @@ -274,19 +284,19 @@ bool SSAIfConv::findInsertionPoint() { } // Update live regunits. - for (MIOperands MO(I); MO.isValid(); ++MO) { + for (const MachineOperand &MO : I->operands()) { // We're ignoring regmask operands. That is conservatively correct. - if (!MO->isReg()) + if (!MO.isReg()) continue; - unsigned Reg = MO->getReg(); + unsigned Reg = MO.getReg(); if (!TargetRegisterInfo::isPhysicalRegister(Reg)) continue; // I clobbers Reg, so it isn't live before I. - if (MO->isDef()) + if (MO.isDef()) for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) LiveRegUnits.erase(*Units); // Unless I reads Reg. - if (MO->readsReg()) + if (MO.readsReg()) Reads.push_back(Reg); } // Anything read by I is live before I. @@ -329,7 +339,7 @@ bool SSAIfConv::findInsertionPoint() { /// bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) { Head = MBB; - TBB = FBB = Tail = 0; + TBB = FBB = Tail = nullptr; if (Head->succ_size() != 2) return false; @@ -343,11 +353,7 @@ bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) { if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1) return false; - // We could support additional Tail predecessors by updating phis instead of - // eliminating them. Let's see an example where it matters first. Tail = Succ0->succ_begin()[0]; - if (Tail->pred_size() != 2) - return false; // This is not a triangle. if (Tail != Succ1) { @@ -434,9 +440,74 @@ bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) { if (!findInsertionPoint()) return false; + if (isTriangle()) + ++NumTrianglesSeen; + else + ++NumDiamondsSeen; return true; } +/// replacePHIInstrs - Completely replace PHI instructions with selects. +/// This is possible when the only Tail predecessors are the if-converted +/// blocks. +void SSAIfConv::replacePHIInstrs() { + assert(Tail->pred_size() == 2 && "Cannot replace PHIs"); + MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); + assert(FirstTerm != Head->end() && "No terminators"); + DebugLoc HeadDL = FirstTerm->getDebugLoc(); + + // Convert all PHIs to select instructions inserted before FirstTerm. + for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { + PHIInfo &PI = PHIs[i]; + DEBUG(dbgs() << "If-converting " << *PI.PHI); + unsigned DstReg = PI.PHI->getOperand(0).getReg(); + TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); + DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); + PI.PHI->eraseFromParent(); + PI.PHI = nullptr; + } +} + +/// rewritePHIOperands - When there are additional Tail predecessors, insert +/// select instructions in Head and rewrite PHI operands to use the selects. +/// Keep the PHI instructions in Tail to handle the other predecessors. +void SSAIfConv::rewritePHIOperands() { + MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); + assert(FirstTerm != Head->end() && "No terminators"); + DebugLoc HeadDL = FirstTerm->getDebugLoc(); + + // Convert all PHIs to select instructions inserted before FirstTerm. + for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { + PHIInfo &PI = PHIs[i]; + unsigned DstReg = 0; + + DEBUG(dbgs() << "If-converting " << *PI.PHI); + if (PI.TReg == PI.FReg) { + // We do not need the select instruction if both incoming values are + // equal. + DstReg = PI.TReg; + } else { + unsigned PHIDst = PI.PHI->getOperand(0).getReg(); + DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst)); + TII->insertSelect(*Head, FirstTerm, HeadDL, + DstReg, Cond, PI.TReg, PI.FReg); + DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); + } + + // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred. + for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) { + MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB(); + if (MBB == getTPred()) { + PI.PHI->getOperand(i-1).setMBB(Head); + PI.PHI->getOperand(i-2).setReg(DstReg); + } else if (MBB == getFPred()) { + PI.PHI->RemoveOperand(i-1); + PI.PHI->RemoveOperand(i-2); + } + } + DEBUG(dbgs() << " --> " << *PI.PHI); + } +} /// convertIf - Execute the if conversion after canConvertIf has determined the /// feasibility. @@ -446,38 +517,36 @@ bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) { void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks) { assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); + // Update statistics. + if (isTriangle()) + ++NumTrianglesConv; + else + ++NumDiamondsConv; + // Move all instructions into Head, except for the terminators. if (TBB != Tail) Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator()); if (FBB != Tail) Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator()); - MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); - assert(FirstTerm != Head->end() && "No terminators"); - DebugLoc HeadDL = FirstTerm->getDebugLoc(); - - // Convert all PHIs to select instructions inserted before FirstTerm. - for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { - PHIInfo &PI = PHIs[i]; - DEBUG(dbgs() << "If-converting " << *PI.PHI); - assert(PI.PHI->getNumOperands() == 5 && "Unexpected PHI operands."); - unsigned DstReg = PI.PHI->getOperand(0).getReg(); - TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); - DEBUG(dbgs() << " --> " << *llvm::prior(FirstTerm)); - PI.PHI->eraseFromParent(); - PI.PHI = 0; - } + // Are there extra Tail predecessors? + bool ExtraPreds = Tail->pred_size() != 2; + if (ExtraPreds) + rewritePHIOperands(); + else + replacePHIInstrs(); // Fix up the CFG, temporarily leave Head without any successors. Head->removeSuccessor(TBB); - Head->removeSuccessor(FBB); + Head->removeSuccessor(FBB, true); if (TBB != Tail) - TBB->removeSuccessor(Tail); + TBB->removeSuccessor(Tail, true); if (FBB != Tail) - FBB->removeSuccessor(Tail); + FBB->removeSuccessor(Tail, true); // Fix up Head's terminators. // It should become a single branch or a fallthrough. + DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc(); TII->RemoveBranch(*Head); // Erase the now empty conditional blocks. It is likely that Head can fall @@ -492,7 +561,7 @@ void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks) { } assert(Head->succ_empty() && "Additional head successors?"); - if (Head->isLayoutSuccessor(Tail)) { + if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) { // Splice Tail onto the end of Head. DEBUG(dbgs() << "Joining tail BB#" << Tail->getNumber() << " into head BB#" << Head->getNumber() << '\n'); @@ -505,7 +574,7 @@ void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks) { // We need a branch to Tail, let code placement work it out later. DEBUG(dbgs() << "Converting to unconditional branch.\n"); SmallVector EmptyCond; - TII->InsertBranch(*Head, Tail, 0, EmptyCond, HeadDL); + TII->InsertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL); Head->addSuccessor(Tail); } DEBUG(dbgs() << *Head); @@ -520,7 +589,7 @@ namespace { class EarlyIfConverter : public MachineFunctionPass { const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; - const MCSchedModel *SchedModel; + MCSchedModel SchedModel; MachineRegisterInfo *MRI; MachineDominatorTree *DomTree; MachineLoopInfo *Loops; @@ -531,8 +600,9 @@ class EarlyIfConverter : public MachineFunctionPass { public: static char ID; EarlyIfConverter() : MachineFunctionPass(ID) {} - void getAnalysisUsage(AnalysisUsage &AU) const; - bool runOnMachineFunction(MachineFunction &MF); + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnMachineFunction(MachineFunction &MF) override; + const char *getPassName() const override { return "Early If-Conversion"; } private: bool tryConvertIf(MachineBasicBlock*); @@ -627,7 +697,7 @@ bool EarlyIfConverter::shouldConvertIf() { FBBTrace.getCriticalPath()); // Set a somewhat arbitrary limit on the critical path extension we accept. - unsigned CritLimit = SchedModel->MispredictPenalty/2; + unsigned CritLimit = SchedModel.MispredictPenalty/2; // If-conversion only makes sense when there is unexploited ILP. Compute the // maximum-ILP resource length of the trace after if-conversion. Compare it @@ -714,16 +784,20 @@ bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) { bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" - << "********** Function: " - << ((Value*)MF.getFunction())->getName() << '\n'); - TII = MF.getTarget().getInstrInfo(); - TRI = MF.getTarget().getRegisterInfo(); - SchedModel = MF.getTarget().getInstrItineraryData()->SchedModel; + << "********** Function: " << MF.getName() << '\n'); + // Only run if conversion if the target wants it. + const TargetSubtargetInfo &STI = MF.getSubtarget(); + if (!STI.enableEarlyIfConversion()) + return false; + + TII = STI.getInstrInfo(); + TRI = STI.getRegisterInfo(); + SchedModel = STI.getSchedModel(); MRI = &MF.getRegInfo(); DomTree = &getAnalysis(); Loops = getAnalysisIfAvailable(); Traces = &getAnalysis(); - MinInstr = 0; + MinInstr = nullptr; bool Changed = false; IfConv.runOnMachineFunction(MF); @@ -732,11 +806,9 @@ bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { // if-conversion in a single pass. The tryConvertIf() function may erase // blocks, but only blocks dominated by the head block. This makes it safe to // update the dominator tree while the post-order iterator is still active. - for (po_iterator - I = po_begin(DomTree), E = po_end(DomTree); I != E; ++I) - if (tryConvertIf(I->getBlock())) + for (auto DomNode : post_order(DomTree)) + if (tryConvertIf(DomNode->getBlock())) Changed = true; - MF.verify(this, "After early if-conversion"); return Changed; }