#define DEBUG_TYPE "isel"
#include "ScheduleDAGSDNodes.h"
#include "SelectionDAGBuilder.h"
-#include "FunctionLoweringInfo.h"
+#include "llvm/CodeGen/FunctionLoweringInfo.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/DebugInfo.h"
const TargetLowering &TLI = IS->getTargetLowering();
if (OptLevel == CodeGenOpt::None)
- return createFastDAGScheduler(IS, OptLevel);
+ return createSourceListDAGScheduler(IS, OptLevel);
if (TLI.getSchedulingPreference() == Sched::Latency)
return createTDListDAGScheduler(IS, OptLevel);
if (TLI.getSchedulingPreference() == Sched::RegPressure)
return createBURRListDAGScheduler(IS, OptLevel);
- assert(TLI.getSchedulingPreference() == Sched::Hybrid &&
+ if (TLI.getSchedulingPreference() == Sched::Hybrid)
+ return createHybridListDAGScheduler(IS, OptLevel);
+ assert(TLI.getSchedulingPreference() == Sched::ILP &&
"Unknown sched type!");
- return createHybridListDAGScheduler(IS, OptLevel);
+ return createILPListDAGScheduler(IS, OptLevel);
}
}
//===----------------------------------------------------------------------===//
SelectionDAGISel::SelectionDAGISel(const TargetMachine &tm, CodeGenOpt::Level OL) :
- MachineFunctionPass(&ID), TM(tm), TLI(*tm.getTargetLowering()),
+ MachineFunctionPass(ID), TM(tm), TLI(*tm.getTargetLowering()),
FuncInfo(new FunctionLoweringInfo(TLI)),
CurDAG(new SelectionDAG(tm)),
SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)),
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 (const CallInst *CI = dyn_cast<CallInst>(*I))
if (CI->getParent()->getParent() == F)
return true;
}
for (MachineBasicBlock::const_iterator
II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
const TargetInstrDesc &TID = TM.getInstrInfo()->get(II->getOpcode());
- if (II->isInlineAsm() || (TID.isCall() && !TID.isReturn())) {
+
+ // Operand 1 of an inline asm instruction indicates whether the asm
+ // needs stack or not.
+ if ((II->isInlineAsm() && II->getOperand(1).getImm()) ||
+ (TID.isCall() && !TID.isReturn())) {
MFI->setHasCalls(true);
goto done;
}
// Determine if there is a call to setjmp in the machine function.
MF->setCallsSetJmp(FunctionCallsSetJmp(&Fn));
+ // Replace forward-declared registers with the registers containing
+ // the desired value.
+ MachineRegisterInfo &MRI = MF->getRegInfo();
+ for (DenseMap<unsigned, unsigned>::iterator
+ I = FuncInfo->RegFixups.begin(), E = FuncInfo->RegFixups.end();
+ I != E; ++I) {
+ unsigned From = I->first;
+ unsigned To = I->second;
+ // If To is also scheduled to be replaced, find what its ultimate
+ // replacement is.
+ for (;;) {
+ DenseMap<unsigned, unsigned>::iterator J =
+ FuncInfo->RegFixups.find(To);
+ if (J == E) break;
+ To = J->second;
+ }
+ // Replace it.
+ MRI.replaceRegWith(From, To);
+ }
+
// Release function-specific state. SDB and CurDAG are already cleared
// at this point.
FuncInfo->clear();
return true;
}
-MachineBasicBlock *
-SelectionDAGISel::SelectBasicBlock(MachineBasicBlock *BB,
- BasicBlock::const_iterator Begin,
+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
SDB->clear();
// Final step, emit the lowered DAG as machine code.
- return CodeGenAndEmitDAG(BB);
+ CodeGenAndEmitDAG();
}
namespace {
} while (!Worklist.empty());
}
-MachineBasicBlock *SelectionDAGISel::CodeGenAndEmitDAG(MachineBasicBlock *BB) {
+void SelectionDAGISel::CodeGenAndEmitDAG() {
std::string GroupName;
if (TimePassesIsEnabled)
GroupName = "Instruction Selection and Scheduling";
ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
ViewSUnitDAGs)
BlockName = MF->getFunction()->getNameStr() + ":" +
- BB->getBasicBlock()->getNameStr();
+ FuncInfo->MBB->getBasicBlock()->getNameStr();
DEBUG(dbgs() << "Initial selection DAG:\n"; CurDAG->dump());
{
NamedRegionTimer T("Instruction Scheduling", GroupName,
TimePassesIsEnabled);
- Scheduler->Run(CurDAG, BB, BB->end());
+ Scheduler->Run(CurDAG, FuncInfo->MBB, FuncInfo->InsertPt);
}
if (ViewSUnitDAGs) Scheduler->viewGraph();
// inserted into.
{
NamedRegionTimer T("Instruction Creation", GroupName, TimePassesIsEnabled);
- BB = Scheduler->EmitSchedule();
+
+ FuncInfo->MBB = Scheduler->EmitSchedule();
+ FuncInfo->InsertPt = Scheduler->InsertPos;
}
// Free the scheduler state.
// Free the SelectionDAG state, now that we're finished with it.
CurDAG->clear();
-
- return BB;
}
void SelectionDAGISel::DoInstructionSelection() {
/// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
/// do other setup for EH landing-pad blocks.
-void SelectionDAGISel::PrepareEHLandingPad(MachineBasicBlock *BB) {
+void SelectionDAGISel::PrepareEHLandingPad() {
// Add a label to mark the beginning of the landing pad. Deletion of the
// landing pad can thus be detected via the MachineModuleInfo.
- MCSymbol *Label = MF->getMMI().addLandingPad(BB);
+ MCSymbol *Label = MF->getMMI().addLandingPad(FuncInfo->MBB);
const TargetInstrDesc &II = TM.getInstrInfo()->get(TargetOpcode::EH_LABEL);
- BuildMI(BB, SDB->getCurDebugLoc(), II).addSym(Label);
+ BuildMI(*FuncInfo->MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
+ .addSym(Label);
// Mark exception register as live in.
unsigned Reg = TLI.getExceptionAddressRegister();
- if (Reg) BB->addLiveIn(Reg);
+ if (Reg) FuncInfo->MBB->addLiveIn(Reg);
// Mark exception selector register as live in.
Reg = TLI.getExceptionSelectorRegister();
- if (Reg) BB->addLiveIn(Reg);
+ if (Reg) FuncInfo->MBB->addLiveIn(Reg);
// FIXME: Hack around an exception handling flaw (PR1508): the personality
// function and list of typeids logically belong to the invoke (or, if you
// in exceptions not being caught because no typeids are associated with
// the invoke. This may not be the only way things can go wrong, but it
// is the only way we try to work around for the moment.
- const BasicBlock *LLVMBB = BB->getBasicBlock();
+ const BasicBlock *LLVMBB = FuncInfo->MBB->getBasicBlock();
const BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
if (Br && Br->isUnconditional()) { // Critical edge?
// Initialize the Fast-ISel state, if needed.
FastISel *FastIS = 0;
if (EnableFastISel)
- FastIS = TLI.createFastISel(*MF, FuncInfo->ValueMap, FuncInfo->MBBMap,
- FuncInfo->StaticAllocaMap,
- FuncInfo->PHINodesToUpdate
-#ifndef NDEBUG
- , FuncInfo->CatchInfoLost
-#endif
- );
+ FastIS = TLI.createFastISel(*FuncInfo);
// Iterate over all basic blocks in the function.
for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
const BasicBlock *LLVMBB = &*I;
- MachineBasicBlock *BB = FuncInfo->MBBMap[LLVMBB];
+ FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
+ FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI();
BasicBlock::const_iterator const Begin = LLVMBB->getFirstNonPHI();
BasicBlock::const_iterator const End = LLVMBB->end();
- BasicBlock::const_iterator BI = Begin;
+ BasicBlock::const_iterator BI = End;
+
+ FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI();
+ // Setup an EH landing-pad block.
+ if (FuncInfo->MBB->isLandingPad())
+ PrepareEHLandingPad();
+
// Lower any arguments needed in this block if this is the entry block.
if (LLVMBB == &Fn.getEntryBlock())
LowerArguments(LLVMBB);
- // Setup an EH landing-pad block.
- if (BB->isLandingPad())
- PrepareEHLandingPad(BB);
-
// Before doing SelectionDAG ISel, see if FastISel has been requested.
if (FastIS) {
+ FastIS->startNewBlock();
+
// Emit code for any incoming arguments. This must happen before
// beginning FastISel on the entry block.
if (LLVMBB == &Fn.getEntryBlock()) {
CurDAG->setRoot(SDB->getControlRoot());
SDB->clear();
- BB = CodeGenAndEmitDAG(BB);
+ CodeGenAndEmitDAG();
+
+ // If we inserted any instructions at the beginning, make a note of
+ // where they are, so we can be sure to emit subsequent instructions
+ // after them.
+ if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
+ FastIS->setLastLocalValue(llvm::prior(FuncInfo->InsertPt));
+ else
+ FastIS->setLastLocalValue(0);
}
- FastIS->startNewBlock(BB);
+
// Do FastISel on as many instructions as possible.
- for (; BI != End; ++BI) {
-#if 0
- // Defer instructions with no side effects; they'll be emitted
- // on-demand later.
- if (BI->isSafeToSpeculativelyExecute() &&
- !FuncInfo->isExportedInst(BI))
+ for (; BI != Begin; --BI) {
+ 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))
continue;
-#endif
+
+ // Bottom-up: reset the insert pos at the top, after any local-value
+ // instructions.
+ FastIS->recomputeInsertPt();
// Try to select the instruction with FastISel.
- if (FastIS->SelectInstruction(BI))
+ if (FastIS->SelectInstruction(Inst))
continue;
// Then handle certain instructions as single-LLVM-Instruction blocks.
- if (isa<CallInst>(BI)) {
+ if (isa<CallInst>(Inst)) {
++NumFastIselFailures;
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel missed call: ";
- BI->dump();
+ Inst->dump();
}
- if (!BI->getType()->isVoidTy() && !BI->use_empty()) {
- unsigned &R = FuncInfo->ValueMap[BI];
+ if (!Inst->getType()->isVoidTy() && !Inst->use_empty()) {
+ unsigned &R = FuncInfo->ValueMap[Inst];
if (!R)
- R = FuncInfo->CreateRegs(BI->getType());
+ R = FuncInfo->CreateRegs(Inst->getType());
}
bool HadTailCall = false;
- BB = SelectBasicBlock(BB, BI, llvm::next(BI), HadTailCall);
+ SelectBasicBlock(Inst, BI, HadTailCall);
// If the call was emitted as a tail call, we're done with the block.
if (HadTailCall) {
- BI = End;
+ --BI;
break;
}
- // If the instruction was codegen'd with multiple blocks,
- // inform the FastISel object where to resume inserting.
- FastIS->setCurrentBlock(BB);
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>(BI) || isa<BranchInst>(BI)) {
+ if (!isa<TerminatorInst>(Inst) || isa<BranchInst>(Inst)) {
++NumFastIselFailures;
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel miss: ";
- BI->dump();
+ Inst->dump();
}
if (EnableFastISelAbort)
// The "fast" selector couldn't handle something and bailed.
}
break;
}
+
+ FastIS->recomputeInsertPt();
}
// Run SelectionDAG instruction selection on the remainder of the block
// not handled by FastISel. If FastISel is not run, this is the entire
// block.
- if (BI != End) {
- bool HadTailCall;
- BB = SelectBasicBlock(BB, BI, End, HadTailCall);
- }
+ bool HadTailCall;
+ SelectBasicBlock(Begin, BI, HadTailCall);
- FinishBasicBlock(BB);
+ FinishBasicBlock();
FuncInfo->PHINodesToUpdate.clear();
}
}
void
-SelectionDAGISel::FinishBasicBlock(MachineBasicBlock *BB) {
+SelectionDAGISel::FinishBasicBlock() {
DEBUG(dbgs() << "Total amount of phi nodes to update: "
<< FuncInfo->PHINodesToUpdate.size() << "\n";
MachineInstr *PHI = FuncInfo->PHINodesToUpdate[i].first;
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
- if (!BB->isSuccessor(PHI->getParent()))
+ if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
continue;
PHI->addOperand(
MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[i].second, false));
- PHI->addOperand(MachineOperand::CreateMBB(BB));
+ PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB));
}
return;
}
// Lower header first, if it wasn't already lowered
if (!SDB->BitTestCases[i].Emitted) {
// Set the current basic block to the mbb we wish to insert the code into
- BB = SDB->BitTestCases[i].Parent;
+ FuncInfo->MBB = SDB->BitTestCases[i].Parent;
+ FuncInfo->InsertPt = FuncInfo->MBB->end();
// Emit the code
- SDB->visitBitTestHeader(SDB->BitTestCases[i], BB);
+ SDB->visitBitTestHeader(SDB->BitTestCases[i], FuncInfo->MBB);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
- BB = CodeGenAndEmitDAG(BB);
+ CodeGenAndEmitDAG();
}
for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) {
// Set the current basic block to the mbb we wish to insert the code into
- BB = SDB->BitTestCases[i].Cases[j].ThisBB;
+ FuncInfo->MBB = SDB->BitTestCases[i].Cases[j].ThisBB;
+ FuncInfo->InsertPt = FuncInfo->MBB->end();
// Emit the code
if (j+1 != ej)
SDB->visitBitTestCase(SDB->BitTestCases[i].Cases[j+1].ThisBB,
SDB->BitTestCases[i].Reg,
SDB->BitTestCases[i].Cases[j],
- BB);
+ FuncInfo->MBB);
else
SDB->visitBitTestCase(SDB->BitTestCases[i].Default,
SDB->BitTestCases[i].Reg,
SDB->BitTestCases[i].Cases[j],
- BB);
+ FuncInfo->MBB);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
- BB = CodeGenAndEmitDAG(BB);
+ CodeGenAndEmitDAG();
}
// Update PHI Nodes
// Lower header first, if it wasn't already lowered
if (!SDB->JTCases[i].first.Emitted) {
// Set the current basic block to the mbb we wish to insert the code into
- BB = SDB->JTCases[i].first.HeaderBB;
+ FuncInfo->MBB = SDB->JTCases[i].first.HeaderBB;
+ FuncInfo->InsertPt = FuncInfo->MBB->end();
// Emit the code
SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first,
- BB);
+ FuncInfo->MBB);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
- BB = CodeGenAndEmitDAG(BB);
+ CodeGenAndEmitDAG();
}
// Set the current basic block to the mbb we wish to insert the code into
- BB = SDB->JTCases[i].second.MBB;
+ FuncInfo->MBB = SDB->JTCases[i].second.MBB;
+ FuncInfo->InsertPt = FuncInfo->MBB->end();
// Emit the code
SDB->visitJumpTable(SDB->JTCases[i].second);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
- BB = CodeGenAndEmitDAG(BB);
+ CodeGenAndEmitDAG();
// Update PHI Nodes
for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
(MachineOperand::CreateMBB(SDB->JTCases[i].first.HeaderBB));
}
// JT BB. Just iterate over successors here
- if (BB->isSuccessor(PHIBB)) {
+ if (FuncInfo->MBB->isSuccessor(PHIBB)) {
PHI->addOperand
(MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[pi].second,
false));
- PHI->addOperand(MachineOperand::CreateMBB(BB));
+ PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB));
}
}
}
MachineInstr *PHI = FuncInfo->PHINodesToUpdate[i].first;
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
- if (BB->isSuccessor(PHI->getParent())) {
+ if (FuncInfo->MBB->isSuccessor(PHI->getParent())) {
PHI->addOperand(
MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[i].second, false));
- PHI->addOperand(MachineOperand::CreateMBB(BB));
+ PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB));
}
}
// additional DAGs necessary.
for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
// Set the current basic block to the mbb we wish to insert the code into
- MachineBasicBlock *ThisBB = BB = SDB->SwitchCases[i].ThisBB;
+ MachineBasicBlock *ThisBB = FuncInfo->MBB = SDB->SwitchCases[i].ThisBB;
+ FuncInfo->InsertPt = FuncInfo->MBB->end();
// Determine the unique successors.
SmallVector<MachineBasicBlock *, 2> Succs;
// Emit the code. Note that this could result in ThisBB being split, so
// we need to check for updates.
- SDB->visitSwitchCase(SDB->SwitchCases[i], BB);
+ SDB->visitSwitchCase(SDB->SwitchCases[i], FuncInfo->MBB);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
- ThisBB = CodeGenAndEmitDAG(BB);
+ CodeGenAndEmitDAG();
+ ThisBB = FuncInfo->MBB;
// Handle any PHI nodes in successors of this chunk, as if we were coming
// from the original BB before switch expansion. Note that PHI nodes can
// occur multiple times in PHINodesToUpdate. We have to be very careful to
// handle them the right number of times.
for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
- BB = Succs[i];
- // BB may have been removed from the CFG if a branch was constant folded.
- if (ThisBB->isSuccessor(BB)) {
- for (MachineBasicBlock::iterator Phi = BB->begin();
- Phi != BB->end() && Phi->isPHI();
+ FuncInfo->MBB = Succs[i];
+ FuncInfo->InsertPt = FuncInfo->MBB->end();
+ // FuncInfo->MBB may have been removed from the CFG if a branch was
+ // constant folded.
+ if (ThisBB->isSuccessor(FuncInfo->MBB)) {
+ for (MachineBasicBlock::iterator Phi = FuncInfo->MBB->begin();
+ Phi != FuncInfo->MBB->end() && Phi->isPHI();
++Phi) {
// This value for this PHI node is recorded in PHINodesToUpdate.
for (unsigned pn = 0; ; ++pn) {
projects / oota-llvm.git / blobdiff