ScheduleDAGSDNodes.cpp revision 3881cb7a5d54c0011b40997adcd742e1c7b91abd
1aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// 2aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// 3aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// The LLVM Compiler Infrastructure 4aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// 5aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// This file is distributed under the University of Illinois Open Source 6aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// License. See LICENSE.TXT for details. 7aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// 8aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger//===----------------------------------------------------------------------===// 9aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// 10aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// This implements the ScheduleDAG class, which is a base class used by 11aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// scheduling implementation classes. 12aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// 13aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger//===----------------------------------------------------------------------===// 14aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 15aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#define DEBUG_TYPE "pre-RA-sched" 16aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "SDNodeDbgValue.h" 17aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "ScheduleDAGSDNodes.h" 18aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "InstrEmitter.h" 19aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/CodeGen/SelectionDAG.h" 20aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/Target/TargetMachine.h" 21aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/Target/TargetInstrInfo.h" 22aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/Target/TargetLowering.h" 23aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/Target/TargetRegisterInfo.h" 24aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/Target/TargetSubtarget.h" 25aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/ADT/DenseMap.h" 26aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/ADT/SmallPtrSet.h" 27aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/ADT/SmallSet.h" 28aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/ADT/SmallVector.h" 29aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/ADT/Statistic.h" 30aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/Support/Debug.h" 31aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#include "llvm/Support/raw_ostream.h" 32aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerusing namespace llvm; 33aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 34aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerSTATISTIC(LoadsClustered, "Number of loads clustered together"); 35aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 36aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 37aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger : ScheduleDAG(mf), 38aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger InstrItins(mf.getTarget().getInstrItineraryData()) {} 39aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 40aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// Run - perform scheduling. 41aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// 42aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 43aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger MachineBasicBlock::iterator insertPos) { 44aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger DAG = dag; 45aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger ScheduleDAG::Run(bb, insertPos); 46aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 47aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 48aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// NewSUnit - Creates a new SUnit and return a ptr to it. 49aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// 50aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerSUnit *ScheduleDAGSDNodes::NewSUnit(SDNode *N) { 51aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#ifndef NDEBUG 52aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const SUnit *Addr = 0; 53aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!SUnits.empty()) 54aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Addr = &SUnits[0]; 55aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger#endif 5608fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 57ae665a522bd46bea44c5ea84c89c8b1731954170Stephen Hemminger assert((Addr == 0 || Addr == &SUnits[0]) && 58aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger "SUnits std::vector reallocated on the fly!"); 59aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SUnits.back().OrigNode = &SUnits.back(); 60aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SUnit *SU = &SUnits.back(); 61aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 62aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!N || 63aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger (N->isMachineOpcode() && 64aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)) 651db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer SU->SchedulingPref = Sched::None; 661db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer else 67aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->SchedulingPref = TLI.getSchedulingPreference(N); 68aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return SU; 69aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 70aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 71aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 721db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer SUnit *SU = NewSUnit(Old->getNode()); 73aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->OrigNode = Old->OrigNode; 74f332d169246447bd5e258ac03d5ee840a70adb1eshemminger SU->Latency = Old->Latency; 75aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->isTwoAddress = Old->isTwoAddress; 76aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->isCommutable = Old->isCommutable; 77aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->hasPhysRegDefs = Old->hasPhysRegDefs; 78aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 79aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->SchedulingPref = Old->SchedulingPref; 80aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Old->isCloned = true; 81aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return SU; 821db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer} 83aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 84aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// CheckForPhysRegDependency - Check if the dependency between def and use of 85aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// a specified operand is a physical register dependency. If so, returns the 86aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// register and the cost of copying the register. 87aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 88aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const TargetRegisterInfo *TRI, 89aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const TargetInstrInfo *TII, 90aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned &PhysReg, int &Cost) { 91aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 92aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 93aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 94aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 95aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (TargetRegisterInfo::isVirtualRegister(Reg)) 96aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 97aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 981db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer unsigned ResNo = User->getOperand(2).getResNo(); 99aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (Def->isMachineOpcode()) { 100aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 101aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (ResNo >= II.getNumDefs() && 102aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 103aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger PhysReg = Reg; 1041db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer const TargetRegisterClass *RC = 105aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 106aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Cost = RC->getCopyCost(); 107aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 108aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 109aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 1101db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer 111aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerstatic void AddFlags(SDNode *N, SDValue Flag, bool AddFlag, 112aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SelectionDAG *DAG) { 113aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallVector<EVT, 4> VTs; 114aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *FlagDestNode = Flag.getNode(); 115aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 116aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Don't add a flag from a node to itself. 11708fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer if (FlagDestNode == N) return; 11808fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer 11908fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer // Don't add a flag to something which already has a flag. 12008fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer if (N->getValueType(N->getNumValues() - 1) == MVT::Flag) return; 12108fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer 1221db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 123aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger VTs.push_back(N->getValueType(I)); 124aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 125aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (AddFlag) 126aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger VTs.push_back(MVT::Flag); 127aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 128aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallVector<SDValue, 4> Ops; 129aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 130aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Ops.push_back(N->getOperand(I)); 131aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 132aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (FlagDestNode) 133aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Ops.push_back(Flag); 134aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 135aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 136aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger MachineSDNode::mmo_iterator Begin = 0, End = 0; 137aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 138aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 139aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Store memory references. 140aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (MN) { 141aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Begin = MN->memoperands_begin(); 142aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger End = MN->memoperands_end(); 143aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 144aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 145aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 146d5f46f9cc3856af532e852ef29fd7ddfd141faf0Jesper Dangaard Brouer 14708fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer // Reset the memory references 148d5f46f9cc3856af532e852ef29fd7ddfd141faf0Jesper Dangaard Brouer if (MN) 149aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger MN->setMemRefs(Begin, End); 150aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 151aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 152aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// ClusterNeighboringLoads - Force nearby loads together by "flagging" them. 153aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// This function finds loads of the same base and different offsets. If the 154aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// offsets are not far apart (target specific), it add MVT::Flag inputs and 155aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// outputs to ensure they are scheduled together and in order. This 156476daa7278aaf324f6cef27981f81187afce8836Patrick McHardy/// optimization may benefit some targets by improving cache locality. 157aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 158aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *Chain = 0; 159aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned NumOps = Node->getNumOperands(); 160034102f2589b79e92ff677dc74a54096ef10d99dn); if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 161aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Chain = Node->getOperand(NumOps-1).getNode(); 162aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!Chain) 163aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 164aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 165aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Look for other loads of the same chain. Find loads that are loading from 166aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // the same base pointer and different offsets. 167aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallPtrSet<SDNode*, 16> Visited; 168aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallVector<int64_t, 4> Offsets; 169aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 170aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger bool Cluster = false; 171034102f2589b79e92ff677dc74a54096ef10d99dvoid *) NLMSG_TAIL(n) - (void *) tail; SDNode *Base = Node; 172aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); 173aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger I != E; ++I) { 174aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *User = *I; 175aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (User == Node || !Visited.insert(User)) 176aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger continue; 177aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger int64_t Offset1, Offset2; 178aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || 179aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Offset1 == Offset2) 180aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // FIXME: Should be ok if they addresses are identical. But earlier 181aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // optimizations really should have eliminated one of the loads. 182aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger continue; 183aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (O2SMap.insert(std::make_pair(Offset1, Base)).second) 184aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Offsets.push_back(Offset1); 185ae665a522bd46bea44c5ea84c89c8b1731954170Stephen Hemminger O2SMap.insert(std::make_pair(Offset2, User)); 186aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Offsets.push_back(Offset2); 187aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (Offset2 < Offset1) 188aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Base = User; 18908fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer Cluster = true; 190aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 191aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 192aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!Cluster) 193aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 194aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 195aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Sort them in increasing order. 196aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger std::sort(Offsets.begin(), Offsets.end()); 197aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 198aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Check if the loads are close enough. 1991db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer SmallVector<SDNode*, 4> Loads; 200aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned NumLoads = 0; 201aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger int64_t BaseOff = Offsets[0]; 202aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *BaseLoad = O2SMap[BaseOff]; 203aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Loads.push_back(BaseLoad); 204aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 2051db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer int64_t Offset = Offsets[i]; 206aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *Load = O2SMap[Offset]; 207aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 208aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger break; // Stop right here. Ignore loads that are further away. 209aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Loads.push_back(Load); 210aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger ++NumLoads; 2111db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer } 212aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 213aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (NumLoads == 0) 214aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 215aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 216aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Cluster loads by adding MVT::Flag outputs and inputs. This also 217aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // ensure they are scheduled in order of increasing addresses. 2181db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer SDNode *Lead = Loads[0]; 219aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger AddFlags(Lead, SDValue(0, 0), true, DAG); 220aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 221aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDValue InFlag = SDValue(Lead, Lead->getNumValues() - 1); 222aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 223aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger bool OutFlag = I < E - 1; 224aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *Load = Loads[I]; 2251db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer 226aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger AddFlags(Load, InFlag, OutFlag, DAG); 227aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 228aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (OutFlag) 229aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger InFlag = SDValue(Load, Load->getNumValues() - 1); 230aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 231aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger ++LoadsClustered; 2321db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer } 233aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 234aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 2351db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer/// ClusterNodes - Cluster certain nodes which should be scheduled together. 236aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// 237aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::ClusterNodes() { 2381db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 239aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger E = DAG->allnodes_end(); NI != E; ++NI) { 240aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *Node = &*NI; 2411db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer if (!Node || !Node->isMachineOpcode()) 242aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger continue; 243aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 2441db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer unsigned Opc = Node->getMachineOpcode(); 245aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const TargetInstrDesc &TID = TII->get(Opc); 246f332d169246447bd5e258ac03d5ee840a70adb1eshemminger if (TID.mayLoad()) 247aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Cluster loads from "near" addresses into combined SUnits. 248aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger ClusterNeighboringLoads(Node); 249aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 250aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 251aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 252aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::BuildSchedUnits() { 253aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // During scheduling, the NodeId field of SDNode is used to map SDNodes 254aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // to their associated SUnits by holding SUnits table indices. A value 2551db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer // of -1 means the SDNode does not yet have an associated SUnit. 256aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned NumNodes = 0; 257aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 258aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger E = DAG->allnodes_end(); NI != E; ++NI) { 259aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger NI->setNodeId(-1); 260aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger ++NumNodes; 261aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 262aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 263aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Reserve entries in the vector for each of the SUnits we are creating. This 264aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 265aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // invalidated. 266aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // FIXME: Multiply by 2 because we may clone nodes during scheduling. 267aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // This is a temporary workaround. 268aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SUnits.reserve(NumNodes * 2); 269aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 270aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Add all nodes in depth first order. 2711db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer SmallVector<SDNode*, 64> Worklist; 272aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallPtrSet<SDNode*, 64> Visited; 273aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Worklist.push_back(DAG->getRoot().getNode()); 274aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Visited.insert(DAG->getRoot().getNode()); 275aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 276aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger while (!Worklist.empty()) { 277aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *NI = Worklist.pop_back_val(); 278aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 279aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Add all operands to the worklist unless they've already been added. 280aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 281aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (Visited.insert(NI->getOperand(i).getNode())) 282aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Worklist.push_back(NI->getOperand(i).getNode()); 283aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 2841db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 285aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger continue; 286aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 287aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // If this node has already been processed, stop now. 288aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (NI->getNodeId() != -1) continue; 289aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 2901db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer SUnit *NodeSUnit = NewSUnit(NI); 291aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 292aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // See if anything is flagged to this node, if so, add them to flagged 293aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // nodes. Nodes can have at most one flag input and one flag output. Flags 294aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // are required to be the last operand and result of a node. 295aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 296aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Scan up to find flagged preds. 2971db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer SDNode *N = NI; 298aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger while (N->getNumOperands() && 299aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 300aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger N = N->getOperand(N->getNumOperands()-1).getNode(); 301aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger assert(N->getNodeId() == -1 && "Node already inserted!"); 302aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger N->setNodeId(NodeSUnit->NodeNum); 3031db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer } 304aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 305aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Scan down to find any flagged succs. 306aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger N = NI; 307aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 308aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDValue FlagVal(N, N->getNumValues()-1); 309aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 3101db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer // There are either zero or one users of the Flag result. 311aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger bool HasFlagUse = false; 312aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 313aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger UI != E; ++UI) 314aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (FlagVal.isOperandOf(*UI)) { 315aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger HasFlagUse = true; 316aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger assert(N->getNodeId() == -1 && "Node already inserted!"); 3171db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer N->setNodeId(NodeSUnit->NodeNum); 318aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger N = *UI; 319aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger break; 320aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 321aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!HasFlagUse) break; 322aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 323aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 324aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // If there are flag operands involved, N is now the bottom-most node 325aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // of the sequence of nodes that are flagged together. 326aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Update the SUnit. 327aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger NodeSUnit->setNode(N); 32808fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer assert(N->getNodeId() == -1 && "Node already inserted!"); 32908fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer N->setNodeId(NodeSUnit->NodeNum); 33008fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer 33108fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer // Assign the Latency field of NodeSUnit using target-provided information. 33208fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer ComputeLatency(NodeSUnit); 3331db5e2ec13402a54aa40b518a5d07dc4a45746caJesper Dangaard Brouer } 334aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 335aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 336aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::AddSchedEdges() { 337aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 338aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 339aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Check to see if the scheduler cares about latencies. 340aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger bool UnitLatencies = ForceUnitLatencies(); 341aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 342aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Pass 2: add the preds, succs, etc. 343aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 344aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SUnit *SU = &SUnits[su]; 345aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *MainNode = SU->getNode(); 346aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 347aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (MainNode->isMachineOpcode()) { 348aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned Opc = MainNode->getMachineOpcode(); 349aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const TargetInstrDesc &TID = TII->get(Opc); 350aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 351d5f46f9cc3856af532e852ef29fd7ddfd141faf0Jesper Dangaard Brouer if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 35208fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer SU->isTwoAddress = true; 353d5f46f9cc3856af532e852ef29fd7ddfd141faf0Jesper Dangaard Brouer break; 354aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 355aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 356aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (TID.isCommutable()) 357aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->isCommutable = true; 358aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 359aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 360aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Find all predecessors and successors of the group. 361aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 362aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (N->isMachineOpcode() && 363aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger TII->get(N->getMachineOpcode()).getImplicitDefs()) { 364aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->hasPhysRegClobbers = true; 365aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned NumUsed = InstrEmitter::CountResults(N); 366aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 367aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger --NumUsed; // Skip over unused values at the end. 368aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 369aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->hasPhysRegDefs = true; 370aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 371aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 372aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 373aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SDNode *OpN = N->getOperand(i).getNode(); 374aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (isPassiveNode(OpN)) continue; // Not scheduled. 375aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SUnit *OpSU = &SUnits[OpN->getNodeId()]; 376aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger assert(OpSU && "Node has no SUnit!"); 377aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (OpSU == SU) continue; // In the same group. 378aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 379aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger EVT OpVT = N->getOperand(i).getValueType(); 380aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 381aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger bool isChain = OpVT == MVT::Other; 382aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 383aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned PhysReg = 0; 384aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger int Cost = 1; 385aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Determine if this is a physical register dependency. 386aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 387aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger assert((PhysReg == 0 || !isChain) && 388aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger "Chain dependence via physreg data?"); 389aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 390aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // emits a copy from the physical register to a virtual register unless 391aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // it requires a cross class copy (cost < 0). That means we are only 392aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // treating "expensive to copy" register dependency as physical register 393aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // dependency. This may change in the future though. 394aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (Cost >= 0) 395aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger PhysReg = 0; 396aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 397aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // If this is a ctrl dep, latency is 1. 398aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned OpLatency = isChain ? 1 : OpSU->Latency; 399aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const SDep &dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 400034102f2589b79e92ff677dc74a54096ef10d99dn); OpLatency, PhysReg); 401aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!isChain && !UnitLatencies) { 402aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger ComputeOperandLatency(OpN, N, i, const_cast<SDep &>(dep)); 403aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger ST.adjustSchedDependency(OpSU, SU, const_cast<SDep &>(dep)); 404aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 405aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 406aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->addPred(dep); 407aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 408aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 409aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 410aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 411aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 412aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 413aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// are input. This SUnit graph is similar to the SelectionDAG, but 414aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// excludes nodes that aren't interesting to scheduling, and represents 415aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// flagged together nodes with a single SUnit. 416aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 417aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Cluster certain nodes which should be scheduled together. 418aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger ClusterNodes(); 419aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Populate the SUnits array. 420034102f2589b79e92ff677dc74a54096ef10d99dvoid *) NLMSG_TAIL(n) - (void *) tail; BuildSchedUnits(); 421aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Compute all the scheduling dependencies between nodes. 422aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger AddSchedEdges(); 423aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 424aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 425aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 426aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Check to see if the scheduler cares about latencies. 427aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (ForceUnitLatencies()) { 428aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->Latency = 1; 429aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 430aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 431aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 432aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!InstrItins || InstrItins->isEmpty()) { 433bd29e35d9de9dc0b9015dd3a178ee2c716ce8301Patrick McHardy SU->Latency = 1; 434aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 435aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 436aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 437aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Compute the latency for the node. We use the sum of the latencies for 438021ed13fdceaa41de91af64825b7ca3e98f00a5etb, TCA_CBQ_MAX, opt); // all nodes flagged together into this SUnit. 439aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->Latency = 0; 440aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 441aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (N->isMachineOpcode()) { 442aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->Latency += InstrItins-> 443aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger getStageLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 444aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 445aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 446aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 447aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::ComputeOperandLatency(SDNode *Def, SDNode *Use, 448aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned OpIdx, SDep& dep) const{ 449aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Check to see if the scheduler cares about latencies. 450aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (ForceUnitLatencies()) 451aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 452aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 453aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!InstrItins || InstrItins->isEmpty()) 454aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 455aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 456aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (dep.getKind() != SDep::Data) 457aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 458aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 459aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 460aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!Def->isMachineOpcode()) 461aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 462aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 463aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 464aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (DefIdx >= II.getNumDefs()) 465aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 466aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 467ae665a522bd46bea44c5ea84c89c8b1731954170Stephen Hemminger int Latency = 0; 468bb6a21a4fcaf400ca4766eea6064f2df30393d1eosdl.net!shemminger if (!Use->isMachineOpcode()) { 469aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Latency = InstrItins->getOperandCycle(II.getSchedClass(), DefIdx); 470aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } else { 471aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned DefClass = II.getSchedClass(); 472aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned UseClass = TII->get(Use->getMachineOpcode()).getSchedClass(); 473aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Latency = InstrItins->getOperandLatency(DefClass, DefIdx, UseClass, OpIdx); 474aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 475aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 476aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (Latency >= 0) 477aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger dep.setLatency(Latency); 478aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 479aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 480aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingervoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 48108fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer if (!SU->getNode()) { 48208fd01843f26beccc734bbd4d8b103327b7be39eJesper Dangaard Brouer dbgs() << "PHYS REG COPY\n"; 483aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 484aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 485aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 486aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SU->getNode()->dump(DAG); 487aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger dbgs() << "\n"; 488aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallVector<SDNode *, 4> FlaggedNodes; 489aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 490aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger FlaggedNodes.push_back(N); 491aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger while (!FlaggedNodes.empty()) { 492aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger dbgs() << " "; 493aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger FlaggedNodes.back()->dump(DAG); 494aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger dbgs() << "\n"; 495aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger FlaggedNodes.pop_back(); 496aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 497aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 498aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 499aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingernamespace { 500aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger struct OrderSorter { 501aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger bool operator()(const std::pair<unsigned, MachineInstr*> &A, 502aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger const std::pair<unsigned, MachineInstr*> &B) { 503aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return A.first < B.first; 504aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 505aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger }; 506aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 507aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 508aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// ProcessSourceNode - Process nodes with source order numbers. These are added 509aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// to a vector which EmitSchedule uses to determine how to insert dbg_value 510aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger// instructions in the right order. 511aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerstatic void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, 512aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger InstrEmitter &Emitter, 513aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger DenseMap<SDValue, unsigned> &VRBaseMap, 514aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 515aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallSet<unsigned, 8> &Seen) { 516aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned Order = DAG->GetOrdering(N); 517aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (!Order || !Seen.insert(Order)) 518bd29e35d9de9dc0b9015dd3a178ee2c716ce8301Patrick McHardy return; 519aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 520aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger MachineBasicBlock *BB = Emitter.getBlock(); 521aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI()) { 522aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Did not insert any instruction. 523bd29e35d9de9dc0b9015dd3a178ee2c716ce8301Patrick McHardy Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); 524aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 525aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 526aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 527aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); 528bd29e35d9de9dc0b9015dd3a178ee2c716ce8301Patrick McHardy if (!N->getHasDebugValue()) 529aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger return; 530aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // Opportunistically insert immediate dbg_value uses, i.e. those with source 531aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // order number right after the N. 532aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 533aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallVector<SDDbgValue*,2> &DVs = DAG->GetDbgValues(N); 534aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 535aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (DVs[i]->isInvalidated()) 536aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger continue; 537aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger unsigned DVOrder = DVs[i]->getOrder(); 538aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (DVOrder == ++Order) { 539aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 540aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger if (DbgMI) { 541aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger Orders.push_back(std::make_pair(DVOrder, DbgMI)); 542aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger BB->insert(InsertPos, DbgMI); 543aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 544aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger DVs[i]->setIsInvalidated(); 545aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 546aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 547aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger} 548aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 549aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 550aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger/// EmitSchedule - Emit the machine code in scheduled order. 551aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemmingerMachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { 552aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger InstrEmitter Emitter(BB, InsertPos); 553aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger DenseMap<SDValue, unsigned> VRBaseMap; 554aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger DenseMap<SUnit*, unsigned> CopyVRBaseMap; 555aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 556aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger SmallSet<unsigned, 8> Seen; 557aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger bool HasDbg = DAG->hasDebugValues(); 558aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger 559aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger // If this is the first BB, emit byval parameter dbg_value's. 56095812b56a5a66e7e9a21744cfe8bc0bb9791ea98net[shemminger]!kaber if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 561f2f99e2eefdbd9cb6a750b19a7b3036db351b983osdl.net!shemminger SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 562f2f99e2eefdbd9cb6a750b19a7b3036db351b983osdl.net!shemminger SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 563f2f99e2eefdbd9cb6a750b19a7b3036db351b983osdl.net!shemminger for (; PDI != PDE; ++PDI) { 564f2f99e2eefdbd9cb6a750b19a7b3036db351b983osdl.net!shemminger MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 565f2f99e2eefdbd9cb6a750b19a7b3036db351b983osdl.net!shemminger if (DbgMI) 566f2f99e2eefdbd9cb6a750b19a7b3036db351b983osdl.net!shemminger BB->insert(InsertPos, DbgMI); 567aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 568aba5acdfdb347d2c21fc67d613d83d4430ca3937osdl.org!shemminger } 569 570 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 571 SUnit *SU = Sequence[i]; 572 if (!SU) { 573 // Null SUnit* is a noop. 574 EmitNoop(); 575 continue; 576 } 577 578 // For pre-regalloc scheduling, create instructions corresponding to the 579 // SDNode and any flagged SDNodes and append them to the block. 580 if (!SU->getNode()) { 581 // Emit a copy. 582 EmitPhysRegCopy(SU, CopyVRBaseMap); 583 continue; 584 } 585 586 SmallVector<SDNode *, 4> FlaggedNodes; 587 for (SDNode *N = SU->getNode()->getFlaggedNode(); N; 588 N = N->getFlaggedNode()) 589 FlaggedNodes.push_back(N); 590 while (!FlaggedNodes.empty()) { 591 SDNode *N = FlaggedNodes.back(); 592 Emitter.EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, SU->isCloned, 593 VRBaseMap); 594 // Remember the source order of the inserted instruction. 595 if (HasDbg) 596 ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 597 FlaggedNodes.pop_back(); 598 } 599 Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 600 VRBaseMap); 601 // Remember the source order of the inserted instruction. 602 if (HasDbg) 603 ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 604 Seen); 605 } 606 607 // Insert all the dbg_values which have not already been inserted in source 608 // order sequence. 609 if (HasDbg) { 610 MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 611 612 // Sort the source order instructions and use the order to insert debug 613 // values. 614 std::sort(Orders.begin(), Orders.end(), OrderSorter()); 615 616 SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 617 SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 618 // Now emit the rest according to source order. 619 unsigned LastOrder = 0; 620 for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 621 unsigned Order = Orders[i].first; 622 MachineInstr *MI = Orders[i].second; 623 // Insert all SDDbgValue's whose order(s) are before "Order". 624 if (!MI) 625 continue; 626#ifndef NDEBUG 627 unsigned LastDIOrder = 0; 628#endif 629 for (; DI != DE && 630 (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 631#ifndef NDEBUG 632 assert((*DI)->getOrder() >= LastDIOrder && 633 "SDDbgValue nodes must be in source order!"); 634 LastDIOrder = (*DI)->getOrder(); 635#endif 636 if ((*DI)->isInvalidated()) 637 continue; 638 MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 639 if (DbgMI) { 640 if (!LastOrder) 641 // Insert to start of the BB (after PHIs). 642 BB->insert(BBBegin, DbgMI); 643 else { 644 // Insert at the instruction, which may be in a different 645 // block, if the block was split by a custom inserter. 646 MachineBasicBlock::iterator Pos = MI; 647 MI->getParent()->insert(llvm::next(Pos), DbgMI); 648 } 649 } 650 } 651 LastOrder = Order; 652 } 653 // Add trailing DbgValue's before the terminator. FIXME: May want to add 654 // some of them before one or more conditional branches? 655 while (DI != DE) { 656 MachineBasicBlock *InsertBB = Emitter.getBlock(); 657 MachineBasicBlock::iterator Pos= Emitter.getBlock()->getFirstTerminator(); 658 if (!(*DI)->isInvalidated()) { 659 MachineInstr *DbgMI= Emitter.EmitDbgValue(*DI, VRBaseMap); 660 if (DbgMI) 661 InsertBB->insert(Pos, DbgMI); 662 } 663 ++DI; 664 } 665 } 666 667 BB = Emitter.getBlock(); 668 InsertPos = Emitter.getInsertPos(); 669 return BB; 670} 671