/// 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) {
  InstrEmitter Emitter(BB, InsertPos);
  DenseMap<SDValue, unsigned> VRBaseMap;
  DenseMap<SUnit*, unsigned> CopyVRBaseMap;
  SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders;
  SmallSet<unsigned, 8> Seen;
  bool HasDbg = DAG->hasDebugValues();

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

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

  // If this is the first BB, emit byval parameter dbg_value's.
  if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
    SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();
    SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();
    for (; PDI != PDE; ++PDI) {
      MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
      if (DbgMI) {
        BB->insert(InsertPos, DbgMI);
        // We re-emit the dbg_value closer to its use, too, after instructions
        // are emitted to the BB.
        (*PDI)->clearIsEmitted();
      }
    }
  }

  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
    SUnit *SU = Sequence[i];
    if (!SU) {
      // Null SUnit* is a noop.
      TII->insertNoop(*Emitter.getBlock(), InsertPos);
      continue;
    }

    // For pre-regalloc scheduling, create instructions corresponding to the
    // SDNode and any glued SDNodes and append them to the block.
    if (!SU->getNode()) {
      // Emit a copy.
      EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
      continue;
    }

    SmallVector<SDNode *, 4> GluedNodes;
    for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
      GluedNodes.push_back(N);
    while (!GluedNodes.empty()) {
      SDNode *N = GluedNodes.back();
      auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
      // Remember the source order of the inserted instruction.
      if (HasDbg)
        ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);
      GluedNodes.pop_back();
    }
    auto NewInsn =
        EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
    // Remember the source order of the inserted instruction.
    if (HasDbg)
      ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
                        NewInsn);
  }

  // Insert all the dbg_values which have not already been inserted in source
  // order sequence.
  if (HasDbg) {
    MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();

    // Sort the source order instructions and use the order to insert debug
//.........这里部分代码省略.........

/// run - 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.
  HandleSDNode Dummy(DAG.getRoot());
  Dummy.setNodeId(Unanalyzed);

  // The root of the dag may dangle to deleted nodes until the type legalizer is
  // done.  Set it to null to avoid confusion.
  DAG.setRoot(SDValue());

  // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess'
  // (and remembering them) if they are leaves and assigning 'Unanalyzed' if
  // non-leaves.
  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
       E = DAG.allnodes_end(); I != E; ++I) {
    if (I->getNumOperands() == 0) {
      I->setNodeId(ReadyToProcess);
      Worklist.push_back(I);
    } else {
      I->setNodeId(Unanalyzed);
    }
  }

  // Now that we have a set of nodes to process, handle them all.
  while (!Worklist.empty()) {
#ifndef XDEBUG
    if (EnableExpensiveChecks)
#endif
      PerformExpensiveChecks();

    SDNode *N = Worklist.back();
    Worklist.pop_back();
    assert(N->getNodeId() == ReadyToProcess &&
           "Node should be ready if on worklist!");

    if (IgnoreNodeResults(N))
      goto ScanOperands;

    // Scan the values produced by the node, checking to see if any result
    // types are illegal.
    for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) {
      EVT ResultVT = N->getValueType(i);
      switch (getTypeAction(ResultVT)) {
      case TargetLowering::TypeLegal:
        break;
      // The following calls must take care of *all* of the node's results,
      // not just the illegal result they were passed (this includes results
      // with a legal type).  Results can be remapped using ReplaceValueWith,
      // or their promoted/expanded/etc values registered in PromotedIntegers,
      // ExpandedIntegers etc.
      case TargetLowering::TypePromoteInteger:
        PromoteIntegerResult(N, i);
        Changed = true;
        goto NodeDone;
      case TargetLowering::TypeExpandInteger:
        ExpandIntegerResult(N, i);
        Changed = true;
        goto NodeDone;
      case TargetLowering::TypeSoftenFloat:
        SoftenFloatResult(N, i);
        Changed = true;
        goto NodeDone;
      case TargetLowering::TypeExpandFloat:
        ExpandFloatResult(N, i);
        Changed = true;
        goto NodeDone;
      case TargetLowering::TypeScalarizeVector:
        ScalarizeVectorResult(N, i);
        Changed = true;
        goto NodeDone;
      case TargetLowering::TypeSplitVector:
        SplitVectorResult(N, i);
        Changed = true;
        goto NodeDone;
      case TargetLowering::TypeWidenVector:
        WidenVectorResult(N, i);
        Changed = true;
        goto NodeDone;
      }
    }

ScanOperands:
    // Scan the operand list for the node, handling any nodes with operands that
    // are illegal.
    {
    unsigned NumOperands = N->getNumOperands();
    bool NeedsReanalyzing = false;
    unsigned i;
    for (i = 0; i != NumOperands; ++i) {
      if (IgnoreNodeResults(N->getOperand(i).getNode()))
        continue;

      EVT OpVT = N->getOperand(i).getValueType();
      switch (getTypeAction(OpVT)) {
//.........这里部分代码省略.........

/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them.
/// This function finds loads of the same base and different offsets. If the
/// offsets are not far apart (target specific), it add MVT::Glue inputs and
/// outputs to ensure they are scheduled together and in order. This
/// optimization may benefit some targets by improving cache locality.
void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
  SDNode *Chain = 0;
  unsigned NumOps = Node->getNumOperands();
  if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
    Chain = Node->getOperand(NumOps-1).getNode();
  if (!Chain)
    return;

  // Look for other loads of the same chain. Find loads that are loading from
  // the same base pointer and different offsets.
  SmallPtrSet<SDNode*, 16> Visited;
  SmallVector<int64_t, 4> Offsets;
  DenseMap<long long, SDNode*> O2SMap;  // Map from offset to SDNode.
  bool Cluster = false;
  SDNode *Base = Node;
  for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
       I != E; ++I) {
    SDNode *User = *I;
    if (User == Node || !Visited.insert(User))
      continue;
    int64_t Offset1, Offset2;
    if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
        Offset1 == Offset2)
      // FIXME: Should be ok if they addresses are identical. But earlier
      // optimizations really should have eliminated one of the loads.
      continue;
    if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
      Offsets.push_back(Offset1);
    O2SMap.insert(std::make_pair(Offset2, User));
    Offsets.push_back(Offset2);
    if (Offset2 < Offset1)
      Base = User;
    Cluster = true;
  }

  if (!Cluster)
    return;

  // Sort them in increasing order.
  std::sort(Offsets.begin(), Offsets.end());

  // Check if the loads are close enough.
  SmallVector<SDNode*, 4> Loads;
  unsigned NumLoads = 0;
  int64_t BaseOff = Offsets[0];
  SDNode *BaseLoad = O2SMap[BaseOff];
  Loads.push_back(BaseLoad);
  for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
    int64_t Offset = Offsets[i];
    SDNode *Load = O2SMap[Offset];
    if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
      break; // Stop right here. Ignore loads that are further away.
    Loads.push_back(Load);
    ++NumLoads;
  }

  if (NumLoads == 0)
    return;

  // Cluster loads by adding MVT::Glue outputs and inputs. This also
  // ensure they are scheduled in order of increasing addresses.
  SDNode *Lead = Loads[0];
  AddGlue(Lead, SDValue(0, 0), true, DAG);

  SDValue InGlue = SDValue(Lead, Lead->getNumValues() - 1);
  for (unsigned I = 1, E = Loads.size(); I != E; ++I) {
    bool OutGlue = I < E - 1;
    SDNode *Load = Loads[I];

    AddGlue(Load, InGlue, OutGlue, DAG);

    if (OutGlue)
      InGlue = SDValue(Load, Load->getNumValues() - 1);

    ++LoadsClustered;
  }
}

/// EmitMachineNode - Generate machine code for a target-specific node and
/// needed dependencies.
///
void InstrEmitter::
EmitMachineNode(SDNode *Node, bool IsClone, bool IsCloned,
                DenseMap<SDValue, unsigned> &VRBaseMap) {
  unsigned Opc = Node->getMachineOpcode();

  // Handle subreg insert/extract specially
  if (Opc == TargetOpcode::EXTRACT_SUBREG ||
      Opc == TargetOpcode::INSERT_SUBREG ||
      Opc == TargetOpcode::SUBREG_TO_REG) {
    EmitSubregNode(Node, VRBaseMap, IsClone, IsCloned);
    return;
  }

  // Handle COPY_TO_REGCLASS specially.
  if (Opc == TargetOpcode::COPY_TO_REGCLASS) {
    EmitCopyToRegClassNode(Node, VRBaseMap);
    return;
  }

  // Handle REG_SEQUENCE specially.
  if (Opc == TargetOpcode::REG_SEQUENCE) {
    EmitRegSequence(Node, VRBaseMap, IsClone, IsCloned);
    return;
  }

  if (Opc == TargetOpcode::IMPLICIT_DEF)
    // We want a unique VR for each IMPLICIT_DEF use.
    return;

  const MCInstrDesc &II = TII->get(Opc);
  unsigned NumResults = CountResults(Node);
  unsigned NumDefs = II.getNumDefs();
  const MCPhysReg *ScratchRegs = nullptr;

  // Handle STACKMAP and PATCHPOINT specially and then use the generic code.
  if (Opc == TargetOpcode::STACKMAP || Opc == TargetOpcode::PATCHPOINT) {
    // Stackmaps do not have arguments and do not preserve their calling
    // convention. However, to simplify runtime support, they clobber the same
    // scratch registers as AnyRegCC.
    unsigned CC = CallingConv::AnyReg;
    if (Opc == TargetOpcode::PATCHPOINT) {
      CC = Node->getConstantOperandVal(PatchPointOpers::CCPos);
      NumDefs = NumResults;
    }
    ScratchRegs = TLI->getScratchRegisters((CallingConv::ID) CC);
  }

  unsigned NumImpUses = 0;
  unsigned NodeOperands =
    countOperands(Node, II.getNumOperands() - NumDefs, NumImpUses);
  bool HasPhysRegOuts = NumResults > NumDefs && II.getImplicitDefs()!=nullptr;
#ifndef NDEBUG
  unsigned NumMIOperands = NodeOperands + NumResults;
  if (II.isVariadic())
    assert(NumMIOperands >= II.getNumOperands() &&
           "Too few operands for a variadic node!");
  else
    assert(NumMIOperands >= II.getNumOperands() &&
           NumMIOperands <= II.getNumOperands() + II.getNumImplicitDefs() +
                            NumImpUses &&
           "#operands for dag node doesn't match .td file!");
#endif

  // Create the new machine instruction.
  MachineInstrBuilder MIB = BuildMI(*MF, Node->getDebugLoc(), II);

  // Add result register values for things that are defined by this
  // instruction.
  if (NumResults) {
    CreateVirtualRegisters(Node, MIB, II, IsClone, IsCloned, VRBaseMap);

    // Transfer any IR flags from the SDNode to the MachineInstr
    MachineInstr *MI = MIB.getInstr();
    const SDNodeFlags Flags = Node->getFlags();
    if (Flags.hasNoSignedZeros())
      MI->setFlag(MachineInstr::MIFlag::FmNsz);

    if (Flags.hasAllowReciprocal())
      MI->setFlag(MachineInstr::MIFlag::FmArcp);

    if (Flags.hasNoNaNs())
      MI->setFlag(MachineInstr::MIFlag::FmNoNans);

    if (Flags.hasNoInfs())
      MI->setFlag(MachineInstr::MIFlag::FmNoInfs);

    if (Flags.hasAllowContract())
      MI->setFlag(MachineInstr::MIFlag::FmContract);

    if (Flags.hasApproximateFuncs())
      MI->setFlag(MachineInstr::MIFlag::FmAfn);

    if (Flags.hasAllowReassociation())
      MI->setFlag(MachineInstr::MIFlag::FmReassoc);
  }

  // Emit all of the actual operands of this instruction, adding them to the
//.........这里部分代码省略.........

// Note: branch conditions, by definition, only have a chain user.
// This is why it should not be saved in a map for recall.
Value* ARMIREmitter::visitBRCOND(const SDNode *N) {
  // Get the address
  const ConstantSDNode *DestNode = dyn_cast<ConstantSDNode>(N->getOperand(0));
  if (!DestNode) {
    printError("visitBRCOND: Not a constant integer for branch!");
    return NULL;
  }

  uint64_t DestInt = DestNode->getSExtValue();
  uint64_t PC = Dec->getDisassembler()->getDebugOffset(N->getDebugLoc());
  // Note: pipeline is 8 bytes
  uint64_t Tgt = PC + 8 + DestInt;

  Function *F = IRB->GetInsertBlock()->getParent();
  BasicBlock *CurBB = IRB->GetInsertBlock();

  BasicBlock *BBTgt = Dec->getOrCreateBasicBlock(Tgt, F);

  // Parse the branch condition code
  const ConstantSDNode *CCNode = dyn_cast<ConstantSDNode>(N->getOperand(1));
  if (!CCNode) {
    printError("visitBRCOND: Condition code is not a constant integer!");
    return NULL;
  }
  ARMCC::CondCodes ARMcc = ARMCC::CondCodes(CCNode->getZExtValue());

  // Unconditional branch
  if (ARMcc == ARMCC::AL) {
    Instruction *Br = IRB->CreateBr(BBTgt);
    Br->setDebugLoc(N->getDebugLoc());
    return Br;
  }

  // If not a conditional branch, find the successor block and look at CC
  BasicBlock *NextBB = NULL;
  Function::iterator BI = F->begin(), BE= F->end();
  while (BI != BE && BI->getName() != CurBB->getName()) ++BI;
  ++BI;
  if (BI == BE) {               // NOTE: This should never happen...
    NextBB = Dec->getOrCreateBasicBlock("end", F);
  } else {
    NextBB = &(*BI);
  }


  SDNode *CPSR = N->getOperand(2)->getOperand(1).getNode();
  SDNode *CMPNode = NULL;
  for (SDNode::use_iterator I = CPSR->use_begin(), E = CPSR->use_end(); I != E;
       ++I) {
    if (I->getOpcode() == ISD::CopyToReg) {
      CMPNode = I->getOperand(2).getNode();
    }
  }

  if (CMPNode == NULL) {
    errs() << "ARMIREmitter ERROR: Could not find CMP SDNode for ARMBRCond!\n";
    return NULL;
  }

  Value *Cmp = NULL;
  Value *LHS = visit(CMPNode->getOperand(0).getNode());
  Value *RHS = visit(CMPNode->getOperand(1).getNode());
  // See ARMCC::CondCodes IntCCToARMCC(ISD::CondCode CC); in ARMISelLowering.cpp
  // TODO: Add support for conditions that handle floating point
  switch(ARMcc) {
    default:
      printError("Unknown condition code");
      return NULL;
    case ARMCC::EQ:
      Cmp = IRB->CreateICmpEQ(LHS, RHS);
      break;
    case ARMCC::NE:
      Cmp = IRB->CreateICmpNE(LHS, RHS);
      break;
    case ARMCC::HS:
      // HS - unsigned higher or same (or carry set)
      Cmp = IRB->CreateICmpUGE(LHS, RHS);
      break;
    case ARMCC::LO:
      // LO - unsigned lower (or carry clear)
      Cmp = IRB->CreateICmpULT(LHS, RHS);
      break;
    case ARMCC::MI:
      // MI - minus (negative)
      printError("Condition code MI is not handled at this time!");
      return NULL;
      // break;
    case ARMCC::PL:
      // PL - plus (positive or zero)
      printError("Condition code PL is not handled at this time!");
      return NULL;
      // break;
    case ARMCC::VS:
      // VS - V Set (signed overflow)
      printError("Condition code VS is not handled at this time!");
      return NULL;
      // break;
    case ARMCC::VC:
//.........这里部分代码省略.........

void ScheduleDAGSDNodes::AddSchedEdges() {
  const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>();

  // Check to see if the scheduler cares about latencies.
  bool UnitLatencies = forceUnitLatencies();

  // Pass 2: add the preds, succs, etc.
  for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
    SUnit *SU = &SUnits[su];
    SDNode *MainNode = SU->getNode();

    if (MainNode->isMachineOpcode()) {
      unsigned Opc = MainNode->getMachineOpcode();
      const MCInstrDesc &MCID = TII->get(Opc);
      for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
        if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
          SU->isTwoAddress = true;
          break;
        }
      }
      if (MCID.isCommutable())
        SU->isCommutable = true;
    }

    // Find all predecessors and successors of the group.
    for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
      if (N->isMachineOpcode() &&
          TII->get(N->getMachineOpcode()).getImplicitDefs()) {
        SU->hasPhysRegClobbers = true;
        unsigned NumUsed = InstrEmitter::CountResults(N);
        while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
          --NumUsed;    // Skip over unused values at the end.
        if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
          SU->hasPhysRegDefs = true;
      }

      for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
        SDNode *OpN = N->getOperand(i).getNode();
        if (isPassiveNode(OpN)) continue;   // Not scheduled.
        SUnit *OpSU = &SUnits[OpN->getNodeId()];
        assert(OpSU && "Node has no SUnit!");
        if (OpSU == SU) continue;           // In the same group.

        EVT OpVT = N->getOperand(i).getValueType();
        assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
        bool isChain = OpVT == MVT::Other;

        unsigned PhysReg = 0;
        int Cost = 1;
        // Determine if this is a physical register dependency.
        CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
        assert((PhysReg == 0 || !isChain) &&
               "Chain dependence via physreg data?");
        // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
        // emits a copy from the physical register to a virtual register unless
        // it requires a cross class copy (cost < 0). That means we are only
        // treating "expensive to copy" register dependency as physical register
        // dependency. This may change in the future though.
        if (Cost >= 0 && !StressSched)
          PhysReg = 0;

        // If this is a ctrl dep, latency is 1.
        unsigned OpLatency = isChain ? 1 : OpSU->Latency;
        // Special-case TokenFactor chains as zero-latency.
        if(isChain && OpN->getOpcode() == ISD::TokenFactor)
          OpLatency = 0;

        const SDep &dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data,
                               OpLatency, PhysReg);
        if (!isChain && !UnitLatencies) {
          computeOperandLatency(OpN, N, i, const_cast<SDep &>(dep));
          ST.adjustSchedDependency(OpSU, SU, const_cast<SDep &>(dep));
        }

        if (!SU->addPred(dep) && !dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
          // Multiple register uses are combined in the same SUnit. For example,
          // we could have a set of glued nodes with all their defs consumed by
          // another set of glued nodes. Register pressure tracking sees this as
          // a single use, so to keep pressure balanced we reduce the defs.
          //
          // We can't tell (without more book-keeping) if this results from
          // glued nodes or duplicate operands. As long as we don't reduce
          // NumRegDefsLeft to zero, we handle the common cases well.
          --OpSU->NumRegDefsLeft;
        }
      }
    }
  }
}

/// EmitSubregNode - Generate machine code for subreg nodes.
///
void InstrEmitter::EmitSubregNode(SDNode *Node,
                                  DenseMap<SDValue, unsigned> &VRBaseMap,
                                  bool IsClone, bool IsCloned) {
    unsigned VRBase = 0;
    unsigned Opc = Node->getMachineOpcode();

    // If the node is only used by a CopyToReg and the dest reg is a vreg, use
    // the CopyToReg'd destination register instead of creating a new vreg.
    for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
            UI != E; ++UI) {
        SDNode *User = *UI;
        if (User->getOpcode() == ISD::CopyToReg &&
                User->getOperand(2).getNode() == Node) {
            unsigned DestReg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
            if (TargetRegisterInfo::isVirtualRegister(DestReg)) {
                VRBase = DestReg;
                break;
            }
        }
    }

    if (Opc == TargetOpcode::EXTRACT_SUBREG) {
        // EXTRACT_SUBREG is lowered as %dst = COPY %src:sub.  There are no
        // constraints on the %dst register, COPY can target all legal register
        // classes.
        unsigned SubIdx = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
        const TargetRegisterClass *TRC = TLI->getRegClassFor(Node->getValueType(0));

        unsigned VReg = getVR(Node->getOperand(0), VRBaseMap);
        MachineInstr *DefMI = MRI->getVRegDef(VReg);
        unsigned SrcReg, DstReg, DefSubIdx;
        if (DefMI &&
                TII->isCoalescableExtInstr(*DefMI, SrcReg, DstReg, DefSubIdx) &&
                SubIdx == DefSubIdx) {
            // Optimize these:
            // r1025 = s/zext r1024, 4
            // r1026 = extract_subreg r1025, 4
            // to a copy
            // r1026 = copy r1024
            VRBase = MRI->createVirtualRegister(TRC);
            BuildMI(*MBB, InsertPos, Node->getDebugLoc(),
                    TII->get(TargetOpcode::COPY), VRBase).addReg(SrcReg);
        } else {
            // VReg may not support a SubIdx sub-register, and we may need to
            // constrain its register class or issue a COPY to a compatible register
            // class.
            VReg = ConstrainForSubReg(VReg, SubIdx,
                                      Node->getOperand(0).getValueType(),
                                      Node->getDebugLoc());

            // Create the destreg if it is missing.
            if (VRBase == 0)
                VRBase = MRI->createVirtualRegister(TRC);

            // Create the extract_subreg machine instruction.
            BuildMI(*MBB, InsertPos, Node->getDebugLoc(),
                    TII->get(TargetOpcode::COPY), VRBase).addReg(VReg, 0, SubIdx);
        }
    } else if (Opc == TargetOpcode::INSERT_SUBREG ||
               Opc == TargetOpcode::SUBREG_TO_REG) {
        SDValue N0 = Node->getOperand(0);
        SDValue N1 = Node->getOperand(1);
        SDValue N2 = Node->getOperand(2);
        unsigned SubIdx = cast<ConstantSDNode>(N2)->getZExtValue();

        // Figure out the register class to create for the destreg.  It should be
        // the largest legal register class supporting SubIdx sub-registers.
        // RegisterCoalescer will constrain it further if it decides to eliminate
        // the INSERT_SUBREG instruction.
        //
        //   %dst = INSERT_SUBREG %src, %sub, SubIdx
        //
        // is lowered by TwoAddressInstructionPass to:
        //
        //   %dst = COPY %src
        //   %dst:SubIdx = COPY %sub
        //
        // There is no constraint on the %src register class.
        //
        const TargetRegisterClass *SRC = TLI->getRegClassFor(Node->getValueType(0));
        SRC = TRI->getSubClassWithSubReg(SRC, SubIdx);
        assert(SRC && "No register class supports VT and SubIdx for INSERT_SUBREG");

        if (VRBase == 0 || !SRC->hasSubClassEq(MRI->getRegClass(VRBase)))
            VRBase = MRI->createVirtualRegister(SRC);

        // Create the insert_subreg or subreg_to_reg machine instruction.
        MachineInstr *MI = BuildMI(*MF, Node->getDebugLoc(), TII->get(Opc));
        MI->addOperand(MachineOperand::CreateReg(VRBase, true));

        // If creating a subreg_to_reg, then the first input operand
        // is an implicit value immediate, otherwise it's a register
        if (Opc == TargetOpcode::SUBREG_TO_REG) {
            const ConstantSDNode *SD = cast<ConstantSDNode>(N0);
            MI->addOperand(MachineOperand::CreateImm(SD->getZExtValue()));
        } else
            AddOperand(MI, N0, 0, 0, VRBaseMap, /*IsDebug=*/false,
                       IsClone, IsCloned);
//.........这里部分代码省略.........

/// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an
/// implicit physical register output.
void InstrEmitter::
EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, bool IsCloned,
                unsigned SrcReg, DenseMap<SDValue, unsigned> &VRBaseMap) {
    unsigned VRBase = 0;
    if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
        // Just use the input register directly!
        SDValue Op(Node, ResNo);
        if (IsClone)
            VRBaseMap.erase(Op);
        bool isNew = VRBaseMap.insert(std::make_pair(Op, SrcReg)).second;
        (void)isNew; // Silence compiler warning.
        assert(isNew && "Node emitted out of order - early");
        return;
    }

    // If the node is only used by a CopyToReg and the dest reg is a vreg, use
    // the CopyToReg'd destination register instead of creating a new vreg.
    bool MatchReg = true;
    const TargetRegisterClass *UseRC = NULL;
    EVT VT = Node->getValueType(ResNo);

    // Stick to the preferred register classes for legal types.
    if (TLI->isTypeLegal(VT))
        UseRC = TLI->getRegClassFor(VT);

    if (!IsClone && !IsCloned)
        for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
                UI != E; ++UI) {
            SDNode *User = *UI;
            bool Match = true;
            if (User->getOpcode() == ISD::CopyToReg &&
                    User->getOperand(2).getNode() == Node &&
                    User->getOperand(2).getResNo() == ResNo) {
                unsigned DestReg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
                if (TargetRegisterInfo::isVirtualRegister(DestReg)) {
                    VRBase = DestReg;
                    Match = false;
                } else if (DestReg != SrcReg)
                    Match = false;
            } else {
                for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
                    SDValue Op = User->getOperand(i);
                    if (Op.getNode() != Node || Op.getResNo() != ResNo)
                        continue;
                    EVT VT = Node->getValueType(Op.getResNo());
                    if (VT == MVT::Other || VT == MVT::Glue)
                        continue;
                    Match = false;
                    if (User->isMachineOpcode()) {
                        const MCInstrDesc &II = TII->get(User->getMachineOpcode());
                        const TargetRegisterClass *RC = 0;
                        if (i+II.getNumDefs() < II.getNumOperands())
                            RC = TII->getRegClass(II, i+II.getNumDefs(), TRI);
                        if (!UseRC)
                            UseRC = RC;
                        else if (RC) {
                            const TargetRegisterClass *ComRC =
                                TRI->getCommonSubClass(UseRC, RC);
                            // If multiple uses expect disjoint register classes, we emit
                            // copies in AddRegisterOperand.
                            if (ComRC)
                                UseRC = ComRC;
                        }
                    }
                }
            }
            MatchReg &= Match;
            if (VRBase)
                break;
        }

    const TargetRegisterClass *SrcRC = 0, *DstRC = 0;
    SrcRC = TRI->getMinimalPhysRegClass(SrcReg, VT);

    // Figure out the register class to create for the destreg.
    if (VRBase) {
        DstRC = MRI->getRegClass(VRBase);
    } else if (UseRC) {
        assert(UseRC->hasType(VT) && "Incompatible phys register def and uses!");
        DstRC = UseRC;
    } else {
        DstRC = TLI->getRegClassFor(VT);
    }

    // If all uses are reading from the src physical register and copying the
    // register is either impossible or very expensive, then don't create a copy.
    if (MatchReg && SrcRC->getCopyCost() < 0) {
        VRBase = SrcReg;
    } else {
        // Create the reg, emit the copy.
        VRBase = MRI->createVirtualRegister(DstRC);
        BuildMI(*MBB, InsertPos, Node->getDebugLoc(), TII->get(TargetOpcode::COPY),
                VRBase).addReg(SrcReg);
    }

    SDValue Op(Node, ResNo);
    if (IsClone)
        VRBaseMap.erase(Op);
//.........这里部分代码省略.........

void SelectionDAGBuilder::LowerStatepoint(
    ImmutableStatepoint ISP, MachineBasicBlock *LandingPad /*=nullptr*/) {
  // The basic scheme here is that information about both the original call and
  // the safepoint is encoded in the CallInst.  We create a temporary call and
  // lower it, then reverse engineer the calling sequence.

  NumOfStatepoints++;
  // Clear state
  StatepointLowering.startNewStatepoint(*this);

  ImmutableCallSite CS(ISP.getCallSite());

#ifndef NDEBUG
  // Consistency check. Don't do this for invokes. It would be too
  // expensive to preserve this information across different basic blocks
  if (!CS.isInvoke()) {
    for (const User *U : CS->users()) {
      const CallInst *Call = cast<CallInst>(U);
      if (isGCRelocate(Call))
        StatepointLowering.scheduleRelocCall(*Call);
    }
  }
#endif

#ifndef NDEBUG
  // If this is a malformed statepoint, report it early to simplify debugging.
  // This should catch any IR level mistake that's made when constructing or
  // transforming statepoints.
  ISP.verify();

  // Check that the associated GCStrategy expects to encounter statepoints.
  assert(GFI->getStrategy().useStatepoints() &&
         "GCStrategy does not expect to encounter statepoints");
#endif

  // Lower statepoint vmstate and gcstate arguments
  SmallVector<SDValue, 10> LoweredMetaArgs;
  lowerStatepointMetaArgs(LoweredMetaArgs, ISP, *this);

  // Get call node, we will replace it later with statepoint
  SDNode *CallNode =
      lowerCallFromStatepoint(ISP, LandingPad, *this, PendingExports);

  // Construct the actual GC_TRANSITION_START, STATEPOINT, and GC_TRANSITION_END
  // nodes with all the appropriate arguments and return values.

  // Call Node: Chain, Target, {Args}, RegMask, [Glue]
  SDValue Chain = CallNode->getOperand(0);

  SDValue Glue;
  bool CallHasIncomingGlue = CallNode->getGluedNode();
  if (CallHasIncomingGlue) {
    // Glue is always last operand
    Glue = CallNode->getOperand(CallNode->getNumOperands() - 1);
  }

  // Build the GC_TRANSITION_START node if necessary.
  //
  // The operands to the GC_TRANSITION_{START,END} nodes are laid out in the
  // order in which they appear in the call to the statepoint intrinsic. If
  // any of the operands is a pointer-typed, that operand is immediately
  // followed by a SRCVALUE for the pointer that may be used during lowering
  // (e.g. to form MachinePointerInfo values for loads/stores).
  const bool IsGCTransition =
      (ISP.getFlags() & (uint64_t)StatepointFlags::GCTransition) ==
          (uint64_t)StatepointFlags::GCTransition;
  if (IsGCTransition) {
    SmallVector<SDValue, 8> TSOps;

    // Add chain
    TSOps.push_back(Chain);

    // Add GC transition arguments
    for (const Value *V : ISP.gc_transition_args()) {
      TSOps.push_back(getValue(V));
      if (V->getType()->isPointerTy())
        TSOps.push_back(DAG.getSrcValue(V));
    }

    // Add glue if necessary
    if (CallHasIncomingGlue)
      TSOps.push_back(Glue);

    SDVTList NodeTys = DAG.getVTList(MVT::Other, MVT::Glue);

    SDValue GCTransitionStart =
        DAG.getNode(ISD::GC_TRANSITION_START, getCurSDLoc(), NodeTys, TSOps);

    Chain = GCTransitionStart.getValue(0);
    Glue = GCTransitionStart.getValue(1);
  }

  // TODO: Currently, all of these operands are being marked as read/write in
  // PrologEpilougeInserter.cpp, we should special case the VMState arguments
  // and flags to be read-only.
  SmallVector<SDValue, 40> Ops;

  // Add the <id> and <numBytes> constants.
  Ops.push_back(DAG.getTargetConstant(ISP.getID(), getCurSDLoc(), MVT::i64));
  Ops.push_back(
//.........这里部分代码省略.........

SDNode *AMDGPUDAGToDAGISel::Select(SDNode *N) {
  const R600InstrInfo *TII =
                      static_cast<const R600InstrInfo*>(TM.getInstrInfo());
  unsigned int Opc = N->getOpcode();
  if (N->isMachineOpcode()) {
    return NULL;   // Already selected.
  }
  switch (Opc) {
  default: break;
  case AMDGPUISD::CONST_ADDRESS: {
    for (SDNode::use_iterator I = N->use_begin(), Next = llvm::next(I);
                              I != SDNode::use_end(); I = Next) {
      Next = llvm::next(I);
      if (!I->isMachineOpcode()) {
        continue;
      }
      unsigned Opcode = I->getMachineOpcode();
      bool HasDst = TII->getOperandIdx(Opcode, AMDGPU::OpName::dst) > -1;
      int SrcIdx = I.getOperandNo();
      int SelIdx;
      // Unlike MachineInstrs, SDNodes do not have results in their operand
      // list, so we need to increment the SrcIdx, since
      // R600InstrInfo::getOperandIdx is based on the MachineInstr indices.
      if (HasDst) {
        SrcIdx++;
      }

      SelIdx = TII->getSelIdx(I->getMachineOpcode(), SrcIdx);
      if (SelIdx < 0) {
        continue;
      }

      SDValue CstOffset;
      if (N->getValueType(0).isVector() ||
          !SelectGlobalValueConstantOffset(N->getOperand(0), CstOffset))
        continue;

      // Gather constants values
      int SrcIndices[] = {
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src0),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src1),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src2),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src0_X),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src0_Y),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src0_Z),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src0_W),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src1_X),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src1_Y),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src1_Z),
        TII->getOperandIdx(Opcode, AMDGPU::OpName::src1_W)
      };
      std::vector<unsigned> Consts;
      for (unsigned i = 0; i < sizeof(SrcIndices) / sizeof(int); i++) {
        int OtherSrcIdx = SrcIndices[i];
        int OtherSelIdx = TII->getSelIdx(Opcode, OtherSrcIdx);
        if (OtherSrcIdx < 0 || OtherSelIdx < 0) {
          continue;
        }
        if (HasDst) {
          OtherSrcIdx--;
          OtherSelIdx--;
        }
        if (RegisterSDNode *Reg =
                         dyn_cast<RegisterSDNode>(I->getOperand(OtherSrcIdx))) {
          if (Reg->getReg() == AMDGPU::ALU_CONST) {
            ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(I->getOperand(OtherSelIdx));
            Consts.push_back(Cst->getZExtValue());
          }
        }
      }

      ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(CstOffset);
      Consts.push_back(Cst->getZExtValue());
      if (!TII->fitsConstReadLimitations(Consts))
        continue;

      // Convert back to SDNode indices
      if (HasDst) {
        SrcIdx--;
        SelIdx--;
      }
      std::vector<SDValue> Ops;
      for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
        if (i == SrcIdx) {
          Ops.push_back(CurDAG->getRegister(AMDGPU::ALU_CONST, MVT::f32));
        } else if (i == SelIdx) {
          Ops.push_back(CstOffset);
        } else {
          Ops.push_back(I->getOperand(i));
        }
      }
      CurDAG->UpdateNodeOperands(*I, Ops.data(), Ops.size());
    }
    break;
  }
  case ISD::BUILD_VECTOR: {
    const AMDGPUSubtarget &ST = TM.getSubtarget<AMDGPUSubtarget>();
    if (ST.getGeneration() > AMDGPUSubtarget::NORTHERN_ISLANDS) {
      break;
    }
//.........这里部分代码省略.........

/// Extract call from statepoint, lower it and return pointer to the
/// call node. Also update NodeMap so that getValue(statepoint) will
/// reference lowered call result
static SDNode *
lowerCallFromStatepoint(ImmutableStatepoint ISP, MachineBasicBlock *LandingPad,
                        SelectionDAGBuilder &Builder,
                        SmallVectorImpl<SDValue> &PendingExports) {

  ImmutableCallSite CS(ISP.getCallSite());

  SDValue ActualCallee = Builder.getValue(ISP.getCalledValue());

  assert(CS.getCallingConv() != CallingConv::AnyReg &&
         "anyregcc is not supported on statepoints!");

  Type *DefTy = ISP.getActualReturnType();
  bool HasDef = !DefTy->isVoidTy();

  SDValue ReturnValue, CallEndVal;
  std::tie(ReturnValue, CallEndVal) = Builder.lowerCallOperands(
      ISP.getCallSite(), ImmutableStatepoint::CallArgsBeginPos,
      ISP.getNumCallArgs(), ActualCallee, DefTy, LandingPad,
      false /* IsPatchPoint */);

  SDNode *CallEnd = CallEndVal.getNode();

  // Get a call instruction from the call sequence chain.  Tail calls are not
  // allowed.  The following code is essentially reverse engineering X86's
  // LowerCallTo.
  //
  // We are expecting DAG to have the following form:
  //
  // ch = eh_label (only in case of invoke statepoint)
  //   ch, glue = callseq_start ch
  //   ch, glue = X86::Call ch, glue
  //   ch, glue = callseq_end ch, glue
  //   get_return_value ch, glue
  //
  // get_return_value can either be a CopyFromReg to grab the return value from
  // %RAX, or it can be a LOAD to load a value returned by reference via a stack
  // slot.

  if (HasDef && (CallEnd->getOpcode() == ISD::CopyFromReg ||
                 CallEnd->getOpcode() == ISD::LOAD))
    CallEnd = CallEnd->getOperand(0).getNode();

  assert(CallEnd->getOpcode() == ISD::CALLSEQ_END && "expected!");

  if (HasDef) {
    if (CS.isInvoke()) {
      // Result value will be used in different basic block for invokes
      // so we need to export it now. But statepoint call has a different type
      // than the actuall call. It means that standart exporting mechanism will
      // create register of the wrong type. So instead we need to create
      // register with correct type and save value into it manually.
      // TODO: To eliminate this problem we can remove gc.result intrinsics
      //       completelly and make statepoint call to return a tuple.
      unsigned Reg = Builder.FuncInfo.CreateRegs(ISP.getActualReturnType());
      RegsForValue RFV(
          *Builder.DAG.getContext(), Builder.DAG.getTargetLoweringInfo(),
          Builder.DAG.getDataLayout(), Reg, ISP.getActualReturnType());
      SDValue Chain = Builder.DAG.getEntryNode();

      RFV.getCopyToRegs(ReturnValue, Builder.DAG, Builder.getCurSDLoc(), Chain,
                        nullptr);
      PendingExports.push_back(Chain);
      Builder.FuncInfo.ValueMap[CS.getInstruction()] = Reg;
    } else {
      // The value of the statepoint itself will be the value of call itself.
      // We'll replace the actually call node shortly.  gc_result will grab
      // this value.
      Builder.setValue(CS.getInstruction(), ReturnValue);
    }
  } else {
    // The token value is never used from here on, just generate a poison value
    Builder.setValue(CS.getInstruction(),
                     Builder.DAG.getIntPtrConstant(-1, Builder.getCurSDLoc()));
  }

  return CallEnd->getOperand(0).getNode();
}

/// EmitMachineNode - Generate machine code for a target-specific node and
/// needed dependencies.
///
void InstrEmitter::
EmitMachineNode(SDNode *Node, bool IsClone, bool IsCloned,
                DenseMap<SDValue, unsigned> &VRBaseMap) {
  unsigned Opc = Node->getMachineOpcode();
  
  // Handle subreg insert/extract specially
  if (Opc == TargetOpcode::EXTRACT_SUBREG || 
      Opc == TargetOpcode::INSERT_SUBREG ||
      Opc == TargetOpcode::SUBREG_TO_REG) {
    EmitSubregNode(Node, VRBaseMap, IsClone, IsCloned);
    return;
  }

  // Handle COPY_TO_REGCLASS specially.
  if (Opc == TargetOpcode::COPY_TO_REGCLASS) {
    EmitCopyToRegClassNode(Node, VRBaseMap);
    return;
  }

  // Handle REG_SEQUENCE specially.
  if (Opc == TargetOpcode::REG_SEQUENCE) {
    EmitRegSequence(Node, VRBaseMap, IsClone, IsCloned);
    return;
  }

  if (Opc == TargetOpcode::IMPLICIT_DEF)
    // We want a unique VR for each IMPLICIT_DEF use.
    return;
  
  const TargetInstrDesc &II = TII->get(Opc);
  unsigned NumResults = CountResults(Node);
  unsigned NodeOperands = CountOperands(Node);
  bool HasPhysRegOuts = NumResults > II.getNumDefs() && II.getImplicitDefs()!=0;
#ifndef NDEBUG
  unsigned NumMIOperands = NodeOperands + NumResults;
  if (II.isVariadic())
    assert(NumMIOperands >= II.getNumOperands() &&
           "Too few operands for a variadic node!");
  else
    assert(NumMIOperands >= II.getNumOperands() &&
           NumMIOperands <= II.getNumOperands()+II.getNumImplicitDefs() &&
           "#operands for dag node doesn't match .td file!");
#endif

  // Create the new machine instruction.
  MachineInstr *MI = BuildMI(*MF, Node->getDebugLoc(), II);

  // The MachineInstr constructor adds implicit-def operands. Scan through
  // these to determine which are dead.
  if (MI->getNumOperands() != 0 &&
      Node->getValueType(Node->getNumValues()-1) == MVT::Glue) {
    // First, collect all used registers.
    SmallVector<unsigned, 8> UsedRegs;
    for (SDNode *F = Node->getGluedUser(); F; F = F->getGluedUser())
      if (F->getOpcode() == ISD::CopyFromReg)
        UsedRegs.push_back(cast<RegisterSDNode>(F->getOperand(1))->getReg());
      else {
        // Collect declared implicit uses.
        const TargetInstrDesc &TID = TII->get(F->getMachineOpcode());
        UsedRegs.append(TID.getImplicitUses(),
                        TID.getImplicitUses() + TID.getNumImplicitUses());
        // In addition to declared implicit uses, we must also check for
        // direct RegisterSDNode operands.
        for (unsigned i = 0, e = F->getNumOperands(); i != e; ++i)
          if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(F->getOperand(i))) {
            unsigned Reg = R->getReg();
            if (TargetRegisterInfo::isPhysicalRegister(Reg))
              UsedRegs.push_back(Reg);
          }
      }
    // Then mark unused registers as dead.
    MI->setPhysRegsDeadExcept(UsedRegs, *TRI);
  }
  
  // Add result register values for things that are defined by this
  // instruction.
  if (NumResults)
    CreateVirtualRegisters(Node, MI, II, IsClone, IsCloned, VRBaseMap);
  
  // Emit all of the actual operands of this instruction, adding them to the
  // instruction as appropriate.
  bool HasOptPRefs = II.getNumDefs() > NumResults;
  assert((!HasOptPRefs || !HasPhysRegOuts) &&
         "Unable to cope with optional defs and phys regs defs!");
  unsigned NumSkip = HasOptPRefs ? II.getNumDefs() - NumResults : 0;
  for (unsigned i = NumSkip; i != NodeOperands; ++i)
    AddOperand(MI, Node->getOperand(i), i-NumSkip+II.getNumDefs(), &II,
               VRBaseMap, /*IsDebug=*/false, IsClone, IsCloned);

  // Transfer all of the memory reference descriptions of this instruction.
  MI->setMemRefs(cast<MachineSDNode>(Node)->memoperands_begin(),
                 cast<MachineSDNode>(Node)->memoperands_end());

  // Insert the instruction into position in the block. This needs to
  // happen before any custom inserter hook is called so that the
  // hook knows where in the block to insert the replacement code.
  MBB->insert(InsertPos, MI);
//.........这里部分代码省略.........