Implement bottom-up fast-isel. This has the advantage of not requiring
a separate DCE pass over MachineInstrs.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107804 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp
index d437370..bf3137e 100644
--- a/lib/CodeGen/LLVMTargetMachine.cpp
+++ b/lib/CodeGen/LLVMTargetMachine.cpp
@@ -329,19 +329,15 @@
if (OptLevel != CodeGenOpt::None)
PM.add(createOptimizePHIsPass());
- // Delete dead machine instructions regardless of optimization level.
- //
- // At -O0, fast-isel frequently creates dead instructions.
- //
- // With optimization, dead code should already be eliminated. However
- // there is one known exception: lowered code for arguments that are only
- // used by tail calls, where the tail calls reuse the incoming stack
- // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll).
- PM.add(createDeadMachineInstructionElimPass());
- printAndVerify(PM, "After codegen DCE pass",
- /* allowDoubleDefs= */ true);
-
if (OptLevel != CodeGenOpt::None) {
+ // With optimization, dead code should already be eliminated. However
+ // there is one known exception: lowered code for arguments that are only
+ // used by tail calls, where the tail calls reuse the incoming stack
+ // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll).
+ PM.add(createDeadMachineInstructionElimPass());
+ printAndVerify(PM, "After codegen DCE pass",
+ /* allowDoubleDefs= */ true);
+
PM.add(createOptimizeExtsPass());
if (!DisableMachineLICM)
PM.add(createMachineLICMPass());
diff --git a/lib/CodeGen/SelectionDAG/FastISel.cpp b/lib/CodeGen/SelectionDAG/FastISel.cpp
index 2ba8315..5a24512 100644
--- a/lib/CodeGen/SelectionDAG/FastISel.cpp
+++ b/lib/CodeGen/SelectionDAG/FastISel.cpp
@@ -57,6 +57,17 @@
#include "llvm/Support/ErrorHandling.h"
using namespace llvm;
+/// startNewBlock - Set the current block to which generated machine
+/// instructions will be appended, and clear the local CSE map.
+///
+void FastISel::startNewBlock() {
+ LocalValueMap.clear();
+
+ // Start out as end(), meaining no local-value instructions have
+ // been emitted.
+ LastLocalValue = FuncInfo.MBB->end();
+}
+
bool FastISel::hasTrivialKill(const Value *V) const {
// Don't consider constants or arguments to have trivial kills.
const Instruction *I = dyn_cast<Instruction>(V);
@@ -109,12 +120,9 @@
// In bottom-up mode, just create the virtual register which will be used
// to hold the value. It will be materialized later.
- if (IsBottomUp) {
+ if (isa<Instruction>(V)) {
Reg = createResultReg(TLI.getRegClassFor(VT));
- if (isa<Instruction>(V))
- FuncInfo.ValueMap[V] = Reg;
- else
- LocalValueMap[V] = Reg;
+ FuncInfo.ValueMap[V] = Reg;
return Reg;
}
@@ -180,8 +188,10 @@
// Don't cache constant materializations in the general ValueMap.
// To do so would require tracking what uses they dominate.
- if (Reg != 0)
+ if (Reg != 0) {
LocalValueMap[V] = Reg;
+ LastLocalValue = MRI.getVRegDef(Reg);
+ }
return Reg;
}
@@ -210,12 +220,20 @@
unsigned &AssignedReg = FuncInfo.ValueMap[I];
if (AssignedReg == 0)
+ // Use the new register.
AssignedReg = Reg;
else if (Reg != AssignedReg) {
- const TargetRegisterClass *RegClass = MRI.getRegClass(Reg);
- TII.copyRegToReg(*FuncInfo.MBB, FuncInfo.InsertPt, AssignedReg,
- Reg, RegClass, RegClass, DL);
+ // We already have a register for this value. Replace uses of
+ // the existing register with uses of the new one.
+ MRI.replaceRegWith(AssignedReg, Reg);
+ // Replace uses of the existing register in PHINodesToUpdate too.
+ for (unsigned i = 0, e = FuncInfo.PHINodesToUpdate.size(); i != e; ++i)
+ if (FuncInfo.PHINodesToUpdate[i].second == AssignedReg)
+ FuncInfo.PHINodesToUpdate[i].second = Reg;
+ // And update the ValueMap.
+ AssignedReg = Reg;
}
+
return AssignedReg;
}
@@ -736,11 +754,15 @@
BasicBlock::iterator ScanFrom = LI;
if (const Value *V = FindAvailableLoadedValue(LI->getPointerOperand(),
LI->getParent(), ScanFrom)) {
+ if (!isa<Instruction>(V) ||
+ cast<Instruction>(V)->getParent() == LI->getParent() ||
+ (isa<AllocaInst>(V) && FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V)))) {
unsigned ResultReg = getRegForValue(V);
if (ResultReg != 0) {
UpdateValueMap(I, ResultReg);
return true;
}
+ }
}
}
@@ -871,8 +893,7 @@
TD(*TM.getTargetData()),
TII(*TM.getInstrInfo()),
TLI(*TM.getTargetLowering()),
- TRI(*TM.getRegisterInfo()),
- IsBottomUp(false) {
+ TRI(*TM.getRegisterInfo()) {
}
FastISel::~FastISel() {}
diff --git a/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp b/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
index 8c4211a..55171fc 100644
--- a/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
+++ b/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
@@ -78,6 +78,13 @@
MF = &mf;
RegInfo = &MF->getRegInfo();
+ // Check whether the function can return without sret-demotion.
+ SmallVector<ISD::OutputArg, 4> Outs;
+ GetReturnInfo(Fn->getReturnType(),
+ Fn->getAttributes().getRetAttributes(), Outs, TLI);
+ CanLowerReturn = TLI.CanLowerReturn(Fn->getCallingConv(), Fn->isVarArg(),
+ Outs, Fn->getContext());
+
// Create a vreg for each argument register that is not dead and is used
// outside of the entry block for the function.
for (Function::const_arg_iterator AI = Fn->arg_begin(), E = Fn->arg_end();
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index f855f3a..3b3ee3e 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -951,12 +951,10 @@
// If this is an instruction which fast-isel has deferred, select it now.
if (const Instruction *Inst = dyn_cast<Instruction>(V)) {
- assert(Inst->isSafeToSpeculativelyExecute() &&
- "Instruction with side effects deferred!");
- visit(*Inst);
- DenseMap<const Value *, SDValue>::iterator NIt = NodeMap.find(Inst);
- if (NIt != NodeMap.end() && NIt->second.getNode())
- return NIt->second;
+ unsigned InReg = FuncInfo.InitializeRegForValue(Inst);
+ RegsForValue RFV(*DAG.getContext(), TLI, InReg, Inst->getType());
+ SDValue Chain = DAG.getEntryNode();
+ return RFV.getCopyFromRegs(DAG, FuncInfo, getCurDebugLoc(), Chain, NULL);
}
llvm_unreachable("Can't get register for value!");
@@ -1259,7 +1257,7 @@
}
void SelectionDAGBuilder::visitBr(const BranchInst &I) {
- MachineBasicBlock *BrMBB = FuncInfo.MBBMap[I.getParent()];
+ MachineBasicBlock *BrMBB = FuncInfo.MBB;
// Update machine-CFG edges.
MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
@@ -1585,7 +1583,7 @@
}
void SelectionDAGBuilder::visitInvoke(const InvokeInst &I) {
- MachineBasicBlock *InvokeMBB = FuncInfo.MBBMap[I.getParent()];
+ MachineBasicBlock *InvokeMBB = FuncInfo.MBB;
// Retrieve successors.
MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
@@ -2113,7 +2111,7 @@
}
void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) {
- MachineBasicBlock *SwitchMBB = FuncInfo.MBBMap[SI.getParent()];
+ MachineBasicBlock *SwitchMBB = FuncInfo.MBB;
// Figure out which block is immediately after the current one.
MachineBasicBlock *NextBlock = 0;
@@ -2179,7 +2177,7 @@
}
void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) {
- MachineBasicBlock *IndirectBrMBB = FuncInfo.MBBMap[I.getParent()];
+ MachineBasicBlock *IndirectBrMBB = FuncInfo.MBB;
// Update machine-CFG edges with unique successors.
SmallVector<BasicBlock*, 32> succs;
@@ -3839,7 +3837,7 @@
if (DV.isInlinedFnArgument(MF.getFunction()))
return false;
- MachineBasicBlock *MBB = FuncInfo.MBBMap[DI.getParent()];
+ MachineBasicBlock *MBB = FuncInfo.MBB;
if (MBB != &MF.front())
return false;
@@ -4102,7 +4100,7 @@
}
case Intrinsic::eh_exception: {
// Insert the EXCEPTIONADDR instruction.
- assert(FuncInfo.MBBMap[I.getParent()]->isLandingPad() &&
+ assert(FuncInfo.MBB->isLandingPad() &&
"Call to eh.exception not in landing pad!");
SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
SDValue Ops[1];
@@ -4114,7 +4112,7 @@
}
case Intrinsic::eh_selector: {
- MachineBasicBlock *CallMBB = FuncInfo.MBBMap[I.getParent()];
+ MachineBasicBlock *CallMBB = FuncInfo.MBB;
MachineModuleInfo &MMI = DAG.getMachineFunction().getMMI();
if (CallMBB->isLandingPad())
AddCatchInfo(I, &MMI, CallMBB);
@@ -4124,7 +4122,7 @@
#endif
// FIXME: Mark exception selector register as live in. Hack for PR1508.
unsigned Reg = TLI.getExceptionSelectorRegister();
- if (Reg) FuncInfo.MBBMap[I.getParent()]->addLiveIn(Reg);
+ if (Reg) FuncInfo.MBB->addLiveIn(Reg);
}
// Insert the EHSELECTION instruction.
@@ -5901,9 +5899,6 @@
GetReturnInfo(F.getReturnType(), F.getAttributes().getRetAttributes(),
Outs, TLI);
- FuncInfo->CanLowerReturn = TLI.CanLowerReturn(F.getCallingConv(),
- F.isVarArg(),
- Outs, F.getContext());
if (!FuncInfo->CanLowerReturn) {
// Put in an sret pointer parameter before all the other parameters.
SmallVector<EVT, 1> ValueVTs;
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index bea65b2..8918516 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -680,60 +680,55 @@
BasicBlock::const_iterator const Begin = LLVMBB->getFirstNonPHI();
BasicBlock::const_iterator const End = LLVMBB->end();
- BasicBlock::const_iterator BI = Begin;
+ BasicBlock::const_iterator BI = End;
- // 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 (FuncInfo->MBB->isLandingPad())
- PrepareEHLandingPad();
-
// Before doing SelectionDAG ISel, see if FastISel has been requested.
if (FastIS) {
- // 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();
- CodeGenAndEmitDAG();
- }
FastIS->startNewBlock();
+
// 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.
+ MachineBasicBlock::iterator LVIP = FastIS->getLastLocalValue();
+ if (LVIP != FuncInfo->MBB->end())
+ FuncInfo->InsertPt = next(LVIP);
+ else
+ FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI();
// 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;
- SelectBasicBlock(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;
}
@@ -746,7 +741,7 @@
++NumFastIselFailures;
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel miss: ";
- BI->dump();
+ Inst->dump();
}
if (EnableFastISelAbort)
// The "fast" selector couldn't handle something and bailed.
@@ -757,13 +752,21 @@
}
}
+ 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);
+
// 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;
- SelectBasicBlock(BI, End, HadTailCall);
- }
+ bool HadTailCall;
+ SelectBasicBlock(Begin, BI, HadTailCall);
FinishBasicBlock();
FuncInfo->PHINodesToUpdate.clear();
@@ -963,7 +966,8 @@
for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
FuncInfo->MBB = Succs[i];
FuncInfo->InsertPt = FuncInfo->MBB->end();
- // BB may have been removed from the CFG if a branch was constant folded.
+ // 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();