SelectionDAGISel.cpp [plain text]
#define DEBUG_TYPE "isel"
#include "ScheduleDAGSDNodes.h"
#include "SelectionDAGBuilder.h"
#include "FunctionLoweringInfo.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/DebugInfo.h"
#include "llvm/Constants.h"
#include "llvm/CallingConv.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.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/CodeGen/FastISel.h"
#include "llvm/CodeGen/GCStrategy.h"
#include "llvm/CodeGen/GCMetadata.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionAnalysis.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineJumpTableInfo.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/DwarfWriter.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetFrameInfo.h"
#include "llvm/Target/TargetIntrinsicInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.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 "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
#include <algorithm>
using namespace llvm;
STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
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>
SchedLiveInCopies("schedule-livein-copies", cl::Hidden,
cl::desc("Schedule copies of livein registers"),
cl::init(false));
#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)
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);
}
}
MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
MachineBasicBlock *MBB,
DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) const {
#ifndef NDEBUG
dbgs() << "If a target marks an instruction with "
"'usesCustomInserter', it must implement "
"TargetLowering::EmitInstrWithCustomInserter!";
#endif
llvm_unreachable(0);
return 0;
}
static void EmitLiveInCopy(MachineBasicBlock *MBB,
MachineBasicBlock::iterator &InsertPos,
unsigned VirtReg, unsigned PhysReg,
const TargetRegisterClass *RC,
DenseMap<MachineInstr*, unsigned> &CopyRegMap,
const MachineRegisterInfo &MRI,
const TargetRegisterInfo &TRI,
const TargetInstrInfo &TII) {
unsigned NumUses = 0;
MachineInstr *UseMI = NULL;
for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(VirtReg),
UE = MRI.use_end(); UI != UE; ++UI) {
UseMI = &*UI;
if (++NumUses > 1)
break;
}
bool Coalesced = false;
unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
if (NumUses == 1 &&
TII.isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
TargetRegisterInfo::isVirtualRegister(DstReg)) {
VirtReg = DstReg;
Coalesced = true;
}
MachineBasicBlock::iterator Pos = InsertPos;
while (Pos != MBB->begin()) {
MachineInstr *PrevMI = prior(Pos);
DenseMap<MachineInstr*, unsigned>::iterator RI = CopyRegMap.find(PrevMI);
unsigned CopyDstReg = (RI == CopyRegMap.end()) ? 0 : RI->second;
if (CopyDstReg && !TRI.regsOverlap(CopyDstReg, PhysReg))
break; --Pos;
}
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);
}
}
static void EmitLiveInCopies(MachineBasicBlock *EntryMBB,
const MachineRegisterInfo &MRI,
const TargetRegisterInfo &TRI,
const TargetInstrInfo &TII) {
if (SchedLiveInCopies) {
DenseMap<MachineInstr*, unsigned> CopyRegMap;
MachineBasicBlock::iterator InsertPos = EntryMBB->begin();
for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(),
E = MRI.livein_end(); LI != E; ++LI)
if (LI->second) {
const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
EmitLiveInCopy(EntryMBB, InsertPos, LI->second, LI->first,
RC, CopyRegMap, MRI, TRI, TII);
}
} else {
for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(),
E = MRI.livein_end(); LI != E; ++LI)
if (LI->second) {
const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
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::SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL) :
MachineFunctionPass(&ID), TM(tm), TLI(*tm.getTargetLowering()),
FuncInfo(new FunctionLoweringInfo(TLI)),
CurDAG(new SelectionDAG(TLI, *FuncInfo)),
SDB(new SelectionDAGBuilder(*CurDAG, TLI, *FuncInfo, OL)),
GFI(),
OptLevel(OL),
DAGSize(0)
{}
SelectionDAGISel::~SelectionDAGISel() {
delete SDB;
delete CurDAG;
delete FuncInfo;
}
unsigned SelectionDAGISel::MakeReg(EVT VT) {
return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
}
void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<AliasAnalysis>();
AU.addPreserved<AliasAnalysis>();
AU.addRequired<GCModuleInfo>();
AU.addPreserved<GCModuleInfo>();
AU.addRequired<DwarfWriter>();
AU.addPreserved<DwarfWriter>();
MachineFunctionPass::getAnalysisUsage(AU);
}
static bool FunctionCallsSetJmp(const Function *F) {
const Module *M = F->getParent();
static const char *ReturnsTwiceFns[] = {
"setjmp",
"sigsetjmp",
"setjmp_syscall",
"savectx",
"qsetjmp",
"vfork",
"getcontext"
};
#define NUM_RETURNS_TWICE_FNS sizeof(ReturnsTwiceFns) / sizeof(const char *)
for (unsigned I = 0; I < NUM_RETURNS_TWICE_FNS; ++I)
if (const Function *Callee = M->getFunction(ReturnsTwiceFns[I])) {
if (!Callee->use_empty())
for (Value::use_const_iterator
I = Callee->use_begin(), E = Callee->use_end();
I != E; ++I)
if (const CallInst *CI = dyn_cast<CallInst>(I))
if (CI->getParent()->getParent() == F)
return true;
}
return false;
#undef NUM_RETURNS_TWICE_FNS
}
bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
Function &Fn = *mf.getFunction();
assert((!EnableFastISelVerbose || EnableFastISel) &&
"-fast-isel-verbose requires -fast-isel");
assert((!EnableFastISelAbort || EnableFastISel) &&
"-fast-isel-abort requires -fast-isel");
AA = &getAnalysis<AliasAnalysis>();
MF = &mf;
const TargetInstrInfo &TII = *TM.getInstrInfo();
const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
if (Fn.hasGC())
GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn);
else
GFI = 0;
RegInfo = &MF->getRegInfo();
DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>();
DwarfWriter *DW = getAnalysisIfAvailable<DwarfWriter>();
CurDAG->init(*MF, MMI, DW);
FuncInfo->set(Fn, *MF, EnableFastISel);
SDB->init(GFI, *AA);
for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator()))
FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
SelectAllBasicBlocks(Fn, *MF, MMI, DW, TII);
MachineBasicBlock *EntryMBB = MF->begin();
EmitLiveInCopies(EntryMBB, *RegInfo, TRI, TII);
for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(),
E = RegInfo->livein_end(); I != E; ++I)
MF->begin()->addLiveIn(I->first);
#ifndef NDEBUG
assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() &&
"Not all catch info was assigned to a landing pad!");
#endif
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);
if (RegInfo->hasOneNonDBGUse(LDI->second)) {
MachineInstr *CopyUseMI = NULL;
for (MachineRegisterInfo::use_iterator
UI = RegInfo->use_begin(LDI->second),
UE = RegInfo->use_end(); UI != UE; ++UI) {
MachineInstr *UseMI = &*UI;
if (UseMI->isDebugValue()) continue;
unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
if (TII.isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
SrcReg == LDI->second && !SrcSubReg && !DstSubReg)
CopyUseMI = UseMI;
}
if (CopyUseMI) {
MachineInstr *NewMI =
BuildMI(*MF, CopyUseMI->getDebugLoc(),
TII.get(TargetOpcode::DBG_VALUE))
.addReg(CopyUseMI->getOperand(0).getReg(), RegState::Debug)
.addImm(Offset).addMetadata(Variable);
EntryMBB->insertAfter(CopyUseMI, 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 TargetInstrDesc &TID = TM.getInstrInfo()->get(II->getOpcode());
if ((II->isInlineAsm() && II->getOperand(1).getImm()) ||
(TID.isCall() && !TID.isReturn())) {
MFI->setHasCalls(true);
goto done;
}
}
}
done:;
}
MF->setCallsSetJmp(FunctionCallsSetJmp(&Fn));
FuncInfo->clear();
return true;
}
static void SetDebugLoc(Instruction *I, SelectionDAGBuilder *SDB,
FastISel *FastIS, MachineFunction *MF) {
DebugLoc DL = I->getDebugLoc();
if (DL.isUnknown()) return;
SDB->setCurDebugLoc(DL);
if (FastIS)
FastIS->setCurDebugLoc(DL);
if (MF->getDefaultDebugLoc().isUnknown())
MF->setDefaultDebugLoc(DL);
}
static void ResetDebugLoc(SelectionDAGBuilder *SDB, FastISel *FastIS) {
SDB->setCurDebugLoc(DebugLoc());
if (FastIS)
FastIS->setCurDebugLoc(DebugLoc());
}
void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB,
BasicBlock::iterator Begin,
BasicBlock::iterator End,
bool &HadTailCall) {
SDB->setCurrentBasicBlock(BB);
for (BasicBlock::iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
SetDebugLoc(I, SDB, 0, MF);
if (!isa<TerminatorInst>(I)) {
SDB->visit(*I);
ResetDebugLoc(SDB, 0);
}
}
if (!SDB->HasTailCall) {
for (BasicBlock::iterator I = Begin; I != End; ++I)
if (!isa<PHINode>(I) && !isa<InvokeInst>(I))
SDB->CopyToExportRegsIfNeeded(I);
if (End == LLVMBB->end()) {
HandlePHINodesInSuccessorBlocks(LLVMBB);
SetDebugLoc(LLVMBB->getTerminator(), SDB, 0, MF);
SDB->visit(*LLVMBB->getTerminator());
ResetDebugLoc(SDB, 0);
}
}
CurDAG->setRoot(SDB->getControlRoot());
CodeGenAndEmitDAG();
HadTailCall = SDB->HasTailCall;
SDB->clear();
}
namespace {
class SDOPsWorkListRemover : public SelectionDAG::DAGUpdateListener {
SmallVector<SDNode*, 128> &Worklist;
SmallPtrSet<SDNode*, 128> &InWorklist;
public:
SDOPsWorkListRemover(SmallVector<SDNode*, 128> &wl,
SmallPtrSet<SDNode*, 128> &inwl)
: Worklist(wl), InWorklist(inwl) {}
void RemoveFromWorklist(SDNode *N) {
if (!InWorklist.erase(N)) return;
SmallVector<SDNode*, 128>::iterator I =
std::find(Worklist.begin(), Worklist.end(), N);
assert(I != Worklist.end() && "Not in worklist");
*I = Worklist.back();
Worklist.pop_back();
}
virtual void NodeDeleted(SDNode *N, SDNode *E) {
RemoveFromWorklist(N);
}
virtual void NodeUpdated(SDNode *N) {
}
};
}
static bool TrivialTruncElim(SDValue Op,
TargetLowering::TargetLoweringOpt &TLO) {
SDValue N0 = Op.getOperand(0);
EVT VT = Op.getValueType();
if ((N0.getOpcode() == ISD::ZERO_EXTEND ||
N0.getOpcode() == ISD::SIGN_EXTEND ||
N0.getOpcode() == ISD::ANY_EXTEND) &&
N0.getOperand(0).getValueType() == VT) {
return TLO.CombineTo(Op, N0.getOperand(0));
}
return false;
}
void SelectionDAGISel::ShrinkDemandedOps() {
SmallVector<SDNode*, 128> Worklist;
SmallPtrSet<SDNode*, 128> InWorklist;
Worklist.reserve(CurDAG->allnodes_size());
for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
E = CurDAG->allnodes_end(); I != E; ++I) {
Worklist.push_back(I);
InWorklist.insert(I);
}
TargetLowering::TargetLoweringOpt TLO(*CurDAG, true, true, true);
while (!Worklist.empty()) {
SDNode *N = Worklist.pop_back_val();
InWorklist.erase(N);
if (N->use_empty() && N != CurDAG->getRoot().getNode()) {
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
if (InWorklist.insert(N->getOperand(i).getNode()))
Worklist.push_back(N->getOperand(i).getNode());
CurDAG->DeleteNode(N);
continue;
}
if (N->getNumValues() != 1 ||
!N->getValueType(0).isSimple() || !N->getValueType(0).isInteger())
continue;
unsigned BitWidth = N->getValueType(0).getScalarType().getSizeInBits();
APInt Demanded = APInt::getAllOnesValue(BitWidth);
APInt KnownZero, KnownOne;
if (!TLI.SimplifyDemandedBits(SDValue(N, 0), Demanded,
KnownZero, KnownOne, TLO) &&
(N->getOpcode() != ISD::TRUNCATE ||
!TrivialTruncElim(SDValue(N, 0), TLO)))
continue;
assert(!InWorklist.count(N) && "Already in worklist");
Worklist.push_back(N);
InWorklist.insert(N);
DEBUG(errs() << "\nShrinkDemandedOps replacing ";
TLO.Old.getNode()->dump(CurDAG);
errs() << "\nWith: ";
TLO.New.getNode()->dump(CurDAG);
errs() << '\n');
if (InWorklist.insert(TLO.New.getNode()))
Worklist.push_back(TLO.New.getNode());
SDOPsWorkListRemover DeadNodes(Worklist, InWorklist);
CurDAG->ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, &DeadNodes);
if (!TLO.Old.getNode()->use_empty()) continue;
for (unsigned i = 0, e = TLO.Old.getNode()->getNumOperands();
i != e; ++i) {
SDNode *OpNode = TLO.Old.getNode()->getOperand(i).getNode();
if (OpNode->hasOneUse()) {
DeadNodes.RemoveFromWorklist(OpNode);
Worklist.push_back(OpNode);
InWorklist.insert(OpNode);
}
}
DeadNodes.RemoveFromWorklist(TLO.Old.getNode());
CurDAG->DeleteNode(TLO.Old.getNode());
}
}
void SelectionDAGISel::ComputeLiveOutVRegInfo() {
SmallPtrSet<SDNode*, 128> VisitedNodes;
SmallVector<SDNode*, 128> Worklist;
Worklist.push_back(CurDAG->getRoot().getNode());
APInt Mask;
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);
Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits());
CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne);
if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) {
DestReg -= TargetRegisterInfo::FirstVirtualRegister;
if (DestReg >= FuncInfo->LiveOutRegInfo.size())
FuncInfo->LiveOutRegInfo.resize(DestReg+1);
FunctionLoweringInfo::LiveOutInfo &LOI =
FuncInfo->LiveOutRegInfo[DestReg];
LOI.NumSignBits = NumSignBits;
LOI.KnownOne = KnownOne;
LOI.KnownZero = KnownZero;
}
} while (!Worklist.empty());
}
void SelectionDAGISel::CodeGenAndEmitDAG() {
std::string GroupName;
if (TimePassesIsEnabled)
GroupName = "Instruction Selection and Scheduling";
std::string BlockName;
if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
ViewSUnitDAGs)
BlockName = MF->getFunction()->getNameStr() + ":" +
BB->getBasicBlock()->getNameStr();
DEBUG(dbgs() << "Initial selection DAG:\n");
DEBUG(CurDAG->dump());
if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName);
if (TimePassesIsEnabled) {
NamedRegionTimer T("DAG Combining 1", GroupName);
CurDAG->Combine(Unrestricted, *AA, OptLevel);
} else {
CurDAG->Combine(Unrestricted, *AA, OptLevel);
}
DEBUG(dbgs() << "Optimized lowered selection DAG:\n");
DEBUG(CurDAG->dump());
if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " +
BlockName);
bool Changed;
if (TimePassesIsEnabled) {
NamedRegionTimer T("Type Legalization", GroupName);
Changed = CurDAG->LegalizeTypes();
} else {
Changed = CurDAG->LegalizeTypes();
}
DEBUG(dbgs() << "Type-legalized selection DAG:\n");
DEBUG(CurDAG->dump());
if (Changed) {
if (ViewDAGCombineLT)
CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
if (TimePassesIsEnabled) {
NamedRegionTimer T("DAG Combining after legalize types", GroupName);
CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
} else {
CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);
}
DEBUG(dbgs() << "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);
CurDAG->LegalizeTypes();
} else {
CurDAG->LegalizeTypes();
}
if (ViewDAGCombineLT)
CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
if (TimePassesIsEnabled) {
NamedRegionTimer T("DAG Combining after legalize vectors", GroupName);
CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
} else {
CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
}
DEBUG(dbgs() << "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(OptLevel);
} else {
CurDAG->Legalize(OptLevel);
}
DEBUG(dbgs() << "Legalized selection DAG:\n");
DEBUG(CurDAG->dump());
if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName);
if (TimePassesIsEnabled) {
NamedRegionTimer T("DAG Combining 2", GroupName);
CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
} else {
CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);
}
DEBUG(dbgs() << "Optimized legalized selection DAG:\n");
DEBUG(CurDAG->dump());
if (OptLevel != CodeGenOpt::None) {
ShrinkDemandedOps();
ComputeLiveOutVRegInfo();
}
if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName);
if (TimePassesIsEnabled) {
NamedRegionTimer T("Instruction Selection", GroupName);
DoInstructionSelection();
} else {
DoInstructionSelection();
}
DEBUG(dbgs() << "Selected selection DAG:\n");
DEBUG(CurDAG->dump());
if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName);
ScheduleDAGSDNodes *Scheduler = CreateScheduler();
if (TimePassesIsEnabled) {
NamedRegionTimer T("Instruction Scheduling", GroupName);
Scheduler->Run(CurDAG, BB, BB->end());
} else {
Scheduler->Run(CurDAG, BB, BB->end());
}
if (ViewSUnitDAGs) Scheduler->viewGraph();
if (TimePassesIsEnabled) {
NamedRegionTimer T("Instruction Creation", GroupName);
BB = Scheduler->EmitSchedule(&SDB->EdgeMapping);
} else {
BB = Scheduler->EmitSchedule(&SDB->EdgeMapping);
}
if (TimePassesIsEnabled) {
NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName);
delete Scheduler;
} else {
delete Scheduler;
}
}
void SelectionDAGISel::DoInstructionSelection() {
DEBUG(errs() << "===== Instruction selection begins:\n");
PreprocessISelDAG();
{
DAGSize = CurDAG->AssignTopologicalOrder();
HandleSDNode Dummy(CurDAG->getRoot());
ISelPosition = SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode());
++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()) { ISelUpdater ISU(ISelPosition);
CurDAG->RemoveDeadNode(Node, &ISU);
}
}
CurDAG->setRoot(Dummy.getValue());
}
DEBUG(errs() << "===== Instruction selection ends:\n");
PostprocessISelDAG();
CurDAG->RemoveDeadNodes();
}
void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn,
MachineFunction &MF,
MachineModuleInfo *MMI,
DwarfWriter *DW,
const TargetInstrInfo &TII) {
FastISel *FastIS = 0;
if (EnableFastISel)
FastIS = TLI.createFastISel(MF, MMI, DW,
FuncInfo->ValueMap,
FuncInfo->MBBMap,
FuncInfo->StaticAllocaMap
#ifndef NDEBUG
, FuncInfo->CatchInfoLost
#endif
);
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 BI = Begin;
bool SuppressFastISel = false;
if (LLVMBB == &Fn.getEntryBlock()) {
LowerArguments(LLVMBB);
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)
dbgs() << "FastISel skips entry block due to byval argument\n";
SuppressFastISel = true;
break;
}
}
}
if (MMI && BB->isLandingPad()) {
MCSymbol *Label = MMI->addLandingPad(BB);
const TargetInstrDesc &II = TII.get(TargetOpcode::EH_LABEL);
BuildMI(BB, SDB->getCurDebugLoc(), II).addSym(Label);
unsigned Reg = TLI.getExceptionAddressRegister();
if (Reg) BB->addLiveIn(Reg);
Reg = TLI.getExceptionSelectorRegister();
if (Reg) BB->addLiveIn(Reg);
BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
if (Br && Br->isUnconditional()) { BasicBlock::iterator I, E;
for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
if (isa<EHSelectorInst>(I))
break;
if (I == E)
CopyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo);
}
}
if (FastIS && !SuppressFastISel) {
if (LLVMBB == &Fn.getEntryBlock()) {
CurDAG->setRoot(SDB->getControlRoot());
CodeGenAndEmitDAG();
SDB->clear();
}
FastIS->startNewBlock(BB);
for (; BI != End; ++BI) {
if (isa<TerminatorInst>(BI))
if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, FastIS)) {
++NumFastIselFailures;
ResetDebugLoc(SDB, FastIS);
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel miss: ";
BI->dump();
}
assert(!EnableFastISelAbort &&
"FastISel didn't handle a PHI in a successor");
break;
}
SetDebugLoc(BI, SDB, FastIS, &MF);
if (FastIS->SelectInstruction(BI)) {
ResetDebugLoc(SDB, FastIS);
continue;
}
ResetDebugLoc(SDB, FastIS);
if (isa<CallInst>(BI)) {
++NumFastIselFailures;
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel missed call: ";
BI->dump();
}
if (!BI->getType()->isVoidTy()) {
unsigned &R = FuncInfo->ValueMap[BI];
if (!R)
R = FuncInfo->CreateRegForValue(BI);
}
bool HadTailCall = false;
SelectBasicBlock(LLVMBB, BI, llvm::next(BI), HadTailCall);
if (HadTailCall) {
BI = End;
break;
}
FastIS->setCurrentBlock(BB);
continue;
}
if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) {
++NumFastIselFailures;
if (EnableFastISelVerbose || EnableFastISelAbort) {
dbgs() << "FastISel miss: ";
BI->dump();
}
if (EnableFastISelAbort)
llvm_unreachable("FastISel didn't select the entire block");
}
break;
}
}
if (BI != End) {
bool HadTailCall;
SelectBasicBlock(LLVMBB, BI, End, HadTailCall);
}
FinishBasicBlock();
}
delete FastIS;
}
void
SelectionDAGISel::FinishBasicBlock() {
DEBUG(dbgs() << "Target-post-processed machine code:\n");
DEBUG(BB->dump());
DEBUG(dbgs() << "Total amount of phi nodes to update: "
<< SDB->PHINodesToUpdate.size() << "\n");
DEBUG(for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i)
dbgs() << "Node " << i << " : ("
<< SDB->PHINodesToUpdate[i].first
<< ", " << SDB->PHINodesToUpdate[i].second << ")\n");
if (SDB->SwitchCases.empty() &&
SDB->JTCases.empty() &&
SDB->BitTestCases.empty()) {
for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i) {
MachineInstr *PHI = SDB->PHINodesToUpdate[i].first;
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
if (!BB->isSuccessor(PHI->getParent()))
continue;
PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[i].second,
false));
PHI->addOperand(MachineOperand::CreateMBB(BB));
}
SDB->PHINodesToUpdate.clear();
return;
}
for (unsigned i = 0, e = SDB->BitTestCases.size(); i != e; ++i) {
if (!SDB->BitTestCases[i].Emitted) {
BB = SDB->BitTestCases[i].Parent;
SDB->setCurrentBasicBlock(BB);
SDB->visitBitTestHeader(SDB->BitTestCases[i]);
CurDAG->setRoot(SDB->getRoot());
CodeGenAndEmitDAG();
SDB->clear();
}
for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) {
BB = SDB->BitTestCases[i].Cases[j].ThisBB;
SDB->setCurrentBasicBlock(BB);
if (j+1 != ej)
SDB->visitBitTestCase(SDB->BitTestCases[i].Cases[j+1].ThisBB,
SDB->BitTestCases[i].Reg,
SDB->BitTestCases[i].Cases[j]);
else
SDB->visitBitTestCase(SDB->BitTestCases[i].Default,
SDB->BitTestCases[i].Reg,
SDB->BitTestCases[i].Cases[j]);
CurDAG->setRoot(SDB->getRoot());
CodeGenAndEmitDAG();
SDB->clear();
}
for (unsigned pi = 0, pe = SDB->PHINodesToUpdate.size(); pi != pe; ++pi) {
MachineInstr *PHI = SDB->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(SDB->PHINodesToUpdate[pi].second, false));
PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Parent));
PHI->addOperand(MachineOperand::
CreateReg(SDB->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(SDB->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) {
BB = SDB->JTCases[i].first.HeaderBB;
SDB->setCurrentBasicBlock(BB);
SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first);
CurDAG->setRoot(SDB->getRoot());
CodeGenAndEmitDAG();
SDB->clear();
}
BB = SDB->JTCases[i].second.MBB;
SDB->setCurrentBasicBlock(BB);
SDB->visitJumpTable(SDB->JTCases[i].second);
CurDAG->setRoot(SDB->getRoot());
CodeGenAndEmitDAG();
SDB->clear();
for (unsigned pi = 0, pe = SDB->PHINodesToUpdate.size(); pi != pe; ++pi) {
MachineInstr *PHI = SDB->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(SDB->PHINodesToUpdate[pi].second, false));
PHI->addOperand
(MachineOperand::CreateMBB(SDB->JTCases[i].first.HeaderBB));
}
if (BB->isSuccessor(PHIBB)) {
PHI->addOperand
(MachineOperand::CreateReg(SDB->PHINodesToUpdate[pi].second, false));
PHI->addOperand(MachineOperand::CreateMBB(BB));
}
}
}
SDB->JTCases.clear();
for (unsigned i = 0, e = SDB->PHINodesToUpdate.size(); i != e; ++i) {
MachineInstr *PHI = SDB->PHINodesToUpdate[i].first;
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
if (BB->isSuccessor(PHI->getParent())) {
PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[i].second,
false));
PHI->addOperand(MachineOperand::CreateMBB(BB));
}
}
for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
MachineBasicBlock *ThisBB = BB = SDB->SwitchCases[i].ThisBB;
SDB->setCurrentBasicBlock(BB);
SDB->visitSwitchCase(SDB->SwitchCases[i]);
CurDAG->setRoot(SDB->getRoot());
CodeGenAndEmitDAG();
while ((BB = SDB->SwitchCases[i].TrueBB)) { DenseMap<MachineBasicBlock*, MachineBasicBlock*>::iterator EI =
SDB->EdgeMapping.find(BB);
if (EI != SDB->EdgeMapping.end())
ThisBB = EI->second;
if (ThisBB->isSuccessor(BB)) {
for (MachineBasicBlock::iterator Phi = BB->begin();
Phi != BB->end() && Phi->isPHI();
++Phi) {
for (unsigned pn = 0; ; ++pn) {
assert(pn != SDB->PHINodesToUpdate.size() &&
"Didn't find PHI entry!");
if (SDB->PHINodesToUpdate[pn].first == Phi) {
Phi->addOperand(MachineOperand::
CreateReg(SDB->PHINodesToUpdate[pn].second,
false));
Phi->addOperand(MachineOperand::CreateMBB(ThisBB));
break;
}
}
}
}
if (BB == SDB->SwitchCases[i].FalseBB)
SDB->SwitchCases[i].FalseBB = 0;
SDB->SwitchCases[i].TrueBB = SDB->SwitchCases[i].FalseBB;
SDB->SwitchCases[i].FalseBB = 0;
}
assert(SDB->SwitchCases[i].TrueBB == 0 && SDB->SwitchCases[i].FalseBB == 0);
SDB->clear();
}
SDB->SwitchCases.clear();
SDB->PHINodesToUpdate.clear();
}
ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
if (!Ctor) {
Ctor = ISHeuristic;
RegisterScheduler::setDefault(Ctor);
}
return Ctor(this, OptLevel);
}
ScheduleHazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
return new ScheduleHazardRecognizer();
}
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, NeededMask, 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[0]); Ops.push_back(InOps[1]); Ops.push_back(InOps[2]);
unsigned i = 3, e = InOps.size();
if (InOps[e-1].getValueType() == MVT::Flag)
--e;
while (i != e) {
unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
if ((Flags & 7) != 4 ) {
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)) {
llvm_report_error("Could not match memory address. Inline asm"
" failure!");
}
Ops.push_back(CurDAG->getTargetConstant(4 | (SelOps.size()<< 3),
MVT::i32));
Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
i += 2;
}
}
if (e != InOps.size())
Ops.push_back(InOps.back());
}
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;
}
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,
bool IgnoreChains) const {
if (OptLevel == CodeGenOpt::None) return false;
EVT 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);
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::Flag);
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));
}
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::
UpdateChainsAndFlags(SDNode *NodeToMatch, SDValue InputChain,
const SmallVectorImpl<SDNode*> &ChainNodesMatched,
SDValue InputFlag,
const SmallVectorImpl<SDNode*> &FlagResultNodesMatched,
bool isMorphNodeTo) {
SmallVector<SDNode*, 4> NowDeadNodes;
ISelUpdater ISU(ISelPosition);
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::Flag)
ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain, &ISU);
if (ChainNode->use_empty())
NowDeadNodes.push_back(ChainNode);
}
}
if (InputFlag.getNode() != 0) {
for (unsigned i = 0, e = FlagResultNodesMatched.size(); i != e; ++i) {
SDNode *FRN = FlagResultNodesMatched[i];
if (FRN->getOpcode() == ISD::DELETED_NODE)
continue;
assert(FRN->getValueType(FRN->getNumValues()-1) == MVT::Flag &&
"Doesn't have a flag result");
CurDAG->ReplaceAllUsesOfValueWith(SDValue(FRN, FRN->getNumValues()-1),
InputFlag, &ISU);
if (FRN->use_empty())
NowDeadNodes.push_back(FRN);
}
}
if (!NowDeadNodes.empty())
CurDAG->RemoveDeadNodes(NowDeadNodes, &ISU);
DEBUG(errs() << "ISEL: Match complete!\n");
}
enum ChainResult {
CR_Simple,
CR_InducesCycle,
CR_LeadsToInteriorNode
};
static ChainResult
WalkChainUsers(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;
if (User->getOpcode() == ISD::CopyToReg ||
User->getOpcode() == ISD::CopyFromReg ||
User->getOpcode() == ISD::INLINEASM ||
User->getOpcode() == ISD::EH_LABEL) {
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 OldFlagResultNo = -1, OldChainResultNo = -1;
unsigned NTMNumResults = Node->getNumValues();
if (Node->getValueType(NTMNumResults-1) == MVT::Flag) {
OldFlagResultNo = 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_FlagOutput) && OldFlagResultNo != -1 &&
(unsigned)OldFlagResultNo != ResNumResults-1)
CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldFlagResultNo),
SDValue(Res, ResNumResults-1));
if ((EmitNodeInfo & OPFL_FlagOutput) != 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;
}
ALWAYS_INLINE static bool
CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N, const SmallVectorImpl<SDValue> &RecordedNodes) {
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
return N == RecordedNodes[RecNo];
}
ALWAYS_INLINE static bool
CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SelectionDAGISel &SDISel) {
return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
}
ALWAYS_INLINE static bool
CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SelectionDAGISel &SDISel, SDNode *N) {
return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
}
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;
}
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();
}
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);
}
ALWAYS_INLINE static bool
CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N) {
return cast<CondCodeSDNode>(N)->get() ==
(ISD::CondCode)MatcherTable[MatcherIndex++];
}
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();
}
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;
}
ALWAYS_INLINE static bool
CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N, 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);
}
ALWAYS_INLINE static bool
CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
SDValue N, 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, SelectionDAGISel &SDISel,
SmallVectorImpl<SDValue> &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;
}
}
struct MatchScope {
unsigned FailIndex;
SmallVector<SDValue, 4> NodeStack;
unsigned NumRecordedNodes;
unsigned NumMatchedMemRefs;
SDValue InputChain, InputFlag;
bool HasChainNodesMatched, HasFlagResultNodesMatched;
};
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::HANDLENODE:
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:
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<SDValue, 8> RecordedNodes;
SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
SDValue InputChain, InputFlag;
SmallVector<SDNode*, 3> ChainNodesMatched;
SmallVector<SDNode*, 3> FlagResultNodesMatched;
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;
bool Result;
MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
Result, *this, RecordedNodes);
if (!Result)
break;
DEBUG(errs() << " Skipped scope entry at index " << MatcherIndex
<< " continuing at " << FailIndex << "\n");
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.InputFlag = InputFlag;
NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
NewEntry.HasFlagResultNodesMatched = !FlagResultNodesMatched.empty();
MatchScopes.push_back(NewEntry);
continue;
}
case OPC_RecordNode:
RecordedNodes.push_back(N);
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(N->getOperand(ChildNo));
continue;
}
case OPC_RecordMemRef:
MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
continue;
case OPC_CaptureFlagInput:
if (N->getNumOperands() != 0 &&
N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag)
InputFlag = 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], 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::SimpleValueType CurNodeVT = N.getValueType().getSimpleVT().SimpleTy;
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::SimpleValueType CaseVT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
if (CaseVT == MVT::iPTR)
CaseVT = TLI.getPointerTy().SimpleTy;
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, 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(CurDAG->getTargetConstant(Val, VT));
continue;
}
case OPC_EmitRegister: {
MVT::SimpleValueType VT =
(MVT::SimpleValueType)MatcherTable[MatcherIndex++];
unsigned RegNo = MatcherTable[MatcherIndex++];
RecordedNodes.push_back(CurDAG->getRegister(RegNo, VT));
continue;
}
case OPC_EmitConvertToTarget: {
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
SDValue Imm = RecordedNodes[RecNo];
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(Imm);
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].getNode());
if (ChainNodesMatched.back() != NodeToMatch &&
!RecordedNodes[RecNo].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],
InputFlag);
InputFlag = InputChain.getValue(1);
continue;
}
case OPC_EmitNodeXForm: {
unsigned XFormNo = MatcherTable[MatcherIndex++];
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
RecordedNodes.push_back(RunSDNodeXForm(RecordedNodes[RecNo], XFormNo));
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_FlagOutput)
VTs.push_back(MVT::Flag);
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]);
}
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::Flag) break;
Ops.push_back(V);
}
}
if (EmitNodeInfo & OPFL_Chain)
Ops.push_back(InputChain);
if ((EmitNodeInfo & OPFL_FlagInput) && InputFlag.getNode() != 0)
Ops.push_back(InputFlag);
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::Flag) break;
RecordedNodes.push_back(SDValue(Res, i));
}
} else {
Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops.data(), Ops.size(),
EmitNodeInfo);
}
if (EmitNodeInfo & OPFL_FlagOutput) {
InputFlag = 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) {
MachineSDNode::mmo_iterator MemRefs =
MF->allocateMemRefsArray(MatchedMemRefs.size());
std::copy(MatchedMemRefs.begin(), MatchedMemRefs.end(), MemRefs);
cast<MachineSDNode>(Res)
->setMemRefs(MemRefs, MemRefs + MatchedMemRefs.size());
}
DEBUG(errs() << " "
<< (Opcode == OPC_MorphNodeTo ? "Morphed" : "Created")
<< " node: "; Res->dump(CurDAG); errs() << "\n");
if (Opcode == OPC_MorphNodeTo) {
UpdateChainsAndFlags(NodeToMatch, InputChain, ChainNodesMatched,
InputFlag, FlagResultNodesMatched, true);
return Res;
}
continue;
}
case OPC_MarkFlagResults: {
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");
FlagResultNodesMatched.push_back(RecordedNodes[RecNo].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];
if (NodeToMatch->getNumValues() <= i ||
NodeToMatch->getValueType(i) == MVT::Other ||
NodeToMatch->getValueType(i) == MVT::Flag)
break;
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::Flag)
FlagResultNodesMatched.push_back(NodeToMatch);
UpdateChainsAndFlags(NodeToMatch, InputChain, ChainNodesMatched,
InputFlag, FlagResultNodesMatched, false);
assert(NodeToMatch->use_empty() &&
"Didn't replace all uses of the node?");
return 0;
}
}
DEBUG(errs() << " Match failed at index " << CurrentOpcodeIndex << "\n");
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;
InputFlag = LastScope.InputFlag;
if (!LastScope.HasChainNodesMatched)
ChainNodesMatched.clear();
if (!LastScope.HasFlagResultNodesMatched)
FlagResultNodesMatched.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 yet select: ";
if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
N->getOpcode() != ISD::INTRINSIC_VOID) {
N->printrFull(Msg, CurDAG);
} 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;
}
llvm_report_error(Msg.str());
}
char SelectionDAGISel::ID = 0;