ScheduleDAGSDNodes.cpp revision bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33
1343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// 2343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 3343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// The LLVM Compiler Infrastructure 4343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 5343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file is distributed under the University of Illinois Open Source 6343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// License. See LICENSE.TXT for details. 7343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 8343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 9343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 10343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This implements the ScheduleDAG class, which is a base class used by 11343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// scheduling implementation classes. 12343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 13343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 14343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 15343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#define DEBUG_TYPE "pre-RA-sched" 16bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen#include "SDDbgValue.h" 1784fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman#include "ScheduleDAGSDNodes.h" 18bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman#include "InstrEmitter.h" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/SelectionDAG.h" 20343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetMachine.h" 21343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetInstrInfo.h" 22343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetRegisterInfo.h" 23710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin#include "llvm/Target/TargetSubtarget.h" 24c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/DenseMap.h" 25c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 26c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/SmallVector.h" 27c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/Statistic.h" 28343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 29343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/raw_ostream.h" 30343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 31343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 32c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan ChengSTATISTIC(LoadsClustered, "Number of loads clustered together"); 33c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 3479ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 3579ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman : ScheduleDAG(mf) { 36343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 37343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 3847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// Run - perform scheduling. 3947ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// 4047ac0f0c7c39289f5970688154e385be22b7f293Dan Gohmanvoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 4147ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman MachineBasicBlock::iterator insertPos) { 4247ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman DAG = dag; 4347ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman ScheduleDAG::Run(bb, insertPos); 4447ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman} 4547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 46343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 47343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = NewSUnit(Old->getNode()); 48343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->OrigNode = Old->OrigNode; 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = Old->Latency; 50343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = Old->isTwoAddress; 51343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = Old->isCommutable; 52343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->hasPhysRegDefs = Old->hasPhysRegDefs; 533974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 54e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng Old->isCloned = true; 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return SU; 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CheckForPhysRegDependency - Check if the dependency between def and use of 59343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a specified operand is a physical register dependency. If so, returns the 60c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// register and the cost of copying the register. 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 62343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetRegisterInfo *TRI, 63343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrInfo *TII, 64c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng unsigned &PhysReg, int &Cost) { 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 66343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 67343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 68343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 69343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TargetRegisterInfo::isVirtualRegister(Reg)) 70343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 71343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 72343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned ResNo = User->getOperand(2).getResNo(); 73343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Def->isMachineOpcode()) { 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 75343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (ResNo >= II.getNumDefs() && 76c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman PhysReg = Reg; 78c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *RC = 79c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); 80c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng Cost = RC->getCopyCost(); 81c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 82343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 83343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 84343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 85c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Chengstatic void AddFlags(SDNode *N, SDValue Flag, bool AddFlag, 86c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SelectionDAG *DAG) { 87c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<EVT, 4> VTs; 88c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 89c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng VTs.push_back(N->getValueType(i)); 90c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (AddFlag) 91c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng VTs.push_back(MVT::Flag); 92c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<SDValue, 4> Ops; 93c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 94c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Ops.push_back(N->getOperand(i)); 95c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (Flag.getNode()) 96c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Ops.push_back(Flag); 97c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 98c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 99c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng} 100c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 101c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// ClusterNeighboringLoads - Force nearby loads together by "flagging" them. 102c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// This function finds loads of the same base and different offsets. If the 103c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// offsets are not far apart (target specific), it add MVT::Flag inputs and 104c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// outputs to ensure they are scheduled together and in order. This 105c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// optimization may benefit some targets by improving cache locality. 106c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Chengvoid ScheduleDAGSDNodes::ClusterNeighboringLoads() { 107c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallPtrSet<SDNode*, 16> Visited; 108c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<int64_t, 4> Offsets; 109c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 110c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 111c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng E = DAG->allnodes_end(); NI != E; ++NI) { 112c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDNode *Node = &*NI; 113c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (!Node || !Node->isMachineOpcode()) 114c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 115c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 116c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng unsigned Opc = Node->getMachineOpcode(); 117c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng const TargetInstrDesc &TID = TII->get(Opc); 118c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (!TID.mayLoad()) 119c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 120c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 121c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDNode *Chain = 0; 122c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng unsigned NumOps = Node->getNumOperands(); 123c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 124c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Chain = Node->getOperand(NumOps-1).getNode(); 125c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (!Chain) 126c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 127c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 128c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // Look for other loads of the same chain. Find loads that are loading from 129c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // the same base pointer and different offsets. 130c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Visited.clear(); 131c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Offsets.clear(); 132c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng O2SMap.clear(); 133c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng bool Cluster = false; 134c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDNode *Base = Node; 135c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng int64_t BaseOffset; 136c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); 137c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng I != E; ++I) { 138c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDNode *User = *I; 139c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (User == Node || !Visited.insert(User)) 140c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 141c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng int64_t Offset1, Offset2; 142c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || 143c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Offset1 == Offset2) 144c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // FIXME: Should be ok if they addresses are identical. But earlier 145c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // optimizations really should have eliminated one of the loads. 146c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 147c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (O2SMap.insert(std::make_pair(Offset1, Base)).second) 148c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Offsets.push_back(Offset1); 149c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng O2SMap.insert(std::make_pair(Offset2, User)); 150c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Offsets.push_back(Offset2); 151c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (Offset2 < Offset1) { 152c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Base = User; 153c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng BaseOffset = Offset2; 154c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } else { 155c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng BaseOffset = Offset1; 156c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } 157c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Cluster = true; 158c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } 159c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 160c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (!Cluster) 161c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 162c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 163c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // Sort them in increasing order. 164c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng std::sort(Offsets.begin(), Offsets.end()); 165c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 166c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // Check if the loads are close enough. 167c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<SDNode*, 4> Loads; 168c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng unsigned NumLoads = 0; 169c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng int64_t BaseOff = Offsets[0]; 170c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDNode *BaseLoad = O2SMap[BaseOff]; 171c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Loads.push_back(BaseLoad); 172c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 173c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng int64_t Offset = Offsets[i]; 174c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDNode *Load = O2SMap[Offset]; 175c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset, 176c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng NumLoads)) 177c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng break; // Stop right here. Ignore loads that are further away. 178c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Loads.push_back(Load); 179c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng ++NumLoads; 180c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } 181c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 182c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (NumLoads == 0) 183c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 184c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 185c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // Cluster loads by adding MVT::Flag outputs and inputs. This also 186c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // ensure they are scheduled in order of increasing addresses. 187c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDNode *Lead = Loads[0]; 188c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng AddFlags(Lead, SDValue(0,0), true, DAG); 189c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDValue InFlag = SDValue(Lead, Lead->getNumValues()-1); 190c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng for (unsigned i = 1, e = Loads.size(); i != e; ++i) { 191c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng bool OutFlag = i < e-1; 192c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDNode *Load = Loads[i]; 193c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng AddFlags(Load, InFlag, OutFlag, DAG); 194c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (OutFlag) 195c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng InFlag = SDValue(Load, Load->getNumValues()-1); 196c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng ++LoadsClustered; 197c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } 198c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } 199c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng} 200c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 201343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::BuildSchedUnits() { 202343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // During scheduling, the NodeId field of SDNode is used to map SDNodes 203343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // to their associated SUnits by holding SUnits table indices. A value 204343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of -1 means the SDNode does not yet have an associated SUnit. 205e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman unsigned NumNodes = 0; 206343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 207e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 208343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NI->setNodeId(-1); 209e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman ++NumNodes; 210e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman } 211343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 212e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // Reserve entries in the vector for each of the SUnits we are creating. This 213e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 214e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // invalidated. 215e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // FIXME: Multiply by 2 because we may clone nodes during scheduling. 216e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // This is a temporary workaround. 217e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman SUnits.reserve(NumNodes * 2); 218e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman 2193f23744df4809eba94284e601e81489212c974d4Dan Gohman // Check to see if the scheduler cares about latencies. 2203f23744df4809eba94284e601e81489212c974d4Dan Gohman bool UnitLatencies = ForceUnitLatencies(); 2213f23744df4809eba94284e601e81489212c974d4Dan Gohman 222736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner // Add all nodes in depth first order. 223736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SmallVector<SDNode*, 64> Worklist; 224736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SmallPtrSet<SDNode*, 64> Visited; 225736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Worklist.push_back(DAG->getRoot().getNode()); 226736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Visited.insert(DAG->getRoot().getNode()); 227736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner 228736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner while (!Worklist.empty()) { 229736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SDNode *NI = Worklist.pop_back_val(); 230736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner 231736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner // Add all operands to the worklist unless they've already been added. 232736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 233736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner if (Visited.insert(NI->getOperand(i).getNode())) 234736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Worklist.push_back(NI->getOperand(i).getNode()); 235736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner 236343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 237343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman continue; 238343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 239343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If this node has already been processed, stop now. 240343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (NI->getNodeId() != -1) continue; 241343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 242343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *NodeSUnit = NewSUnit(NI); 243343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 244343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // See if anything is flagged to this node, if so, add them to flagged 245343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // nodes. Nodes can have at most one flag input and one flag output. Flags 246db95fa131a229652f925794ca7a5b84e9490050bDan Gohman // are required to be the last operand and result of a node. 247343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 248343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan up to find flagged preds. 249343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *N = NI; 250db95fa131a229652f925794ca7a5b84e9490050bDan Gohman while (N->getNumOperands() && 251825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 252db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N = N->getOperand(N->getNumOperands()-1).getNode(); 253db95fa131a229652f925794ca7a5b84e9490050bDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 254db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N->setNodeId(NodeSUnit->NodeNum); 255343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 256343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 257343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan down to find any flagged succs. 258343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = NI; 259825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 260343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDValue FlagVal(N, N->getNumValues()-1); 261343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 262343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // There are either zero or one users of the Flag result. 263343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman bool HasFlagUse = false; 264343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 265343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman UI != E; ++UI) 266343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (FlagVal.isOperandOf(*UI)) { 267343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman HasFlagUse = true; 268343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 269343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 270343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = *UI; 271343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 272343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 273343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (!HasFlagUse) break; 274343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 275343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 276343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If there are flag operands involved, N is now the bottom-most node 277343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of the sequence of nodes that are flagged together. 278343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update the SUnit. 279343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NodeSUnit->setNode(N); 280343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 281343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 282343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 283787782f4ca0cca2523825131c24a6f78535a3eb8Dan Gohman // Assign the Latency field of NodeSUnit using target-provided information. 2843f23744df4809eba94284e601e81489212c974d4Dan Gohman if (UnitLatencies) 2853f23744df4809eba94284e601e81489212c974d4Dan Gohman NodeSUnit->Latency = 1; 2863f23744df4809eba94284e601e81489212c974d4Dan Gohman else 2873f23744df4809eba94284e601e81489212c974d4Dan Gohman ComputeLatency(NodeSUnit); 288343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 289c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 290c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 291c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::AddSchedEdges() { 292710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 293710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 294dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin // Check to see if the scheduler cares about latencies. 295dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin bool UnitLatencies = ForceUnitLatencies(); 296dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin 297343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Pass 2: add the preds, succs, etc. 298343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 299343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[su]; 300343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *MainNode = SU->getNode(); 301343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 302343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (MainNode->isMachineOpcode()) { 303343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Opc = MainNode->getMachineOpcode(); 304343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &TID = TII->get(Opc); 305343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 306343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 307343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = true; 308343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 309343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 310343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 311343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.isCommutable()) 312343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = true; 313343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 314343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 315343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Find all predecessors and successors of the group. 316343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 317343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode() && 3183974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman TII->get(N->getMachineOpcode()).getImplicitDefs()) { 3193974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = true; 320bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman unsigned NumUsed = InstrEmitter::CountResults(N); 3218cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 3228cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman --NumUsed; // Skip over unused values at the end. 3238cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 3243974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegDefs = true; 3253974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman } 326343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 327343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 328343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *OpN = N->getOperand(i).getNode(); 329343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(OpN)) continue; // Not scheduled. 330343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *OpSU = &SUnits[OpN->getNodeId()]; 331343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpSU && "Node has no SUnit!"); 332343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (OpSU == SU) continue; // In the same group. 333343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 334e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT OpVT = N->getOperand(i).getValueType(); 335825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 336825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson bool isChain = OpVT == MVT::Other; 337343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 338343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned PhysReg = 0; 339c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng int Cost = 1; 340343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Determine if this is a physical register dependency. 341c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 34254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((PhysReg == 0 || !isChain) && 34354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "Chain dependence via physreg data?"); 344c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 345c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // emits a copy from the physical register to a virtual register unless 346c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // it requires a cross class copy (cost < 0). That means we are only 347c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // treating "expensive to copy" register dependency as physical register 348c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // dependency. This may change in the future though. 349c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (Cost >= 0) 350c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng PhysReg = 0; 351710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 352710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin const SDep& dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 353710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin OpSU->Latency, PhysReg); 354dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin if (!isChain && !UnitLatencies) { 355dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin ComputeOperandLatency(OpSU, SU, (SDep &)dep); 356dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin ST.adjustSchedDependency(OpSU, SU, (SDep &)dep); 357dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin } 358710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 359710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin SU->addPred(dep); 360343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 361343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 362343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 363343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 364343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 365c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 366c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// are input. This SUnit graph is similar to the SelectionDAG, but 367c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// excludes nodes that aren't interesting to scheduling, and represents 368c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// flagged together nodes with a single SUnit. 36998976e4dcd18adbbe676048c0069e67346eb4adeDan Gohmanvoid ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 370c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng // Cluster loads from "near" addresses into combined SUnits. 37142dae2d5ba0c22bed65e80ac56a7c304de911c33Evan Cheng ClusterNeighboringLoads(); 372c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Populate the SUnits array. 373c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman BuildSchedUnits(); 374c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Compute all the scheduling dependencies between nodes. 375c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman AddSchedEdges(); 376c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 377c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 378343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 379343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 380343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 381343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Compute the latency for the node. We use the sum of the latencies for 382343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // all nodes flagged together into this SUnit. 383343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = 0; 384c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 385343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode()) { 386dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin SU->Latency += InstrItins. 387dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin getStageLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 388343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 389343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 390343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 391343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 392c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (!SU->getNode()) { 39384fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "PHYS REG COPY\n"; 394c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng return; 395c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 396c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng 397c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SU->getNode()->dump(DAG); 39884fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "\n"; 399343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SmallVector<SDNode *, 4> FlaggedNodes; 400343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 401343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.push_back(N); 402343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (!FlaggedNodes.empty()) { 40384fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << " "; 404343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.back()->dump(DAG); 40584fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "\n"; 406343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.pop_back(); 407343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 408343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 409bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 410bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman/// EmitSchedule - Emit the machine code in scheduled order. 411bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan GohmanMachineBasicBlock *ScheduleDAGSDNodes:: 412bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan GohmanEmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) { 413bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman InstrEmitter Emitter(BB, InsertPos); 414bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman DenseMap<SDValue, unsigned> VRBaseMap; 415bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman DenseMap<SUnit*, unsigned> CopyVRBaseMap; 416bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen 417bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen // For now, any constant debug info nodes go at the beginning. 418bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen for (SDDbgInfo::ConstDbgIterator I = DAG->DbgConstBegin(), 419bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen E = DAG->DbgConstEnd(); I!=E; I++) { 420bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen Emitter.EmitDbgValue(*I, EM); 421bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen delete *I; 422bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen } 423bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen 424bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 425bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman SUnit *SU = Sequence[i]; 426bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman if (!SU) { 427bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // Null SUnit* is a noop. 428bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman EmitNoop(); 429bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman continue; 430bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 431bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 432bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // For pre-regalloc scheduling, create instructions corresponding to the 433bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // SDNode and any flagged SDNodes and append them to the block. 434bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman if (!SU->getNode()) { 435bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // Emit a copy. 436bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman EmitPhysRegCopy(SU, CopyVRBaseMap); 437bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman continue; 438bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 439bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 440bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman SmallVector<SDNode *, 4> FlaggedNodes; 441bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman for (SDNode *N = SU->getNode()->getFlaggedNode(); N; 442bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman N = N->getFlaggedNode()) 443bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman FlaggedNodes.push_back(N); 444bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman while (!FlaggedNodes.empty()) { 445bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman Emitter.EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, SU->isCloned, 446bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman VRBaseMap, EM); 447bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen if (FlaggedNodes.back()->getHasDebugValue()) 448bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen if (SDDbgValue *sd = DAG->GetDbgInfo(FlaggedNodes.back())) { 449bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen Emitter.EmitDbgValue(FlaggedNodes.back(), VRBaseMap, sd); 450bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen delete sd; 451bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen } 452bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman FlaggedNodes.pop_back(); 453bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 454bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 455bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman VRBaseMap, EM); 456bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen if (SU->getNode()->getHasDebugValue()) 457bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen if (SDDbgValue *sd = DAG->GetDbgInfo(SU->getNode())) { 458bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen Emitter.EmitDbgValue(SU->getNode(), VRBaseMap, sd); 459bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen delete sd; 460bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen } 461bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 462bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 463bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman BB = Emitter.getBlock(); 464bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman InsertPos = Emitter.getInsertPos(); 465bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman return BB; 466bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman} 467