#include "llvm/CodeGen/FunctionLoweringInfo.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/DebugInfo.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
using namespace llvm;
STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
+STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
-#ifndef NDEBUG
-STATISTIC(NumBBWithOutOfOrderLineInfo,
- "Number of blocks with out of order line number info");
-STATISTIC(NumMBBWithOutOfOrderLineInfo,
- "Number of machine blocks with out of order line number info");
-#endif
-
static cl::opt<bool>
EnableFastISelVerbose("fast-isel-verbose", cl::Hidden,
cl::desc("Enable verbose messages in the \"fast\" "
EnableFastISelAbort("fast-isel-abort", cl::Hidden,
cl::desc("Enable abort calls when \"fast\" instruction fails"));
+static cl::opt<bool>
+UseMBPI("use-mbpi",
+ cl::desc("use Machine Branch Probability Info"),
+ cl::init(true), cl::Hidden);
+
#ifndef NDEBUG
static cl::opt<bool>
ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
DAGSize(0) {
initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());
initializeAliasAnalysisAnalysisGroup(*PassRegistry::getPassRegistry());
+ initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry());
}
SelectionDAGISel::~SelectionDAGISel() {
AU.addPreserved<AliasAnalysis>();
AU.addRequired<GCModuleInfo>();
AU.addPreserved<GCModuleInfo>();
+ if (UseMBPI && OptLevel != CodeGenOpt::None)
+ AU.addRequired<BranchProbabilityInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
-/// FunctionCallsSetJmp - Return true if the function has a call to setjmp or
-/// other function that gcc recognizes as "returning twice". This is used to
-/// limit code-gen optimizations on the machine function.
-///
-/// FIXME: Remove after <rdar://problem/8031714> is fixed.
-static bool FunctionCallsSetJmp(const Function *F) {
- const Module *M = F->getParent();
- static const char *ReturnsTwiceFns[] = {
- "_setjmp",
- "setjmp",
- "sigsetjmp",
- "setjmp_syscall",
- "savectx",
- "qsetjmp",
- "vfork",
- "getcontext"
- };
-#define NUM_RETURNS_TWICE_FNS sizeof(ReturnsTwiceFns) / sizeof(const char *)
-
- for (unsigned I = 0; I < NUM_RETURNS_TWICE_FNS; ++I)
- if (const Function *Callee = M->getFunction(ReturnsTwiceFns[I])) {
- if (!Callee->use_empty())
- for (Value::const_use_iterator
- I = Callee->use_begin(), E = Callee->use_end();
- I != E; ++I)
- if (const CallInst *CI = dyn_cast<CallInst>(*I))
- if (CI->getParent()->getParent() == F)
- return true;
- }
-
- return false;
-#undef NUM_RETURNS_TWICE_FNS
-}
-
/// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
/// may trap on it. In this case we have to split the edge so that the path
/// through the predecessor block that doesn't go to the phi block doesn't
CurDAG->init(*MF);
FuncInfo->set(Fn, *MF);
+
+ if (UseMBPI && OptLevel != CodeGenOpt::None)
+ FuncInfo->BPI = &getAnalysis<BranchProbabilityInfo>();
+ else
+ FuncInfo->BPI = 0;
+
SDB->init(GFI, *AA);
SelectAllBasicBlocks(Fn);
}
// Determine if there is a call to setjmp in the machine function.
- MF->setCallsSetJmp(FunctionCallsSetJmp(&Fn));
+ MF->setCallsSetJmp(Fn.callsFunctionThatReturnsTwice());
// Replace forward-declared registers with the registers containing
// the desired value.
return true;
}
-void
-SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
- BasicBlock::const_iterator End,
- bool &HadTailCall) {
+void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
+ BasicBlock::const_iterator End,
+ bool &HadTailCall) {
// Lower all of the non-terminator instructions. If a call is emitted
// as a tail call, cease emitting nodes for this block. Terminators
// are handled below.
// Final step, emit the lowered DAG as machine code.
CodeGenAndEmitDAG();
- return;
}
void SelectionDAGISel::ComputeLiveOutVRegInfo() {
if (TimePassesIsEnabled)
GroupName = "Instruction Selection and Scheduling";
std::string BlockName;
+ int BlockNumber = -1;
+#ifdef NDEBUG
if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
ViewSUnitDAGs)
+#endif
+ {
+ BlockNumber = FuncInfo->MBB->getNumber();
BlockName = MF->getFunction()->getNameStr() + ":" +
FuncInfo->MBB->getBasicBlock()->getNameStr();
-
- DEBUG(dbgs() << "Initial selection DAG:\n"; CurDAG->dump());
+ }
+ DEBUG(dbgs() << "Initial selection DAG: BB#" << BlockNumber
+ << " '" << BlockName << "'\n"; CurDAG->dump());
if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName);
CurDAG->Combine(Unrestricted, *AA, OptLevel);
}
- DEBUG(dbgs() << "Optimized lowered selection DAG:\n"; CurDAG->dump());
+ DEBUG(dbgs() << "Optimized lowered selection DAG: BB#" << BlockNumber
+ << " '" << BlockName << "'\n"; CurDAG->dump());
// Second step, hack on the DAG until it only uses operations and types that
// the target supports.
Changed = CurDAG->LegalizeTypes();
}
- DEBUG(dbgs() << "Type-legalized selection DAG:\n"; CurDAG->dump());
+ DEBUG(dbgs() << "Type-legalized selection DAG: BB#" << BlockNumber
+ << " '" << BlockName << "'\n"; CurDAG->dump());
if (Changed) {
if (ViewDAGCombineLT)
CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
}
- DEBUG(dbgs() << "Optimized type-legalized selection DAG:\n";
- CurDAG->dump());
+ DEBUG(dbgs() << "Optimized type-legalized selection DAG: BB#" << BlockNumber
+ << " '" << BlockName << "'\n"; CurDAG->dump());
}
{
CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
}
- DEBUG(dbgs() << "Optimized vector-legalized selection DAG:\n";
- CurDAG->dump());
+ DEBUG(dbgs() << "Optimized vector-legalized selection DAG: BB#"
+ << BlockNumber << " '" << BlockName << "'\n"; CurDAG->dump());
}
if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName);
{
NamedRegionTimer T("DAG Legalization", GroupName, TimePassesIsEnabled);
- CurDAG->Legalize(OptLevel);
+ CurDAG->Legalize();
}
- DEBUG(dbgs() << "Legalized selection DAG:\n"; CurDAG->dump());
+ DEBUG(dbgs() << "Legalized selection DAG: BB#" << BlockNumber
+ << " '" << BlockName << "'\n"; CurDAG->dump());
if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName);
CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
}
- DEBUG(dbgs() << "Optimized legalized selection DAG:\n"; CurDAG->dump());
+ DEBUG(dbgs() << "Optimized legalized selection DAG: BB#" << BlockNumber
+ << " '" << BlockName << "'\n"; CurDAG->dump());
if (OptLevel != CodeGenOpt::None)
ComputeLiveOutVRegInfo();
DoInstructionSelection();
}
- DEBUG(dbgs() << "Selected selection DAG:\n"; CurDAG->dump());
+ DEBUG(dbgs() << "Selected selection DAG: BB#" << BlockNumber
+ << " '" << BlockName << "'\n"; CurDAG->dump());
if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName);
}
void SelectionDAGISel::DoInstructionSelection() {
- DEBUG(errs() << "===== Instruction selection begins:\n");
+ DEBUG(errs() << "===== Instruction selection begins: BB#"
+ << FuncInfo->MBB->getNumber()
+ << " '" << FuncInfo->MBB->getName() << "'\n");
PreprocessISelDAG();
-
+/// TryToFoldFastISelLoad - We're checking to see if we can fold the specified
+/// load into the specified FoldInst. Note that we could have a sequence where
+/// multiple LLVM IR instructions are folded into the same machineinstr. For
+/// example we could have:
+/// A: x = load i32 *P
+/// B: y = icmp A, 42
+/// C: br y, ...
+///
+/// In this scenario, LI is "A", and FoldInst is "C". We know about "B" (and
+/// any other folded instructions) because it is between A and C.
+///
+/// If we succeed in folding the load into the operation, return true.
+///
bool SelectionDAGISel::TryToFoldFastISelLoad(const LoadInst *LI,
+ const Instruction *FoldInst,
FastISel *FastIS) {
+ // We know that the load has a single use, but don't know what it is. If it
+ // isn't one of the folded instructions, then we can't succeed here. Handle
+ // this by scanning the single-use users of the load until we get to FoldInst.
+ unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs.
+
+ const Instruction *TheUser = LI->use_back();
+ while (TheUser != FoldInst && // Scan up until we find FoldInst.
+ // Stay in the right block.
+ TheUser->getParent() == FoldInst->getParent() &&
+ --MaxUsers) { // Don't scan too far.
+ // If there are multiple or no uses of this instruction, then bail out.
+ if (!TheUser->hasOneUse())
+ return false;
+
+ TheUser = TheUser->use_back();
+ }
+
// Don't try to fold volatile loads. Target has to deal with alignment
// constraints.
if (LI->isVolatile()) return false;
- // Figure out which vreg this is going into.
+ // Figure out which vreg this is going into. If there is no assigned vreg yet
+ // then there actually was no reference to it. Perhaps the load is referenced
+ // by a dead instruction.
unsigned LoadReg = FastIS->getRegForValue(LI);
- assert(LoadReg && "Load isn't already assigned a vreg? ");
+ if (LoadReg == 0)
+ return false;
// Check to see what the uses of this vreg are. If it has no uses, or more
// than one use (at the machine instr level) then we can't fold it.
return FastIS->TryToFoldLoad(User, RI.getOperandNo(), LI);
}
-#ifndef NDEBUG
-/// CheckLineNumbers - Check if basic block instructions follow source order
-/// or not.
-static void CheckLineNumbers(const BasicBlock *BB) {
- unsigned Line = 0;
- unsigned Col = 0;
- for (BasicBlock::const_iterator BI = BB->begin(),
- BE = BB->end(); BI != BE; ++BI) {
- const DebugLoc DL = BI->getDebugLoc();
- if (DL.isUnknown()) continue;
- unsigned L = DL.getLine();
- unsigned C = DL.getCol();
- if (L < Line || (L == Line && C < Col)) {
- ++NumBBWithOutOfOrderLineInfo;
- return;
- }
- Line = L;
- Col = C;
- }
+/// isFoldedOrDeadInstruction - Return true if the specified instruction is
+/// side-effect free and is either dead or folded into a generated instruction.
+/// Return false if it needs to be emitted.
+static bool isFoldedOrDeadInstruction(const Instruction *I,
+ FunctionLoweringInfo *FuncInfo) {
+ return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
+ !isa<TerminatorInst>(I) && // Terminators aren't folded.
+ !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded.
+ !FuncInfo->isExportedInst(I); // Exported instrs must be computed.
}
-/// CheckLineNumbers - Check if machine basic block instructions follow source
-/// order or not.
-static void CheckLineNumbers(const MachineBasicBlock *MBB) {
- unsigned Line = 0;
- unsigned Col = 0;
- for (MachineBasicBlock::const_iterator MBI = MBB->begin(),
- MBE = MBB->end(); MBI != MBE; ++MBI) {
- const DebugLoc DL = MBI->getDebugLoc();
- if (DL.isUnknown()) continue;
- unsigned L = DL.getLine();
- unsigned C = DL.getCol();
- if (L < Line || (L == Line && C < Col)) {
- ++NumMBBWithOutOfOrderLineInfo;
- return;
- }
- Line = L;
- Col = C;
- }
-}
-#endif
-
void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
// Initialize the Fast-ISel state, if needed.
FastISel *FastIS = 0;
for (ReversePostOrderTraversal<const Function*>::rpo_iterator
I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
const BasicBlock *LLVMBB = *I;
-#ifndef NDEBUG
- CheckLineNumbers(LLVMBB);
-#endif
if (OptLevel != CodeGenOpt::None) {
bool AllPredsVisited = true;
}
if (AllPredsVisited) {
- for (BasicBlock::const_iterator I = LLVMBB->begin(), E = LLVMBB->end();
- I != E && isa<PHINode>(I); ++I) {
+ for (BasicBlock::const_iterator I = LLVMBB->begin();
+ isa<PHINode>(I); ++I)
FuncInfo->ComputePHILiveOutRegInfo(cast<PHINode>(I));
- }
} else {
- for (BasicBlock::const_iterator I = LLVMBB->begin(), E = LLVMBB->end();
- I != E && isa<PHINode>(I); ++I) {
+ for (BasicBlock::const_iterator I = LLVMBB->begin();
+ isa<PHINode>(I); ++I)
FuncInfo->InvalidatePHILiveOutRegInfo(cast<PHINode>(I));
- }
}
FuncInfo->VisitedBBs.insert(LLVMBB);
const Instruction *Inst = llvm::prior(BI);
// If we no longer require this instruction, skip it.
- if (!Inst->mayWriteToMemory() &&
- !isa<TerminatorInst>(Inst) &&
- !isa<DbgInfoIntrinsic>(Inst) &&
- !FuncInfo->isExportedInst(Inst))
+ if (isFoldedOrDeadInstruction(Inst, FuncInfo))
continue;
// Bottom-up: reset the insert pos at the top, after any local-value
// Try to select the instruction with FastISel.
if (FastIS->SelectInstruction(Inst)) {
- // If fast isel succeeded, check to see if there is a single-use
- // non-volatile load right before the selected instruction, and see if
- // the load is used by the instruction. If so, try to fold it.
- const Instruction *BeforeInst = 0;
- if (Inst != Begin)
- BeforeInst = llvm::prior(llvm::prior(BI));
- if (BeforeInst && isa<LoadInst>(BeforeInst) &&
- BeforeInst->hasOneUse() && *BeforeInst->use_begin() == Inst &&
- TryToFoldFastISelLoad(cast<LoadInst>(BeforeInst), FastIS))
- --BI; // If we succeeded, don't re-select the load.
+ ++NumFastIselSuccess;
+ // If fast isel succeeded, skip over all the folded instructions, and
+ // then see if there is a load right before the selected instructions.
+ // Try to fold the load if so.
+ const Instruction *BeforeInst = Inst;
+ while (BeforeInst != Begin) {
+ BeforeInst = llvm::prior(BasicBlock::const_iterator(BeforeInst));
+ if (!isFoldedOrDeadInstruction(BeforeInst, FuncInfo))
+ break;
+ }
+ if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
+ BeforeInst->hasOneUse() &&
+ TryToFoldFastISelLoad(cast<LoadInst>(BeforeInst), Inst, FastIS))
+ // If we succeeded, don't re-select the load.
+ BI = llvm::next(BasicBlock::const_iterator(BeforeInst));
continue;
}
continue;
}
- // Otherwise, give up on FastISel for the rest of the block.
- // For now, be a little lenient about non-branch terminators.
- if (!isa<TerminatorInst>(Inst) || isa<BranchInst>(Inst)) {
+ if (isa<TerminatorInst>(Inst) && !isa<BranchInst>(Inst)) {
+ // Don't abort, and use a different message for terminator misses.
+ ++NumFastIselFailures;
+ if (EnableFastISelVerbose || EnableFastISelAbort) {
+ dbgs() << "FastISel missed terminator: ";
+ Inst->dump();
+ }
+ } else {
++NumFastIselFailures;
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel miss: ";
else
++NumFastIselBlocks;
- // Run SelectionDAG instruction selection on the remainder of the block
- // not handled by FastISel. If FastISel is not run, this is the entire
- // block.
- bool HadTailCall;
- SelectBasicBlock(Begin, BI, HadTailCall);
+ if (Begin != BI) {
+ // Run SelectionDAG instruction selection on the remainder of the block
+ // not handled by FastISel. If FastISel is not run, this is the entire
+ // block.
+ bool HadTailCall;
+ SelectBasicBlock(Begin, BI, HadTailCall);
+ }
FinishBasicBlock();
FuncInfo->PHINodesToUpdate.clear();
}
delete FastIS;
-#ifndef NDEBUG
- for (MachineFunction::const_iterator MBI = MF->begin(), MBE = MF->end();
- MBI != MBE; ++MBI)
- CheckLineNumbers(MBI);
-#endif
+ SDB->clearDanglingDebugInfo();
}
void
// instructions that access memory and for ComplexPatterns that match
// loads.
if (EmitNodeInfo & OPFL_MemRefs) {
+ // Only attach load or store memory operands if the generated
+ // instruction may load or store.
+ const TargetInstrDesc &TID = TM.getInstrInfo()->get(TargetOpc);
+ bool mayLoad = TID.mayLoad();
+ bool mayStore = TID.mayStore();
+
+ unsigned NumMemRefs = 0;
+ for (SmallVector<MachineMemOperand*, 2>::const_iterator I =
+ MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
+ if ((*I)->isLoad()) {
+ if (mayLoad)
+ ++NumMemRefs;
+ } else if ((*I)->isStore()) {
+ if (mayStore)
+ ++NumMemRefs;
+ } else {
+ ++NumMemRefs;
+ }
+ }
+
MachineSDNode::mmo_iterator MemRefs =
- MF->allocateMemRefsArray(MatchedMemRefs.size());
- std::copy(MatchedMemRefs.begin(), MatchedMemRefs.end(), MemRefs);
+ MF->allocateMemRefsArray(NumMemRefs);
+
+ MachineSDNode::mmo_iterator MemRefsPos = MemRefs;
+ for (SmallVector<MachineMemOperand*, 2>::const_iterator I =
+ MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
+ if ((*I)->isLoad()) {
+ if (mayLoad)
+ *MemRefsPos++ = *I;
+ } else if ((*I)->isStore()) {
+ if (mayStore)
+ *MemRefsPos++ = *I;
+ } else {
+ *MemRefsPos++ = *I;
+ }
+ }
+
cast<MachineSDNode>(Res)
- ->setMemRefs(MemRefs, MemRefs + MatchedMemRefs.size());
+ ->setMemRefs(MemRefs, MemRefs + NumMemRefs);
}
DEBUG(errs() << " "
projects / oota-llvm.git / blobdiff