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 1584fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman#include "ScheduleDAGSDNodes.h" 16bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman#include "InstrEmitter.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "SDNodeDbgValue.h" 18c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/DenseMap.h" 19c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 20bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng#include "llvm/ADT/SmallSet.h" 21c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/SmallVector.h" 22c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng#include "llvm/ADT/Statistic.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineInstrBuilder.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineRegisterInfo.h" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/SelectionDAG.h" 26d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/MC/MCInstrItineraries.h" 27e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick#include "llvm/Support/CommandLine.h" 28343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 29343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/raw_ostream.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetLowering.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetSubtargetInfo.h" 35343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 36343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "pre-RA-sched" 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 39c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan ChengSTATISTIC(LoadsClustered, "Number of loads clustered together"); 40c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 41e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick// This allows latency based scheduler to notice high latency instructions 42e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick// without a target itinerary. The choise if number here has more to do with 43e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick// balancing scheduler heursitics than with the actual machine latency. 44e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trickstatic cl::opt<int> HighLatencyCycles( 45e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick "sched-high-latency-cycles", cl::Hidden, cl::init(10), 46e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick cl::desc("Roughly estimate the number of cycles that 'long latency'" 47e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick "instructions take for targets with no itinerary")); 48e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick 4979ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : ScheduleDAG(mf), BB(nullptr), DAG(nullptr), 513ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng InstrItins(mf.getTarget().getInstrItineraryData()) {} 52343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 5347ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// Run - perform scheduling. 5447ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// 5547c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trickvoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) { 5647c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick BB = bb; 5747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman DAG = dag; 5847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 5947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick // Clear the scheduler's SUnit DAG. 6047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick ScheduleDAG::clearDAG(); 6147c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick Sequence.clear(); 6247c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 6347c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick // Invoke the target's selection of scheduler. 6447c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick Schedule(); 6547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman} 6647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 671cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng/// NewSUnit - Creates a new SUnit and return a ptr to it. 681cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng/// 69953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew TrickSUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) { 701cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng#ifndef NDEBUG 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const SUnit *Addr = nullptr; 721cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng if (!SUnits.empty()) 731cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng Addr = &SUnits[0]; 741cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng#endif 751cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 76dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert((Addr == nullptr || Addr == &SUnits[0]) && 771cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng "SUnits std::vector reallocated on the fly!"); 781cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnits.back().OrigNode = &SUnits.back(); 791cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnit *SU = &SUnits.back(); 801cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 81c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng if (!N || 82c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng (N->isMachineOpcode() && 83c120af45671c75fd1297ac6300c03a6a9e1264daEvan Cheng N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)) 84046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng SU->SchedulingPref = Sched::None; 85046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng else 86046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng SU->SchedulingPref = TLI.getSchedulingPreference(N); 871cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng return SU; 881cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng} 891cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 90343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 91953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick SUnit *SU = newSUnit(Old->getNode()); 92343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->OrigNode = Old->OrigNode; 93343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = Old->Latency; 9454699765064842fd08d1466adc93453660bc2a85Andrew Trick SU->isVRegCycle = Old->isVRegCycle; 958239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng SU->isCall = Old->isCall; 96554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SU->isCallOp = Old->isCallOp; 97343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = Old->isTwoAddress; 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = Old->isCommutable; 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->hasPhysRegDefs = Old->hasPhysRegDefs; 1003974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 10112f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick SU->isScheduleHigh = Old->isScheduleHigh; 10212f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick SU->isScheduleLow = Old->isScheduleLow; 1031cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SU->SchedulingPref = Old->SchedulingPref; 104e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng Old->isCloned = true; 105343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return SU; 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CheckForPhysRegDependency - Check if the dependency between def and use of 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a specified operand is a physical register dependency. If so, returns the 110c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// register and the cost of copying the register. 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 112cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick const TargetRegisterInfo *TRI, 113343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrInfo *TII, 114c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng unsigned &PhysReg, int &Cost) { 115343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 116343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 117343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 118343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 119343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TargetRegisterInfo::isVirtualRegister(Reg)) 120343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 121343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 122343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned ResNo = User->getOperand(2).getResNo(); 123343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Def->isMachineOpcode()) { 124e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &II = TII->get(Def->getMachineOpcode()); 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (ResNo >= II.getNumDefs() && 126c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 127343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman PhysReg = Reg; 128c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *RC = 129d31f972bd33de85071c716f69bf5c6d735f730f2Rafael Espindola TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 130c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng Cost = RC->getCopyCost(); 131c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 132343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 133343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 134343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 1352674a4acdb51ce610d060b76608f631765a6e508Andrew Trick// Helper for AddGlue to clone node operands. 1362674a4acdb51ce610d060b76608f631765a6e508Andrew Trickstatic void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, 1372674a4acdb51ce610d060b76608f631765a6e508Andrew Trick SmallVectorImpl<EVT> &VTs, 1382674a4acdb51ce610d060b76608f631765a6e508Andrew Trick SDValue ExtraOper = SDValue()) { 139c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<SDValue, 4> Ops; 14010707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 14110707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling Ops.push_back(N->getOperand(I)); 142151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 1432674a4acdb51ce610d060b76608f631765a6e508Andrew Trick if (ExtraOper.getNode()) 1442674a4acdb51ce610d060b76608f631765a6e508Andrew Trick Ops.push_back(ExtraOper); 145151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SDVTList VTList = DAG->getVTList(VTs); 147dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineSDNode::mmo_iterator Begin = nullptr, End = nullptr; 148151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 149151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 150151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling // Store memory references. 151151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling if (MN) { 152151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling Begin = MN->memoperands_begin(); 153151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling End = MN->memoperands_end(); 154151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling } 155151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops); 157151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 158151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling // Reset the memory references 159151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling if (MN) 160151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling MN->setMemRefs(Begin, End); 161c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng} 162c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 1632674a4acdb51ce610d060b76608f631765a6e508Andrew Trickstatic bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) { 1642674a4acdb51ce610d060b76608f631765a6e508Andrew Trick SmallVector<EVT, 4> VTs; 1652674a4acdb51ce610d060b76608f631765a6e508Andrew Trick SDNode *GlueDestNode = Glue.getNode(); 1662674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 1672674a4acdb51ce610d060b76608f631765a6e508Andrew Trick // Don't add glue from a node to itself. 1682674a4acdb51ce610d060b76608f631765a6e508Andrew Trick if (GlueDestNode == N) return false; 1692674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 1702674a4acdb51ce610d060b76608f631765a6e508Andrew Trick // Don't add a glue operand to something that already uses glue. 1712674a4acdb51ce610d060b76608f631765a6e508Andrew Trick if (GlueDestNode && 1722674a4acdb51ce610d060b76608f631765a6e508Andrew Trick N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 1732674a4acdb51ce610d060b76608f631765a6e508Andrew Trick return false; 1742674a4acdb51ce610d060b76608f631765a6e508Andrew Trick } 1752674a4acdb51ce610d060b76608f631765a6e508Andrew Trick // Don't add glue to something that already has a glue value. 1762674a4acdb51ce610d060b76608f631765a6e508Andrew Trick if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false; 1772674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 1782674a4acdb51ce610d060b76608f631765a6e508Andrew Trick for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 1792674a4acdb51ce610d060b76608f631765a6e508Andrew Trick VTs.push_back(N->getValueType(I)); 1802674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 1812674a4acdb51ce610d060b76608f631765a6e508Andrew Trick if (AddGlue) 1822674a4acdb51ce610d060b76608f631765a6e508Andrew Trick VTs.push_back(MVT::Glue); 1832674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 1842674a4acdb51ce610d060b76608f631765a6e508Andrew Trick CloneNodeWithValues(N, DAG, VTs, Glue); 1852674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 1862674a4acdb51ce610d060b76608f631765a6e508Andrew Trick return true; 1872674a4acdb51ce610d060b76608f631765a6e508Andrew Trick} 1882674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 1892674a4acdb51ce610d060b76608f631765a6e508Andrew Trick// Cleanup after unsuccessful AddGlue. Use the standard method of morphing the 1902674a4acdb51ce610d060b76608f631765a6e508Andrew Trick// node even though simply shrinking the value list is sufficient. 1912674a4acdb51ce610d060b76608f631765a6e508Andrew Trickstatic void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) { 1922674a4acdb51ce610d060b76608f631765a6e508Andrew Trick assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue && 1932674a4acdb51ce610d060b76608f631765a6e508Andrew Trick !N->hasAnyUseOfValue(N->getNumValues() - 1)) && 1942674a4acdb51ce610d060b76608f631765a6e508Andrew Trick "expected an unused glue value"); 1952674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 1962674a4acdb51ce610d060b76608f631765a6e508Andrew Trick SmallVector<EVT, 4> VTs; 1972674a4acdb51ce610d060b76608f631765a6e508Andrew Trick for (unsigned I = 0, E = N->getNumValues()-1; I != E; ++I) 1982674a4acdb51ce610d060b76608f631765a6e508Andrew Trick VTs.push_back(N->getValueType(I)); 1992674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 2002674a4acdb51ce610d060b76608f631765a6e508Andrew Trick CloneNodeWithValues(N, DAG, VTs); 2012674a4acdb51ce610d060b76608f631765a6e508Andrew Trick} 2022674a4acdb51ce610d060b76608f631765a6e508Andrew Trick 20329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them. 204c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// This function finds loads of the same base and different offsets. If the 205f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner/// offsets are not far apart (target specific), it add MVT::Glue inputs and 206c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// outputs to ensure they are scheduled together and in order. This 207c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng/// optimization may benefit some targets by improving cache locality. 208302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Chengvoid ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 209dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SDNode *Chain = nullptr; 210302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned NumOps = Node->getNumOperands(); 211302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 212302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Chain = Node->getOperand(NumOps-1).getNode(); 213302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Chain) 214302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 215302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng 216302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Look for other loads of the same chain. Find loads that are loading from 217302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // the same base pointer and different offsets. 218c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallPtrSet<SDNode*, 16> Visited; 219c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng SmallVector<int64_t, 4> Offsets; 220c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 221302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng bool Cluster = false; 222302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Base = Node; 223dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // This algorithm requires a reasonably low use count before finding a match 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // to avoid uselessly blowing up compile time in large blocks. 225dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines unsigned UseCount = 0; 226302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); 227dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines I != E && UseCount < 100; ++I, ++UseCount) { 228302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *User = *I; 229302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (User == Node || !Visited.insert(User)) 230c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 231302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t Offset1, Offset2; 232302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || 233302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offset1 == Offset2) 234302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // FIXME: Should be ok if they addresses are identical. But earlier 235302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // optimizations really should have eliminated one of the loads. 236c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 237302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (O2SMap.insert(std::make_pair(Offset1, Base)).second) 238302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offsets.push_back(Offset1); 239302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng O2SMap.insert(std::make_pair(Offset2, User)); 240302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Offsets.push_back(Offset2); 241b447c4e65b5f6d39db16cb8fc338133965291972Duncan Sands if (Offset2 < Offset1) 242302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Base = User; 243302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Cluster = true; 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Reset UseCount to allow more matches. 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines UseCount = 0; 246302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 247c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 248302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Cluster) 249302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 250c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 251302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Sort them in increasing order. 252302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng std::sort(Offsets.begin(), Offsets.end()); 253c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 254302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Check if the loads are close enough. 255302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SmallVector<SDNode*, 4> Loads; 256302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned NumLoads = 0; 257302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t BaseOff = Offsets[0]; 258302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *BaseLoad = O2SMap[BaseOff]; 259302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Loads.push_back(BaseLoad); 260302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 261302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng int64_t Offset = Offsets[i]; 262302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Load = O2SMap[Offset]; 263302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 264302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng break; // Stop right here. Ignore loads that are further away. 265302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng Loads.push_back(Load); 266302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ++NumLoads; 267302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 268c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 269302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (NumLoads == 0) 270302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng return; 271c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 272f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner // Cluster loads by adding MVT::Glue outputs and inputs. This also 273302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // ensure they are scheduled in order of increasing addresses. 274302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Lead = Loads[0]; 275dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SDValue InGlue = SDValue(nullptr, 0); 2762674a4acdb51ce610d060b76608f631765a6e508Andrew Trick if (AddGlue(Lead, InGlue, true, DAG)) 2772674a4acdb51ce610d060b76608f631765a6e508Andrew Trick InGlue = SDValue(Lead, Lead->getNumValues() - 1); 27810707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 27929d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner bool OutGlue = I < E - 1; 28010707f3b442aa5a6cc55b899d630871f06b8ebbcBill Wendling SDNode *Load = Loads[I]; 281151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 2822674a4acdb51ce610d060b76608f631765a6e508Andrew Trick // If AddGlue fails, we could leave an unsused glue value. This should not 2832674a4acdb51ce610d060b76608f631765a6e508Andrew Trick // cause any 2842674a4acdb51ce610d060b76608f631765a6e508Andrew Trick if (AddGlue(Load, InGlue, OutGlue, DAG)) { 2852674a4acdb51ce610d060b76608f631765a6e508Andrew Trick if (OutGlue) 2862674a4acdb51ce610d060b76608f631765a6e508Andrew Trick InGlue = SDValue(Load, Load->getNumValues() - 1); 287151d26d15dc6fe89329d7cccb0638c324c58f485Bill Wendling 2882674a4acdb51ce610d060b76608f631765a6e508Andrew Trick ++LoadsClustered; 2892674a4acdb51ce610d060b76608f631765a6e508Andrew Trick } 2902674a4acdb51ce610d060b76608f631765a6e508Andrew Trick else if (!OutGlue && InGlue.getNode()) 2912674a4acdb51ce610d060b76608f631765a6e508Andrew Trick RemoveUnusedGlue(InGlue.getNode(), DAG); 292302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng } 293302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng} 294c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 295302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng/// ClusterNodes - Cluster certain nodes which should be scheduled together. 296302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng/// 297302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Chengvoid ScheduleDAGSDNodes::ClusterNodes() { 298302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 299302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng E = DAG->allnodes_end(); NI != E; ++NI) { 300302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng SDNode *Node = &*NI; 301302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng if (!Node || !Node->isMachineOpcode()) 302c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng continue; 303c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 304302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng unsigned Opc = Node->getMachineOpcode(); 305e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = TII->get(Opc); 306e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.mayLoad()) 307302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Cluster loads from "near" addresses into combined SUnits. 308302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ClusterNeighboringLoads(Node); 309c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng } 310c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng} 311c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 312343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::BuildSchedUnits() { 313343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // During scheduling, the NodeId field of SDNode is used to map SDNodes 314343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // to their associated SUnits by holding SUnits table indices. A value 315343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of -1 means the SDNode does not yet have an associated SUnit. 316e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman unsigned NumNodes = 0; 317343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 318e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 319343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NI->setNodeId(-1); 320e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman ++NumNodes; 321e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman } 322343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 323e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // Reserve entries in the vector for each of the SUnits we are creating. This 324e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 325e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // invalidated. 326e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // FIXME: Multiply by 2 because we may clone nodes during scheduling. 327e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // This is a temporary workaround. 328e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman SUnits.reserve(NumNodes * 2); 329cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 330736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner // Add all nodes in depth first order. 331736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SmallVector<SDNode*, 64> Worklist; 332736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SmallPtrSet<SDNode*, 64> Visited; 333736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Worklist.push_back(DAG->getRoot().getNode()); 334736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Visited.insert(DAG->getRoot().getNode()); 335cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 336554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SmallVector<SUnit*, 8> CallSUnits; 337736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner while (!Worklist.empty()) { 338736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner SDNode *NI = Worklist.pop_back_val(); 339cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 340736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner // Add all operands to the worklist unless they've already been added. 341736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 342736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner if (Visited.insert(NI->getOperand(i).getNode())) 343736a6ea3a2a5322db0e09d97651a1acc07502e41Chris Lattner Worklist.push_back(NI->getOperand(i).getNode()); 344cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 345343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 346343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman continue; 347cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 348343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If this node has already been processed, stop now. 349343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (NI->getNodeId() != -1) continue; 350cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 351953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick SUnit *NodeSUnit = newSUnit(NI); 352cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 35329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // See if anything is glued to this node, if so, add them to glued 35429d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // nodes. Nodes can have at most one glue input and one glue output. Glue 35529d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // is required to be the last operand and result of a node. 356cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 35729d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // Scan up to find glued preds. 358343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *N = NI; 359db95fa131a229652f925794ca7a5b84e9490050bDan Gohman while (N->getNumOperands() && 360f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 361db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N = N->getOperand(N->getNumOperands()-1).getNode(); 362db95fa131a229652f925794ca7a5b84e9490050bDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 363db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N->setNodeId(NodeSUnit->NodeNum); 3648239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 3658239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng NodeSUnit->isCall = true; 366343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 367cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 36829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // Scan down to find any glued succs. 369343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = NI; 370f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner while (N->getValueType(N->getNumValues()-1) == MVT::Glue) { 37129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SDValue GlueVal(N, N->getNumValues()-1); 372cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 37329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // There are either zero or one users of the Glue result. 37429d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner bool HasGlueUse = false; 375cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 376343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman UI != E; ++UI) 37729d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (GlueVal.isOperandOf(*UI)) { 37829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner HasGlueUse = true; 379343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 380343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 381343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = *UI; 3828239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 3838239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng NodeSUnit->isCall = true; 384343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 385343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 38629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (!HasGlueUse) break; 387343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 388cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 389554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng if (NodeSUnit->isCall) 390554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng CallSUnits.push_back(NodeSUnit); 391554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng 39212f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick // Schedule zero-latency TokenFactor below any nodes that may increase the 39312f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick // schedule height. Otherwise, ancestors of the TokenFactor may appear to 39412f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick // have false stalls. 39512f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick if (NI->getOpcode() == ISD::TokenFactor) 39612f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick NodeSUnit->isScheduleLow = true; 39712f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick 39829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // If there are glue operands involved, N is now the bottom-most node 39929d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // of the sequence of nodes that are glued together. 400343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update the SUnit. 401343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NodeSUnit->setNode(N); 402343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 403343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 404343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 40592e946630d5f9bb092853b93501387dd216899b9Andrew Trick // Compute NumRegDefsLeft. This must be done before AddSchedEdges. 40692e946630d5f9bb092853b93501387dd216899b9Andrew Trick InitNumRegDefsLeft(NodeSUnit); 40792e946630d5f9bb092853b93501387dd216899b9Andrew Trick 408787782f4ca0cca2523825131c24a6f78535a3eb8Dan Gohman // Assign the Latency field of NodeSUnit using target-provided information. 409953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick computeLatency(NodeSUnit); 410343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 411554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng 412554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng // Find all call operands. 413554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng while (!CallSUnits.empty()) { 414554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SUnit *SU = CallSUnits.pop_back_val(); 415554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng for (const SDNode *SUNode = SU->getNode(); SUNode; 416554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SUNode = SUNode->getGluedNode()) { 417554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng if (SUNode->getOpcode() != ISD::CopyToReg) 418554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng continue; 419554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SDNode *SrcN = SUNode->getOperand(2).getNode(); 420554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng if (isPassiveNode(SrcN)) continue; // Not scheduled. 421554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SUnit *SrcSU = &SUnits[SrcN->getNodeId()]; 422554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng SrcSU->isCallOp = true; 423554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng } 424554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng } 425c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 426c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 427c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::AddSchedEdges() { 4285b1b4489cf3a0f56f8be0673fc5cc380a32d277bEvan Cheng const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 429710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 430dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin // Check to see if the scheduler cares about latencies. 431953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick bool UnitLatencies = forceUnitLatencies(); 432dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin 433343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Pass 2: add the preds, succs, etc. 434343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 435343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[su]; 436343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *MainNode = SU->getNode(); 437cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 438343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (MainNode->isMachineOpcode()) { 439343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Opc = MainNode->getMachineOpcode(); 440e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = TII->get(Opc); 441e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { 442e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { 443343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = true; 444343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 445343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 446343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 447e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.isCommutable()) 448343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = true; 449343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 450cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 451343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Find all predecessors and successors of the group. 45229d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) { 453343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode() && 4543974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman TII->get(N->getMachineOpcode()).getImplicitDefs()) { 4553974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = true; 456bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman unsigned NumUsed = InstrEmitter::CountResults(N); 4578cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 4588cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman --NumUsed; // Skip over unused values at the end. 4598cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 4603974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegDefs = true; 4613974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman } 462cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 463343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 464343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *OpN = N->getOperand(i).getNode(); 465343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(OpN)) continue; // Not scheduled. 466343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *OpSU = &SUnits[OpN->getNodeId()]; 467343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpSU && "Node has no SUnit!"); 468343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (OpSU == SU) continue; // In the same group. 469343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 470e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT OpVT = N->getOperand(i).getValueType(); 47129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!"); 472825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson bool isChain = OpVT == MVT::Other; 473343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 474343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned PhysReg = 0; 475c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng int Cost = 1; 476343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Determine if this is a physical register dependency. 477c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 47854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((PhysReg == 0 || !isChain) && 47954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "Chain dependence via physreg data?"); 480c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 481c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // emits a copy from the physical register to a virtual register unless 482c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // it requires a cross class copy (cost < 0). That means we are only 483c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // treating "expensive to copy" register dependency as physical register 484c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // dependency. This may change in the future though. 4854cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick if (Cost >= 0 && !StressSched) 486c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng PhysReg = 0; 487710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 488046fa3f90a31ebfa10df89ae348f478d492709a9Evan Cheng // If this is a ctrl dep, latency is 1. 489c558bf397257f5ef902bdb45a28e622ee2b5b4f2Andrew Trick unsigned OpLatency = isChain ? 1 : OpSU->Latency; 49087896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick // Special-case TokenFactor chains as zero-latency. 49187896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick if(isChain && OpN->getOpcode() == ISD::TokenFactor) 49287896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick OpLatency = 0; 49387896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick 494a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick SDep Dep = isChain ? SDep(OpSU, SDep::Barrier) 495a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick : SDep(OpSU, SDep::Data, PhysReg); 496a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Dep.setLatency(OpLatency); 497dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin if (!isChain && !UnitLatencies) { 498a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick computeOperandLatency(OpN, N, i, Dep); 499a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick ST.adjustSchedDependency(OpSU, SU, Dep); 500dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin } 501710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 502a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick if (!SU->addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) { 50392e946630d5f9bb092853b93501387dd216899b9Andrew Trick // Multiple register uses are combined in the same SUnit. For example, 50492e946630d5f9bb092853b93501387dd216899b9Andrew Trick // we could have a set of glued nodes with all their defs consumed by 50592e946630d5f9bb092853b93501387dd216899b9Andrew Trick // another set of glued nodes. Register pressure tracking sees this as 50692e946630d5f9bb092853b93501387dd216899b9Andrew Trick // a single use, so to keep pressure balanced we reduce the defs. 5074bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick // 5084bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick // We can't tell (without more book-keeping) if this results from 5094bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick // glued nodes or duplicate operands. As long as we don't reduce 5104bbf4678e341e9bf899c0faa3e3bcfe134db81ebAndrew Trick // NumRegDefsLeft to zero, we handle the common cases well. 51192e946630d5f9bb092853b93501387dd216899b9Andrew Trick --OpSU->NumRegDefsLeft; 51292e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 513343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 514343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 515343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 516343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 517343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 518c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 519c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// are input. This SUnit graph is similar to the SelectionDAG, but 520c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// excludes nodes that aren't interesting to scheduling, and represents 52129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner/// glued together nodes with a single SUnit. 52298976e4dcd18adbbe676048c0069e67346eb4adeDan Gohmanvoid ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 523302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng // Cluster certain nodes which should be scheduled together. 524302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng ClusterNodes(); 525c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Populate the SUnits array. 526c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman BuildSchedUnits(); 527c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Compute all the scheduling dependencies between nodes. 528c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman AddSchedEdges(); 529c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 530c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 53192e946630d5f9bb092853b93501387dd216899b9Andrew Trick// Initialize NumNodeDefs for the current Node's opcode. 53292e946630d5f9bb092853b93501387dd216899b9Andrew Trickvoid ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() { 53329449448b0f0420dfcf52e278fc01adbf1690d70Eric Christopher // Check for phys reg copy. 53429449448b0f0420dfcf52e278fc01adbf1690d70Eric Christopher if (!Node) 53529449448b0f0420dfcf52e278fc01adbf1690d70Eric Christopher return; 53629449448b0f0420dfcf52e278fc01adbf1690d70Eric Christopher 53792e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (!Node->isMachineOpcode()) { 53892e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (Node->getOpcode() == ISD::CopyFromReg) 53992e946630d5f9bb092853b93501387dd216899b9Andrew Trick NodeNumDefs = 1; 54092e946630d5f9bb092853b93501387dd216899b9Andrew Trick else 54192e946630d5f9bb092853b93501387dd216899b9Andrew Trick NodeNumDefs = 0; 54292e946630d5f9bb092853b93501387dd216899b9Andrew Trick return; 54392e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 54492e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned POpc = Node->getMachineOpcode(); 54592e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (POpc == TargetOpcode::IMPLICIT_DEF) { 54692e946630d5f9bb092853b93501387dd216899b9Andrew Trick // No register need be allocated for this. 54792e946630d5f9bb092853b93501387dd216899b9Andrew Trick NodeNumDefs = 0; 54892e946630d5f9bb092853b93501387dd216899b9Andrew Trick return; 54992e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 55092e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs(); 55192e946630d5f9bb092853b93501387dd216899b9Andrew Trick // Some instructions define regs that are not represented in the selection DAG 55292e946630d5f9bb092853b93501387dd216899b9Andrew Trick // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues. 55392e946630d5f9bb092853b93501387dd216899b9Andrew Trick NodeNumDefs = std::min(Node->getNumValues(), NRegDefs); 55492e946630d5f9bb092853b93501387dd216899b9Andrew Trick DefIdx = 0; 55592e946630d5f9bb092853b93501387dd216899b9Andrew Trick} 55692e946630d5f9bb092853b93501387dd216899b9Andrew Trick 55792e946630d5f9bb092853b93501387dd216899b9Andrew Trick// Construct a RegDefIter for this SUnit and find the first valid value. 55892e946630d5f9bb092853b93501387dd216899b9Andrew TrickScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU, 55992e946630d5f9bb092853b93501387dd216899b9Andrew Trick const ScheduleDAGSDNodes *SD) 56092e946630d5f9bb092853b93501387dd216899b9Andrew Trick : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) { 56192e946630d5f9bb092853b93501387dd216899b9Andrew Trick InitNodeNumDefs(); 56292e946630d5f9bb092853b93501387dd216899b9Andrew Trick Advance(); 56392e946630d5f9bb092853b93501387dd216899b9Andrew Trick} 56492e946630d5f9bb092853b93501387dd216899b9Andrew Trick 56592e946630d5f9bb092853b93501387dd216899b9Andrew Trick// Advance to the next valid value defined by the SUnit. 56692e946630d5f9bb092853b93501387dd216899b9Andrew Trickvoid ScheduleDAGSDNodes::RegDefIter::Advance() { 56792e946630d5f9bb092853b93501387dd216899b9Andrew Trick for (;Node;) { // Visit all glued nodes. 56892e946630d5f9bb092853b93501387dd216899b9Andrew Trick for (;DefIdx < NodeNumDefs; ++DefIdx) { 56992e946630d5f9bb092853b93501387dd216899b9Andrew Trick if (!Node->hasAnyUseOfValue(DefIdx)) 57092e946630d5f9bb092853b93501387dd216899b9Andrew Trick continue; 571860e7cdab9d5eceda5ac52ae0ddfb4bdab0067f2Patrik Hagglund ValueType = Node->getSimpleValueType(DefIdx); 57292e946630d5f9bb092853b93501387dd216899b9Andrew Trick ++DefIdx; 57392e946630d5f9bb092853b93501387dd216899b9Andrew Trick return; // Found a normal regdef. 57492e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 57592e946630d5f9bb092853b93501387dd216899b9Andrew Trick Node = Node->getGluedNode(); 576dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Node) { 57792e946630d5f9bb092853b93501387dd216899b9Andrew Trick return; // No values left to visit. 57892e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 57992e946630d5f9bb092853b93501387dd216899b9Andrew Trick InitNodeNumDefs(); 58092e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 58192e946630d5f9bb092853b93501387dd216899b9Andrew Trick} 58292e946630d5f9bb092853b93501387dd216899b9Andrew Trick 58392e946630d5f9bb092853b93501387dd216899b9Andrew Trickvoid ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) { 58492e946630d5f9bb092853b93501387dd216899b9Andrew Trick assert(SU->NumRegDefsLeft == 0 && "expect a new node"); 58592e946630d5f9bb092853b93501387dd216899b9Andrew Trick for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) { 58692e946630d5f9bb092853b93501387dd216899b9Andrew Trick assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected"); 58792e946630d5f9bb092853b93501387dd216899b9Andrew Trick ++SU->NumRegDefsLeft; 58892e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 58992e946630d5f9bb092853b93501387dd216899b9Andrew Trick} 59092e946630d5f9bb092853b93501387dd216899b9Andrew Trick 591953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trickvoid ScheduleDAGSDNodes::computeLatency(SUnit *SU) { 59287896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick SDNode *N = SU->getNode(); 59387896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick 59487896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick // TokenFactor operands are considered zero latency, and some schedulers 59587896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero 59687896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick // whenever node latency is nonzero. 59787896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick if (N && N->getOpcode() == ISD::TokenFactor) { 59887896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick SU->Latency = 0; 59987896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick return; 60087896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick } 60187896d9368e08d93493427ce7bf8272d1e5cca35Andrew Trick 602e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng // Check to see if the scheduler cares about latencies. 603953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick if (forceUnitLatencies()) { 604e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng SU->Latency = 1; 605e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng return; 606e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng } 607e163168aab987dc3df0845b9e92310f764d8b158Evan Cheng 6083ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng if (!InstrItins || InstrItins->isEmpty()) { 6095e84e3ccaa555bd48ecca384e93e55abd76fb40aAndrew Trick if (N && N->isMachineOpcode() && 6105e84e3ccaa555bd48ecca384e93e55abd76fb40aAndrew Trick TII->isHighLatencyDef(N->getMachineOpcode())) 611e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick SU->Latency = HighLatencyCycles; 612e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick else 613e0ef509aeb47b396cf1bdc170ca4f468f799719fAndrew Trick SU->Latency = 1; 61415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 61515a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng } 616cd5af07c4573c6b1270d6737e76ef3219091a733Andrew Trick 617343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Compute the latency for the node. We use the sum of the latencies for 61829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // all nodes glued together into this SUnit. 619343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = 0; 62029d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) 6218239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng if (N->isMachineOpcode()) 6228239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng SU->Latency += TII->getInstrLatency(InstrItins, N); 623343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 624343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 625953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trickvoid ScheduleDAGSDNodes::computeOperandLatency(SDNode *Def, SDNode *Use, 62615a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned OpIdx, SDep& dep) const{ 62715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng // Check to see if the scheduler cares about latencies. 628953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick if (forceUnitLatencies()) 62915a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 63015a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 63115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng if (dep.getKind() != SDep::Data) 63215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return; 63315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 63415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 6357e2fe9150f905167f6685c9730911c2abc08293cEvan Cheng if (Use->isMachineOpcode()) 6367e2fe9150f905167f6685c9730911c2abc08293cEvan Cheng // Adjust the use operand index by num of defs. 6377e2fe9150f905167f6685c9730911c2abc08293cEvan Cheng OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs(); 638a0792de66c8364d47b0a688c7f408efb7b10f31bEvan Cheng int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx); 639089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg && 640089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng !BB->succ_empty()) { 641089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg(); 642089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Reg)) 643089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng // This copy is a liveout value. It is likely coalesced, so reduce the 644089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng // latency so not to penalize the def. 645089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng // FIXME: need target specific adjustment here? 646089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng Latency = (Latency > 1) ? Latency - 1 : 1; 647089751535d6e9adf65842e2ca5867bf9a70e1e95Evan Cheng } 6483881cb7a5d54c0011b40997adcd742e1c7b91abdEvan Cheng if (Latency >= 0) 6493881cb7a5d54c0011b40997adcd742e1c7b91abdEvan Cheng dep.setLatency(Latency); 65015a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng} 65115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 652343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 653b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 654c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (!SU->getNode()) { 65584fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "PHYS REG COPY\n"; 656c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng return; 657c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 658c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng 659c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SU->getNode()->dump(DAG); 66084fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "\n"; 66129d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SmallVector<SDNode *, 4> GluedNodes; 66229d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 66329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.push_back(N); 66429d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner while (!GluedNodes.empty()) { 66584fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << " "; 66629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.back()->dump(DAG); 66784fa8229bbd3813505b7e8d6555fb2e522104e30David Greene dbgs() << "\n"; 66829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.pop_back(); 669343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 67077e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 671343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 672bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 673b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 67473ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trickvoid ScheduleDAGSDNodes::dumpSchedule() const { 67573ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 67673ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick if (SUnit *SU = Sequence[i]) 67773ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick SU->dump(this); 67873ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick else 67973ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick dbgs() << "**** NOOP ****\n"; 68073ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick } 68173ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick} 68277e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 68373ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick 6844c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick#ifndef NDEBUG 6854c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// VerifyScheduledSequence - Verify that all SUnits were scheduled and that 6864c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// their state is consistent with the nodes listed in Sequence. 6874c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// 6884c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trickvoid ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) { 6894c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp); 6904c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick unsigned Noops = 0; 6914c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 6924c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick if (!Sequence[i]) 6934c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick ++Noops; 6944c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick assert(Sequence.size() - Noops == ScheduledNodes && 6954c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick "The number of nodes scheduled doesn't match the expected number!"); 6964c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick} 6974c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick#endif // NDEBUG 6984c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick 6997a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// ProcessSDDbgValues - Process SDDbgValues associated with this node. 700a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topperstatic void 701a0ec3f9b7b826b9b40b80199923b664bad808cceCraig TopperProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, 702a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders, 703a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper DenseMap<SDValue, unsigned> &VRBaseMap, unsigned Order) { 70455d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel if (!N->getHasDebugValue()) 70555d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel return; 70655d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel 70755d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel // Opportunistically insert immediate dbg_value uses, i.e. those with source 70855d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel // order number right after the N. 70955d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel MachineBasicBlock *BB = Emitter.getBlock(); 71055d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 71122a54c1cd711afccd4558374918d12a939e1cca5Benjamin Kramer ArrayRef<SDDbgValue*> DVs = DAG->GetDbgValues(N); 71255d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 71355d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel if (DVs[i]->isInvalidated()) 71455d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel continue; 71555d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel unsigned DVOrder = DVs[i]->getOrder(); 71655d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel if (!Order || DVOrder == ++Order) { 71755d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 71855d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel if (DbgMI) { 71955d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel Orders.push_back(std::make_pair(DVOrder, DbgMI)); 72055d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel BB->insert(InsertPos, DbgMI); 72155d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel } 72255d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel DVs[i]->setIsInvalidated(); 72355d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel } 72455d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel } 72555d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel} 72655d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel 727bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng// ProcessSourceNode - Process nodes with source order numbers. These are added 728d27946d1d4272d7e2bbee00fac020dc8147dfd25Jim Grosbach// to a vector which EmitSchedule uses to determine how to insert dbg_value 729bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng// instructions in the right order. 730a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topperstatic void 731a0ec3f9b7b826b9b40b80199923b664bad808cceCraig TopperProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, 732a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper DenseMap<SDValue, unsigned> &VRBaseMap, 733a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders, 734a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallSet<unsigned, 8> &Seen) { 735dd0fb018a7cd2214c7bc5c6c767f626f99b47ba9Andrew Trick unsigned Order = N->getIROrder(); 73639078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel if (!Order || !Seen.insert(Order)) { 73739078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel // Process any valid SDDbgValues even if node does not have any order 73839078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel // assigned. 73939078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0); 740bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return; 74139078a8bde256ee22e981713a4d2ff8235dc7706Devang Patel } 742bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 743bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineBasicBlock *BB = Emitter.getBlock(); 7446cd04fdaae8c604aca3696ba120bde26a2ee9b67Bill Schmidt if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI() || 7456cd04fdaae8c604aca3696ba120bde26a2ee9b67Bill Schmidt // Fast-isel may have inserted some instructions, in which case the 7466cd04fdaae8c604aca3696ba120bde26a2ee9b67Bill Schmidt // BB->back().isPHI() test will not fire when we want it to. 74736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::prev(Emitter.getInsertPos())->isPHI()) { 748bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Did not insert any instruction. 749dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Orders.push_back(std::make_pair(Order, (MachineInstr*)nullptr)); 750bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return; 751bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 752bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 75336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Orders.push_back(std::make_pair(Order, std::prev(Emitter.getInsertPos()))); 75455d20e8ff1e458f177302386d14f1a4dbdd86028Devang Patel ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order); 755bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng} 756bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 75784b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trickvoid ScheduleDAGSDNodes:: 75884b454d1a270a5d685e01686ed15e68c44b0b56aAndrew TrickEmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, 75984b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick MachineBasicBlock::iterator InsertPos) { 76084b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 76184b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick I != E; ++I) { 76284b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick if (I->isCtrl()) continue; // ignore chain preds 76384b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick if (I->getSUnit()->CopyDstRC) { 76484b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick // Copy to physical register. 76584b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->getSUnit()); 76684b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick assert(VRI != VRBaseMap.end() && "Node emitted out of order - late"); 76784b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick // Find the destination physical register. 76884b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick unsigned Reg = 0; 76984b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick for (SUnit::const_succ_iterator II = SU->Succs.begin(), 77084b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick EE = SU->Succs.end(); II != EE; ++II) { 77184b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick if (II->isCtrl()) continue; // ignore chain preds 77284b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick if (II->getReg()) { 77384b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick Reg = II->getReg(); 77484b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick break; 77584b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick } 77684b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick } 77784b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg) 77884b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick .addReg(VRI->second); 77984b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick } else { 78084b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick // Copy from physical register. 78184b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick assert(I->getReg() && "Unknown physical register!"); 78284b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC); 78384b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second; 78484b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick (void)isNew; // Silence compiler warning. 78584b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick assert(isNew && "Node emitted out of order - early"); 78684b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase) 78784b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick .addReg(I->getReg()); 78884b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick } 78984b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick break; 79084b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick } 79184b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick} 792bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 79384b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick/// EmitSchedule - Emit the machine code in scheduled order. Return the new 79484b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick/// InsertPos and MachineBasicBlock that contains this insertion 79584b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick/// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does 79684b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick/// not necessarily refer to returned BB. The emitter may split blocks. 79747c144505b9be28ed22c626b3a407c11dba2fec5Andrew TrickMachineBasicBlock *ScheduleDAGSDNodes:: 79847c144505b9be28ed22c626b3a407c11dba2fec5Andrew TrickEmitSchedule(MachineBasicBlock::iterator &InsertPos) { 799bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman InstrEmitter Emitter(BB, InsertPos); 800bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman DenseMap<SDValue, unsigned> VRBaseMap; 801bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman DenseMap<SUnit*, unsigned> CopyVRBaseMap; 802bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 803bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SmallSet<unsigned, 8> Seen; 804bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng bool HasDbg = DAG->hasDebugValues(); 805bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen 806fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // If this is the first BB, emit byval parameter dbg_value's. 807fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 808fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 809fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 810fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen for (; PDI != PDE; ++PDI) { 811891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 812fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen if (DbgMI) 81384023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman BB->insert(InsertPos, DbgMI); 814fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen } 815fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen } 816fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen 817bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 818bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman SUnit *SU = Sequence[i]; 819bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman if (!SU) { 820bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // Null SUnit* is a noop. 82184b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick TII->insertNoop(*Emitter.getBlock(), InsertPos); 822bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman continue; 823bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 824bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 825bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // For pre-regalloc scheduling, create instructions corresponding to the 82629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner // SDNode and any glued SDNodes and append them to the block. 827bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman if (!SU->getNode()) { 828bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman // Emit a copy. 82984b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos); 830bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman continue; 831bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 832bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 83329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SmallVector<SDNode *, 4> GluedNodes; 834d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 83529d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.push_back(N); 83629d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner while (!GluedNodes.empty()) { 83729d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner SDNode *N = GluedNodes.back(); 83829d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner Emitter.EmitNode(GluedNodes.back(), SU->OrigNode != SU, SU->isCloned, 839af1d8ca44a18f304f207e209b3bdb94b590f86ffDan Gohman VRBaseMap); 840fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Remember the source order of the inserted instruction. 841bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) 842891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 84329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner GluedNodes.pop_back(); 844bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 845bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 846af1d8ca44a18f304f207e209b3bdb94b590f86ffDan Gohman VRBaseMap); 847fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Remember the source order of the inserted instruction. 848bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) 849891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 850bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng Seen); 851bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 852bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 853fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // Insert all the dbg_values which have not already been inserted in source 854bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // order sequence. 855bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (HasDbg) { 85684023e0fbefc406a4c611d3d64a10df5d3a97dd7Dan Gohman MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 857bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 858bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Sort the source order instructions and use the order to insert debug 859bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // values. 8600b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer std::sort(Orders.begin(), Orders.end(), less_first()); 861bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 862bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 863bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 864bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Now emit the rest according to source order. 865bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned LastOrder = 0; 866bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 867bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng unsigned Order = Orders[i].first; 868bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng MachineInstr *MI = Orders[i].second; 869bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Insert all SDDbgValue's whose order(s) are before "Order". 870bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if (!MI) 871bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng continue; 872bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng for (; DI != DE && 873bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 874bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng if ((*DI)->isInvalidated()) 875bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng continue; 876891ff8fbd61a06ef8ea57461fa377ebbb663ed09Dan Gohman MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 877962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (DbgMI) { 878962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng if (!LastOrder) 879962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng // Insert to start of the BB (after PHIs). 880962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng BB->insert(BBBegin, DbgMI); 881962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng else { 882a8dab36f3dfdfcd3f74224afa4ffb32776674c93Dan Gohman // Insert at the instruction, which may be in a different 883a8dab36f3dfdfcd3f74224afa4ffb32776674c93Dan Gohman // block, if the block was split by a custom inserter. 884962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng MachineBasicBlock::iterator Pos = MI; 8859edb37feb5984b25494651ee4307fd2284d3538bAndrew Trick MI->getParent()->insert(Pos, DbgMI); 886962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng } 887bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 888bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen } 889bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng LastOrder = Order; 890bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 891bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // Add trailing DbgValue's before the terminator. FIXME: May want to add 892bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // some of them before one or more conditional branches? 8937bf116acd417e50f6fac677b9cb9204ee7f35c00Bill Wendling SmallVector<MachineInstr*, 8> DbgMIs; 894bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng while (DI != DE) { 8957bf116acd417e50f6fac677b9cb9204ee7f35c00Bill Wendling if (!(*DI)->isInvalidated()) 8967bf116acd417e50f6fac677b9cb9204ee7f35c00Bill Wendling if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap)) 8977bf116acd417e50f6fac677b9cb9204ee7f35c00Bill Wendling DbgMIs.push_back(DbgMI); 898bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng ++DI; 899bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 9007bf116acd417e50f6fac677b9cb9204ee7f35c00Bill Wendling 9017bf116acd417e50f6fac677b9cb9204ee7f35c00Bill Wendling MachineBasicBlock *InsertBB = Emitter.getBlock(); 9027bf116acd417e50f6fac677b9cb9204ee7f35c00Bill Wendling MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator(); 9037bf116acd417e50f6fac677b9cb9204ee7f35c00Bill Wendling InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end()); 904bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman } 905bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman 906bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman InsertPos = Emitter.getInsertPos(); 90747c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick return Emitter.getBlock(); 908bcea859fc1dd1af9ac66ec93ea04ce9a19c8451cDan Gohman} 90956b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick 91056b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick/// Return the basic block label. 91156b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trickstd::string ScheduleDAGSDNodes::getDAGName() const { 91256b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick return "sunit-dag." + BB->getFullName(); 91356b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick} 914