Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
Line
Count
Source (jump to first uncovered line)
1
//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
/// \file This implements the ScheduleDAGInstrs class, which implements
10
/// re-scheduling of MachineInstrs.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
15
#include "llvm/ADT/IntEqClasses.h"
16
#include "llvm/ADT/MapVector.h"
17
#include "llvm/ADT/SmallPtrSet.h"
18
#include "llvm/ADT/SmallVector.h"
19
#include "llvm/ADT/SparseSet.h"
20
#include "llvm/ADT/iterator_range.h"
21
#include "llvm/Analysis/AliasAnalysis.h"
22
#include "llvm/Analysis/ValueTracking.h"
23
#include "llvm/CodeGen/LiveIntervals.h"
24
#include "llvm/CodeGen/LivePhysRegs.h"
25
#include "llvm/CodeGen/MachineBasicBlock.h"
26
#include "llvm/CodeGen/MachineFrameInfo.h"
27
#include "llvm/CodeGen/MachineFunction.h"
28
#include "llvm/CodeGen/MachineInstr.h"
29
#include "llvm/CodeGen/MachineInstrBundle.h"
30
#include "llvm/CodeGen/MachineMemOperand.h"
31
#include "llvm/CodeGen/MachineOperand.h"
32
#include "llvm/CodeGen/MachineRegisterInfo.h"
33
#include "llvm/CodeGen/PseudoSourceValue.h"
34
#include "llvm/CodeGen/RegisterPressure.h"
35
#include "llvm/CodeGen/ScheduleDAG.h"
36
#include "llvm/CodeGen/ScheduleDFS.h"
37
#include "llvm/CodeGen/SlotIndexes.h"
38
#include "llvm/CodeGen/TargetRegisterInfo.h"
39
#include "llvm/CodeGen/TargetSubtargetInfo.h"
40
#include "llvm/Config/llvm-config.h"
41
#include "llvm/IR/Constants.h"
42
#include "llvm/IR/Function.h"
43
#include "llvm/IR/Instruction.h"
44
#include "llvm/IR/Instructions.h"
45
#include "llvm/IR/Operator.h"
46
#include "llvm/IR/Type.h"
47
#include "llvm/IR/Value.h"
48
#include "llvm/MC/LaneBitmask.h"
49
#include "llvm/MC/MCRegisterInfo.h"
50
#include "llvm/Support/Casting.h"
51
#include "llvm/Support/CommandLine.h"
52
#include "llvm/Support/Compiler.h"
53
#include "llvm/Support/Debug.h"
54
#include "llvm/Support/ErrorHandling.h"
55
#include "llvm/Support/Format.h"
56
#include "llvm/Support/raw_ostream.h"
57
#include <algorithm>
58
#include <cassert>
59
#include <iterator>
60
#include <string>
61
#include <utility>
62
#include <vector>
63
64
using namespace llvm;
65
66
#define DEBUG_TYPE "machine-scheduler"
67
68
static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
69
    cl::ZeroOrMore, cl::init(false),
70
    cl::desc("Enable use of AA during MI DAG construction"));
71
72
static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden,
73
    cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"));
74
75
// Note: the two options below might be used in tuning compile time vs
76
// output quality. Setting HugeRegion so large that it will never be
77
// reached means best-effort, but may be slow.
78
79
// When Stores and Loads maps (or NonAliasStores and NonAliasLoads)
80
// together hold this many SUs, a reduction of maps will be done.
81
static cl::opt<unsigned> HugeRegion("dag-maps-huge-region", cl::Hidden,
82
    cl::init(1000), cl::desc("The limit to use while constructing the DAG "
83
                             "prior to scheduling, at which point a trade-off "
84
                             "is made to avoid excessive compile time."));
85
86
static cl::opt<unsigned> ReductionSize(
87
    "dag-maps-reduction-size", cl::Hidden,
88
    cl::desc("A huge scheduling region will have maps reduced by this many "
89
             "nodes at a time. Defaults to HugeRegion / 2."));
90
91
0
static unsigned getReductionSize() {
92
0
  // Always reduce a huge region with half of the elements, except
93
0
  // when user sets this number explicitly.
94
0
  if (ReductionSize.getNumOccurrences() == 0)
95
0
    return HugeRegion / 2;
96
0
  return ReductionSize;
97
0
}
98
99
0
static void dumpSUList(ScheduleDAGInstrs::SUList &L) {
100
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
101
  dbgs() << "{ ";
102
  for (const SUnit *su : L) {
103
    dbgs() << "SU(" << su->NodeNum << ")";
104
    if (su != L.back())
105
      dbgs() << ", ";
106
  }
107
  dbgs() << "}\n";
108
#endif
109
}
110
111
ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
112
                                     const MachineLoopInfo *mli,
113
                                     bool RemoveKillFlags)
114
    : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
115
      RemoveKillFlags(RemoveKillFlags),
116
      UnknownValue(UndefValue::get(
117
526k
                             Type::getVoidTy(mf.getFunction().getContext()))), Topo(SUnits, &ExitSU) {
118
526k
  DbgValues.clear();
119
526k
120
526k
  const TargetSubtargetInfo &ST = mf.getSubtarget();
121
526k
  SchedModel.init(&ST);
122
526k
}
123
124
/// If this machine instr has memory reference information and it can be
125
/// tracked to a normal reference to a known object, return the Value
126
/// for that object. This function returns false the memory location is
127
/// unknown or may alias anything.
128
static bool getUnderlyingObjectsForInstr(const MachineInstr *MI,
129
                                         const MachineFrameInfo &MFI,
130
                                         UnderlyingObjectsVector &Objects,
131
2.61M
                                         const DataLayout &DL) {
132
2.61M
  auto allMMOsOkay = [&]() {
133
2.62M
    for (const MachineMemOperand *MMO : MI->memoperands()) {
134
2.62M
      // TODO: Figure out whether isAtomic is really necessary (see D57601).
135
2.62M
      if (MMO->isVolatile() || 
MMO->isAtomic()2.62M
)
136
526
        return false;
137
2.62M
138
2.62M
      if (const PseudoSourceValue *PSV = MMO->getPseudoValue()) {
139
166k
        // Function that contain tail calls don't have unique PseudoSourceValue
140
166k
        // objects. Two PseudoSourceValues might refer to the same or
141
166k
        // overlapping locations. The client code calling this function assumes
142
166k
        // this is not the case. So return a conservative answer of no known
143
166k
        // object.
144
166k
        if (MFI.hasTailCall())
145
11.0k
          return false;
146
155k
147
155k
        // For now, ignore PseudoSourceValues which may alias LLVM IR values
148
155k
        // because the code that uses this function has no way to cope with
149
155k
        // such aliases.
150
155k
        if (PSV->isAliased(&MFI))
151
40.5k
          return false;
152
115k
153
115k
        bool MayAlias = PSV->mayAlias(&MFI);
154
115k
        Objects.push_back(UnderlyingObjectsVector::value_type(PSV, MayAlias));
155
2.45M
      } else if (const Value *V = MMO->getValue()) {
156
2.44M
        SmallVector<Value *, 4> Objs;
157
2.44M
        if (!getUnderlyingObjectsForCodeGen(V, Objs, DL))
158
1.45M
          return false;
159
988k
160
992k
        
for (Value *V : Objs)988k
{
161
992k
          assert(isIdentifiedObject(V));
162
992k
          Objects.push_back(UnderlyingObjectsVector::value_type(V, true));
163
992k
        }
164
988k
      } else
165
15.6k
        return false;
166
2.62M
    }
167
2.61M
    
return true1.08M
;
168
2.61M
  };
169
2.61M
170
2.61M
  if (!allMMOsOkay()) {
171
1.52M
    Objects.clear();
172
1.52M
    return false;
173
1.52M
  }
174
1.08M
175
1.08M
  return true;
176
1.08M
}
177
178
2.88M
void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) {
179
2.88M
  BB = bb;
180
2.88M
}
181
182
2.89M
void ScheduleDAGInstrs::finishBlock() {
183
2.89M
  // Subclasses should no longer refer to the old block.
184
2.89M
  BB = nullptr;
185
2.89M
}
186
187
void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb,
188
                                    MachineBasicBlock::iterator begin,
189
                                    MachineBasicBlock::iterator end,
190
4.99M
                                    unsigned regioninstrs) {
191
4.99M
  assert(bb == BB && "startBlock should set BB");
192
4.99M
  RegionBegin = begin;
193
4.99M
  RegionEnd = end;
194
4.99M
  NumRegionInstrs = regioninstrs;
195
4.99M
}
196
197
4.99M
void ScheduleDAGInstrs::exitRegion() {
198
4.99M
  // Nothing to do.
199
4.99M
}
200
201
2.99M
void ScheduleDAGInstrs::addSchedBarrierDeps() {
202
2.99M
  MachineInstr *ExitMI = RegionEnd != BB->end() ? 
&*RegionEnd2.68M
:
nullptr301k
;
203
2.99M
  ExitSU.setInstr(ExitMI);
204
2.99M
  // Add dependencies on the defs and uses of the instruction.
205
2.99M
  if (ExitMI) {
206
12.9M
    for (const MachineOperand &MO : ExitMI->operands()) {
207
12.9M
      if (!MO.isReg() || 
MO.isDef()8.21M
)
continue7.16M
;
208
5.73M
      unsigned Reg = MO.getReg();
209
5.73M
      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
210
5.34M
        Uses.insert(PhysRegSUOper(&ExitSU, -1, Reg));
211
5.34M
      } else 
if (389k
TargetRegisterInfo::isVirtualRegister(Reg)389k
&&
MO.readsReg()282k
) {
212
282k
        addVRegUseDeps(&ExitSU, ExitMI->getOperandNo(&MO));
213
282k
      }
214
5.73M
    }
215
2.68M
  }
216
2.99M
  if (!ExitMI || 
(2.68M
!ExitMI->isCall()2.68M
&&
!ExitMI->isBarrier()1.66M
)) {
217
1.56M
    // For others, e.g. fallthrough, conditional branch, assume the exit
218
1.56M
    // uses all the registers that are livein to the successor blocks.
219
2.36M
    for (const MachineBasicBlock *Succ : BB->successors()) {
220
2.36M
      for (const auto &LI : Succ->liveins()) {
221
772k
        if (!Uses.contains(LI.PhysReg))
222
551k
          Uses.insert(PhysRegSUOper(&ExitSU, -1, LI.PhysReg));
223
772k
      }
224
2.36M
    }
225
1.56M
  }
226
2.99M
}
227
228
/// MO is an operand of SU's instruction that defines a physical register. Adds
229
/// data dependencies from SU to any uses of the physical register.
230
5.11M
void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) {
231
5.11M
  const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx);
232
5.11M
  assert(MO.isDef() && "expect physreg def");
233
5.11M
234
5.11M
  // Ask the target if address-backscheduling is desirable, and if so how much.
235
5.11M
  const TargetSubtargetInfo &ST = MF.getSubtarget();
236
5.11M
237
5.11M
  // Only use any non-zero latency for real defs/uses, in contrast to
238
5.11M
  // "fake" operands added by regalloc.
239
5.11M
  const MCInstrDesc *DefMIDesc = &SU->getInstr()->getDesc();
240
5.11M
  bool ImplicitPseudoDef = (OperIdx >= DefMIDesc->getNumOperands() &&
241
5.11M
                            
!DefMIDesc->hasImplicitDefOfPhysReg(MO.getReg())1.30M
);
242
5.11M
  for (MCRegAliasIterator Alias(MO.getReg(), TRI, true);
243
32.5M
       Alias.isValid(); 
++Alias27.4M
) {
244
27.4M
    if (!Uses.contains(*Alias))
245
22.0M
      continue;
246
11.0M
    
for (Reg2SUnitsMap::iterator I = Uses.find(*Alias); 5.33M
I != Uses.end();
++I5.69M
) {
247
5.69M
      SUnit *UseSU = I->SU;
248
5.69M
      if (UseSU == SU)
249
0
        continue;
250
5.69M
251
5.69M
      // Adjust the dependence latency using operand def/use information,
252
5.69M
      // then allow the target to perform its own adjustments.
253
5.69M
      int UseOp = I->OpIdx;
254
5.69M
      MachineInstr *RegUse = nullptr;
255
5.69M
      SDep Dep;
256
5.69M
      if (UseOp < 0)
257
4.28M
        Dep = SDep(SU, SDep::Artificial);
258
1.41M
      else {
259
1.41M
        // Set the hasPhysRegDefs only for physreg defs that have a use within
260
1.41M
        // the scheduling region.
261
1.41M
        SU->hasPhysRegDefs = true;
262
1.41M
        Dep = SDep(SU, SDep::Data, *Alias);
263
1.41M
        RegUse = UseSU->getInstr();
264
1.41M
      }
265
5.69M
      const MCInstrDesc *UseMIDesc =
266
5.69M
          (RegUse ? 
&UseSU->getInstr()->getDesc()1.41M
:
nullptr4.28M
);
267
5.69M
      bool ImplicitPseudoUse =
268
5.69M
          (UseMIDesc && 
UseOp >= ((int)UseMIDesc->getNumOperands())1.41M
&&
269
5.69M
           
!UseMIDesc->hasImplicitUseOfPhysReg(*Alias)435k
);
270
5.69M
      if (!ImplicitPseudoDef && 
!ImplicitPseudoUse5.54M
) {
271
5.41M
        Dep.setLatency(SchedModel.computeOperandLatency(SU->getInstr(), OperIdx,
272
5.41M
                                                        RegUse, UseOp));
273
5.41M
        ST.adjustSchedDependency(SU, UseSU, Dep);
274
5.41M
      } else
275
281k
        Dep.setLatency(0);
276
5.69M
277
5.69M
      UseSU->addPred(Dep);
278
5.69M
    }
279
5.33M
  }
280
5.11M
}
281
282
/// Adds register dependencies (data, anti, and output) from this SUnit
283
/// to following instructions in the same scheduling region that depend the
284
/// physical register referenced at OperIdx.
285
9.36M
void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) {
286
9.36M
  MachineInstr *MI = SU->getInstr();
287
9.36M
  MachineOperand &MO = MI->getOperand(OperIdx);
288
9.36M
  unsigned Reg = MO.getReg();
289
9.36M
  // We do not need to track any dependencies for constant registers.
290
9.36M
  if (MRI.isConstantPhysReg(Reg))
291
1.76M
    return;
292
7.59M
293
7.59M
  // Optionally add output and anti dependencies. For anti
294
7.59M
  // dependencies we use a latency of 0 because for a multi-issue
295
7.59M
  // target we want to allow the defining instruction to issue
296
7.59M
  // in the same cycle as the using instruction.
297
7.59M
  // TODO: Using a latency of 1 here for output dependencies assumes
298
7.59M
  //       there's no cost for reusing registers.
299
7.59M
  SDep::Kind Kind = MO.isUse() ? 
SDep::Anti2.48M
:
SDep::Output5.11M
;
300
56.0M
  for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); 
++Alias48.4M
) {
301
48.4M
    if (!Defs.contains(*Alias))
302
46.5M
      continue;
303
5.15M
    
for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); 1.89M
I != Defs.end();
++I3.26M
) {
304
3.26M
      SUnit *DefSU = I->SU;
305
3.26M
      if (DefSU == &ExitSU)
306
0
        continue;
307
3.26M
      if (DefSU != SU &&
308
3.26M
          
(2.81M
Kind != SDep::Output2.81M
||
!MO.isDead()2.18M
||
309
2.81M
           
!DefSU->getInstr()->registerDefIsDead(*Alias)1.57M
)) {
310
1.40M
        if (Kind == SDep::Anti)
311
632k
          DefSU->addPred(SDep(SU, Kind, /*Reg=*/*Alias));
312
774k
        else {
313
774k
          SDep Dep(SU, Kind, /*Reg=*/*Alias);
314
774k
          Dep.setLatency(
315
774k
            SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
316
774k
          DefSU->addPred(Dep);
317
774k
        }
318
1.40M
      }
319
3.26M
    }
320
1.89M
  }
321
7.59M
322
7.59M
  if (!MO.isDef()) {
323
2.48M
    SU->hasPhysRegUses = true;
324
2.48M
    // Either insert a new Reg2SUnits entry with an empty SUnits list, or
325
2.48M
    // retrieve the existing SUnits list for this register's uses.
326
2.48M
    // Push this SUnit on the use list.
327
2.48M
    Uses.insert(PhysRegSUOper(SU, OperIdx, Reg));
328
2.48M
    if (RemoveKillFlags)
329
220k
      MO.setIsKill(false);
330
5.11M
  } else {
331
5.11M
    addPhysRegDataDeps(SU, OperIdx);
332
5.11M
333
5.11M
    // Clear previous uses and defs of this register and its subergisters.
334
14.6M
    for (MCSubRegIterator SubReg(Reg, TRI, true); SubReg.isValid(); 
++SubReg9.49M
) {
335
9.49M
      if (Uses.contains(*SubReg))
336
4.51M
        Uses.eraseAll(*SubReg);
337
9.49M
      if (!MO.isDead())
338
8.85M
        Defs.eraseAll(*SubReg);
339
9.49M
    }
340
5.11M
    if (MO.isDead() && 
SU->isCall481k
) {
341
1.40k
      // Calls will not be reordered because of chain dependencies (see
342
1.40k
      // below). Since call operands are dead, calls may continue to be added
343
1.40k
      // to the DefList making dependence checking quadratic in the size of
344
1.40k
      // the block. Instead, we leave only one call at the back of the
345
1.40k
      // DefList.
346
1.40k
      Reg2SUnitsMap::RangePair P = Defs.equal_range(Reg);
347
1.40k
      Reg2SUnitsMap::iterator B = P.first;
348
1.40k
      Reg2SUnitsMap::iterator I = P.second;
349
2.02k
      for (bool isBegin = I == B; !isBegin; /* empty */) {
350
1.10k
        isBegin = (--I) == B;
351
1.10k
        if (!I->SU->isCall)
352
476
          break;
353
628
        I = Defs.erase(I);
354
628
      }
355
1.40k
    }
356
5.11M
357
5.11M
    // Defs are pushed in the order they are visited and never reordered.
358
5.11M
    Defs.insert(PhysRegSUOper(SU, OperIdx, Reg));
359
5.11M
  }
360
7.59M
}
361
362
LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const
363
782k
{
364
782k
  unsigned Reg = MO.getReg();
365
782k
  // No point in tracking lanemasks if we don't have interesting subregisters.
366
782k
  const TargetRegisterClass &RC = *MRI.getRegClass(Reg);
367
782k
  if (!RC.HasDisjunctSubRegs)
368
310k
    return LaneBitmask::getAll();
369
471k
370
471k
  unsigned SubReg = MO.getSubReg();
371
471k
  if (SubReg == 0)
372
213k
    return RC.getLaneMask();
373
257k
  return TRI->getSubRegIndexLaneMask(SubReg);
374
257k
}
375
376
/// Adds register output and data dependencies from this SUnit to instructions
377
/// that occur later in the same scheduling region if they read from or write to
378
/// the virtual register defined at OperIdx.
379
///
380
/// TODO: Hoist loop induction variable increments. This has to be
381
/// reevaluated. Generally, IV scheduling should be done before coalescing.
382
7.10M
void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
383
7.10M
  MachineInstr *MI = SU->getInstr();
384
7.10M
  MachineOperand &MO = MI->getOperand(OperIdx);
385
7.10M
  unsigned Reg = MO.getReg();
386
7.10M
387
7.10M
  LaneBitmask DefLaneMask;
388
7.10M
  LaneBitmask KillLaneMask;
389
7.10M
  if (TrackLaneMasks) {
390
360k
    bool IsKill = MO.getSubReg() == 0 || 
MO.isUndef()141k
;
391
360k
    DefLaneMask = getLaneMaskForMO(MO);
392
360k
    // If we have a <read-undef> flag, none of the lane values comes from an
393
360k
    // earlier instruction.
394
360k
    KillLaneMask = IsKill ? 
LaneBitmask::getAll()266k
:
DefLaneMask94.2k
;
395
360k
396
360k
    // Clear undef flag, we'll re-add it later once we know which subregister
397
360k
    // Def is first.
398
360k
    MO.setIsUndef(false);
399
6.74M
  } else {
400
6.74M
    DefLaneMask = LaneBitmask::getAll();
401
6.74M
    KillLaneMask = LaneBitmask::getAll();
402
6.74M
  }
403
7.10M
404
7.10M
  if (MO.isDead()) {
405
16.7k
    assert(CurrentVRegUses.find(Reg) == CurrentVRegUses.end() &&
406
16.7k
           "Dead defs should have no uses");
407
7.09M
  } else {
408
7.09M
    // Add data dependence to all uses we found so far.
409
7.09M
    const TargetSubtargetInfo &ST = MF.getSubtarget();
410
7.09M
    for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Reg),
411
13.3M
         E = CurrentVRegUses.end(); I != E; /*empty*/) {
412
6.22M
      LaneBitmask LaneMask = I->LaneMask;
413
6.22M
      // Ignore uses of other lanes.
414
6.22M
      if ((LaneMask & KillLaneMask).none()) {
415
56.3k
        ++I;
416
56.3k
        continue;
417
56.3k
      }
418
6.16M
419
6.16M
      
if (6.16M
(LaneMask & DefLaneMask).any()6.16M
) {
420
6.16M
        SUnit *UseSU = I->SU;
421
6.16M
        MachineInstr *Use = UseSU->getInstr();
422
6.16M
        SDep Dep(SU, SDep::Data, Reg);
423
6.16M
        Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use,
424
6.16M
                                                        I->OperandIndex));
425
6.16M
        ST.adjustSchedDependency(SU, UseSU, Dep);
426
6.16M
        UseSU->addPred(Dep);
427
6.16M
      }
428
6.16M
429
6.16M
      LaneMask &= ~KillLaneMask;
430
6.16M
      // If we found a Def for all lanes of this use, remove it from the list.
431
6.16M
      if (LaneMask.any()) {
432
116k
        I->LaneMask = LaneMask;
433
116k
        ++I;
434
116k
      } else
435
6.05M
        I = CurrentVRegUses.erase(I);
436
6.16M
    }
437
7.09M
  }
438
7.10M
439
7.10M
  // Shortcut: Singly defined vregs do not have output/anti dependencies.
440
7.10M
  if (MRI.hasOneDef(Reg))
441
5.56M
    return;
442
1.54M
443
1.54M
  // Add output dependence to the next nearest defs of this vreg.
444
1.54M
  //
445
1.54M
  // Unless this definition is dead, the output dependence should be
446
1.54M
  // transitively redundant with antidependencies from this definition's
447
1.54M
  // uses. We're conservative for now until we have a way to guarantee the uses
448
1.54M
  // are not eliminated sometime during scheduling. The output dependence edge
449
1.54M
  // is also useful if output latency exceeds def-use latency.
450
1.54M
  LaneBitmask LaneMask = DefLaneMask;
451
1.54M
  for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
452
1.54M
                                     CurrentVRegDefs.end())) {
453
728k
    // Ignore defs for other lanes.
454
728k
    if ((V2SU.LaneMask & LaneMask).none())
455
218k
      continue;
456
510k
    // Add an output dependence.
457
510k
    SUnit *DefSU = V2SU.SU;
458
510k
    // Ignore additional defs of the same lanes in one instruction. This can
459
510k
    // happen because lanemasks are shared for targets with too many
460
510k
    // subregisters. We also use some representration tricks/hacks where we
461
510k
    // add super-register defs/uses, to imply that although we only access parts
462
510k
    // of the reg we care about the full one.
463
510k
    if (DefSU == SU)
464
0
      continue;
465
510k
    SDep Dep(SU, SDep::Output, Reg);
466
510k
    Dep.setLatency(
467
510k
      SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
468
510k
    DefSU->addPred(Dep);
469
510k
470
510k
    // Update current definition. This can get tricky if the def was about a
471
510k
    // bigger lanemask before. We then have to shrink it and create a new
472
510k
    // VReg2SUnit for the non-overlapping part.
473
510k
    LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
474
510k
    LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
475
510k
    V2SU.SU = SU;
476
510k
    V2SU.LaneMask = OverlapMask;
477
510k
    if (NonOverlapMask.any())
478
604
      CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, DefSU));
479
510k
  }
480
1.54M
  // If there was no CurrentVRegDefs entry for some lanes yet, create one.
481
1.54M
  if (LaneMask.any())
482
1.54M
    CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU));
483
1.54M
}
484
485
/// Adds a register data dependency if the instruction that defines the
486
/// virtual register used at OperIdx is mapped to an SUnit. Add a register
487
/// antidependency from this SUnit to instructions that occur later in the same
488
/// scheduling region if they write the virtual register.
489
///
490
/// TODO: Handle ExitSU "uses" properly.
491
11.9M
void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
492
11.9M
  const MachineInstr *MI = SU->getInstr();
493
11.9M
  const MachineOperand &MO = MI->getOperand(OperIdx);
494
11.9M
  unsigned Reg = MO.getReg();
495
11.9M
496
11.9M
  // Remember the use. Data dependencies will be added when we find the def.
497
11.9M
  LaneBitmask LaneMask = TrackLaneMasks ? 
getLaneMaskForMO(MO)422k
498
11.9M
                                        : 
LaneBitmask::getAll()11.5M
;
499
11.9M
  CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU));
500
11.9M
501
11.9M
  // Add antidependences to the following defs of the vreg.
502
11.9M
  for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
503
11.9M
                                     CurrentVRegDefs.end())) {
504
1.20M
    // Ignore defs for unrelated lanes.
505
1.20M
    LaneBitmask PrevDefLaneMask = V2SU.LaneMask;
506
1.20M
    if ((PrevDefLaneMask & LaneMask).none())
507
28.1k
      continue;
508
1.17M
    if (V2SU.SU == SU)
509
757k
      continue;
510
419k
511
419k
    V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg));
512
419k
  }
513
11.9M
}
514
515
/// Returns true if MI is an instruction we are unable to reason about
516
/// (like a call or something with unmodeled side effects).
517
12.9M
static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) {
518
12.9M
  return MI->isCall() || 
MI->hasUnmodeledSideEffects()12.9M
||
519
12.9M
         
(12.7M
MI->hasOrderedMemoryRef()12.7M
&&
!MI->isDereferenceableInvariantLoad(AA)117k
);
520
12.9M
}
521
522
void ScheduleDAGInstrs::addChainDependency (SUnit *SUa, SUnit *SUb,
523
16.5M
                                            unsigned Latency) {
524
16.5M
  if (SUa->getInstr()->mayAlias(AAForDep, *SUb->getInstr(), UseTBAA)) {
525
4.59M
    SDep Dep(SUa, SDep::MayAliasMem);
526
4.59M
    Dep.setLatency(Latency);
527
4.59M
    SUb->addPred(Dep);
528
4.59M
  }
529
16.5M
}
530
531
/// Creates an SUnit for each real instruction, numbered in top-down
532
/// topological order. The instruction order A < B, implies that no edge exists
533
/// from B to A.
534
///
535
/// Map each real instruction to its SUnit.
536
///
537
/// After initSUnits, the SUnits vector cannot be resized and the scheduler may
538
/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs
539
/// instead of pointers.
540
///
541
/// MachineScheduler relies on initSUnits numbering the nodes by their order in
542
/// the original instruction list.
543
2.99M
void ScheduleDAGInstrs::initSUnits() {
544
2.99M
  // We'll be allocating one SUnit for each real instruction in the region,
545
2.99M
  // which is contained within a basic block.
546
2.99M
  SUnits.reserve(NumRegionInstrs);
547
2.99M
548
12.9M
  for (MachineInstr &MI : make_range(RegionBegin, RegionEnd)) {
549
12.9M
    if (MI.isDebugInstr())
550
999
      continue;
551
12.9M
552
12.9M
    SUnit *SU = newSUnit(&MI);
553
12.9M
    MISUnitMap[&MI] = SU;
554
12.9M
555
12.9M
    SU->isCall = MI.isCall();
556
12.9M
    SU->isCommutable = MI.isCommutable();
557
12.9M
558
12.9M
    // Assign the Latency field of SU using target-provided information.
559
12.9M
    SU->Latency = SchedModel.computeInstrLatency(SU->getInstr());
560
12.9M
561
12.9M
    // If this SUnit uses a reserved or unbuffered resource, mark it as such.
562
12.9M
    //
563
12.9M
    // Reserved resources block an instruction from issuing and stall the
564
12.9M
    // entire pipeline. These are identified by BufferSize=0.
565
12.9M
    //
566
12.9M
    // Unbuffered resources prevent execution of subsequent instructions that
567
12.9M
    // require the same resources. This is used for in-order execution pipelines
568
12.9M
    // within an out-of-order core. These are identified by BufferSize=1.
569
12.9M
    if (SchedModel.hasInstrSchedModel()) {
570
11.1M
      const MCSchedClassDesc *SC = getSchedClass(SU);
571
11.1M
      for (const MCWriteProcResEntry &PRE :
572
11.1M
           make_range(SchedModel.getWriteProcResBegin(SC),
573
11.3M
                      SchedModel.getWriteProcResEnd(SC))) {
574
11.3M
        switch (SchedModel.getProcResource(PRE.ProcResourceIdx)->BufferSize) {
575
11.3M
        case 0:
576
21.8k
          SU->hasReservedResource = true;
577
21.8k
          break;
578
11.3M
        case 1:
579
511k
          SU->isUnbuffered = true;
580
511k
          break;
581
11.3M
        default:
582
10.8M
          break;
583
11.3M
        }
584
11.3M
      }
585
11.1M
    }
586
12.9M
  }
587
2.99M
}
588
589
class ScheduleDAGInstrs::Value2SUsMap : public MapVector<ValueType, SUList> {
590
  /// Current total number of SUs in map.
591
  unsigned NumNodes = 0;
592
593
  /// 1 for loads, 0 for stores. (see comment in SUList)
594
  unsigned TrueMemOrderLatency;
595
596
public:
597
14.9M
  Value2SUsMap(unsigned lat = 0) : TrueMemOrderLatency(lat) {}
598
599
  /// To keep NumNodes up to date, insert() is used instead of
600
  /// this operator w/ push_back().
601
0
  ValueType &operator[](const SUList &Key) {
602
0
    llvm_unreachable("Don't use. Use insert() instead."); };
603
604
  /// Adds SU to the SUList of V. If Map grows huge, reduce its size by calling
605
  /// reduce().
606
2.62M
  void inline insert(SUnit *SU, ValueType V) {
607
2.62M
    MapVector::operator[](V).push_back(SU);
608
2.62M
    NumNodes++;
609
2.62M
  }
610
611
  /// Clears the list of SUs mapped to V.
612
0
  void inline clearList(ValueType V) {
613
0
    iterator Itr = find(V);
614
0
    if (Itr != end()) {
615
0
      assert(NumNodes >= Itr->second.size());
616
0
      NumNodes -= Itr->second.size();
617
0
618
0
      Itr->second.clear();
619
0
    }
620
0
  }
621
622
  /// Clears map from all contents.
623
1.31M
  void clear() {
624
1.31M
    MapVector<ValueType, SUList>::clear();
625
1.31M
    NumNodes = 0;
626
1.31M
  }
627
628
10.4M
  unsigned inline size() const { return NumNodes; }
629
630
  /// Counts the number of SUs in this map after a reduction.
631
0
  void reComputeSize() {
632
0
    NumNodes = 0;
633
0
    for (auto &I : *this)
634
0
      NumNodes += I.second.size();
635
0
  }
636
637
1.35M
  unsigned inline getTrueMemOrderLatency() const {
638
1.35M
    return TrueMemOrderLatency;
639
1.35M
  }
640
641
  void dump();
642
};
643
644
void ScheduleDAGInstrs::addChainDependencies(SUnit *SU,
645
4.08M
                                             Value2SUsMap &Val2SUsMap) {
646
4.08M
  for (auto &I : Val2SUsMap)
647
769k
    addChainDependencies(SU, I.second,
648
769k
                         Val2SUsMap.getTrueMemOrderLatency());
649
4.08M
}
650
651
void ScheduleDAGInstrs::addChainDependencies(SUnit *SU,
652
                                             Value2SUsMap &Val2SUsMap,
653
3.67M
                                             ValueType V) {
654
3.67M
  Value2SUsMap::iterator Itr = Val2SUsMap.find(V);
655
3.67M
  if (Itr != Val2SUsMap.end())
656
583k
    addChainDependencies(SU, Itr->second,
657
583k
                         Val2SUsMap.getTrueMemOrderLatency());
658
3.67M
}
659
660
1.31M
void ScheduleDAGInstrs::addBarrierChain(Value2SUsMap &map) {
661
1.31M
  assert(BarrierChain != nullptr);
662
1.31M
663
1.31M
  for (auto &I : map) {
664
48.6k
    SUList &sus = I.second;
665
48.6k
    for (auto *SU : sus)
666
97.6k
      SU->addPredBarrier(BarrierChain);
667
48.6k
  }
668
1.31M
  map.clear();
669
1.31M
}
670
671
0
void ScheduleDAGInstrs::insertBarrierChain(Value2SUsMap &map) {
672
0
  assert(BarrierChain != nullptr);
673
0
674
0
  // Go through all lists of SUs.
675
0
  for (Value2SUsMap::iterator I = map.begin(), EE = map.end(); I != EE;) {
676
0
    Value2SUsMap::iterator CurrItr = I++;
677
0
    SUList &sus = CurrItr->second;
678
0
    SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
679
0
    for (; SUItr != SUEE; ++SUItr) {
680
0
      // Stop on BarrierChain or any instruction above it.
681
0
      if ((*SUItr)->NodeNum <= BarrierChain->NodeNum)
682
0
        break;
683
0
684
0
      (*SUItr)->addPredBarrier(BarrierChain);
685
0
    }
686
0
687
0
    // Remove also the BarrierChain from list if present.
688
0
    if (SUItr != SUEE && *SUItr == BarrierChain)
689
0
      SUItr++;
690
0
691
0
    // Remove all SUs that are now successors of BarrierChain.
692
0
    if (SUItr != sus.begin())
693
0
      sus.erase(sus.begin(), SUItr);
694
0
  }
695
0
696
0
  // Remove all entries with empty su lists.
697
0
  map.remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
698
0
      return (mapEntry.second.empty()); });
699
0
700
0
  // Recompute the size of the map (NumNodes).
701
0
  map.reComputeSize();
702
0
}
703
704
void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
705
                                        RegPressureTracker *RPTracker,
706
                                        PressureDiffs *PDiffs,
707
                                        LiveIntervals *LIS,
708
2.99M
                                        bool TrackLaneMasks) {
709
2.99M
  const TargetSubtargetInfo &ST = MF.getSubtarget();
710
2.99M
  bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? 
EnableAASchedMI110
711
2.99M
                                                       : 
ST.useAA()2.99M
;
712
2.99M
  AAForDep = UseAA ? 
AA63.9k
:
nullptr2.92M
;
713
2.99M
714
2.99M
  BarrierChain = nullptr;
715
2.99M
716
2.99M
  this->TrackLaneMasks = TrackLaneMasks;
717
2.99M
  MISUnitMap.clear();
718
2.99M
  ScheduleDAG::clearDAG();
719
2.99M
720
2.99M
  // Create an SUnit for each real instruction.
721
2.99M
  initSUnits();
722
2.99M
723
2.99M
  if (PDiffs)
724
158k
    PDiffs->init(SUnits.size());
725
2.99M
726
2.99M
  // We build scheduling units by walking a block's instruction list
727
2.99M
  // from bottom to top.
728
2.99M
729
2.99M
  // Each MIs' memory operand(s) is analyzed to a list of underlying
730
2.99M
  // objects. The SU is then inserted in the SUList(s) mapped from the
731
2.99M
  // Value(s). Each Value thus gets mapped to lists of SUs depending
732
2.99M
  // on it, stores and loads kept separately. Two SUs are trivially
733
2.99M
  // non-aliasing if they both depend on only identified Values and do
734
2.99M
  // not share any common Value.
735
2.99M
  Value2SUsMap Stores, Loads(1 /*TrueMemOrderLatency*/);
736
2.99M
737
2.99M
  // Certain memory accesses are known to not alias any SU in Stores
738
2.99M
  // or Loads, and have therefore their own 'NonAlias'
739
2.99M
  // domain. E.g. spill / reload instructions never alias LLVM I/R
740
2.99M
  // Values. It would be nice to assume that this type of memory
741
2.99M
  // accesses always have a proper memory operand modelling, and are
742
2.99M
  // therefore never unanalyzable, but this is conservatively not
743
2.99M
  // done.
744
2.99M
  Value2SUsMap NonAliasStores, NonAliasLoads(1 /*TrueMemOrderLatency*/);
745
2.99M
746
2.99M
  // Track all instructions that may raise floating-point exceptions.
747
2.99M
  // These do not depend on one other (or normal loads or stores), but
748
2.99M
  // must not be rescheduled across global barriers.  Note that we don't
749
2.99M
  // really need a "map" here since we don't track those MIs by value;
750
2.99M
  // using the same Value2SUsMap data type here is simply a matter of
751
2.99M
  // convenience.
752
2.99M
  Value2SUsMap FPExceptions;
753
2.99M
754
2.99M
  // Remove any stale debug info; sometimes BuildSchedGraph is called again
755
2.99M
  // without emitting the info from the previous call.
756
2.99M
  DbgValues.clear();
757
2.99M
  FirstDbgValue = nullptr;
758
2.99M
759
2.99M
  assert(Defs.empty() && Uses.empty() &&
760
2.99M
         "Only BuildGraph should update Defs/Uses");
761
2.99M
  Defs.setUniverse(TRI->getNumRegs());
762
2.99M
  Uses.setUniverse(TRI->getNumRegs());
763
2.99M
764
2.99M
  assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs");
765
2.99M
  assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses");
766
2.99M
  unsigned NumVirtRegs = MRI.getNumVirtRegs();
767
2.99M
  CurrentVRegDefs.setUniverse(NumVirtRegs);
768
2.99M
  CurrentVRegUses.setUniverse(NumVirtRegs);
769
2.99M
770
2.99M
  // Model data dependencies between instructions being scheduled and the
771
2.99M
  // ExitSU.
772
2.99M
  addSchedBarrierDeps();
773
2.99M
774
2.99M
  // Walk the list of instructions, from bottom moving up.
775
2.99M
  MachineInstr *DbgMI = nullptr;
776
2.99M
  for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin;
777
15.9M
       MII != MIE; 
--MII12.9M
) {
778
12.9M
    MachineInstr &MI = *std::prev(MII);
779
12.9M
    if (DbgMI) {
780
787
      DbgValues.push_back(std::make_pair(DbgMI, &MI));
781
787
      DbgMI = nullptr;
782
787
    }
783
12.9M
784
12.9M
    if (MI.isDebugValue()) {
785
995
      DbgMI = &MI;
786
995
      continue;
787
995
    }
788
12.9M
    if (MI.isDebugLabel())
789
4
      continue;
790
12.9M
791
12.9M
    SUnit *SU = MISUnitMap[&MI];
792
12.9M
    assert(SU && "No SUnit mapped to this MI");
793
12.9M
794
12.9M
    if (RPTracker) {
795
3.01M
      RegisterOperands RegOpers;
796
3.01M
      RegOpers.collect(MI, *TRI, MRI, TrackLaneMasks, false);
797
3.01M
      if (TrackLaneMasks) {
798
406k
        SlotIndex SlotIdx = LIS->getInstructionIndex(MI);
799
406k
        RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx);
800
406k
      }
801
3.01M
      if (PDiffs != nullptr)
802
3.01M
        PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI);
803
3.01M
804
3.01M
      if (RPTracker->getPos() == RegionEnd || 
&*RPTracker->getPos() != &MI2.85M
)
805
3.01M
        RPTracker->recedeSkipDebugValues();
806
3.01M
      assert(&*RPTracker->getPos() == &MI && "RPTracker in sync");
807
3.01M
      RPTracker->recede(RegOpers);
808
3.01M
    }
809
12.9M
810
12.9M
    assert(
811
12.9M
        (CanHandleTerminators || (!MI.isTerminator() && !MI.isPosition())) &&
812
12.9M
        "Cannot schedule terminators or labels!");
813
12.9M
814
12.9M
    // Add register-based dependencies (data, anti, and output).
815
12.9M
    // For some instructions (calls, returns, inline-asm, etc.) there can
816
12.9M
    // be explicit uses and implicit defs, in which case the use will appear
817
12.9M
    // on the operand list before the def. Do two passes over the operand
818
12.9M
    // list to make sure that defs are processed before any uses.
819
12.9M
    bool HasVRegDef = false;
820
54.2M
    for (unsigned j = 0, n = MI.getNumOperands(); j != n; 
++j41.2M
) {
821
41.2M
      const MachineOperand &MO = MI.getOperand(j);
822
41.2M
      if (!MO.isReg() || 
!MO.isDef()29.6M
)
823
28.5M
        continue;
824
12.7M
      unsigned Reg = MO.getReg();
825
12.7M
      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
826
5.63M
        addPhysRegDeps(SU, j);
827
7.10M
      } else if (TargetRegisterInfo::isVirtualRegister(Reg)) {
828
7.10M
        HasVRegDef = true;
829
7.10M
        addVRegDefDeps(SU, j);
830
7.10M
      }
831
12.7M
    }
832
12.9M
    // Now process all uses.
833
54.2M
    for (unsigned j = 0, n = MI.getNumOperands(); j != n; 
++j41.2M
) {
834
41.2M
      const MachineOperand &MO = MI.getOperand(j);
835
41.2M
      // Only look at use operands.
836
41.2M
      // We do not need to check for MO.readsReg() here because subsequent
837
41.2M
      // subregister defs will get output dependence edges and need no
838
41.2M
      // additional use dependencies.
839
41.2M
      if (!MO.isReg() || 
!MO.isUse()29.6M
)
840
24.3M
        continue;
841
16.9M
      unsigned Reg = MO.getReg();
842
16.9M
      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
843
3.73M
        addPhysRegDeps(SU, j);
844
13.1M
      } else if (TargetRegisterInfo::isVirtualRegister(Reg) && 
MO.readsReg()11.7M
) {
845
11.7M
        addVRegUseDeps(SU, j);
846
11.7M
      }
847
16.9M
    }
848
12.9M
849
12.9M
    // If we haven't seen any uses in this scheduling region, create a
850
12.9M
    // dependence edge to ExitSU to model the live-out latency. This is required
851
12.9M
    // for vreg defs with no in-region use, and prefetches with no vreg def.
852
12.9M
    //
853
12.9M
    // FIXME: NumDataSuccs would be more precise than NumSuccs here. This
854
12.9M
    // check currently relies on being called before adding chain deps.
855
12.9M
    if (SU->NumSuccs == 0 && 
SU->Latency > 17.21M
&&
(1.82M
HasVRegDef1.82M
||
MI.mayLoad()1.11M
)) {
856
761k
      SDep Dep(SU, SDep::Artificial);
857
761k
      Dep.setLatency(SU->Latency - 1);
858
761k
      ExitSU.addPred(Dep);
859
761k
    }
860
12.9M
861
12.9M
    // Add memory dependencies (Note: isStoreToStackSlot and
862
12.9M
    // isLoadFromStackSLot are not usable after stack slots are lowered to
863
12.9M
    // actual addresses).
864
12.9M
865
12.9M
    // This is a barrier event that acts as a pivotal node in the DAG.
866
12.9M
    if (isGlobalMemoryObject(AA, &MI)) {
867
263k
868
263k
      // Become the barrier chain.
869
263k
      if (BarrierChain)
870
135k
        BarrierChain->addPredBarrier(SU);
871
263k
      BarrierChain = SU;
872
263k
873
263k
      LLVM_DEBUG(dbgs() << "Global memory object and new barrier chain: SU("
874
263k
                        << BarrierChain->NodeNum << ").\n";);
875
263k
876
263k
      // Add dependencies against everything below it and clear maps.
877
263k
      addBarrierChain(Stores);
878
263k
      addBarrierChain(Loads);
879
263k
      addBarrierChain(NonAliasStores);
880
263k
      addBarrierChain(NonAliasLoads);
881
263k
      addBarrierChain(FPExceptions);
882
263k
883
263k
      continue;
884
263k
    }
885
12.6M
886
12.6M
    // Instructions that may raise FP exceptions may not be moved
887
12.6M
    // across any global barriers.
888
12.6M
    if (MI.mayRaiseFPException()) {
889
786
      if (BarrierChain)
890
8
        BarrierChain->addPredBarrier(SU);
891
786
892
786
      FPExceptions.insert(SU, UnknownValue);
893
786
894
786
      if (FPExceptions.size() >= HugeRegion) {
895
0
        LLVM_DEBUG(dbgs() << "Reducing FPExceptions map.\n";);
896
0
        Value2SUsMap empty;
897
0
        reduceHugeMemNodeMaps(FPExceptions, empty, getReductionSize());
898
0
      }
899
786
    }
900
12.6M
901
12.6M
    // If it's not a store or a variant load, we're done.
902
12.6M
    if (!MI.mayStore() &&
903
12.6M
        
!(11.4M
MI.mayLoad()11.4M
&&
!MI.isDereferenceableInvariantLoad(AA)1.56M
))
904
10.0M
      continue;
905
2.61M
906
2.61M
    // Always add dependecy edge to BarrierChain if present.
907
2.61M
    if (BarrierChain)
908
52.9k
      BarrierChain->addPredBarrier(SU);
909
2.61M
910
2.61M
    // Find the underlying objects for MI. The Objs vector is either
911
2.61M
    // empty, or filled with the Values of memory locations which this
912
2.61M
    // SU depends on.
913
2.61M
    UnderlyingObjectsVector Objs;
914
2.61M
    bool ObjsFound = getUnderlyingObjectsForInstr(&MI, MFI, Objs,
915
2.61M
                                                  MF.getDataLayout());
916
2.61M
917
2.61M
    if (MI.mayStore()) {
918
1.25M
      if (!ObjsFound) {
919
521k
        // An unknown store depends on all stores and loads.
920
521k
        addChainDependencies(SU, Stores);
921
521k
        addChainDependencies(SU, NonAliasStores);
922
521k
        addChainDependencies(SU, Loads);
923
521k
        addChainDependencies(SU, NonAliasLoads);
924
521k
925
521k
        // Map this store to 'UnknownValue'.
926
521k
        Stores.insert(SU, UnknownValue);
927
729k
      } else {
928
729k
        // Add precise dependencies against all previously seen memory
929
729k
        // accesses mapped to the same Value(s).
930
743k
        for (const UnderlyingObject &UnderlObj : Objs) {
931
743k
          ValueType V = UnderlObj.getValue();
932
743k
          bool ThisMayAlias = UnderlObj.mayAlias();
933
743k
934
743k
          // Add dependencies to previous stores and loads mapped to V.
935
743k
          addChainDependencies(SU, (ThisMayAlias ? 
Stores732k
:
NonAliasStores11.4k
), V);
936
743k
          addChainDependencies(SU, (ThisMayAlias ? 
Loads732k
:
NonAliasLoads11.4k
), V);
937
743k
        }
938
729k
        // Update the store map after all chains have been added to avoid adding
939
729k
        // self-loop edge if multiple underlying objects are present.
940
743k
        for (const UnderlyingObject &UnderlObj : Objs) {
941
743k
          ValueType V = UnderlObj.getValue();
942
743k
          bool ThisMayAlias = UnderlObj.mayAlias();
943
743k
944
743k
          // Map this store to V.
945
743k
          (ThisMayAlias ? 
Stores732k
:
NonAliasStores11.4k
).insert(SU, V);
946
743k
        }
947
729k
        // The store may have dependencies to unanalyzable loads and
948
729k
        // stores.
949
729k
        addChainDependencies(SU, Loads, UnknownValue);
950
729k
        addChainDependencies(SU, Stores, UnknownValue);
951
729k
      }
952
1.36M
    } else { // SU is a load.
953
1.36M
      if (!ObjsFound) {
954
1.00M
        // An unknown load depends on all stores.
955
1.00M
        addChainDependencies(SU, Stores);
956
1.00M
        addChainDependencies(SU, NonAliasStores);
957
1.00M
958
1.00M
        Loads.insert(SU, UnknownValue);
959
1.00M
      } else {
960
363k
        for (const UnderlyingObject &UnderlObj : Objs) {
961
363k
          ValueType V = UnderlObj.getValue();
962
363k
          bool ThisMayAlias = UnderlObj.mayAlias();
963
363k
964
363k
          // Add precise dependencies against all previously seen stores
965
363k
          // mapping to the same Value(s).
966
363k
          addChainDependencies(SU, (ThisMayAlias ? 
Stores350k
:
NonAliasStores13.1k
), V);
967
363k
968
363k
          // Map this load to V.
969
363k
          (ThisMayAlias ? 
Loads350k
:
NonAliasLoads13.1k
).insert(SU, V);
970
363k
        }
971
359k
        // The load may have dependencies to unanalyzable stores.
972
359k
        addChainDependencies(SU, Stores, UnknownValue);
973
359k
      }
974
1.36M
    }
975
2.61M
976
2.61M
    // Reduce maps if they grow huge.
977
2.61M
    if (Stores.size() + Loads.size() >= HugeRegion) {
978
0
      LLVM_DEBUG(dbgs() << "Reducing Stores and Loads maps.\n";);
979
0
      reduceHugeMemNodeMaps(Stores, Loads, getReductionSize());
980
0
    }
981
2.61M
    if (NonAliasStores.size() + NonAliasLoads.size() >= HugeRegion) {
982
0
      LLVM_DEBUG(
983
0
          dbgs() << "Reducing NonAliasStores and NonAliasLoads maps.\n";);
984
0
      reduceHugeMemNodeMaps(NonAliasStores, NonAliasLoads, getReductionSize());
985
0
    }
986
2.61M
  }
987
2.99M
988
2.99M
  if (DbgMI)
989
208
    FirstDbgValue = DbgMI;
990
2.99M
991
2.99M
  Defs.clear();
992
2.99M
  Uses.clear();
993
2.99M
  CurrentVRegDefs.clear();
994
2.99M
  CurrentVRegUses.clear();
995
2.99M
996
2.99M
  Topo.MarkDirty();
997
2.99M
}
998
999
0
raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) {
1000
0
  PSV->printCustom(OS);
1001
0
  return OS;
1002
0
}
1003
1004
0
void ScheduleDAGInstrs::Value2SUsMap::dump() {
1005
0
  for (auto &Itr : *this) {
1006
0
    if (Itr.first.is<const Value*>()) {
1007
0
      const Value *V = Itr.first.get<const Value*>();
1008
0
      if (isa<UndefValue>(V))
1009
0
        dbgs() << "Unknown";
1010
0
      else
1011
0
        V->printAsOperand(dbgs());
1012
0
    }
1013
0
    else if (Itr.first.is<const PseudoSourceValue*>())
1014
0
      dbgs() <<  Itr.first.get<const PseudoSourceValue*>();
1015
0
    else
1016
0
      llvm_unreachable("Unknown Value type.");
1017
0
1018
0
    dbgs() << " : ";
1019
0
    dumpSUList(Itr.second);
1020
0
  }
1021
0
}
1022
1023
void ScheduleDAGInstrs::reduceHugeMemNodeMaps(Value2SUsMap &stores,
1024
0
                                              Value2SUsMap &loads, unsigned N) {
1025
0
  LLVM_DEBUG(dbgs() << "Before reduction:\nStoring SUnits:\n"; stores.dump();
1026
0
             dbgs() << "Loading SUnits:\n"; loads.dump());
1027
0
1028
0
  // Insert all SU's NodeNums into a vector and sort it.
1029
0
  std::vector<unsigned> NodeNums;
1030
0
  NodeNums.reserve(stores.size() + loads.size());
1031
0
  for (auto &I : stores)
1032
0
    for (auto *SU : I.second)
1033
0
      NodeNums.push_back(SU->NodeNum);
1034
0
  for (auto &I : loads)
1035
0
    for (auto *SU : I.second)
1036
0
      NodeNums.push_back(SU->NodeNum);
1037
0
  llvm::sort(NodeNums);
1038
0
1039
0
  // The N last elements in NodeNums will be removed, and the SU with
1040
0
  // the lowest NodeNum of them will become the new BarrierChain to
1041
0
  // let the not yet seen SUs have a dependency to the removed SUs.
1042
0
  assert(N <= NodeNums.size());
1043
0
  SUnit *newBarrierChain = &SUnits[*(NodeNums.end() - N)];
1044
0
  if (BarrierChain) {
1045
0
    // The aliasing and non-aliasing maps reduce independently of each
1046
0
    // other, but share a common BarrierChain. Check if the
1047
0
    // newBarrierChain is above the former one. If it is not, it may
1048
0
    // introduce a loop to use newBarrierChain, so keep the old one.
1049
0
    if (newBarrierChain->NodeNum < BarrierChain->NodeNum) {
1050
0
      BarrierChain->addPredBarrier(newBarrierChain);
1051
0
      BarrierChain = newBarrierChain;
1052
0
      LLVM_DEBUG(dbgs() << "Inserting new barrier chain: SU("
1053
0
                        << BarrierChain->NodeNum << ").\n";);
1054
0
    }
1055
0
    else
1056
0
      LLVM_DEBUG(dbgs() << "Keeping old barrier chain: SU("
1057
0
                        << BarrierChain->NodeNum << ").\n";);
1058
0
  }
1059
0
  else
1060
0
    BarrierChain = newBarrierChain;
1061
0
1062
0
  insertBarrierChain(stores);
1063
0
  insertBarrierChain(loads);
1064
0
1065
0
  LLVM_DEBUG(dbgs() << "After reduction:\nStoring SUnits:\n"; stores.dump();
1066
0
             dbgs() << "Loading SUnits:\n"; loads.dump());
1067
0
}
1068
1069
static void toggleKills(const MachineRegisterInfo &MRI, LivePhysRegs &LiveRegs,
1070
1.11M
                        MachineInstr &MI, bool addToLiveRegs) {
1071
4.90M
  for (MachineOperand &MO : MI.operands()) {
1072
4.90M
    if (!MO.isReg() || 
!MO.readsReg()3.29M
)
1073
2.71M
      continue;
1074
2.19M
    unsigned Reg = MO.getReg();
1075
2.19M
    if (!Reg)
1076
511k
      continue;
1077
1.68M
1078
1.68M
    // Things that are available after the instruction are killed by it.
1079
1.68M
    bool IsKill = LiveRegs.available(MRI, Reg);
1080
1.68M
    MO.setIsKill(IsKill);
1081
1.68M
    if (addToLiveRegs)
1082
1.65M
      LiveRegs.addReg(Reg);
1083
1.68M
  }
1084
1.11M
}
1085
1086
138k
void ScheduleDAGInstrs::fixupKills(MachineBasicBlock &MBB) {
1087
138k
  LLVM_DEBUG(dbgs() << "Fixup kills for " << printMBBReference(MBB) << '\n');
1088
138k
1089
138k
  LiveRegs.init(*TRI);
1090
138k
  LiveRegs.addLiveOuts(MBB);
1091
138k
1092
138k
  // Examine block from end to start...
1093
1.09M
  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
1094
1.09M
    if (MI.isDebugInstr())
1095
302
      continue;
1096
1.09M
1097
1.09M
    // Update liveness.  Registers that are defed but not used in this
1098
1.09M
    // instruction are now dead. Mark register and all subregs as they
1099
1.09M
    // are completely defined.
1100
6.00M
    
for (ConstMIBundleOperands O(MI); 1.09M
O.isValid();
++O4.90M
) {
1101
4.90M
      const MachineOperand &MO = *O;
1102
4.90M
      if (MO.isReg()) {
1103
3.29M
        if (!MO.isDef())
1104
2.23M
          continue;
1105
1.06M
        unsigned Reg = MO.getReg();
1106
1.06M
        if (!Reg)
1107
2
          continue;
1108
1.06M
        LiveRegs.removeReg(Reg);
1109
1.61M
      } else if (MO.isRegMask()) {
1110
42.8k
        LiveRegs.removeRegsInMask(MO);
1111
42.8k
      }
1112
4.90M
    }
1113
1.09M
1114
1.09M
    // If there is a bundle header fix it up first.
1115
1.09M
    if (!MI.isBundled()) {
1116
1.08M
      toggleKills(MRI, LiveRegs, MI, true);
1117
1.08M
    } else {
1118
9.04k
      MachineBasicBlock::instr_iterator Bundle = MI.getIterator();
1119
9.04k
      if (MI.isBundle())
1120
9.04k
        toggleKills(MRI, LiveRegs, MI, false);
1121
9.04k
1122
9.04k
      // Some targets make the (questionable) assumtion that the instructions
1123
9.04k
      // inside the bundle are ordered and consequently only the last use of
1124
9.04k
      // a register inside the bundle can kill it.
1125
9.04k
      MachineBasicBlock::instr_iterator I = std::next(Bundle);
1126
22.3k
      while (I->isBundledWithSucc())
1127
13.2k
        ++I;
1128
22.3k
      do {
1129
22.3k
        if (!I->isDebugInstr())
1130
22.3k
          toggleKills(MRI, LiveRegs, *I, true);
1131
22.3k
        --I;
1132
22.3k
      } while (I != Bundle);
1133
9.04k
    }
1134
1.09M
  }
1135
138k
}
1136
1137
0
void ScheduleDAGInstrs::dumpNode(const SUnit &SU) const {
1138
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1139
  dumpNodeName(SU);
1140
  dbgs() << ": ";
1141
  SU.getInstr()->dump();
1142
#endif
1143
}
1144
1145
0
void ScheduleDAGInstrs::dump() const {
1146
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1147
  if (EntrySU.getInstr() != nullptr)
1148
    dumpNodeAll(EntrySU);
1149
  for (const SUnit &SU : SUnits)
1150
    dumpNodeAll(SU);
1151
  if (ExitSU.getInstr() != nullptr)
1152
    dumpNodeAll(ExitSU);
1153
#endif
1154
}
1155
1156
0
std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
1157
0
  std::string s;
1158
0
  raw_string_ostream oss(s);
1159
0
  if (SU == &EntrySU)
1160
0
    oss << "<entry>";
1161
0
  else if (SU == &ExitSU)
1162
0
    oss << "<exit>";
1163
0
  else
1164
0
    SU->getInstr()->print(oss, /*SkipOpers=*/true);
1165
0
  return oss.str();
1166
0
}
1167
1168
/// Return the basic block label. It is not necessarilly unique because a block
1169
/// contains multiple scheduling regions. But it is fine for visualization.
1170
0
std::string ScheduleDAGInstrs::getDAGName() const {
1171
0
  return "dag." + BB->getFullName();
1172
0
}
1173
1174
50.9k
bool ScheduleDAGInstrs::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
1175
50.9k
  return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
1176
50.9k
}
1177
1178
1.32M
bool ScheduleDAGInstrs::addEdge(SUnit *SuccSU, const SDep &PredDep) {
1179
1.32M
  if (SuccSU != &ExitSU) {
1180
838k
    // Do not use WillCreateCycle, it assumes SD scheduling.
1181
838k
    // If Pred is reachable from Succ, then the edge creates a cycle.
1182
838k
    if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
1183
10.2k
      return false;
1184
828k
    Topo.AddPredQueued(SuccSU, PredDep.getSUnit());
1185
828k
  }
1186
1.32M
  SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
1187
1.31M
  // Return true regardless of whether a new edge needed to be inserted.
1188
1.31M
  return true;
1189
1.32M
}
1190
1191
//===----------------------------------------------------------------------===//
1192
// SchedDFSResult Implementation
1193
//===----------------------------------------------------------------------===//
1194
1195
namespace llvm {
1196
1197
/// Internal state used to compute SchedDFSResult.
1198
class SchedDFSImpl {
1199
  SchedDFSResult &R;
1200
1201
  /// Join DAG nodes into equivalence classes by their subtree.
1202
  IntEqClasses SubtreeClasses;
1203
  /// List PredSU, SuccSU pairs that represent data edges between subtrees.
1204
  std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1205
1206
  struct RootData {
1207
    unsigned NodeID;
1208
    unsigned ParentNodeID;  ///< Parent node (member of the parent subtree).
1209
    unsigned SubInstrCount = 0; ///< Instr count in this tree only, not
1210
                                /// children.
1211
1212
    RootData(unsigned id): NodeID(id),
1213
542
                           ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1214
1215
1.04k
    unsigned getSparseSetIndex() const { return NodeID; }
1216
  };
1217
1218
  SparseSet<RootData> RootSet;
1219
1220
public:
1221
10
  SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) {
1222
10
    RootSet.setUniverse(R.DFSNodeData.size());
1223
10
  }
1224
1225
  /// Returns true if this node been visited by the DFS traversal.
1226
  ///
1227
  /// During visitPostorderNode the Node's SubtreeID is assigned to the Node
1228
  /// ID. Later, SubtreeID is updated but remains valid.
1229
360
  bool isVisited(const SUnit *SU) const {
1230
360
    return R.DFSNodeData[SU->NodeNum].SubtreeID
1231
360
      != SchedDFSResult::InvalidSubtreeID;
1232
360
  }
1233
1234
  /// Initializes this node's instruction count. We don't need to flag the node
1235
  /// visited until visitPostorder because the DAG cannot have cycles.
1236
182
  void visitPreorder(const SUnit *SU) {
1237
182
    R.DFSNodeData[SU->NodeNum].InstrCount =
1238
182
      SU->getInstr()->isTransient() ? 
040
:
1142
;
1239
182
  }
1240
1241
  /// Called once for each node after all predecessors are visited. Revisit this
1242
  /// node's predecessors and potentially join them now that we know the ILP of
1243
  /// the other predecessors.
1244
182
  void visitPostorderNode(const SUnit *SU) {
1245
182
    // Mark this node as the root of a subtree. It may be joined with its
1246
182
    // successors later.
1247
182
    R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum;
1248
182
    RootData RData(SU->NodeNum);
1249
182
    RData.SubInstrCount = SU->getInstr()->isTransient() ? 
040
:
1142
;
1250
182
1251
182
    // If any predecessors are still in their own subtree, they either cannot be
1252
182
    // joined or are large enough to remain separate. If this parent node's
1253
182
    // total instruction count is not greater than a child subtree by at least
1254
182
    // the subtree limit, then try to join it now since splitting subtrees is
1255
182
    // only useful if multiple high-pressure paths are possible.
1256
182
    unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount;
1257
378
    for (const SDep &PredDep : SU->Preds) {
1258
378
      if (PredDep.getKind() != SDep::Data)
1259
200
        continue;
1260
178
      unsigned PredNum = PredDep.getSUnit()->NodeNum;
1261
178
      if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1262
170
        joinPredSubtree(PredDep, SU, /*CheckLimit=*/false);
1263
178
1264
178
      // Either link or merge the TreeData entry from the child to the parent.
1265
178
      if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1266
32
        // If the predecessor's parent is invalid, this is a tree edge and the
1267
32
        // current node is the parent.
1268
32
        if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1269
8
          RootSet[PredNum].ParentNodeID = SU->NodeNum;
1270
32
      }
1271
146
      else if (RootSet.count(PredNum)) {
1272
138
        // The predecessor is not a root, but is still in the root set. This
1273
138
        // must be the new parent that it was just joined to. Note that
1274
138
        // RootSet[PredNum].ParentNodeID may either be invalid or may still be
1275
138
        // set to the original parent.
1276
138
        RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1277
138
        RootSet.erase(PredNum);
1278
138
      }
1279
178
    }
1280
182
    RootSet[SU->NodeNum] = RData;
1281
182
  }
1282
1283
  /// Called once for each tree edge after calling visitPostOrderNode on
1284
  /// the predecessor. Increment the parent node's instruction count and
1285
  /// preemptively join this subtree to its parent's if it is small enough.
1286
146
  void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) {
1287
146
    R.DFSNodeData[Succ->NodeNum].InstrCount
1288
146
      += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount;
1289
146
    joinPredSubtree(PredDep, Succ);
1290
146
  }
1291
1292
  /// Adds a connection for cross edges.
1293
32
  void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) {
1294
32
    ConnectionPairs.push_back(std::make_pair(PredDep.getSUnit(), Succ));
1295
32
  }
1296
1297
  /// Sets each node's subtree ID to the representative ID and record
1298
  /// connections between trees.
1299
10
  void finalize() {
1300
10
    SubtreeClasses.compress();
1301
10
    R.DFSTreeData.resize(SubtreeClasses.getNumClasses());
1302
10
    assert(SubtreeClasses.getNumClasses() == RootSet.size()
1303
10
           && "number of roots should match trees");
1304
44
    for (const RootData &Root : RootSet) {
1305
44
      unsigned TreeID = SubtreeClasses[Root.NodeID];
1306
44
      if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1307
8
        R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1308
44
      R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1309
44
      // Note that SubInstrCount may be greater than InstrCount if we joined
1310
44
      // subtrees across a cross edge. InstrCount will be attributed to the
1311
44
      // original parent, while SubInstrCount will be attributed to the joined
1312
44
      // parent.
1313
44
    }
1314
10
    R.SubtreeConnections.resize(SubtreeClasses.getNumClasses());
1315
10
    R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses());
1316
10
    LLVM_DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n");
1317
192
    for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; 
++Idx182
) {
1318
182
      R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1319
182
      LLVM_DEBUG(dbgs() << "  SU(" << Idx << ") in tree "
1320
182
                        << R.DFSNodeData[Idx].SubtreeID << '\n');
1321
182
    }
1322
32
    for (const std::pair<const SUnit*, const SUnit*> &P : ConnectionPairs) {
1323
32
      unsigned PredTree = SubtreeClasses[P.first->NodeNum];
1324
32
      unsigned SuccTree = SubtreeClasses[P.second->NodeNum];
1325
32
      if (PredTree == SuccTree)
1326
0
        continue;
1327
32
      unsigned Depth = P.first->getDepth();
1328
32
      addConnection(PredTree, SuccTree, Depth);
1329
32
      addConnection(SuccTree, PredTree, Depth);
1330
32
    }
1331
10
  }
1332
1333
protected:
1334
  /// Joins the predecessor subtree with the successor that is its DFS parent.
1335
  /// Applies some heuristics before joining.
1336
  bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ,
1337
316
                       bool CheckLimit = true) {
1338
316
    assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges");
1339
316
1340
316
    // Check if the predecessor is already joined.
1341
316
    const SUnit *PredSU = PredDep.getSUnit();
1342
316
    unsigned PredNum = PredSU->NodeNum;
1343
316
    if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1344
130
      return false;
1345
186
1346
186
    // Four is the magic number of successors before a node is considered a
1347
186
    // pinch point.
1348
186
    unsigned NumDataSucs = 0;
1349
472
    for (const SDep &SuccDep : PredSU->Succs) {
1350
472
      if (SuccDep.getKind() == SDep::Data) {
1351
314
        if (++NumDataSucs >= 4)
1352
40
          return false;
1353
314
      }
1354
472
    }
1355
186
    
if (146
CheckLimit146
&&
R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit138
)
1356
8
      return false;
1357
138
    R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum;
1358
138
    SubtreeClasses.join(Succ->NodeNum, PredNum);
1359
138
    return true;
1360
138
  }
1361
1362
  /// Called by finalize() to record a connection between trees.
1363
64
  void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) {
1364
64
    if (!Depth)
1365
54
      return;
1366
10
1367
10
    do {
1368
10
      SmallVectorImpl<SchedDFSResult::Connection> &Connections =
1369
10
        R.SubtreeConnections[FromTree];
1370
10
      for (SchedDFSResult::Connection &C : Connections) {
1371
2
        if (C.TreeID == ToTree) {
1372
2
          C.Level = std::max(C.Level, Depth);
1373
2
          return;
1374
2
        }
1375
2
      }
1376
10
      Connections.push_back(SchedDFSResult::Connection(ToTree, Depth));
1377
8
      FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1378
8
    } while (FromTree != SchedDFSResult::InvalidSubtreeID);
1379
10
  }
1380
};
1381
1382
} // end namespace llvm
1383
1384
namespace {
1385
1386
/// Manage the stack used by a reverse depth-first search over the DAG.
1387
class SchedDAGReverseDFS {
1388
  std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1389
1390
public:
1391
182
  bool isComplete() const { return DFSStack.empty(); }
1392
1393
182
  void follow(const SUnit *SU) {
1394
182
    DFSStack.push_back(std::make_pair(SU, SU->Preds.begin()));
1395
182
  }
1396
378
  void advance() { ++DFSStack.back().second; }
1397
1398
182
  const SDep *backtrack() {
1399
182
    DFSStack.pop_back();
1400
182
    return DFSStack.empty() ? 
nullptr36
:
std::prev(DFSStack.back().second)146
;
1401
182
  }
1402
1403
920
  const SUnit *getCurr() const { return DFSStack.back().first; }
1404
1405
938
  SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; }
1406
1407
560
  SUnit::const_pred_iterator getPredEnd() const {
1408
560
    return getCurr()->Preds.end();
1409
560
  }
1410
};
1411
1412
} // end anonymous namespace
1413
1414
182
static bool hasDataSucc(const SUnit *SU) {
1415
189
  for (const SDep &SuccDep : SU->Succs) {
1416
189
    if (SuccDep.getKind() == SDep::Data &&
1417
189
        
!SuccDep.getSUnit()->isBoundaryNode()146
)
1418
146
      return true;
1419
189
  }
1420
182
  
return false36
;
1421
182
}
1422
1423
/// Computes an ILP metric for all nodes in the subDAG reachable via depth-first
1424
/// search from this root.
1425
10
void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) {
1426
10
  if (!IsBottomUp)
1427
10
    
llvm_unreachable0
("Top-down ILP metric is unimplemented");
1428
10
1429
10
  SchedDFSImpl Impl(*this);
1430
182
  for (const SUnit &SU : SUnits) {
1431
182
    if (Impl.isVisited(&SU) || hasDataSucc(&SU))
1432
146
      continue;
1433
36
1434
36
    SchedDAGReverseDFS DFS;
1435
36
    Impl.visitPreorder(&SU);
1436
36
    DFS.follow(&SU);
1437
182
    while (true) {
1438
182
      // Traverse the leftmost path as far as possible.
1439
560
      while (DFS.getPred() != DFS.getPredEnd()) {
1440
378
        const SDep &PredDep = *DFS.getPred();
1441
378
        DFS.advance();
1442
378
        // Ignore non-data edges.
1443
378
        if (PredDep.getKind() != SDep::Data
1444
378
            || 
PredDep.getSUnit()->isBoundaryNode()178
) {
1445
200
          continue;
1446
200
        }
1447
178
        // An already visited edge is a cross edge, assuming an acyclic DAG.
1448
178
        if (Impl.isVisited(PredDep.getSUnit())) {
1449
32
          Impl.visitCrossEdge(PredDep, DFS.getCurr());
1450
32
          continue;
1451
32
        }
1452
146
        Impl.visitPreorder(PredDep.getSUnit());
1453
146
        DFS.follow(PredDep.getSUnit());
1454
146
      }
1455
182
      // Visit the top of the stack in postorder and backtrack.
1456
182
      const SUnit *Child = DFS.getCurr();
1457
182
      const SDep *PredDep = DFS.backtrack();
1458
182
      Impl.visitPostorderNode(Child);
1459
182
      if (PredDep)
1460
146
        Impl.visitPostorderEdge(*PredDep, DFS.getCurr());
1461
182
      if (DFS.isComplete())
1462
36
        break;
1463
182
    }
1464
36
  }
1465
10
  Impl.finalize();
1466
10
}
1467
1468
/// The root of the given SubtreeID was just scheduled. For all subtrees
1469
/// connected to this tree, record the depth of the connection so that the
1470
/// nearest connected subtrees can be prioritized.
1471
44
void SchedDFSResult::scheduleTree(unsigned SubtreeID) {
1472
44
  for (const Connection &C : SubtreeConnections[SubtreeID]) {
1473
8
    SubtreeConnectLevels[C.TreeID] =
1474
8
      std::max(SubtreeConnectLevels[C.TreeID], C.Level);
1475
8
    LLVM_DEBUG(dbgs() << "  Tree: " << C.TreeID << " @"
1476
8
                      << SubtreeConnectLevels[C.TreeID] << '\n');
1477
8
  }
1478
44
}
1479
1480
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1481
LLVM_DUMP_METHOD void ILPValue::print(raw_ostream &OS) const {
1482
  OS << InstrCount << " / " << Length << " = ";
1483
  if (!Length)
1484
    OS << "BADILP";
1485
  else
1486
    OS << format("%g", ((double)InstrCount / Length));
1487
}
1488
1489
LLVM_DUMP_METHOD void ILPValue::dump() const {
1490
  dbgs() << *this << '\n';
1491
}
1492
1493
namespace llvm {
1494
1495
LLVM_DUMP_METHOD
1496
raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) {
1497
  Val.print(OS);
1498
  return OS;
1499
}
1500
1501
} // end namespace llvm
1502
1503
#endif