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.

      FinishBasicBlock();
    }
}

// CodeGenAndEmitDAG()

CodeGenAndEmitDAG()

Do instruction selection and scheduling using DAG, and generate MIR.

SelectionDAGISel::CodeGenAndEmitDAG()

Emission DAG Nodes to MIR Instructions

This is the last step of ISelDAG algorithm: convert DAG to MIR instructions. After this, DAG will be cleared.

 // DAG ->  Block MIR
void SelectionDAGISel::CodeGenAndEmitDAG() {

  // Instr Selection/Sechduling Optimizations using DAG.
  ...

  // 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);
  }

  // Free the SelectionDAG state, now that we're finished with it.
  CurDAG->clear();
}

Scheduler->EmitSchedule(FuncInfo->InsertPt) will emit the current basic block’s DAG representation into a list of MIR MachineInstruction’s.

ScheduleDAGSDNodes::EmitSchedule()

/// EmitSchedule - Emit the machine code in scheduled order. Return the new
/// InsertPos and MachineBasicBlock that contains this insertion
/// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does
/// not necessarily refer to returned BB. The emitter may split blocks.
MachineBasicBlock *ScheduleDAGSDNodes::
EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
  ...
// Emit a node, and determine where its first instruction is for debuginfo.
  // Zero, one, or multiple instructions can be created when emitting a node.
  auto EmitNode =
      [&](SDNode *Node, bool IsClone, bool IsCloned,
          DenseMap<SDValue, unsigned> &VRBaseMap) -> MachineInstr * {
    // Fetch instruction prior to this, or end() if nonexistant.
    auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {
      if (I == BB->begin())
        return BB->end();
      else
        return std::prev(Emitter.getInsertPos());
    };

    MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());
    Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);
    MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());

    // If the iterator did not change, no instructions were inserted.
    if (Before == After)
      return nullptr;

    MachineInstr *MI;
    if (Before == BB->end()) {
      // There were no prior instructions; the new ones must start at the
      // beginning of the block.
      MI = &Emitter.getBlock()->instr_front();
    } else {
      // Return first instruction after the pre-existing instructions.
      MI = &*std::next(Before);
    }

    if (MI->isCall() && DAG->getTarget().Options.EnableDebugEntryValues)
      MF.addCallArgsForwardingRegs(MI, DAG->getSDCallSiteInfo(Node));
    
    // Lele: transfer the ownership from DAG Node to MIR Instruction
    if (Node->hasCapsuleOwnership()){
      MI->setCapsuleOwnership(Node->getCapsuleOwnership());
      DebugLL("\n-- CapsuleOwnership transferred from DAG: "; Node->dump());
      DebugLLS("\n\tto MIR Instruction: "; MI->dump());
    }
    return MI;
  };
  ...
}

EmitNode()

// llvm/lib/CodeGen/SelectionDAG/InstrEmitter.h

  /// EmitNode - Generate machine code for a node and needed dependencies.
  ///
  void EmitNode(SDNode *Node, bool IsClone, bool IsCloned,
                DenseMap<SDValue, unsigned> &VRBaseMap) {
    if (Node->isMachineOpcode())
      EmitMachineNode(Node, IsClone, IsCloned, VRBaseMap);
    else
      EmitSpecialNode(Node, IsClone, IsCloned, VRBaseMap);
  }
Created Jul 23, 2020 // Last Updated May 18, 2021

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

... what would you change?