Welcome > The LLVM Target Independent Code Generator > Core ISel > Selection Dag

Selection Dag

References:

Pass registration

// llvm/lib/Target/Mips/MipsTargetMachine.cpp

// Install an instruction selector pass using
// the ISelDag to gen Mips code.
bool MipsPassConfig::addInstSelector() {
  DebugLL("adding MipsModuleISelDagPass\n");
  addPass(createMipsModuleISelDagPass());
  DebugLL("adding Mips16ISelDag\n");
  addPass(createMips16ISelDag(getMipsTargetMachine(), getOptLevel()));
  DebugLL("adding MipsSEISelDag\n");
  addPass(createMipsSEISelDag(getMipsTargetMachine(), getOptLevel()));
  DebugLL("done adding MipsSEISelDag\n");
  return false;
}

SelectionDAGISel::runOnMachineFunction()

SelectionDAGISel::runOnMachineFunction(MachineFunction &mf)

SelectionDAGISel::runOnMachineFunction()

bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
  DebugLL("SelectionDAGISel pass on MF: "<< mf.getName() << "\n");

  CurDAG->init(*MF, *ORE, this, LibInfo,
   getAnalysisIfAvailable<LegacyDivergenceAnalysis>());
  
  SDB->init(GFI, AA, LibInfo); // SDB: SelectionDAGBuilder

  MachineBasicBlock *EntryMBB = &MF->front();

  ///////////////////////////////////////////
  // Do selection for all basic blocks.
  //////////////////////////////////////////

  SelectAllBasicBlocks(Fn);

  ///////////////////////////////////////////
  // Post-processing the MIR being generated.
  ///////////////////////////////////////////

  // 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<unsigned, unsigned>::iterator I = FuncInfo->RegFixups.begin(),
                                              E = FuncInfo->RegFixups.end();
       I != E; ++I) {
    unsigned From = I->first;
    unsigned To = I->second;
    // If To is also scheduled to be replaced, find what its ultimate
    // replacement is.
    while (true) {
      DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To);
      if (J == E)
        break;
      To = J->second;
    }
    // Make sure the new register has a sufficiently constrained register class.
    if (Register::isVirtualRegister(From) && Register::isVirtualRegister(To))
      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.clearKillFlags(From);
    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())
        continue;

      MachineBasicBlock::iterator Term = MBB.getFirstTerminator();
      if (Term != MBB.end() && Term->isReturn()) {
        Returns.push_back(&MBB);
        continue;
      }
    }
    TLI->insertCopiesSplitCSR(EntryMBB, Returns);
  }

  for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i){
    // Insert DBG_VALUE instructions for function arguments to the entry block.

    // If Reg is live-in then update debug info to track its copy in a vreg.
  }

  // Determine if there are any calls in this machine function.
  // Determine if there are any Inline ASM in this machine function.

  // Determine if there is a call to setjmp in the machine function.
  MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice());

  // Replace forward-declared registers with the registers containing
  // the desired value.
  ...

  TLI->finalizeLowering(*MF);

  // Release function-specific state. SDB and CurDAG are already cleared
  // at this point.
  FuncInfo->clear();
  
  ////////////////////////////////////////////////////////////////
  LLVM_DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n");
  LLVM_DEBUG(MF->print(dbgs()));
}

SelectionDAGISel::SelectAllBasicBlocks()

// llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
    ...
    // No FastIS
    // Lower arguments to copyFromReg instruction
    LowerArguments(Fn);

    // For every basic block:
    {
      SelectBasicBlock();
      // Block IR -> DAG
      ->> SelectionDAGBuilder::visit(const Instruction &I)
          ->> SelectionDAGBuilder::HandlePHINodesInSuccessorBlocks()
            // 1-1 correspondence between LLVM PHI nodes and Machine PHI nodes,
          ->> vist(I.getOpcode(), I);
             ->> vistXXX(I); // 
      // DAG -> Block MIR
      ->> CodeGenAndEmitDAG();
          ->> Scheduler->EmitSchedule() 
          ->> CurDAG->Clear() // Empty the DAG when CodeGenAndEmitDAG() finishes.

      FinishBasicBlock();
    }
}

vistXXX()

// visit() --> visit##OPCODE()

void SelectionDAGBuilder::visit(unsigned Opcode, const User &I) {
  // Note: this doesn't use InstVisitor, because it has to work with
  // ConstantExpr's in addition to instructions.
  switch (Opcode) {
  default: llvm_unreachable("Unknown instruction type encountered!");
    // Build the switch statement using the Instruction.def file.
#define HANDLE_INST(NUM, OPCODE, CLASS) \
    case Instruction::OPCODE: visit##OPCODE((const CLASS&)I); break;
#include "llvm/IR/Instruction.def"
  }
}

// visitLoad()


void SelectionDAGBuilder::visitLoad(const LoadInst &I) {
  if (I.isAtomic())
    return visitAtomicLoad(I);

  ...

  SDValue DSA = DAG.getNode(ISD::MERGE_VALUES, dl,
                           DAG.getVTList(ValueVTs), Values);
  setValue(&I, DSA);
}

Tracking SDNode Creation

In SelectionDAG::SelectionDAG()

Entry SDNode is created for the DAG.

In SelectionDAGISel::LowerArguments()

Call paths:

SelectionDAGISel::runOnMachineFunction()
-> SelectionDAGISel::SelectAllBasicBlocks()
   -> SelectionDAGISel::LowerArguments()
      -> (SelectionDAGBuilder.cpp: findArgumentCopyElisionCandidates())
      -> MipsTargetLowering::LowerFormalArguments(), create a chain of DAG Nodes as arguments.

Mips Implementation MipsTargetLowering::LowerFormalArguments():

// llvm/lib/Target/Mips/MipsISelLowering.cpp

//===----------------------------------------------------------------------===//
//             Formal Arguments Calling Convention Implementation
//===----------------------------------------------------------------------===//
/// LowerFormalArguments - transform physical registers into virtual registers
/// and generate load operations for arguments places on the stack.
SDValue MipsTargetLowering::LowerFormalArguments(
    SDValue Chain, CallingConv::ID CallConv, bool IsVarArg,
    const SmallVectorImpl<ISD::InputArg> &Ins, const SDLoc &DL,
    SelectionDAG &DAG, SmallVectorImpl<SDValue> &InVals) const {
  MachineFunction &MF = DAG.getMachineFunction();
  MachineFrameInfo &MFI = MF.getFrameInfo();
  MipsFunctionInfo *MipsFI = MF.getInfo<MipsFunctionInfo>();

  MipsFI->setVarArgsFrameIndex(0);
  CCInfo.AllocateStack(ABI.GetCalleeAllocdArgSizeInBytes(CallConv), 1);
  
  // for each (implicit & explict) argument in the function
  for (unsigned i = 0, e = ArgLocs.size(); i != e; ++i){
      // handling byvalue arguments
      copyByValRegs(Chain, DL, OutChains, DAG, Flags, InVals, &*FuncArg,
                        FirstByValReg, LastByValReg, VA, CCInfo);
      // if argument stored in register...
      SDValue ArgValue = DAG.getCopyFromReg(Chain, DL, Reg, RegVT);
      InVals.push_back(ArgValue);
      // if argument not stored in register...
      ArgValue = DAG.getLoad(LocVT, DL, Chain, Addr, MachinePointerInfo());
      InVals.push_back(ArgValue);
  }

}

In SelectionDAGISel::CodeGenAndEmitDAG()

Here all the CurDAG nodes are dumped.

Tracking SDNode Replacement

SDNode can be replaced during DAG optmization stages for a basic block.

DAG based optimization is driven by function SelectionDAGISel::CodeGenAndEmitDAG().

It includes the following stages:

Run DAG Combiner in pre-legalize mode

code: DAG Combiner 1

Passing info across DAG via DAG node

To pass srcloc MetaData across DAG for inline ASM, use MDNodeSDNode.

// llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

  // If we have a !srcloc metadata node associated with it, we want to attach
  // this to the ultimately generated inline asm machineinstr.  To do this, we
  // pass in the third operand as this (potentially null) inline asm MDNode.
  const MDNode *SrcLoc = CS.getInstruction()->getMetadata("srcloc");
  AsmNodeOperands.push_back(DAG.getMDNode(SrcLoc));

Code Learning

To detect a return block in a Function:

// see SelectionDAGISel::runOnMachineFunction()
// in llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

// Collect all the return blocks.
for (const BasicBlock &BB : Fn) {
if (!succ_empty(&BB))
   continue;
// handle return blocks: 
}

To scan a DAG (e.g. check for cycles):

// llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp


void llvm::checkForCycles(const llvm::SDNode *N,
                      const llvm::SelectionDAG *DAG,
                      bool force) {
#ifndef NDEBUG
bool check = force;
#ifdef EXPENSIVE_CHECKS
check = true;
#endif  // EXPENSIVE_CHECKS
if (check) {
assert(N && "Checking nonexistent SDNode");
SmallPtrSet<const SDNode*, 32> visited;
SmallPtrSet<const SDNode*, 32> checked;
checkForCyclesHelper(N, visited, checked, DAG);
}
#endif  // !NDEBUG
}


static void checkForCyclesHelper(const SDNode *N,
                             SmallPtrSetImpl<const SDNode*> &Visited,
                             SmallPtrSetImpl<const SDNode*> &Checked,
                             const llvm::SelectionDAG *DAG) {
// If this node has already been checked, don't check it again.
if (Checked.count(N))
return;

// If a node has already been visited on this depth-first walk, reject it as
// a cycle.
if (!Visited.insert(N).second) {
errs() << "Detected cycle in SelectionDAG\n";
dbgs() << "Offending node:\n";
N->dumprFull(DAG); dbgs() << "\n";
abort();
}

for (const SDValue &Op : N->op_values())
checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);

Checked.insert(N);
Visited.erase(N);
}

Legalize

References: llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp // llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp /// This is the entry point for the file. void SelectionDAG::Legalize() { AssignTopologicalOrder(); SmallPtrSet<SDNode *, 16> LegalizedNodes; ... SelectionDAGLegalize Legalizer(*this, LegalizedNodes); // Visit all the nodes. We start in topological order, so that we see // nodes with their original operands intact. Legalization can produce // new nodes which may themselves need to be legalized. Iterate until all // nodes have been legalized. while (true) { bool AnyLegalized = false; for (auto NI = allnodes_end(); NI !

Legalize Types

Some DAG node will be replaced in this pass over the DAG nodes for a basic block. References: llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp /// This is the main entry point for the type legalizer. This does a top-down /// traversal of the dag, legalizing types as it goes. Returns "true" if it made /// any changes. bool DAGTypeLegalizer::run() { bool Changed = false; // 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.

Instr Emission

Reference reference Overview // llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { ... // No FastIS // Lower arguments to copyFromReg instruction LowerArguments(Fn); // For every basic block: { SelectBasicBlock(); // Block IR -> DAG ->> SelectionDAGBuilder::visit(const Instruction &I) ->> SelectionDAGBuilder::HandlePHINodesInSuccessorBlocks() // 1-1 correspondence between LLVM PHI nodes and Machine PHI nodes, ->> vist(I.getOpcode(), I); ->> vistXXX(I); // // DAG -> Block MIR ->> CodeGenAndEmitDAG(); ->> Scheduler->EmitSchedule() ->> CurDAG->Clear() // Empty the DAG when CodeGenAndEmitDAG() finishes.

If you could revise
the fundmental principles of
computer system design
to improve security...

... what would you change?