Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveRangeCalc.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LiveRangeCalc.cpp - Calculate live ranges --------------------------===//
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
// Implementation of the LiveRangeCalc class.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "LiveRangeCalc.h"
14
#include "llvm/ADT/BitVector.h"
15
#include "llvm/ADT/STLExtras.h"
16
#include "llvm/ADT/SetVector.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/CodeGen/LiveInterval.h"
19
#include "llvm/CodeGen/MachineBasicBlock.h"
20
#include "llvm/CodeGen/MachineDominators.h"
21
#include "llvm/CodeGen/MachineFunction.h"
22
#include "llvm/CodeGen/MachineInstr.h"
23
#include "llvm/CodeGen/MachineOperand.h"
24
#include "llvm/CodeGen/MachineRegisterInfo.h"
25
#include "llvm/CodeGen/SlotIndexes.h"
26
#include "llvm/CodeGen/TargetRegisterInfo.h"
27
#include "llvm/MC/LaneBitmask.h"
28
#include "llvm/Support/ErrorHandling.h"
29
#include "llvm/Support/raw_ostream.h"
30
#include <algorithm>
31
#include <cassert>
32
#include <iterator>
33
#include <tuple>
34
#include <utility>
35
36
using namespace llvm;
37
38
#define DEBUG_TYPE "regalloc"
39
40
// Reserve an address that indicates a value that is known to be "undef".
41
static VNInfo UndefVNI(0xbad, SlotIndex());
42
43
31.1M
void LiveRangeCalc::resetLiveOutMap() {
44
31.1M
  unsigned NumBlocks = MF->getNumBlockIDs();
45
31.1M
  Seen.clear();
46
31.1M
  Seen.resize(NumBlocks);
47
31.1M
  EntryInfos.clear();
48
31.1M
  Map.resize(NumBlocks);
49
31.1M
}
50
51
void LiveRangeCalc::reset(const MachineFunction *mf,
52
                          SlotIndexes *SI,
53
                          MachineDominatorTree *MDT,
54
18.3M
                          VNInfo::Allocator *VNIA) {
55
18.3M
  MF = mf;
56
18.3M
  MRI = &MF->getRegInfo();
57
18.3M
  Indexes = SI;
58
18.3M
  DomTree = MDT;
59
18.3M
  Alloc = VNIA;
60
18.3M
  resetLiveOutMap();
61
18.3M
  LiveIn.clear();
62
18.3M
}
63
64
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
65
21.4M
                          LiveRange &LR, const MachineOperand &MO) {
66
21.4M
  const MachineInstr &MI = *MO.getParent();
67
21.4M
  SlotIndex DefIdx =
68
21.4M
      Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
69
21.4M
70
21.4M
  // Create the def in LR. This may find an existing def.
71
21.4M
  LR.createDeadDef(DefIdx, Alloc);
72
21.4M
}
73
74
12.8M
void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
75
12.8M
  assert(MRI && Indexes && "call reset() first");
76
12.8M
77
12.8M
  // Step 1: Create minimal live segments for every definition of Reg.
78
12.8M
  // Visit all def operands. If the same instruction has multiple defs of Reg,
79
12.8M
  // createDeadDef() will deduplicate.
80
12.8M
  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
81
12.8M
  unsigned Reg = LI.reg;
82
34.5M
  for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
83
34.5M
    if (!MO.isDef() && 
!MO.readsReg()20.2M
)
84
16.2k
      continue;
85
34.5M
86
34.5M
    unsigned SubReg = MO.getSubReg();
87
34.5M
    if (LI.hasSubRanges() || 
(33.9M
SubReg != 033.9M
&&
TrackSubRegs661k
)) {
88
796k
      LaneBitmask SubMask = SubReg != 0 ? 
TRI.getSubRegIndexLaneMask(SubReg)659k
89
796k
                                        : 
MRI->getMaxLaneMaskForVReg(Reg)136k
;
90
796k
      // If this is the first time we see a subregister def, initialize
91
796k
      // subranges by creating a copy of the main range.
92
796k
      if (!LI.hasSubRanges() && 
!LI.empty()200k
) {
93
93.2k
        LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
94
93.2k
        LI.createSubRangeFrom(*Alloc, ClassMask, LI);
95
93.2k
      }
96
796k
97
796k
      LI.refineSubRanges(*Alloc, SubMask,
98
1.06M
                         [&MO, this](LiveInterval::SubRange &SR) {
99
1.06M
                           if (MO.isDef())
100
312k
                             createDeadDef(*Indexes, *Alloc, SR, MO);
101
1.06M
                         },
102
796k
                         *Indexes, TRI);
103
796k
    }
104
34.5M
105
34.5M
    // Create the def in the main liverange. We do not have to do this if
106
34.5M
    // subranges are tracked as we recreate the main range later in this case.
107
34.5M
    if (MO.isDef() && 
!LI.hasSubRanges()14.3M
)
108
14.0M
      createDeadDef(*Indexes, *Alloc, LI, MO);
109
34.5M
  }
110
12.8M
111
12.8M
  // We may have created empty live ranges for partially undefined uses, we
112
12.8M
  // can't keep them because we won't find defs in them later.
113
12.8M
  LI.removeEmptySubRanges();
114
12.8M
115
12.8M
  // Step 2: Extend live segments to all uses, constructing SSA form as
116
12.8M
  // necessary.
117
12.8M
  if (LI.hasSubRanges()) {
118
586k
    for (LiveInterval::SubRange &S : LI.subranges()) {
119
586k
      LiveRangeCalc SubLRC;
120
586k
      SubLRC.reset(MF, Indexes, DomTree, Alloc);
121
586k
      SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
122
586k
    }
123
200k
    LI.clear();
124
200k
    constructMainRangeFromSubranges(LI);
125
12.6M
  } else {
126
12.6M
    resetLiveOutMap();
127
12.6M
    extendToUses(LI, Reg, LaneBitmask::getAll());
128
12.6M
  }
129
12.8M
}
130
131
201k
void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
132
201k
  // First create dead defs at all defs found in subranges.
133
201k
  LiveRange &MainRange = LI;
134
201k
  assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
135
201k
         "Expect empty main liverange");
136
201k
137
588k
  for (const LiveInterval::SubRange &SR : LI.subranges()) {
138
597k
    for (const VNInfo *VNI : SR.valnos) {
139
597k
      if (!VNI->isUnused() && 
!VNI->isPHIDef()597k
)
140
596k
        MainRange.createDeadDef(VNI->def, *Alloc);
141
597k
    }
142
588k
  }
143
201k
  resetLiveOutMap();
144
201k
  extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI);
145
201k
}
146
147
2.10M
void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
148
2.10M
  assert(MRI && Indexes && "call reset() first");
149
2.10M
150
2.10M
  // Visit all def operands. If the same instruction has multiple defs of Reg,
151
2.10M
  // LR.createDeadDef() will deduplicate.
152
2.10M
  for (MachineOperand &MO : MRI->def_operands(Reg))
153
7.06M
    createDeadDef(*Indexes, *Alloc, LR, MO);
154
2.10M
}
155
156
void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
157
15.5M
                                 LiveInterval *LI) {
158
15.5M
  SmallVector<SlotIndex, 4> Undefs;
159
15.5M
  if (LI != nullptr)
160
787k
    LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
161
15.5M
162
15.5M
  // Visit all operands that read Reg. This may include partial defs.
163
15.5M
  bool IsSubRange = !Mask.all();
164
15.5M
  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
165
51.1M
  for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
166
51.1M
    // Clear all kill flags. They will be reinserted after register allocation
167
51.1M
    // by LiveIntervals::addKillFlags().
168
51.1M
    if (MO.isUse())
169
28.8M
      MO.setIsKill(false);
170
51.1M
    // MO::readsReg returns "true" for subregister defs. This is for keeping
171
51.1M
    // liveness of the entire register (i.e. for the main range of the live
172
51.1M
    // interval). For subranges, definitions of non-overlapping subregisters
173
51.1M
    // do not count as uses.
174
51.1M
    if (!MO.readsReg() || 
(29.8M
IsSubRange29.8M
&&
MO.isDef()2.68M
))
175
22.0M
      continue;
176
29.0M
177
29.0M
    unsigned SubReg = MO.getSubReg();
178
29.0M
    if (SubReg != 0) {
179
2.36M
      LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
180
2.36M
      if (MO.isDef())
181
210k
        SLM = ~SLM;
182
2.36M
      // Ignore uses not reading the current (sub)range.
183
2.36M
      if ((SLM & Mask).none())
184
1.13M
        continue;
185
27.8M
    }
186
27.8M
187
27.8M
    // Determine the actual place of the use.
188
27.8M
    const MachineInstr *MI = MO.getParent();
189
27.8M
    unsigned OpNo = (&MO - &MI->getOperand(0));
190
27.8M
    SlotIndex UseIdx;
191
27.8M
    if (MI->isPHI()) {
192
14.2k
      assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
193
14.2k
      // The actual place where a phi operand is used is the end of the pred
194
14.2k
      // MBB. PHI operands are paired: (Reg, PredMBB).
195
14.2k
      UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
196
27.8M
    } else {
197
27.8M
      // Check for early-clobber redefs.
198
27.8M
      bool isEarlyClobber = false;
199
27.8M
      unsigned DefIdx;
200
27.8M
      if (MO.isDef())
201
210k
        isEarlyClobber = MO.isEarlyClobber();
202
27.6M
      else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
203
407k
        // FIXME: This would be a lot easier if tied early-clobber uses also
204
407k
        // had an early-clobber flag.
205
407k
        isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
206
407k
      }
207
27.8M
      UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
208
27.8M
    }
209
27.8M
210
27.8M
    // MI is reading Reg. We may have visited MI before if it happens to be
211
27.8M
    // reading Reg multiple times. That is OK, extend() is idempotent.
212
27.8M
    extend(LR, UseIdx, Reg, Undefs);
213
27.8M
  }
214
15.5M
}
215
216
989k
void LiveRangeCalc::updateFromLiveIns() {
217
989k
  LiveRangeUpdater Updater;
218
2.46M
  for (const LiveInBlock &I : LiveIn) {
219
2.46M
    if (!I.DomNode)
220
820k
      continue;
221
1.64M
    MachineBasicBlock *MBB = I.DomNode->getBlock();
222
1.64M
    assert(I.Value && "No live-in value found");
223
1.64M
    SlotIndex Start, End;
224
1.64M
    std::tie(Start, End) = Indexes->getMBBRange(MBB);
225
1.64M
226
1.64M
    if (I.Kill.isValid())
227
106k
      // Value is killed inside this block.
228
106k
      End = I.Kill;
229
1.54M
    else {
230
1.54M
      // The value is live-through, update LiveOut as well.
231
1.54M
      // Defer the Domtree lookup until it is needed.
232
1.54M
      assert(Seen.test(MBB->getNumber()));
233
1.54M
      Map[MBB] = LiveOutPair(I.Value, nullptr);
234
1.54M
    }
235
1.64M
    Updater.setDest(&I.LR);
236
1.64M
    Updater.add(Start, End, I.Value);
237
1.64M
  }
238
989k
  LiveIn.clear();
239
989k
}
240
241
void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
242
28.7M
                           ArrayRef<SlotIndex> Undefs) {
243
28.7M
  assert(Use.isValid() && "Invalid SlotIndex");
244
28.7M
  assert(Indexes && "Missing SlotIndexes");
245
28.7M
  assert(DomTree && "Missing dominator tree");
246
28.7M
247
28.7M
  MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
248
28.7M
  assert(UseMBB && "No MBB at Use");
249
28.7M
250
28.7M
  // Is there a def in the same MBB we can extend?
251
28.7M
  auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
252
28.7M
  if (EP.first != nullptr || 
EP.second4.09M
)
253
24.6M
    return;
254
4.09M
255
4.09M
  // Find the single reaching def, or determine if Use is jointly dominated by
256
4.09M
  // multiple values, and we may need to create even more phi-defs to preserve
257
4.09M
  // VNInfo SSA form.  Perform a search for all predecessor blocks where we
258
4.09M
  // know the dominating VNInfo.
259
4.09M
  if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
260
3.42M
    return;
261
668k
262
668k
  // When there were multiple different values, we may need new PHIs.
263
668k
  calculateValues();
264
668k
}
265
266
// This function is called by a client after using the low-level API to add
267
// live-out and live-in blocks.  The unique value optimization is not
268
// available, SplitEditor::transferValues handles that case directly anyway.
269
989k
void LiveRangeCalc::calculateValues() {
270
989k
  assert(Indexes && "Missing SlotIndexes");
271
989k
  assert(DomTree && "Missing dominator tree");
272
989k
  updateSSA();
273
989k
  updateFromLiveIns();
274
989k
}
275
276
bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
277
                                 MachineBasicBlock &MBB, BitVector &DefOnEntry,
278
1.02k
                                 BitVector &UndefOnEntry) {
279
1.02k
  unsigned BN = MBB.getNumber();
280
1.02k
  if (DefOnEntry[BN])
281
197
    return true;
282
824
  if (UndefOnEntry[BN])
283
1
    return false;
284
823
285
823
  auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
286
819
    for (MachineBasicBlock *S : B.successors())
287
1.34k
      DefOnEntry[S->getNumber()] = true;
288
819
    DefOnEntry[BN] = true;
289
819
    return true;
290
819
  };
291
823
292
823
  SetVector<unsigned> WorkList;
293
823
  // Checking if the entry of MBB is reached by some def: add all predecessors
294
823
  // that are potentially defined-on-exit to the work list.
295
823
  for (MachineBasicBlock *P : MBB.predecessors())
296
1.46k
    WorkList.insert(P->getNumber());
297
823
298
968
  for (unsigned i = 0; i != WorkList.size(); 
++i145
) {
299
964
    // Determine if the exit from the block is reached by some def.
300
964
    unsigned N = WorkList[i];
301
964
    MachineBasicBlock &B = *MF->getBlockNumbered(N);
302
964
    if (Seen[N]) {
303
964
      const LiveOutPair &LOB = Map[&B];
304
964
      if (LOB.first != nullptr && 
LOB.first != &UndefVNI668
)
305
663
        return MarkDefined(B);
306
301
    }
307
301
    SlotIndex Begin, End;
308
301
    std::tie(Begin, End) = Indexes->getMBBRange(&B);
309
301
    // Treat End as not belonging to B.
310
301
    // If LR has a segment S that starts at the next block, i.e. [End, ...),
311
301
    // std::upper_bound will return the segment following S. Instead,
312
301
    // S should be treated as the first segment that does not overlap B.
313
301
    LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
314
301
                                              End.getPrevSlot());
315
301
    if (UB != LR.begin()) {
316
294
      LiveRange::Segment &Seg = *std::prev(UB);
317
294
      if (Seg.end > Begin) {
318
0
        // There is a segment that overlaps B. If the range is not explicitly
319
0
        // undefined between the end of the segment and the end of the block,
320
0
        // treat the block as defined on exit. If it is, go to the next block
321
0
        // on the work list.
322
0
        if (LR.isUndefIn(Undefs, Seg.end, End))
323
0
          continue;
324
0
        return MarkDefined(B);
325
0
      }
326
294
    }
327
301
328
301
    // No segment overlaps with this block. If this block is not defined on
329
301
    // entry, or it undefines the range, do not process its predecessors.
330
301
    if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
331
5
      UndefOnEntry[N] = true;
332
5
      continue;
333
5
    }
334
296
    if (DefOnEntry[N])
335
156
      return MarkDefined(B);
336
140
337
140
    // Still don't know: add all predecessors to the work list.
338
140
    for (MachineBasicBlock *P : B.predecessors())
339
266
      WorkList.insert(P->getNumber());
340
140
  }
341
823
342
823
  UndefOnEntry[BN] = true;
343
4
  return false;
344
823
}
345
346
bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
347
                                     SlotIndex Use, unsigned PhysReg,
348
4.09M
                                     ArrayRef<SlotIndex> Undefs) {
349
4.09M
  unsigned UseMBBNum = UseMBB.getNumber();
350
4.09M
351
4.09M
  // Block numbers where LR should be live-in.
352
4.09M
  SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
353
4.09M
354
4.09M
  // Remember if we have seen more than one value.
355
4.09M
  bool UniqueVNI = true;
356
4.09M
  VNInfo *TheVNI = nullptr;
357
4.09M
358
4.09M
  bool FoundUndef = false;
359
4.09M
360
4.09M
  // Using Seen as a visited set, perform a BFS for all reaching defs.
361
31.9M
  for (unsigned i = 0; i != WorkList.size(); 
++i27.8M
) {
362
27.8M
    MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
363
27.8M
364
#ifndef NDEBUG
365
    if (MBB->pred_empty()) {
366
      MBB->getParent()->verify();
367
      errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())
368
             << " does not have a corresponding definition on every path:\n";
369
      const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
370
      if (MI != nullptr)
371
        errs() << Use << " " << *MI;
372
      report_fatal_error("Use not jointly dominated by defs.");
373
    }
374
375
    if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
376
        !MBB->isLiveIn(PhysReg)) {
377
      MBB->getParent()->verify();
378
      const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
379
      errs() << "The register " << printReg(PhysReg, TRI)
380
             << " needs to be live in to " << printMBBReference(*MBB)
381
             << ", but is missing from the live-in list.\n";
382
      report_fatal_error("Invalid global physical register");
383
    }
384
#endif
385
    FoundUndef |= MBB->pred_empty();
386
27.8M
387
41.1M
    for (MachineBasicBlock *Pred : MBB->predecessors()) {
388
41.1M
       // Is this a known live-out block?
389
41.1M
       if (Seen.test(Pred->getNumber())) {
390
12.3M
         if (VNInfo *VNI = Map[Pred].first) {
391
1.87M
           if (TheVNI && 
TheVNI != VNI948k
)
392
15.0k
             UniqueVNI = false;
393
1.87M
           TheVNI = VNI;
394
1.87M
         }
395
12.3M
         continue;
396
12.3M
       }
397
28.8M
398
28.8M
       SlotIndex Start, End;
399
28.8M
       std::tie(Start, End) = Indexes->getMBBRange(Pred);
400
28.8M
401
28.8M
       // First time we see Pred.  Try to determine the live-out value, but set
402
28.8M
       // it as null if Pred is live-through with an unknown value.
403
28.8M
       auto EP = LR.extendInBlock(Undefs, Start, End);
404
28.8M
       VNInfo *VNI = EP.first;
405
28.8M
       FoundUndef |= EP.second;
406
28.8M
       setLiveOutValue(Pred, EP.second ? 
&UndefVNI7
:
VNI28.8M
);
407
28.8M
       if (VNI) {
408
4.34M
         if (TheVNI && 
TheVNI != VNI1.17M
)
409
962k
           UniqueVNI = false;
410
4.34M
         TheVNI = VNI;
411
4.34M
       }
412
28.8M
       if (VNI || 
EP.second24.5M
)
413
4.34M
         continue;
414
24.5M
415
24.5M
       // No, we need a live-in value for Pred as well
416
24.5M
       if (Pred != &UseMBB)
417
23.7M
         WorkList.push_back(Pred->getNumber());
418
729k
       else
419
729k
          // Loopback to UseMBB, so value is really live through.
420
729k
         Use = SlotIndex();
421
24.5M
    }
422
27.8M
  }
423
4.09M
424
4.09M
  LiveIn.clear();
425
4.09M
  FoundUndef |= (TheVNI == nullptr || 
TheVNI == &UndefVNI4.09M
);
426
4.09M
  if (!Undefs.empty() && 
FoundUndef3.45k
)
427
8
    UniqueVNI = false;
428
4.09M
429
4.09M
  // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
430
4.09M
  // neither require it. Skip the sorting overhead for small updates.
431
4.09M
  if (WorkList.size() > 4)
432
980k
    array_pod_sort(WorkList.begin(), WorkList.end());
433
4.09M
434
4.09M
  // If a unique reaching def was found, blit in the live ranges immediately.
435
4.09M
  if (UniqueVNI) {
436
3.42M
    assert(TheVNI != nullptr && TheVNI != &UndefVNI);
437
3.42M
    LiveRangeUpdater Updater(&LR);
438
26.5M
    for (unsigned BN : WorkList) {
439
26.5M
      SlotIndex Start, End;
440
26.5M
      std::tie(Start, End) = Indexes->getMBBRange(BN);
441
26.5M
      // Trim the live range in UseMBB.
442
26.5M
      if (BN == UseMBBNum && 
Use.isValid()3.42M
)
443
2.71M
        End = Use;
444
23.8M
      else
445
23.8M
        Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
446
26.5M
      Updater.add(Start, End, TheVNI);
447
26.5M
    }
448
3.42M
    return true;
449
3.42M
  }
450
668k
451
668k
  // Prepare the defined/undefined bit vectors.
452
668k
  EntryInfoMap::iterator Entry;
453
668k
  bool DidInsert;
454
668k
  std::tie(Entry, DidInsert) = EntryInfos.insert(
455
668k
      std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
456
668k
  if (DidInsert) {
457
660k
    // Initialize newly inserted entries.
458
660k
    unsigned N = MF->getNumBlockIDs();
459
660k
    Entry->second.first.resize(N);
460
660k
    Entry->second.second.resize(N);
461
660k
  }
462
668k
  BitVector &DefOnEntry = Entry->second.first;
463
668k
  BitVector &UndefOnEntry = Entry->second.second;
464
668k
465
668k
  // Multiple values were found, so transfer the work list to the LiveIn array
466
668k
  // where UpdateSSA will use it as a work list.
467
668k
  LiveIn.reserve(WorkList.size());
468
1.33M
  for (unsigned BN : WorkList) {
469
1.33M
    MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
470
1.33M
    if (!Undefs.empty() &&
471
1.33M
        
!isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry)1.02k
)
472
5
      continue;
473
1.33M
    addLiveInBlock(LR, DomTree->getNode(MBB));
474
1.33M
    if (MBB == &UseMBB)
475
668k
      LiveIn.back().Kill = Use;
476
1.33M
  }
477
668k
478
668k
  return false;
479
668k
}
480
481
// This is essentially the same iterative algorithm that SSAUpdater uses,
482
// except we already have a dominator tree, so we don't have to recompute it.
483
989k
void LiveRangeCalc::updateSSA() {
484
989k
  assert(Indexes && "Missing SlotIndexes");
485
989k
  assert(DomTree && "Missing dominator tree");
486
989k
487
989k
  // Interate until convergence.
488
989k
  bool Changed;
489
1.78M
  do {
490
1.78M
    Changed = false;
491
1.78M
    // Propagate live-out values down the dominator tree, inserting phi-defs
492
1.78M
    // when necessary.
493
6.68M
    for (LiveInBlock &I : LiveIn) {
494
6.68M
      MachineDomTreeNode *Node = I.DomNode;
495
6.68M
      // Skip block if the live-in value has already been determined.
496
6.68M
      if (!Node)
497
955k
        continue;
498
5.72M
      MachineBasicBlock *MBB = Node->getBlock();
499
5.72M
      MachineDomTreeNode *IDom = Node->getIDom();
500
5.72M
      LiveOutPair IDomValue;
501
5.72M
502
5.72M
      // We need a live-in value to a block with no immediate dominator?
503
5.72M
      // This is probably an unreachable block that has survived somehow.
504
5.72M
      bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
505
5.72M
506
5.72M
      // IDom dominates all of our predecessors, but it may not be their
507
5.72M
      // immediate dominator. Check if any of them have live-out values that are
508
5.72M
      // properly dominated by IDom. If so, we need a phi-def here.
509
5.72M
      if (!needPHI) {
510
5.45M
        IDomValue = Map[IDom->getBlock()];
511
5.45M
512
5.45M
        // Cache the DomTree node that defined the value.
513
5.45M
        if (IDomValue.first && 
IDomValue.first != &UndefVNI5.32M
&&
514
5.45M
            
!IDomValue.second5.32M
) {
515
520k
          Map[IDom->getBlock()].second = IDomValue.second =
516
520k
            DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
517
520k
        }
518
5.45M
519
7.93M
        for (MachineBasicBlock *Pred : MBB->predecessors()) {
520
7.93M
          LiveOutPair &Value = Map[Pred];
521
7.93M
          if (!Value.first || 
Value.first == IDomValue.first7.44M
)
522
7.34M
            continue;
523
589k
          if (Value.first == &UndefVNI) {
524
1
            needPHI = true;
525
1
            break;
526
1
          }
527
589k
528
589k
          // Cache the DomTree node that defined the value.
529
589k
          if (!Value.second)
530
451k
            Value.second =
531
451k
              DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
532
589k
533
589k
          // This predecessor is carrying something other than IDomValue.
534
589k
          // It could be because IDomValue hasn't propagated yet, or it could be
535
589k
          // because MBB is in the dominance frontier of that value.
536
589k
          if (DomTree->dominates(IDom, Value.second)) {
537
543k
            needPHI = true;
538
543k
            break;
539
543k
          }
540
589k
        }
541
5.45M
      }
542
5.72M
543
5.72M
      // The value may be live-through even if Kill is set, as can happen when
544
5.72M
      // we are called from extendRange. In that case LiveOutSeen is true, and
545
5.72M
      // LiveOut indicates a foreign or missing value.
546
5.72M
      LiveOutPair &LOP = Map[MBB];
547
5.72M
548
5.72M
      // Create a phi-def if required.
549
5.72M
      if (needPHI) {
550
820k
        Changed = true;
551
820k
        assert(Alloc && "Need VNInfo allocator to create PHI-defs");
552
820k
        SlotIndex Start, End;
553
820k
        std::tie(Start, End) = Indexes->getMBBRange(MBB);
554
820k
        LiveRange &LR = I.LR;
555
820k
        VNInfo *VNI = LR.getNextValue(Start, *Alloc);
556
820k
        I.Value = VNI;
557
820k
        // This block is done, we know the final value.
558
820k
        I.DomNode = nullptr;
559
820k
560
820k
        // Add liveness since updateFromLiveIns now skips this node.
561
820k
        if (I.Kill.isValid()) {
562
670k
          if (VNI)
563
670k
            LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
564
670k
        } else {
565
150k
          if (VNI)
566
150k
            LR.addSegment(LiveInterval::Segment(Start, End, VNI));
567
150k
          LOP = LiveOutPair(VNI, Node);
568
150k
        }
569
4.90M
      } else if (IDomValue.first && 
IDomValue.first != &UndefVNI4.79M
) {
570
4.79M
        // No phi-def here. Remember incoming value.
571
4.79M
        I.Value = IDomValue.first;
572
4.79M
573
4.79M
        // If the IDomValue is killed in the block, don't propagate through.
574
4.79M
        if (I.Kill.isValid())
575
260k
          continue;
576
4.53M
577
4.53M
        // Propagate IDomValue if it isn't killed:
578
4.53M
        // MBB is live-out and doesn't define its own value.
579
4.53M
        if (LOP.first == IDomValue.first)
580
2.56M
          continue;
581
1.96M
        Changed = true;
582
1.96M
        LOP = IDomValue;
583
1.96M
      }
584
5.72M
    }
585
1.78M
  } while (Changed);
586
989k
}
587
588
bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB,
589
                                       ArrayRef<SlotIndex> Defs,
590
0
                                       const SlotIndexes &Indexes) {
591
0
  const MachineFunction &MF = *MBB->getParent();
592
0
  BitVector DefBlocks(MF.getNumBlockIDs());
593
0
  for (SlotIndex I : Defs)
594
0
    DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());
595
0
596
0
  SetVector<unsigned> PredQueue;
597
0
  PredQueue.insert(MBB->getNumber());
598
0
  for (unsigned i = 0; i != PredQueue.size(); ++i) {
599
0
    unsigned BN = PredQueue[i];
600
0
    if (DefBlocks[BN])
601
0
      return true;
602
0
    const MachineBasicBlock *B = MF.getBlockNumbered(BN);
603
0
    for (const MachineBasicBlock *P : B->predecessors())
604
0
      PredQueue.insert(P->getNumber());
605
0
  }
606
0
  return false;
607
0
}