ScheduleDAGSDNodes.cpp revision 4c727204271067f3dbf50bd23098b2df8e1cc47a
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" 16a8efe28a44996978faa42a387f1a6087a7b942c7Evan Cheng#include "SDNodeDbgValue.h" 1784fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman#include "ScheduleDAGSDNodes.h" 18bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman#include "InstrEmitter.h" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/SelectionDAG.h" 20ab8be96fd30ca9396e6b84fdddf1ac6208984cadEvan Cheng#include "llvm/MC/MCInstrItineraries.h" 21343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetMachine.h" 22343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetInstrInfo.h" 231cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng#include "llvm/Target/TargetLowering.h" 24343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetRegisterInfo.h" 255b1b4489cf3a0f56f8be0673fc5cc380a32d277bEvan Cheng#include "llvm/Target/TargetSubtargetInfo.h" 26c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/DenseMap.h" 27c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 28bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng#include "llvm/ADT/SmallSet.h" 29c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/SmallVector.h" 30c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/Statistic.h" 31e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick#include "llvm/Support/CommandLine.h" 32343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 33343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/raw_ostream.h" 34343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 35343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 36c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan ChengSTATISTIC(LoadsClustered, "Number of loads clustered together"); 37c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 38e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick// This allows latency based scheduler to notice high latency instructions 39e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick// without a target itinerary. The choise if number here has more to do with 40e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick// balancing scheduler heursitics than with the actual machine latency. 41e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trickstatic cl::opt<int> HighLatencyCycles( 42e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick "sched-high-latency-cycles", cl::Hidden, cl::init(10), 43e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick cl::desc("Roughly estimate the number of cycles that 'long latency'" 44e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick "instructions take for targets with no itinerary")); 45e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick 4679ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 473ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng : ScheduleDAG(mf), 483ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng InstrItins(mf.getTarget().getInstrItineraryData()) {} 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 5047ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// Run - perform scheduling. 5147ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// 5247ac0f0c7c39289f5970688154e385be22b7f293Dan Gohmanvoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 5347ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman MachineBasicBlock::iterator insertPos) { 5447ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman DAG = dag; 5547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman ScheduleDAG::Run(bb, insertPos); 5647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman} 5747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 581cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng/// NewSUnit - Creates a new SUnit and return a ptr to it. 591cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng/// 601cc3984148be113c6e5e470f23c9ddbd37679c5fEvan ChengSUnit *ScheduleDAGSDNodes::NewSUnit(SDNode *N) { 611cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng#ifndef NDEBUG 621cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng const SUnit *Addr = 0; 631cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng if (!SUnits.empty()) 641cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng Addr = &SUnits[0]; 651cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng#endif 661cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 671cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng assert((Addr == 0 || Addr == &SUnits[0]) && 681cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng "SUnits std::vector reallocated on the fly!"); 691cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnits.back().OrigNode = &SUnits.back(); 701cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnit *SU = &SUnits.back(); 711cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 72c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng if (!N || 73c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng (N->isMachineOpcode() && 74c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)) 75046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng SU->SchedulingPref = Sched::None; 76046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng else 77046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng SU->SchedulingPref = TLI.getSchedulingPreference(N); 781cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng return SU; 791cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng} 801cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 81343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 82343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = NewSUnit(Old->getNode()); 83343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->OrigNode = Old->OrigNode; 84343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = Old->Latency; 8554699765064842fd08d1466adc93453660bc2a85Andrew Trick SU->isVRegCycle = Old->isVRegCycle; 868239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng SU->isCall = Old->isCall; 87554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SU->isCallOp = Old->isCallOp; 88343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = Old->isTwoAddress; 89343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = Old->isCommutable; 90343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->hasPhysRegDefs = Old->hasPhysRegDefs; 913974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 9212f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick SU->isScheduleHigh = Old->isScheduleHigh; 9312f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick SU->isScheduleLow = Old->isScheduleLow; 941cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SU->SchedulingPref = Old->SchedulingPref; 95e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng Old->isCloned = true; 96343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return SU; 97343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CheckForPhysRegDependency - Check if the dependency between def and use of 100343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a specified operand is a physical register dependency. If so, returns the 101c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// register and the cost of copying the register. 102343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 103cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick const TargetRegisterInfo *TRI, 104343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrInfo *TII, 105c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng unsigned &PhysReg, int &Cost) { 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 110343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TargetRegisterInfo::isVirtualRegister(Reg)) 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 112343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 113343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned ResNo = User->getOperand(2).getResNo(); 114343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Def->isMachineOpcode()) { 115e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &II = TII->get(Def->getMachineOpcode()); 116343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (ResNo >= II.getNumDefs() && 117c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 118343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman PhysReg = Reg; 119c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *RC = 120d31f972bd33de85071c716f69bf5c6d735f730f2Rafael Espindola TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 121c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng Cost = RC->getCopyCost(); 122c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 123343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 124343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 12629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattnerstatic void AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) { 127c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<EVT, 4> VTs; 12829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SDNode *GlueDestNode = Glue.getNode(); 129151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 13029d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // Don't add glue from a node to itself. 13129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (GlueDestNode == N) return; 13210707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling 13329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // Don't add glue to something which already has glue. 134f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return; 13510707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling 13610707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 13710707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling VTs.push_back(N->getValueType(I)); 138151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 13929d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (AddGlue) 140f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner VTs.push_back(MVT::Glue); 141151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 142c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<SDValue, 4> Ops; 14310707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 14410707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling Ops.push_back(N->getOperand(I)); 145151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 14629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (GlueDestNode) 14729d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner Ops.push_back(Glue); 148151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 149c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 150151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling MachineSDNode::mmo_iterator Begin = 0, End = 0; 151151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 152151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 153151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling // Store memory references. 154151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling if (MN) { 155151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling Begin = MN->memoperands_begin(); 156151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling End = MN->memoperands_end(); 157151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling } 158151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 159c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 160151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 161151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling // Reset the memory references 162151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling if (MN) 163151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling MN->setMemRefs(Begin, End); 164c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng} 165c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 16629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them. 167c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// This function finds loads of the same base and different offsets. If the 168f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner/// offsets are not far apart (target specific), it add MVT::Glue inputs and 169c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// outputs to ensure they are scheduled together and in order. This 170c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// optimization may benefit some targets by improving cache locality. 171302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Chengvoid ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 172302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Chain = 0; 173302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned NumOps = Node->getNumOperands(); 174302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 175302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Chain = Node->getOperand(NumOps-1).getNode(); 176302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Chain) 177302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 178302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng 179302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Look for other loads of the same chain. Find loads that are loading from 180302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // the same base pointer and different offsets. 181c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallPtrSet<SDNode*, 16> Visited; 182c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<int64_t, 4> Offsets; 183c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 184302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng bool Cluster = false; 185302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Base = Node; 186302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); 187302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng I != E; ++I) { 188302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *User = *I; 189302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (User == Node || !Visited.insert(User)) 190c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 191302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t Offset1, Offset2; 192302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || 193302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offset1 == Offset2) 194302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // FIXME: Should be ok if they addresses are identical. But earlier 195302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // optimizations really should have eliminated one of the loads. 196c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 197302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (O2SMap.insert(std::make_pair(Offset1, Base)).second) 198302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offsets.push_back(Offset1); 199302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng O2SMap.insert(std::make_pair(Offset2, User)); 200302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offsets.push_back(Offset2); 201b447c4e65b5f6d39db16cb8fc338133965291972Duncan Sands if (Offset2 < Offset1) 202302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Base = User; 203302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Cluster = true; 204302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 205c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 206302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Cluster) 207302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 208c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 209302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Sort them in increasing order. 210302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng std::sort(Offsets.begin(), Offsets.end()); 211c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 212302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Check if the loads are close enough. 213302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SmallVector<SDNode*, 4> Loads; 214302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned NumLoads = 0; 215302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t BaseOff = Offsets[0]; 216302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *BaseLoad = O2SMap[BaseOff]; 217302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Loads.push_back(BaseLoad); 218302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 219302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t Offset = Offsets[i]; 220302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Load = O2SMap[Offset]; 221302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 222302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng break; // Stop right here. Ignore loads that are further away. 223302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Loads.push_back(Load); 224302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ++NumLoads; 225302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 226c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 227302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (NumLoads == 0) 228302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 229c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 230f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner // Cluster loads by adding MVT::Glue outputs and inputs. This also 231302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // ensure they are scheduled in order of increasing addresses. 232302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Lead = Loads[0]; 23329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner AddGlue(Lead, SDValue(0, 0), true, DAG); 23410707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling 23529d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SDValue InGlue = SDValue(Lead, Lead->getNumValues() - 1); 23610707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 23729d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner bool OutGlue = I < E - 1; 23810707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling SDNode *Load = Loads[I]; 239151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 24029d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner AddGlue(Load, InGlue, OutGlue, DAG); 241151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 24229d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (OutGlue) 24329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner InGlue = SDValue(Load, Load->getNumValues() - 1); 244151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 245302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ++LoadsClustered; 246302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 247302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng} 248c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 249302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng/// ClusterNodes - Cluster certain nodes which should be scheduled together. 250302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng/// 251302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Chengvoid ScheduleDAGSDNodes::ClusterNodes() { 252302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 253302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng E = DAG->allnodes_end(); NI != E; ++NI) { 254302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Node = &*NI; 255302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Node || !Node->isMachineOpcode()) 256c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 257c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 258302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned Opc = Node->getMachineOpcode(); 259e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = TII->get(Opc); 260e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.mayLoad()) 261302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Cluster loads from "near" addresses into combined SUnits. 262302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ClusterNeighboringLoads(Node); 263c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } 264c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng} 265c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 266343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::BuildSchedUnits() { 267343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // During scheduling, the NodeId field of SDNode is used to map SDNodes 268343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // to their associated SUnits by holding SUnits table indices. A value 269343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of -1 means the SDNode does not yet have an associated SUnit. 270e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman unsigned NumNodes = 0; 271343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 272e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 273343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NI->setNodeId(-1); 274e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman ++NumNodes; 275e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman } 276343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 277e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // Reserve entries in the vector for each of the SUnits we are creating. This 278e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 279e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // invalidated. 280e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // FIXME: Multiply by 2 because we may clone nodes during scheduling. 281e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // This is a temporary workaround. 282e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman SUnits.reserve(NumNodes * 2); 283cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 284736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner // Add all nodes in depth first order. 285736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SmallVector<SDNode*, 64> Worklist; 286736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SmallPtrSet<SDNode*, 64> Visited; 287736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Worklist.push_back(DAG->getRoot().getNode()); 288736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Visited.insert(DAG->getRoot().getNode()); 289cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 290554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SmallVector<SUnit*, 8> CallSUnits; 291736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner while (!Worklist.empty()) { 292736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SDNode *NI = Worklist.pop_back_val(); 293cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 294736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner // Add all operands to the worklist unless they've already been added. 295736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 296736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner if (Visited.insert(NI->getOperand(i).getNode())) 297736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Worklist.push_back(NI->getOperand(i).getNode()); 298cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 299343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 300343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman continue; 301cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 302343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If this node has already been processed, stop now. 303343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (NI->getNodeId() != -1) continue; 304cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 305343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *NodeSUnit = NewSUnit(NI); 306cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 30729d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // See if anything is glued to this node, if so, add them to glued 30829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // nodes. Nodes can have at most one glue input and one glue output. Glue 30929d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // is required to be the last operand and result of a node. 310cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 31129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // Scan up to find glued preds. 312343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *N = NI; 313db95fa131a229652f925794ca7a5b84e9490050bDan Gohman while (N->getNumOperands() && 314f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 315db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N = N->getOperand(N->getNumOperands()-1).getNode(); 316db95fa131a229652f925794ca7a5b84e9490050bDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 317db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N->setNodeId(NodeSUnit->NodeNum); 3188239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 3198239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng NodeSUnit->isCall = true; 320343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 321cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 32229d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // Scan down to find any glued succs. 323343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = NI; 324f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner while (N->getValueType(N->getNumValues()-1) == MVT::Glue) { 32529d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SDValue GlueVal(N, N->getNumValues()-1); 326cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 32729d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // There are either zero or one users of the Glue result. 32829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner bool HasGlueUse = false; 329cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 330343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman UI != E; ++UI) 33129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (GlueVal.isOperandOf(*UI)) { 33229d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner HasGlueUse = true; 333343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 334343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 335343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = *UI; 3368239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 3378239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng NodeSUnit->isCall = true; 338343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 339343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 34029d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (!HasGlueUse) break; 341343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 342cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 343554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng if (NodeSUnit->isCall) 344554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng CallSUnits.push_back(NodeSUnit); 345554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng 34612f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick // Schedule zero-latency TokenFactor below any nodes that may increase the 34712f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick // schedule height. Otherwise, ancestors of the TokenFactor may appear to 34812f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick // have false stalls. 34912f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick if (NI->getOpcode() == ISD::TokenFactor) 35012f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick NodeSUnit->isScheduleLow = true; 35112f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick 35229d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // If there are glue operands involved, N is now the bottom-most node 35329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // of the sequence of nodes that are glued together. 354343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update the SUnit. 355343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NodeSUnit->setNode(N); 356343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 357343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 358343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 35992e946630d5f9bb092853b93501387dd216899b9Andrew Trick // Compute NumRegDefsLeft. This must be done before AddSchedEdges. 36092e946630d5f9bb092853b93501387dd216899b9Andrew Trick InitNumRegDefsLeft(NodeSUnit); 36192e946630d5f9bb092853b93501387dd216899b9Andrew Trick 362787782f4ca0cca2523825131c24a6f78535a3eb8Dan Gohman // Assign the Latency field of NodeSUnit using target-provided information. 363e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng ComputeLatency(NodeSUnit); 364343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 365554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng 366554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng // Find all call operands. 367554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng while (!CallSUnits.empty()) { 368554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SUnit *SU = CallSUnits.pop_back_val(); 369554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng for (const SDNode *SUNode = SU->getNode(); SUNode; 370554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SUNode = SUNode->getGluedNode()) { 371554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng if (SUNode->getOpcode() != ISD::CopyToReg) 372554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng continue; 373554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SDNode *SrcN = SUNode->getOperand(2).getNode(); 374554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng if (isPassiveNode(SrcN)) continue; // Not scheduled. 375554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SUnit *SrcSU = &SUnits[SrcN->getNodeId()]; 376554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SrcSU->isCallOp = true; 377554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng } 378554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng } 379c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 380c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 381c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::AddSchedEdges() { 3825b1b4489cf3a0f56f8be0673fc5cc380a32d277bEvan Cheng const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 383710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 384dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin // Check to see if the scheduler cares about latencies. 385dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin bool UnitLatencies = ForceUnitLatencies(); 386dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin 387343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Pass 2: add the preds, succs, etc. 388343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 389343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[su]; 390343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *MainNode = SU->getNode(); 391cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 392343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (MainNode->isMachineOpcode()) { 393343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Opc = MainNode->getMachineOpcode(); 394e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = TII->get(Opc); 395e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { 396e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { 397343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = true; 398343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 399343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 400343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 401e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.isCommutable()) 402343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = true; 403343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 404cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 405343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Find all predecessors and successors of the group. 40629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) { 407343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode() && 4083974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman TII->get(N->getMachineOpcode()).getImplicitDefs()) { 4093974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = true; 410bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman unsigned NumUsed = InstrEmitter::CountResults(N); 4118cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 4128cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman --NumUsed; // Skip over unused values at the end. 4138cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 4143974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegDefs = true; 4153974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman } 416cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 417343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 418343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *OpN = N->getOperand(i).getNode(); 419343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(OpN)) continue; // Not scheduled. 420343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *OpSU = &SUnits[OpN->getNodeId()]; 421343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpSU && "Node has no SUnit!"); 422343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (OpSU == SU) continue; // In the same group. 423343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 424e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT OpVT = N->getOperand(i).getValueType(); 42529d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!"); 426825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson bool isChain = OpVT == MVT::Other; 427343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 428343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned PhysReg = 0; 429c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng int Cost = 1; 430343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Determine if this is a physical register dependency. 431c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 43254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((PhysReg == 0 || !isChain) && 43354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "Chain dependence via physreg data?"); 434c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 435c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // emits a copy from the physical register to a virtual register unless 436c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // it requires a cross class copy (cost < 0). That means we are only 437c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // treating "expensive to copy" register dependency as physical register 438c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // dependency. This may change in the future though. 4394cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick if (Cost >= 0 && !StressSched) 440c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng PhysReg = 0; 441710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 442046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng // If this is a ctrl dep, latency is 1. 443c558bf397257f5ef902bdb45a28e622ee2b5b4f2Andrew Trick unsigned OpLatency = isChain ? 1 : OpSU->Latency; 44487896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick // Special-case TokenFactor chains as zero-latency. 44587896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick if(isChain && OpN->getOpcode() == ISD::TokenFactor) 44687896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick OpLatency = 0; 44787896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick 448046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng const SDep &dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 449046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng OpLatency, PhysReg); 450dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin if (!isChain && !UnitLatencies) { 45115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng ComputeOperandLatency(OpN, N, i, const_cast<SDep &>(dep)); 4523fb150a9024a38872ec4abbc3300e08a8bfc1812Dan Gohman ST.adjustSchedDependency(OpSU, SU, const_cast<SDep &>(dep)); 453dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin } 454710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 4554bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick if (!SU->addPred(dep) && !dep.isCtrl() && OpSU->NumRegDefsLeft > 1) { 45692e946630d5f9bb092853b93501387dd216899b9Andrew Trick // Multiple register uses are combined in the same SUnit. For example, 45792e946630d5f9bb092853b93501387dd216899b9Andrew Trick // we could have a set of glued nodes with all their defs consumed by 45892e946630d5f9bb092853b93501387dd216899b9Andrew Trick // another set of glued nodes. Register pressure tracking sees this as 45992e946630d5f9bb092853b93501387dd216899b9Andrew Trick // a single use, so to keep pressure balanced we reduce the defs. 4604bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick // 4614bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick // We can't tell (without more book-keeping) if this results from 4624bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick // glued nodes or duplicate operands. As long as we don't reduce 4634bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick // NumRegDefsLeft to zero, we handle the common cases well. 46492e946630d5f9bb092853b93501387dd216899b9Andrew Trick --OpSU->NumRegDefsLeft; 46592e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 466343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 467343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 468343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 469343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 470343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 471c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 472c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// are input. This SUnit graph is similar to the SelectionDAG, but 473c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// excludes nodes that aren't interesting to scheduling, and represents 47429d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner/// glued together nodes with a single SUnit. 47598976e4dcd18adbbe676048c0069e67346eb4adeDan Gohmanvoid ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 476302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Cluster certain nodes which should be scheduled together. 477302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ClusterNodes(); 478c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Populate the SUnits array. 479c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman BuildSchedUnits(); 480c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Compute all the scheduling dependencies between nodes. 481c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman AddSchedEdges(); 482c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 483c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 48492e946630d5f9bb092853b93501387dd216899b9Andrew Trick// Initialize NumNodeDefs for the current Node's opcode. 48592e946630d5f9bb092853b93501387dd216899b9Andrew Trickvoid ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() { 48629449448b0f0420dfcf52e278fc01adbf1690d70Eric Christopher // Check for phys reg copy. 48729449448b0f0420dfcf52e278fc01adbf1690d70Eric Christopher if (!Node) 48829449448b0f0420dfcf52e278fc01adbf1690d70Eric Christopher return; 48929449448b0f0420dfcf52e278fc01adbf1690d70Eric Christopher 49092e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (!Node->isMachineOpcode()) { 49192e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (Node->getOpcode() == ISD::CopyFromReg) 49292e946630d5f9bb092853b93501387dd216899b9Andrew Trick NodeNumDefs = 1; 49392e946630d5f9bb092853b93501387dd216899b9Andrew Trick else 49492e946630d5f9bb092853b93501387dd216899b9Andrew Trick NodeNumDefs = 0; 49592e946630d5f9bb092853b93501387dd216899b9Andrew Trick return; 49692e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 49792e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned POpc = Node->getMachineOpcode(); 49892e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (POpc == TargetOpcode::IMPLICIT_DEF) { 49992e946630d5f9bb092853b93501387dd216899b9Andrew Trick // No register need be allocated for this. 50092e946630d5f9bb092853b93501387dd216899b9Andrew Trick NodeNumDefs = 0; 50192e946630d5f9bb092853b93501387dd216899b9Andrew Trick return; 50292e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 50392e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs(); 50492e946630d5f9bb092853b93501387dd216899b9Andrew Trick // Some instructions define regs that are not represented in the selection DAG 50592e946630d5f9bb092853b93501387dd216899b9Andrew Trick // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues. 50692e946630d5f9bb092853b93501387dd216899b9Andrew Trick NodeNumDefs = std::min(Node->getNumValues(), NRegDefs); 50792e946630d5f9bb092853b93501387dd216899b9Andrew Trick DefIdx = 0; 50892e946630d5f9bb092853b93501387dd216899b9Andrew Trick} 50992e946630d5f9bb092853b93501387dd216899b9Andrew Trick 51092e946630d5f9bb092853b93501387dd216899b9Andrew Trick// Construct a RegDefIter for this SUnit and find the first valid value. 51192e946630d5f9bb092853b93501387dd216899b9Andrew TrickScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU, 51292e946630d5f9bb092853b93501387dd216899b9Andrew Trick const ScheduleDAGSDNodes *SD) 51392e946630d5f9bb092853b93501387dd216899b9Andrew Trick : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) { 51492e946630d5f9bb092853b93501387dd216899b9Andrew Trick InitNodeNumDefs(); 51592e946630d5f9bb092853b93501387dd216899b9Andrew Trick Advance(); 51692e946630d5f9bb092853b93501387dd216899b9Andrew Trick} 51792e946630d5f9bb092853b93501387dd216899b9Andrew Trick 51892e946630d5f9bb092853b93501387dd216899b9Andrew Trick// Advance to the next valid value defined by the SUnit. 51992e946630d5f9bb092853b93501387dd216899b9Andrew Trickvoid ScheduleDAGSDNodes::RegDefIter::Advance() { 52092e946630d5f9bb092853b93501387dd216899b9Andrew Trick for (;Node;) { // Visit all glued nodes. 52192e946630d5f9bb092853b93501387dd216899b9Andrew Trick for (;DefIdx < NodeNumDefs; ++DefIdx) { 52292e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (!Node->hasAnyUseOfValue(DefIdx)) 52392e946630d5f9bb092853b93501387dd216899b9Andrew Trick continue; 5244ef4c171dba8e479f5f3fe7acb22e9fe97a4d6f8Andrew Trick ValueType = Node->getValueType(DefIdx); 52592e946630d5f9bb092853b93501387dd216899b9Andrew Trick ++DefIdx; 52692e946630d5f9bb092853b93501387dd216899b9Andrew Trick return; // Found a normal regdef. 52792e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 52892e946630d5f9bb092853b93501387dd216899b9Andrew Trick Node = Node->getGluedNode(); 52992e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (Node == NULL) { 53092e946630d5f9bb092853b93501387dd216899b9Andrew Trick return; // No values left to visit. 53192e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 53292e946630d5f9bb092853b93501387dd216899b9Andrew Trick InitNodeNumDefs(); 53392e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 53492e946630d5f9bb092853b93501387dd216899b9Andrew Trick} 53592e946630d5f9bb092853b93501387dd216899b9Andrew Trick 53692e946630d5f9bb092853b93501387dd216899b9Andrew Trickvoid ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) { 53792e946630d5f9bb092853b93501387dd216899b9Andrew Trick assert(SU->NumRegDefsLeft == 0 && "expect a new node"); 53892e946630d5f9bb092853b93501387dd216899b9Andrew Trick for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) { 53992e946630d5f9bb092853b93501387dd216899b9Andrew Trick assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected"); 54092e946630d5f9bb092853b93501387dd216899b9Andrew Trick ++SU->NumRegDefsLeft; 54192e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 54292e946630d5f9bb092853b93501387dd216899b9Andrew Trick} 54392e946630d5f9bb092853b93501387dd216899b9Andrew Trick 544343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 54587896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick SDNode *N = SU->getNode(); 54687896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick 54787896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick // TokenFactor operands are considered zero latency, and some schedulers 54887896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero 54987896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick // whenever node latency is nonzero. 55087896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick if (N && N->getOpcode() == ISD::TokenFactor) { 55187896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick SU->Latency = 0; 55287896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick return; 55387896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick } 55487896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick 555e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng // Check to see if the scheduler cares about latencies. 556e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng if (ForceUnitLatencies()) { 557e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng SU->Latency = 1; 558e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng return; 559e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng } 560e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng 5613ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng if (!InstrItins || InstrItins->isEmpty()) { 5625e84e3ccaa555bd48ecca384e93e55abd76fb40aAndrew Trick if (N && N->isMachineOpcode() && 5635e84e3ccaa555bd48ecca384e93e55abd76fb40aAndrew Trick TII->isHighLatencyDef(N->getMachineOpcode())) 564e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick SU->Latency = HighLatencyCycles; 565e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick else 566e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick SU->Latency = 1; 56715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 56815a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng } 569cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 570343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Compute the latency for the node. We use the sum of the latencies for 57129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // all nodes glued together into this SUnit. 572343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = 0; 57329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) 5748239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng if (N->isMachineOpcode()) 5758239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng SU->Latency += TII->getInstrLatency(InstrItins, N); 576343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 577343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 57815a16def6e70c8f7df1023da80ceb89887203b40Evan Chengvoid ScheduleDAGSDNodes::ComputeOperandLatency(SDNode *Def, SDNode *Use, 57915a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned OpIdx, SDep& dep) const{ 58015a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng // Check to see if the scheduler cares about latencies. 58115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (ForceUnitLatencies()) 58215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 58315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 58415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (dep.getKind() != SDep::Data) 58515a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 58615a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 58715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 5887e2fe9150f905167f6685c9730911c2abc08293cEvan Cheng if (Use->isMachineOpcode()) 5897e2fe9150f905167f6685c9730911c2abc08293cEvan Cheng // Adjust the use operand index by num of defs. 5907e2fe9150f905167f6685c9730911c2abc08293cEvan Cheng OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs(); 591a0792de66c8364d47b0a688c7f408efb7b10f31bEvan Cheng int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx); 592089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg && 593089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng !BB->succ_empty()) { 594089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg(); 595089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Reg)) 596089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng // This copy is a liveout value. It is likely coalesced, so reduce the 597089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng // latency so not to penalize the def. 598089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng // FIXME: need target specific adjustment here? 599089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng Latency = (Latency > 1) ? Latency - 1 : 1; 600089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng } 6013881cb7a5d54c0011b40997adcd742e1c7b91abdEvan Cheng if (Latency >= 0) 6023881cb7a5d54c0011b40997adcd742e1c7b91abdEvan Cheng dep.setLatency(Latency); 60315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng} 60415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 605343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 606c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (!SU->getNode()) { 60784fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "PHYS REG COPY\n"; 608c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng return; 609c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 610c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng 611c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SU->getNode()->dump(DAG); 61284fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "\n"; 61329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SmallVector<SDNode *, 4> GluedNodes; 61429d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 61529d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.push_back(N); 61629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner while (!GluedNodes.empty()) { 61784fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << " "; 61829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.back()->dump(DAG); 61984fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "\n"; 62029d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.pop_back(); 621343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 622343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 623bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 6244c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick#ifndef NDEBUG 6254c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// VerifyScheduledSequence - Verify that all SUnits were scheduled and that 6264c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// their state is consistent with the nodes listed in Sequence. 6274c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// 6284c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trickvoid ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) { 6294c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp); 6304c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick unsigned Noops = 0; 6314c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 6324c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick if (!Sequence[i]) 6334c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick ++Noops; 6344c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick assert(Sequence.size() - Noops == ScheduledNodes && 6354c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick "The number of nodes scheduled doesn't match the expected number!"); 6364c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick} 6374c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick#endif // NDEBUG 6384c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick 639bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Chengnamespace { 640bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng struct OrderSorter { 641bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng bool operator()(const std::pair<unsigned, MachineInstr*> &A, 642bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng const std::pair<unsigned, MachineInstr*> &B) { 643bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return A.first < B.first; 644bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 645bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng }; 646bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng} 647bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 6487a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// ProcessSDDbgValues - Process SDDbgValues associated with this node. 649cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trickstatic void ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, 65055d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel InstrEmitter &Emitter, 65155d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 65255d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel DenseMap<SDValue, unsigned> &VRBaseMap, 65355d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel unsigned Order) { 65455d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel if (!N->getHasDebugValue()) 65555d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel return; 65655d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel 65755d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel // Opportunistically insert immediate dbg_value uses, i.e. those with source 65855d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel // order number right after the N. 65955d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel MachineBasicBlock *BB = Emitter.getBlock(); 66055d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 66122a54c1cd711afccd4558374918d12a939e1cca5Benjamin Kramer ArrayRef<SDDbgValue*> DVs = DAG->GetDbgValues(N); 66255d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 66355d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel if (DVs[i]->isInvalidated()) 66455d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel continue; 66555d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel unsigned DVOrder = DVs[i]->getOrder(); 66655d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel if (!Order || DVOrder == ++Order) { 66755d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 66855d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel if (DbgMI) { 66955d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel Orders.push_back(std::make_pair(DVOrder, DbgMI)); 67055d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel BB->insert(InsertPos, DbgMI); 67155d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel } 67255d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel DVs[i]->setIsInvalidated(); 67355d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel } 67455d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel } 67555d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel} 67655d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel 677bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng// ProcessSourceNode - Process nodes with source order numbers. These are added 678d27946d1d4272d7e2bbee00fac020dc8147dfd25Jim Grosbach// to a vector which EmitSchedule uses to determine how to insert dbg_value 679bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng// instructions in the right order. 680bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Chengstatic void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, 681bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng InstrEmitter &Emitter, 682bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng DenseMap<SDValue, unsigned> &VRBaseMap, 683bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 684bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallSet<unsigned, 8> &Seen) { 685bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned Order = DAG->GetOrdering(N); 68639078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel if (!Order || !Seen.insert(Order)) { 68739078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel // Process any valid SDDbgValues even if node does not have any order 68839078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel // assigned. 68939078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0); 690bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return; 69139078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel } 692bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 693bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineBasicBlock *BB = Emitter.getBlock(); 69484023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI()) { 695bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Did not insert any instruction. 696bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); 697bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return; 698bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 699bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 70084023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); 70155d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order); 702bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng} 703bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 704bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 705bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman/// EmitSchedule - Emit the machine code in scheduled order. 706af1d8ca44a18f304f207e209b3bdb94b590f86ffDan GohmanMachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { 707bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman InstrEmitter Emitter(BB, InsertPos); 708bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman DenseMap<SDValue, unsigned> VRBaseMap; 709bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman DenseMap<SUnit*, unsigned> CopyVRBaseMap; 710bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 711bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallSet<unsigned, 8> Seen; 712bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng bool HasDbg = DAG->hasDebugValues(); 713bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen 714fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // If this is the first BB, emit byval parameter dbg_value's. 715fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 716fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 717fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 718fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen for (; PDI != PDE; ++PDI) { 719891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 720fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen if (DbgMI) 72184023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman BB->insert(InsertPos, DbgMI); 722fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen } 723fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen } 724fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen 725bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 726bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman SUnit *SU = Sequence[i]; 727bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman if (!SU) { 728bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // Null SUnit* is a noop. 729bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman EmitNoop(); 730bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman continue; 731bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 732bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 733bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // For pre-regalloc scheduling, create instructions corresponding to the 73429d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // SDNode and any glued SDNodes and append them to the block. 735bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman if (!SU->getNode()) { 736bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // Emit a copy. 737bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman EmitPhysRegCopy(SU, CopyVRBaseMap); 738bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman continue; 739bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 740bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 74129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SmallVector<SDNode *, 4> GluedNodes; 74229d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner for (SDNode *N = SU->getNode()->getGluedNode(); N; 74329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner N = N->getGluedNode()) 74429d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.push_back(N); 74529d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner while (!GluedNodes.empty()) { 74629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SDNode *N = GluedNodes.back(); 74729d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner Emitter.EmitNode(GluedNodes.back(), SU->OrigNode != SU, SU->isCloned, 748af1d8ca44a18f304f207e209b3bdb94b590f86ffDan Gohman VRBaseMap); 749fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Remember the source order of the inserted instruction. 750bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) 751891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 75229d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.pop_back(); 753bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 754bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 755af1d8ca44a18f304f207e209b3bdb94b590f86ffDan Gohman VRBaseMap); 756fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Remember the source order of the inserted instruction. 757bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) 758891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 759bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng Seen); 760bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 761bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 762fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Insert all the dbg_values which have not already been inserted in source 763bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // order sequence. 764bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) { 76584023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 766bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 767bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Sort the source order instructions and use the order to insert debug 768bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // values. 769bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng std::sort(Orders.begin(), Orders.end(), OrderSorter()); 770bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 771bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 772bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 773bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Now emit the rest according to source order. 774bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned LastOrder = 0; 775bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 776bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned Order = Orders[i].first; 777bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineInstr *MI = Orders[i].second; 778bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Insert all SDDbgValue's whose order(s) are before "Order". 779bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (!MI) 780bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng continue; 781bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng for (; DI != DE && 782bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 783bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if ((*DI)->isInvalidated()) 784bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng continue; 785891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 786962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (DbgMI) { 787962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (!LastOrder) 788962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng // Insert to start of the BB (after PHIs). 789962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng BB->insert(BBBegin, DbgMI); 790962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng else { 791a8dab36f3dfdfcd3f74224afa4ffb32776674c93Dan Gohman // Insert at the instruction, which may be in a different 792a8dab36f3dfdfcd3f74224afa4ffb32776674c93Dan Gohman // block, if the block was split by a custom inserter. 793962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng MachineBasicBlock::iterator Pos = MI; 794a8dab36f3dfdfcd3f74224afa4ffb32776674c93Dan Gohman MI->getParent()->insert(llvm::next(Pos), DbgMI); 795962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng } 796bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 797bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen } 798bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng LastOrder = Order; 799bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 800bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Add trailing DbgValue's before the terminator. FIXME: May want to add 801bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // some of them before one or more conditional branches? 802bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng while (DI != DE) { 803bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineBasicBlock *InsertBB = Emitter.getBlock(); 804bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineBasicBlock::iterator Pos= Emitter.getBlock()->getFirstTerminator(); 805bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (!(*DI)->isInvalidated()) { 806891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI= Emitter.EmitDbgValue(*DI, VRBaseMap); 807962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (DbgMI) 808962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng InsertBB->insert(Pos, DbgMI); 809bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 810bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng ++DI; 811bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 812bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 813bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 814bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman BB = Emitter.getBlock(); 815bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman InsertPos = Emitter.getInsertPos(); 816bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman return BB; 817bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman} 81856b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick 81956b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick/// Return the basic block label. 82056b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trickstd::string ScheduleDAGSDNodes::getDAGName() const { 82156b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick return "sunit-dag." + BB->getFullName(); 82256b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick} 823