X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FEarlyIfConversion.cpp;h=7f28828a5d20adf606408958f5e189aac6f3617e;hb=10ad98bbbb00d67d4272e8f29186a65e2a75215e;hp=ab64c80cb8e6bd7652d8c2b85fa69f18112b884c;hpb=eb74c08192d9c9425b2d8cf08852e9e787a87881;p=oota-llvm.git diff --git a/lib/CodeGen/EarlyIfConversion.cpp b/lib/CodeGen/EarlyIfConversion.cpp index ab64c80cb8e..7f28828a5d2 100644 --- a/lib/CodeGen/EarlyIfConversion.cpp +++ b/lib/CodeGen/EarlyIfConversion.cpp @@ -18,12 +18,12 @@ #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" @@ -31,9 +31,9 @@ #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/MC/MCInstrItineraries.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -50,7 +50,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,6 +143,12 @@ 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) { @@ -343,11 +352,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,24 +439,18 @@ bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) { if (!findInsertionPoint()) return false; + if (isTriangle()) + ++NumTrianglesSeen; + else + ++NumDiamondsSeen; return true; } - -/// convertIf - Execute the if conversion after canConvertIf has determined the -/// feasibility. -/// -/// Any basic blocks erased will be added to RemovedBlocks. -/// -void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks) { - assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); - - // 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()); - +/// 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(); @@ -467,6 +466,66 @@ void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks) { PI.PHI->eraseFromParent(); PI.PHI = 0; } +} + +/// 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]; + DEBUG(dbgs() << "If-converting " << *PI.PHI); + unsigned PHIDst = PI.PHI->getOperand(0).getReg(); + unsigned DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst)); + TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); + DEBUG(dbgs() << " --> " << *llvm::prior(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. +/// +/// Any basic blocks erased will be added to RemovedBlocks. +/// +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()); + + // 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); @@ -478,6 +537,7 @@ void SSAIfConv::convertIf(SmallVectorImpl &RemovedBlocks) { // 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 +552,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'); @@ -714,11 +774,11 @@ bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) { bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" - << "********** Function: " - << ((Value*)MF.getFunction())->getName() << '\n'); + << "********** Function: " << MF.getName() << '\n'); TII = MF.getTarget().getInstrInfo(); TRI = MF.getTarget().getRegisterInfo(); - SchedModel = MF.getTarget().getInstrItineraryData()->SchedModel; + SchedModel = + MF.getTarget().getSubtarget().getSchedModel(); MRI = &MF.getRegInfo(); DomTree = &getAnalysis(); Loops = getAnalysisIfAvailable();