1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This implements the ScheduleDAG class, which is a base class used by 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// scheduling implementation classes. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define DEBUG_TYPE "pre-RA-sched" 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "SDNodeDbgValue.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "ScheduleDAGSDNodes.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "InstrEmitter.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/SelectionDAG.h" 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/MC/MCInstrItineraries.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetMachine.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetInstrInfo.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetLowering.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetRegisterInfo.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetSubtargetInfo.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMap.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallPtrSet.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallSet.h" 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallVector.h" 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/Statistic.h" 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/CommandLine.h" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(LoadsClustered, "Number of loads clustered together"); 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This allows latency based scheduler to notice high latency instructions 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// without a target itinerary. The choise if number here has more to do with 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// balancing scheduler heursitics than with the actual machine latency. 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic cl::opt<int> HighLatencyCycles( 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "sched-high-latency-cycles", cl::Hidden, cl::init(10), 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::desc("Roughly estimate the number of cycles that 'long latency'" 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "instructions take for targets with no itinerary")); 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : ScheduleDAG(mf), 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InstrItins(mf.getTarget().getInstrItineraryData()) {} 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Run - perform scheduling. 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator insertPos) { 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG = dag; 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScheduleDAG::Run(bb, insertPos); 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// NewSUnit - Creates a new SUnit and return a ptr to it. 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSUnit *ScheduleDAGSDNodes::NewSUnit(SDNode *N) { 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SUnit *Addr = 0; 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!SUnits.empty()) 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Addr = &SUnits[0]; 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((Addr == 0 || Addr == &SUnits[0]) && 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "SUnits std::vector reallocated on the fly!"); 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnits.back().OrigNode = &SUnits.back(); 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *SU = &SUnits.back(); 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!N || 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (N->isMachineOpcode() && 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)) 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->SchedulingPref = Sched::None; 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->SchedulingPref = TLI.getSchedulingPreference(N); 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return SU; 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *SU = NewSUnit(Old->getNode()); 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->OrigNode = Old->OrigNode; 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->Latency = Old->Latency; 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->isVRegCycle = Old->isVRegCycle; 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->isCall = Old->isCall; 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->isCallOp = Old->isCallOp; 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->isTwoAddress = Old->isTwoAddress; 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->isCommutable = Old->isCommutable; 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->hasPhysRegDefs = Old->hasPhysRegDefs; 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->isScheduleHigh = Old->isScheduleHigh; 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->isScheduleLow = Old->isScheduleLow; 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->SchedulingPref = Old->SchedulingPref; 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Old->isCloned = true; 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return SU; 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// CheckForPhysRegDependency - Check if the dependency between def and use of 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// a specified operand is a physical register dependency. If so, returns the 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// register and the cost of copying the register. 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterInfo *TRI, 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetInstrInfo *TII, 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned &PhysReg, int &Cost) { 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TargetRegisterInfo::isVirtualRegister(Reg)) 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ResNo = User->getOperand(2).getResNo(); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Def->isMachineOpcode()) { 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &II = TII->get(Def->getMachineOpcode()); 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ResNo >= II.getNumDefs() && 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PhysReg = Reg; 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *RC = 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Cost = RC->getCopyCost(); 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic void AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) { 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<EVT, 4> VTs; 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDNode *GlueDestNode = Glue.getNode(); 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Don't add glue from a node to itself. 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GlueDestNode == N) return; 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Don't add glue to something which already has glue. 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return; 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VTs.push_back(N->getValueType(I)); 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AddGlue) 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VTs.push_back(MVT::Glue); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDValue, 4> Ops; 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.push_back(N->getOperand(I)); 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GlueDestNode) 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Ops.push_back(Glue); 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineSDNode::mmo_iterator Begin = 0, End = 0; 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Store memory references. 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MN) { 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Begin = MN->memoperands_begin(); 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman End = MN->memoperands_end(); 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Reset the memory references 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MN) 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MN->setMemRefs(Begin, End); 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them. 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This function finds loads of the same base and different offsets. If the 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// offsets are not far apart (target specific), it add MVT::Glue inputs and 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// outputs to ensure they are scheduled together and in order. This 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// optimization may benefit some targets by improving cache locality. 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *Chain = 0; 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumOps = Node->getNumOperands(); 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Chain = Node->getOperand(NumOps-1).getNode(); 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Chain) 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Look for other loads of the same chain. Find loads that are loading from 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the same base pointer and different offsets. 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<SDNode*, 16> Visited; 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<int64_t, 4> Offsets; 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Cluster = false; 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *Base = Node; 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I != E; ++I) { 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *User = *I; 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (User == Node || !Visited.insert(User)) 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t Offset1, Offset2; 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Offset1 == Offset2) 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: Should be ok if they addresses are identical. But earlier 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // optimizations really should have eliminated one of the loads. 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (O2SMap.insert(std::make_pair(Offset1, Base)).second) 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Offsets.push_back(Offset1); 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman O2SMap.insert(std::make_pair(Offset2, User)); 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Offsets.push_back(Offset2); 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Offset2 < Offset1) 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Base = User; 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Cluster = true; 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Cluster) 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Sort them in increasing order. 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::sort(Offsets.begin(), Offsets.end()); 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check if the loads are close enough. 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDNode*, 4> Loads; 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumLoads = 0; 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t BaseOff = Offsets[0]; 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *BaseLoad = O2SMap[BaseOff]; 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loads.push_back(BaseLoad); 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t Offset = Offsets[i]; 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *Load = O2SMap[Offset]; 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; // Stop right here. Ignore loads that are further away. 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Loads.push_back(Load); 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumLoads; 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumLoads == 0) 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Cluster loads by adding MVT::Glue outputs and inputs. This also 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ensure they are scheduled in order of increasing addresses. 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *Lead = Loads[0]; 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AddGlue(Lead, SDValue(0, 0), true, DAG); 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDValue InGlue = SDValue(Lead, Lead->getNumValues() - 1); 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool OutGlue = I < E - 1; 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *Load = Loads[I]; 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AddGlue(Load, InGlue, OutGlue, DAG); 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (OutGlue) 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InGlue = SDValue(Load, Load->getNumValues() - 1); 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++LoadsClustered; 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ClusterNodes - Cluster certain nodes which should be scheduled together. 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::ClusterNodes() { 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = DAG->allnodes_end(); NI != E; ++NI) { 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *Node = &*NI; 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Node || !Node->isMachineOpcode()) 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Opc = Node->getMachineOpcode(); 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &MCID = TII->get(Opc); 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MCID.mayLoad()) 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Cluster loads from "near" addresses into combined SUnits. 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ClusterNeighboringLoads(Node); 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::BuildSchedUnits() { 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // During scheduling, the NodeId field of SDNode is used to map SDNodes 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to their associated SUnits by holding SUnits table indices. A value 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // of -1 means the SDNode does not yet have an associated SUnit. 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumNodes = 0; 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = DAG->allnodes_end(); NI != E; ++NI) { 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NI->setNodeId(-1); 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumNodes; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Reserve entries in the vector for each of the SUnits we are creating. This 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // invalidated. 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: Multiply by 2 because we may clone nodes during scheduling. 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This is a temporary workaround. 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnits.reserve(NumNodes * 2); 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add all nodes in depth first order. 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDNode*, 64> Worklist; 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<SDNode*, 64> Visited; 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Worklist.push_back(DAG->getRoot().getNode()); 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Visited.insert(DAG->getRoot().getNode()); 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<SUnit*, 8> CallSUnits; 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (!Worklist.empty()) { 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *NI = Worklist.pop_back_val(); 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add all operands to the worklist unless they've already been added. 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Visited.insert(NI->getOperand(i).getNode())) 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Worklist.push_back(NI->getOperand(i).getNode()); 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this node has already been processed, stop now. 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NI->getNodeId() != -1) continue; 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *NodeSUnit = NewSUnit(NI); 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // See if anything is glued to this node, if so, add them to glued 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // nodes. Nodes can have at most one glue input and one glue output. Glue 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // is required to be the last operand and result of a node. 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Scan up to find glued preds. 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *N = NI; 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (N->getNumOperands() && 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N = N->getOperand(N->getNumOperands()-1).getNode(); 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() == -1 && "Node already inserted!"); 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setNodeId(NodeSUnit->NodeNum); 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeSUnit->isCall = true; 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Scan down to find any glued succs. 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N = NI; 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (N->getValueType(N->getNumValues()-1) == MVT::Glue) { 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDValue GlueVal(N, N->getNumValues()-1); 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // There are either zero or one users of the Glue result. 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool HasGlueUse = false; 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GlueVal.isOperandOf(*UI)) { 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman HasGlueUse = true; 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() == -1 && "Node already inserted!"); 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setNodeId(NodeSUnit->NodeNum); 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N = *UI; 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeSUnit->isCall = true; 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!HasGlueUse) break; 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NodeSUnit->isCall) 34419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CallSUnits.push_back(NodeSUnit); 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Schedule zero-latency TokenFactor below any nodes that may increase the 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // schedule height. Otherwise, ancestors of the TokenFactor may appear to 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // have false stalls. 34919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NI->getOpcode() == ISD::TokenFactor) 35019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeSUnit->isScheduleLow = true; 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If there are glue operands involved, N is now the bottom-most node 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // of the sequence of nodes that are glued together. 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update the SUnit. 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodeSUnit->setNode(N); 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() == -1 && "Node already inserted!"); 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setNodeId(NodeSUnit->NodeNum); 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute NumRegDefsLeft. This must be done before AddSchedEdges. 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InitNumRegDefsLeft(NodeSUnit); 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Assign the Latency field of NodeSUnit using target-provided information. 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ComputeLatency(NodeSUnit); 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 36519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 36619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Find all call operands. 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!CallSUnits.empty()) { 36819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SUnit *SU = CallSUnits.pop_back_val(); 36919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const SDNode *SUNode = SU->getNode(); SUNode; 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SUNode = SUNode->getGluedNode()) { 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SUNode->getOpcode() != ISD::CopyToReg) 37219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDNode *SrcN = SUNode->getOperand(2).getNode(); 37419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isPassiveNode(SrcN)) continue; // Not scheduled. 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SUnit *SrcSU = &SUnits[SrcN->getNodeId()]; 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SrcSU->isCallOp = true; 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::AddSchedEdges() { 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if the scheduler cares about latencies. 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool UnitLatencies = ForceUnitLatencies(); 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Pass 2: add the preds, succs, etc. 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *SU = &SUnits[su]; 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *MainNode = SU->getNode(); 39119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MainNode->isMachineOpcode()) { 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Opc = MainNode->getMachineOpcode(); 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &MCID = TII->get(Opc); 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->isTwoAddress = true; 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MCID.isCommutable()) 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->isCommutable = true; 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Find all predecessors and successors of the group. 40619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) { 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (N->isMachineOpcode() && 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TII->get(N->getMachineOpcode()).getImplicitDefs()) { 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->hasPhysRegClobbers = true; 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumUsed = InstrEmitter::CountResults(N); 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumUsed; // Skip over unused values at the end. 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->hasPhysRegDefs = true; 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *OpN = N->getOperand(i).getNode(); 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isPassiveNode(OpN)) continue; // Not scheduled. 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *OpSU = &SUnits[OpN->getNodeId()]; 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(OpSU && "Node has no SUnit!"); 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (OpSU == SU) continue; // In the same group. 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT OpVT = N->getOperand(i).getValueType(); 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!"); 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isChain = OpVT == MVT::Other; 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned PhysReg = 0; 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int Cost = 1; 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Determine if this is a physical register dependency. 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((PhysReg == 0 || !isChain) && 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Chain dependence via physreg data?"); 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // emits a copy from the physical register to a virtual register unless 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // it requires a cross class copy (cost < 0). That means we are only 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // treating "expensive to copy" register dependency as physical register 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // dependency. This may change in the future though. 43919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Cost >= 0 && !StressSched) 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PhysReg = 0; 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a ctrl dep, latency is 1. 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OpLatency = isChain ? 1 : OpSU->Latency; 44419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Special-case TokenFactor chains as zero-latency. 44519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if(isChain && OpN->getOpcode() == ISD::TokenFactor) 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OpLatency = 0; 44719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SDep &dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OpLatency, PhysReg); 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isChain && !UnitLatencies) { 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ComputeOperandLatency(OpN, N, i, const_cast<SDep &>(dep)); 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ST.adjustSchedDependency(OpSU, SU, const_cast<SDep &>(dep)); 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!SU->addPred(dep) && !dep.isCtrl() && OpSU->NumRegDefsLeft > 1) { 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Multiple register uses are combined in the same SUnit. For example, 45719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // we could have a set of glued nodes with all their defs consumed by 45819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // another set of glued nodes. Register pressure tracking sees this as 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // a single use, so to keep pressure balanced we reduce the defs. 46019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We can't tell (without more book-keeping) if this results from 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // glued nodes or duplicate operands. As long as we don't reduce 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // NumRegDefsLeft to zero, we handle the common cases well. 46419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman --OpSU->NumRegDefsLeft; 46519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// are input. This SUnit graph is similar to the SelectionDAG, but 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// excludes nodes that aren't interesting to scheduling, and represents 47419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// glued together nodes with a single SUnit. 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Cluster certain nodes which should be scheduled together. 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ClusterNodes(); 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Populate the SUnits array. 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BuildSchedUnits(); 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute all the scheduling dependencies between nodes. 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddSchedEdges(); 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 48419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Initialize NumNodeDefs for the current Node's opcode. 48519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() { 48619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Check for phys reg copy. 48719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Node) 48819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 48919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 49019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Node->isMachineOpcode()) { 49119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Node->getOpcode() == ISD::CopyFromReg) 49219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeNumDefs = 1; 49319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 49419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeNumDefs = 0; 49519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 49619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 49719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned POpc = Node->getMachineOpcode(); 49819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (POpc == TargetOpcode::IMPLICIT_DEF) { 49919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // No register need be allocated for this. 50019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeNumDefs = 0; 50119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 50219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs(); 50419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Some instructions define regs that are not represented in the selection DAG 50519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues. 50619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeNumDefs = std::min(Node->getNumValues(), NRegDefs); 50719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DefIdx = 0; 50819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 50919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Construct a RegDefIter for this SUnit and find the first valid value. 51119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU, 51219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const ScheduleDAGSDNodes *SD) 51319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) { 51419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InitNodeNumDefs(); 51519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Advance(); 51619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 51719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Advance to the next valid value defined by the SUnit. 51919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ScheduleDAGSDNodes::RegDefIter::Advance() { 52019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (;Node;) { // Visit all glued nodes. 52119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (;DefIdx < NodeNumDefs; ++DefIdx) { 52219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Node->hasAnyUseOfValue(DefIdx)) 52319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 52419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValueType = Node->getValueType(DefIdx); 52519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++DefIdx; 52619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; // Found a normal regdef. 52719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 52819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Node = Node->getGluedNode(); 52919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Node == NULL) { 53019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; // No values left to visit. 53119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 53219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InitNodeNumDefs(); 53319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 53419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 53519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 53619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) { 53719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(SU->NumRegDefsLeft == 0 && "expect a new node"); 53819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) { 53919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected"); 54019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++SU->NumRegDefsLeft; 54119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 54219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 54319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDNode *N = SU->getNode(); 54619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TokenFactor operands are considered zero latency, and some schedulers 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero 54919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // whenever node latency is nonzero. 55019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (N && N->getOpcode() == ISD::TokenFactor) { 55119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->Latency = 0; 55219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 55319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 55419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if the scheduler cares about latencies. 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ForceUnitLatencies()) { 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->Latency = 1; 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 56119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!InstrItins || InstrItins->isEmpty()) { 56219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (N && N->isMachineOpcode() && 56319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TII->isHighLatencyDef(N->getMachineOpcode())) 56419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->Latency = HighLatencyCycles; 56519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 56619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->Latency = 1; 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 56919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute the latency for the node. We use the sum of the latencies for 57119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // all nodes glued together into this SUnit. 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->Latency = 0; 57319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) 57419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (N->isMachineOpcode()) 57519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SU->Latency += TII->getInstrLatency(InstrItins, N); 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::ComputeOperandLatency(SDNode *Def, SDNode *Use, 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OpIdx, SDep& dep) const{ 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if the scheduler cares about latencies. 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ForceUnitLatencies()) 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 583894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (dep.getKind() != SDep::Data) 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 586894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 58819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Use->isMachineOpcode()) 58919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Adjust the use operand index by num of defs. 59019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs(); 59119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx); 59219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg && 59319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !BB->succ_empty()) { 59419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg(); 59519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isVirtualRegister(Reg)) 59619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This copy is a liveout value. It is likely coalesced, so reduce the 59719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // latency so not to penalize the def. 59819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // FIXME: need target specific adjustment here? 59919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Latency = (Latency > 1) ? Latency - 1 : 1; 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 60119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Latency >= 0) 60219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dep.setLatency(Latency); 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!SU->getNode()) { 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "PHYS REG COPY\n"; 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 610894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 611894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SU->getNode()->dump(DAG); 612894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "\n"; 61319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<SDNode *, 4> GluedNodes; 61419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 61519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GluedNodes.push_back(N); 61619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!GluedNodes.empty()) { 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " "; 61819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GluedNodes.back()->dump(DAG); 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "\n"; 62019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GluedNodes.pop_back(); 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 625894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct OrderSorter { 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator()(const std::pair<unsigned, MachineInstr*> &A, 627894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const std::pair<unsigned, MachineInstr*> &B) { 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return A.first < B.first; 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 63319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ProcessSDDbgValues - Process SDDbgValues associated with this node. 63419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic void ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, 63519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InstrEmitter &Emitter, 63619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 63719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<SDValue, unsigned> &VRBaseMap, 63819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Order) { 63919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!N->getHasDebugValue()) 64019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 64119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Opportunistically insert immediate dbg_value uses, i.e. those with source 64319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // order number right after the N. 64419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *BB = Emitter.getBlock(); 64519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 64619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArrayRef<SDDbgValue*> DVs = DAG->GetDbgValues(N); 64719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 64819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DVs[i]->isInvalidated()) 64919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 65019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DVOrder = DVs[i]->getOrder(); 65119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Order || DVOrder == ++Order) { 65219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 65319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DbgMI) { 65419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Orders.push_back(std::make_pair(DVOrder, DbgMI)); 65519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BB->insert(InsertPos, DbgMI); 65619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 65719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DVs[i]->setIsInvalidated(); 65819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 65919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 66019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 66119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// ProcessSourceNode - Process nodes with source order numbers. These are added 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// to a vector which EmitSchedule uses to determine how to insert dbg_value 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// instructions in the right order. 665894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, 666894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InstrEmitter &Emitter, 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<SDValue, unsigned> &VRBaseMap, 668894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 669894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSet<unsigned, 8> &Seen) { 670894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Order = DAG->GetOrdering(N); 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Order || !Seen.insert(Order)) { 67219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Process any valid SDDbgValues even if node does not have any order 67319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // assigned. 67419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0); 675894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 67619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *BB = Emitter.getBlock(); 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI()) { 680894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Did not insert any instruction. 681894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 684894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); 68619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order); 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 689894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 690894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// EmitSchedule - Emit the machine code in scheduled order. 691894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanMachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { 692894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InstrEmitter Emitter(BB, InsertPos); 693894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<SDValue, unsigned> VRBaseMap; 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<SUnit*, unsigned> CopyVRBaseMap; 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSet<unsigned, 8> Seen; 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool HasDbg = DAG->hasDebugValues(); 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is the first BB, emit byval parameter dbg_value's. 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 701894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (; PDI != PDE; ++PDI) { 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 705894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DbgMI) 706894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->insert(InsertPos, DbgMI); 707894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 709894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 710894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *SU = Sequence[i]; 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!SU) { 713894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Null SUnit* is a noop. 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EmitNoop(); 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 716894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 717894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 718894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // For pre-regalloc scheduling, create instructions corresponding to the 71919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // SDNode and any glued SDNodes and append them to the block. 720894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!SU->getNode()) { 721894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Emit a copy. 722894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EmitPhysRegCopy(SU, CopyVRBaseMap); 723894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 724894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 725894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 72619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<SDNode *, 4> GluedNodes; 72719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SDNode *N = SU->getNode()->getGluedNode(); N; 72819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman N = N->getGluedNode()) 72919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GluedNodes.push_back(N); 73019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!GluedNodes.empty()) { 73119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDNode *N = GluedNodes.back(); 73219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Emitter.EmitNode(GluedNodes.back(), SU->OrigNode != SU, SU->isCloned, 733894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VRBaseMap); 734894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember the source order of the inserted instruction. 735894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (HasDbg) 736894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 73719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GluedNodes.pop_back(); 738894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 739894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 740894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VRBaseMap); 741894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember the source order of the inserted instruction. 742894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (HasDbg) 743894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 744894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Seen); 745894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 746894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 747894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert all the dbg_values which have not already been inserted in source 748894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // order sequence. 749894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (HasDbg) { 750894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 751894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 752894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Sort the source order instructions and use the order to insert debug 753894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // values. 754894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::sort(Orders.begin(), Orders.end(), OrderSorter()); 755894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 756894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 757894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 758894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now emit the rest according to source order. 759894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned LastOrder = 0; 760894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 761894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Order = Orders[i].first; 762894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *MI = Orders[i].second; 763894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert all SDDbgValue's whose order(s) are before "Order". 764894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MI) 765894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 766894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (; DI != DE && 767894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 768894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((*DI)->isInvalidated()) 769894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 770894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 771894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DbgMI) { 772894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!LastOrder) 773894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert to start of the BB (after PHIs). 774894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->insert(BBBegin, DbgMI); 775894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else { 776894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert at the instruction, which may be in a different 777894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // block, if the block was split by a custom inserter. 778894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator Pos = MI; 779894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MI->getParent()->insert(llvm::next(Pos), DbgMI); 780894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 781894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 782894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 783894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LastOrder = Order; 784894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 785894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add trailing DbgValue's before the terminator. FIXME: May want to add 786894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // some of them before one or more conditional branches? 787894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (DI != DE) { 788894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *InsertBB = Emitter.getBlock(); 789894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator Pos= Emitter.getBlock()->getFirstTerminator(); 790894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!(*DI)->isInvalidated()) { 791894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *DbgMI= Emitter.EmitDbgValue(*DI, VRBaseMap); 792894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DbgMI) 793894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertBB->insert(Pos, DbgMI); 794894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 795894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++DI; 796894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 797894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 798894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 799894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB = Emitter.getBlock(); 800894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertPos = Emitter.getInsertPos(); 801894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return BB; 802894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 803