SelectionDAGISel.cpp [plain text]
#define DEBUG_TYPE "isel"
#include "ScheduleDAGSDNodes.h"
#include "SelectionDAGBuilder.h"
#include "llvm/Constants.h"
#include "llvm/DebugInfo.h"
#include "llvm/Function.h"
#include "llvm/InlineAsm.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/CodeGen/FastISel.h"
#include "llvm/CodeGen/FunctionLoweringInfo.h"
#include "llvm/CodeGen/GCStrategy.h"
#include "llvm/CodeGen/GCMetadata.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetIntrinsicInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include <algorithm>
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
static cl::opt<bool>
EnableFastISelVerbose2("fast-isel-verbose2", cl::Hidden,
cl::desc("Enable extra verbose messages in the \"fast\" "
"instruction selector"));
STATISTIC(NumFastIselFailRet,"Fast isel fails on Ret");
STATISTIC(NumFastIselFailBr,"Fast isel fails on Br");
STATISTIC(NumFastIselFailSwitch,"Fast isel fails on Switch");
STATISTIC(NumFastIselFailIndirectBr,"Fast isel fails on IndirectBr");
STATISTIC(NumFastIselFailInvoke,"Fast isel fails on Invoke");
STATISTIC(NumFastIselFailResume,"Fast isel fails on Resume");
STATISTIC(NumFastIselFailUnreachable,"Fast isel fails on Unreachable");
STATISTIC(NumFastIselFailAdd,"Fast isel fails on Add");
STATISTIC(NumFastIselFailFAdd,"Fast isel fails on FAdd");
STATISTIC(NumFastIselFailSub,"Fast isel fails on Sub");
STATISTIC(NumFastIselFailFSub,"Fast isel fails on FSub");
STATISTIC(NumFastIselFailMul,"Fast isel fails on Mul");
STATISTIC(NumFastIselFailFMul,"Fast isel fails on FMul");
STATISTIC(NumFastIselFailUDiv,"Fast isel fails on UDiv");
STATISTIC(NumFastIselFailSDiv,"Fast isel fails on SDiv");
STATISTIC(NumFastIselFailFDiv,"Fast isel fails on FDiv");
STATISTIC(NumFastIselFailURem,"Fast isel fails on URem");
STATISTIC(NumFastIselFailSRem,"Fast isel fails on SRem");
STATISTIC(NumFastIselFailFRem,"Fast isel fails on FRem");
STATISTIC(NumFastIselFailAnd,"Fast isel fails on And");
STATISTIC(NumFastIselFailOr,"Fast isel fails on Or");
STATISTIC(NumFastIselFailXor,"Fast isel fails on Xor");
STATISTIC(NumFastIselFailAlloca,"Fast isel fails on Alloca");
STATISTIC(NumFastIselFailLoad,"Fast isel fails on Load");
STATISTIC(NumFastIselFailStore,"Fast isel fails on Store");
STATISTIC(NumFastIselFailAtomicCmpXchg,"Fast isel fails on AtomicCmpXchg");
STATISTIC(NumFastIselFailAtomicRMW,"Fast isel fails on AtomicRWM");
STATISTIC(NumFastIselFailFence,"Fast isel fails on Frence");
STATISTIC(NumFastIselFailGetElementPtr,"Fast isel fails on GetElementPtr");
STATISTIC(NumFastIselFailTrunc,"Fast isel fails on Trunc");
STATISTIC(NumFastIselFailZExt,"Fast isel fails on ZExt");
STATISTIC(NumFastIselFailSExt,"Fast isel fails on SExt");
STATISTIC(NumFastIselFailFPTrunc,"Fast isel fails on FPTrunc");
STATISTIC(NumFastIselFailFPExt,"Fast isel fails on FPExt");
STATISTIC(NumFastIselFailFPToUI,"Fast isel fails on FPToUI");
STATISTIC(NumFastIselFailFPToSI,"Fast isel fails on FPToSI");
STATISTIC(NumFastIselFailUIToFP,"Fast isel fails on UIToFP");
STATISTIC(NumFastIselFailSIToFP,"Fast isel fails on SIToFP");
STATISTIC(NumFastIselFailIntToPtr,"Fast isel fails on IntToPtr");
STATISTIC(NumFastIselFailPtrToInt,"Fast isel fails on PtrToInt");
STATISTIC(NumFastIselFailBitCast,"Fast isel fails on BitCast");
STATISTIC(NumFastIselFailICmp,"Fast isel fails on ICmp");
STATISTIC(NumFastIselFailFCmp,"Fast isel fails on FCmp");
STATISTIC(NumFastIselFailPHI,"Fast isel fails on PHI");
STATISTIC(NumFastIselFailSelect,"Fast isel fails on Select");
STATISTIC(NumFastIselFailCall,"Fast isel fails on Call");
STATISTIC(NumFastIselFailShl,"Fast isel fails on Shl");
STATISTIC(NumFastIselFailLShr,"Fast isel fails on LShr");
STATISTIC(NumFastIselFailAShr,"Fast isel fails on AShr");
STATISTIC(NumFastIselFailVAArg,"Fast isel fails on VAArg");
STATISTIC(NumFastIselFailExtractElement,"Fast isel fails on ExtractElement");
STATISTIC(NumFastIselFailInsertElement,"Fast isel fails on InsertElement");
STATISTIC(NumFastIselFailShuffleVector,"Fast isel fails on ShuffleVector");
STATISTIC(NumFastIselFailExtractValue,"Fast isel fails on ExtractValue");
STATISTIC(NumFastIselFailInsertValue,"Fast isel fails on InsertValue");
STATISTIC(NumFastIselFailLandingPad,"Fast isel fails on LandingPad");
#endif
static cl::opt<bool>
EnableFastISelVerbose("fast-isel-verbose", cl::Hidden,
cl::desc("Enable verbose messages in the \"fast\" "
"instruction selector"));
static cl::opt<bool>
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,
cl::desc("Pop up a window to show dags before the first "
"dag combine pass"));
static cl::opt<bool>
ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
cl::desc("Pop up a window to show dags before legalize types"));
static cl::opt<bool>
ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
cl::desc("Pop up a window to show dags before legalize"));
static cl::opt<bool>
ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
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>
ViewSchedDAGs("view-sched-dags", cl::Hidden,
cl::desc("Pop up a window to show sched dags as they are processed"));
static cl::opt<bool>
ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
cl::desc("Pop up a window to show SUnit dags after they are processed"));
#else
static const bool ViewDAGCombine1 = false,
ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
ViewDAGCombine2 = false,
ViewDAGCombineLT = false,
ViewISelDAGs = false, ViewSchedDAGs = false,
ViewSUnitDAGs = false;
#endif
MachinePassRegistry RegisterScheduler::Registry;
static cl::opt<RegisterScheduler::FunctionPassCtor, false,
RegisterPassParser<RegisterScheduler> >
ISHeuristic("pre-RA-sched",
cl::init(&createDefaultScheduler),
cl::desc("Instruction schedulers available (before register"
" allocation):"));
static RegisterScheduler
defaultListDAGScheduler("default", "Best scheduler for the target",
createDefaultScheduler);
namespace llvm {
ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
CodeGenOpt::Level OptLevel) {
const TargetLowering &TLI = IS->getTargetLowering();
if (OptLevel == CodeGenOpt::None ||
TLI.getSchedulingPreference() == Sched::Source)
return createSourceListDAGScheduler(IS, OptLevel);
if (TLI.getSchedulingPreference() == Sched::RegPressure)
return createBURRListDAGScheduler(IS, OptLevel);
if (TLI.getSchedulingPreference() == Sched::Hybrid)
return createHybridListDAGScheduler(IS, OptLevel);
if (TLI.getSchedulingPreference() == Sched::VLIW)
return createVLIWDAGScheduler(IS, OptLevel);
assert(TLI.getSchedulingPreference() == Sched::ILP &&
"Unknown sched type!");
return createILPListDAGScheduler(IS, OptLevel);
}
}
MachineBasicBlock *
TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
MachineBasicBlock *MBB) const {
#ifndef NDEBUG
dbgs() << "If a target marks an instruction with "
"'usesCustomInserter', it must implement "
"TargetLowering::EmitInstrWithCustomInserter!";
#endif
llvm_unreachable(0);
}
void TargetLowering::AdjustInstrPostInstrSelection(MachineInstr *MI,
SDNode *Node) const {
assert(!MI->hasPostISelHook() &&
"If a target marks an instruction with 'hasPostISelHook', "
"it must implement TargetLowering::AdjustInstrPostInstrSelection!");
}
SelectionDAGISel::SelectionDAGISel(const TargetMachine &tm,
CodeGenOpt::Level OL) :
MachineFunctionPass(ID), TM(tm), TLI(*tm.getTargetLowering()),
FuncInfo(new FunctionLoweringInfo(TLI)),
CurDAG(new SelectionDAG(tm, OL)),
SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)),
GFI(),
OptLevel(OL),
DAGSize(0) {
initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());
initializeAliasAnalysisAnalysisGroup(*PassRegistry::getPassRegistry());
initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry());
initializeTargetLibraryInfoPass(*PassRegistry::getPassRegistry());
}
SelectionDAGISel::~SelectionDAGISel() {
delete SDB;
delete CurDAG;
delete FuncInfo;
}
void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<AliasAnalysis>();
AU.addPreserved<AliasAnalysis>();
AU.addRequired<GCModuleInfo>();
AU.addPreserved<GCModuleInfo>();
AU.addRequired<TargetLibraryInfo>();
if (UseMBPI && OptLevel != CodeGenOpt::None)
AU.addRequired<BranchProbabilityInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
static void SplitCriticalSideEffectEdges(Function &Fn, Pass *SDISel) {
for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
PHINode *PN = dyn_cast<PHINode>(BB->begin());
if (PN == 0) continue;
ReprocessBlock:
for (BasicBlock::iterator I = BB->begin(); (PN = dyn_cast<PHINode>(I)); ++I)
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
ConstantExpr *CE = dyn_cast<ConstantExpr>(PN->getIncomingValue(i));
if (CE == 0 || !CE->canTrap()) continue;
BasicBlock *Pred = PN->getIncomingBlock(i);
if (Pred->getTerminator()->getNumSuccessors() == 1)
continue;
SplitCriticalEdge(Pred->getTerminator(),
GetSuccessorNumber(Pred, BB), SDISel, true);
goto ReprocessBlock;
}
}
}
bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
assert((!EnableFastISelVerbose || TM.Options.EnableFastISel) &&
"-fast-isel-verbose requires -fast-isel");
assert((!EnableFastISelAbort || TM.Options.EnableFastISel) &&
"-fast-isel-abort requires -fast-isel");
const Function &Fn = *mf.getFunction();
const TargetInstrInfo &TII = *TM.getInstrInfo();
const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
MF = &mf;
RegInfo = &MF->getRegInfo();
AA = &getAnalysis<AliasAnalysis>();
LibInfo = &getAnalysis<TargetLibraryInfo>();
GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : 0;
DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
SplitCriticalSideEffectEdges(const_cast<Function&>(Fn), this);
CurDAG->init(*MF);
FuncInfo->set(Fn, *MF);
if (UseMBPI && OptLevel != CodeGenOpt::None)
FuncInfo->BPI = &getAnalysis<BranchProbabilityInfo>();
else
FuncInfo->BPI = 0;
SDB->init(GFI, *AA, LibInfo);
SelectAllBasicBlocks(Fn);
MachineBasicBlock *EntryMBB = MF->begin();
RegInfo->EmitLiveInCopies(EntryMBB, TRI, TII);
DenseMap<unsigned, unsigned> LiveInMap;
if (!FuncInfo->ArgDbgValues.empty())
for (MachineRegisterInfo::livein_iterator LI = RegInfo->livein_begin(),
E = RegInfo->livein_end(); LI != E; ++LI)
if (LI->second)
LiveInMap.insert(std::make_pair(LI->first, LI->second));
for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
MachineInstr *MI = FuncInfo->ArgDbgValues[e-i-1];
unsigned Reg = MI->getOperand(0).getReg();
if (TargetRegisterInfo::isPhysicalRegister(Reg))
EntryMBB->insert(EntryMBB->begin(), MI);
else {
MachineInstr *Def = RegInfo->getVRegDef(Reg);
MachineBasicBlock::iterator InsertPos = Def;
Def->getParent()->insert(llvm::next(InsertPos), MI);
}
DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
if (LDI != LiveInMap.end()) {
MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
MachineBasicBlock::iterator InsertPos = Def;
const MDNode *Variable =
MI->getOperand(MI->getNumOperands()-1).getMetadata();
unsigned Offset = MI->getOperand(1).getImm();
BuildMI(*EntryMBB, ++InsertPos, MI->getDebugLoc(),
TII.get(TargetOpcode::DBG_VALUE))
.addReg(LDI->second, RegState::Debug)
.addImm(Offset).addMetadata(Variable);
MachineInstr *CopyUseMI = NULL;
for (MachineRegisterInfo::use_iterator
UI = RegInfo->use_begin(LDI->second);
MachineInstr *UseMI = UI.skipInstruction();) {
if (UseMI->isDebugValue()) continue;
if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) {
CopyUseMI = UseMI; continue;
}
CopyUseMI = NULL; break;
}
if (CopyUseMI) {
MachineInstr *NewMI =
BuildMI(*MF, CopyUseMI->getDebugLoc(),
TII.get(TargetOpcode::DBG_VALUE))
.addReg(CopyUseMI->getOperand(0).getReg(), RegState::Debug)
.addImm(Offset).addMetadata(Variable);
MachineBasicBlock::iterator Pos = CopyUseMI;
EntryMBB->insertAfter(Pos, NewMI);
}
}
}
MachineFrameInfo *MFI = MF->getFrameInfo();
if (!MFI->hasCalls()) {
for (MachineFunction::const_iterator
I = MF->begin(), E = MF->end(); I != E; ++I) {
const MachineBasicBlock *MBB = I;
for (MachineBasicBlock::const_iterator
II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
const MCInstrDesc &MCID = TM.getInstrInfo()->get(II->getOpcode());
if ((MCID.isCall() && !MCID.isReturn()) ||
II->isStackAligningInlineAsm()) {
MFI->setHasCalls(true);
goto done;
}
}
}
}
done:
MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice());
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;
for (;;) {
DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To);
if (J == E) break;
To = J->second;
}
MRI.replaceRegWith(From, To);
}
MRI.freezeReservedRegs(*MF);
FuncInfo->clear();
return true;
}
void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
BasicBlock::const_iterator End,
bool &HadTailCall) {
for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I)
SDB->visit(*I);
CurDAG->setRoot(SDB->getControlRoot());
HadTailCall = SDB->HasTailCall;
SDB->clear();
CodeGenAndEmitDAG();
}
void SelectionDAGISel::ComputeLiveOutVRegInfo() {
SmallPtrSet<SDNode*, 128> VisitedNodes;
SmallVector<SDNode*, 128> Worklist;
Worklist.push_back(CurDAG->getRoot().getNode());
APInt KnownZero;
APInt KnownOne;
do {
SDNode *N = Worklist.pop_back_val();
if (!VisitedNodes.insert(N))
continue;
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
if (N->getOperand(i).getValueType() == MVT::Other)
Worklist.push_back(N->getOperand(i).getNode());
if (N->getOpcode() != ISD::CopyToReg)
continue;
unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
if (!TargetRegisterInfo::isVirtualRegister(DestReg))
continue;
SDValue Src = N->getOperand(2);
EVT SrcVT = Src.getValueType();
if (!SrcVT.isInteger() || SrcVT.isVector())
continue;
unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
CurDAG->ComputeMaskedBits(Src, KnownZero, KnownOne);
FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, KnownZero, KnownOne);
} while (!Worklist.empty());
}
void SelectionDAGISel::CodeGenAndEmitDAG() {
std::string GroupName;
if (TimePassesIsEnabled)
GroupName = "Instruction Selection and Scheduling";
std::string BlockName;
int BlockNumber = -1;
(void)BlockNumber;
#ifdef NDEBUG
if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
ViewSUnitDAGs)
#endif
{
BlockNumber = FuncInfo->MBB->getNumber();
BlockName = MF->getName().str() + ":" +
FuncInfo->MBB->getBasicBlock()->getName().str();
}
DEBUG(dbgs() << "Initial selection DAG: BB#" << BlockNumber
<< " '" << BlockName << "'\n"; CurDAG->dump());
if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName);
{
NamedRegionTimer T("DAG Combining 1", GroupName, TimePassesIsEnabled);
CurDAG->Combine(BeforeLegalizeTypes, *AA, OptLevel);
}
DEBUG(dbgs() << "Optimized lowered selection DAG: BB#" << BlockNumber
<< " '" << BlockName << "'\n"; CurDAG->dump());
if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " +
BlockName);
bool Changed;
{
NamedRegionTimer T("Type Legalization", GroupName, TimePassesIsEnabled);
Changed = CurDAG->LegalizeTypes();
}
DEBUG(dbgs() << "Type-legalized selection DAG: BB#" << BlockNumber
<< " '" << BlockName << "'\n"; CurDAG->dump());
if (Changed) {
if (ViewDAGCombineLT)
CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
{
NamedRegionTimer T("DAG Combining after legalize types", GroupName,
TimePassesIsEnabled);
CurDAG->Combine(AfterLegalizeTypes, *AA, OptLevel);
}
DEBUG(dbgs() << "Optimized type-legalized selection DAG: BB#" << BlockNumber
<< " '" << BlockName << "'\n"; CurDAG->dump());
}
{
NamedRegionTimer T("Vector Legalization", GroupName, TimePassesIsEnabled);
Changed = CurDAG->LegalizeVectors();
}
if (Changed) {
{
NamedRegionTimer T("Type Legalization 2", GroupName, TimePassesIsEnabled);
CurDAG->LegalizeTypes();
}
if (ViewDAGCombineLT)
CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
{
NamedRegionTimer T("DAG Combining after legalize vectors", GroupName,
TimePassesIsEnabled);
CurDAG->Combine(AfterLegalizeVectorOps, *AA, OptLevel);
}
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();
}
DEBUG(dbgs() << "Legalized selection DAG: BB#" << BlockNumber
<< " '" << BlockName << "'\n"; CurDAG->dump());
if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName);
{
NamedRegionTimer T("DAG Combining 2", GroupName, TimePassesIsEnabled);
CurDAG->Combine(AfterLegalizeDAG, *AA, OptLevel);
}
DEBUG(dbgs() << "Optimized legalized selection DAG: BB#" << BlockNumber
<< " '" << BlockName << "'\n"; CurDAG->dump());
if (OptLevel != CodeGenOpt::None)
ComputeLiveOutVRegInfo();
if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName);
{
NamedRegionTimer T("Instruction Selection", GroupName, TimePassesIsEnabled);
DoInstructionSelection();
}
DEBUG(dbgs() << "Selected selection DAG: BB#" << BlockNumber
<< " '" << BlockName << "'\n"; CurDAG->dump());
if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName);
ScheduleDAGSDNodes *Scheduler = CreateScheduler();
{
NamedRegionTimer T("Instruction Scheduling", GroupName,
TimePassesIsEnabled);
Scheduler->Run(CurDAG, FuncInfo->MBB);
}
if (ViewSUnitDAGs) Scheduler->viewGraph();
MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
{
NamedRegionTimer T("Instruction Creation", GroupName, TimePassesIsEnabled);
LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
}
if (FirstMBB != LastMBB)
SDB->UpdateSplitBlock(FirstMBB, LastMBB);
{
NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName,
TimePassesIsEnabled);
delete Scheduler;
}
CurDAG->clear();
}
namespace {
class ISelUpdater : public SelectionDAG::DAGUpdateListener {
SelectionDAG::allnodes_iterator &ISelPosition;
public:
ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
: SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
virtual void NodeDeleted(SDNode *N, SDNode *E) {
if (ISelPosition == SelectionDAG::allnodes_iterator(N))
++ISelPosition;
}
};
}
void SelectionDAGISel::DoInstructionSelection() {
DEBUG(errs() << "===== Instruction selection begins: BB#"
<< FuncInfo->MBB->getNumber()
<< " '" << FuncInfo->MBB->getName() << "'\n");
PreprocessISelDAG();
{
DAGSize = CurDAG->AssignTopologicalOrder();
HandleSDNode Dummy(CurDAG->getRoot());
SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());
++ISelPosition;
ISelUpdater ISU(*CurDAG, ISelPosition);
while (ISelPosition != CurDAG->allnodes_begin()) {
SDNode *Node = --ISelPosition;
if (Node->use_empty())
continue;
SDNode *ResNode = Select(Node);
if (ResNode == Node || Node->getOpcode() == ISD::DELETED_NODE)
continue;
if (ResNode)
ReplaceUses(Node, ResNode);
if (Node->use_empty()) CurDAG->RemoveDeadNode(Node);
}
CurDAG->setRoot(Dummy.getValue());
}
DEBUG(errs() << "===== Instruction selection ends:\n");
PostprocessISelDAG();
}
void SelectionDAGISel::PrepareEHLandingPad() {
MachineBasicBlock *MBB = FuncInfo->MBB;
MCSymbol *Label = MF->getMMI().addLandingPad(MBB);
MF->getMMI().setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
const MCInstrDesc &II = TM.getInstrInfo()->get(TargetOpcode::EH_LABEL);
BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
.addSym(Label);
unsigned Reg = TLI.getExceptionPointerRegister();
if (Reg) MBB->addLiveIn(Reg);
Reg = TLI.getExceptionSelectorRegister();
if (Reg) MBB->addLiveIn(Reg);
}
bool SelectionDAGISel::TryToFoldFastISelLoad(const LoadInst *LI,
const Instruction *FoldInst,
FastISel *FastIS) {
unsigned MaxUsers = 6;
const Instruction *TheUser = LI->use_back();
while (TheUser != FoldInst && TheUser->getParent() == FoldInst->getParent() &&
--MaxUsers) { if (!TheUser->hasOneUse())
return false;
TheUser = TheUser->use_back();
}
if (TheUser != FoldInst)
return false;
if (LI->isVolatile()) return false;
unsigned LoadReg = FastIS->getRegForValue(LI);
if (LoadReg == 0)
return false;
MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(LoadReg);
if (RI == RegInfo->reg_end())
return false;
MachineRegisterInfo::reg_iterator PostRI = RI; ++PostRI;
if (PostRI != RegInfo->reg_end())
return false;
assert(RI.getOperand().isUse() &&
"The only use of the vreg must be a use, we haven't emitted the def!");
MachineInstr *User = &*RI;
FuncInfo->InsertPt = User;
FuncInfo->MBB = User->getParent();
return FastIS->TryToFoldLoad(User, RI.getOperandNo(), LI);
}
static bool isFoldedOrDeadInstruction(const Instruction *I,
FunctionLoweringInfo *FuncInfo) {
return !I->mayWriteToMemory() && !isa<TerminatorInst>(I) && !isa<DbgInfoIntrinsic>(I) && !isa<LandingPadInst>(I) && !FuncInfo->isExportedInst(I); }
#ifndef NDEBUG
static void collectFailStats(const Instruction *I) {
switch (I->getOpcode()) {
default: assert (0 && "<Invalid operator> ");
case Instruction::Ret: NumFastIselFailRet++; return;
case Instruction::Br: NumFastIselFailBr++; return;
case Instruction::Switch: NumFastIselFailSwitch++; return;
case Instruction::IndirectBr: NumFastIselFailIndirectBr++; return;
case Instruction::Invoke: NumFastIselFailInvoke++; return;
case Instruction::Resume: NumFastIselFailResume++; return;
case Instruction::Unreachable: NumFastIselFailUnreachable++; return;
case Instruction::Add: NumFastIselFailAdd++; return;
case Instruction::FAdd: NumFastIselFailFAdd++; return;
case Instruction::Sub: NumFastIselFailSub++; return;
case Instruction::FSub: NumFastIselFailFSub++; return;
case Instruction::Mul: NumFastIselFailMul++; return;
case Instruction::FMul: NumFastIselFailFMul++; return;
case Instruction::UDiv: NumFastIselFailUDiv++; return;
case Instruction::SDiv: NumFastIselFailSDiv++; return;
case Instruction::FDiv: NumFastIselFailFDiv++; return;
case Instruction::URem: NumFastIselFailURem++; return;
case Instruction::SRem: NumFastIselFailSRem++; return;
case Instruction::FRem: NumFastIselFailFRem++; return;
case Instruction::And: NumFastIselFailAnd++; return;
case Instruction::Or: NumFastIselFailOr++; return;
case Instruction::Xor: NumFastIselFailXor++; return;
case Instruction::Alloca: NumFastIselFailAlloca++; return;
case Instruction::Load: NumFastIselFailLoad++; return;
case Instruction::Store: NumFastIselFailStore++; return;
case Instruction::AtomicCmpXchg: NumFastIselFailAtomicCmpXchg++; return;
case Instruction::AtomicRMW: NumFastIselFailAtomicRMW++; return;
case Instruction::Fence: NumFastIselFailFence++; return;
case Instruction::GetElementPtr: NumFastIselFailGetElementPtr++; return;
case Instruction::Trunc: NumFastIselFailTrunc++; return;
case Instruction::ZExt: NumFastIselFailZExt++; return;
case Instruction::SExt: NumFastIselFailSExt++; return;
case Instruction::FPTrunc: NumFastIselFailFPTrunc++; return;
case Instruction::FPExt: NumFastIselFailFPExt++; return;
case Instruction::FPToUI: NumFastIselFailFPToUI++; return;
case Instruction::FPToSI: NumFastIselFailFPToSI++; return;
case Instruction::UIToFP: NumFastIselFailUIToFP++; return;
case Instruction::SIToFP: NumFastIselFailSIToFP++; return;
case Instruction::IntToPtr: NumFastIselFailIntToPtr++; return;
case Instruction::PtrToInt: NumFastIselFailPtrToInt++; return;
case Instruction::BitCast: NumFastIselFailBitCast++; return;
case Instruction::ICmp: NumFastIselFailICmp++; return;
case Instruction::FCmp: NumFastIselFailFCmp++; return;
case Instruction::PHI: NumFastIselFailPHI++; return;
case Instruction::Select: NumFastIselFailSelect++; return;
case Instruction::Call: NumFastIselFailCall++; return;
case Instruction::Shl: NumFastIselFailShl++; return;
case Instruction::LShr: NumFastIselFailLShr++; return;
case Instruction::AShr: NumFastIselFailAShr++; return;
case Instruction::VAArg: NumFastIselFailVAArg++; return;
case Instruction::ExtractElement: NumFastIselFailExtractElement++; return;
case Instruction::InsertElement: NumFastIselFailInsertElement++; return;
case Instruction::ShuffleVector: NumFastIselFailShuffleVector++; return;
case Instruction::ExtractValue: NumFastIselFailExtractValue++; return;
case Instruction::InsertValue: NumFastIselFailInsertValue++; return;
case Instruction::LandingPad: NumFastIselFailLandingPad++; return;
}
}
#endif
void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
FastISel *FastIS = 0;
if (TM.Options.EnableFastISel)
FastIS = TLI.createFastISel(*FuncInfo, LibInfo);
ReversePostOrderTraversal<const Function*> RPOT(&Fn);
for (ReversePostOrderTraversal<const Function*>::rpo_iterator
I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
const BasicBlock *LLVMBB = *I;
if (OptLevel != CodeGenOpt::None) {
bool AllPredsVisited = true;
for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
PI != PE; ++PI) {
if (!FuncInfo->VisitedBBs.count(*PI)) {
AllPredsVisited = false;
break;
}
}
if (AllPredsVisited) {
for (BasicBlock::const_iterator I = LLVMBB->begin();
isa<PHINode>(I); ++I)
FuncInfo->ComputePHILiveOutRegInfo(cast<PHINode>(I));
} else {
for (BasicBlock::const_iterator I = LLVMBB->begin();
isa<PHINode>(I); ++I)
FuncInfo->InvalidatePHILiveOutRegInfo(cast<PHINode>(I));
}
FuncInfo->VisitedBBs.insert(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 = End;
FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI();
if (FuncInfo->MBB->isLandingPad())
PrepareEHLandingPad();
if (LLVMBB == &Fn.getEntryBlock())
LowerArguments(LLVMBB);
if (FastIS) {
FastIS->startNewBlock();
if (LLVMBB == &Fn.getEntryBlock()) {
CurDAG->setRoot(SDB->getControlRoot());
SDB->clear();
CodeGenAndEmitDAG();
if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
FastIS->setLastLocalValue(llvm::prior(FuncInfo->InsertPt));
else
FastIS->setLastLocalValue(0);
}
unsigned NumFastIselRemaining = std::distance(Begin, End);
for (; BI != Begin; --BI) {
const Instruction *Inst = llvm::prior(BI);
if (isFoldedOrDeadInstruction(Inst, FuncInfo)) {
--NumFastIselRemaining;
continue;
}
FastIS->recomputeInsertPt();
if (FastIS->SelectInstruction(Inst)) {
--NumFastIselRemaining;
++NumFastIselSuccess;
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)) {
BI = llvm::next(BasicBlock::const_iterator(BeforeInst));
--NumFastIselRemaining;
++NumFastIselSuccess;
}
continue;
}
#ifndef NDEBUG
if (EnableFastISelVerbose2)
collectFailStats(Inst);
#endif
if (isa<CallInst>(Inst)) {
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel missed call: ";
Inst->dump();
}
if (!Inst->getType()->isVoidTy() && !Inst->use_empty()) {
unsigned &R = FuncInfo->ValueMap[Inst];
if (!R)
R = FuncInfo->CreateRegs(Inst->getType());
}
bool HadTailCall = false;
SelectBasicBlock(Inst, BI, HadTailCall);
unsigned RemainingNow = std::distance(Begin, BI);
NumFastIselFailures += NumFastIselRemaining - RemainingNow;
if (HadTailCall) {
--BI;
break;
}
NumFastIselRemaining = RemainingNow;
continue;
}
if (isa<TerminatorInst>(Inst) && !isa<BranchInst>(Inst)) {
NumFastIselFailures += NumFastIselRemaining;
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel missed terminator: ";
Inst->dump();
}
} else {
NumFastIselFailures += NumFastIselRemaining;
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel miss: ";
Inst->dump();
}
if (EnableFastISelAbort)
llvm_unreachable("FastISel didn't select the entire block");
}
break;
}
FastIS->recomputeInsertPt();
}
if (Begin != BI)
++NumDAGBlocks;
else
++NumFastIselBlocks;
if (Begin != BI) {
bool HadTailCall;
SelectBasicBlock(Begin, BI, HadTailCall);
}
FinishBasicBlock();
FuncInfo->PHINodesToUpdate.clear();
}
delete FastIS;
SDB->clearDanglingDebugInfo();
}
void
SelectionDAGISel::FinishBasicBlock() {
DEBUG(dbgs() << "Total amount of phi nodes to update: "
<< FuncInfo->PHINodesToUpdate.size() << "\n";
for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i)
dbgs() << "Node " << i << " : ("
<< FuncInfo->PHINodesToUpdate[i].first
<< ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
if (SDB->SwitchCases.empty() &&
SDB->JTCases.empty() &&
SDB->BitTestCases.empty()) {
for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
MachineInstr *PHI = FuncInfo->PHINodesToUpdate[i].first;
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
continue;
PHI->addOperand(
MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[i].second, false));
PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB));
}
return;
}
for (unsigned i = 0, e = SDB->BitTestCases.size(); i != e; ++i) {
if (!SDB->BitTestCases[i].Emitted) {
FuncInfo->MBB = SDB->BitTestCases[i].Parent;
FuncInfo->InsertPt = FuncInfo->MBB->end();
SDB->visitBitTestHeader(SDB->BitTestCases[i], FuncInfo->MBB);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
CodeGenAndEmitDAG();
}
uint32_t UnhandledWeight = 0;
for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j)
UnhandledWeight += SDB->BitTestCases[i].Cases[j].ExtraWeight;
for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) {
UnhandledWeight -= SDB->BitTestCases[i].Cases[j].ExtraWeight;
FuncInfo->MBB = SDB->BitTestCases[i].Cases[j].ThisBB;
FuncInfo->InsertPt = FuncInfo->MBB->end();
if (j+1 != ej)
SDB->visitBitTestCase(SDB->BitTestCases[i],
SDB->BitTestCases[i].Cases[j+1].ThisBB,
UnhandledWeight,
SDB->BitTestCases[i].Reg,
SDB->BitTestCases[i].Cases[j],
FuncInfo->MBB);
else
SDB->visitBitTestCase(SDB->BitTestCases[i],
SDB->BitTestCases[i].Default,
UnhandledWeight,
SDB->BitTestCases[i].Reg,
SDB->BitTestCases[i].Cases[j],
FuncInfo->MBB);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
CodeGenAndEmitDAG();
}
for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
pi != pe; ++pi) {
MachineInstr *PHI = FuncInfo->PHINodesToUpdate[pi].first;
MachineBasicBlock *PHIBB = PHI->getParent();
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
if (PHIBB == SDB->BitTestCases[i].Default) {
PHI->addOperand(MachineOperand::
CreateReg(FuncInfo->PHINodesToUpdate[pi].second,
false));
PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Parent));
PHI->addOperand(MachineOperand::
CreateReg(FuncInfo->PHINodesToUpdate[pi].second,
false));
PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Cases.
back().ThisBB));
}
for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size();
j != ej; ++j) {
MachineBasicBlock* cBB = SDB->BitTestCases[i].Cases[j].ThisBB;
if (cBB->isSuccessor(PHIBB)) {
PHI->addOperand(MachineOperand::
CreateReg(FuncInfo->PHINodesToUpdate[pi].second,
false));
PHI->addOperand(MachineOperand::CreateMBB(cBB));
}
}
}
}
SDB->BitTestCases.clear();
for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) {
if (!SDB->JTCases[i].first.Emitted) {
FuncInfo->MBB = SDB->JTCases[i].first.HeaderBB;
FuncInfo->InsertPt = FuncInfo->MBB->end();
SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first,
FuncInfo->MBB);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
CodeGenAndEmitDAG();
}
FuncInfo->MBB = SDB->JTCases[i].second.MBB;
FuncInfo->InsertPt = FuncInfo->MBB->end();
SDB->visitJumpTable(SDB->JTCases[i].second);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
CodeGenAndEmitDAG();
for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
pi != pe; ++pi) {
MachineInstr *PHI = FuncInfo->PHINodesToUpdate[pi].first;
MachineBasicBlock *PHIBB = PHI->getParent();
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
if (PHIBB == SDB->JTCases[i].second.Default) {
PHI->addOperand
(MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[pi].second,
false));
PHI->addOperand
(MachineOperand::CreateMBB(SDB->JTCases[i].first.HeaderBB));
}
if (FuncInfo->MBB->isSuccessor(PHIBB)) {
PHI->addOperand
(MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[pi].second,
false));
PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB));
}
}
}
SDB->JTCases.clear();
for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
MachineInstr *PHI = FuncInfo->PHINodesToUpdate[i].first;
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
if (FuncInfo->MBB->isSuccessor(PHI->getParent())) {
PHI->addOperand(
MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[i].second, false));
PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB));
}
}
for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
FuncInfo->MBB = SDB->SwitchCases[i].ThisBB;
FuncInfo->InsertPt = FuncInfo->MBB->end();
SmallVector<MachineBasicBlock *, 2> Succs;
Succs.push_back(SDB->SwitchCases[i].TrueBB);
if (SDB->SwitchCases[i].TrueBB != SDB->SwitchCases[i].FalseBB)
Succs.push_back(SDB->SwitchCases[i].FalseBB);
SDB->visitSwitchCase(SDB->SwitchCases[i], FuncInfo->MBB);
CurDAG->setRoot(SDB->getRoot());
SDB->clear();
CodeGenAndEmitDAG();
MachineBasicBlock *ThisBB = FuncInfo->MBB;
for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
FuncInfo->MBB = Succs[i];
FuncInfo->InsertPt = FuncInfo->MBB->end();
if (ThisBB->isSuccessor(FuncInfo->MBB)) {
for (MachineBasicBlock::iterator Phi = FuncInfo->MBB->begin();
Phi != FuncInfo->MBB->end() && Phi->isPHI();
++Phi) {
for (unsigned pn = 0; ; ++pn) {
assert(pn != FuncInfo->PHINodesToUpdate.size() &&
"Didn't find PHI entry!");
if (FuncInfo->PHINodesToUpdate[pn].first == Phi) {
Phi->addOperand(MachineOperand::
CreateReg(FuncInfo->PHINodesToUpdate[pn].second,
false));
Phi->addOperand(MachineOperand::CreateMBB(ThisBB));
break;
}
}
}
}
}
}
SDB->SwitchCases.clear();
}
ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
if (!Ctor) {
Ctor = ISHeuristic;
RegisterScheduler::setDefault(Ctor);
}
return Ctor(this, OptLevel);
}
bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
int64_t DesiredMaskS) const {
const APInt &ActualMask = RHS->getAPIntValue();
const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
if (ActualMask == DesiredMask)
return true;
if (ActualMask.intersects(~DesiredMask))
return false;
APInt NeededMask = DesiredMask & ~ActualMask;
if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
return true;
return false;
}
bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
int64_t DesiredMaskS) const {
const APInt &ActualMask = RHS->getAPIntValue();
const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
if (ActualMask == DesiredMask)
return true;
if (ActualMask.intersects(~DesiredMask))
return false;
APInt NeededMask = DesiredMask & ~ActualMask;
APInt KnownZero, KnownOne;
CurDAG->ComputeMaskedBits(LHS, KnownZero, KnownOne);
if ((NeededMask & KnownOne) == NeededMask)
return true;
return false;
}
void SelectionDAGISel::
SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) {
std::vector<SDValue> InOps;
std::swap(InOps, Ops);
Ops.push_back(InOps[InlineAsm::Op_InputChain]); Ops.push_back(InOps[InlineAsm::Op_AsmString]); Ops.push_back(InOps[InlineAsm::Op_MDNode]); Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]);
unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
if (InOps[e-1].getValueType() == MVT::Glue)
--e;
while (i != e) {
unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
if (!InlineAsm::isMemKind(Flags)) {
Ops.insert(Ops.end(), InOps.begin()+i,
InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
i += InlineAsm::getNumOperandRegisters(Flags) + 1;
} else {
assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
"Memory operand with multiple values?");
std::vector<SDValue> SelOps;
if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps))
report_fatal_error("Could not match memory address. Inline asm"
" failure!");
unsigned NewFlags =
InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size());
Ops.push_back(CurDAG->getTargetConstant(NewFlags, MVT::i32));
Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
i += 2;
}
}
if (e != InOps.size())
Ops.push_back(InOps.back());
}
static SDNode *findGlueUse(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;
}
static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
SDNode *Root, SmallPtrSet<SDNode*, 16> &Visited,
bool IgnoreChains) {
if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1))
return false;
if (!Visited.insert(Use))
return false;
for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
if (Use->getOperand(i).getValueType() == MVT::Other && IgnoreChains)
continue;
SDNode *N = Use->getOperand(i).getNode();
if (N == Def) {
if (Use == ImmedUse || Use == Root)
continue; assert(N != Root);
return true;
}
if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains))
return true;
}
return false;
}
bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
SDNode *Root) const {
if (OptLevel == CodeGenOpt::None) return false;
return N.hasOneUse();
}
bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
CodeGenOpt::Level OptLevel,
bool IgnoreChains) {
if (OptLevel == CodeGenOpt::None) return false;
EVT VT = Root->getValueType(Root->getNumValues()-1);
while (VT == MVT::Glue) {
SDNode *GU = findGlueUse(Root);
if (GU == NULL)
break;
Root = GU;
VT = Root->getValueType(Root->getNumValues()-1);
IgnoreChains = false;
}
SmallPtrSet<SDNode*, 16> Visited;
return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
}
SDNode *SelectionDAGISel::Select_INLINEASM(SDNode *N) {
std::vector<SDValue> Ops(N->op_begin(), N->op_end());
SelectInlineAsmMemoryOperands(Ops);
std::vector<EVT> VTs;
VTs.push_back(MVT::Other);
VTs.push_back(MVT::Glue);
SDValue New = CurDAG->getNode(ISD::INLINEASM, N->getDebugLoc(),
VTs, &Ops[0], Ops.size());
New->setNodeId(-1);
return New.getNode();
}
SDNode *SelectionDAGISel::Select_UNDEF(SDNode *N) {
return CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF,N->getValueType(0));
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static uint64_t
GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
assert(Val >= 128 && "Not a VBR");
Val &= 127;
unsigned Shift = 7;
uint64_t NextBits;
do {
NextBits = MatcherTable[Idx++];
Val |= (NextBits&127) << Shift;
Shift += 7;
} while (NextBits & 128);
return Val;
}
void SelectionDAGISel::
UpdateChainsAndGlue(SDNode *NodeToMatch, SDValue InputChain,
const SmallVectorImpl<SDNode*> &ChainNodesMatched,
SDValue InputGlue,
const SmallVectorImpl<SDNode*> &GlueResultNodesMatched,
bool isMorphNodeTo) {
SmallVector<SDNode*, 4> NowDeadNodes;
if (!ChainNodesMatched.empty()) {
assert(InputChain.getNode() != 0 &&
"Matched input chains but didn't produce a chain");
for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
SDNode *ChainNode = ChainNodesMatched[i];
if (ChainNode->getOpcode() == ISD::DELETED_NODE)
continue;
if (ChainNode == NodeToMatch && isMorphNodeTo)
continue;
SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
if (ChainVal.getValueType() == MVT::Glue)
ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain);
if (ChainNode->use_empty() &&
!std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode))
NowDeadNodes.push_back(ChainNode);
}
}
if (InputGlue.getNode() != 0) {
for (unsigned i = 0, e = GlueResultNodesMatched.size(); i != e; ++i) {
SDNode *FRN = GlueResultNodesMatched[i];
if (FRN->getOpcode() == ISD::DELETED_NODE)
continue;
assert(FRN->getValueType(FRN->getNumValues()-1) == MVT::Glue &&
"Doesn't have a glue result");
CurDAG->ReplaceAllUsesOfValueWith(SDValue(FRN, FRN->getNumValues()-1),
InputGlue);
if (FRN->use_empty() &&
!std::count(NowDeadNodes.begin(), NowDeadNodes.end(), FRN))
NowDeadNodes.push_back(FRN);
}
}
if (!NowDeadNodes.empty())
CurDAG->RemoveDeadNodes(NowDeadNodes);
DEBUG(errs() << "ISEL: Match complete!\n");
}
enum ChainResult {
CR_Simple,
CR_InducesCycle,
CR_LeadsToInteriorNode
};
static ChainResult
WalkChainUsers(const SDNode *ChainedNode,
SmallVectorImpl<SDNode*> &ChainedNodesInPattern,
SmallVectorImpl<SDNode*> &InteriorChainedNodes) {
ChainResult Result = CR_Simple;
for (SDNode::use_iterator UI = ChainedNode->use_begin(),
E = ChainedNode->use_end(); UI != E; ++UI) {
if (UI.getUse().getValueType() != MVT::Other) continue;
SDNode *User = *UI;
if (User->isMachineOpcode() ||
User->getOpcode() == ISD::HANDLENODE) continue;
unsigned UserOpcode = User->getOpcode();
if (UserOpcode == ISD::CopyToReg ||
UserOpcode == ISD::CopyFromReg ||
UserOpcode == ISD::INLINEASM ||
UserOpcode == ISD::EH_LABEL ||
UserOpcode == ISD::LIFETIME_START ||
UserOpcode == ISD::LIFETIME_END) {
if (User->getNodeId() == -1)
continue;
}
if (User->getOpcode() != ISD::TokenFactor) {
if (!std::count(ChainedNodesInPattern.begin(),
ChainedNodesInPattern.end(), User))
return CR_InducesCycle;
Result = CR_LeadsToInteriorNode;
InteriorChainedNodes.push_back(User);
continue;
}
switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) {
case CR_Simple:
continue;
case CR_InducesCycle:
return CR_InducesCycle;
case CR_LeadsToInteriorNode:
break; }
Result = CR_LeadsToInteriorNode;
ChainedNodesInPattern.push_back(User);
InteriorChainedNodes.push_back(User);
continue;
}
return Result;
}
static SDValue
HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
SelectionDAG *CurDAG) {
SmallVector<SDNode*, 3> InteriorChainedNodes;
for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
InteriorChainedNodes) == CR_InducesCycle)
return SDValue(); }
SmallVector<SDValue, 3> InputChains;
for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
SDNode *N = ChainNodesMatched[i];
if (N->getOpcode() != ISD::TokenFactor) {
if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
continue;
SDValue InChain = ChainNodesMatched[i]->getOperand(0);
assert(InChain.getValueType() == MVT::Other && "Not a chain");
InputChains.push_back(InChain);
continue;
}
for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) {
if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
N->getOperand(op).getNode()))
InputChains.push_back(N->getOperand(op));
}
}
SDValue Res;
if (InputChains.size() == 1)
return InputChains[0];
return CurDAG->getNode(ISD::TokenFactor, ChainNodesMatched[0]->getDebugLoc(),
MVT::Other, &InputChains[0], InputChains.size());
}
SDNode *SelectionDAGISel::
MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo) {
int OldGlueResultNo = -1, OldChainResultNo = -1;
unsigned NTMNumResults = Node->getNumValues();
if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
OldGlueResultNo = NTMNumResults-1;
if (NTMNumResults != 1 &&
Node->getValueType(NTMNumResults-2) == MVT::Other)
OldChainResultNo = NTMNumResults-2;
} else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
OldChainResultNo = NTMNumResults-1;
SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops, NumOps);
if (Res == Node) {
Res->setNodeId(-1);
}
unsigned ResNumResults = Res->getNumValues();
if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
(unsigned)OldGlueResultNo != ResNumResults-1)
CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo),
SDValue(Res, ResNumResults-1));
if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
--ResNumResults;
if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
(unsigned)OldChainResultNo != ResNumResults-1)
CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo),
SDValue(Res, ResNumResults-1));
if (Res != Node)
CurDAG->ReplaceAllUsesWith(Node, Res);
return Res;
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N,
const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) {
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
return N == RecordedNodes[RecNo].first;
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
const SelectionDAGISel &SDISel) {
return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
const SelectionDAGISel &SDISel, SDNode *N) {
return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDNode *N) {
uint16_t Opc = MatcherTable[MatcherIndex++];
Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
return N->getOpcode() == Opc;
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N, const TargetLowering &TLI) {
MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
if (N.getValueType() == VT) return true;
return VT == MVT::iPTR && N.getValueType() == TLI.getPointerTy();
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N, const TargetLowering &TLI,
unsigned ChildNo) {
if (ChildNo >= N.getNumOperands())
return false; return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI);
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N) {
return cast<CondCodeSDNode>(N)->get() ==
(ISD::CondCode)MatcherTable[MatcherIndex++];
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N, const TargetLowering &TLI) {
MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
if (cast<VTSDNode>(N)->getVT() == VT)
return true;
return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI.getPointerTy();
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N) {
int64_t Val = MatcherTable[MatcherIndex++];
if (Val & 128)
Val = GetVBR(Val, MatcherTable, MatcherIndex);
ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
return C != 0 && C->getSExtValue() == Val;
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N, const SelectionDAGISel &SDISel) {
int64_t Val = MatcherTable[MatcherIndex++];
if (Val & 128)
Val = GetVBR(Val, MatcherTable, MatcherIndex);
if (N->getOpcode() != ISD::AND) return false;
ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
return C != 0 && SDISel.CheckAndMask(N.getOperand(0), C, Val);
}
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N, const SelectionDAGISel &SDISel) {
int64_t Val = MatcherTable[MatcherIndex++];
if (Val & 128)
Val = GetVBR(Val, MatcherTable, MatcherIndex);
if (N->getOpcode() != ISD::OR) return false;
ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
return C != 0 && SDISel.CheckOrMask(N.getOperand(0), C, Val);
}
static unsigned IsPredicateKnownToFail(const unsigned char *Table,
unsigned Index, SDValue N,
bool &Result,
const SelectionDAGISel &SDISel,
SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) {
switch (Table[Index++]) {
default:
Result = false;
return Index-1; case SelectionDAGISel::OPC_CheckSame:
Result = !::CheckSame(Table, Index, N, RecordedNodes);
return Index;
case SelectionDAGISel::OPC_CheckPatternPredicate:
Result = !::CheckPatternPredicate(Table, Index, SDISel);
return Index;
case SelectionDAGISel::OPC_CheckPredicate:
Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
return Index;
case SelectionDAGISel::OPC_CheckOpcode:
Result = !::CheckOpcode(Table, Index, N.getNode());
return Index;
case SelectionDAGISel::OPC_CheckType:
Result = !::CheckType(Table, Index, N, SDISel.TLI);
return Index;
case SelectionDAGISel::OPC_CheckChild0Type:
case SelectionDAGISel::OPC_CheckChild1Type:
case SelectionDAGISel::OPC_CheckChild2Type:
case SelectionDAGISel::OPC_CheckChild3Type:
case SelectionDAGISel::OPC_CheckChild4Type:
case SelectionDAGISel::OPC_CheckChild5Type:
case SelectionDAGISel::OPC_CheckChild6Type:
case SelectionDAGISel::OPC_CheckChild7Type:
Result = !::CheckChildType(Table, Index, N, SDISel.TLI,
Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Type);
return Index;
case SelectionDAGISel::OPC_CheckCondCode:
Result = !::CheckCondCode(Table, Index, N);
return Index;
case SelectionDAGISel::OPC_CheckValueType:
Result = !::CheckValueType(Table, Index, N, SDISel.TLI);
return Index;
case SelectionDAGISel::OPC_CheckInteger:
Result = !::CheckInteger(Table, Index, N);
return Index;
case SelectionDAGISel::OPC_CheckAndImm:
Result = !::CheckAndImm(Table, Index, N, SDISel);
return Index;
case SelectionDAGISel::OPC_CheckOrImm:
Result = !::CheckOrImm(Table, Index, N, SDISel);
return Index;
}
}
namespace {
struct MatchScope {
unsigned FailIndex;
SmallVector<SDValue, 4> NodeStack;
unsigned NumRecordedNodes;
unsigned NumMatchedMemRefs;
SDValue InputChain, InputGlue;
bool HasChainNodesMatched, HasGlueResultNodesMatched;
};
}
SDNode *SelectionDAGISel::
SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
unsigned TableSize) {
switch (NodeToMatch->getOpcode()) {
default:
break;
case ISD::EntryToken: case ISD::BasicBlock:
case ISD::Register:
case ISD::RegisterMask:
case ISD::HANDLENODE:
case ISD::MDNODE_SDNODE:
case ISD::TargetConstant:
case ISD::TargetConstantFP:
case ISD::TargetConstantPool:
case ISD::TargetFrameIndex:
case ISD::TargetExternalSymbol:
case ISD::TargetBlockAddress:
case ISD::TargetJumpTable:
case ISD::TargetGlobalTLSAddress:
case ISD::TargetGlobalAddress:
case ISD::TokenFactor:
case ISD::CopyFromReg:
case ISD::CopyToReg:
case ISD::EH_LABEL:
case ISD::LIFETIME_START:
case ISD::LIFETIME_END:
NodeToMatch->setNodeId(-1); return 0;
case ISD::AssertSext:
case ISD::AssertZext:
CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
NodeToMatch->getOperand(0));
return 0;
case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
case ISD::UNDEF: return Select_UNDEF(NodeToMatch);
}
assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
SmallVector<SDValue, 8> NodeStack;
SDValue N = SDValue(NodeToMatch, 0);
NodeStack.push_back(N);
SmallVector<MatchScope, 8> MatchScopes;
SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
SDValue InputChain, InputGlue;
SmallVector<SDNode*, 3> ChainNodesMatched;
SmallVector<SDNode*, 3> GlueResultNodesMatched;
DEBUG(errs() << "ISEL: Starting pattern match on root node: ";
NodeToMatch->dump(CurDAG);
errs() << '\n');
unsigned MatcherIndex = 0;
if (!OpcodeOffset.empty()) {
if (N.getOpcode() < OpcodeOffset.size())
MatcherIndex = OpcodeOffset[N.getOpcode()];
DEBUG(errs() << " Initial Opcode index to " << MatcherIndex << "\n");
} else if (MatcherTable[0] == OPC_SwitchOpcode) {
unsigned Idx = 1;
while (1) {
unsigned CaseSize = MatcherTable[Idx++];
if (CaseSize & 128)
CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
if (CaseSize == 0) break;
uint16_t Opc = MatcherTable[Idx++];
Opc |= (unsigned short)MatcherTable[Idx++] << 8;
if (Opc >= OpcodeOffset.size())
OpcodeOffset.resize((Opc+1)*2);
OpcodeOffset[Opc] = Idx;
Idx += CaseSize;
}
if (N.getOpcode() < OpcodeOffset.size())
MatcherIndex = OpcodeOffset[N.getOpcode()];
}
while (1) {
assert(MatcherIndex < TableSize && "Invalid index");
#ifndef NDEBUG
unsigned CurrentOpcodeIndex = MatcherIndex;
#endif
BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
switch (Opcode) {
case OPC_Scope: {
unsigned FailIndex;
while (1) {
unsigned NumToSkip = MatcherTable[MatcherIndex++];
if (NumToSkip & 128)
NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
if (NumToSkip == 0) {
FailIndex = 0;
break;
}
FailIndex = MatcherIndex+NumToSkip;
unsigned MatcherIndexOfPredicate = MatcherIndex;
(void)MatcherIndexOfPredicate;
bool Result;
MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
Result, *this, RecordedNodes);
if (!Result)
break;
DEBUG(errs() << " Skipped scope entry (due to false predicate) at "
<< "index " << MatcherIndexOfPredicate
<< ", continuing at " << FailIndex << "\n");
++NumDAGIselRetries;
MatcherIndex = FailIndex;
}
if (FailIndex == 0) break;
MatchScope NewEntry;
NewEntry.FailIndex = FailIndex;
NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
NewEntry.NumRecordedNodes = RecordedNodes.size();
NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
NewEntry.InputChain = InputChain;
NewEntry.InputGlue = InputGlue;
NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
NewEntry.HasGlueResultNodesMatched = !GlueResultNodesMatched.empty();
MatchScopes.push_back(NewEntry);
continue;
}
case OPC_RecordNode: {
SDNode *Parent = 0;
if (NodeStack.size() > 1)
Parent = NodeStack[NodeStack.size()-2].getNode();
RecordedNodes.push_back(std::make_pair(N, Parent));
continue;
}
case OPC_RecordChild0: case OPC_RecordChild1:
case OPC_RecordChild2: case OPC_RecordChild3:
case OPC_RecordChild4: case OPC_RecordChild5:
case OPC_RecordChild6: case OPC_RecordChild7: {
unsigned ChildNo = Opcode-OPC_RecordChild0;
if (ChildNo >= N.getNumOperands())
break;
RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
N.getNode()));
continue;
}
case OPC_RecordMemRef:
MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
continue;
case OPC_CaptureGlueInput:
if (N->getNumOperands() != 0 &&
N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
InputGlue = N->getOperand(N->getNumOperands()-1);
continue;
case OPC_MoveChild: {
unsigned ChildNo = MatcherTable[MatcherIndex++];
if (ChildNo >= N.getNumOperands())
break; N = N.getOperand(ChildNo);
NodeStack.push_back(N);
continue;
}
case OPC_MoveParent:
NodeStack.pop_back();
assert(!NodeStack.empty() && "Node stack imbalance!");
N = NodeStack.back();
continue;
case OPC_CheckSame:
if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
continue;
case OPC_CheckPatternPredicate:
if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break;
continue;
case OPC_CheckPredicate:
if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
N.getNode()))
break;
continue;
case OPC_CheckComplexPat: {
unsigned CPNum = MatcherTable[MatcherIndex++];
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
RecordedNodes[RecNo].first, CPNum,
RecordedNodes))
break;
continue;
}
case OPC_CheckOpcode:
if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
continue;
case OPC_CheckType:
if (!::CheckType(MatcherTable, MatcherIndex, N, TLI)) break;
continue;
case OPC_SwitchOpcode: {
unsigned CurNodeOpcode = N.getOpcode();
unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
unsigned CaseSize;
while (1) {
CaseSize = MatcherTable[MatcherIndex++];
if (CaseSize & 128)
CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
if (CaseSize == 0) break;
uint16_t Opc = MatcherTable[MatcherIndex++];
Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
if (CurNodeOpcode == Opc)
break;
MatcherIndex += CaseSize;
}
if (CaseSize == 0) break;
DEBUG(errs() << " OpcodeSwitch from " << SwitchStart
<< " to " << MatcherIndex << "\n");
continue;
}
case OPC_SwitchType: {
MVT CurNodeVT = N.getValueType().getSimpleVT();
unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
unsigned CaseSize;
while (1) {
CaseSize = MatcherTable[MatcherIndex++];
if (CaseSize & 128)
CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
if (CaseSize == 0) break;
MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
if (CaseVT == MVT::iPTR)
CaseVT = TLI.getPointerTy();
if (CurNodeVT == CaseVT)
break;
MatcherIndex += CaseSize;
}
if (CaseSize == 0) break;
DEBUG(errs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString()
<< "] from " << SwitchStart << " to " << MatcherIndex<<'\n');
continue;
}
case OPC_CheckChild0Type: case OPC_CheckChild1Type:
case OPC_CheckChild2Type: case OPC_CheckChild3Type:
case OPC_CheckChild4Type: case OPC_CheckChild5Type:
case OPC_CheckChild6Type: case OPC_CheckChild7Type:
if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI,
Opcode-OPC_CheckChild0Type))
break;
continue;
case OPC_CheckCondCode:
if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
continue;
case OPC_CheckValueType:
if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI)) break;
continue;
case OPC_CheckInteger:
if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
continue;
case OPC_CheckAndImm:
if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
continue;
case OPC_CheckOrImm:
if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
continue;
case OPC_CheckFoldableChainNode: {
assert(NodeStack.size() != 1 && "No parent node");
bool HasMultipleUses = false;
for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
if (!NodeStack[i].hasOneUse()) {
HasMultipleUses = true;
break;
}
if (HasMultipleUses) break;
if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
NodeToMatch) ||
!IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
NodeToMatch, OptLevel,
true))
break;
continue;
}
case OPC_EmitInteger: {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
int64_t Val = MatcherTable[MatcherIndex++];
if (Val & 128)
Val = GetVBR(Val, MatcherTable, MatcherIndex);
RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
CurDAG->getTargetConstant(Val, VT), (SDNode*)0));
continue;
}
case OPC_EmitRegister: {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
unsigned RegNo = MatcherTable[MatcherIndex++];
RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
CurDAG->getRegister(RegNo, VT), (SDNode*)0));
continue;
}
case OPC_EmitRegister2: {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
unsigned RegNo = MatcherTable[MatcherIndex++];
RegNo |= MatcherTable[MatcherIndex++] << 8;
RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
CurDAG->getRegister(RegNo, VT), (SDNode*)0));
continue;
}
case OPC_EmitConvertToTarget: {
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
SDValue Imm = RecordedNodes[RecNo].first;
if (Imm->getOpcode() == ISD::Constant) {
int64_t Val = cast<ConstantSDNode>(Imm)->getZExtValue();
Imm = CurDAG->getTargetConstant(Val, Imm.getValueType());
} else if (Imm->getOpcode() == ISD::ConstantFP) {
const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
Imm = CurDAG->getTargetConstantFP(*Val, Imm.getValueType());
}
RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
continue;
}
case OPC_EmitMergeInputChains1_0: case OPC_EmitMergeInputChains1_1: { assert(InputChain.getNode() == 0 &&
"EmitMergeInputChains should be the first chain producing node");
assert(ChainNodesMatched.empty() &&
"Should only have one EmitMergeInputChains per match");
unsigned RecNo = Opcode == OPC_EmitMergeInputChains1_1;
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
if (ChainNodesMatched.back() != NodeToMatch &&
!RecordedNodes[RecNo].first.hasOneUse()) {
ChainNodesMatched.clear();
break;
}
InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
if (InputChain.getNode() == 0)
break; continue;
}
case OPC_EmitMergeInputChains: {
assert(InputChain.getNode() == 0 &&
"EmitMergeInputChains should be the first chain producing node");
unsigned NumChains = MatcherTable[MatcherIndex++];
assert(NumChains != 0 && "Can't TF zero chains");
assert(ChainNodesMatched.empty() &&
"Should only have one EmitMergeInputChains per match");
for (unsigned i = 0; i != NumChains; ++i) {
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
if (ChainNodesMatched.back() != NodeToMatch &&
!RecordedNodes[RecNo].first.hasOneUse()) {
ChainNodesMatched.clear();
break;
}
}
if (ChainNodesMatched.empty())
break;
InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
if (InputChain.getNode() == 0)
break;
continue;
}
case OPC_EmitCopyToReg: {
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
unsigned DestPhysReg = MatcherTable[MatcherIndex++];
if (InputChain.getNode() == 0)
InputChain = CurDAG->getEntryNode();
InputChain = CurDAG->getCopyToReg(InputChain, NodeToMatch->getDebugLoc(),
DestPhysReg, RecordedNodes[RecNo].first,
InputGlue);
InputGlue = InputChain.getValue(1);
continue;
}
case OPC_EmitNodeXForm: {
unsigned XFormNo = MatcherTable[MatcherIndex++];
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, (SDNode*) 0));
continue;
}
case OPC_EmitNode:
case OPC_MorphNodeTo: {
uint16_t TargetOpc = MatcherTable[MatcherIndex++];
TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
unsigned NumVTs = MatcherTable[MatcherIndex++];
SmallVector<EVT, 4> VTs;
for (unsigned i = 0; i != NumVTs; ++i) {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
if (VT == MVT::iPTR) VT = TLI.getPointerTy().SimpleTy;
VTs.push_back(VT);
}
if (EmitNodeInfo & OPFL_Chain)
VTs.push_back(MVT::Other);
if (EmitNodeInfo & OPFL_GlueOutput)
VTs.push_back(MVT::Glue);
SDVTList VTList;
if (VTs.size() == 1)
VTList = CurDAG->getVTList(VTs[0]);
else if (VTs.size() == 2)
VTList = CurDAG->getVTList(VTs[0], VTs[1]);
else
VTList = CurDAG->getVTList(VTs.data(), VTs.size());
unsigned NumOps = MatcherTable[MatcherIndex++];
SmallVector<SDValue, 8> Ops;
for (unsigned i = 0; i != NumOps; ++i) {
unsigned RecNo = MatcherTable[MatcherIndex++];
if (RecNo & 128)
RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
Ops.push_back(RecordedNodes[RecNo].first);
}
if (EmitNodeInfo & OPFL_VariadicInfo) {
unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
"Invalid variadic node");
for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
i != e; ++i) {
SDValue V = NodeToMatch->getOperand(i);
if (V.getValueType() == MVT::Glue) break;
Ops.push_back(V);
}
}
if (EmitNodeInfo & OPFL_Chain)
Ops.push_back(InputChain);
if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != 0)
Ops.push_back(InputGlue);
SDNode *Res = 0;
if (Opcode != OPC_MorphNodeTo) {
Res = CurDAG->getMachineNode(TargetOpc, NodeToMatch->getDebugLoc(),
VTList, Ops.data(), Ops.size());
for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
(SDNode*) 0));
}
} else if (NodeToMatch->getOpcode() != ISD::DELETED_NODE) {
Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops.data(), Ops.size(),
EmitNodeInfo);
} else {
DEBUG(dbgs() << "Node was eliminated by CSE\n");
return 0;
}
if (EmitNodeInfo & OPFL_GlueOutput) {
InputGlue = SDValue(Res, VTs.size()-1);
if (EmitNodeInfo & OPFL_Chain)
InputChain = SDValue(Res, VTs.size()-2);
} else if (EmitNodeInfo & OPFL_Chain)
InputChain = SDValue(Res, VTs.size()-1);
if (EmitNodeInfo & OPFL_MemRefs) {
const MCInstrDesc &MCID = TM.getInstrInfo()->get(TargetOpc);
bool mayLoad = MCID.mayLoad();
bool mayStore = MCID.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(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 + NumMemRefs);
}
DEBUG(errs() << " "
<< (Opcode == OPC_MorphNodeTo ? "Morphed" : "Created")
<< " node: "; Res->dump(CurDAG); errs() << "\n");
if (Opcode == OPC_MorphNodeTo) {
UpdateChainsAndGlue(NodeToMatch, InputChain, ChainNodesMatched,
InputGlue, GlueResultNodesMatched, true);
return Res;
}
continue;
}
case OPC_MarkGlueResults: {
unsigned NumNodes = MatcherTable[MatcherIndex++];
for (unsigned i = 0; i != NumNodes; ++i) {
unsigned RecNo = MatcherTable[MatcherIndex++];
if (RecNo & 128)
RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
GlueResultNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
}
continue;
}
case OPC_CompleteMatch: {
unsigned NumResults = MatcherTable[MatcherIndex++];
for (unsigned i = 0; i != NumResults; ++i) {
unsigned ResSlot = MatcherTable[MatcherIndex++];
if (ResSlot & 128)
ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
assert(ResSlot < RecordedNodes.size() && "Invalid CheckSame");
SDValue Res = RecordedNodes[ResSlot].first;
assert(i < NodeToMatch->getNumValues() &&
NodeToMatch->getValueType(i) != MVT::Other &&
NodeToMatch->getValueType(i) != MVT::Glue &&
"Invalid number of results to complete!");
assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
NodeToMatch->getValueType(i) == MVT::iPTR ||
Res.getValueType() == MVT::iPTR ||
NodeToMatch->getValueType(i).getSizeInBits() ==
Res.getValueType().getSizeInBits()) &&
"invalid replacement");
CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res);
}
if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) == MVT::Glue)
GlueResultNodesMatched.push_back(NodeToMatch);
UpdateChainsAndGlue(NodeToMatch, InputChain, ChainNodesMatched,
InputGlue, GlueResultNodesMatched, false);
assert(NodeToMatch->use_empty() &&
"Didn't replace all uses of the node?");
return 0;
}
}
DEBUG(errs() << " Match failed at index " << CurrentOpcodeIndex << "\n");
++NumDAGIselRetries;
while (1) {
if (MatchScopes.empty()) {
CannotYetSelect(NodeToMatch);
return 0;
}
MatchScope &LastScope = MatchScopes.back();
RecordedNodes.resize(LastScope.NumRecordedNodes);
NodeStack.clear();
NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
N = NodeStack.back();
if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
MatcherIndex = LastScope.FailIndex;
DEBUG(errs() << " Continuing at " << MatcherIndex << "\n");
InputChain = LastScope.InputChain;
InputGlue = LastScope.InputGlue;
if (!LastScope.HasChainNodesMatched)
ChainNodesMatched.clear();
if (!LastScope.HasGlueResultNodesMatched)
GlueResultNodesMatched.clear();
unsigned NumToSkip = MatcherTable[MatcherIndex++];
if (NumToSkip & 128)
NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
if (NumToSkip != 0) {
LastScope.FailIndex = MatcherIndex+NumToSkip;
break;
}
MatchScopes.pop_back();
}
}
}
void SelectionDAGISel::CannotYetSelect(SDNode *N) {
std::string msg;
raw_string_ostream Msg(msg);
Msg << "Cannot select: ";
if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
N->getOpcode() != ISD::INTRINSIC_VOID) {
N->printrFull(Msg, CurDAG);
Msg << "\nIn function: " << MF->getName();
} else {
bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
unsigned iid =
cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue();
if (iid < Intrinsic::num_intrinsics)
Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid);
else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
Msg << "target intrinsic %" << TII->getName(iid);
else
Msg << "unknown intrinsic #" << iid;
}
report_fatal_error(Msg.str());
}
char SelectionDAGISel::ID = 0;