ScheduleDAGSDNodes.cpp revision 3ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1
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" 20343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetMachine.h" 21343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetInstrInfo.h" 221cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng#include "llvm/Target/TargetLowering.h" 23343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetRegisterInfo.h" 24710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin#include "llvm/Target/TargetSubtarget.h" 25c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/DenseMap.h" 26c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 27bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng#include "llvm/ADT/SmallSet.h" 28c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/SmallVector.h" 29c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/Statistic.h" 30343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 31343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/raw_ostream.h" 32343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 33343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 34c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan ChengSTATISTIC(LoadsClustered, "Number of loads clustered together"); 35c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 3679ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 373ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng : ScheduleDAG(mf), 383ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng InstrItins(mf.getTarget().getInstrItineraryData()) {} 39343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 4047ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// Run - perform scheduling. 4147ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// 4247ac0f0c7c39289f5970688154e385be22b7f293Dan Gohmanvoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 4347ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman MachineBasicBlock::iterator insertPos) { 4447ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman DAG = dag; 4547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman ScheduleDAG::Run(bb, insertPos); 4647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman} 4747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 481cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng/// NewSUnit - Creates a new SUnit and return a ptr to it. 491cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng/// 501cc3984148be113c6e5e470f23c9ddbd37679c5fEvan ChengSUnit *ScheduleDAGSDNodes::NewSUnit(SDNode *N) { 511cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng#ifndef NDEBUG 521cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng const SUnit *Addr = 0; 531cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng if (!SUnits.empty()) 541cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng Addr = &SUnits[0]; 551cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng#endif 561cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 571cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng assert((Addr == 0 || Addr == &SUnits[0]) && 581cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng "SUnits std::vector reallocated on the fly!"); 591cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnits.back().OrigNode = &SUnits.back(); 601cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnit *SU = &SUnits.back(); 611cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 62c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng if (!N || 63c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng (N->isMachineOpcode() && 64c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)) 65046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng SU->SchedulingPref = Sched::None; 66046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng else 67046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng SU->SchedulingPref = TLI.getSchedulingPreference(N); 681cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng return SU; 691cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng} 701cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 71343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 72343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = NewSUnit(Old->getNode()); 73343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->OrigNode = Old->OrigNode; 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = Old->Latency; 75343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = Old->isTwoAddress; 76343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = Old->isCommutable; 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->hasPhysRegDefs = Old->hasPhysRegDefs; 783974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 791cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SU->SchedulingPref = Old->SchedulingPref; 80e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng Old->isCloned = true; 81343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return SU; 82343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 83343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 84343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CheckForPhysRegDependency - Check if the dependency between def and use of 85343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a specified operand is a physical register dependency. If so, returns the 86c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// register and the cost of copying the register. 87343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 88343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetRegisterInfo *TRI, 89343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrInfo *TII, 90c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng unsigned &PhysReg, int &Cost) { 91343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 92343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 93343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 94343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 95343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TargetRegisterInfo::isVirtualRegister(Reg)) 96343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 97343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned ResNo = User->getOperand(2).getResNo(); 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Def->isMachineOpcode()) { 100343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 101343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (ResNo >= II.getNumDefs() && 102c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 103343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman PhysReg = Reg; 104c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *RC = 105d31f972bd33de85071c716f69bf5c6d735f730f2Rafael Espindola TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 106c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng Cost = RC->getCopyCost(); 107c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 110343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 111c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Chengstatic void AddFlags(SDNode *N, SDValue Flag, bool AddFlag, 112c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SelectionDAG *DAG) { 113c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<EVT, 4> VTs; 11410707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling SDNode *FlagDestNode = Flag.getNode(); 115151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 11610707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling // Don't add a flag from a node to itself. 11710707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling if (FlagDestNode == N) return; 11810707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling 11910707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling // Don't add a flag to something which already has a flag. 12010707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling if (N->getValueType(N->getNumValues() - 1) == MVT::Flag) return; 12110707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling 12210707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 12310707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling VTs.push_back(N->getValueType(I)); 124151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 125c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng if (AddFlag) 126c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng VTs.push_back(MVT::Flag); 127151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 128c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<SDValue, 4> Ops; 12910707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 13010707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling Ops.push_back(N->getOperand(I)); 131151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 13210707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling if (FlagDestNode) 133c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng Ops.push_back(Flag); 134151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 135c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 136151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling MachineSDNode::mmo_iterator Begin = 0, End = 0; 137151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 138151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 139151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling // Store memory references. 140151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling if (MN) { 141151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling Begin = MN->memoperands_begin(); 142151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling End = MN->memoperands_end(); 143151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling } 144151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 145c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 146151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 147151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling // Reset the memory references 148151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling if (MN) 149151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling MN->setMemRefs(Begin, End); 150c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng} 151c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 152c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// ClusterNeighboringLoads - Force nearby loads together by "flagging" them. 153c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// This function finds loads of the same base and different offsets. If the 154c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// offsets are not far apart (target specific), it add MVT::Flag inputs and 155c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// outputs to ensure they are scheduled together and in order. This 156c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// optimization may benefit some targets by improving cache locality. 157302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Chengvoid ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 158302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Chain = 0; 159302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned NumOps = Node->getNumOperands(); 160302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 161302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Chain = Node->getOperand(NumOps-1).getNode(); 162302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Chain) 163302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 164302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng 165302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Look for other loads of the same chain. Find loads that are loading from 166302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // the same base pointer and different offsets. 167c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallPtrSet<SDNode*, 16> Visited; 168c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<int64_t, 4> Offsets; 169c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 170302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng bool Cluster = false; 171302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Base = Node; 172302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); 173302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng I != E; ++I) { 174302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *User = *I; 175302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (User == Node || !Visited.insert(User)) 176c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 177302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t Offset1, Offset2; 178302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || 179302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offset1 == Offset2) 180302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // FIXME: Should be ok if they addresses are identical. But earlier 181302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // optimizations really should have eliminated one of the loads. 182c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 183302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (O2SMap.insert(std::make_pair(Offset1, Base)).second) 184302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offsets.push_back(Offset1); 185302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng O2SMap.insert(std::make_pair(Offset2, User)); 186302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offsets.push_back(Offset2); 187b447c4e65b5f6d39db16cb8fc338133965291972Duncan Sands if (Offset2 < Offset1) 188302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Base = User; 189302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Cluster = true; 190302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 191c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 192302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Cluster) 193302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 194c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 195302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Sort them in increasing order. 196302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng std::sort(Offsets.begin(), Offsets.end()); 197c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 198302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Check if the loads are close enough. 199302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SmallVector<SDNode*, 4> Loads; 200302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned NumLoads = 0; 201302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t BaseOff = Offsets[0]; 202302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *BaseLoad = O2SMap[BaseOff]; 203302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Loads.push_back(BaseLoad); 204302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 205302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t Offset = Offsets[i]; 206302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Load = O2SMap[Offset]; 207302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 208302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng break; // Stop right here. Ignore loads that are further away. 209302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Loads.push_back(Load); 210302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ++NumLoads; 211302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 212c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 213302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (NumLoads == 0) 214302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 215c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 216302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Cluster loads by adding MVT::Flag outputs and inputs. This also 217302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // ensure they are scheduled in order of increasing addresses. 218302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Lead = Loads[0]; 21910707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling AddFlags(Lead, SDValue(0, 0), true, DAG); 22010707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling 22110707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling SDValue InFlag = SDValue(Lead, Lead->getNumValues() - 1); 22210707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 22310707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling bool OutFlag = I < E - 1; 22410707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling SDNode *Load = Loads[I]; 225151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 226302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng AddFlags(Load, InFlag, OutFlag, DAG); 227151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 228302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (OutFlag) 22910707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling InFlag = SDValue(Load, Load->getNumValues() - 1); 230151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 231302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ++LoadsClustered; 232302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 233302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng} 234c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 235302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng/// ClusterNodes - Cluster certain nodes which should be scheduled together. 236302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng/// 237302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Chengvoid ScheduleDAGSDNodes::ClusterNodes() { 238302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 239302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng E = DAG->allnodes_end(); NI != E; ++NI) { 240302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Node = &*NI; 241302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Node || !Node->isMachineOpcode()) 242c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 243c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 244302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned Opc = Node->getMachineOpcode(); 245302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng const TargetInstrDesc &TID = TII->get(Opc); 246302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (TID.mayLoad()) 247302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Cluster loads from "near" addresses into combined SUnits. 248302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ClusterNeighboringLoads(Node); 249c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } 250c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng} 251c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 252343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::BuildSchedUnits() { 253343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // During scheduling, the NodeId field of SDNode is used to map SDNodes 254343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // to their associated SUnits by holding SUnits table indices. A value 255343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of -1 means the SDNode does not yet have an associated SUnit. 256e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman unsigned NumNodes = 0; 257343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 258e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 259343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NI->setNodeId(-1); 260e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman ++NumNodes; 261e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman } 262343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 263e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // Reserve entries in the vector for each of the SUnits we are creating. This 264e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 265e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // invalidated. 266e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // FIXME: Multiply by 2 because we may clone nodes during scheduling. 267e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // This is a temporary workaround. 268e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman SUnits.reserve(NumNodes * 2); 269e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman 270736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner // Add all nodes in depth first order. 271736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SmallVector<SDNode*, 64> Worklist; 272736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SmallPtrSet<SDNode*, 64> Visited; 273736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Worklist.push_back(DAG->getRoot().getNode()); 274736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Visited.insert(DAG->getRoot().getNode()); 275736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner 276736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner while (!Worklist.empty()) { 277736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SDNode *NI = Worklist.pop_back_val(); 278736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner 279736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner // Add all operands to the worklist unless they've already been added. 280736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 281736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner if (Visited.insert(NI->getOperand(i).getNode())) 282736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Worklist.push_back(NI->getOperand(i).getNode()); 283736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner 284343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 285343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman continue; 286343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 287343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If this node has already been processed, stop now. 288343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (NI->getNodeId() != -1) continue; 289343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 290343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *NodeSUnit = NewSUnit(NI); 291343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 292343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // See if anything is flagged to this node, if so, add them to flagged 293343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // nodes. Nodes can have at most one flag input and one flag output. Flags 294db95fa131a229652f925794ca7a5b84e9490050bDan Gohman // are required to be the last operand and result of a node. 295343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 296343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan up to find flagged preds. 297343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *N = NI; 298db95fa131a229652f925794ca7a5b84e9490050bDan Gohman while (N->getNumOperands() && 299825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 300db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N = N->getOperand(N->getNumOperands()-1).getNode(); 301db95fa131a229652f925794ca7a5b84e9490050bDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 302db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N->setNodeId(NodeSUnit->NodeNum); 303343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 304343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 305343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan down to find any flagged succs. 306343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = NI; 307825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 308343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDValue FlagVal(N, N->getNumValues()-1); 309343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 310343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // There are either zero or one users of the Flag result. 311343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman bool HasFlagUse = false; 312343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 313343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman UI != E; ++UI) 314343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (FlagVal.isOperandOf(*UI)) { 315343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman HasFlagUse = true; 316343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 317343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 318343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = *UI; 319343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 320343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 321343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (!HasFlagUse) break; 322343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 323343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 324343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If there are flag operands involved, N is now the bottom-most node 325343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of the sequence of nodes that are flagged together. 326343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update the SUnit. 327343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NodeSUnit->setNode(N); 328343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 329343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 330343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 331787782f4ca0cca2523825131c24a6f78535a3eb8Dan Gohman // Assign the Latency field of NodeSUnit using target-provided information. 332e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng ComputeLatency(NodeSUnit); 333343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 334c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 335c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 336c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::AddSchedEdges() { 337710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 338710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 339dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin // Check to see if the scheduler cares about latencies. 340dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin bool UnitLatencies = ForceUnitLatencies(); 341dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin 342343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Pass 2: add the preds, succs, etc. 343343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 344343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[su]; 345343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *MainNode = SU->getNode(); 346343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 347343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (MainNode->isMachineOpcode()) { 348343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Opc = MainNode->getMachineOpcode(); 349343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &TID = TII->get(Opc); 350343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 351343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 352343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = true; 353343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 354343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 355343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 356343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.isCommutable()) 357343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = true; 358343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 359343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 360343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Find all predecessors and successors of the group. 361343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 362343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode() && 3633974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman TII->get(N->getMachineOpcode()).getImplicitDefs()) { 3643974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = true; 365bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman unsigned NumUsed = InstrEmitter::CountResults(N); 3668cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 3678cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman --NumUsed; // Skip over unused values at the end. 3688cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 3693974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegDefs = true; 3703974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman } 371343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 372343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 373343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *OpN = N->getOperand(i).getNode(); 374343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(OpN)) continue; // Not scheduled. 375343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *OpSU = &SUnits[OpN->getNodeId()]; 376343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpSU && "Node has no SUnit!"); 377343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (OpSU == SU) continue; // In the same group. 378343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 379e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT OpVT = N->getOperand(i).getValueType(); 380825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 381825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson bool isChain = OpVT == MVT::Other; 382343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 383343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned PhysReg = 0; 384c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng int Cost = 1; 385343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Determine if this is a physical register dependency. 386c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 38754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((PhysReg == 0 || !isChain) && 38854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "Chain dependence via physreg data?"); 389c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 390c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // emits a copy from the physical register to a virtual register unless 391c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // it requires a cross class copy (cost < 0). That means we are only 392c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // treating "expensive to copy" register dependency as physical register 393c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // dependency. This may change in the future though. 394c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (Cost >= 0) 395c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng PhysReg = 0; 396710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 397046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng // If this is a ctrl dep, latency is 1. 398046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng unsigned OpLatency = isChain ? 1 : OpSU->Latency; 399046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng const SDep &dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 400046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng OpLatency, PhysReg); 401dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin if (!isChain && !UnitLatencies) { 40215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng ComputeOperandLatency(OpN, N, i, const_cast<SDep &>(dep)); 4033fb150a9024a38872ec4abbc3300e08a8bfc1812Dan Gohman ST.adjustSchedDependency(OpSU, SU, const_cast<SDep &>(dep)); 404dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin } 405710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 406710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin SU->addPred(dep); 407343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 408343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 409343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 410343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 411343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 412c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 413c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// are input. This SUnit graph is similar to the SelectionDAG, but 414c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// excludes nodes that aren't interesting to scheduling, and represents 415c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// flagged together nodes with a single SUnit. 41698976e4dcd18adbbe676048c0069e67346eb4adeDan Gohmanvoid ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 417302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Cluster certain nodes which should be scheduled together. 418302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ClusterNodes(); 419c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Populate the SUnits array. 420c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman BuildSchedUnits(); 421c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Compute all the scheduling dependencies between nodes. 422c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman AddSchedEdges(); 423c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 424c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 425343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 426e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng // Check to see if the scheduler cares about latencies. 427e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng if (ForceUnitLatencies()) { 428e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng SU->Latency = 1; 429e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng return; 430e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng } 431e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng 4323ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng if (!InstrItins || InstrItins->isEmpty()) { 43315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng SU->Latency = 1; 43415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 43515a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng } 436343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 437343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Compute the latency for the node. We use the sum of the latencies for 438343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // all nodes flagged together into this SUnit. 439343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = 0; 440c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 441343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode()) { 4423ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng SU->Latency += InstrItins-> 443dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin getStageLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 444343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 445343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 446343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 44715a16def6e70c8f7df1023da80ceb89887203b40Evan Chengvoid ScheduleDAGSDNodes::ComputeOperandLatency(SDNode *Def, SDNode *Use, 44815a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned OpIdx, SDep& dep) const{ 44915a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng // Check to see if the scheduler cares about latencies. 45015a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (ForceUnitLatencies()) 45115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 45215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 4533ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng if (!InstrItins || InstrItins->isEmpty()) 45415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 45515a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 45615a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (dep.getKind() != SDep::Data) 45715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 45815a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 45915a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 460046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng if (Def->isMachineOpcode()) { 46115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 46215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (DefIdx >= II.getNumDefs()) 46315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 4643ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng int DefCycle = InstrItins->getOperandCycle(II.getSchedClass(), DefIdx); 46515a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (DefCycle < 0) 46615a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 467046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng int UseCycle = 1; 468046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng if (Use->isMachineOpcode()) { 469046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng const unsigned UseClass = TII->get(Use->getMachineOpcode()).getSchedClass(); 4703ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng UseCycle = InstrItins->getOperandCycle(UseClass, OpIdx); 471046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng } 47215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (UseCycle >= 0) { 47315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng int Latency = DefCycle - UseCycle + 1; 47415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (Latency >= 0) 47515a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng dep.setLatency(Latency); 47615a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng } 47715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng } 47815a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng} 47915a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 480343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 481c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (!SU->getNode()) { 48284fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "PHYS REG COPY\n"; 483c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng return; 484c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 485c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng 486c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SU->getNode()->dump(DAG); 48784fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "\n"; 488343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SmallVector<SDNode *, 4> FlaggedNodes; 489343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 490343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.push_back(N); 491343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (!FlaggedNodes.empty()) { 49284fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << " "; 493343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.back()->dump(DAG); 49484fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "\n"; 495343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.pop_back(); 496343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 497343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 498bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 499bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Chengnamespace { 500bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng struct OrderSorter { 501bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng bool operator()(const std::pair<unsigned, MachineInstr*> &A, 502bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng const std::pair<unsigned, MachineInstr*> &B) { 503bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return A.first < B.first; 504bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 505bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng }; 506bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng} 507bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 508bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng// ProcessSourceNode - Process nodes with source order numbers. These are added 509d27946d1d4272d7e2bbee00fac020dc8147dfd25Jim Grosbach// to a vector which EmitSchedule uses to determine how to insert dbg_value 510bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng// instructions in the right order. 511bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Chengstatic void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, 512bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng InstrEmitter &Emitter, 513bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng DenseMap<SDValue, unsigned> &VRBaseMap, 514bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 515bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallSet<unsigned, 8> &Seen) { 516bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned Order = DAG->GetOrdering(N); 517bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (!Order || !Seen.insert(Order)) 518bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return; 519bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 520bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineBasicBlock *BB = Emitter.getBlock(); 52184023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI()) { 522bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Did not insert any instruction. 523bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); 524bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return; 525bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 526bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 52784023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); 528bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (!N->getHasDebugValue()) 529bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return; 530bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Opportunistically insert immediate dbg_value uses, i.e. those with source 531bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // order number right after the N. 532bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 533bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallVector<SDDbgValue*,2> &DVs = DAG->GetDbgValues(N); 534bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 535bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (DVs[i]->isInvalidated()) 536bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng continue; 537bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned DVOrder = DVs[i]->getOrder(); 538bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (DVOrder == ++Order) { 539891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 540962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (DbgMI) { 541962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng Orders.push_back(std::make_pair(DVOrder, DbgMI)); 542962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng BB->insert(InsertPos, DbgMI); 543962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng } 544bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng DVs[i]->setIsInvalidated(); 545bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 546bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 547bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng} 548bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 549bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 550bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman/// EmitSchedule - Emit the machine code in scheduled order. 551af1d8ca44a18f304f207e209b3bdb94b590f86ffDan GohmanMachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { 552bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman InstrEmitter Emitter(BB, InsertPos); 553bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman DenseMap<SDValue, unsigned> VRBaseMap; 554bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman DenseMap<SUnit*, unsigned> CopyVRBaseMap; 555bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 556bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallSet<unsigned, 8> Seen; 557bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng bool HasDbg = DAG->hasDebugValues(); 558bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen 559fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // If this is the first BB, emit byval parameter dbg_value's. 560fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 561fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 562fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 563fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen for (; PDI != PDE; ++PDI) { 564891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 565fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen if (DbgMI) 56684023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman BB->insert(InsertPos, DbgMI); 567fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen } 568fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen } 569fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen 570bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 571bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman SUnit *SU = Sequence[i]; 572bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman if (!SU) { 573bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // Null SUnit* is a noop. 574bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman EmitNoop(); 575bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman continue; 576bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 577bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 578bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // For pre-regalloc scheduling, create instructions corresponding to the 579bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // SDNode and any flagged SDNodes and append them to the block. 580bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman if (!SU->getNode()) { 581bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // Emit a copy. 582bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman EmitPhysRegCopy(SU, CopyVRBaseMap); 583bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman continue; 584bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 585bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 586bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman SmallVector<SDNode *, 4> FlaggedNodes; 587bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman for (SDNode *N = SU->getNode()->getFlaggedNode(); N; 588bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman N = N->getFlaggedNode()) 589bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman FlaggedNodes.push_back(N); 590bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman while (!FlaggedNodes.empty()) { 591bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SDNode *N = FlaggedNodes.back(); 592bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman Emitter.EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, SU->isCloned, 593af1d8ca44a18f304f207e209b3bdb94b590f86ffDan Gohman VRBaseMap); 594fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Remember the source order of the inserted instruction. 595bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) 596891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 597bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman FlaggedNodes.pop_back(); 598bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 599bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 600af1d8ca44a18f304f207e209b3bdb94b590f86ffDan Gohman VRBaseMap); 601fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Remember the source order of the inserted instruction. 602bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) 603891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 604bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng Seen); 605bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 606bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 607fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Insert all the dbg_values which have not already been inserted in source 608bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // order sequence. 609bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) { 61084023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 611bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 612bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Sort the source order instructions and use the order to insert debug 613bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // values. 614bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng std::sort(Orders.begin(), Orders.end(), OrderSorter()); 615bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 616bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 617bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 618bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Now emit the rest according to source order. 619bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned LastOrder = 0; 620bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 621bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned Order = Orders[i].first; 622bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineInstr *MI = Orders[i].second; 623bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Insert all SDDbgValue's whose order(s) are before "Order". 624bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (!MI) 625bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng continue; 6264ec9bd9a6f92a10185870bae2cebce199f6acc5aEvan Cheng#ifndef NDEBUG 6274ec9bd9a6f92a10185870bae2cebce199f6acc5aEvan Cheng unsigned LastDIOrder = 0; 6284ec9bd9a6f92a10185870bae2cebce199f6acc5aEvan Cheng#endif 629bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng for (; DI != DE && 630bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 6314ec9bd9a6f92a10185870bae2cebce199f6acc5aEvan Cheng#ifndef NDEBUG 6324ec9bd9a6f92a10185870bae2cebce199f6acc5aEvan Cheng assert((*DI)->getOrder() >= LastDIOrder && 6334ec9bd9a6f92a10185870bae2cebce199f6acc5aEvan Cheng "SDDbgValue nodes must be in source order!"); 6344ec9bd9a6f92a10185870bae2cebce199f6acc5aEvan Cheng LastDIOrder = (*DI)->getOrder(); 6354ec9bd9a6f92a10185870bae2cebce199f6acc5aEvan Cheng#endif 636bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if ((*DI)->isInvalidated()) 637bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng continue; 638891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 639962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (DbgMI) { 640962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (!LastOrder) 641962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng // Insert to start of the BB (after PHIs). 642962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng BB->insert(BBBegin, DbgMI); 643962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng else { 644a8dab36f3dfdfcd3f74224afa4ffb32776674c93Dan Gohman // Insert at the instruction, which may be in a different 645a8dab36f3dfdfcd3f74224afa4ffb32776674c93Dan Gohman // block, if the block was split by a custom inserter. 646962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng MachineBasicBlock::iterator Pos = MI; 647a8dab36f3dfdfcd3f74224afa4ffb32776674c93Dan Gohman MI->getParent()->insert(llvm::next(Pos), DbgMI); 648962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng } 649bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 650bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen } 651bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng LastOrder = Order; 652bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 653bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Add trailing DbgValue's before the terminator. FIXME: May want to add 654bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // some of them before one or more conditional branches? 655bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng while (DI != DE) { 656bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineBasicBlock *InsertBB = Emitter.getBlock(); 657bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineBasicBlock::iterator Pos= Emitter.getBlock()->getFirstTerminator(); 658bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (!(*DI)->isInvalidated()) { 659891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI= Emitter.EmitDbgValue(*DI, VRBaseMap); 660962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (DbgMI) 661962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng InsertBB->insert(Pos, DbgMI); 662bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 663bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng ++DI; 664bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 665bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 666bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 667bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman BB = Emitter.getBlock(); 668bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman InsertPos = Emitter.getInsertPos(); 669bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman return BB; 670bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman} 671