X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FX86%2FX86PadShortFunction.cpp;h=83e75ea994cafec909d77eae3b4a285dca5246cc;hb=258d9b7bc021ebc78f5a3aef3907e225e632edfa;hp=05f8a62a75e79f5b65ccb0adca5785c0fec6ea1a;hpb=dd30b471750aca5c652873f9a8972df162b7e5eb;p=oota-llvm.git diff --git a/lib/Target/X86/X86PadShortFunction.cpp b/lib/Target/X86/X86PadShortFunction.cpp index 05f8a62a75e..83e75ea994c 100644 --- a/lib/Target/X86/X86PadShortFunction.cpp +++ b/lib/Target/X86/X86PadShortFunction.cpp @@ -13,7 +13,6 @@ // //===----------------------------------------------------------------------===// -#include #include #define DEBUG_TYPE "x86-pad-short-functions" @@ -24,44 +23,62 @@ #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/IR/Function.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" + using namespace llvm; STATISTIC(NumBBsPadded, "Number of basic blocks padded"); namespace { + struct VisitedBBInfo { + // HasReturn - Whether the BB contains a return instruction + bool HasReturn; + + // Cycles - Number of cycles until return if HasReturn is true, otherwise + // number of cycles until end of the BB + unsigned int Cycles; + + VisitedBBInfo() : HasReturn(false), Cycles(0) {} + VisitedBBInfo(bool HasReturn, unsigned int Cycles) + : HasReturn(HasReturn), Cycles(Cycles) {} + }; + struct PadShortFunc : public MachineFunctionPass { static char ID; PadShortFunc() : MachineFunctionPass(ID) - , Threshold(4) - {} + , Threshold(4), TM(0), TII(0) {} virtual bool runOnMachineFunction(MachineFunction &MF); - virtual const char *getPassName() const - { + virtual const char *getPassName() const { return "X86 Atom pad short functions"; } private: - bool addPadding(MachineFunction &MF, - MachineBasicBlock &MBB, + void findReturns(MachineBasicBlock *MBB, + unsigned int Cycles = 0); + + bool cyclesUntilReturn(MachineBasicBlock *MBB, + unsigned int &Cycles); + + void addPadding(MachineBasicBlock *MBB, MachineBasicBlock::iterator &MBBI, unsigned int NOOPsToAdd); - void findReturn(MachineFunction &MF, - MachineBasicBlock &MBB, - unsigned int Cycles); + const unsigned int Threshold; - bool cyclesUntilReturn(MachineFunction &MF, - MachineBasicBlock &MBB, - unsigned int &Cycles, - MachineBasicBlock::iterator *Location = 0); + // ReturnBBs - Maps basic blocks that return to the minimum number of + // cycles until the return, starting from the entry block. + DenseMap ReturnBBs; - const unsigned int Threshold; - std::map ReturnBBs; + // VisitedBBs - Cache of previously visited BBs. + DenseMap VisitedBBs; + + const TargetMachine *TM; + const TargetInstrInfo *TII; }; char PadShortFunc::ID = 0; @@ -74,111 +91,122 @@ FunctionPass *llvm::createX86PadShortFunctions() { /// runOnMachineFunction - Loop over all of the basic blocks, inserting /// NOOP instructions before early exits. bool PadShortFunc::runOnMachineFunction(MachineFunction &MF) { - // Process all basic blocks. - ReturnBBs.clear(); + const AttributeSet &FnAttrs = MF.getFunction()->getAttributes(); + if (FnAttrs.hasAttribute(AttributeSet::FunctionIndex, + Attribute::OptimizeForSize) || + FnAttrs.hasAttribute(AttributeSet::FunctionIndex, + Attribute::MinSize)) { + return false; + } + + TM = &MF.getTarget(); + TII = TM->getInstrInfo(); // Search through basic blocks and mark the ones that have early returns - findReturn(MF, *MF.begin(), 0); + ReturnBBs.clear(); + VisitedBBs.clear(); + findReturns(MF.begin()); - int BBNum; - MachineBasicBlock::iterator ReturnLoc; - MachineBasicBlock *MBB; + bool MadeChange = false; + MachineBasicBlock *MBB; unsigned int Cycles = 0; - unsigned int BBCycles; // Pad the identified basic blocks with NOOPs - for (std::map::iterator I = ReturnBBs.begin(); + for (DenseMap::iterator I = ReturnBBs.begin(); I != ReturnBBs.end(); ++I) { - BBNum = I->first; + MBB = I->first; Cycles = I->second; if (Cycles < Threshold) { - MBB = MF.getBlockNumbered(BBNum); - if (!cyclesUntilReturn(MF, *MBB, BBCycles, &ReturnLoc)) - continue; - - addPadding(MF, *MBB, ReturnLoc, Threshold - Cycles); + // BB ends in a return. Skip over any DBG_VALUE instructions + // trailing the terminator. + assert(MBB->size() > 0 && + "Basic block should contain at least a RET but is empty"); + MachineBasicBlock::iterator ReturnLoc = --MBB->end(); + + while (ReturnLoc->isDebugValue()) + --ReturnLoc; + assert(ReturnLoc->isReturn() && !ReturnLoc->isCall() && + "Basic block does not end with RET"); + + addPadding(MBB, ReturnLoc, Threshold - Cycles); NumBBsPadded++; + MadeChange = true; } } - return false; + return MadeChange; } /// findReturn - Starting at MBB, follow control flow and add all /// basic blocks that contain a return to ReturnBBs. -void PadShortFunc::findReturn(MachineFunction &MF, - MachineBasicBlock &MBB, - unsigned int Cycles) -{ +void PadShortFunc::findReturns(MachineBasicBlock *MBB, unsigned int Cycles) { // If this BB has a return, note how many cycles it takes to get there. - bool hasReturn = cyclesUntilReturn(MF, MBB, Cycles); + bool hasReturn = cyclesUntilReturn(MBB, Cycles); if (Cycles >= Threshold) return; if (hasReturn) { - int BBNum = MBB.getNumber(); - ReturnBBs[BBNum] = std::max(ReturnBBs[BBNum], Cycles); - + ReturnBBs[MBB] = std::max(ReturnBBs[MBB], Cycles); return; } // Follow branches in BB and look for returns - for (MachineBasicBlock::succ_iterator I = MBB.succ_begin(); - I != MBB.succ_end(); ++I) { - findReturn(MF, **I, Cycles); + for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(); + I != MBB->succ_end(); ++I) { + if (*I == MBB) + continue; + findReturns(*I, Cycles); } } -/// cyclesUntilReturn - if the MBB has a return instruction, set Location to -/// to the instruction and return true. Return false otherwise. +/// cyclesUntilReturn - return true if the MBB has a return instruction, +/// and return false otherwise. /// Cycles will be incremented by the number of cycles taken to reach the /// return or the end of the BB, whichever occurs first. -bool PadShortFunc::cyclesUntilReturn(MachineFunction &MF, - MachineBasicBlock &MBB, - unsigned int &Cycles, - MachineBasicBlock::iterator *Location) -{ - const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); - const TargetMachine &Target = MF.getTarget(); - - for (MachineBasicBlock::iterator MBBI = MBB.begin(); MBBI != MBB.end(); - ++MBBI) { +bool PadShortFunc::cyclesUntilReturn(MachineBasicBlock *MBB, + unsigned int &Cycles) { + // Return cached result if BB was previously visited + DenseMap::iterator it + = VisitedBBs.find(MBB); + if (it != VisitedBBs.end()) { + VisitedBBInfo BBInfo = it->second; + Cycles += BBInfo.Cycles; + return BBInfo.HasReturn; + } + + unsigned int CyclesToEnd = 0; + + for (MachineBasicBlock::iterator MBBI = MBB->begin(); + MBBI != MBB->end(); ++MBBI) { MachineInstr *MI = MBBI; - // Mark basic blocks with a return instruction. Calls to other functions - // do not count because the called function will be padded, if necessary + // Mark basic blocks with a return instruction. Calls to other + // functions do not count because the called function will be padded, + // if necessary. if (MI->isReturn() && !MI->isCall()) { - if (Location) - *Location = MBBI; + VisitedBBs[MBB] = VisitedBBInfo(true, CyclesToEnd); + Cycles += CyclesToEnd; return true; } - Cycles += TII.getInstrLatency(Target.getInstrItineraryData(), MI); + CyclesToEnd += TII->getInstrLatency(TM->getInstrItineraryData(), MI); } + VisitedBBs[MBB] = VisitedBBInfo(false, CyclesToEnd); + Cycles += CyclesToEnd; return false; } /// addPadding - Add the given number of NOOP instructions to the function -/// right before the return at MBBI -bool PadShortFunc::addPadding(MachineFunction &MF, - MachineBasicBlock &MBB, +/// just prior to the return at MBBI +void PadShortFunc::addPadding(MachineBasicBlock *MBB, MachineBasicBlock::iterator &MBBI, - unsigned int NOOPsToAdd) -{ - const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); - + unsigned int NOOPsToAdd) { DebugLoc DL = MBBI->getDebugLoc(); while (NOOPsToAdd-- > 0) { - // Since Atom has two instruction execution ports, - // the code emits two noops, which will be executed in parallell - // during one cycle. - BuildMI(MBB, MBBI, DL, TII.get(X86::NOOP)); - BuildMI(MBB, MBBI, DL, TII.get(X86::NOOP)); + BuildMI(*MBB, MBBI, DL, TII->get(X86::NOOP)); + BuildMI(*MBB, MBBI, DL, TII->get(X86::NOOP)); } - - return true; } -