1193323Sed//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This implements the ScheduleDAGInstrs class, which implements re-scheduling 11193323Sed// of MachineInstrs. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15249423Sdim#include "llvm/CodeGen/ScheduleDAGInstrs.h" 16296417Sdim#include "llvm/ADT/IntEqClasses.h" 17249423Sdim#include "llvm/ADT/MapVector.h" 18249423Sdim#include "llvm/ADT/SmallPtrSet.h" 19249423Sdim#include "llvm/ADT/SmallSet.h" 20193323Sed#include "llvm/Analysis/AliasAnalysis.h" 21218893Sdim#include "llvm/Analysis/ValueTracking.h" 22193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 23288943Sdim#include "llvm/CodeGen/MachineFrameInfo.h" 24276479Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 25198090Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 26193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 27193323Sed#include "llvm/CodeGen/PseudoSourceValue.h" 28239462Sdim#include "llvm/CodeGen/RegisterPressure.h" 29249423Sdim#include "llvm/CodeGen/ScheduleDFS.h" 30249423Sdim#include "llvm/IR/Operator.h" 31239462Sdim#include "llvm/Support/CommandLine.h" 32193323Sed#include "llvm/Support/Debug.h" 33243830Sdim#include "llvm/Support/Format.h" 34193323Sed#include "llvm/Support/raw_ostream.h" 35249423Sdim#include "llvm/Target/TargetInstrInfo.h" 36249423Sdim#include "llvm/Target/TargetMachine.h" 37249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 38249423Sdim#include "llvm/Target/TargetSubtargetInfo.h" 39261991Sdim#include <queue> 40261991Sdim 41193323Sedusing namespace llvm; 42193323Sed 43276479Sdim#define DEBUG_TYPE "misched" 44276479Sdim 45239462Sdimstatic cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, 46239462Sdim cl::ZeroOrMore, cl::init(false), 47280031Sdim cl::desc("Enable use of AA during MI DAG construction")); 48239462Sdim 49276479Sdimstatic cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, 50280031Sdim cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction")); 51276479Sdim 52193323SedScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf, 53280031Sdim const MachineLoopInfo *mli, 54296417Sdim bool RemoveKillFlags) 55296417Sdim : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()), 56296417Sdim RemoveKillFlags(RemoveKillFlags), CanHandleTerminators(false), 57296417Sdim TrackLaneMasks(false), FirstDbgValue(nullptr) { 58223017Sdim DbgValues.clear(); 59243830Sdim 60288943Sdim const TargetSubtargetInfo &ST = mf.getSubtarget(); 61280031Sdim SchedModel.init(ST.getSchedModel(), &ST, TII); 62198396Srdivacky} 63193323Sed 64193323Sed/// getUnderlyingObjectFromInt - This is the function that does the work of 65193323Sed/// looking through basic ptrtoint+arithmetic+inttoptr sequences. 66193323Sedstatic const Value *getUnderlyingObjectFromInt(const Value *V) { 67193323Sed do { 68198090Srdivacky if (const Operator *U = dyn_cast<Operator>(V)) { 69193323Sed // If we find a ptrtoint, we can transfer control back to the 70193323Sed // regular getUnderlyingObjectFromInt. 71198090Srdivacky if (U->getOpcode() == Instruction::PtrToInt) 72193323Sed return U->getOperand(0); 73249423Sdim // If we find an add of a constant, a multiplied value, or a phi, it's 74193323Sed // likely that the other operand will lead us to the base 75193323Sed // object. We don't have to worry about the case where the 76198090Srdivacky // object address is somehow being computed by the multiply, 77193323Sed // because our callers only care when the result is an 78243830Sdim // identifiable object. 79198090Srdivacky if (U->getOpcode() != Instruction::Add || 80193323Sed (!isa<ConstantInt>(U->getOperand(1)) && 81249423Sdim Operator::getOpcode(U->getOperand(1)) != Instruction::Mul && 82249423Sdim !isa<PHINode>(U->getOperand(1)))) 83193323Sed return V; 84193323Sed V = U->getOperand(0); 85193323Sed } else { 86193323Sed return V; 87193323Sed } 88204642Srdivacky assert(V->getType()->isIntegerTy() && "Unexpected operand type!"); 89193323Sed } while (1); 90193323Sed} 91193323Sed 92249423Sdim/// getUnderlyingObjects - This is a wrapper around GetUnderlyingObjects 93193323Sed/// and adds support for basic ptrtoint+arithmetic+inttoptr sequences. 94249423Sdimstatic void getUnderlyingObjects(const Value *V, 95288943Sdim SmallVectorImpl<Value *> &Objects, 96288943Sdim const DataLayout &DL) { 97276479Sdim SmallPtrSet<const Value *, 16> Visited; 98249423Sdim SmallVector<const Value *, 4> Working(1, V); 99193323Sed do { 100249423Sdim V = Working.pop_back_val(); 101249423Sdim 102249423Sdim SmallVector<Value *, 4> Objs; 103288943Sdim GetUnderlyingObjects(const_cast<Value *>(V), Objs, DL); 104249423Sdim 105261991Sdim for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), IE = Objs.end(); 106249423Sdim I != IE; ++I) { 107249423Sdim V = *I; 108280031Sdim if (!Visited.insert(V).second) 109249423Sdim continue; 110249423Sdim if (Operator::getOpcode(V) == Instruction::IntToPtr) { 111249423Sdim const Value *O = 112249423Sdim getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0)); 113249423Sdim if (O->getType()->isPointerTy()) { 114249423Sdim Working.push_back(O); 115249423Sdim continue; 116249423Sdim } 117249423Sdim } 118249423Sdim Objects.push_back(const_cast<Value *>(V)); 119249423Sdim } 120249423Sdim } while (!Working.empty()); 121193323Sed} 122193323Sed 123276479Sdimtypedef PointerUnion<const Value *, const PseudoSourceValue *> ValueType; 124276479Sdimtypedef SmallVector<PointerIntPair<ValueType, 1, bool>, 4> 125261991SdimUnderlyingObjectsVector; 126261991Sdim 127249423Sdim/// getUnderlyingObjectsForInstr - If this machine instr has memory reference 128193323Sed/// information and it can be tracked to a normal reference to a known 129249423Sdim/// object, return the Value for that object. 130249423Sdimstatic void getUnderlyingObjectsForInstr(const MachineInstr *MI, 131261991Sdim const MachineFrameInfo *MFI, 132288943Sdim UnderlyingObjectsVector &Objects, 133288943Sdim const DataLayout &DL) { 134193323Sed if (!MI->hasOneMemOperand() || 135276479Sdim (!(*MI->memoperands_begin())->getValue() && 136276479Sdim !(*MI->memoperands_begin())->getPseudoValue()) || 137198090Srdivacky (*MI->memoperands_begin())->isVolatile()) 138249423Sdim return; 139193323Sed 140276479Sdim if (const PseudoSourceValue *PSV = 141276479Sdim (*MI->memoperands_begin())->getPseudoValue()) { 142288943Sdim // Function that contain tail calls don't have unique PseudoSourceValue 143288943Sdim // objects. Two PseudoSourceValues might refer to the same or overlapping 144288943Sdim // locations. The client code calling this function assumes this is not the 145288943Sdim // case. So return a conservative answer of no known object. 146288943Sdim if (MFI->hasTailCall()) 147288943Sdim return; 148288943Sdim 149276479Sdim // For now, ignore PseudoSourceValues which may alias LLVM IR values 150276479Sdim // because the code that uses this function has no way to cope with 151276479Sdim // such aliases. 152276479Sdim if (!PSV->isAliased(MFI)) { 153276479Sdim bool MayAlias = PSV->mayAlias(MFI); 154276479Sdim Objects.push_back(UnderlyingObjectsVector::value_type(PSV, MayAlias)); 155276479Sdim } 156276479Sdim return; 157276479Sdim } 158276479Sdim 159198090Srdivacky const Value *V = (*MI->memoperands_begin())->getValue(); 160193323Sed if (!V) 161249423Sdim return; 162193323Sed 163249423Sdim SmallVector<Value *, 4> Objs; 164288943Sdim getUnderlyingObjects(V, Objs, DL); 165223017Sdim 166288943Sdim for (Value *V : Objs) { 167276479Sdim if (!isIdentifiedObject(V)) { 168249423Sdim Objects.clear(); 169249423Sdim return; 170249423Sdim } 171249423Sdim 172276479Sdim Objects.push_back(UnderlyingObjectsVector::value_type(V, true)); 173249423Sdim } 174193323Sed} 175193323Sed 176239462Sdimvoid ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) { 177239462Sdim BB = bb; 178193323Sed} 179193323Sed 180234353Sdimvoid ScheduleDAGInstrs::finishBlock() { 181239462Sdim // Subclasses should no longer refer to the old block. 182276479Sdim BB = nullptr; 183234353Sdim} 184234353Sdim 185234353Sdim/// Initialize the DAG and common scheduler state for the current scheduling 186234353Sdim/// region. This does not actually create the DAG, only clears it. The 187234353Sdim/// scheduling driver may call BuildSchedGraph multiple times per scheduling 188234353Sdim/// region. 189234353Sdimvoid ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb, 190234353Sdim MachineBasicBlock::iterator begin, 191234353Sdim MachineBasicBlock::iterator end, 192261991Sdim unsigned regioninstrs) { 193239462Sdim assert(bb == BB && "startBlock should set BB"); 194234353Sdim RegionBegin = begin; 195234353Sdim RegionEnd = end; 196261991Sdim NumRegionInstrs = regioninstrs; 197234353Sdim} 198234353Sdim 199234353Sdim/// Close the current scheduling region. Don't clear any state in case the 200234353Sdim/// driver wants to refer to the previous scheduling region. 201234353Sdimvoid ScheduleDAGInstrs::exitRegion() { 202234353Sdim // Nothing to do. 203234353Sdim} 204234353Sdim 205234353Sdim/// addSchedBarrierDeps - Add dependencies from instructions in the current 206218893Sdim/// list of instructions being scheduled to scheduling barrier by adding 207218893Sdim/// the exit SU to the register defs and use list. This is because we want to 208218893Sdim/// make sure instructions which define registers that are either used by 209218893Sdim/// the terminator or are live-out are properly scheduled. This is 210218893Sdim/// especially important when the definition latency of the return value(s) 211218893Sdim/// are too high to be hidden by the branch or when the liveout registers 212218893Sdim/// used by instructions in the fallthrough block. 213234353Sdimvoid ScheduleDAGInstrs::addSchedBarrierDeps() { 214276479Sdim MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : nullptr; 215218893Sdim ExitSU.setInstr(ExitMI); 216218893Sdim bool AllDepKnown = ExitMI && 217234353Sdim (ExitMI->isCall() || ExitMI->isBarrier()); 218218893Sdim if (ExitMI && AllDepKnown) { 219218893Sdim // If it's a call or a barrier, add dependencies on the defs and uses of 220218893Sdim // instruction. 221218893Sdim for (unsigned i = 0, e = ExitMI->getNumOperands(); i != e; ++i) { 222218893Sdim const MachineOperand &MO = ExitMI->getOperand(i); 223218893Sdim if (!MO.isReg() || MO.isDef()) continue; 224218893Sdim unsigned Reg = MO.getReg(); 225218893Sdim if (Reg == 0) continue; 226218893Sdim 227234353Sdim if (TRI->isPhysicalRegister(Reg)) 228249423Sdim Uses.insert(PhysRegSUOper(&ExitSU, -1, Reg)); 229296417Sdim else if (MO.readsReg()) // ignore undef operands 230296417Sdim addVRegUseDeps(&ExitSU, i); 231218893Sdim } 232218893Sdim } else { 233218893Sdim // For others, e.g. fallthrough, conditional branch, assume the exit 234218893Sdim // uses all the registers that are livein to the successor blocks. 235234353Sdim assert(Uses.empty() && "Uses in set before adding deps?"); 236218893Sdim for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 237218893Sdim SE = BB->succ_end(); SI != SE; ++SI) 238296417Sdim for (const auto &LI : (*SI)->liveins()) { 239296417Sdim if (!Uses.contains(LI.PhysReg)) 240296417Sdim Uses.insert(PhysRegSUOper(&ExitSU, -1, LI.PhysReg)); 241218893Sdim } 242218893Sdim } 243218893Sdim} 244218893Sdim 245234353Sdim/// MO is an operand of SU's instruction that defines a physical register. Add 246234353Sdim/// data dependencies from SU to any uses of the physical register. 247243830Sdimvoid ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { 248243830Sdim const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx); 249234353Sdim assert(MO.isDef() && "expect physreg def"); 250234353Sdim 251234353Sdim // Ask the target if address-backscheduling is desirable, and if so how much. 252288943Sdim const TargetSubtargetInfo &ST = MF.getSubtarget(); 253234353Sdim 254239462Sdim for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); 255239462Sdim Alias.isValid(); ++Alias) { 256234353Sdim if (!Uses.contains(*Alias)) 257234353Sdim continue; 258249423Sdim for (Reg2SUnitsMap::iterator I = Uses.find(*Alias); I != Uses.end(); ++I) { 259249423Sdim SUnit *UseSU = I->SU; 260234353Sdim if (UseSU == SU) 261234353Sdim continue; 262239462Sdim 263243830Sdim // Adjust the dependence latency using operand def/use information, 264243830Sdim // then allow the target to perform its own adjustments. 265249423Sdim int UseOp = I->OpIdx; 266276479Sdim MachineInstr *RegUse = nullptr; 267249423Sdim SDep Dep; 268249423Sdim if (UseOp < 0) 269249423Sdim Dep = SDep(SU, SDep::Artificial); 270249423Sdim else { 271251662Sdim // Set the hasPhysRegDefs only for physreg defs that have a use within 272251662Sdim // the scheduling region. 273251662Sdim SU->hasPhysRegDefs = true; 274249423Sdim Dep = SDep(SU, SDep::Data, *Alias); 275249423Sdim RegUse = UseSU->getInstr(); 276249423Sdim } 277249423Sdim Dep.setLatency( 278261991Sdim SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, RegUse, 279261991Sdim UseOp)); 280243830Sdim 281249423Sdim ST.adjustSchedDependency(SU, UseSU, Dep); 282249423Sdim UseSU->addPred(Dep); 283234353Sdim } 284234353Sdim } 285234353Sdim} 286234353Sdim 287234353Sdim/// addPhysRegDeps - Add register dependencies (data, anti, and output) from 288234353Sdim/// this SUnit to following instructions in the same scheduling region that 289234353Sdim/// depend the physical register referenced at OperIdx. 290234353Sdimvoid ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { 291276479Sdim MachineInstr *MI = SU->getInstr(); 292276479Sdim MachineOperand &MO = MI->getOperand(OperIdx); 293234353Sdim 294234353Sdim // Optionally add output and anti dependencies. For anti 295234353Sdim // dependencies we use a latency of 0 because for a multi-issue 296234353Sdim // target we want to allow the defining instruction to issue 297234353Sdim // in the same cycle as the using instruction. 298234353Sdim // TODO: Using a latency of 1 here for output dependencies assumes 299234353Sdim // there's no cost for reusing registers. 300234353Sdim SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output; 301239462Sdim for (MCRegAliasIterator Alias(MO.getReg(), TRI, true); 302239462Sdim Alias.isValid(); ++Alias) { 303234353Sdim if (!Defs.contains(*Alias)) 304234353Sdim continue; 305249423Sdim for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); I != Defs.end(); ++I) { 306249423Sdim SUnit *DefSU = I->SU; 307234353Sdim if (DefSU == &ExitSU) 308234353Sdim continue; 309234353Sdim if (DefSU != SU && 310234353Sdim (Kind != SDep::Output || !MO.isDead() || 311234353Sdim !DefSU->getInstr()->registerDefIsDead(*Alias))) { 312234353Sdim if (Kind == SDep::Anti) 313243830Sdim DefSU->addPred(SDep(SU, Kind, /*Reg=*/*Alias)); 314234353Sdim else { 315243830Sdim SDep Dep(SU, Kind, /*Reg=*/*Alias); 316261991Sdim Dep.setLatency( 317261991Sdim SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr())); 318243830Sdim DefSU->addPred(Dep); 319234353Sdim } 320234353Sdim } 321234353Sdim } 322234353Sdim } 323234353Sdim 324234353Sdim if (!MO.isDef()) { 325251662Sdim SU->hasPhysRegUses = true; 326234353Sdim // Either insert a new Reg2SUnits entry with an empty SUnits list, or 327234353Sdim // retrieve the existing SUnits list for this register's uses. 328234353Sdim // Push this SUnit on the use list. 329249423Sdim Uses.insert(PhysRegSUOper(SU, OperIdx, MO.getReg())); 330276479Sdim if (RemoveKillFlags) 331276479Sdim MO.setIsKill(false); 332234353Sdim } 333234353Sdim else { 334243830Sdim addPhysRegDataDeps(SU, OperIdx); 335249423Sdim unsigned Reg = MO.getReg(); 336234353Sdim 337234353Sdim // clear this register's use list 338249423Sdim if (Uses.contains(Reg)) 339249423Sdim Uses.eraseAll(Reg); 340234353Sdim 341249423Sdim if (!MO.isDead()) { 342249423Sdim Defs.eraseAll(Reg); 343249423Sdim } else if (SU->isCall) { 344249423Sdim // Calls will not be reordered because of chain dependencies (see 345249423Sdim // below). Since call operands are dead, calls may continue to be added 346249423Sdim // to the DefList making dependence checking quadratic in the size of 347249423Sdim // the block. Instead, we leave only one call at the back of the 348249423Sdim // DefList. 349249423Sdim Reg2SUnitsMap::RangePair P = Defs.equal_range(Reg); 350249423Sdim Reg2SUnitsMap::iterator B = P.first; 351249423Sdim Reg2SUnitsMap::iterator I = P.second; 352249423Sdim for (bool isBegin = I == B; !isBegin; /* empty */) { 353249423Sdim isBegin = (--I) == B; 354249423Sdim if (!I->SU->isCall) 355249423Sdim break; 356249423Sdim I = Defs.erase(I); 357249423Sdim } 358249423Sdim } 359234353Sdim 360234353Sdim // Defs are pushed in the order they are visited and never reordered. 361249423Sdim Defs.insert(PhysRegSUOper(SU, OperIdx, Reg)); 362234353Sdim } 363234353Sdim} 364234353Sdim 365296417SdimLaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const 366296417Sdim{ 367296417Sdim unsigned Reg = MO.getReg(); 368296417Sdim // No point in tracking lanemasks if we don't have interesting subregisters. 369296417Sdim const TargetRegisterClass &RC = *MRI.getRegClass(Reg); 370296417Sdim if (!RC.HasDisjunctSubRegs) 371296417Sdim return ~0u; 372296417Sdim 373296417Sdim unsigned SubReg = MO.getSubReg(); 374296417Sdim if (SubReg == 0) 375296417Sdim return RC.getLaneMask(); 376296417Sdim return TRI->getSubRegIndexLaneMask(SubReg); 377296417Sdim} 378296417Sdim 379234353Sdim/// addVRegDefDeps - Add register output and data dependencies from this SUnit 380234353Sdim/// to instructions that occur later in the same scheduling region if they read 381234353Sdim/// from or write to the virtual register defined at OperIdx. 382234353Sdim/// 383234353Sdim/// TODO: Hoist loop induction variable increments. This has to be 384234353Sdim/// reevaluated. Generally, IV scheduling should be done before coalescing. 385234353Sdimvoid ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { 386296417Sdim MachineInstr *MI = SU->getInstr(); 387296417Sdim MachineOperand &MO = MI->getOperand(OperIdx); 388296417Sdim unsigned Reg = MO.getReg(); 389234353Sdim 390296417Sdim LaneBitmask DefLaneMask; 391296417Sdim LaneBitmask KillLaneMask; 392296417Sdim if (TrackLaneMasks) { 393296417Sdim bool IsKill = MO.getSubReg() == 0 || MO.isUndef(); 394296417Sdim DefLaneMask = getLaneMaskForMO(MO); 395296417Sdim // If we have a <read-undef> flag, none of the lane values comes from an 396296417Sdim // earlier instruction. 397296417Sdim KillLaneMask = IsKill ? ~0u : DefLaneMask; 398296417Sdim 399296417Sdim // Clear undef flag, we'll re-add it later once we know which subregister 400296417Sdim // Def is first. 401296417Sdim MO.setIsUndef(false); 402296417Sdim } else { 403296417Sdim DefLaneMask = ~0u; 404296417Sdim KillLaneMask = ~0u; 405296417Sdim } 406296417Sdim 407296417Sdim if (MO.isDead()) { 408296417Sdim assert(CurrentVRegUses.find(Reg) == CurrentVRegUses.end() && 409296417Sdim "Dead defs should have no uses"); 410296417Sdim } else { 411296417Sdim // Add data dependence to all uses we found so far. 412296417Sdim const TargetSubtargetInfo &ST = MF.getSubtarget(); 413296417Sdim for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Reg), 414296417Sdim E = CurrentVRegUses.end(); I != E; /*empty*/) { 415296417Sdim LaneBitmask LaneMask = I->LaneMask; 416296417Sdim // Ignore uses of other lanes. 417296417Sdim if ((LaneMask & KillLaneMask) == 0) { 418296417Sdim ++I; 419296417Sdim continue; 420296417Sdim } 421296417Sdim 422296417Sdim if ((LaneMask & DefLaneMask) != 0) { 423296417Sdim SUnit *UseSU = I->SU; 424296417Sdim MachineInstr *Use = UseSU->getInstr(); 425296417Sdim SDep Dep(SU, SDep::Data, Reg); 426296417Sdim Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use, 427296417Sdim I->OperandIndex)); 428296417Sdim ST.adjustSchedDependency(SU, UseSU, Dep); 429296417Sdim UseSU->addPred(Dep); 430296417Sdim } 431296417Sdim 432296417Sdim LaneMask &= ~KillLaneMask; 433296417Sdim // If we found a Def for all lanes of this use, remove it from the list. 434296417Sdim if (LaneMask != 0) { 435296417Sdim I->LaneMask = LaneMask; 436296417Sdim ++I; 437296417Sdim } else 438296417Sdim I = CurrentVRegUses.erase(I); 439296417Sdim } 440296417Sdim } 441296417Sdim 442296417Sdim // Shortcut: Singly defined vregs do not have output/anti dependencies. 443239462Sdim if (MRI.hasOneDef(Reg)) 444234353Sdim return; 445234353Sdim 446296417Sdim // Add output dependence to the next nearest defs of this vreg. 447234353Sdim // 448234353Sdim // Unless this definition is dead, the output dependence should be 449234353Sdim // transitively redundant with antidependencies from this definition's 450234353Sdim // uses. We're conservative for now until we have a way to guarantee the uses 451234353Sdim // are not eliminated sometime during scheduling. The output dependence edge 452234353Sdim // is also useful if output latency exceeds def-use latency. 453296417Sdim LaneBitmask LaneMask = DefLaneMask; 454296417Sdim for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg), 455296417Sdim CurrentVRegDefs.end())) { 456296417Sdim // Ignore defs for other lanes. 457296417Sdim if ((V2SU.LaneMask & LaneMask) == 0) 458296417Sdim continue; 459296417Sdim // Add an output dependence. 460296417Sdim SUnit *DefSU = V2SU.SU; 461296417Sdim // Ignore additional defs of the same lanes in one instruction. This can 462296417Sdim // happen because lanemasks are shared for targets with too many 463296417Sdim // subregisters. We also use some representration tricks/hacks where we 464296417Sdim // add super-register defs/uses, to imply that although we only access parts 465296417Sdim // of the reg we care about the full one. 466296417Sdim if (DefSU == SU) 467296417Sdim continue; 468296417Sdim SDep Dep(SU, SDep::Output, Reg); 469296417Sdim Dep.setLatency( 470296417Sdim SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr())); 471296417Sdim DefSU->addPred(Dep); 472296417Sdim 473296417Sdim // Update current definition. This can get tricky if the def was about a 474296417Sdim // bigger lanemask before. We then have to shrink it and create a new 475296417Sdim // VReg2SUnit for the non-overlapping part. 476296417Sdim LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask; 477296417Sdim LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask; 478296417Sdim if (NonOverlapMask != 0) 479296417Sdim CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, V2SU.SU)); 480296417Sdim V2SU.SU = SU; 481296417Sdim V2SU.LaneMask = OverlapMask; 482234353Sdim } 483296417Sdim // If there was no CurrentVRegDefs entry for some lanes yet, create one. 484296417Sdim if (LaneMask != 0) 485296417Sdim CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU)); 486234353Sdim} 487234353Sdim 488234353Sdim/// addVRegUseDeps - Add a register data dependency if the instruction that 489234353Sdim/// defines the virtual register used at OperIdx is mapped to an SUnit. Add a 490234353Sdim/// register antidependency from this SUnit to instructions that occur later in 491234353Sdim/// the same scheduling region if they write the virtual register. 492234353Sdim/// 493234353Sdim/// TODO: Handle ExitSU "uses" properly. 494234353Sdimvoid ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { 495296417Sdim const MachineInstr *MI = SU->getInstr(); 496296417Sdim const MachineOperand &MO = MI->getOperand(OperIdx); 497296417Sdim unsigned Reg = MO.getReg(); 498234353Sdim 499296417Sdim // Remember the use. Data dependencies will be added when we find the def. 500296417Sdim LaneBitmask LaneMask = TrackLaneMasks ? getLaneMaskForMO(MO) : ~0u; 501296417Sdim CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU)); 502261991Sdim 503296417Sdim // Add antidependences to the following defs of the vreg. 504296417Sdim for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg), 505296417Sdim CurrentVRegDefs.end())) { 506296417Sdim // Ignore defs for unrelated lanes. 507296417Sdim LaneBitmask PrevDefLaneMask = V2SU.LaneMask; 508296417Sdim if ((PrevDefLaneMask & LaneMask) == 0) 509296417Sdim continue; 510296417Sdim if (V2SU.SU == SU) 511296417Sdim continue; 512239462Sdim 513296417Sdim V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg)); 514234353Sdim } 515234353Sdim} 516234353Sdim 517239462Sdim/// Return true if MI is an instruction we are unable to reason about 518239462Sdim/// (like a call or something with unmodeled side effects). 519239462Sdimstatic inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) { 520296417Sdim return MI->isCall() || MI->hasUnmodeledSideEffects() || 521296417Sdim (MI->hasOrderedMemoryRef() && 522296417Sdim (!MI->mayLoad() || !MI->isInvariantLoad(AA))); 523239462Sdim} 524239462Sdim 525239462Sdim// This MI might have either incomplete info, or known to be unsafe 526239462Sdim// to deal with (i.e. volatile object). 527239462Sdimstatic inline bool isUnsafeMemoryObject(MachineInstr *MI, 528288943Sdim const MachineFrameInfo *MFI, 529288943Sdim const DataLayout &DL) { 530239462Sdim if (!MI || MI->memoperands_empty()) 531239462Sdim return true; 532239462Sdim // We purposefully do no check for hasOneMemOperand() here 533239462Sdim // in hope to trigger an assert downstream in order to 534239462Sdim // finish implementation. 535239462Sdim if ((*MI->memoperands_begin())->isVolatile() || 536239462Sdim MI->hasUnmodeledSideEffects()) 537239462Sdim return true; 538276479Sdim 539276479Sdim if ((*MI->memoperands_begin())->getPseudoValue()) { 540276479Sdim // Similarly to getUnderlyingObjectForInstr: 541276479Sdim // For now, ignore PseudoSourceValues which may alias LLVM IR values 542276479Sdim // because the code that uses this function has no way to cope with 543276479Sdim // such aliases. 544276479Sdim return true; 545276479Sdim } 546276479Sdim 547239462Sdim const Value *V = (*MI->memoperands_begin())->getValue(); 548239462Sdim if (!V) 549239462Sdim return true; 550239462Sdim 551249423Sdim SmallVector<Value *, 4> Objs; 552288943Sdim getUnderlyingObjects(V, Objs, DL); 553288943Sdim for (Value *V : Objs) { 554249423Sdim // Does this pointer refer to a distinct and identifiable object? 555288943Sdim if (!isIdentifiedObject(V)) 556239462Sdim return true; 557239462Sdim } 558239462Sdim 559239462Sdim return false; 560239462Sdim} 561239462Sdim 562296417Sdim/// This returns true if the two MIs need a chain edge between them. 563239462Sdim/// If these are not even memory operations, we still may need 564239462Sdim/// chain deps between them. The question really is - could 565239462Sdim/// these two MIs be reordered during scheduling from memory dependency 566239462Sdim/// point of view. 567239462Sdimstatic bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI, 568288943Sdim const DataLayout &DL, MachineInstr *MIa, 569239462Sdim MachineInstr *MIb) { 570280031Sdim const MachineFunction *MF = MIa->getParent()->getParent(); 571280031Sdim const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); 572280031Sdim 573239462Sdim // Cover a trivial case - no edge is need to itself. 574239462Sdim if (MIa == MIb) 575239462Sdim return false; 576280031Sdim 577280031Sdim // Let the target decide if memory accesses cannot possibly overlap. 578280031Sdim if ((MIa->mayLoad() || MIa->mayStore()) && 579280031Sdim (MIb->mayLoad() || MIb->mayStore())) 580280031Sdim if (TII->areMemAccessesTriviallyDisjoint(MIa, MIb, AA)) 581280031Sdim return false; 582239462Sdim 583276479Sdim // FIXME: Need to handle multiple memory operands to support all targets. 584276479Sdim if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand()) 585276479Sdim return true; 586276479Sdim 587288943Sdim if (isUnsafeMemoryObject(MIa, MFI, DL) || isUnsafeMemoryObject(MIb, MFI, DL)) 588239462Sdim return true; 589239462Sdim 590239462Sdim // If we are dealing with two "normal" loads, we do not need an edge 591239462Sdim // between them - they could be reordered. 592239462Sdim if (!MIa->mayStore() && !MIb->mayStore()) 593239462Sdim return false; 594239462Sdim 595239462Sdim // To this point analysis is generic. From here on we do need AA. 596239462Sdim if (!AA) 597239462Sdim return true; 598239462Sdim 599239462Sdim MachineMemOperand *MMOa = *MIa->memoperands_begin(); 600239462Sdim MachineMemOperand *MMOb = *MIb->memoperands_begin(); 601239462Sdim 602276479Sdim if (!MMOa->getValue() || !MMOb->getValue()) 603276479Sdim return true; 604239462Sdim 605239462Sdim // The following interface to AA is fashioned after DAGCombiner::isAlias 606239462Sdim // and operates with MachineMemOperand offset with some important 607239462Sdim // assumptions: 608239462Sdim // - LLVM fundamentally assumes flat address spaces. 609239462Sdim // - MachineOperand offset can *only* result from legalization and 610239462Sdim // cannot affect queries other than the trivial case of overlap 611239462Sdim // checking. 612239462Sdim // - These offsets never wrap and never step outside 613239462Sdim // of allocated objects. 614239462Sdim // - There should never be any negative offsets here. 615239462Sdim // 616239462Sdim // FIXME: Modify API to hide this math from "user" 617239462Sdim // FIXME: Even before we go to AA we can reason locally about some 618239462Sdim // memory objects. It can save compile time, and possibly catch some 619239462Sdim // corner cases not currently covered. 620239462Sdim 621239462Sdim assert ((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset"); 622239462Sdim assert ((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset"); 623239462Sdim 624239462Sdim int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset()); 625239462Sdim int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset; 626239462Sdim int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset; 627239462Sdim 628288943Sdim AliasResult AAResult = 629288943Sdim AA->alias(MemoryLocation(MMOa->getValue(), Overlapa, 630288943Sdim UseTBAA ? MMOa->getAAInfo() : AAMDNodes()), 631288943Sdim MemoryLocation(MMOb->getValue(), Overlapb, 632288943Sdim UseTBAA ? MMOb->getAAInfo() : AAMDNodes())); 633239462Sdim 634288943Sdim return (AAResult != NoAlias); 635239462Sdim} 636239462Sdim 637239462Sdim/// This recursive function iterates over chain deps of SUb looking for 638239462Sdim/// "latest" node that needs a chain edge to SUa. 639288943Sdimstatic unsigned iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI, 640288943Sdim const DataLayout &DL, SUnit *SUa, SUnit *SUb, 641288943Sdim SUnit *ExitSU, unsigned *Depth, 642288943Sdim SmallPtrSetImpl<const SUnit *> &Visited) { 643239462Sdim if (!SUa || !SUb || SUb == ExitSU) 644239462Sdim return *Depth; 645239462Sdim 646239462Sdim // Remember visited nodes. 647280031Sdim if (!Visited.insert(SUb).second) 648239462Sdim return *Depth; 649239462Sdim // If there is _some_ dependency already in place, do not 650239462Sdim // descend any further. 651239462Sdim // TODO: Need to make sure that if that dependency got eliminated or ignored 652239462Sdim // for any reason in the future, we would not violate DAG topology. 653239462Sdim // Currently it does not happen, but makes an implicit assumption about 654239462Sdim // future implementation. 655239462Sdim // 656239462Sdim // Independently, if we encounter node that is some sort of global 657239462Sdim // object (like a call) we already have full set of dependencies to it 658239462Sdim // and we can stop descending. 659239462Sdim if (SUa->isSucc(SUb) || 660239462Sdim isGlobalMemoryObject(AA, SUb->getInstr())) 661239462Sdim return *Depth; 662239462Sdim 663239462Sdim // If we do need an edge, or we have exceeded depth budget, 664239462Sdim // add that edge to the predecessors chain of SUb, 665239462Sdim // and stop descending. 666239462Sdim if (*Depth > 200 || 667288943Sdim MIsNeedChainEdge(AA, MFI, DL, SUa->getInstr(), SUb->getInstr())) { 668243830Sdim SUb->addPred(SDep(SUa, SDep::MayAliasMem)); 669239462Sdim return *Depth; 670239462Sdim } 671239462Sdim // Track current depth. 672239462Sdim (*Depth)++; 673280031Sdim // Iterate over memory dependencies only. 674239462Sdim for (SUnit::const_succ_iterator I = SUb->Succs.begin(), E = SUb->Succs.end(); 675239462Sdim I != E; ++I) 676280031Sdim if (I->isNormalMemoryOrBarrier()) 677288943Sdim iterateChainSucc(AA, MFI, DL, SUa, I->getSUnit(), ExitSU, Depth, Visited); 678239462Sdim return *Depth; 679239462Sdim} 680239462Sdim 681239462Sdim/// This function assumes that "downward" from SU there exist 682239462Sdim/// tail/leaf of already constructed DAG. It iterates downward and 683239462Sdim/// checks whether SU can be aliasing any node dominated 684239462Sdim/// by it. 685239462Sdimstatic void adjustChainDeps(AliasAnalysis *AA, const MachineFrameInfo *MFI, 686288943Sdim const DataLayout &DL, SUnit *SU, SUnit *ExitSU, 687288943Sdim std::set<SUnit *> &CheckList, 688239462Sdim unsigned LatencyToLoad) { 689239462Sdim if (!SU) 690239462Sdim return; 691239462Sdim 692239462Sdim SmallPtrSet<const SUnit*, 16> Visited; 693239462Sdim unsigned Depth = 0; 694239462Sdim 695239462Sdim for (std::set<SUnit *>::iterator I = CheckList.begin(), IE = CheckList.end(); 696239462Sdim I != IE; ++I) { 697239462Sdim if (SU == *I) 698239462Sdim continue; 699288943Sdim if (MIsNeedChainEdge(AA, MFI, DL, SU->getInstr(), (*I)->getInstr())) { 700243830Sdim SDep Dep(SU, SDep::MayAliasMem); 701243830Sdim Dep.setLatency(((*I)->getInstr()->mayLoad()) ? LatencyToLoad : 0); 702243830Sdim (*I)->addPred(Dep); 703239462Sdim } 704280031Sdim 705280031Sdim // Iterate recursively over all previously added memory chain 706280031Sdim // successors. Keep track of visited nodes. 707239462Sdim for (SUnit::const_succ_iterator J = (*I)->Succs.begin(), 708239462Sdim JE = (*I)->Succs.end(); J != JE; ++J) 709280031Sdim if (J->isNormalMemoryOrBarrier()) 710288943Sdim iterateChainSucc(AA, MFI, DL, SU, J->getSUnit(), ExitSU, &Depth, 711288943Sdim Visited); 712239462Sdim } 713239462Sdim} 714239462Sdim 715239462Sdim/// Check whether two objects need a chain edge, if so, add it 716239462Sdim/// otherwise remember the rejected SU. 717288943Sdimstatic inline void addChainDependency(AliasAnalysis *AA, 718288943Sdim const MachineFrameInfo *MFI, 719288943Sdim const DataLayout &DL, SUnit *SUa, 720288943Sdim SUnit *SUb, std::set<SUnit *> &RejectList, 721288943Sdim unsigned TrueMemOrderLatency = 0, 722288943Sdim bool isNormalMemory = false) { 723239462Sdim // If this is a false dependency, 724296417Sdim // do not add the edge, but remember the rejected node. 725288943Sdim if (MIsNeedChainEdge(AA, MFI, DL, SUa->getInstr(), SUb->getInstr())) { 726243830Sdim SDep Dep(SUa, isNormalMemory ? SDep::MayAliasMem : SDep::Barrier); 727243830Sdim Dep.setLatency(TrueMemOrderLatency); 728243830Sdim SUb->addPred(Dep); 729243830Sdim } 730239462Sdim else { 731239462Sdim // Duplicate entries should be ignored. 732239462Sdim RejectList.insert(SUb); 733239462Sdim DEBUG(dbgs() << "\tReject chain dep between SU(" 734239462Sdim << SUa->NodeNum << ") and SU(" 735239462Sdim << SUb->NodeNum << ")\n"); 736239462Sdim } 737239462Sdim} 738239462Sdim 739296417Sdim/// Create an SUnit for each real instruction, numbered in top-down topological 740234353Sdim/// order. The instruction order A < B, implies that no edge exists from B to A. 741234353Sdim/// 742234353Sdim/// Map each real instruction to its SUnit. 743234353Sdim/// 744234353Sdim/// After initSUnits, the SUnits vector cannot be resized and the scheduler may 745234353Sdim/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs 746234353Sdim/// instead of pointers. 747234353Sdim/// 748234353Sdim/// MachineScheduler relies on initSUnits numbering the nodes by their order in 749234353Sdim/// the original instruction list. 750234353Sdimvoid ScheduleDAGInstrs::initSUnits() { 751234353Sdim // We'll be allocating one SUnit for each real instruction in the region, 752234353Sdim // which is contained within a basic block. 753261991Sdim SUnits.reserve(NumRegionInstrs); 754193323Sed 755234353Sdim for (MachineBasicBlock::iterator I = RegionBegin; I != RegionEnd; ++I) { 756234353Sdim MachineInstr *MI = I; 757234353Sdim if (MI->isDebugValue()) 758234353Sdim continue; 759234353Sdim 760234353Sdim SUnit *SU = newSUnit(MI); 761234353Sdim MISUnitMap[MI] = SU; 762234353Sdim 763234353Sdim SU->isCall = MI->isCall(); 764234353Sdim SU->isCommutable = MI->isCommutable(); 765234353Sdim 766234353Sdim // Assign the Latency field of SU using target-provided information. 767243830Sdim SU->Latency = SchedModel.computeInstrLatency(SU->getInstr()); 768276479Sdim 769276479Sdim // If this SUnit uses a reserved or unbuffered resource, mark it as such. 770276479Sdim // 771276479Sdim // Reserved resources block an instruction from issuing and stall the 772276479Sdim // entire pipeline. These are identified by BufferSize=0. 773276479Sdim // 774276479Sdim // Unbuffered resources prevent execution of subsequent instructions that 775276479Sdim // require the same resources. This is used for in-order execution pipelines 776276479Sdim // within an out-of-order core. These are identified by BufferSize=1. 777276479Sdim if (SchedModel.hasInstrSchedModel()) { 778276479Sdim const MCSchedClassDesc *SC = getSchedClass(SU); 779276479Sdim for (TargetSchedModel::ProcResIter 780276479Sdim PI = SchedModel.getWriteProcResBegin(SC), 781276479Sdim PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) { 782276479Sdim switch (SchedModel.getProcResource(PI->ProcResourceIdx)->BufferSize) { 783276479Sdim case 0: 784276479Sdim SU->hasReservedResource = true; 785276479Sdim break; 786276479Sdim case 1: 787276479Sdim SU->isUnbuffered = true; 788276479Sdim break; 789276479Sdim default: 790276479Sdim break; 791276479Sdim } 792276479Sdim } 793276479Sdim } 794234353Sdim } 795234353Sdim} 796234353Sdim 797296417Sdimvoid ScheduleDAGInstrs::collectVRegUses(SUnit *SU) { 798296417Sdim const MachineInstr *MI = SU->getInstr(); 799296417Sdim for (const MachineOperand &MO : MI->operands()) { 800296417Sdim if (!MO.isReg()) 801296417Sdim continue; 802296417Sdim if (!MO.readsReg()) 803296417Sdim continue; 804296417Sdim if (TrackLaneMasks && !MO.isUse()) 805296417Sdim continue; 806296417Sdim 807296417Sdim unsigned Reg = MO.getReg(); 808296417Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg)) 809296417Sdim continue; 810296417Sdim 811296417Sdim // Record this local VReg use. 812296417Sdim VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg); 813296417Sdim for (; UI != VRegUses.end(); ++UI) { 814296417Sdim if (UI->SU == SU) 815296417Sdim break; 816296417Sdim } 817296417Sdim if (UI == VRegUses.end()) 818296417Sdim VRegUses.insert(VReg2SUnit(Reg, 0, SU)); 819296417Sdim } 820296417Sdim} 821296417Sdim 822276479Sdim/// If RegPressure is non-null, compute register pressure as a side effect. The 823239462Sdim/// DAG builder is an efficient place to do it because it already visits 824239462Sdim/// operands. 825239462Sdimvoid ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA, 826261991Sdim RegPressureTracker *RPTracker, 827296417Sdim PressureDiffs *PDiffs, 828296417Sdim bool TrackLaneMasks) { 829288943Sdim const TargetSubtargetInfo &ST = MF.getSubtarget(); 830261991Sdim bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI 831261991Sdim : ST.useAA(); 832276479Sdim AliasAnalysis *AAForDep = UseAA ? AA : nullptr; 833261991Sdim 834296417Sdim this->TrackLaneMasks = TrackLaneMasks; 835261991Sdim MISUnitMap.clear(); 836261991Sdim ScheduleDAG::clearDAG(); 837261991Sdim 838234353Sdim // Create an SUnit for each real instruction. 839234353Sdim initSUnits(); 840234353Sdim 841261991Sdim if (PDiffs) 842261991Sdim PDiffs->init(SUnits.size()); 843261991Sdim 844193323Sed // We build scheduling units by walking a block's instruction list from bottom 845193323Sed // to top. 846193323Sed 847296417Sdim // Remember where a generic side-effecting instruction is as we proceed. 848276479Sdim SUnit *BarrierChain = nullptr, *AliasChain = nullptr; 849193323Sed 850199481Srdivacky // Memory references to specific known memory locations are tracked 851199481Srdivacky // so that they can be given more precise dependencies. We track 852199481Srdivacky // separately the known memory locations that may alias and those 853199481Srdivacky // that are known not to alias 854276479Sdim MapVector<ValueType, std::vector<SUnit *> > AliasMemDefs, NonAliasMemDefs; 855276479Sdim MapVector<ValueType, std::vector<SUnit *> > AliasMemUses, NonAliasMemUses; 856239462Sdim std::set<SUnit*> RejectMemNodes; 857193323Sed 858205218Srdivacky // Remove any stale debug info; sometimes BuildSchedGraph is called again 859205218Srdivacky // without emitting the info from the previous call. 860223017Sdim DbgValues.clear(); 861276479Sdim FirstDbgValue = nullptr; 862205218Srdivacky 863234353Sdim assert(Defs.empty() && Uses.empty() && 864234353Sdim "Only BuildGraph should update Defs/Uses"); 865249423Sdim Defs.setUniverse(TRI->getNumRegs()); 866249423Sdim Uses.setUniverse(TRI->getNumRegs()); 867234353Sdim 868296417Sdim assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs"); 869296417Sdim assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses"); 870296417Sdim unsigned NumVirtRegs = MRI.getNumVirtRegs(); 871296417Sdim CurrentVRegDefs.setUniverse(NumVirtRegs); 872296417Sdim CurrentVRegUses.setUniverse(NumVirtRegs); 873296417Sdim 874261991Sdim VRegUses.clear(); 875296417Sdim VRegUses.setUniverse(NumVirtRegs); 876234353Sdim 877218893Sdim // Model data dependencies between instructions being scheduled and the 878218893Sdim // ExitSU. 879234353Sdim addSchedBarrierDeps(); 880218893Sdim 881193323Sed // Walk the list of instructions, from bottom moving up. 882276479Sdim MachineInstr *DbgMI = nullptr; 883234353Sdim for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin; 884193323Sed MII != MIE; --MII) { 885276479Sdim MachineInstr *MI = std::prev(MII); 886249423Sdim if (MI && DbgMI) { 887249423Sdim DbgValues.push_back(std::make_pair(DbgMI, MI)); 888276479Sdim DbgMI = nullptr; 889223017Sdim } 890223017Sdim 891205218Srdivacky if (MI->isDebugValue()) { 892249423Sdim DbgMI = MI; 893205218Srdivacky continue; 894205218Srdivacky } 895261991Sdim SUnit *SU = MISUnitMap[MI]; 896261991Sdim assert(SU && "No SUnit mapped to this MI"); 897261991Sdim 898239462Sdim if (RPTracker) { 899296417Sdim collectVRegUses(SU); 900296417Sdim 901296417Sdim RegisterOperands RegOpers; 902296417Sdim RegOpers.collect(*MI, *TRI, MRI); 903296417Sdim if (PDiffs != nullptr) 904296417Sdim PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI); 905296417Sdim 906296417Sdim RPTracker->recedeSkipDebugValues(); 907296417Sdim assert(&*RPTracker->getPos() == MI && "RPTracker in sync"); 908296417Sdim RPTracker->recede(RegOpers); 909239462Sdim } 910223017Sdim 911276479Sdim assert( 912276479Sdim (CanHandleTerminators || (!MI->isTerminator() && !MI->isPosition())) && 913276479Sdim "Cannot schedule terminators or labels!"); 914193323Sed 915193323Sed // Add register-based dependencies (data, anti, and output). 916249423Sdim bool HasVRegDef = false; 917193323Sed for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { 918193323Sed const MachineOperand &MO = MI->getOperand(j); 919193323Sed if (!MO.isReg()) continue; 920193323Sed unsigned Reg = MO.getReg(); 921193323Sed if (Reg == 0) continue; 922193323Sed 923234353Sdim if (TRI->isPhysicalRegister(Reg)) 924234353Sdim addPhysRegDeps(SU, j); 925234353Sdim else { 926249423Sdim if (MO.isDef()) { 927249423Sdim HasVRegDef = true; 928234353Sdim addVRegDefDeps(SU, j); 929249423Sdim } 930234353Sdim else if (MO.readsReg()) // ignore undef operands 931234353Sdim addVRegUseDeps(SU, j); 932193323Sed } 933193323Sed } 934249423Sdim // If we haven't seen any uses in this scheduling region, create a 935249423Sdim // dependence edge to ExitSU to model the live-out latency. This is required 936249423Sdim // for vreg defs with no in-region use, and prefetches with no vreg def. 937249423Sdim // 938249423Sdim // FIXME: NumDataSuccs would be more precise than NumSuccs here. This 939249423Sdim // check currently relies on being called before adding chain deps. 940249423Sdim if (SU->NumSuccs == 0 && SU->Latency > 1 941249423Sdim && (HasVRegDef || MI->mayLoad())) { 942249423Sdim SDep Dep(SU, SDep::Artificial); 943249423Sdim Dep.setLatency(SU->Latency - 1); 944249423Sdim ExitSU.addPred(Dep); 945249423Sdim } 946193323Sed 947193323Sed // Add chain dependencies. 948198892Srdivacky // Chain dependencies used to enforce memory order should have 949198892Srdivacky // latency of 0 (except for true dependency of Store followed by 950198892Srdivacky // aliased Load... we estimate that with a single cycle of latency 951198892Srdivacky // assuming the hardware will bypass) 952193323Sed // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable 953193323Sed // after stack slots are lowered to actual addresses. 954193323Sed // TODO: Use an AliasAnalysis and do real alias-analysis queries, and 955193323Sed // produce more precise dependence information. 956239462Sdim unsigned TrueMemOrderLatency = MI->mayStore() ? 1 : 0; 957239462Sdim if (isGlobalMemoryObject(AA, MI)) { 958199481Srdivacky // Be conservative with these and add dependencies on all memory 959199481Srdivacky // references, even those that are known to not alias. 960276479Sdim for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 961199481Srdivacky NonAliasMemDefs.begin(), E = NonAliasMemDefs.end(); I != E; ++I) { 962276479Sdim for (unsigned i = 0, e = I->second.size(); i != e; ++i) { 963276479Sdim I->second[i]->addPred(SDep(SU, SDep::Barrier)); 964276479Sdim } 965199481Srdivacky } 966276479Sdim for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 967199481Srdivacky NonAliasMemUses.begin(), E = NonAliasMemUses.end(); I != E; ++I) { 968243830Sdim for (unsigned i = 0, e = I->second.size(); i != e; ++i) { 969243830Sdim SDep Dep(SU, SDep::Barrier); 970243830Sdim Dep.setLatency(TrueMemOrderLatency); 971243830Sdim I->second[i]->addPred(Dep); 972243830Sdim } 973199481Srdivacky } 974199481Srdivacky // Add SU to the barrier chain. 975199481Srdivacky if (BarrierChain) 976243830Sdim BarrierChain->addPred(SDep(SU, SDep::Barrier)); 977199481Srdivacky BarrierChain = SU; 978239462Sdim // This is a barrier event that acts as a pivotal node in the DAG, 979239462Sdim // so it is safe to clear list of exposed nodes. 980296417Sdim adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, 981239462Sdim TrueMemOrderLatency); 982239462Sdim RejectMemNodes.clear(); 983239462Sdim NonAliasMemDefs.clear(); 984239462Sdim NonAliasMemUses.clear(); 985199481Srdivacky 986199481Srdivacky // fall-through 987199481Srdivacky new_alias_chain: 988280031Sdim // Chain all possibly aliasing memory references through SU. 989239462Sdim if (AliasChain) { 990239462Sdim unsigned ChainLatency = 0; 991239462Sdim if (AliasChain->getInstr()->mayLoad()) 992239462Sdim ChainLatency = TrueMemOrderLatency; 993296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, 994288943Sdim RejectMemNodes, ChainLatency); 995239462Sdim } 996199481Srdivacky AliasChain = SU; 997193323Sed for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 998296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 999288943Sdim PendingLoads[k], RejectMemNodes, 1000239462Sdim TrueMemOrderLatency); 1001276479Sdim for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1002276479Sdim AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) { 1003276479Sdim for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1004296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1005288943Sdim I->second[i], RejectMemNodes); 1006276479Sdim } 1007276479Sdim for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1008199481Srdivacky AliasMemUses.begin(), E = AliasMemUses.end(); I != E; ++I) { 1009193323Sed for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1010296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1011288943Sdim I->second[i], RejectMemNodes, TrueMemOrderLatency); 1012193323Sed } 1013296417Sdim // This call must come after calls to addChainDependency() since it 1014296417Sdim // consumes the 'RejectMemNodes' list that addChainDependency() possibly 1015296417Sdim // adds to. 1016296417Sdim adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, 1017239462Sdim TrueMemOrderLatency); 1018199481Srdivacky PendingLoads.clear(); 1019199481Srdivacky AliasMemDefs.clear(); 1020199481Srdivacky AliasMemUses.clear(); 1021234353Sdim } else if (MI->mayStore()) { 1022280031Sdim // Add dependence on barrier chain, if needed. 1023280031Sdim // There is no point to check aliasing on barrier event. Even if 1024280031Sdim // SU and barrier _could_ be reordered, they should not. In addition, 1025280031Sdim // we have lost all RejectMemNodes below barrier. 1026280031Sdim if (BarrierChain) 1027280031Sdim BarrierChain->addPred(SDep(SU, SDep::Barrier)); 1028280031Sdim 1029261991Sdim UnderlyingObjectsVector Objs; 1030296417Sdim getUnderlyingObjectsForInstr(MI, MFI, Objs, MF.getDataLayout()); 1031249423Sdim 1032249423Sdim if (Objs.empty()) { 1033249423Sdim // Treat all other stores conservatively. 1034249423Sdim goto new_alias_chain; 1035249423Sdim } 1036249423Sdim 1037249423Sdim bool MayAlias = false; 1038261991Sdim for (UnderlyingObjectsVector::iterator K = Objs.begin(), KE = Objs.end(); 1039261991Sdim K != KE; ++K) { 1040276479Sdim ValueType V = K->getPointer(); 1041261991Sdim bool ThisMayAlias = K->getInt(); 1042249423Sdim if (ThisMayAlias) 1043249423Sdim MayAlias = true; 1044249423Sdim 1045193323Sed // A store to a specific PseudoSourceValue. Add precise dependencies. 1046199481Srdivacky // Record the def in MemDefs, first adding a dep if there is 1047199481Srdivacky // an existing def. 1048276479Sdim MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1049249423Sdim ((ThisMayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 1050276479Sdim MapVector<ValueType, std::vector<SUnit *> >::iterator IE = 1051249423Sdim ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 1052199481Srdivacky if (I != IE) { 1053276479Sdim for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1054296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1055288943Sdim I->second[i], RejectMemNodes, 0, true); 1056276479Sdim 1057276479Sdim // If we're not using AA, then we only need one store per object. 1058276479Sdim if (!AAForDep) 1059276479Sdim I->second.clear(); 1060276479Sdim I->second.push_back(SU); 1061193323Sed } else { 1062276479Sdim if (ThisMayAlias) { 1063276479Sdim if (!AAForDep) 1064276479Sdim AliasMemDefs[V].clear(); 1065276479Sdim AliasMemDefs[V].push_back(SU); 1066276479Sdim } else { 1067276479Sdim if (!AAForDep) 1068276479Sdim NonAliasMemDefs[V].clear(); 1069276479Sdim NonAliasMemDefs[V].push_back(SU); 1070276479Sdim } 1071193323Sed } 1072193323Sed // Handle the uses in MemUses, if there are any. 1073276479Sdim MapVector<ValueType, std::vector<SUnit *> >::iterator J = 1074249423Sdim ((ThisMayAlias) ? AliasMemUses.find(V) : NonAliasMemUses.find(V)); 1075276479Sdim MapVector<ValueType, std::vector<SUnit *> >::iterator JE = 1076249423Sdim ((ThisMayAlias) ? AliasMemUses.end() : NonAliasMemUses.end()); 1077199481Srdivacky if (J != JE) { 1078193323Sed for (unsigned i = 0, e = J->second.size(); i != e; ++i) 1079296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1080288943Sdim J->second[i], RejectMemNodes, 1081239462Sdim TrueMemOrderLatency, true); 1082193323Sed J->second.clear(); 1083193323Sed } 1084198892Srdivacky } 1085249423Sdim if (MayAlias) { 1086249423Sdim // Add dependencies from all the PendingLoads, i.e. loads 1087249423Sdim // with no underlying object. 1088249423Sdim for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) 1089296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1090288943Sdim PendingLoads[k], RejectMemNodes, 1091249423Sdim TrueMemOrderLatency); 1092249423Sdim // Add dependence on alias chain, if needed. 1093249423Sdim if (AliasChain) 1094296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, 1095288943Sdim RejectMemNodes); 1096249423Sdim } 1097296417Sdim // This call must come after calls to addChainDependency() since it 1098296417Sdim // consumes the 'RejectMemNodes' list that addChainDependency() possibly 1099296417Sdim // adds to. 1100296417Sdim adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, RejectMemNodes, 1101288943Sdim TrueMemOrderLatency); 1102234353Sdim } else if (MI->mayLoad()) { 1103198892Srdivacky bool MayAlias = true; 1104198090Srdivacky if (MI->isInvariantLoad(AA)) { 1105193323Sed // Invariant load, no chain dependencies needed! 1106198953Srdivacky } else { 1107261991Sdim UnderlyingObjectsVector Objs; 1108296417Sdim getUnderlyingObjectsForInstr(MI, MFI, Objs, MF.getDataLayout()); 1109249423Sdim 1110249423Sdim if (Objs.empty()) { 1111199481Srdivacky // A load with no underlying object. Depend on all 1112199481Srdivacky // potentially aliasing stores. 1113276479Sdim for (MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1114199481Srdivacky AliasMemDefs.begin(), E = AliasMemDefs.end(); I != E; ++I) 1115276479Sdim for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1116296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1117288943Sdim I->second[i], RejectMemNodes); 1118223017Sdim 1119199481Srdivacky PendingLoads.push_back(SU); 1120199481Srdivacky MayAlias = true; 1121249423Sdim } else { 1122249423Sdim MayAlias = false; 1123198892Srdivacky } 1124249423Sdim 1125261991Sdim for (UnderlyingObjectsVector::iterator 1126249423Sdim J = Objs.begin(), JE = Objs.end(); J != JE; ++J) { 1127276479Sdim ValueType V = J->getPointer(); 1128261991Sdim bool ThisMayAlias = J->getInt(); 1129249423Sdim 1130249423Sdim if (ThisMayAlias) 1131249423Sdim MayAlias = true; 1132249423Sdim 1133249423Sdim // A load from a specific PseudoSourceValue. Add precise dependencies. 1134276479Sdim MapVector<ValueType, std::vector<SUnit *> >::iterator I = 1135249423Sdim ((ThisMayAlias) ? AliasMemDefs.find(V) : NonAliasMemDefs.find(V)); 1136276479Sdim MapVector<ValueType, std::vector<SUnit *> >::iterator IE = 1137249423Sdim ((ThisMayAlias) ? AliasMemDefs.end() : NonAliasMemDefs.end()); 1138249423Sdim if (I != IE) 1139276479Sdim for (unsigned i = 0, e = I->second.size(); i != e; ++i) 1140296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, 1141288943Sdim I->second[i], RejectMemNodes, 0, true); 1142249423Sdim if (ThisMayAlias) 1143249423Sdim AliasMemUses[V].push_back(SU); 1144249423Sdim else 1145249423Sdim NonAliasMemUses[V].push_back(SU); 1146249423Sdim } 1147199481Srdivacky // Add dependencies on alias and barrier chains, if needed. 1148199481Srdivacky if (MayAlias && AliasChain) 1149296417Sdim addChainDependency(AAForDep, MFI, MF.getDataLayout(), SU, AliasChain, 1150288943Sdim RejectMemNodes); 1151296417Sdim if (MayAlias) 1152296417Sdim // This call must come after calls to addChainDependency() since it 1153296417Sdim // consumes the 'RejectMemNodes' list that addChainDependency() 1154296417Sdim // possibly adds to. 1155296417Sdim adjustChainDeps(AA, MFI, MF.getDataLayout(), SU, &ExitSU, 1156296417Sdim RejectMemNodes, /*Latency=*/0); 1157199481Srdivacky if (BarrierChain) 1158243830Sdim BarrierChain->addPred(SDep(SU, SDep::Barrier)); 1159223017Sdim } 1160193323Sed } 1161193323Sed } 1162249423Sdim if (DbgMI) 1163249423Sdim FirstDbgValue = DbgMI; 1164193323Sed 1165234353Sdim Defs.clear(); 1166234353Sdim Uses.clear(); 1167296417Sdim CurrentVRegDefs.clear(); 1168296417Sdim CurrentVRegUses.clear(); 1169193323Sed PendingLoads.clear(); 1170193323Sed} 1171193323Sed 1172276479Sdim/// \brief Initialize register live-range state for updating kills. 1173276479Sdimvoid ScheduleDAGInstrs::startBlockForKills(MachineBasicBlock *BB) { 1174276479Sdim // Start with no live registers. 1175276479Sdim LiveRegs.reset(); 1176276479Sdim 1177276479Sdim // Examine the live-in regs of all successors. 1178276479Sdim for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 1179276479Sdim SE = BB->succ_end(); SI != SE; ++SI) { 1180296417Sdim for (const auto &LI : (*SI)->liveins()) { 1181276479Sdim // Repeat, for reg and all subregs. 1182296417Sdim for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true); 1183276479Sdim SubRegs.isValid(); ++SubRegs) 1184276479Sdim LiveRegs.set(*SubRegs); 1185276479Sdim } 1186276479Sdim } 1187276479Sdim} 1188276479Sdim 1189288943Sdim/// \brief If we change a kill flag on the bundle instruction implicit register 1190288943Sdim/// operands, then we also need to propagate that to any instructions inside 1191288943Sdim/// the bundle which had the same kill state. 1192288943Sdimstatic void toggleBundleKillFlag(MachineInstr *MI, unsigned Reg, 1193288943Sdim bool NewKillState) { 1194288943Sdim if (MI->getOpcode() != TargetOpcode::BUNDLE) 1195288943Sdim return; 1196288943Sdim 1197288943Sdim // Walk backwards from the last instruction in the bundle to the first. 1198288943Sdim // Once we set a kill flag on an instruction, we bail out, as otherwise we 1199288943Sdim // might set it on too many operands. We will clear as many flags as we 1200288943Sdim // can though. 1201296417Sdim MachineBasicBlock::instr_iterator Begin = MI->getIterator(); 1202288943Sdim MachineBasicBlock::instr_iterator End = getBundleEnd(MI); 1203288943Sdim while (Begin != End) { 1204288943Sdim for (MachineOperand &MO : (--End)->operands()) { 1205288943Sdim if (!MO.isReg() || MO.isDef() || Reg != MO.getReg()) 1206288943Sdim continue; 1207288943Sdim 1208288943Sdim // DEBUG_VALUE nodes do not contribute to code generation and should 1209288943Sdim // always be ignored. Failure to do so may result in trying to modify 1210288943Sdim // KILL flags on DEBUG_VALUE nodes, which is distressing. 1211288943Sdim if (MO.isDebug()) 1212288943Sdim continue; 1213288943Sdim 1214288943Sdim // If the register has the internal flag then it could be killing an 1215288943Sdim // internal def of the register. In this case, just skip. We only want 1216288943Sdim // to toggle the flag on operands visible outside the bundle. 1217288943Sdim if (MO.isInternalRead()) 1218288943Sdim continue; 1219288943Sdim 1220288943Sdim if (MO.isKill() == NewKillState) 1221288943Sdim continue; 1222288943Sdim MO.setIsKill(NewKillState); 1223288943Sdim if (NewKillState) 1224288943Sdim return; 1225288943Sdim } 1226288943Sdim } 1227288943Sdim} 1228288943Sdim 1229276479Sdimbool ScheduleDAGInstrs::toggleKillFlag(MachineInstr *MI, MachineOperand &MO) { 1230276479Sdim // Setting kill flag... 1231276479Sdim if (!MO.isKill()) { 1232276479Sdim MO.setIsKill(true); 1233288943Sdim toggleBundleKillFlag(MI, MO.getReg(), true); 1234276479Sdim return false; 1235276479Sdim } 1236276479Sdim 1237276479Sdim // If MO itself is live, clear the kill flag... 1238276479Sdim if (LiveRegs.test(MO.getReg())) { 1239276479Sdim MO.setIsKill(false); 1240288943Sdim toggleBundleKillFlag(MI, MO.getReg(), false); 1241276479Sdim return false; 1242276479Sdim } 1243276479Sdim 1244276479Sdim // If any subreg of MO is live, then create an imp-def for that 1245276479Sdim // subreg and keep MO marked as killed. 1246276479Sdim MO.setIsKill(false); 1247288943Sdim toggleBundleKillFlag(MI, MO.getReg(), false); 1248276479Sdim bool AllDead = true; 1249276479Sdim const unsigned SuperReg = MO.getReg(); 1250276479Sdim MachineInstrBuilder MIB(MF, MI); 1251276479Sdim for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) { 1252276479Sdim if (LiveRegs.test(*SubRegs)) { 1253276479Sdim MIB.addReg(*SubRegs, RegState::ImplicitDefine); 1254276479Sdim AllDead = false; 1255276479Sdim } 1256276479Sdim } 1257276479Sdim 1258288943Sdim if(AllDead) { 1259276479Sdim MO.setIsKill(true); 1260288943Sdim toggleBundleKillFlag(MI, MO.getReg(), true); 1261288943Sdim } 1262276479Sdim return false; 1263276479Sdim} 1264276479Sdim 1265276479Sdim// FIXME: Reuse the LivePhysRegs utility for this. 1266276479Sdimvoid ScheduleDAGInstrs::fixupKills(MachineBasicBlock *MBB) { 1267276479Sdim DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); 1268276479Sdim 1269276479Sdim LiveRegs.resize(TRI->getNumRegs()); 1270276479Sdim BitVector killedRegs(TRI->getNumRegs()); 1271276479Sdim 1272276479Sdim startBlockForKills(MBB); 1273276479Sdim 1274276479Sdim // Examine block from end to start... 1275276479Sdim unsigned Count = MBB->size(); 1276276479Sdim for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); 1277276479Sdim I != E; --Count) { 1278276479Sdim MachineInstr *MI = --I; 1279276479Sdim if (MI->isDebugValue()) 1280276479Sdim continue; 1281276479Sdim 1282276479Sdim // Update liveness. Registers that are defed but not used in this 1283276479Sdim // instruction are now dead. Mark register and all subregs as they 1284276479Sdim // are completely defined. 1285276479Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1286276479Sdim MachineOperand &MO = MI->getOperand(i); 1287276479Sdim if (MO.isRegMask()) 1288276479Sdim LiveRegs.clearBitsNotInMask(MO.getRegMask()); 1289276479Sdim if (!MO.isReg()) continue; 1290276479Sdim unsigned Reg = MO.getReg(); 1291276479Sdim if (Reg == 0) continue; 1292276479Sdim if (!MO.isDef()) continue; 1293276479Sdim // Ignore two-addr defs. 1294276479Sdim if (MI->isRegTiedToUseOperand(i)) continue; 1295276479Sdim 1296276479Sdim // Repeat for reg and all subregs. 1297276479Sdim for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 1298276479Sdim SubRegs.isValid(); ++SubRegs) 1299276479Sdim LiveRegs.reset(*SubRegs); 1300276479Sdim } 1301276479Sdim 1302276479Sdim // Examine all used registers and set/clear kill flag. When a 1303276479Sdim // register is used multiple times we only set the kill flag on 1304276479Sdim // the first use. Don't set kill flags on undef operands. 1305276479Sdim killedRegs.reset(); 1306276479Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1307276479Sdim MachineOperand &MO = MI->getOperand(i); 1308276479Sdim if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 1309276479Sdim unsigned Reg = MO.getReg(); 1310276479Sdim if ((Reg == 0) || MRI.isReserved(Reg)) continue; 1311276479Sdim 1312276479Sdim bool kill = false; 1313276479Sdim if (!killedRegs.test(Reg)) { 1314276479Sdim kill = true; 1315276479Sdim // A register is not killed if any subregs are live... 1316276479Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 1317276479Sdim if (LiveRegs.test(*SubRegs)) { 1318276479Sdim kill = false; 1319276479Sdim break; 1320276479Sdim } 1321276479Sdim } 1322276479Sdim 1323276479Sdim // If subreg is not live, then register is killed if it became 1324276479Sdim // live in this instruction 1325276479Sdim if (kill) 1326276479Sdim kill = !LiveRegs.test(Reg); 1327276479Sdim } 1328276479Sdim 1329276479Sdim if (MO.isKill() != kill) { 1330276479Sdim DEBUG(dbgs() << "Fixing " << MO << " in "); 1331276479Sdim // Warning: toggleKillFlag may invalidate MO. 1332276479Sdim toggleKillFlag(MI, MO); 1333276479Sdim DEBUG(MI->dump()); 1334288943Sdim DEBUG(if (MI->getOpcode() == TargetOpcode::BUNDLE) { 1335296417Sdim MachineBasicBlock::instr_iterator Begin = MI->getIterator(); 1336288943Sdim MachineBasicBlock::instr_iterator End = getBundleEnd(MI); 1337288943Sdim while (++Begin != End) 1338288943Sdim DEBUG(Begin->dump()); 1339288943Sdim }); 1340276479Sdim } 1341276479Sdim 1342276479Sdim killedRegs.set(Reg); 1343276479Sdim } 1344276479Sdim 1345276479Sdim // Mark any used register (that is not using undef) and subregs as 1346276479Sdim // now live... 1347276479Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1348276479Sdim MachineOperand &MO = MI->getOperand(i); 1349276479Sdim if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 1350276479Sdim unsigned Reg = MO.getReg(); 1351276479Sdim if ((Reg == 0) || MRI.isReserved(Reg)) continue; 1352276479Sdim 1353276479Sdim for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 1354276479Sdim SubRegs.isValid(); ++SubRegs) 1355276479Sdim LiveRegs.set(*SubRegs); 1356276479Sdim } 1357276479Sdim } 1358276479Sdim} 1359276479Sdim 1360193323Sedvoid ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { 1361243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1362193323Sed SU->getInstr()->dump(); 1363243830Sdim#endif 1364193323Sed} 1365193323Sed 1366193323Sedstd::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { 1367193323Sed std::string s; 1368193323Sed raw_string_ostream oss(s); 1369193323Sed if (SU == &EntrySU) 1370193323Sed oss << "<entry>"; 1371193323Sed else if (SU == &ExitSU) 1372193323Sed oss << "<exit>"; 1373193323Sed else 1374288943Sdim SU->getInstr()->print(oss, /*SkipOpers=*/true); 1375193323Sed return oss.str(); 1376193323Sed} 1377193323Sed 1378234353Sdim/// Return the basic block label. It is not necessarilly unique because a block 1379234353Sdim/// contains multiple scheduling regions. But it is fine for visualization. 1380234353Sdimstd::string ScheduleDAGInstrs::getDAGName() const { 1381234353Sdim return "dag." + BB->getFullName(); 1382193323Sed} 1383243830Sdim 1384249423Sdim//===----------------------------------------------------------------------===// 1385249423Sdim// SchedDFSResult Implementation 1386249423Sdim//===----------------------------------------------------------------------===// 1387249423Sdim 1388249423Sdimnamespace llvm { 1389249423Sdim/// \brief Internal state used to compute SchedDFSResult. 1390249423Sdimclass SchedDFSImpl { 1391249423Sdim SchedDFSResult &R; 1392249423Sdim 1393249423Sdim /// Join DAG nodes into equivalence classes by their subtree. 1394249423Sdim IntEqClasses SubtreeClasses; 1395249423Sdim /// List PredSU, SuccSU pairs that represent data edges between subtrees. 1396249423Sdim std::vector<std::pair<const SUnit*, const SUnit*> > ConnectionPairs; 1397249423Sdim 1398249423Sdim struct RootData { 1399249423Sdim unsigned NodeID; 1400249423Sdim unsigned ParentNodeID; // Parent node (member of the parent subtree). 1401249423Sdim unsigned SubInstrCount; // Instr count in this tree only, not children. 1402249423Sdim 1403249423Sdim RootData(unsigned id): NodeID(id), 1404249423Sdim ParentNodeID(SchedDFSResult::InvalidSubtreeID), 1405249423Sdim SubInstrCount(0) {} 1406249423Sdim 1407249423Sdim unsigned getSparseSetIndex() const { return NodeID; } 1408249423Sdim }; 1409249423Sdim 1410249423Sdim SparseSet<RootData> RootSet; 1411249423Sdim 1412249423Sdimpublic: 1413249423Sdim SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) { 1414249423Sdim RootSet.setUniverse(R.DFSNodeData.size()); 1415249423Sdim } 1416249423Sdim 1417249423Sdim /// Return true if this node been visited by the DFS traversal. 1418249423Sdim /// 1419249423Sdim /// During visitPostorderNode the Node's SubtreeID is assigned to the Node 1420249423Sdim /// ID. Later, SubtreeID is updated but remains valid. 1421249423Sdim bool isVisited(const SUnit *SU) const { 1422249423Sdim return R.DFSNodeData[SU->NodeNum].SubtreeID 1423249423Sdim != SchedDFSResult::InvalidSubtreeID; 1424249423Sdim } 1425249423Sdim 1426249423Sdim /// Initialize this node's instruction count. We don't need to flag the node 1427249423Sdim /// visited until visitPostorder because the DAG cannot have cycles. 1428249423Sdim void visitPreorder(const SUnit *SU) { 1429249423Sdim R.DFSNodeData[SU->NodeNum].InstrCount = 1430249423Sdim SU->getInstr()->isTransient() ? 0 : 1; 1431249423Sdim } 1432249423Sdim 1433249423Sdim /// Called once for each node after all predecessors are visited. Revisit this 1434249423Sdim /// node's predecessors and potentially join them now that we know the ILP of 1435249423Sdim /// the other predecessors. 1436249423Sdim void visitPostorderNode(const SUnit *SU) { 1437249423Sdim // Mark this node as the root of a subtree. It may be joined with its 1438249423Sdim // successors later. 1439249423Sdim R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum; 1440249423Sdim RootData RData(SU->NodeNum); 1441249423Sdim RData.SubInstrCount = SU->getInstr()->isTransient() ? 0 : 1; 1442249423Sdim 1443249423Sdim // If any predecessors are still in their own subtree, they either cannot be 1444249423Sdim // joined or are large enough to remain separate. If this parent node's 1445249423Sdim // total instruction count is not greater than a child subtree by at least 1446249423Sdim // the subtree limit, then try to join it now since splitting subtrees is 1447249423Sdim // only useful if multiple high-pressure paths are possible. 1448249423Sdim unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount; 1449249423Sdim for (SUnit::const_pred_iterator 1450249423Sdim PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) { 1451249423Sdim if (PI->getKind() != SDep::Data) 1452249423Sdim continue; 1453249423Sdim unsigned PredNum = PI->getSUnit()->NodeNum; 1454249423Sdim if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit) 1455249423Sdim joinPredSubtree(*PI, SU, /*CheckLimit=*/false); 1456249423Sdim 1457249423Sdim // Either link or merge the TreeData entry from the child to the parent. 1458249423Sdim if (R.DFSNodeData[PredNum].SubtreeID == PredNum) { 1459249423Sdim // If the predecessor's parent is invalid, this is a tree edge and the 1460249423Sdim // current node is the parent. 1461249423Sdim if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID) 1462249423Sdim RootSet[PredNum].ParentNodeID = SU->NodeNum; 1463249423Sdim } 1464249423Sdim else if (RootSet.count(PredNum)) { 1465249423Sdim // The predecessor is not a root, but is still in the root set. This 1466249423Sdim // must be the new parent that it was just joined to. Note that 1467249423Sdim // RootSet[PredNum].ParentNodeID may either be invalid or may still be 1468249423Sdim // set to the original parent. 1469249423Sdim RData.SubInstrCount += RootSet[PredNum].SubInstrCount; 1470249423Sdim RootSet.erase(PredNum); 1471249423Sdim } 1472249423Sdim } 1473249423Sdim RootSet[SU->NodeNum] = RData; 1474249423Sdim } 1475249423Sdim 1476249423Sdim /// Called once for each tree edge after calling visitPostOrderNode on the 1477249423Sdim /// predecessor. Increment the parent node's instruction count and 1478249423Sdim /// preemptively join this subtree to its parent's if it is small enough. 1479249423Sdim void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) { 1480249423Sdim R.DFSNodeData[Succ->NodeNum].InstrCount 1481249423Sdim += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount; 1482249423Sdim joinPredSubtree(PredDep, Succ); 1483249423Sdim } 1484249423Sdim 1485249423Sdim /// Add a connection for cross edges. 1486249423Sdim void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) { 1487249423Sdim ConnectionPairs.push_back(std::make_pair(PredDep.getSUnit(), Succ)); 1488249423Sdim } 1489249423Sdim 1490249423Sdim /// Set each node's subtree ID to the representative ID and record connections 1491249423Sdim /// between trees. 1492249423Sdim void finalize() { 1493249423Sdim SubtreeClasses.compress(); 1494249423Sdim R.DFSTreeData.resize(SubtreeClasses.getNumClasses()); 1495249423Sdim assert(SubtreeClasses.getNumClasses() == RootSet.size() 1496249423Sdim && "number of roots should match trees"); 1497249423Sdim for (SparseSet<RootData>::const_iterator 1498249423Sdim RI = RootSet.begin(), RE = RootSet.end(); RI != RE; ++RI) { 1499249423Sdim unsigned TreeID = SubtreeClasses[RI->NodeID]; 1500249423Sdim if (RI->ParentNodeID != SchedDFSResult::InvalidSubtreeID) 1501249423Sdim R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[RI->ParentNodeID]; 1502249423Sdim R.DFSTreeData[TreeID].SubInstrCount = RI->SubInstrCount; 1503249423Sdim // Note that SubInstrCount may be greater than InstrCount if we joined 1504249423Sdim // subtrees across a cross edge. InstrCount will be attributed to the 1505249423Sdim // original parent, while SubInstrCount will be attributed to the joined 1506249423Sdim // parent. 1507249423Sdim } 1508249423Sdim R.SubtreeConnections.resize(SubtreeClasses.getNumClasses()); 1509249423Sdim R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses()); 1510249423Sdim DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n"); 1511249423Sdim for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) { 1512249423Sdim R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx]; 1513249423Sdim DEBUG(dbgs() << " SU(" << Idx << ") in tree " 1514249423Sdim << R.DFSNodeData[Idx].SubtreeID << '\n'); 1515249423Sdim } 1516249423Sdim for (std::vector<std::pair<const SUnit*, const SUnit*> >::const_iterator 1517249423Sdim I = ConnectionPairs.begin(), E = ConnectionPairs.end(); 1518249423Sdim I != E; ++I) { 1519249423Sdim unsigned PredTree = SubtreeClasses[I->first->NodeNum]; 1520249423Sdim unsigned SuccTree = SubtreeClasses[I->second->NodeNum]; 1521249423Sdim if (PredTree == SuccTree) 1522249423Sdim continue; 1523249423Sdim unsigned Depth = I->first->getDepth(); 1524249423Sdim addConnection(PredTree, SuccTree, Depth); 1525249423Sdim addConnection(SuccTree, PredTree, Depth); 1526249423Sdim } 1527249423Sdim } 1528249423Sdim 1529249423Sdimprotected: 1530249423Sdim /// Join the predecessor subtree with the successor that is its DFS 1531249423Sdim /// parent. Apply some heuristics before joining. 1532249423Sdim bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, 1533249423Sdim bool CheckLimit = true) { 1534249423Sdim assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges"); 1535249423Sdim 1536249423Sdim // Check if the predecessor is already joined. 1537249423Sdim const SUnit *PredSU = PredDep.getSUnit(); 1538249423Sdim unsigned PredNum = PredSU->NodeNum; 1539249423Sdim if (R.DFSNodeData[PredNum].SubtreeID != PredNum) 1540249423Sdim return false; 1541249423Sdim 1542249423Sdim // Four is the magic number of successors before a node is considered a 1543249423Sdim // pinch point. 1544249423Sdim unsigned NumDataSucs = 0; 1545249423Sdim for (SUnit::const_succ_iterator SI = PredSU->Succs.begin(), 1546249423Sdim SE = PredSU->Succs.end(); SI != SE; ++SI) { 1547249423Sdim if (SI->getKind() == SDep::Data) { 1548249423Sdim if (++NumDataSucs >= 4) 1549249423Sdim return false; 1550249423Sdim } 1551249423Sdim } 1552249423Sdim if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit) 1553249423Sdim return false; 1554249423Sdim R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum; 1555249423Sdim SubtreeClasses.join(Succ->NodeNum, PredNum); 1556249423Sdim return true; 1557249423Sdim } 1558249423Sdim 1559249423Sdim /// Called by finalize() to record a connection between trees. 1560249423Sdim void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) { 1561249423Sdim if (!Depth) 1562249423Sdim return; 1563249423Sdim 1564249423Sdim do { 1565249423Sdim SmallVectorImpl<SchedDFSResult::Connection> &Connections = 1566249423Sdim R.SubtreeConnections[FromTree]; 1567249423Sdim for (SmallVectorImpl<SchedDFSResult::Connection>::iterator 1568249423Sdim I = Connections.begin(), E = Connections.end(); I != E; ++I) { 1569249423Sdim if (I->TreeID == ToTree) { 1570249423Sdim I->Level = std::max(I->Level, Depth); 1571249423Sdim return; 1572249423Sdim } 1573249423Sdim } 1574249423Sdim Connections.push_back(SchedDFSResult::Connection(ToTree, Depth)); 1575249423Sdim FromTree = R.DFSTreeData[FromTree].ParentTreeID; 1576249423Sdim } while (FromTree != SchedDFSResult::InvalidSubtreeID); 1577249423Sdim } 1578249423Sdim}; 1579249423Sdim} // namespace llvm 1580249423Sdim 1581243830Sdimnamespace { 1582243830Sdim/// \brief Manage the stack used by a reverse depth-first search over the DAG. 1583243830Sdimclass SchedDAGReverseDFS { 1584243830Sdim std::vector<std::pair<const SUnit*, SUnit::const_pred_iterator> > DFSStack; 1585243830Sdimpublic: 1586243830Sdim bool isComplete() const { return DFSStack.empty(); } 1587243830Sdim 1588243830Sdim void follow(const SUnit *SU) { 1589243830Sdim DFSStack.push_back(std::make_pair(SU, SU->Preds.begin())); 1590243830Sdim } 1591243830Sdim void advance() { ++DFSStack.back().second; } 1592243830Sdim 1593249423Sdim const SDep *backtrack() { 1594249423Sdim DFSStack.pop_back(); 1595276479Sdim return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second); 1596249423Sdim } 1597243830Sdim 1598243830Sdim const SUnit *getCurr() const { return DFSStack.back().first; } 1599243830Sdim 1600243830Sdim SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; } 1601243830Sdim 1602243830Sdim SUnit::const_pred_iterator getPredEnd() const { 1603243830Sdim return getCurr()->Preds.end(); 1604243830Sdim } 1605243830Sdim}; 1606243830Sdim} // anonymous 1607243830Sdim 1608249423Sdimstatic bool hasDataSucc(const SUnit *SU) { 1609249423Sdim for (SUnit::const_succ_iterator 1610249423Sdim SI = SU->Succs.begin(), SE = SU->Succs.end(); SI != SE; ++SI) { 1611249423Sdim if (SI->getKind() == SDep::Data && !SI->getSUnit()->isBoundaryNode()) 1612249423Sdim return true; 1613249423Sdim } 1614249423Sdim return false; 1615243830Sdim} 1616243830Sdim 1617243830Sdim/// Compute an ILP metric for all nodes in the subDAG reachable via depth-first 1618243830Sdim/// search from this root. 1619249423Sdimvoid SchedDFSResult::compute(ArrayRef<SUnit> SUnits) { 1620243830Sdim if (!IsBottomUp) 1621243830Sdim llvm_unreachable("Top-down ILP metric is unimplemnted"); 1622243830Sdim 1623249423Sdim SchedDFSImpl Impl(*this); 1624249423Sdim for (ArrayRef<SUnit>::const_iterator 1625249423Sdim SI = SUnits.begin(), SE = SUnits.end(); SI != SE; ++SI) { 1626249423Sdim const SUnit *SU = &*SI; 1627249423Sdim if (Impl.isVisited(SU) || hasDataSucc(SU)) 1628249423Sdim continue; 1629249423Sdim 1630249423Sdim SchedDAGReverseDFS DFS; 1631249423Sdim Impl.visitPreorder(SU); 1632249423Sdim DFS.follow(SU); 1633249423Sdim for (;;) { 1634249423Sdim // Traverse the leftmost path as far as possible. 1635249423Sdim while (DFS.getPred() != DFS.getPredEnd()) { 1636249423Sdim const SDep &PredDep = *DFS.getPred(); 1637249423Sdim DFS.advance(); 1638249423Sdim // Ignore non-data edges. 1639249423Sdim if (PredDep.getKind() != SDep::Data 1640249423Sdim || PredDep.getSUnit()->isBoundaryNode()) { 1641249423Sdim continue; 1642249423Sdim } 1643249423Sdim // An already visited edge is a cross edge, assuming an acyclic DAG. 1644249423Sdim if (Impl.isVisited(PredDep.getSUnit())) { 1645249423Sdim Impl.visitCrossEdge(PredDep, DFS.getCurr()); 1646249423Sdim continue; 1647249423Sdim } 1648249423Sdim Impl.visitPreorder(PredDep.getSUnit()); 1649249423Sdim DFS.follow(PredDep.getSUnit()); 1650249423Sdim } 1651249423Sdim // Visit the top of the stack in postorder and backtrack. 1652249423Sdim const SUnit *Child = DFS.getCurr(); 1653249423Sdim const SDep *PredDep = DFS.backtrack(); 1654249423Sdim Impl.visitPostorderNode(Child); 1655249423Sdim if (PredDep) 1656249423Sdim Impl.visitPostorderEdge(*PredDep, DFS.getCurr()); 1657249423Sdim if (DFS.isComplete()) 1658249423Sdim break; 1659243830Sdim } 1660243830Sdim } 1661249423Sdim Impl.finalize(); 1662243830Sdim} 1663243830Sdim 1664249423Sdim/// The root of the given SubtreeID was just scheduled. For all subtrees 1665249423Sdim/// connected to this tree, record the depth of the connection so that the 1666249423Sdim/// nearest connected subtrees can be prioritized. 1667249423Sdimvoid SchedDFSResult::scheduleTree(unsigned SubtreeID) { 1668249423Sdim for (SmallVectorImpl<Connection>::const_iterator 1669249423Sdim I = SubtreeConnections[SubtreeID].begin(), 1670249423Sdim E = SubtreeConnections[SubtreeID].end(); I != E; ++I) { 1671249423Sdim SubtreeConnectLevels[I->TreeID] = 1672249423Sdim std::max(SubtreeConnectLevels[I->TreeID], I->Level); 1673249423Sdim DEBUG(dbgs() << " Tree: " << I->TreeID 1674249423Sdim << " @" << SubtreeConnectLevels[I->TreeID] << '\n'); 1675249423Sdim } 1676249423Sdim} 1677249423Sdim 1678276479SdimLLVM_DUMP_METHOD 1679243830Sdimvoid ILPValue::print(raw_ostream &OS) const { 1680249423Sdim OS << InstrCount << " / " << Length << " = "; 1681249423Sdim if (!Length) 1682243830Sdim OS << "BADILP"; 1683249423Sdim else 1684249423Sdim OS << format("%g", ((double)InstrCount / Length)); 1685243830Sdim} 1686243830Sdim 1687276479SdimLLVM_DUMP_METHOD 1688243830Sdimvoid ILPValue::dump() const { 1689243830Sdim dbgs() << *this << '\n'; 1690243830Sdim} 1691243830Sdim 1692243830Sdimnamespace llvm { 1693243830Sdim 1694276479SdimLLVM_DUMP_METHOD 1695243830Sdimraw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) { 1696243830Sdim Val.print(OS); 1697243830Sdim return OS; 1698243830Sdim} 1699243830Sdim 1700243830Sdim} // namespace llvm 1701