//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "isel"
-#include "llvm/CodeGen/SelectionDAGISel.h"
+#include "ScheduleDAGSDNodes.h"
#include "SelectionDAGBuild.h"
-#include "llvm/ADT/BitVector.h"
+#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Constants.h"
#include "llvm/CallingConv.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/IntrinsicInst.h"
-#include "llvm/ParameterAttributes.h"
#include "llvm/CodeGen/FastISel.h"
#include "llvm/CodeGen/GCStrategy.h"
#include "llvm/CodeGen/GCMetadata.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAG.h"
+#include "llvm/CodeGen/DwarfWriter.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetFrameInfo.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Timer.h"
#include <algorithm>
using namespace llvm;
static cl::opt<bool>
-EnableValueProp("enable-value-prop", cl::Hidden);
-static cl::opt<bool>
-EnableLegalizeTypes("enable-legalize-types", cl::Hidden);
+DisableLegalizeTypes("disable-legalize-types", cl::Hidden);
static cl::opt<bool>
-EnableFastISel("fast-isel", cl::Hidden,
- cl::desc("Enable the experimental \"fast\" instruction selector"));
+EnableFastISelVerbose("fast-isel-verbose", cl::Hidden,
+ cl::desc("Enable verbose messages in the \"fast\" "
+ "instruction selector"));
static cl::opt<bool>
-DisableFastISelAbort("fast-isel-no-abort", cl::Hidden,
- cl::desc("Use the SelectionDAGISel when \"fast\" instruction "
- "selection fails"));
+EnableFastISelAbort("fast-isel-abort", cl::Hidden,
+ cl::desc("Enable abort calls when \"fast\" instruction fails"));
static cl::opt<bool>
SchedLiveInCopies("schedule-livein-copies",
cl::desc("Schedule copies of livein registers"),
cl::desc("Pop up a window to show dags before the second "
"dag combine pass"));
static cl::opt<bool>
+ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
+ cl::desc("Pop up a window to show dags before the post legalize types"
+ " dag combine pass"));
+static cl::opt<bool>
ViewISelDAGs("view-isel-dags", cl::Hidden,
cl::desc("Pop up a window to show isel dags as they are selected"));
static cl::opt<bool>
static const bool ViewDAGCombine1 = false,
ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
ViewDAGCombine2 = false,
+ ViewDAGCombineLT = false,
ViewISelDAGs = false, ViewSchedDAGs = false,
ViewSUnitDAGs = false;
#endif
" allocation):"));
static RegisterScheduler
-defaultListDAGScheduler("default", " Best scheduler for the target",
+defaultListDAGScheduler("default", "Best scheduler for the target",
createDefaultScheduler);
namespace llvm {
//===--------------------------------------------------------------------===//
/// createDefaultScheduler - This creates an instruction scheduler appropriate
/// for the target.
- ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
- SelectionDAG *DAG,
- MachineBasicBlock *BB,
- bool Fast) {
- TargetLowering &TLI = IS->getTargetLowering();
-
- if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) {
- return createTDListDAGScheduler(IS, DAG, BB, Fast);
- } else {
- assert(TLI.getSchedulingPreference() ==
- TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
- return createBURRListDAGScheduler(IS, DAG, BB, Fast);
- }
+ ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
+ CodeGenOpt::Level OptLevel) {
+ const TargetLowering &TLI = IS->getTargetLowering();
+
+ if (OptLevel == CodeGenOpt::None)
+ return createFastDAGScheduler(IS, OptLevel);
+ if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency)
+ return createTDListDAGScheduler(IS, OptLevel);
+ assert(TLI.getSchedulingPreference() ==
+ TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
+ return createBURRListDAGScheduler(IS, OptLevel);
}
}
// insert. The specified MachineInstr is created but not inserted into any
// basic blocks, and the scheduler passes ownership of it to this method.
MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
- MachineBasicBlock *MBB) {
- cerr << "If a target marks an instruction with "
- << "'usesCustomDAGSchedInserter', it must implement "
- << "TargetLowering::EmitInstrWithCustomInserter!\n";
- abort();
+ MachineBasicBlock *MBB) const {
+ llvm_report_error("If a target marks an instruction with "
+ "'usesCustomDAGSchedInserter', it must implement "
+ "TargetLowering::EmitInstrWithCustomInserter!");
return 0;
}
// don't coalesce. Also, only coalesce away a virtual register to virtual
// register copy.
bool Coalesced = false;
- unsigned SrcReg, DstReg;
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
if (NumUses == 1 &&
- TII.isMoveInstr(*UseMI, SrcReg, DstReg) &&
+ TII.isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
TargetRegisterInfo::isVirtualRegister(DstReg)) {
VirtReg = DstReg;
Coalesced = true;
--Pos;
}
- TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC);
- CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg));
+ bool Emitted = TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC);
+ assert(Emitted && "Unable to issue a live-in copy instruction!\n");
+ (void) Emitted;
+
+CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg));
if (Coalesced) {
if (&*InsertPos == UseMI) ++InsertPos;
MBB->erase(UseMI);
E = MRI.livein_end(); LI != E; ++LI)
if (LI->second) {
const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
- TII.copyRegToReg(*EntryMBB, EntryMBB->begin(),
- LI->second, LI->first, RC, RC);
+ bool Emitted = TII.copyRegToReg(*EntryMBB, EntryMBB->begin(),
+ LI->second, LI->first, RC, RC);
+ assert(Emitted && "Unable to issue a live-in copy instruction!\n");
+ (void) Emitted;
}
}
}
// SelectionDAGISel code
//===----------------------------------------------------------------------===//
-SelectionDAGISel::SelectionDAGISel(TargetLowering &tli, bool fast) :
- FunctionPass(&ID), TLI(tli),
+SelectionDAGISel::SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL) :
+ FunctionPass(&ID), TM(tm), TLI(*tm.getTargetLowering()),
FuncInfo(new FunctionLoweringInfo(TLI)),
CurDAG(new SelectionDAG(TLI, *FuncInfo)),
- SDL(new SelectionDAGLowering(*CurDAG, TLI, *FuncInfo)),
+ SDL(new SelectionDAGLowering(*CurDAG, TLI, *FuncInfo, OL)),
GFI(),
- Fast(fast),
+ OptLevel(OL),
DAGSize(0)
{}
void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<AliasAnalysis>();
AU.addRequired<GCModuleInfo>();
+ AU.addRequired<DwarfWriter>();
AU.setPreservesAll();
}
bool SelectionDAGISel::runOnFunction(Function &Fn) {
+ // Do some sanity-checking on the command-line options.
+ assert((!EnableFastISelVerbose || EnableFastISel) &&
+ "-fast-isel-verbose requires -fast-isel");
+ assert((!EnableFastISelAbort || EnableFastISel) &&
+ "-fast-isel-abort requires -fast-isel");
+
+ // Do not codegen any 'available_externally' functions at all, they have
+ // definitions outside the translation unit.
+ if (Fn.hasAvailableExternallyLinkage())
+ return false;
+
+
// Get alias analysis for load/store combining.
AA = &getAnalysis<AliasAnalysis>();
TargetMachine &TM = TLI.getTargetMachine();
- MachineFunction &MF = MachineFunction::construct(&Fn, TM);
- const MachineRegisterInfo &MRI = MF.getRegInfo();
+ MF = &MachineFunction::construct(&Fn, TM);
const TargetInstrInfo &TII = *TM.getInstrInfo();
const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
- if (MF.getFunction()->hasGC())
- GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction());
+ if (MF->getFunction()->hasGC())
+ GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF->getFunction());
else
GFI = 0;
- RegInfo = &MF.getRegInfo();
+ RegInfo = &MF->getRegInfo();
DOUT << "\n\n\n=== " << Fn.getName() << "\n";
- FuncInfo->set(Fn, MF, EnableFastISel);
- CurDAG->init(MF, getAnalysisToUpdate<MachineModuleInfo>());
+ MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>();
+ DwarfWriter *DW = getAnalysisIfAvailable<DwarfWriter>();
+ CurDAG->init(*MF, MMI, DW);
+ FuncInfo->set(Fn, *MF, *CurDAG, EnableFastISel);
SDL->init(GFI, *AA);
for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
// Mark landing pad.
FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
- SelectAllBasicBlocks(Fn, MF);
+ SelectAllBasicBlocks(Fn, *MF, MMI, DW, TII);
// If the first basic block in the function has live ins that need to be
// copied into vregs, emit the copies into the top of the block before
// emitting the code for the block.
- EmitLiveInCopies(MF.begin(), MRI, TRI, TII);
+ EmitLiveInCopies(MF->begin(), *RegInfo, TRI, TII);
// Add function live-ins to entry block live-in set.
for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(),
E = RegInfo->livein_end(); I != E; ++I)
- MF.begin()->addLiveIn(I->first);
+ MF->begin()->addLiveIn(I->first);
#ifndef NDEBUG
assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() &&
/// IsFixedFrameObjectWithPosOffset - Check if object is a fixed frame object and
/// whether object offset >= 0.
static bool
-IsFixedFrameObjectWithPosOffset(MachineFrameInfo * MFI, SDValue Op) {
+IsFixedFrameObjectWithPosOffset(MachineFrameInfo *MFI, SDValue Op) {
if (!isa<FrameIndexSDNode>(Op)) return false;
FrameIndexSDNode * FrameIdxNode = dyn_cast<FrameIndexSDNode>(Op);
/// assumes all arguments sourcing from FORMAL_ARGUMENTS or a CopyFromReg with
/// virtual registers would be overwritten by direct lowering.
static bool IsPossiblyOverwrittenArgumentOfTailCall(SDValue Op,
- MachineFrameInfo * MFI) {
+ MachineFrameInfo *MFI) {
RegisterSDNode * OpReg = NULL;
if (Op.getOpcode() == ISD::FORMAL_ARGUMENTS ||
(Op.getOpcode()== ISD::CopyFromReg &&
/// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the
/// DAG and fixes their tailcall attribute operand.
static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG,
- TargetLowering& TLI) {
+ const TargetLowering& TLI) {
SDNode * Ret = NULL;
SDValue Terminator = DAG.getRoot();
for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(),
BI = DAG.allnodes_end(); BI != BE; ) {
--BI;
- if (BI->getOpcode() == ISD::CALL) {
+ if (CallSDNode *TheCall = dyn_cast<CallSDNode>(BI)) {
SDValue OpRet(Ret, 0);
SDValue OpCall(BI, 0);
- bool isMarkedTailCall =
- cast<ConstantSDNode>(OpCall.getOperand(3))->getValue() != 0;
+ bool isMarkedTailCall = TheCall->isTailCall();
// If CALL node has tail call attribute set to true and the call is not
// eligible (no RET or the target rejects) the attribute is fixed to
// false. The TargetLowering::IsEligibleForTailCallOptimization function
// must correctly identify tail call optimizable calls.
if (!isMarkedTailCall) continue;
if (Ret==NULL ||
- !TLI.IsEligibleForTailCallOptimization(OpCall, OpRet, DAG)) {
- // Not eligible. Mark CALL node as non tail call.
- SmallVector<SDValue, 32> Ops;
- unsigned idx=0;
- for(SDNode::op_iterator I =OpCall.getNode()->op_begin(),
- E = OpCall.getNode()->op_end(); I != E; I++, idx++) {
- if (idx!=3)
- Ops.push_back(*I);
- else
- Ops.push_back(DAG.getConstant(false, TLI.getPointerTy()));
- }
- DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size());
+ !TLI.IsEligibleForTailCallOptimization(TheCall, OpRet, DAG)) {
+ // Not eligible. Mark CALL node as non tail call. Note that we
+ // can modify the call node in place since calls are not CSE'd.
+ TheCall->setNotTailCall();
} else {
// Look for tail call clobbered arguments. Emit a series of
// copyto/copyfrom virtual register nodes to protect them.
SmallVector<SDValue, 32> Ops;
- SDValue Chain = OpCall.getOperand(0), InFlag;
- unsigned idx=0;
- for(SDNode::op_iterator I = OpCall.getNode()->op_begin(),
- E = OpCall.getNode()->op_end(); I != E; I++, idx++) {
- SDValue Arg = *I;
- if (idx > 4 && (idx % 2)) {
- bool isByVal = cast<ARG_FLAGSSDNode>(OpCall.getOperand(idx+1))->
- getArgFlags().isByVal();
- MachineFunction &MF = DAG.getMachineFunction();
- MachineFrameInfo *MFI = MF.getFrameInfo();
- if (!isByVal &&
- IsPossiblyOverwrittenArgumentOfTailCall(Arg, MFI)) {
- MVT VT = Arg.getValueType();
- unsigned VReg = MF.getRegInfo().
- createVirtualRegister(TLI.getRegClassFor(VT));
- Chain = DAG.getCopyToReg(Chain, VReg, Arg, InFlag);
- InFlag = Chain.getValue(1);
- Arg = DAG.getCopyFromReg(Chain, VReg, VT, InFlag);
- Chain = Arg.getValue(1);
- InFlag = Arg.getValue(2);
- }
+ SDValue Chain = TheCall->getChain(), InFlag;
+ Ops.push_back(Chain);
+ Ops.push_back(TheCall->getCallee());
+ for (unsigned i = 0, e = TheCall->getNumArgs(); i != e; ++i) {
+ SDValue Arg = TheCall->getArg(i);
+ bool isByVal = TheCall->getArgFlags(i).isByVal();
+ MachineFunction &MF = DAG.getMachineFunction();
+ MachineFrameInfo *MFI = MF.getFrameInfo();
+ if (!isByVal &&
+ IsPossiblyOverwrittenArgumentOfTailCall(Arg, MFI)) {
+ MVT VT = Arg.getValueType();
+ unsigned VReg = MF.getRegInfo().
+ createVirtualRegister(TLI.getRegClassFor(VT));
+ Chain = DAG.getCopyToReg(Chain, Arg.getDebugLoc(),
+ VReg, Arg, InFlag);
+ InFlag = Chain.getValue(1);
+ Arg = DAG.getCopyFromReg(Chain, Arg.getDebugLoc(),
+ VReg, VT, InFlag);
+ Chain = Arg.getValue(1);
+ InFlag = Arg.getValue(2);
}
Ops.push_back(Arg);
+ Ops.push_back(TheCall->getArgFlagsVal(i));
}
// Link in chain of CopyTo/CopyFromReg.
Ops[0] = Chain;
BasicBlock::iterator End) {
SDL->setCurrentBasicBlock(BB);
- MachineModuleInfo *MMI = CurDAG->getMachineModuleInfo();
-
- if (MMI && BB->isLandingPad()) {
- // Add a label to mark the beginning of the landing pad. Deletion of the
- // landing pad can thus be detected via the MachineModuleInfo.
- unsigned LabelID = MMI->addLandingPad(BB);
- CurDAG->setRoot(CurDAG->getLabel(ISD::EH_LABEL,
- CurDAG->getEntryNode(), LabelID));
-
- // Mark exception register as live in.
- unsigned Reg = TLI.getExceptionAddressRegister();
- if (Reg) BB->addLiveIn(Reg);
-
- // Mark exception selector register as live in.
- Reg = TLI.getExceptionSelectorRegister();
- if (Reg) BB->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
- // like, the basic block containing the invoke), and need to be associated
- // with it in the dwarf exception handling tables. Currently however the
- // information is provided by an intrinsic (eh.selector) that can be moved
- // to unexpected places by the optimizers: if the unwind edge is critical,
- // then breaking it can result in the intrinsics being in the successor of
- // the landing pad, not the landing pad itself. This results 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.
- BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
-
- if (Br && Br->isUnconditional()) { // Critical edge?
- BasicBlock::iterator I, E;
- for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
- if (isa<EHSelectorInst>(I))
- break;
-
- if (I == E)
- // No catch info found - try to extract some from the successor.
- copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo);
- }
- }
-
// Lower all of the non-terminator instructions.
for (BasicBlock::iterator I = Begin; I != End; ++I)
if (!isa<TerminatorInst>(I))
// Ensure that all instructions which are used outside of their defining
// blocks are available as virtual registers. Invoke is handled elsewhere.
for (BasicBlock::iterator I = Begin; I != End; ++I)
- if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) {
- DenseMap<const Value*,unsigned>::iterator VMI =FuncInfo->ValueMap.find(I);
- if (VMI != FuncInfo->ValueMap.end())
- SDL->CopyValueToVirtualRegister(I, VMI->second);
- }
+ if (!isa<PHINode>(I) && !isa<InvokeInst>(I))
+ SDL->CopyToExportRegsIfNeeded(I);
// Handle PHI nodes in successor blocks.
if (End == LLVMBB->end()) {
// with correct tailcall attribute so that the target can rely on the tailcall
// attribute indicating whether the call is really eligible for tail call
// optimization.
- CheckDAGForTailCallsAndFixThem(*CurDAG, TLI);
+ if (PerformTailCallOpt)
+ CheckDAGForTailCallsAndFixThem(*CurDAG, TLI);
// Final step, emit the lowered DAG as machine code.
CodeGenAndEmitDAG();
FLI.LiveOutRegInfo.resize(DestReg+1);
FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[DestReg];
LOI.NumSignBits = NumSignBits;
- LOI.KnownOne = NumSignBits;
- LOI.KnownZero = NumSignBits;
+ LOI.KnownOne = KnownOne;
+ LOI.KnownZero = KnownZero;
}
}
}
GroupName = "Instruction Selection and Scheduling";
std::string BlockName;
if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
- ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs || ViewSUnitDAGs)
+ ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
+ ViewSUnitDAGs)
BlockName = CurDAG->getMachineFunction().getFunction()->getName() + ':' +
BB->getBasicBlock()->getName();
// Run the DAG combiner in pre-legalize mode.
if (TimePassesIsEnabled) {
NamedRegionTimer T("DAG Combining 1", GroupName);
- CurDAG->Combine(false, *AA, Fast);
+ CurDAG->Combine(Unrestricted, *AA, OptLevel);
} else {
- CurDAG->Combine(false, *AA, Fast);
+ CurDAG->Combine(Unrestricted, *AA, OptLevel);
}
DOUT << "Optimized lowered selection DAG:\n";
// Second step, hack on the DAG until it only uses operations and types that
// the target supports.
- if (EnableLegalizeTypes) {// Enable this some day.
+ if (!DisableLegalizeTypes) {
if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " +
BlockName);
+ bool Changed;
if (TimePassesIsEnabled) {
NamedRegionTimer T("Type Legalization", GroupName);
- CurDAG->LegalizeTypes();
+ Changed = CurDAG->LegalizeTypes();
} else {
- CurDAG->LegalizeTypes();
+ Changed = CurDAG->LegalizeTypes();
}
DOUT << "Type-legalized selection DAG:\n";
DEBUG(CurDAG->dump());
- // TODO: enable a dag combine pass here.
+ if (Changed) {
+ if (ViewDAGCombineLT)
+ CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
+
+ // Run the DAG combiner in post-type-legalize mode.
+ if (TimePassesIsEnabled) {
+ NamedRegionTimer T("DAG Combining after legalize types", GroupName);
+ CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
+ } else {
+ CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
+ }
+
+ DOUT << "Optimized type-legalized selection DAG:\n";
+ DEBUG(CurDAG->dump());
+ }
+
+ if (TimePassesIsEnabled) {
+ NamedRegionTimer T("Vector Legalization", GroupName);
+ Changed = CurDAG->LegalizeVectors();
+ } else {
+ Changed = CurDAG->LegalizeVectors();
+ }
+
+ if (Changed) {
+ if (TimePassesIsEnabled) {
+ NamedRegionTimer T("Type Legalization 2", GroupName);
+ Changed = CurDAG->LegalizeTypes();
+ } else {
+ Changed = CurDAG->LegalizeTypes();
+ }
+
+ if (ViewDAGCombineLT)
+ CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
+
+ // Run the DAG combiner in post-type-legalize mode.
+ if (TimePassesIsEnabled) {
+ NamedRegionTimer T("DAG Combining after legalize vectors", GroupName);
+ CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
+ } else {
+ CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
+ }
+
+ DOUT << "Optimized vector-legalized selection DAG:\n";
+ DEBUG(CurDAG->dump());
+ }
}
if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName);
if (TimePassesIsEnabled) {
NamedRegionTimer T("DAG Legalization", GroupName);
- CurDAG->Legalize();
+ CurDAG->Legalize(DisableLegalizeTypes, OptLevel);
} else {
- CurDAG->Legalize();
+ CurDAG->Legalize(DisableLegalizeTypes, OptLevel);
}
DOUT << "Legalized selection DAG:\n";
// Run the DAG combiner in post-legalize mode.
if (TimePassesIsEnabled) {
NamedRegionTimer T("DAG Combining 2", GroupName);
- CurDAG->Combine(true, *AA, Fast);
+ CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
} else {
- CurDAG->Combine(true, *AA, Fast);
+ CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
}
DOUT << "Optimized legalized selection DAG:\n";
if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName);
- if (!Fast && EnableValueProp)
+ if (OptLevel != CodeGenOpt::None)
ComputeLiveOutVRegInfo();
// Third, instruction select all of the operations to machine code, adding the
if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName);
// Schedule machine code.
- ScheduleDAG *Scheduler;
+ ScheduleDAGSDNodes *Scheduler = CreateScheduler();
if (TimePassesIsEnabled) {
NamedRegionTimer T("Instruction Scheduling", GroupName);
- Scheduler = Schedule();
+ Scheduler->Run(CurDAG, BB, BB->end());
} else {
- Scheduler = Schedule();
+ Scheduler->Run(CurDAG, BB, BB->end());
}
if (ViewSUnitDAGs) Scheduler->viewGraph();
DEBUG(BB->dump());
}
-void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF) {
+void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn,
+ MachineFunction &MF,
+ MachineModuleInfo *MMI,
+ DwarfWriter *DW,
+ const TargetInstrInfo &TII) {
+ // Initialize the Fast-ISel state, if needed.
+ FastISel *FastIS = 0;
+ if (EnableFastISel)
+ FastIS = TLI.createFastISel(MF, MMI, DW,
+ FuncInfo->ValueMap,
+ FuncInfo->MBBMap,
+ FuncInfo->StaticAllocaMap
+#ifndef NDEBUG
+ , FuncInfo->CatchInfoLost
+#endif
+ );
+
+ // Iterate over all basic blocks in the function.
for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
BasicBlock *LLVMBB = &*I;
BB = FuncInfo->MBBMap[LLVMBB];
BasicBlock::iterator const Begin = LLVMBB->begin();
BasicBlock::iterator const End = LLVMBB->end();
- BasicBlock::iterator I = Begin;
+ BasicBlock::iterator BI = Begin;
// Lower any arguments needed in this block if this is the entry block.
- if (LLVMBB == &Fn.getEntryBlock())
+ bool SuppressFastISel = false;
+ if (LLVMBB == &Fn.getEntryBlock()) {
LowerArguments(LLVMBB);
+ // If any of the arguments has the byval attribute, forgo
+ // fast-isel in the entry block.
+ if (FastIS) {
+ unsigned j = 1;
+ for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end();
+ I != E; ++I, ++j)
+ if (Fn.paramHasAttr(j, Attribute::ByVal)) {
+ if (EnableFastISelVerbose || EnableFastISelAbort)
+ cerr << "FastISel skips entry block due to byval argument\n";
+ SuppressFastISel = true;
+ break;
+ }
+ }
+ }
+
+ if (MMI && BB->isLandingPad()) {
+ // Add a label to mark the beginning of the landing pad. Deletion of the
+ // landing pad can thus be detected via the MachineModuleInfo.
+ unsigned LabelID = MMI->addLandingPad(BB);
+
+ const TargetInstrDesc &II = TII.get(TargetInstrInfo::EH_LABEL);
+ BuildMI(BB, SDL->getCurDebugLoc(), II).addImm(LabelID);
+
+ // Mark exception register as live in.
+ unsigned Reg = TLI.getExceptionAddressRegister();
+ if (Reg) BB->addLiveIn(Reg);
+
+ // Mark exception selector register as live in.
+ Reg = TLI.getExceptionSelectorRegister();
+ if (Reg) BB->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
+ // like, the basic block containing the invoke), and need to be associated
+ // with it in the dwarf exception handling tables. Currently however the
+ // information is provided by an intrinsic (eh.selector) that can be moved
+ // to unexpected places by the optimizers: if the unwind edge is critical,
+ // then breaking it can result in the intrinsics being in the successor of
+ // the landing pad, not the landing pad itself. This results 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.
+ BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
+
+ if (Br && Br->isUnconditional()) { // Critical edge?
+ BasicBlock::iterator I, E;
+ for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
+ if (isa<EHSelectorInst>(I))
+ break;
+
+ if (I == E)
+ // No catch info found - try to extract some from the successor.
+ copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo);
+ }
+ }
+
// Before doing SelectionDAG ISel, see if FastISel has been requested.
- // FastISel doesn't support EH landing pads, which require special handling.
- if (EnableFastISel && !BB->isLandingPad()) {
- if (FastISel *F = TLI.createFastISel(*FuncInfo->MF, FuncInfo->ValueMap,
- FuncInfo->MBBMap)) {
- // Emit code for any incoming arguments. This must happen before
- // beginning FastISel on the entry block.
- if (LLVMBB == &Fn.getEntryBlock()) {
- CurDAG->setRoot(SDL->getControlRoot());
- CodeGenAndEmitDAG();
- SDL->clear();
- }
- F->setCurrentBlock(BB);
- // Do FastISel on as many instructions as possible.
- for (; I != End; ++I) {
- // Just before the terminator instruction, insert instructions to
- // feed PHI nodes in successor blocks.
- if (isa<TerminatorInst>(I))
- if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, F)) {
- if (DisableFastISelAbort)
- break;
-#ifndef NDEBUG
- I->dump();
-#endif
- assert(0 && "FastISel didn't handle a PHI in a successor");
+ if (FastIS && !SuppressFastISel) {
+ // Emit code for any incoming arguments. This must happen before
+ // beginning FastISel on the entry block.
+ if (LLVMBB == &Fn.getEntryBlock()) {
+ CurDAG->setRoot(SDL->getControlRoot());
+ CodeGenAndEmitDAG();
+ SDL->clear();
+ }
+ FastIS->startNewBlock(BB);
+ // Do FastISel on as many instructions as possible.
+ for (; BI != End; ++BI) {
+ // Just before the terminator instruction, insert instructions to
+ // feed PHI nodes in successor blocks.
+ if (isa<TerminatorInst>(BI))
+ if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, FastIS)) {
+ if (EnableFastISelVerbose || EnableFastISelAbort) {
+ cerr << "FastISel miss: ";
+ BI->dump();
}
+ if (EnableFastISelAbort)
+ assert(0 && "FastISel didn't handle a PHI in a successor");
+ break;
+ }
- // First try normal tablegen-generated "fast" selection.
- if (F->SelectInstruction(I))
- continue;
-
- // Next, try calling the target to attempt to handle the instruction.
- if (F->TargetSelectInstruction(I))
- continue;
-
- // Then handle certain instructions as single-LLVM-Instruction blocks.
- if (isa<CallInst>(I) || isa<LoadInst>(I) ||
- isa<StoreInst>(I)) {
- if (I->getType() != Type::VoidTy) {
- unsigned &R = FuncInfo->ValueMap[I];
- if (!R)
- R = FuncInfo->CreateRegForValue(I);
- }
+ // First try normal tablegen-generated "fast" selection.
+ if (FastIS->SelectInstruction(BI))
+ continue;
- SelectBasicBlock(LLVMBB, I, next(I));
- continue;
+ // Next, try calling the target to attempt to handle the instruction.
+ if (FastIS->TargetSelectInstruction(BI))
+ continue;
+
+ // Then handle certain instructions as single-LLVM-Instruction blocks.
+ if (isa<CallInst>(BI)) {
+ if (EnableFastISelVerbose || EnableFastISelAbort) {
+ cerr << "FastISel missed call: ";
+ BI->dump();
+ }
+
+ if (BI->getType() != Type::VoidTy) {
+ unsigned &R = FuncInfo->ValueMap[BI];
+ if (!R)
+ R = FuncInfo->CreateRegForValue(BI);
}
- if (!DisableFastISelAbort &&
- // For now, don't abort on non-conditional-branch terminators.
- (!isa<TerminatorInst>(I) ||
- (isa<BranchInst>(I) &&
- cast<BranchInst>(I)->isUnconditional()))) {
+ SDL->setCurDebugLoc(FastIS->getCurDebugLoc());
+ SelectBasicBlock(LLVMBB, BI, next(BI));
+ // 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 (EnableFastISelVerbose || EnableFastISelAbort) {
+ cerr << "FastISel miss: ";
+ BI->dump();
+ }
+ if (EnableFastISelAbort)
// The "fast" selector couldn't handle something and bailed.
// For the purpose of debugging, just abort.
-#ifndef NDEBUG
- I->dump();
-#endif
- assert(0 && "FastISel didn't select the entire block");
- }
- break;
+ LLVM_UNREACHABLE("FastISel didn't select the entire block");
}
- delete F;
+ break;
}
}
// 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 (I != End)
- SelectBasicBlock(LLVMBB, I, End);
+ if (BI != End) {
+ // If FastISel is run and it has known DebugLoc then use it.
+ if (FastIS && !FastIS->getCurDebugLoc().isUnknown())
+ SDL->setCurDebugLoc(FastIS->getCurDebugLoc());
+ SelectBasicBlock(LLVMBB, BI, End);
+ }
FinishBasicBlock();
}
+
+ delete FastIS;
}
void
SelectionDAGISel::FinishBasicBlock() {
- // Perform target specific isel post processing.
- InstructionSelectPostProcessing();
-
DOUT << "Target-post-processed machine code:\n";
DEBUG(BB->dump());
}
-/// Schedule - Pick a safe ordering for instructions for each
-/// target node in the graph.
+/// Create the scheduler. If a specific scheduler was specified
+/// via the SchedulerRegistry, use it, otherwise select the
+/// one preferred by the target.
///
-ScheduleDAG *SelectionDAGISel::Schedule() {
+ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
if (!Ctor) {
RegisterScheduler::setDefault(Ctor);
}
- ScheduleDAG *Scheduler = Ctor(this, CurDAG, BB, Fast);
- Scheduler->Run();
-
- return Scheduler;
+ return Ctor(this, OptLevel);
}
-
-HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
- return new HazardRecognizer();
+ScheduleHazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
+ return new ScheduleHazardRecognizer();
}
//===----------------------------------------------------------------------===//
--e; // Don't process a flag operand if it is here.
while (i != e) {
- unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue();
+ unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
if ((Flags & 7) != 4 /*MEM*/) {
// Just skip over this operand, copying the operands verbatim.
- Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
- i += (Flags >> 3) + 1;
+ Ops.insert(Ops.end(), InOps.begin()+i,
+ InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
+ i += InlineAsm::getNumOperandRegisters(Flags) + 1;
} else {
- assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
+ assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
+ "Memory operand with multiple values?");
// Otherwise, this is a memory operand. Ask the target to select it.
std::vector<SDValue> SelOps;
if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) {
- cerr << "Could not match memory address. Inline asm failure!\n";
- exit(1);
+ llvm_report_error("Could not match memory address. Inline asm"
+ " failure!");
}
// Add this to the output node.
MVT IntPtrTy = CurDAG->getTargetLoweringInfo().getPointerTy();
- Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
+ Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size()<< 3),
IntPtrTy));
Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
i += 2;
Ops.push_back(InOps.back());
}
+/// findFlagUse - Return use of MVT::Flag value produced by the specified
+/// SDNode.
+///
+static SDNode *findFlagUse(SDNode *N) {
+ unsigned FlagResNo = N->getNumValues()-1;
+ for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
+ SDUse &Use = I.getUse();
+ if (Use.getResNo() == FlagResNo)
+ return Use.getUser();
+ }
+ return NULL;
+}
+
+/// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
+/// This function recursively traverses up the operand chain, ignoring
+/// certain nodes.
+static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
+ SDNode *Root,
+ SmallPtrSet<SDNode*, 16> &Visited) {
+ if (Use->getNodeId() < Def->getNodeId() ||
+ !Visited.insert(Use))
+ return false;
+
+ for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
+ SDNode *N = Use->getOperand(i).getNode();
+ if (N == Def) {
+ if (Use == ImmedUse || Use == Root)
+ continue; // We are not looking for immediate use.
+ assert(N != Root);
+ return true;
+ }
+
+ // Traverse up the operand chain.
+ if (findNonImmUse(N, Def, ImmedUse, Root, Visited))
+ return true;
+ }
+ return false;
+}
+
+/// isNonImmUse - Start searching from Root up the DAG to check is Def can
+/// be reached. Return true if that's the case. However, ignore direct uses
+/// by ImmedUse (which would be U in the example illustrated in
+/// IsLegalAndProfitableToFold) and by Root (which can happen in the store
+/// case).
+/// FIXME: to be really generic, we should allow direct use by any node
+/// that is being folded. But realisticly since we only fold loads which
+/// have one non-chain use, we only need to watch out for load/op/store
+/// and load/op/cmp case where the root (store / cmp) may reach the load via
+/// its chain operand.
+static inline bool isNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse) {
+ SmallPtrSet<SDNode*, 16> Visited;
+ return findNonImmUse(Root, Def, ImmedUse, Root, Visited);
+}
+
+/// IsLegalAndProfitableToFold - Returns true if the specific operand node N of
+/// U can be folded during instruction selection that starts at Root and
+/// folding N is profitable.
+bool SelectionDAGISel::IsLegalAndProfitableToFold(SDNode *N, SDNode *U,
+ SDNode *Root) const {
+ if (OptLevel == CodeGenOpt::None) return false;
+
+ // If Root use can somehow reach N through a path that that doesn't contain
+ // U then folding N would create a cycle. e.g. In the following
+ // diagram, Root can reach N through X. If N is folded into into Root, then
+ // X is both a predecessor and a successor of U.
+ //
+ // [N*] //
+ // ^ ^ //
+ // / \ //
+ // [U*] [X]? //
+ // ^ ^ //
+ // \ / //
+ // \ / //
+ // [Root*] //
+ //
+ // * indicates nodes to be folded together.
+ //
+ // If Root produces a flag, then it gets (even more) interesting. Since it
+ // will be "glued" together with its flag use in the scheduler, we need to
+ // check if it might reach N.
+ //
+ // [N*] //
+ // ^ ^ //
+ // / \ //
+ // [U*] [X]? //
+ // ^ ^ //
+ // \ \ //
+ // \ | //
+ // [Root*] | //
+ // ^ | //
+ // f | //
+ // | / //
+ // [Y] / //
+ // ^ / //
+ // f / //
+ // | / //
+ // [FU] //
+ //
+ // If FU (flag use) indirectly reaches N (the load), and Root folds N
+ // (call it Fold), then X is a predecessor of FU and a successor of
+ // Fold. But since Fold and FU are flagged together, this will create
+ // a cycle in the scheduling graph.
+
+ MVT VT = Root->getValueType(Root->getNumValues()-1);
+ while (VT == MVT::Flag) {
+ SDNode *FU = findFlagUse(Root);
+ if (FU == NULL)
+ break;
+ Root = FU;
+ VT = Root->getValueType(Root->getNumValues()-1);
+ }
+
+ return !isNonImmUse(Root, N, U);
+}
+
+
char SelectionDAGISel::ID = 0;
projects / oota-llvm.git / blobdiff