blob: 8addaf1ae3e5408011e5afc7333c3674940034df [file] [log] [blame]
//===- SelectionDAGISel.cpp - Implement the SelectionDAGISel class --------===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// This implements the SelectionDAGISel class.
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "ScheduleDAGSDNodes.h"
#include "SelectionDAGBuilder.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/UniformityAnalysis.h"
#include "llvm/CodeGen/AssignmentTrackingAnalysis.h"
#include "llvm/CodeGen/CodeGenCommonISel.h"
#include "llvm/CodeGen/FastISel.h"
#include "llvm/CodeGen/FunctionLoweringInfo.h"
#include "llvm/CodeGen/GCMetadata.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/StackMaps.h"
#include "llvm/CodeGen/StackProtector.h"
#include "llvm/CodeGen/SwiftErrorValueTracking.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/CodeGen/WinEHFuncInfo.h"
#include "llvm/CodeGenTypes/MachineValueType.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/EHPersonalities.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/IntrinsicsWebAssembly.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PrintPasses.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Pass.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CodeGen.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetIntrinsicInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <limits>
#include <memory>
#include <optional>
#include <string>
#include <utility>
#include <vector>
using namespace llvm;
#define DEBUG_TYPE "isel"
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");
STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
"Number of entry blocks where fast isel failed to lower arguments");
static cl::opt<int> EnableFastISelAbort(
"fast-isel-abort", cl::Hidden,
cl::desc("Enable abort calls when \"fast\" instruction selection "
"fails to lower an instruction: 0 disable the abort, 1 will "
"abort but for args, calls and terminators, 2 will also "
"abort for argument lowering, and 3 will never fallback "
"to SelectionDAG."));
static cl::opt<bool> EnableFastISelFallbackReport(
"fast-isel-report-on-fallback", cl::Hidden,
cl::desc("Emit a diagnostic when \"fast\" instruction selection "
"falls back to SelectionDAG."));
static cl::opt<bool>
cl::desc("use Machine Branch Probability Info"),
cl::init(true), cl::Hidden);
#ifndef NDEBUG
static cl::opt<std::string>
FilterDAGBasicBlockName("filter-view-dags", cl::Hidden,
cl::desc("Only display the basic block whose name "
"matches this for all view-*-dags options"));
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>
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>
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>
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"));
static const bool ViewDAGCombine1 = false, ViewLegalizeTypesDAGs = false,
ViewDAGCombineLT = false, ViewLegalizeDAGs = false,
ViewDAGCombine2 = false, ViewISelDAGs = false,
ViewSchedDAGs = false, ViewSUnitDAGs = false;
#ifndef NDEBUG
#define ISEL_DUMP(X) \
do { \
if (llvm::DebugFlag && \
(isCurrentDebugType(DEBUG_TYPE) || \
(isCurrentDebugType(ISEL_DUMP_DEBUG_TYPE) && MatchFilterFuncName))) { \
X; \
} \
} while (false)
#define ISEL_DUMP(X) do { } while (false)
/// RegisterScheduler class - Track the registration of instruction schedulers.
/// ISHeuristic command line option for instruction schedulers.
static cl::opt<RegisterScheduler::FunctionPassCtor, false,
cl::init(&createDefaultScheduler), cl::Hidden,
cl::desc("Instruction schedulers available (before register"
" allocation):"));
static RegisterScheduler
defaultListDAGScheduler("default", "Best scheduler for the target",
static bool dontUseFastISelFor(const Function &Fn) {
// Don't enable FastISel for functions with swiftasync Arguments.
// Debug info on those is reliant on good Argument lowering, and FastISel is
// not capable of lowering the entire function. Mixing the two selectors tend
// to result in poor lowering of Arguments.
return any_of(Fn.args(), [](const Argument &Arg) {
return Arg.hasAttribute(Attribute::AttrKind::SwiftAsync);
namespace llvm {
/// This class is used by SelectionDAGISel to temporarily override
/// the optimization level on a per-function basis.
class OptLevelChanger {
SelectionDAGISel &IS;
CodeGenOptLevel SavedOptLevel;
bool SavedFastISel;
OptLevelChanger(SelectionDAGISel &ISel, CodeGenOptLevel NewOptLevel)
: IS(ISel) {
SavedOptLevel = IS.OptLevel;
SavedFastISel = IS.TM.Options.EnableFastISel;
if (NewOptLevel != SavedOptLevel) {
IS.OptLevel = NewOptLevel;
LLVM_DEBUG(dbgs() << "\nChanging optimization level for Function "
<< IS.MF->getFunction().getName() << "\n");
LLVM_DEBUG(dbgs() << "\tBefore: -O" << static_cast<int>(SavedOptLevel)
<< " ; After: -O" << static_cast<int>(NewOptLevel)
<< "\n");
if (NewOptLevel == CodeGenOptLevel::None)
if (dontUseFastISelFor(IS.MF->getFunction()))
dbgs() << "\tFastISel is "
<< (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")
<< "\n");
~OptLevelChanger() {
if (IS.OptLevel == SavedOptLevel)
LLVM_DEBUG(dbgs() << "\nRestoring optimization level for Function "
<< IS.MF->getFunction().getName() << "\n");
LLVM_DEBUG(dbgs() << "\tBefore: -O" << static_cast<int>(IS.OptLevel)
<< " ; After: -O" << static_cast<int>(SavedOptLevel) << "\n");
IS.OptLevel = SavedOptLevel;
/// createDefaultScheduler - This creates an instruction scheduler appropriate
/// for the target.
ScheduleDAGSDNodes *createDefaultScheduler(SelectionDAGISel *IS,
CodeGenOptLevel OptLevel) {
const TargetLowering *TLI = IS->TLI;
const TargetSubtargetInfo &ST = IS->MF->getSubtarget();
// Try first to see if the Target has its own way of selecting a scheduler
if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {
return SchedulerCtor(IS, OptLevel);
if (OptLevel == CodeGenOptLevel::None ||
(ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) ||
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);
if (TLI->getSchedulingPreference() == Sched::Fast)
return createFastDAGScheduler(IS, OptLevel);
if (TLI->getSchedulingPreference() == Sched::Linearize)
return createDAGLinearizer(IS, OptLevel);
assert(TLI->getSchedulingPreference() == Sched::ILP &&
"Unknown sched type!");
return createILPListDAGScheduler(IS, OptLevel);
} // end namespace llvm
// EmitInstrWithCustomInserter - This method should be implemented by targets
// that mark instructions with the 'usesCustomInserter' flag. These
// instructions are special in various ways, which require special support to
// insert. The specified MachineInstr is created but not inserted into any
// basic blocks, and this method is called to expand it into a sequence of
// instructions, potentially also creating new basic blocks and control flow.
// When new basic blocks are inserted and the edges from MBB to its successors
// are modified, the method should insert pairs of <OldSucc, NewSucc> into the
// DenseMap.
MachineBasicBlock *
TargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
MachineBasicBlock *MBB) const {
#ifndef NDEBUG
dbgs() << "If a target marks an instruction with "
"'usesCustomInserter', it must implement "
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 code
SelectionDAGISel::SelectionDAGISel(char &ID, TargetMachine &tm,
CodeGenOptLevel OL)
: MachineFunctionPass(ID), TM(tm), FuncInfo(new FunctionLoweringInfo()),
SwiftError(new SwiftErrorValueTracking()),
CurDAG(new SelectionDAG(tm, OL)),
SDB(std::make_unique<SelectionDAGBuilder>(*CurDAG, *FuncInfo, *SwiftError,
OptLevel(OL) {
SelectionDAGISel::~SelectionDAGISel() {
delete CurDAG;
delete SwiftError;
void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
if (OptLevel != CodeGenOptLevel::None)
if (UseMBPI && OptLevel != CodeGenOptLevel::None)
// AssignmentTrackingAnalysis only runs if assignment tracking is enabled for
// the module.
if (OptLevel != CodeGenOptLevel::None)
static void computeUsesMSVCFloatingPoint(const Triple &TT, const Function &F,
MachineModuleInfo &MMI) {
// Only needed for MSVC
if (!TT.isWindowsMSVCEnvironment())
// If it's already set, nothing to do.
if (MMI.usesMSVCFloatingPoint())
for (const Instruction &I : instructions(F)) {
if (I.getType()->isFPOrFPVectorTy()) {
for (const auto &Op : I.operands()) {
if (Op->getType()->isFPOrFPVectorTy()) {
bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
// If we already selected that function, we do not need to run SDISel.
if (mf.getProperties().hasProperty(
return false;
// Do some sanity-checking on the command-line options.
assert((!EnableFastISelAbort || TM.Options.EnableFastISel) &&
"-fast-isel-abort > 0 requires -fast-isel");
const Function &Fn = mf.getFunction();
MF = &mf;
#ifndef NDEBUG
StringRef FuncName = Fn.getName();
MatchFilterFuncName = isFunctionInPrintList(FuncName);
// Decide what flavour of variable location debug-info will be used, before
// we change the optimisation level.
bool InstrRef = mf.shouldUseDebugInstrRef();
// Reset the target options before resetting the optimization
// level below.
// FIXME: This is a horrible hack and should be processed via
// codegen looking at the optimization level explicitly when
// it wants to look at it.
// Reset OptLevel to None for optnone functions.
CodeGenOptLevel NewOptLevel = OptLevel;
if (OptLevel != CodeGenOptLevel::None && skipFunction(Fn))
NewOptLevel = CodeGenOptLevel::None;
OptLevelChanger OLC(*this, NewOptLevel);
TII = MF->getSubtarget().getInstrInfo();
TLI = MF->getSubtarget().getTargetLowering();
RegInfo = &MF->getRegInfo();
LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(Fn);
GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr;
ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn);
AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(mf.getFunction());
auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
BlockFrequencyInfo *BFI = nullptr;
if (PSI && PSI->hasProfileSummary() && OptLevel != CodeGenOptLevel::None)
BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
FunctionVarLocs const *FnVarLocs = nullptr;
if (isAssignmentTrackingEnabled(*Fn.getParent()))
FnVarLocs = getAnalysis<AssignmentTrackingAnalysis>().getResults();
ISEL_DUMP(dbgs() << "\n\n\n=== " << FuncName << "\n");
UniformityInfo *UA = nullptr;
if (auto *UAPass = getAnalysisIfAvailable<UniformityInfoWrapperPass>())
UA = &UAPass->getUniformityInfo();
CurDAG->init(*MF, *ORE, this, LibInfo, UA, PSI, BFI, FnVarLocs);
FuncInfo->set(Fn, *MF, CurDAG);
// Now get the optional analyzes if we want to.
// This is based on the possibly changed OptLevel (after optnone is taken
// into account). That's unfortunate but OK because it just means we won't
// ask for passes that have been required anyway.
if (UseMBPI && OptLevel != CodeGenOptLevel::None)
FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
FuncInfo->BPI = nullptr;
if (OptLevel != CodeGenOptLevel::None)
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
AA = nullptr;
SDB->init(GFI, AA, AC, LibInfo);
FuncInfo->SplitCSR = false;
// We split CSR if the target supports it for the given function
// and the function has only return exits.
if (OptLevel != CodeGenOptLevel::None && TLI->supportSplitCSR(MF)) {
FuncInfo->SplitCSR = true;
// Collect all the return blocks.
for (const BasicBlock &BB : Fn) {
if (!succ_empty(&BB))
const Instruction *Term = BB.getTerminator();
if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term))
// Bail out if the exit block is not Return nor Unreachable.
FuncInfo->SplitCSR = false;
MachineBasicBlock *EntryMBB = &MF->front();
if (FuncInfo->SplitCSR)
// This performs initialization so lowering for SplitCSR will be correct.
if (FastISelFailed && EnableFastISelFallbackReport) {
DiagnosticInfoISelFallback DiagFallback(Fn);
// Replace forward-declared registers with the registers containing
// the desired value.
// Note: it is important that this happens **before** the call to
// EmitLiveInCopies, since implementations can skip copies of unused
// registers. If we don't apply the reg fixups before, some registers may
// appear as unused and will be skipped, resulting in bad MI.
MachineRegisterInfo &MRI = MF->getRegInfo();
for (DenseMap<Register, Register>::iterator I = FuncInfo->RegFixups.begin(),
E = FuncInfo->RegFixups.end();
I != E; ++I) {
Register From = I->first;
Register To = I->second;
// If To is also scheduled to be replaced, find what its ultimate
// replacement is.
while (true) {
DenseMap<Register, Register>::iterator J = FuncInfo->RegFixups.find(To);
if (J == E)
To = J->second;
// Make sure the new register has a sufficiently constrained register class.
if (From.isVirtual() && To.isVirtual())
MRI.constrainRegClass(To, MRI.getRegClass(From));
// Replace it.
// Replacing one register with another won't touch the kill flags.
// We need to conservatively clear the kill flags as a kill on the old
// register might dominate existing uses of the new register.
if (!MRI.use_empty(To))
MRI.replaceRegWith(From, To);
// If the first basic block in the function has live ins that need to be
// copied into vregs, emit the copies into the top of the block before
// emitting the code for the block.
const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);
// Insert copies in the entry block and the return blocks.
if (FuncInfo->SplitCSR) {
SmallVector<MachineBasicBlock*, 4> Returns;
// Collect all the return blocks.
for (MachineBasicBlock &MBB : mf) {
if (!MBB.succ_empty())
MachineBasicBlock::iterator Term = MBB.getFirstTerminator();
if (Term != MBB.end() && Term->isReturn()) {
TLI->insertCopiesSplitCSR(EntryMBB, Returns);
DenseMap<unsigned, unsigned> LiveInMap;
if (!FuncInfo->ArgDbgValues.empty())
for (std::pair<unsigned, unsigned> LI : RegInfo->liveins())
if (LI.second)
// Insert DBG_VALUE instructions for function arguments to the entry block.
for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
MachineInstr *MI = FuncInfo->ArgDbgValues[e - i - 1];
assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&
"Function parameters should not be described by DBG_VALUE_LIST.");
bool hasFI = MI->getDebugOperand(0).isFI();
Register Reg =
hasFI ? TRI.getFrameRegister(*MF) : MI->getDebugOperand(0).getReg();
if (Reg.isPhysical())
EntryMBB->insert(EntryMBB->begin(), MI);
else {
MachineInstr *Def = RegInfo->getVRegDef(Reg);
if (Def) {
MachineBasicBlock::iterator InsertPos = Def;
// FIXME: VR def may not be in entry block.
Def->getParent()->insert(std::next(InsertPos), MI);
} else
LLVM_DEBUG(dbgs() << "Dropping debug info for dead vreg"
<< Register::virtReg2Index(Reg) << "\n");
// Don't try and extend through copies in instruction referencing mode.
if (InstrRef)
// If Reg is live-in then update debug info to track its copy in a vreg.
DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
if (LDI != LiveInMap.end()) {
assert(!hasFI && "There's no handling of frame pointer updating here yet "
"- add if needed");
MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
MachineBasicBlock::iterator InsertPos = Def;
const MDNode *Variable = MI->getDebugVariable();
const MDNode *Expr = MI->getDebugExpression();
DebugLoc DL = MI->getDebugLoc();
bool IsIndirect = MI->isIndirectDebugValue();
if (IsIndirect)
assert(MI->getDebugOffset().getImm() == 0 &&
"DBG_VALUE with nonzero offset");
assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
"Expected inlined-at fields to agree");
assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&
"Didn't expect to see a DBG_VALUE_LIST here");
// Def is never a terminator here, so it is ok to increment InsertPos.
BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),
IsIndirect, LDI->second, Variable, Expr);
// If this vreg is directly copied into an exported register then
// that COPY instructions also need DBG_VALUE, if it is the only
// user of LDI->second.
MachineInstr *CopyUseMI = nullptr;
for (MachineRegisterInfo::use_instr_iterator
UI = RegInfo->use_instr_begin(LDI->second),
E = RegInfo->use_instr_end(); UI != E; ) {
MachineInstr *UseMI = &*(UI++);
if (UseMI->isDebugValue()) continue;
if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) {
CopyUseMI = UseMI; continue;
// Otherwise this is another use or second copy use.
CopyUseMI = nullptr; break;
if (CopyUseMI &&
TRI.getRegSizeInBits(LDI->second, MRI) ==
TRI.getRegSizeInBits(CopyUseMI->getOperand(0).getReg(), MRI)) {
// Use MI's debug location, which describes where Variable was
// declared, rather than whatever is attached to CopyUseMI.
MachineInstr *NewMI =
BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,
CopyUseMI->getOperand(0).getReg(), Variable, Expr);
MachineBasicBlock::iterator Pos = CopyUseMI;
EntryMBB->insertAfter(Pos, NewMI);
// For debug-info, in instruction referencing mode, we need to perform some
// post-isel maintenence.
if (MF->useDebugInstrRef())
// Determine if there are any calls in this machine function.
MachineFrameInfo &MFI = MF->getFrameInfo();
for (const auto &MBB : *MF) {
if (MFI.hasCalls() && MF->hasInlineAsm())
for (const auto &MI : MBB) {
const MCInstrDesc &MCID = TII->get(MI.getOpcode());
if ((MCID.isCall() && !MCID.isReturn()) ||
MI.isStackAligningInlineAsm()) {
if (MI.isInlineAsm()) {
// Determine if floating point is used for msvc
computeUsesMSVCFloatingPoint(TM.getTargetTriple(), Fn, MF->getMMI());
// Release function-specific state. SDB and CurDAG are already cleared
// at this point.
ISEL_DUMP(dbgs() << "*** MachineFunction at end of ISel ***\n");
return true;
static void reportFastISelFailure(MachineFunction &MF,
OptimizationRemarkEmitter &ORE,
OptimizationRemarkMissed &R,
bool ShouldAbort) {
// Print the function name explicitly if we don't have a debug location (which
// makes the diagnostic less useful) or if we're going to emit a raw error.
if (!R.getLocation().isValid() || ShouldAbort)
R << (" (in function: " + MF.getName() + ")").str();
if (ShouldAbort)
LLVM_DEBUG(dbgs() << R.getMsg() << "\n");
void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
BasicBlock::const_iterator End,
bool &HadTailCall) {
// Allow creating illegal types during DAG building for the basic block.
CurDAG->NewNodesMustHaveLegalTypes = false;
// Lower the instructions. If a call is emitted as a tail call, cease emitting
// nodes for this block. If an instruction is elided, don't emit it, but do
// handle any debug-info attached to it.
for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
if (!ElidedArgCopyInstrs.count(&*I))
// Make sure the root of the DAG is up-to-date.
HadTailCall = SDB->HasTailCall;
// Final step, emit the lowered DAG as machine code.
void SelectionDAGISel::ComputeLiveOutVRegInfo() {
SmallPtrSet<SDNode *, 16> Added;
SmallVector<SDNode*, 128> Worklist;
KnownBits Known;
do {
SDNode *N = Worklist.pop_back_val();
// Otherwise, add all chain operands to the worklist.
for (const SDValue &Op : N->op_values())
if (Op.getValueType() == MVT::Other && Added.insert(Op.getNode()).second)
// If this is a CopyToReg with a vreg dest, process it.
if (N->getOpcode() != ISD::CopyToReg)
unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
if (!Register::isVirtualRegister(DestReg))
// Ignore non-integer values.
SDValue Src = N->getOperand(2);
EVT SrcVT = Src.getValueType();
if (!SrcVT.isInteger())
unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
Known = CurDAG->computeKnownBits(Src);
FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
} while (!Worklist.empty());
void SelectionDAGISel::CodeGenAndEmitDAG() {
StringRef GroupName = "sdag";
StringRef GroupDescription = "Instruction Selection and Scheduling";
std::string BlockName;
bool MatchFilterBB = false; (void)MatchFilterBB;
#ifndef NDEBUG
TargetTransformInfo &TTI =
// Pre-type legalization allow creation of any node types.
CurDAG->NewNodesMustHaveLegalTypes = false;
#ifndef NDEBUG
MatchFilterBB = (FilterDAGBasicBlockName.empty() ||
FilterDAGBasicBlockName ==
#ifdef NDEBUG
if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewDAGCombineLT ||
ViewLegalizeDAGs || ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs ||
BlockName =
(MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();
ISEL_DUMP(dbgs() << "\nInitial selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
if (ViewDAGCombine1 && MatchFilterBB)
CurDAG->viewGraph("dag-combine1 input for " + BlockName);
// Run the DAG combiner in pre-legalize mode.
NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
GroupDescription, TimePassesIsEnabled);
CurDAG->Combine(BeforeLegalizeTypes, AA, OptLevel);
ISEL_DUMP(dbgs() << "\nOptimized lowered selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
// Second step, hack on the DAG until it only uses operations and types that
// the target supports.
if (ViewLegalizeTypesDAGs && MatchFilterBB)
CurDAG->viewGraph("legalize-types input for " + BlockName);
bool Changed;
NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,
GroupDescription, TimePassesIsEnabled);
Changed = CurDAG->LegalizeTypes();
ISEL_DUMP(dbgs() << "\nType-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
// Only allow creation of legal node types.
CurDAG->NewNodesMustHaveLegalTypes = true;
if (Changed) {
if (ViewDAGCombineLT && MatchFilterBB)
CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
// Run the DAG combiner in post-type-legalize mode.
NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",
GroupName, GroupDescription, TimePassesIsEnabled);
CurDAG->Combine(AfterLegalizeTypes, AA, OptLevel);
ISEL_DUMP(dbgs() << "\nOptimized type-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,
GroupDescription, TimePassesIsEnabled);
Changed = CurDAG->LegalizeVectors();
if (Changed) {
ISEL_DUMP(dbgs() << "\nVector-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,
GroupDescription, TimePassesIsEnabled);
ISEL_DUMP(dbgs() << "\nVector/type-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
if (ViewDAGCombineLT && MatchFilterBB)
CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
// Run the DAG combiner in post-type-legalize mode.
NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",
GroupName, GroupDescription, TimePassesIsEnabled);
CurDAG->Combine(AfterLegalizeVectorOps, AA, OptLevel);
ISEL_DUMP(dbgs() << "\nOptimized vector-legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
if (ViewLegalizeDAGs && MatchFilterBB)
CurDAG->viewGraph("legalize input for " + BlockName);
NamedRegionTimer T("legalize", "DAG Legalization", GroupName,
GroupDescription, TimePassesIsEnabled);
ISEL_DUMP(dbgs() << "\nLegalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
if (ViewDAGCombine2 && MatchFilterBB)
CurDAG->viewGraph("dag-combine2 input for " + BlockName);
// Run the DAG combiner in post-legalize mode.
NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,
GroupDescription, TimePassesIsEnabled);
CurDAG->Combine(AfterLegalizeDAG, AA, OptLevel);
ISEL_DUMP(dbgs() << "\nOptimized legalized selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
#ifndef NDEBUG
if (TTI.hasBranchDivergence())
if (OptLevel != CodeGenOptLevel::None)
if (ViewISelDAGs && MatchFilterBB)
CurDAG->viewGraph("isel input for " + BlockName);
// Third, instruction select all of the operations to machine code, adding the
// code to the MachineBasicBlock.
NamedRegionTimer T("isel", "Instruction Selection", GroupName,
GroupDescription, TimePassesIsEnabled);
ISEL_DUMP(dbgs() << "\nSelected selection DAG: "
<< printMBBReference(*FuncInfo->MBB) << " '" << BlockName
<< "'\n";
if (ViewSchedDAGs && MatchFilterBB)
CurDAG->viewGraph("scheduler input for " + BlockName);
// Schedule machine code.
ScheduleDAGSDNodes *Scheduler = CreateScheduler();
NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,
GroupDescription, TimePassesIsEnabled);
Scheduler->Run(CurDAG, FuncInfo->MBB);
if (ViewSUnitDAGs && MatchFilterBB)
// Emit machine code to BB. This can change 'BB' to the last block being
// inserted into.
MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
NamedRegionTimer T("emit", "Instruction Creation", GroupName,
GroupDescription, TimePassesIsEnabled);
// FuncInfo->InsertPt is passed by reference and set to the end of the
// scheduled instructions.
LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
// If the block was split, make sure we update any references that are used to
// update PHI nodes later on.
if (FirstMBB != LastMBB)
SDB->UpdateSplitBlock(FirstMBB, LastMBB);
// Free the scheduler state.
NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,
GroupDescription, TimePassesIsEnabled);
delete Scheduler;
// Free the SelectionDAG state, now that we're finished with it.
namespace {
/// ISelUpdater - helper class to handle updates of the instruction selection
/// graph.
class ISelUpdater : public SelectionDAG::DAGUpdateListener {
SelectionDAG::allnodes_iterator &ISelPosition;
ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
: SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
/// NodeDeleted - Handle nodes deleted from the graph. If the node being
/// deleted is the current ISelPosition node, update ISelPosition.
void NodeDeleted(SDNode *N, SDNode *E) override {
if (ISelPosition == SelectionDAG::allnodes_iterator(N))
/// NodeInserted - Handle new nodes inserted into the graph: propagate
/// metadata from root nodes that also applies to new nodes, in case the root
/// is later deleted.
void NodeInserted(SDNode *N) override {
SDNode *CurNode = &*ISelPosition;
if (MDNode *MD = DAG.getPCSections(CurNode))
DAG.addPCSections(N, MD);
if (MDNode *MMRA = DAG.getMMRAMetadata(CurNode))
DAG.addMMRAMetadata(N, MMRA);
} // end anonymous namespace
// This function is used to enforce the topological node id property
// leveraged during instruction selection. Before the selection process all
// nodes are given a non-negative id such that all nodes have a greater id than
// their operands. As this holds transitively we can prune checks that a node N
// is a predecessor of M another by not recursively checking through M's
// operands if N's ID is larger than M's ID. This significantly improves
// performance of various legality checks (e.g. IsLegalToFold / UpdateChains).
// However, when we fuse multiple nodes into a single node during the
// selection we may induce a predecessor relationship between inputs and
// outputs of distinct nodes being merged, violating the topological property.
// Should a fused node have a successor which has yet to be selected,
// our legality checks would be incorrect. To avoid this we mark all unselected
// successor nodes, i.e. id != -1, as invalid for pruning by bit-negating (x =>
// (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M.
// We use bit-negation to more clearly enforce that node id -1 can only be
// achieved by selected nodes. As the conversion is reversable to the original
// Id, topological pruning can still be leveraged when looking for unselected
// nodes. This method is called internally in all ISel replacement related
// functions.
void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) {
SmallVector<SDNode *, 4> Nodes;
while (!Nodes.empty()) {
SDNode *N = Nodes.pop_back_val();
for (auto *U : N->uses()) {
auto UId = U->getNodeId();
if (UId > 0) {
// InvalidateNodeId - As explained in EnforceNodeIdInvariant, mark a
// NodeId with the equivalent node id which is invalid for topological
// pruning.
void SelectionDAGISel::InvalidateNodeId(SDNode *N) {
int InvalidId = -(N->getNodeId() + 1);
// getUninvalidatedNodeId - get original uninvalidated node id.
int SelectionDAGISel::getUninvalidatedNodeId(SDNode *N) {
int Id = N->getNodeId();
if (Id < -1)
return -(Id + 1);
return Id;
void SelectionDAGISel::DoInstructionSelection() {
LLVM_DEBUG(dbgs() << "===== Instruction selection begins: "
<< printMBBReference(*FuncInfo->MBB) << " '"
<< FuncInfo->MBB->getName() << "'\n");
// Select target instructions for the DAG.
// Number all nodes with a topological order and set DAGSize.
DAGSize = CurDAG->AssignTopologicalOrder();
// Create a dummy node (which is not added to allnodes), that adds
// a reference to the root node, preventing it from being deleted,
// and tracking any changes of the root.
HandleSDNode Dummy(CurDAG->getRoot());
SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());
// Make sure that ISelPosition gets properly updated when nodes are deleted
// in calls made from this function. New nodes inherit relevant metadata.
ISelUpdater ISU(*CurDAG, ISelPosition);
// The AllNodes list is now topological-sorted. Visit the
// nodes by starting at the end of the list (the root of the
// graph) and preceding back toward the beginning (the entry
// node).
while (ISelPosition != CurDAG->allnodes_begin()) {
SDNode *Node = &*--ISelPosition;
// Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
// but there are currently some corner cases that it misses. Also, this
// makes it theoretically possible to disable the DAGCombiner.
if (Node->use_empty())
#ifndef NDEBUG
SmallVector<SDNode *, 4> Nodes;
while (!Nodes.empty()) {
auto N = Nodes.pop_back_val();
if (N->getOpcode() == ISD::TokenFactor || N->getNodeId() < 0)
for (const SDValue &Op : N->op_values()) {
if (Op->getOpcode() == ISD::TokenFactor)
else {
// We rely on topological ordering of node ids for checking for
// cycles when fusing nodes during selection. All unselected nodes
// successors of an already selected node should have a negative id.
// This assertion will catch such cases. If this assertion triggers
// it is likely you using DAG-level Value/Node replacement functions
// (versus equivalent ISEL replacement) in backend-specific
// selections. See comment in EnforceNodeIdInvariant for more
// details.
assert(Op->getNodeId() != -1 &&
"Node has already selected predecessor node");
// When we are using non-default rounding modes or FP exception behavior
// FP operations are represented by StrictFP pseudo-operations. For
// targets that do not (yet) understand strict FP operations directly,
// we convert them to normal FP opcodes instead at this point. This
// will allow them to be handled by existing target-specific instruction
// selectors.
if (!TLI->isStrictFPEnabled() && Node->isStrictFPOpcode()) {
// For some opcodes, we need to call TLI->getOperationAction using
// the first operand type instead of the result type. Note that this
// must match what SelectionDAGLegalize::LegalizeOp is doing.
EVT ActionVT;
switch (Node->getOpcode()) {
ActionVT = Node->getOperand(1).getValueType();
ActionVT = Node->getValueType(0);
if (TLI->getOperationAction(Node->getOpcode(), ActionVT)
== TargetLowering::Expand)
Node = CurDAG->mutateStrictFPToFP(Node);
LLVM_DEBUG(dbgs() << "\nISEL: Starting selection on root node: ";
LLVM_DEBUG(dbgs() << "\n===== Instruction selection ends:\n");
static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI) {
for (const User *U : CPI->users()) {
if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {
Intrinsic::ID IID = EHPtrCall->getIntrinsicID();
if (IID == Intrinsic::eh_exceptionpointer ||
IID == Intrinsic::eh_exceptioncode)
return true;
return false;
// wasm.landingpad.index intrinsic is for associating a landing pad index number
// with a catchpad instruction. Retrieve the landing pad index in the intrinsic
// and store the mapping in the function.
static void mapWasmLandingPadIndex(MachineBasicBlock *MBB,
const CatchPadInst *CPI) {
MachineFunction *MF = MBB->getParent();
// In case of single catch (...), we don't emit LSDA, so we don't need
// this information.
bool IsSingleCatchAllClause =
CPI->arg_size() == 1 &&
// cathchpads for longjmp use an empty type list, e.g. catchpad within %0 []
// and they don't need LSDA info
bool IsCatchLongjmp = CPI->arg_size() == 0;
if (!IsSingleCatchAllClause && !IsCatchLongjmp) {
// Create a mapping from landing pad label to landing pad index.
bool IntrFound = false;
for (const User *U : CPI->users()) {
if (const auto *Call = dyn_cast<IntrinsicInst>(U)) {
Intrinsic::ID IID = Call->getIntrinsicID();
if (IID == Intrinsic::wasm_landingpad_index) {
Value *IndexArg = Call->getArgOperand(1);
int Index = cast<ConstantInt>(IndexArg)->getZExtValue();
MF->setWasmLandingPadIndex(MBB, Index);
IntrFound = true;
assert(IntrFound && "wasm.landingpad.index intrinsic not found!");
/// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
/// do other setup for EH landing-pad blocks.
bool SelectionDAGISel::PrepareEHLandingPad() {
MachineBasicBlock *MBB = FuncInfo->MBB;
const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();
const BasicBlock *LLVMBB = MBB->getBasicBlock();
const TargetRegisterClass *PtrRC =
auto Pers = classifyEHPersonality(PersonalityFn);
// Catchpads have one live-in register, which typically holds the exception
// pointer or code.
if (isFuncletEHPersonality(Pers)) {
if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) {
if (hasExceptionPointerOrCodeUser(CPI)) {
// Get or create the virtual register to hold the pointer or code. Mark
// the live in physreg and copy into the vreg.
MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);
assert(EHPhysReg && "target lacks exception pointer register");
unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);
BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(),
TII->get(TargetOpcode::COPY), VReg)
.addReg(EHPhysReg, RegState::Kill);
return true;
// Add a label to mark the beginning of the landing pad. Deletion of the
// landing pad can thus be detected via the MachineModuleInfo.
MCSymbol *Label = MF->addLandingPad(MBB);
const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);
BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
// If the unwinder does not preserve all registers, ensure that the
// function marks the clobbered registers as used.
const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
if (auto *RegMask = TRI.getCustomEHPadPreservedMask(*MF))
if (Pers == EHPersonality::Wasm_CXX) {
if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI()))
mapWasmLandingPadIndex(MBB, CPI);
} else {
// Assign the call site to the landing pad's begin label.
MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
// Mark exception register as live in.
if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn))
FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);
// Mark exception selector register as live in.
if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn))
FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);
return true;
// Mark and Report IPToState for each Block under IsEHa
void SelectionDAGISel::reportIPToStateForBlocks(MachineFunction *MF) {
MachineModuleInfo &MMI = MF->getMMI();
llvm::WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo();
if (!EHInfo)
for (auto MBBI = MF->begin(), E = MF->end(); MBBI != E; ++MBBI) {
MachineBasicBlock *MBB = &*MBBI;
const BasicBlock *BB = MBB->getBasicBlock();
int State = EHInfo->BlockToStateMap[BB];
if (BB->getFirstMayFaultInst()) {
// Report IP range only for blocks with Faulty inst
auto MBBb = MBB->getFirstNonPHI();
MachineInstr *MIb = &*MBBb;
if (MIb->isTerminator())
// Insert EH Labels
MCSymbol *BeginLabel = MMI.getContext().createTempSymbol();
MCSymbol *EndLabel = MMI.getContext().createTempSymbol();
EHInfo->addIPToStateRange(State, BeginLabel, EndLabel);
BuildMI(*MBB, MBBb, SDB->getCurDebugLoc(),
auto MBBe = MBB->instr_end();
MachineInstr *MIe = &*(--MBBe);
// insert before (possible multiple) terminators
while (MIe->isTerminator())
MIe = &*(--MBBe);
BuildMI(*MBB, MBBe, SDB->getCurDebugLoc(),
/// isFoldedOrDeadInstruction - Return true if the specified instruction is
/// side-effect free and is either dead or folded into a generated instruction.
/// Return false if it needs to be emitted.
static bool isFoldedOrDeadInstruction(const Instruction *I,
const FunctionLoweringInfo &FuncInfo) {
return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
!I->isTerminator() && // Terminators aren't folded.
!isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded.
!I->isEHPad() && // EH pad instructions aren't folded.
!FuncInfo.isExportedInst(I); // Exported instrs must be computed.
static bool processIfEntryValueDbgDeclare(FunctionLoweringInfo &FuncInfo,
const Value *Arg, DIExpression *Expr,
DILocalVariable *Var,
DebugLoc DbgLoc) {
if (!Expr->isEntryValue() || !isa<Argument>(Arg))
return false;
auto ArgIt = FuncInfo.ValueMap.find(Arg);
if (ArgIt == FuncInfo.ValueMap.end())
return false;
Register ArgVReg = ArgIt->getSecond();
// Find the corresponding livein physical register to this argument.
for (auto [PhysReg, VirtReg] : FuncInfo.RegInfo->liveins())
if (VirtReg == ArgVReg) {
// Append an op deref to account for the fact that this is a dbg_declare.
Expr = DIExpression::append(Expr, dwarf::DW_OP_deref);
FuncInfo.MF->setVariableDbgInfo(Var, Expr, PhysReg, DbgLoc);
LLVM_DEBUG(dbgs() << "processDbgDeclare: setVariableDbgInfo Var=" << *Var
<< ", Expr=" << *Expr << ", MCRegister=" << PhysReg
<< ", DbgLoc=" << DbgLoc << "\n");
return true;
return false;
static bool processDbgDeclare(FunctionLoweringInfo &FuncInfo,
const Value *Address, DIExpression *Expr,
DILocalVariable *Var, DebugLoc DbgLoc) {
if (!Address) {
LLVM_DEBUG(dbgs() << "processDbgDeclares skipping " << *Var
<< " (bad address)\n");
return false;
if (processIfEntryValueDbgDeclare(FuncInfo, Address, Expr, Var, DbgLoc))
return true;
MachineFunction *MF = FuncInfo.MF;
const DataLayout &DL = MF->getDataLayout();
assert(Var && "Missing variable");
assert(DbgLoc && "Missing location");
// Look through casts and constant offset GEPs. These mostly come from
// inalloca.
APInt Offset(DL.getTypeSizeInBits(Address->getType()), 0);
Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
// Check if the variable is a static alloca or a byval or inalloca
// argument passed in memory. If it is not, then we will ignore this
// intrinsic and handle this during isel like dbg.value.
int FI = std::numeric_limits<int>::max();
if (const auto *AI = dyn_cast<AllocaInst>(Address)) {
auto SI = FuncInfo.StaticAllocaMap.find(AI);
if (SI != FuncInfo.StaticAllocaMap.end())
FI = SI->second;
} else if (const auto *Arg = dyn_cast<Argument>(Address))
FI = FuncInfo.getArgumentFrameIndex(Arg);
if (FI == std::numeric_limits<int>::max())
return false;
if (Offset.getBoolValue())
Expr = DIExpression::prepend(Expr, DIExpression::ApplyOffset,
LLVM_DEBUG(dbgs() << "processDbgDeclare: setVariableDbgInfo Var=" << *Var
<< ", Expr=" << *Expr << ", FI=" << FI
<< ", DbgLoc=" << DbgLoc << "\n");
MF->setVariableDbgInfo(Var, Expr, FI, DbgLoc);
return true;
/// Collect llvm.dbg.declare information. This is done after argument lowering
/// in case the declarations refer to arguments.
static void processDbgDeclares(FunctionLoweringInfo &FuncInfo) {
for (const auto &I : instructions(*FuncInfo.Fn)) {
const auto *DI = dyn_cast<DbgDeclareInst>(&I);
if (DI && processDbgDeclare(FuncInfo, DI->getAddress(), DI->getExpression(),
DI->getVariable(), DI->getDebugLoc()))
for (const DbgVariableRecord &DVR : filterDbgVars(I.getDbgRecordRange())) {
if (DVR.Type == DbgVariableRecord::LocationType::Declare &&
processDbgDeclare(FuncInfo, DVR.getVariableLocationOp(0),
DVR.getExpression(), DVR.getVariable(),
/// Collect single location variable information generated with assignment
/// tracking. This is done after argument lowering in case the declarations
/// refer to arguments.
static void processSingleLocVars(FunctionLoweringInfo &FuncInfo,
FunctionVarLocs const *FnVarLocs) {
for (auto It = FnVarLocs->single_locs_begin(),
End = FnVarLocs->single_locs_end();
It != End; ++It) {
assert(!It->Values.hasArgList() && "Single loc variadic ops not supported");
processDbgDeclare(FuncInfo, It->Values.getVariableLocationOp(0), It->Expr,
FnVarLocs->getDILocalVariable(It->VariableID), It->DL);
void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
FastISelFailed = false;
// Initialize the Fast-ISel state, if needed.
FastISel *FastIS = nullptr;
if (TM.Options.EnableFastISel) {
LLVM_DEBUG(dbgs() << "Enabling fast-isel\n");
FastIS = TLI->createFastISel(*FuncInfo, LibInfo);
ReversePostOrderTraversal<const Function*> RPOT(&Fn);
// Lower arguments up front. An RPO iteration always visits the entry block
// first.
assert(*RPOT.begin() == &Fn.getEntryBlock());
// Set up FuncInfo for ISel. Entry blocks never have PHIs.
FuncInfo->MBB = FuncInfo->MBBMap[&Fn.getEntryBlock()];
FuncInfo->InsertPt = FuncInfo->MBB->begin();
if (!FastIS) {
} else {
// See if fast isel can lower the arguments.
if (!FastIS->lowerArguments()) {
FastISelFailed = true;
// Fast isel failed to lower these arguments
OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
R << "FastISel didn't lower all arguments: "
<< ore::NV("Prototype", Fn.getFunctionType());
reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 1);
// Use SelectionDAG argument lowering
// If we inserted any instructions at the beginning, make a note of
// where they are, so we can be sure to emit subsequent instructions
// after them.
if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
bool Inserted = SwiftError->createEntriesInEntryBlock(SDB->getCurDebugLoc());
if (FastIS && Inserted)
if (isAssignmentTrackingEnabled(*Fn.getParent())) {
assert(CurDAG->getFunctionVarLocs() &&
"expected AssignmentTrackingAnalysis pass results");
processSingleLocVars(*FuncInfo, CurDAG->getFunctionVarLocs());
} else {
// Iterate over all basic blocks in the function.
StackProtector &SP = getAnalysis<StackProtector>();
for (const BasicBlock *LLVMBB : RPOT) {
if (OptLevel != CodeGenOptLevel::None) {
bool AllPredsVisited = true;
for (const BasicBlock *Pred : predecessors(LLVMBB)) {
if (!FuncInfo->VisitedBBs.count(Pred)) {
AllPredsVisited = false;
if (AllPredsVisited) {
for (const PHINode &PN : LLVMBB->phis())
} else {
for (const PHINode &PN : LLVMBB->phis())
BasicBlock::const_iterator const Begin =
BasicBlock::const_iterator const End = LLVMBB->end();
BasicBlock::const_iterator BI = End;
FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
if (!FuncInfo->MBB)
continue; // Some blocks like catchpads have no code or MBB.
// Insert new instructions after any phi or argument setup code.
FuncInfo->InsertPt = FuncInfo->MBB->end();
// Setup an EH landing-pad block.
FuncInfo->ExceptionPointerVirtReg = 0;
FuncInfo->ExceptionSelectorVirtReg = 0;
if (LLVMBB->isEHPad())
if (!PrepareEHLandingPad())
// Before doing SelectionDAG ISel, see if FastISel has been requested.
if (FastIS) {
if (LLVMBB != &Fn.getEntryBlock())
unsigned NumFastIselRemaining = std::distance(Begin, End);
// Pre-assign swifterror vregs.
SwiftError->preassignVRegs(FuncInfo->MBB, Begin, End);
// Do FastISel on as many instructions as possible.
for (; BI != Begin; --BI) {
const Instruction *Inst = &*std::prev(BI);
// If we no longer require this instruction, skip it.
if (isFoldedOrDeadInstruction(Inst, *FuncInfo) ||
ElidedArgCopyInstrs.count(Inst)) {
// Bottom-up: reset the insert pos at the top, after any local-value
// instructions.
// Try to select the instruction with FastISel.
if (FastIS->selectInstruction(Inst)) {
// If fast isel succeeded, skip over all the folded instructions, and
// then see if there is a load right before the selected instructions.
// Try to fold the load if so.
const Instruction *BeforeInst = Inst;
while (BeforeInst != &*Begin) {
BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));
if (!isFoldedOrDeadInstruction(BeforeInst, *FuncInfo))
if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
BeforeInst->hasOneUse() &&
FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {
// If we succeeded, don't re-select the load.
<< "FastISel folded load: " << *BeforeInst << "\n");
BI = std::next(BasicBlock::const_iterator(BeforeInst));
FastISelFailed = true;
// Then handle certain instructions as single-LLVM-Instruction blocks.
// We cannot separate out GCrelocates to their own blocks since we need
// to keep track of gc-relocates for a particular gc-statepoint. This is
// done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before
// visitGCRelocate.
if (isa<CallInst>(Inst) && !isa<GCStatepointInst>(Inst) &&
!isa<GCRelocateInst>(Inst) && !isa<GCResultInst>(Inst)) {
OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
Inst->getDebugLoc(), LLVMBB);
R << "FastISel missed call";
if (R.isEnabled() || EnableFastISelAbort) {
std::string InstStrStorage;
raw_string_ostream InstStr(InstStrStorage);
InstStr << *Inst;
R << ": " << InstStr.str();
reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 2);
if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() &&
!Inst->use_empty()) {
Register &R = FuncInfo->ValueMap[Inst];
if (!R)
R = FuncInfo->CreateRegs(Inst);
bool HadTailCall = false;
MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;
SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);
// If the call was emitted as a tail call, we're done with the block.
// We also need to delete any previously emitted instructions.
if (HadTailCall) {
FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
// Recompute NumFastIselRemaining as Selection DAG instruction
// selection may have handled the call, input args, etc.
unsigned RemainingNow = std::distance(Begin, BI);
NumFastIselFailures += NumFastIselRemaining - RemainingNow;
NumFastIselRemaining = RemainingNow;
OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
Inst->getDebugLoc(), LLVMBB);
bool ShouldAbort = EnableFastISelAbort;
if (Inst->isTerminator()) {
// Use a different message for terminator misses.
R << "FastISel missed terminator";
// Don't abort for terminator unless the level is really high
ShouldAbort = (EnableFastISelAbort > 2);
} else {
R << "FastISel missed";
if (R.isEnabled() || EnableFastISelAbort) {
std::string InstStrStorage;
raw_string_ostream InstStr(InstStrStorage);
InstStr << *Inst;
R << ": " << InstStr.str();
reportFastISelFailure(*MF, *ORE, R, ShouldAbort);
NumFastIselFailures += NumFastIselRemaining;
if (SP.shouldEmitSDCheck(*LLVMBB)) {
bool FunctionBasedInstrumentation =
SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->MBBMap[LLVMBB],
if (Begin != BI)
if (Begin != BI) {
// Run SelectionDAG instruction selection on the remainder of the block
// not handled by FastISel. If FastISel is not run, this is the entire
// block.
bool HadTailCall;
SelectBasicBlock(Begin, BI, HadTailCall);
// But if FastISel was run, we already selected some of the block.
// If we emitted a tail-call, we need to delete any previously emitted
// instruction that follows it.
if (FastIS && HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end())
FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end());
if (FastIS)
// AsynchEH: Report Block State under -AsynchEH
if (Fn.getParent()->getModuleFlag("eh-asynch"))
delete FastIS;
SelectionDAGISel::FinishBasicBlock() {
LLVM_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");
// Next, now that we know what the last MBB the LLVM BB expanded is, update
// PHI nodes in successors.
for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
// Handle stack protector.
if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
// The target provides a guard check function. There is no need to
// generate error handling code or to split current basic block.
MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
// Add load and check to the basicblock.
FuncInfo->MBB = ParentMBB;
FuncInfo->InsertPt =
findSplitPointForStackProtector(ParentMBB, *TII);
SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
// Clear the Per-BB State.
} else if (SDB->SPDescriptor.shouldEmitStackProtector()) {
MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
// Find the split point to split the parent mbb. At the same time copy all
// physical registers used in the tail of parent mbb into virtual registers
// before the split point and back into physical registers after the split
// point. This prevents us needing to deal with Live-ins and many other
// register allocation issues caused by us splitting the parent mbb. The
// register allocator will clean up said virtual copies later on.
MachineBasicBlock::iterator SplitPoint =
findSplitPointForStackProtector(ParentMBB, *TII);
// Splice the terminator of ParentMBB into SuccessMBB.
SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
// Add compare/jump on neq/jump to the parent BB.
FuncInfo->MBB = ParentMBB;
FuncInfo->InsertPt = ParentMBB->end();
SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
// CodeGen Failure MBB if we have not codegened it yet.
MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
if (FailureMBB->empty()) {
FuncInfo->MBB = FailureMBB;
FuncInfo->InsertPt = FailureMBB->end();
// Clear the Per-BB State.
// Lower each BitTestBlock.
for (auto &BTB : SDB->SL->BitTestCases) {
// Lower header first, if it wasn't already lowered
if (!BTB.Emitted) {
// Set the current basic block to the mbb we wish to insert the code into
FuncInfo->MBB = BTB.Parent;
FuncInfo->InsertPt = FuncInfo->MBB->end();
// Emit the code
SDB->visitBitTestHeader(BTB, FuncInfo->MBB);
BranchProbability UnhandledProb = BTB.Prob;
for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
UnhandledProb -= BTB.Cases[j].ExtraProb;
// Set the current basic block to the mbb we wish to insert the code into
FuncInfo->MBB = BTB.Cases[j].ThisBB;
FuncInfo->InsertPt = FuncInfo->MBB->end();
// Emit the code
// If all cases cover a contiguous range, it is not necessary to jump to
// the default block after the last bit test fails. This is because the
// range check during bit test header creation has guaranteed that every
// case here doesn't go outside the range. In this case, there is no need
// to perform the last bit test, as it will always be true. Instead, make
// the second-to-last bit-test fall through to the target of the last bit
// test, and delete the last bit test.
MachineBasicBlock *NextMBB;
if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {
// Second-to-last bit-test with contiguous range or omitted range
// check: fall through to the target of the final bit test.
NextMBB = BTB.Cases[j + 1].TargetBB;
} else if (j + 1 == ej) {
// For the last bit test, fall through to Default.
NextMBB = BTB.Default;
} else {
// Otherwise, fall through to the next bit test.
NextMBB = BTB.Cases[j + 1].ThisBB;
SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {
// Since we're not going to use the final bit test, remove it.
// Update PHI Nodes
for (const std::pair<MachineInstr *, unsigned> &P :
FuncInfo->PHINodesToUpdate) {
MachineInstrBuilder PHI(*MF, P.first);
MachineBasicBlock *PHIBB = PHI->getParent();
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
// This is "default" BB. We have two jumps to it. From "header" BB and
// from last "case" BB, unless the latter was skipped.
if (PHIBB == BTB.Default) {
if (!BTB.ContiguousRange) {
// One of "cases" BB.
for (const SwitchCG::BitTestCase &BT : BTB.Cases) {
MachineBasicBlock* cBB = BT.ThisBB;
if (cBB->isSuccessor(PHIBB))
// If the JumpTable record is filled in, then we need to emit a jump table.
// Updating the PHI nodes is tricky in this case, since we need to determine
// whether the PHI is a successor of the range check MBB or the jump table MBB
for (unsigned i = 0, e = SDB->SL->JTCases.size(); i != e; ++i) {
// Lower header first, if it wasn't already lowered
if (!SDB->SL->JTCases[i].first.Emitted) {
// Set the current basic block to the mbb we wish to insert the code into
FuncInfo->MBB = SDB->SL->JTCases[i].first.HeaderBB;
FuncInfo->InsertPt = FuncInfo->MBB->end();
// Emit the code
SDB->SL->JTCases[i].first, FuncInfo->MBB);
// Set the current basic block to the mbb we wish to insert the code into
FuncInfo->MBB = SDB->SL->JTCases[i].second.MBB;
FuncInfo->InsertPt = FuncInfo->MBB->end();
// Emit the code
// Update PHI Nodes
for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
pi != pe; ++pi) {
MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
MachineBasicBlock *PHIBB = PHI->getParent();
assert(PHI->isPHI() &&
"This is not a machine PHI node that we are updating!");
// "default" BB. We can go there only from header BB.
if (PHIBB == SDB->SL->JTCases[i].second.Default)
// JT BB. Just iterate over successors here
if (FuncInfo->MBB->isSuccessor(PHIBB))
// If we generated any switch lowering information, build and codegen any
// additional DAGs necessary.
for (unsigned i = 0, e = SDB->SL->SwitchCases.size(); i != e; ++i) {
// Set the current basic block to the mbb we wish to insert the code into
FuncInfo->MBB = SDB->SL->SwitchCases[i].ThisBB;
FuncInfo->InsertPt = FuncInfo->MBB->end();
// Determine the unique successors.
SmallVector<MachineBasicBlock *, 2> Succs;
if (SDB->SL->SwitchCases[i].TrueBB != SDB->SL->SwitchCases[i].FalseBB)
// Emit the code. Note that this could result in FuncInfo->MBB being split.
SDB->visitSwitchCase(SDB->SL->SwitchCases[i], FuncInfo->MBB);
// Remember the last block, now that any splitting is done, for use in
// populating PHI nodes in successors.
MachineBasicBlock *ThisBB = FuncInfo->MBB;
// Handle any PHI nodes in successors of this chunk, as if we were coming
// from the original BB before switch expansion. Note that PHI nodes can
// occur multiple times in PHINodesToUpdate. We have to be very careful to
// handle them the right number of times.
for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
FuncInfo->MBB = Succs[i];
FuncInfo->InsertPt = FuncInfo->MBB->end();
// FuncInfo->MBB may have been removed from the CFG if a branch was
// constant folded.
if (ThisBB->isSuccessor(FuncInfo->MBB)) {
for (MachineBasicBlock::iterator
MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
MBBI != MBBE && MBBI->isPHI(); ++MBBI) {
MachineInstrBuilder PHI(*MF, MBBI);
// This value for this PHI node is recorded in PHINodesToUpdate.
for (unsigned pn = 0; ; ++pn) {
assert(pn != FuncInfo->PHINodesToUpdate.size() &&
"Didn't find PHI entry!");
if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
/// Create the scheduler. If a specific scheduler was specified
/// via the SchedulerRegistry, use it, otherwise select the
/// one preferred by the target.
ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
return ISHeuristic(this, OptLevel);
// Helper functions used by the generated instruction selector.
// Calls to these methods are generated by tblgen.
/// CheckAndMask - The isel is trying to match something like (and X, 255). If
/// the dag combiner simplified the 255, we still want to match. RHS is the
/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
/// specified in the .td file (e.g. 255).
bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
int64_t DesiredMaskS) const {
const APInt &ActualMask = RHS->getAPIntValue();
const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
// If the actual mask exactly matches, success!
if (ActualMask == DesiredMask)
return true;
// If the actual AND mask is allowing unallowed bits, this doesn't match.
if (!ActualMask.isSubsetOf(DesiredMask))
return false;
// Otherwise, the DAG Combiner may have proven that the value coming in is
// either already zero or is not demanded. Check for known zero input bits.
APInt NeededMask = DesiredMask & ~ActualMask;
if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
return true;
// TODO: check to see if missing bits are just not demanded.
// Otherwise, this pattern doesn't match.
return false;
/// CheckOrMask - The isel is trying to match something like (or X, 255). If
/// the dag combiner simplified the 255, we still want to match. RHS is the
/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
/// specified in the .td file (e.g. 255).
bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
int64_t DesiredMaskS) const {
const APInt &ActualMask = RHS->getAPIntValue();
const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
// If the actual mask exactly matches, success!
if (ActualMask == DesiredMask)
return true;
// If the actual AND mask is allowing unallowed bits, this doesn't match.
if (!ActualMask.isSubsetOf(DesiredMask))
return false;
// Otherwise, the DAG Combiner may have proven that the value coming in is
// either already zero or is not demanded. Check for known zero input bits.
APInt NeededMask = DesiredMask & ~ActualMask;
KnownBits Known = CurDAG->computeKnownBits(LHS);
// If all the missing bits in the or are already known to be set, match!
if (NeededMask.isSubsetOf(Known.One))
return true;
// TODO: check to see if missing bits are just not demanded.
// Otherwise, this pattern doesn't match.
return false;
/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
/// by tblgen. Others should not call it.
void SelectionDAGISel::SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
const SDLoc &DL) {
std::vector<SDValue> InOps;
std::swap(InOps, Ops);
Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0
Ops.push_back(InOps[InlineAsm::Op_AsmString]); // 1
Ops.push_back(InOps[InlineAsm::Op_MDNode]); // 2, !srcloc
Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack)
unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
if (InOps[e-1].getValueType() == MVT::Glue)
--e; // Don't process a glue operand if it is here.
while (i != e) {
InlineAsm::Flag Flags(InOps[i]->getAsZExtVal());
if (!Flags.isMemKind() && !Flags.isFuncKind()) {
// Just skip over this operand, copying the operands verbatim.
Ops.insert(Ops.end(), InOps.begin() + i,
InOps.begin() + i + Flags.getNumOperandRegisters() + 1);
i += Flags.getNumOperandRegisters() + 1;
} else {
assert(Flags.getNumOperandRegisters() == 1 &&
"Memory operand with multiple values?");
unsigned TiedToOperand;
if (Flags.isUseOperandTiedToDef(TiedToOperand)) {
// We need the constraint ID from the operand this is tied to.
unsigned CurOp = InlineAsm::Op_FirstOperand;
Flags = InlineAsm::Flag(InOps[CurOp]->getAsZExtVal());
for (; TiedToOperand; --TiedToOperand) {
CurOp += Flags.getNumOperandRegisters() + 1;
Flags = InlineAsm::Flag(InOps[CurOp]->getAsZExtVal());
// Otherwise, this is a memory operand. Ask the target to select it.
std::vector<SDValue> SelOps;
const InlineAsm::ConstraintCode ConstraintID =
if (SelectInlineAsmMemoryOperand(InOps[i+1], ConstraintID, SelOps))
report_fatal_error("Could not match memory address. Inline asm"
" failure!");
// Add this to the output node.
Flags = InlineAsm::Flag(Flags.isMemKind() ? InlineAsm::Kind::Mem
: InlineAsm::Kind::Func,
Ops.push_back(CurDAG->getTargetConstant(Flags, DL, MVT::i32));
llvm::append_range(Ops, SelOps);
i += 2;
// Add the glue input back if present.
if (e != InOps.size())
/// findGlueUse - Return use of MVT::Glue value produced by the specified
/// SDNode.
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 nullptr;
/// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path
/// beyond "ImmedUse". We may ignore chains as they are checked separately.
static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,
bool IgnoreChains) {
SmallPtrSet<const SDNode *, 16> Visited;
SmallVector<const SDNode *, 16> WorkList;
// Only check if we have non-immediate uses of Def.
if (ImmedUse->isOnlyUserOf(Def))
return false;
// We don't care about paths to Def that go through ImmedUse so mark it
// visited and mark non-def operands as used.
for (const SDValue &Op : ImmedUse->op_values()) {
SDNode *N = Op.getNode();
// Ignore chain deps (they are validated by
// HandleMergeInputChains) and immediate uses
if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
if (!Visited.insert(N).second)
// Initialize worklist to operands of Root.
if (Root != ImmedUse) {
for (const SDValue &Op : Root->op_values()) {
SDNode *N = Op.getNode();
// Ignore chains (they are validated by HandleMergeInputChains)
if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
if (!Visited.insert(N).second)
return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);
/// IsProfitableToFold - Returns true if it's profitable to fold the specific
/// operand node N of U during instruction selection that starts at Root.
bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
SDNode *Root) const {
if (OptLevel == CodeGenOptLevel::None)
return false;
return N.hasOneUse();
/// IsLegalToFold - Returns true if the specific operand node N of
/// U can be folded during instruction selection that starts at Root.
bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
CodeGenOptLevel OptLevel,
bool IgnoreChains) {
if (OptLevel == CodeGenOptLevel::None)
return false;
// If Root use can somehow reach N through a path that doesn't contain
// U then folding N would create a cycle. e.g. In the following
// diagram, Root can reach N through X. If N is folded into Root, then
// X is both a predecessor and a successor of U.
// [N*] //
// ^ ^ //
// / \ //
// [U*] [X]? //
// ^ ^ //
// \ / //
// \ / //
// [Root*] //
// * indicates nodes to be folded together.
// If Root produces glue, then it gets (even more) interesting. Since it
// will be "glued" together with its glue use in the scheduler, we need to
// check if it might reach N.
// [N*] //
// ^ ^ //
// / \ //
// [U*] [X]? //
// ^ ^ //
// \ \ //
// \ | //
// [Root*] | //
// ^ | //
// f | //
// | / //
// [Y] / //
// ^ / //
// f / //
// | / //
// [GU] //
// If GU (glue use) indirectly reaches N (the load), and Root folds N
// (call it Fold), then X is a predecessor of GU and a successor of
// Fold. But since Fold and GU are glued together, this will create
// a cycle in the scheduling graph.
// If the node has glue, walk down the graph to the "lowest" node in the
// glueged set.
EVT VT = Root->getValueType(Root->getNumValues()-1);
while (VT == MVT::Glue) {
SDNode *GU = findGlueUse(Root);
if (!GU)
Root = GU;
VT = Root->getValueType(Root->getNumValues()-1);
// If our query node has a glue result with a use, we've walked up it. If
// the user (which has already been selected) has a chain or indirectly uses
// the chain, HandleMergeInputChains will not consider it. Because of
// this, we cannot ignore chains in this predicate.
IgnoreChains = false;
return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);
void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
SDLoc DL(N);
std::vector<SDValue> Ops(N->op_begin(), N->op_end());
SelectInlineAsmMemoryOperands(Ops, DL);
const EVT VTs[] = {MVT::Other, MVT::Glue};
SDValue New = CurDAG->getNode(N->getOpcode(), DL, VTs, Ops);
ReplaceUses(N, New.getNode());
void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {
SDLoc dl(Op);
MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));
const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));
EVT VT = Op->getValueType(0);
LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();
Register Reg =
TLI->getRegisterByName(RegStr->getString().data(), Ty,
SDValue New = CurDAG->getCopyFromReg(
Op->getOperand(0), dl, Reg, Op->getValueType(0));
ReplaceUses(Op, New.getNode());
void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {
SDLoc dl(Op);
MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));
const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));
EVT VT = Op->getOperand(2).getValueType();
LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();
Register Reg = TLI->getRegisterByName(RegStr->getString().data(), Ty,
SDValue New = CurDAG->getCopyToReg(
Op->getOperand(0), dl, Reg, Op->getOperand(2));
ReplaceUses(Op, New.getNode());
void SelectionDAGISel::Select_UNDEF(SDNode *N) {
CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
void SelectionDAGISel::Select_FREEZE(SDNode *N) {
// TODO: We don't have FREEZE pseudo-instruction in MachineInstr-level now.
// If FREEZE instruction is added later, the code below must be changed as
// well.
CurDAG->SelectNodeTo(N, TargetOpcode::COPY, N->getValueType(0),
void SelectionDAGISel::Select_ARITH_FENCE(SDNode *N) {
CurDAG->SelectNodeTo(N, TargetOpcode::ARITH_FENCE, N->getValueType(0),
void SelectionDAGISel::Select_MEMBARRIER(SDNode *N) {
CurDAG->SelectNodeTo(N, TargetOpcode::MEMBARRIER, N->getValueType(0),
void SelectionDAGISel::Select_CONVERGENCECTRL_ANCHOR(SDNode *N) {
void SelectionDAGISel::Select_CONVERGENCECTRL_ENTRY(SDNode *N) {
CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_ENTRY,
void SelectionDAGISel::Select_CONVERGENCECTRL_LOOP(SDNode *N) {
CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_LOOP,
N->getValueType(0), N->getOperand(0));
void SelectionDAGISel::pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops,
SDValue OpVal, SDLoc DL) {
SDNode *OpNode = OpVal.getNode();
// FrameIndex nodes should have been directly emitted to TargetFrameIndex
// nodes at DAG-construction time.
assert(OpNode->getOpcode() != ISD::FrameIndex);
if (OpNode->getOpcode() == ISD::Constant) {
CurDAG->getTargetConstant(StackMaps::ConstantOp, DL, MVT::i64));
Ops.push_back(CurDAG->getTargetConstant(OpNode->getAsZExtVal(), DL,
} else {
void SelectionDAGISel::Select_STACKMAP(SDNode *N) {
SmallVector<SDValue, 32> Ops;
auto *It = N->op_begin();
SDLoc DL(N);
// Stash the chain and glue operands so we can move them to the end.
SDValue Chain = *It++;
SDValue InGlue = *It++;
// <id> operand.
SDValue ID = *It++;
assert(ID.getValueType() == MVT::i64);
// <numShadowBytes> operand.
SDValue Shad = *It++;
assert(Shad.getValueType() == MVT::i32);
// Live variable operands.
for (; It != N->op_end(); It++)
pushStackMapLiveVariable(Ops, *It, DL);
SDVTList NodeTys = CurDAG->getVTList(MVT::Other, MVT::Glue);
CurDAG->SelectNodeTo(N, TargetOpcode::STACKMAP, NodeTys, Ops);
void SelectionDAGISel::Select_PATCHPOINT(SDNode *N) {
SmallVector<SDValue, 32> Ops;
auto *It = N->op_begin();
SDLoc DL(N);
// Cache arguments that will be moved to the end in the target node.
SDValue Chain = *It++;
std::optional<SDValue> Glue;
if (It->getValueType() == MVT::Glue)
Glue = *It++;
SDValue RegMask = *It++;
// <id> operand.
SDValue ID = *It++;
assert(ID.getValueType() == MVT::i64);
// <numShadowBytes> operand.
SDValue Shad = *It++;
assert(Shad.getValueType() == MVT::i32);
// Add the callee.
// Add <numArgs>.
SDValue NumArgs = *It++;
assert(NumArgs.getValueType() == MVT::i32);
// Calling convention.
// Push the args for the call.
for (uint64_t I = NumArgs->getAsZExtVal(); I != 0; I--)
// Now push the live variables.
for (; It != N->op_end(); It++)
pushStackMapLiveVariable(Ops, *It, DL);
// Finally, the regmask, chain and (if present) glue are moved to the end.
if (Glue.has_value())
SDVTList NodeTys = N->getVTList();
CurDAG->SelectNodeTo(N, TargetOpcode::PATCHPOINT, NodeTys, Ops);
/// GetVBR - decode a vbr encoding whose top bit is set.
GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
assert(Val >= 128 && "Not a VBR");
Val &= 127; // Remove first vbr bit.
unsigned Shift = 7;
uint64_t NextBits;
do {
NextBits = MatcherTable[Idx++];
Val |= (NextBits&127) << Shift;
Shift += 7;
} while (NextBits & 128);
return Val;
void SelectionDAGISel::Select_JUMP_TABLE_DEBUG_INFO(SDNode *N) {
SDLoc dl(N);
CurDAG->SelectNodeTo(N, TargetOpcode::JUMP_TABLE_DEBUG_INFO, MVT::Glue,
dl, MVT::i64, true));
/// When a match is complete, this method updates uses of interior chain results
/// to use the new results.
void SelectionDAGISel::UpdateChains(
SDNode *NodeToMatch, SDValue InputChain,
SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
SmallVector<SDNode*, 4> NowDeadNodes;
// Now that all the normal results are replaced, we replace the chain and
// glue results if present.
if (!ChainNodesMatched.empty()) {
assert(InputChain.getNode() &&
"Matched input chains but didn't produce a chain");
// Loop over all of the nodes we matched that produced a chain result.
// Replace all the chain results with the final chain we ended up with.
for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
SDNode *ChainNode = ChainNodesMatched[i];
// If ChainNode is null, it's because we replaced it on a previous
// iteration and we cleared it out of the map. Just skip it.
if (!ChainNode)
assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
"Deleted node left in chain");
// Don't replace the results of the root node if we're doing a
// MorphNodeTo.
if (ChainNode == NodeToMatch && isMorphNodeTo)
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?");
SelectionDAG::DAGNodeDeletedListener NDL(
*CurDAG, [&](SDNode *N, SDNode *E) {
std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
static_cast<SDNode *>(nullptr));
if (ChainNode->getOpcode() != ISD::TokenFactor)
ReplaceUses(ChainVal, InputChain);
// If the node became dead and we haven't already seen it, delete it.
if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
!llvm::is_contained(NowDeadNodes, ChainNode))
if (!NowDeadNodes.empty())
LLVM_DEBUG(dbgs() << "ISEL: Match complete!\n");
/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
/// operation for when the pattern matched at least one node with a chains. The
/// input vector contains a list of all of the chained nodes that we match. We
/// must determine if this is a valid thing to cover (i.e. matching it won't
/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
/// be used as the input node chain for the generated nodes.
static SDValue
HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
SelectionDAG *CurDAG) {
SmallPtrSet<const SDNode *, 16> Visited;
SmallVector<const SDNode *, 8> Worklist;
SmallVector<SDValue, 3> InputChains;
unsigned int Max = 8192;
// Quick exit on trivial merge.
if (ChainNodesMatched.size() == 1)
return ChainNodesMatched[0]->getOperand(0);
// Add chains that aren't already added (internal). Peek through
// token factors.
std::function<void(const SDValue)> AddChains = [&](const SDValue V) {
if (V.getValueType() != MVT::Other)
if (V->getOpcode() == ISD::EntryToken)
if (!Visited.insert(V.getNode()).second)
if (V->getOpcode() == ISD::TokenFactor) {
for (const SDValue &Op : V->op_values())
} else
for (auto *N : ChainNodesMatched) {
while (!Worklist.empty())
// Skip the search if there are no chain dependencies.
if (InputChains.size() == 0)
return CurDAG->getEntryNode();
// If one of these chains is a successor of input, we must have a
// node that is both the predecessor and successor of the
// to-be-merged nodes. Fail.
for (SDValue V : InputChains)
for (auto *N : ChainNodesMatched)
if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))
return SDValue();
// Return merged chain.
if (InputChains.size() == 1)
return InputChains[0];
return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
MVT::Other, InputChains);
/// MorphNode - Handle morphing a node in place for the selector.
SDNode *SelectionDAGISel::
MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
// It is possible we're using MorphNodeTo to replace a node with no
// normal results with one that has a normal result (or we could be
// adding a chain) and the input could have glue and chains as well.
// In this case we need to shift the operands down.
// FIXME: This is a horrible hack and broken in obscure cases, no worse
// than the old isel though.
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;
// Call the underlying SelectionDAG routine to do the transmogrification. Note
// that this deletes operands of the old node that become dead.
SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
// MorphNodeTo can operate in two ways: if an existing node with the
// specified operands exists, it can just return it. Otherwise, it
// updates the node in place to have the requested operands.
if (Res == Node) {
// If we updated the node in place, reset the node ID. To the isel,
// this should be just like a newly allocated machine node.
unsigned ResNumResults = Res->getNumValues();
// Move the glue if needed.
if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
static_cast<unsigned>(OldGlueResultNo) != ResNumResults - 1)
ReplaceUses(SDValue(Node, OldGlueResultNo),
SDValue(Res, ResNumResults - 1));
if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
// Move the chain reference if needed.
if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
static_cast<unsigned>(OldChainResultNo) != ResNumResults - 1)
ReplaceUses(SDValue(Node, OldChainResultNo),
SDValue(Res, ResNumResults - 1));
// Otherwise, no replacement happened because the node already exists. Replace
// Uses of the old node with the new one.
if (Res != Node) {
ReplaceNode(Node, Res);
} else {
return Res;
/// CheckSame - Implements OP_CheckSame.
CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes) {
// Accept if it is exactly the same as a previously recorded node.
unsigned RecNo = MatcherTable[MatcherIndex++];
assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
return N == RecordedNodes[RecNo].first;
/// CheckChildSame - Implements OP_CheckChildXSame.
LLVM_ATTRIBUTE_ALWAYS_INLINE static bool CheckChildSame(
const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes,
unsigned ChildNo) {
if (ChildNo >= N.getNumOperands())
return false; // Match fails if out of range child #.
return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
/// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
CheckPatternPredicate(unsigned Opcode, const unsigned char *MatcherTable,
unsigned &MatcherIndex, const SelectionDAGISel &SDISel) {
bool TwoBytePredNo =
Opcode == SelectionDAGISel::OPC_CheckPatternPredicateTwoByte;
unsigned PredNo =
TwoBytePredNo || Opcode == SelectionDAGISel::OPC_CheckPatternPredicate
? MatcherTable[MatcherIndex++]
: Opcode - SelectionDAGISel::OPC_CheckPatternPredicate0;
if (TwoBytePredNo)
PredNo |= MatcherTable[MatcherIndex++] << 8;
return SDISel.CheckPatternPredicate(PredNo);
/// CheckNodePredicate - Implements OP_CheckNodePredicate.
CheckNodePredicate(unsigned Opcode, const unsigned char *MatcherTable,
unsigned &MatcherIndex, const SelectionDAGISel &SDISel,
SDNode *N) {
unsigned PredNo = Opcode == SelectionDAGISel::OPC_CheckPredicate
? MatcherTable[MatcherIndex++]
: Opcode - SelectionDAGISel::OPC_Chec