//
//===----------------------------------------------------------------------===//
-#include <map>
#include <algorithm>
-#define DEBUG_TYPE "x86-pad-short-functions"
#include "X86.h"
#include "X86InstrInfo.h"
+#include "X86Subtarget.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#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;
+#define DEBUG_TYPE "x86-pad-short-functions"
+
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(nullptr), TII(nullptr) {}
- virtual bool runOnMachineFunction(MachineFunction &MF);
+ bool runOnMachineFunction(MachineFunction &MF) override;
- virtual const char *getPassName() const
- {
+ const char *getPassName() const override {
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<MachineBasicBlock*, unsigned int> ReturnBBs;
- const unsigned int Threshold;
- std::map<int, unsigned int> ReturnBBs;
+ // VisitedBBs - Cache of previously visited BBs.
+ DenseMap<MachineBasicBlock*, VisitedBBInfo> VisitedBBs;
+
+ const TargetMachine *TM;
+ const TargetInstrInfo *TII;
};
char PadShortFunc::ID = 0;
/// 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();
+ if (!TM->getSubtarget<X86Subtarget>().padShortFunctions())
+ return false;
+
+ TII = TM->getSubtargetImpl()->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<int, unsigned int>::iterator I = ReturnBBs.begin();
+ for (DenseMap<MachineBasicBlock*, unsigned int>::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<MachineBasicBlock*, VisitedBBInfo>::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->getSubtargetImpl()->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;
}
-
projects / oota-llvm.git / blobdiff