Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/MemorySSAUpdater.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
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
// This file implements the MemorySSAUpdater class.
10
//
11
//===----------------------------------------------------------------===//
12
#include "llvm/Analysis/MemorySSAUpdater.h"
13
#include "llvm/ADT/STLExtras.h"
14
#include "llvm/ADT/SetVector.h"
15
#include "llvm/ADT/SmallPtrSet.h"
16
#include "llvm/Analysis/IteratedDominanceFrontier.h"
17
#include "llvm/Analysis/MemorySSA.h"
18
#include "llvm/IR/DataLayout.h"
19
#include "llvm/IR/Dominators.h"
20
#include "llvm/IR/GlobalVariable.h"
21
#include "llvm/IR/IRBuilder.h"
22
#include "llvm/IR/LLVMContext.h"
23
#include "llvm/IR/Metadata.h"
24
#include "llvm/IR/Module.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/FormattedStream.h"
27
#include <algorithm>
28
29
#define DEBUG_TYPE "memoryssa"
30
using namespace llvm;
31
32
// This is the marker algorithm from "Simple and Efficient Construction of
33
// Static Single Assignment Form"
34
// The simple, non-marker algorithm places phi nodes at any join
35
// Here, we place markers, and only place phi nodes if they end up necessary.
36
// They are only necessary if they break a cycle (IE we recursively visit
37
// ourselves again), or we discover, while getting the value of the operands,
38
// that there are two or more definitions needing to be merged.
39
// This still will leave non-minimal form in the case of irreducible control
40
// flow, where phi nodes may be in cycles with themselves, but unnecessary.
41
MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(
42
    BasicBlock *BB,
43
267
    DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
44
267
  // First, do a cache lookup. Without this cache, certain CFG structures
45
267
  // (like a series of if statements) take exponential time to visit.
46
267
  auto Cached = CachedPreviousDef.find(BB);
47
267
  if (Cached != CachedPreviousDef.end()) {
48
12
    return Cached->second;
49
12
  }
50
255
51
255
  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
52
120
    // Single predecessor case, just recurse, we can only have one definition.
53
120
    MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);
54
120
    CachedPreviousDef.insert({BB, Result});
55
120
    return Result;
56
120
  }
57
135
58
135
  if (VisitedBlocks.count(BB)) {
59
8
    // We hit our node again, meaning we had a cycle, we must insert a phi
60
8
    // node to break it so we have an operand. The only case this will
61
8
    // insert useless phis is if we have irreducible control flow.
62
8
    MemoryAccess *Result = MSSA->createMemoryPhi(BB);
63
8
    CachedPreviousDef.insert({BB, Result});
64
8
    return Result;
65
8
  }
66
127
67
127
  if (VisitedBlocks.insert(BB).second) {
68
127
    // Mark us visited so we can detect a cycle
69
127
    SmallVector<TrackingVH<MemoryAccess>, 8> PhiOps;
70
127
71
127
    // Recurse to get the values in our predecessors for placement of a
72
127
    // potential phi node. This will insert phi nodes if we cycle in order to
73
127
    // break the cycle and have an operand.
74
127
    for (auto *Pred : predecessors(BB))
75
44
      if (MSSA->DT->isReachableFromEntry(Pred))
76
44
        PhiOps.push_back(getPreviousDefFromEnd(Pred, CachedPreviousDef));
77
0
      else
78
0
        PhiOps.push_back(MSSA->getLiveOnEntryDef());
79
127
80
127
    // Now try to simplify the ops to avoid placing a phi.
81
127
    // This may return null if we never created a phi yet, that's okay
82
127
    MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
83
127
84
127
    // See if we can avoid the phi by simplifying it.
85
127
    auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
86
127
    // If we couldn't simplify, we may have to create a phi
87
127
    if (Result == Phi) {
88
3
      if (!Phi)
89
2
        Phi = MSSA->createMemoryPhi(BB);
90
3
91
3
      // See if the existing phi operands match what we need.
92
3
      // Unlike normal SSA, we only allow one phi node per block, so we can't just
93
3
      // create a new one.
94
3
      if (Phi->getNumOperands() != 0) {
95
0
        // FIXME: Figure out whether this is dead code and if so remove it.
96
0
        if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
97
0
          // These will have been filled in by the recursive read we did above.
98
0
          llvm::copy(PhiOps, Phi->op_begin());
99
0
          std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
100
0
        }
101
3
      } else {
102
3
        unsigned i = 0;
103
3
        for (auto *Pred : predecessors(BB))
104
6
          Phi->addIncoming(&*PhiOps[i++], Pred);
105
3
        InsertedPHIs.push_back(Phi);
106
3
      }
107
3
      Result = Phi;
108
3
    }
109
127
110
127
    // Set ourselves up for the next variable by resetting visited state.
111
127
    VisitedBlocks.erase(BB);
112
127
    CachedPreviousDef.insert({BB, Result});
113
127
    return Result;
114
127
  }
115
0
  llvm_unreachable("Should have hit one of the three cases above");
116
0
}
117
118
// This starts at the memory access, and goes backwards in the block to find the
119
// previous definition. If a definition is not found the block of the access,
120
// it continues globally, creating phi nodes to ensure we have a single
121
// definition.
122
175
MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
123
175
  if (auto *LocalResult = getPreviousDefInBlock(MA))
124
34
    return LocalResult;
125
141
  DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
126
141
  return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);
127
141
}
128
129
// This starts at the memory access, and goes backwards in the block to the find
130
// the previous definition. If the definition is not found in the block of the
131
// access, it returns nullptr.
132
175
MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
133
175
  auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
134
175
135
175
  // It's possible there are no defs, or we got handed the first def to start.
136
175
  if (Defs) {
137
96
    // If this is a def, we can just use the def iterators.
138
96
    if (!isa<MemoryUse>(MA)) {
139
62
      auto Iter = MA->getReverseDefsIterator();
140
62
      ++Iter;
141
62
      if (Iter != Defs->rend())
142
11
        return &*Iter;
143
34
    } else {
144
34
      // Otherwise, have to walk the all access iterator.
145
34
      auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
146
34
      for (auto &U : make_range(++MA->getReverseIterator(), End))
147
62
        if (!isa<MemoryUse>(U))
148
23
          return cast<MemoryAccess>(&U);
149
34
      // Note that if MA comes before Defs->begin(), we won't hit a def.
150
34
      
return nullptr11
;
151
130
    }
152
96
  }
153
130
  return nullptr;
154
130
}
155
156
// This starts at the end of block
157
MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
158
    BasicBlock *BB,
159
168
    DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
160
168
  auto *Defs = MSSA->getWritableBlockDefs(BB);
161
168
162
168
  if (Defs) {
163
42
    CachedPreviousDef.insert({BB, &*Defs->rbegin()});
164
42
    return &*Defs->rbegin();
165
42
  }
166
126
167
126
  return getPreviousDefRecursive(BB, CachedPreviousDef);
168
126
}
169
// Recurse over a set of phi uses to eliminate the trivial ones
170
311
MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
171
311
  if (!Phi)
172
0
    return nullptr;
173
311
  TrackingVH<MemoryAccess> Res(Phi);
174
311
  SmallVector<TrackingVH<Value>, 8> Uses;
175
311
  std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
176
755
  for (auto &U : Uses) {
177
755
    if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U)) {
178
263
      auto OperRange = UsePhi->operands();
179
263
      tryRemoveTrivialPhi(UsePhi, OperRange);
180
263
    }
181
755
  }
182
311
  return Res;
183
311
}
184
185
// Eliminate trivial phis
186
// Phis are trivial if they are defined either by themselves, or all the same
187
// argument.
188
// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
189
// We recursively try to remove them.
190
template <class RangeType>
191
MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
192
1.25k
                                                    RangeType &Operands) {
193
1.25k
  // Bail out on non-opt Phis.
194
1.25k
  if (NonOptPhis.count(Phi))
195
5
    return Phi;
196
1.25k
197
1.25k
  // Detect equal or self arguments
198
1.25k
  MemoryAccess *Same = nullptr;
199
2.33k
  for (auto &Op : Operands) {
200
2.33k
    // If the same or self, good so far
201
2.33k
    if (Op == Phi || 
Op == Same2.30k
)
202
349
      continue;
203
1.98k
    // not the same, return the phi since it's not eliminatable by us
204
1.98k
    if (Same)
205
838
      return Phi;
206
1.14k
    Same = cast<MemoryAccess>(&*Op);
207
1.14k
  }
208
1.25k
  // Never found a non-self reference, the phi is undef
209
1.25k
  
if (416
Same == nullptr416
)
210
105
    return MSSA->getLiveOnEntryDef();
211
311
  if (Phi) {
212
299
    Phi->replaceAllUsesWith(Same);
213
299
    removeMemoryAccess(Phi);
214
299
  }
215
311
216
311
  // We should only end up recursing in case we replaced something, in which
217
311
  // case, we may have made other Phis trivial.
218
311
  return recursePhi(Same);
219
311
}
llvm::MemoryAccess* llvm::MemorySSAUpdater::tryRemoveTrivialPhi<llvm::SmallVector<llvm::TrackingVH<llvm::MemoryAccess>, 8u> >(llvm::MemoryPhi*, llvm::SmallVector<llvm::TrackingVH<llvm::MemoryAccess>, 8u>&)
Line
Count
Source
192
127
                                                    RangeType &Operands) {
193
127
  // Bail out on non-opt Phis.
194
127
  if (NonOptPhis.count(Phi))
195
0
    return Phi;
196
127
197
127
  // Detect equal or self arguments
198
127
  MemoryAccess *Same = nullptr;
199
127
  for (auto &Op : Operands) {
200
44
    // If the same or self, good so far
201
44
    if (Op == Phi || 
Op == Same37
)
202
19
      continue;
203
25
    // not the same, return the phi since it's not eliminatable by us
204
25
    if (Same)
205
3
      return Phi;
206
22
    Same = cast<MemoryAccess>(&*Op);
207
22
  }
208
127
  // Never found a non-self reference, the phi is undef
209
127
  
if (124
Same == nullptr124
)
210
105
    return MSSA->getLiveOnEntryDef();
211
19
  if (Phi) {
212
7
    Phi->replaceAllUsesWith(Same);
213
7
    removeMemoryAccess(Phi);
214
7
  }
215
19
216
19
  // We should only end up recursing in case we replaced something, in which
217
19
  // case, we may have made other Phis trivial.
218
19
  return recursePhi(Same);
219
19
}
llvm::MemoryAccess* llvm::MemorySSAUpdater::tryRemoveTrivialPhi<llvm::iterator_range<llvm::Use*> >(llvm::MemoryPhi*, llvm::iterator_range<llvm::Use*>&)
Line
Count
Source
192
1.13k
                                                    RangeType &Operands) {
193
1.13k
  // Bail out on non-opt Phis.
194
1.13k
  if (NonOptPhis.count(Phi))
195
5
    return Phi;
196
1.12k
197
1.12k
  // Detect equal or self arguments
198
1.12k
  MemoryAccess *Same = nullptr;
199
2.29k
  for (auto &Op : Operands) {
200
2.29k
    // If the same or self, good so far
201
2.29k
    if (Op == Phi || 
Op == Same2.27k
)
202
330
      continue;
203
1.96k
    // not the same, return the phi since it's not eliminatable by us
204
1.96k
    if (Same)
205
835
      return Phi;
206
1.12k
    Same = cast<MemoryAccess>(&*Op);
207
1.12k
  }
208
1.12k
  // Never found a non-self reference, the phi is undef
209
1.12k
  
if (292
Same == nullptr292
)
210
0
    return MSSA->getLiveOnEntryDef();
211
292
  if (Phi) {
212
292
    Phi->replaceAllUsesWith(Same);
213
292
    removeMemoryAccess(Phi);
214
292
  }
215
292
216
292
  // We should only end up recursing in case we replaced something, in which
217
292
  // case, we may have made other Phis trivial.
218
292
  return recursePhi(Same);
219
292
}
220
221
113
void MemorySSAUpdater::insertUse(MemoryUse *MU) {
222
113
  InsertedPHIs.clear();
223
113
  MU->setDefiningAccess(getPreviousDef(MU));
224
113
  // Unlike for defs, there is no extra work to do.  Because uses do not create
225
113
  // new may-defs, there are only two cases:
226
113
  //
227
113
  // 1. There was a def already below us, and therefore, we should not have
228
113
  // created a phi node because it was already needed for the def.
229
113
  //
230
113
  // 2. There is no def below us, and therefore, there is no extra renaming work
231
113
  // to do.
232
113
}
233
234
// Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
235
static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
236
7
                                      MemoryAccess *NewDef) {
237
7
  // Replace any operand with us an incoming block with the new defining
238
7
  // access.
239
7
  int i = MP->getBasicBlockIndex(BB);
240
7
  assert(i != -1 && "Should have found the basic block in the phi");
241
7
  // We can't just compare i against getNumOperands since one is signed and the
242
7
  // other not. So use it to index into the block iterator.
243
14
  for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end();
244
8
       
++BBIter7
) {
245
8
    if (*BBIter != BB)
246
1
      break;
247
7
    MP->setIncomingValue(i, NewDef);
248
7
    ++i;
249
7
  }
250
7
}
251
252
// A brief description of the algorithm:
253
// First, we compute what should define the new def, using the SSA
254
// construction algorithm.
255
// Then, we update the defs below us (and any new phi nodes) in the graph to
256
// point to the correct new defs, to ensure we only have one variable, and no
257
// disconnected stores.
258
56
void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
259
56
  InsertedPHIs.clear();
260
56
261
56
  // See if we had a local def, and if not, go hunting.
262
56
  MemoryAccess *DefBefore = getPreviousDef(MD);
263
56
  bool DefBeforeSameBlock = DefBefore->getBlock() == MD->getBlock();
264
56
265
56
  // There is a def before us, which means we can replace any store/phi uses
266
56
  // of that thing with us, since we are in the way of whatever was there
267
56
  // before.
268
56
  // We now define that def's memorydefs and memoryphis
269
56
  if (DefBeforeSameBlock) {
270
27
    for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end();
271
86
         UI != UE;) {
272
59
      Use &U = *UI++;
273
59
      // Leave the MemoryUses alone.
274
59
      // Also make sure we skip ourselves to avoid self references.
275
59
      if (isa<MemoryUse>(U.getUser()) || 
U.getUser() == MD48
)
276
23
        continue;
277
36
      // Defs are automatically unoptimized when the user is set to MD below,
278
36
      // because the isOptimized() call will fail to find the same ID.
279
36
      U.set(MD);
280
36
    }
281
27
  }
282
56
283
56
  // and that def is now our defining access.
284
56
  MD->setDefiningAccess(DefBefore);
285
56
286
56
  // Remember the index where we may insert new phis below.
287
56
  unsigned NewPhiIndex = InsertedPHIs.size();
288
56
289
56
  SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
290
56
  if (!DefBeforeSameBlock) {
291
29
    // If there was a local def before us, we must have the same effect it
292
29
    // did. Because every may-def is the same, any phis/etc we would create, it
293
29
    // would also have created.  If there was no local def before us, we
294
29
    // performed a global update, and have to search all successors and make
295
29
    // sure we update the first def in each of them (following all paths until
296
29
    // we hit the first def along each path). This may also insert phi nodes.
297
29
    // TODO: There are other cases we can skip this work, such as when we have a
298
29
    // single successor, and only used a straight line of single pred blocks
299
29
    // backwards to find the def.  To make that work, we'd have to track whether
300
29
    // getDefRecursive only ever used the single predecessor case.  These types
301
29
    // of paths also only exist in between CFG simplifications.
302
29
303
29
    // If this is the first def in the block and this insert is in an arbitrary
304
29
    // place, compute IDF and place phis.
305
29
    auto Iter = MD->getDefsIterator();
306
29
    ++Iter;
307
29
    auto IterEnd = MSSA->getBlockDefs(MD->getBlock())->end();
308
29
    if (Iter == IterEnd) {
309
29
      ForwardIDFCalculator IDFs(*MSSA->DT);
310
29
      SmallVector<BasicBlock *, 32> IDFBlocks;
311
29
      SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
312
29
      DefiningBlocks.insert(MD->getBlock());
313
29
      IDFs.setDefiningBlocks(DefiningBlocks);
314
29
      IDFs.calculate(IDFBlocks);
315
29
      SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
316
29
      for (auto *BBIDF : IDFBlocks)
317
7
        if (!MSSA->getMemoryAccess(BBIDF)) {
318
2
          auto *MPhi = MSSA->createMemoryPhi(BBIDF);
319
2
          NewInsertedPHIs.push_back(MPhi);
320
2
          // Add the phis created into the IDF blocks to NonOptPhis, so they are
321
2
          // not optimized out as trivial by the call to getPreviousDefFromEnd
322
2
          // below. Once they are complete, all these Phis are added to the
323
2
          // FixupList, and removed from NonOptPhis inside fixupDefs().
324
2
          NonOptPhis.insert(MPhi);
325
2
        }
326
29
327
29
      for (auto &MPhi : NewInsertedPHIs) {
328
2
        auto *BBIDF = MPhi->getBlock();
329
4
        for (auto *Pred : predecessors(BBIDF)) {
330
4
          DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
331
4
          MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef),
332
4
                            Pred);
333
4
        }
334
2
      }
335
29
336
29
      // Re-take the index where we're adding the new phis, because the above
337
29
      // call to getPreviousDefFromEnd, may have inserted into InsertedPHIs.
338
29
      NewPhiIndex = InsertedPHIs.size();
339
29
      for (auto &MPhi : NewInsertedPHIs) {
340
2
        InsertedPHIs.push_back(&*MPhi);
341
2
        FixupList.push_back(&*MPhi);
342
2
      }
343
29
    }
344
29
345
29
    FixupList.push_back(MD);
346
29
  }
347
56
348
56
  // Remember the index where we stopped inserting new phis above, since the
349
56
  // fixupDefs call in the loop below may insert more, that are already minimal.
350
56
  unsigned NewPhiIndexEnd = InsertedPHIs.size();
351
56
352
85
  while (!FixupList.empty()) {
353
29
    unsigned StartingPHISize = InsertedPHIs.size();
354
29
    fixupDefs(FixupList);
355
29
    FixupList.clear();
356
29
    // Put any new phis on the fixup list, and process them
357
29
    FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
358
29
  }
359
56
360
56
  // Optimize potentially non-minimal phis added in this method.
361
56
  unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
362
56
  if (NewPhiSize)
363
2
    tryRemoveTrivialPhis(ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));
364
56
365
56
  // Now that all fixups are done, rename all uses if we are asked.
366
56
  if (RenameUses) {
367
12
    SmallPtrSet<BasicBlock *, 16> Visited;
368
12
    BasicBlock *StartBlock = MD->getBlock();
369
12
    // We are guaranteed there is a def in the block, because we just got it
370
12
    // handed to us in this function.
371
12
    MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
372
12
    // Convert to incoming value if it's a memorydef. A phi *is* already an
373
12
    // incoming value.
374
12
    if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
375
12
      FirstDef = MD->getDefiningAccess();
376
12
377
12
    MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
378
12
    // We just inserted a phi into this block, so the incoming value will become
379
12
    // the phi anyway, so it does not matter what we pass.
380
12
    for (auto &MP : InsertedPHIs) {
381
0
      MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
382
0
      if (Phi)
383
0
        MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
384
0
    }
385
12
  }
386
56
}
387
388
29
void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
389
29
  SmallPtrSet<const BasicBlock *, 8> Seen;
390
29
  SmallVector<const BasicBlock *, 16> Worklist;
391
32
  for (auto &Var : Vars) {
392
32
    MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
393
32
    if (!NewDef)
394
1
      continue;
395
31
    // First, see if there is a local def after the operand.
396
31
    auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
397
31
    auto DefIter = NewDef->getDefsIterator();
398
31
399
31
    // The temporary Phi is being fixed, unmark it for not to optimize.
400
31
    if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(NewDef))
401
2
      NonOptPhis.erase(Phi);
402
31
403
31
    // If there is a local def after us, we only have to rename that.
404
31
    if (++DefIter != Defs->end()) {
405
0
      cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
406
0
      continue;
407
0
    }
408
31
409
31
    // Otherwise, we need to search down through the CFG.
410
31
    // For each of our successors, handle it directly if their is a phi, or
411
31
    // place on the fixup worklist.
412
31
    for (const auto *S : successors(NewDef->getBlock())) {
413
17
      if (auto *MP = MSSA->getMemoryAccess(S))
414
5
        setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
415
12
      else
416
12
        Worklist.push_back(S);
417
17
    }
418
31
419
33
    while (!Worklist.empty()) {
420
8
      const BasicBlock *FixupBlock = Worklist.back();
421
8
      Worklist.pop_back();
422
8
423
8
      // Get the first def in the block that isn't a phi node.
424
8
      if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
425
6
        auto *FirstDef = &*Defs->begin();
426
6
        // The loop above and below should have taken care of phi nodes
427
6
        assert(!isa<MemoryPhi>(FirstDef) &&
428
6
               "Should have already handled phi nodes!");
429
6
        // We are now this def's defining access, make sure we actually dominate
430
6
        // it
431
6
        assert(MSSA->dominates(NewDef, FirstDef) &&
432
6
               "Should have dominated the new access");
433
6
434
6
        // This may insert new phi nodes, because we are not guaranteed the
435
6
        // block we are processing has a single pred, and depending where the
436
6
        // store was inserted, it may require phi nodes below it.
437
6
        cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
438
6
        return;
439
6
      }
440
2
      // We didn't find a def, so we must continue.
441
2
      for (const auto *S : successors(FixupBlock)) {
442
2
        // If there is a phi node, handle it.
443
2
        // Otherwise, put the block on the worklist
444
2
        if (auto *MP = MSSA->getMemoryAccess(S))
445
2
          setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
446
0
        else {
447
0
          // If we cycle, we should have ended up at a phi node that we already
448
0
          // processed.  FIXME: Double check this
449
0
          if (!Seen.insert(S).second)
450
0
            continue;
451
0
          Worklist.push_back(S);
452
0
        }
453
2
      }
454
2
    }
455
31
  }
456
29
}
457
458
173
void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
459
173
  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
460
62
    MPhi->unorderedDeleteIncomingBlock(From);
461
62
    if (MPhi->getNumIncomingValues() == 1)
462
59
      removeMemoryAccess(MPhi);
463
62
  }
464
173
}
465
466
void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock *From,
467
126
                                                      const BasicBlock *To) {
468
126
  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
469
6
    bool Found = false;
470
16
    MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
471
16
      if (From != B)
472
8
        return false;
473
8
      if (Found)
474
2
        return true;
475
6
      Found = true;
476
6
      return false;
477
6
    });
478
6
    if (MPhi->getNumIncomingValues() == 1)
479
0
      removeMemoryAccess(MPhi);
480
6
  }
481
126
}
482
483
void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
484
                                        const ValueToValueMapTy &VMap,
485
                                        PhiToDefMap &MPhiMap,
486
612
                                        bool CloneWasSimplified) {
487
612
  auto GetNewDefiningAccess = [&](MemoryAccess *MA) -> MemoryAccess * {
488
226
    MemoryAccess *InsnDefining = MA;
489
226
    if (MemoryUseOrDef *DefMUD = dyn_cast<MemoryUseOrDef>(InsnDefining)) {
490
134
      if (!MSSA->isLiveOnEntryDef(DefMUD)) {
491
80
        Instruction *DefMUDI = DefMUD->getMemoryInst();
492
80
        assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
493
80
        if (Instruction *NewDefMUDI =
494
80
                cast_or_null<Instruction>(VMap.lookup(DefMUDI)))
495
80
          InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
496
80
      }
497
134
    } else {
498
92
      MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
499
92
      if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
500
92
        InsnDefining = NewDefPhi;
501
92
    }
502
226
    assert(InsnDefining && "Defining instruction cannot be nullptr.");
503
226
    return InsnDefining;
504
226
  };
505
612
506
612
  const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
507
612
  if (!Acc)
508
401
    return;
509
352
  
for (const MemoryAccess &MA : *Acc)211
{
510
352
    if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
511
227
      Instruction *Insn = MUD->getMemoryInst();
512
227
      // Entry does not exist if the clone of the block did not clone all
513
227
      // instructions. This occurs in LoopRotate when cloning instructions
514
227
      // from the old header to the old preheader. The cloned instruction may
515
227
      // also be a simplified Value, not an Instruction (see LoopRotate).
516
227
      // Also in LoopRotate, even when it's an instruction, due to it being
517
227
      // simplified, it may be a Use rather than a Def, so we cannot use MUD as
518
227
      // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
519
227
      if (Instruction *NewInsn =
520
226
              dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
521
226
        MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
522
226
            NewInsn, GetNewDefiningAccess(MUD->getDefiningAccess()),
523
226
            CloneWasSimplified ? 
nullptr10
:
MUD216
);
524
226
        MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
525
226
      }
526
227
    }
527
352
  }
528
211
}
529
530
void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
531
11
    BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
532
11
  auto *MPhi = MSSA->getMemoryAccess(Header);
533
11
  if (!MPhi)
534
8
    return;
535
3
536
3
  // Create phi node in the backedge block and populate it with the same
537
3
  // incoming values as MPhi. Skip incoming values coming from Preheader.
538
3
  auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);
539
3
  bool HasUniqueIncomingValue = true;
540
3
  MemoryAccess *UniqueValue = nullptr;
541
12
  for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; 
++I9
) {
542
9
    BasicBlock *IBB = MPhi->getIncomingBlock(I);
543
9
    MemoryAccess *IV = MPhi->getIncomingValue(I);
544
9
    if (IBB != Preheader) {
545
6
      NewMPhi->addIncoming(IV, IBB);
546
6
      if (HasUniqueIncomingValue) {
547
6
        if (!UniqueValue)
548
3
          UniqueValue = IV;
549
3
        else if (UniqueValue != IV)
550
3
          HasUniqueIncomingValue = false;
551
6
      }
552
6
    }
553
9
  }
554
3
555
3
  // Update incoming edges into MPhi. Remove all but the incoming edge from
556
3
  // Preheader. Add an edge from NewMPhi
557
3
  auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);
558
3
  MPhi->setIncomingValue(0, AccFromPreheader);
559
3
  MPhi->setIncomingBlock(0, Preheader);
560
9
  for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; 
--I6
)
561
6
    MPhi->unorderedDeleteIncoming(I);
562
3
  MPhi->addIncoming(NewMPhi, BEBlock);
563
3
564
3
  // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
565
3
  // replaced with the unique value.
566
3
  if (HasUniqueIncomingValue)
567
0
    removeMemoryAccess(NewMPhi);
568
3
}
569
570
void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
571
                                           ArrayRef<BasicBlock *> ExitBlocks,
572
                                           const ValueToValueMapTy &VMap,
573
104
                                           bool IgnoreIncomingWithNoClones) {
574
104
  PhiToDefMap MPhiMap;
575
104
576
106
  auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
577
106
    assert(Phi && NewPhi && "Invalid Phi nodes.");
578
106
    BasicBlock *NewPhiBB = NewPhi->getBlock();
579
106
    SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
580
106
                                               pred_end(NewPhiBB));
581
329
    for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; 
++It223
) {
582
223
      MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
583
223
      BasicBlock *IncBB = Phi->getIncomingBlock(It);
584
223
585
223
      if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
586
186
        IncBB = NewIncBB;
587
37
      else if (IgnoreIncomingWithNoClones)
588
37
        continue;
589
186
590
186
      // Now we have IncBB, and will need to add incoming from it to NewPhi.
591
186
592
186
      // If IncBB is not a predecessor of NewPhiBB, then do not add it.
593
186
      // NewPhiBB was cloned without that edge.
594
186
      if (!NewPhiBBPreds.count(IncBB))
595
8
        continue;
596
178
597
178
      // Determine incoming value and add it as incoming from IncBB.
598
178
      if (MemoryUseOrDef *IncMUD = dyn_cast<MemoryUseOrDef>(IncomingAccess)) {
599
120
        if (!MSSA->isLiveOnEntryDef(IncMUD)) {
600
78
          Instruction *IncI = IncMUD->getMemoryInst();
601
78
          assert(IncI && "Found MemoryUseOrDef with no Instruction.");
602
78
          if (Instruction *NewIncI =
603
70
                  cast_or_null<Instruction>(VMap.lookup(IncI))) {
604
70
            IncMUD = MSSA->getMemoryAccess(NewIncI);
605
70
            assert(IncMUD &&
606
70
                   "MemoryUseOrDef cannot be null, all preds processed.");
607
70
          }
608
78
        }
609
120
        NewPhi->addIncoming(IncMUD, IncBB);
610
120
      } else {
611
58
        MemoryPhi *IncPhi = cast<MemoryPhi>(IncomingAccess);
612
58
        if (MemoryAccess *NewDefPhi = MPhiMap.lookup(IncPhi))
613
48
          NewPhi->addIncoming(NewDefPhi, IncBB);
614
10
        else
615
10
          NewPhi->addIncoming(IncPhi, IncBB);
616
58
      }
617
178
    }
618
106
  };
619
104
620
696
  auto ProcessBlock = [&](BasicBlock *BB) {
621
696
    BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));
622
696
    if (!NewBlock)
623
119
      return;
624
577
625
577
    assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
626
577
           "Cloned block should have no accesses");
627
577
628
577
    // Add MemoryPhi.
629
577
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
630
106
      MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
631
106
      MPhiMap[MPhi] = NewPhi;
632
106
    }
633
577
    // Update Uses and Defs.
634
577
    cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap);
635
577
  };
636
104
637
104
  for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
638
696
    ProcessBlock(BB);
639
104
640
104
  for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
641
696
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
642
108
      if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))
643
106
        FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
644
104
}
645
646
void MemorySSAUpdater::updateForClonedBlockIntoPred(
647
35
    BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
648
35
  // All defs/phis from outside BB that are used in BB, are valid uses in P1.
649
35
  // Since those defs/phis must have dominated BB, and also dominate P1.
650
35
  // Defs from BB being used in BB will be replaced with the cloned defs from
651
35
  // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
652
35
  // incoming def into the Phi from P1.
653
35
  // Instructions cloned into the predecessor are in practice sometimes
654
35
  // simplified, so disable the use of the template, and create an access from
655
35
  // scratch.
656
35
  PhiToDefMap MPhiMap;
657
35
  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
658
19
    MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
659
35
  cloneUsesAndDefs(BB, P1, VM, MPhiMap, /*CloneWasSimplified=*/true);
660
35
}
661
662
template <typename Iter>
663
void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
664
    ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
665
98
    DominatorTree &DT) {
666
98
  SmallVector<CFGUpdate, 4> Updates;
667
98
  // Update/insert phis in all successors of exit blocks.
668
98
  for (auto *Exit : ExitBlocks)
669
183
    for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
670
190
      if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
671
154
        BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
672
154
        Updates.push_back({DT.Insert, NewExit, ExitSucc});
673
154
      }
674
98
  applyInsertUpdates(Updates, DT);
675
98
}
void llvm::MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > const* const*>(llvm::ArrayRef<llvm::BasicBlock*>, llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > const* const*, llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > const* const*, llvm::DominatorTree&)
Line
Count
Source
665
38
    DominatorTree &DT) {
666
38
  SmallVector<CFGUpdate, 4> Updates;
667
38
  // Update/insert phis in all successors of exit blocks.
668
38
  for (auto *Exit : ExitBlocks)
669
87
    for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
670
87
      if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
671
87
        BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
672
87
        Updates.push_back({DT.Insert, NewExit, ExitSucc});
673
87
      }
674
38
  applyInsertUpdates(Updates, DT);
675
38
}
MemorySSAUpdater.cpp:void llvm::MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop<llvm::mapped_iterator<std::__1::unique_ptr<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >, std::__1::default_delete<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > > > const*, llvm::MemorySSAUpdater::updateExitBlocksForClonedLoop(llvm::ArrayRef<llvm::BasicBlock*>, llvm::ArrayRef<std::__1::unique_ptr<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >, std::__1::default_delete<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > > > >, llvm::DominatorTree&)::$_4, llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >*> >(llvm::ArrayRef<llvm::BasicBlock*>, llvm::mapped_iterator<std::__1::unique_ptr<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >, std::__1::default_delete<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > > > const*, llvm::MemorySSAUpdater::updateExitBlocksForClonedLoop(llvm::ArrayRef<llvm::BasicBlock*>, llvm::ArrayRef<std::__1::unique_ptr<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >, std::__1::default_delete<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > > > >, llvm::DominatorTree&)::$_4, llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >*>, llvm::mapped_iterator<std::__1::unique_ptr<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >, std::__1::default_delete<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > > > const*, llvm::MemorySSAUpdater::updateExitBlocksForClonedLoop(llvm::ArrayRef<llvm::BasicBlock*>, llvm::ArrayRef<std::__1::unique_ptr<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >, std::__1::default_delete<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > > > > >, llvm::DominatorTree&)::$_4, llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false> > >*>, llvm::DominatorTree&)
Line
Count
Source
665
60
    DominatorTree &DT) {
666
60
  SmallVector<CFGUpdate, 4> Updates;
667
60
  // Update/insert phis in all successors of exit blocks.
668
60
  for (auto *Exit : ExitBlocks)
669
96
    for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
670
103
      if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
671
67
        BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
672
67
        Updates.push_back({DT.Insert, NewExit, ExitSucc});
673
67
      }
674
60
  applyInsertUpdates(Updates, DT);
675
60
}
676
677
void MemorySSAUpdater::updateExitBlocksForClonedLoop(
678
    ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
679
38
    DominatorTree &DT) {
680
38
  const ValueToValueMapTy *const Arr[] = {&VMap};
681
38
  privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),
682
38
                                       std::end(Arr), DT);
683
38
}
684
685
void MemorySSAUpdater::updateExitBlocksForClonedLoop(
686
    ArrayRef<BasicBlock *> ExitBlocks,
687
60
    ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
688
103
  auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
689
103
    return I.get();
690
103
  };
691
60
  using MappedIteratorType =
692
60
      mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
693
60
                      decltype(GetPtr)>;
694
60
  auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
695
60
  auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
696
60
  privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
697
60
}
698
699
void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
700
143
                                    DominatorTree &DT) {
701
143
  SmallVector<CFGUpdate, 4> RevDeleteUpdates;
702
143
  SmallVector<CFGUpdate, 4> InsertUpdates;
703
265
  for (auto &Update : Updates) {
704
265
    if (Update.getKind() == DT.Insert)
705
195
      InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
706
70
    else
707
70
      RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
708
265
  }
709
143
710
143
  if (!RevDeleteUpdates.empty()) {
711
52
    // Update for inserted edges: use newDT and snapshot CFG as if deletes had
712
52
    // not occurred.
713
52
    // FIXME: This creates a new DT, so it's more expensive to do mix
714
52
    // delete/inserts vs just inserts. We can do an incremental update on the DT
715
52
    // to revert deletes, than re-delete the edges. Teaching DT to do this, is
716
52
    // part of a pending cleanup.
717
52
    DominatorTree NewDT(DT, RevDeleteUpdates);
718
52
    GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
719
52
    applyInsertUpdates(InsertUpdates, NewDT, &GD);
720
91
  } else {
721
91
    GraphDiff<BasicBlock *> GD;
722
91
    applyInsertUpdates(InsertUpdates, DT, &GD);
723
91
  }
724
143
725
143
  // Update for deleted edges
726
143
  for (auto &Update : RevDeleteUpdates)
727
70
    removeEdge(Update.getFrom(), Update.getTo());
728
143
}
729
730
void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
731
132
                                          DominatorTree &DT) {
732
132
  GraphDiff<BasicBlock *> GD;
733
132
  applyInsertUpdates(Updates, DT, &GD);
734
132
}
735
736
void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
737
                                          DominatorTree &DT,
738
275
                                          const GraphDiff<BasicBlock *> *GD) {
739
275
  // Get recursive last Def, assuming well formed MSSA and updated DT.
740
938
  auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
741
10.2k
    while (true) {
742
10.2k
      MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
743
10.2k
      // Return last Def or Phi in BB, if it exists.
744
10.2k
      if (Defs)
745
481
        return &*(--Defs->end());
746
9.73k
747
9.73k
      // Check number of predecessors, we only care if there's more than one.
748
9.73k
      unsigned Count = 0;
749
9.73k
      BasicBlock *Pred = nullptr;
750
9.92k
      for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
751
9.92k
        Pred = Pair.second;
752
9.92k
        Count++;
753
9.92k
        if (Count == 2)
754
655
          break;
755
9.92k
      }
756
9.73k
757
9.73k
      // If BB has multiple predecessors, get last definition from IDom.
758
9.73k
      if (Count != 1) {
759
1.11k
        // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
760
1.11k
        // DT is invalidated. Return LoE as its last def. This will be added to
761
1.11k
        // MemoryPhi node, and later deleted when the block is deleted.
762
1.11k
        if (!DT.getNode(BB))
763
0
          return MSSA->getLiveOnEntryDef();
764
1.11k
        if (auto *IDom = DT.getNode(BB)->getIDom())
765
655
          if (IDom->getBlock() != BB) {
766
655
            BB = IDom->getBlock();
767
655
            continue;
768
655
          }
769
457
        return MSSA->getLiveOnEntryDef();
770
8.61k
      } else {
771
8.61k
        // Single predecessor, BB cannot be dead. GetLastDef of Pred.
772
8.61k
        assert(Count == 1 && Pred && "Single predecessor expected.");
773
8.61k
        BB = Pred;
774
8.61k
      }
775
9.73k
    };
776
0
    llvm_unreachable("Unable to get last definition.");
777
938
  };
778
275
779
275
  // Get nearest IDom given a set of blocks.
780
275
  // TODO: this can be optimized by starting the search at the node with the
781
275
  // lowest level (highest in the tree).
782
275
  auto FindNearestCommonDominator =
783
275
      [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
784
191
    BasicBlock *PrevIDom = *BBSet.begin();
785
191
    for (auto *BB : BBSet)
786
199
      PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
787
191
    return PrevIDom;
788
191
  };
789
275
790
275
  // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
791
275
  // include CurrIDom.
792
275
  auto GetNoLongerDomBlocks =
793
275
      [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
794
275
          SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
795
191
        if (PrevIDom == CurrIDom)
796
0
          return;
797
191
        BlocksPrevDom.push_back(PrevIDom);
798
191
        BasicBlock *NextIDom = PrevIDom;
799
575
        while (BasicBlock *UpIDom =
800
575
                   DT.getNode(NextIDom)->getIDom()->getBlock()) {
801
575
          if (UpIDom == CurrIDom)
802
191
            break;
803
384
          BlocksPrevDom.push_back(UpIDom);
804
384
          NextIDom = UpIDom;
805
384
        }
806
191
      };
807
275
808
275
  // Map a BB to its predecessors: added + previously existing. To get a
809
275
  // deterministic order, store predecessors as SetVectors. The order in each
810
275
  // will be defined by the order in Updates (fixed) and the order given by
811
275
  // children<> (also fixed). Since we further iterate over these ordered sets,
812
275
  // we lose the information of multiple edges possibly existing between two
813
275
  // blocks, so we'll keep and EdgeCount map for that.
814
275
  // An alternate implementation could keep unordered set for the predecessors,
815
275
  // traverse either Updates or children<> each time to get  the deterministic
816
275
  // order, and drop the usage of EdgeCount. This alternate approach would still
817
275
  // require querying the maps for each predecessor, and children<> call has
818
275
  // additional computation inside for creating the snapshot-graph predecessors.
819
275
  // As such, we favor using a little additional storage and less compute time.
820
275
  // This decision can be revisited if we find the alternative more favorable.
821
275
822
275
  struct PredInfo {
823
275
    SmallSetVector<BasicBlock *, 2> Added;
824
275
    SmallSetVector<BasicBlock *, 2> Prev;
825
275
  };
826
275
  SmallDenseMap<BasicBlock *, PredInfo> PredMap;
827
275
828
383
  for (auto &Edge : Updates) {
829
383
    BasicBlock *BB = Edge.getTo();
830
383
    auto &AddedBlockSet = PredMap[BB].Added;
831
383
    AddedBlockSet.insert(Edge.getFrom());
832
383
  }
833
275
834
275
  // Store all existing predecessor for each BB, at least one must exist.
835
275
  SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
836
275
  SmallPtrSet<BasicBlock *, 2> NewBlocks;
837
383
  for (auto &BBPredPair : PredMap) {
838
383
    auto *BB = BBPredPair.first;
839
383
    const auto &AddedBlockSet = BBPredPair.second.Added;
840
383
    auto &PrevBlockSet = BBPredPair.second.Prev;
841
771
    for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
842
771
      BasicBlock *Pi = Pair.second;
843
771
      if (!AddedBlockSet.count(Pi))
844
353
        PrevBlockSet.insert(Pi);
845
771
      EdgeCountMap[{Pi, BB}]++;
846
771
    }
847
383
848
383
    if (PrevBlockSet.empty()) {
849
41
      assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
850
41
      LLVM_DEBUG(
851
41
          dbgs()
852
41
          << "Adding a predecessor to a block with no predecessors. "
853
41
             "This must be an edge added to a new, likely cloned, block. "
854
41
             "Its memory accesses must be already correct, assuming completed "
855
41
             "via the updateExitBlocksForClonedLoop API. "
856
41
             "Assert a single such edge is added so no phi addition or "
857
41
             "additional processing is required.\n");
858
41
      assert(AddedBlockSet.size() == 1 &&
859
41
             "Can only handle adding one predecessor to a new block.");
860
41
      // Need to remove new blocks from PredMap. Remove below to not invalidate
861
41
      // iterator here.
862
41
      NewBlocks.insert(BB);
863
41
    }
864
383
  }
865
275
  // Nothing to process for new/cloned blocks.
866
275
  for (auto *BB : NewBlocks)
867
41
    PredMap.erase(BB);
868
275
869
275
  SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
870
275
  SmallVector<WeakVH, 8> InsertedPhis;
871
275
872
275
  // First create MemoryPhis in all blocks that don't have one. Create in the
873
275
  // order found in Updates, not in PredMap, to get deterministic numbering.
874
383
  for (auto &Edge : Updates) {
875
383
    BasicBlock *BB = Edge.getTo();
876
383
    if (PredMap.count(BB) && 
!MSSA->getMemoryAccess(BB)342
)
877
338
      InsertedPhis.push_back(MSSA->createMemoryPhi(BB));
878
383
  }
879
275
880
275
  // Now we'll fill in the MemoryPhis with the right incoming values.
881
342
  for (auto &BBPredPair : PredMap) {
882
342
    auto *BB = BBPredPair.first;
883
342
    const auto &PrevBlockSet = BBPredPair.second.Prev;
884
342
    const auto &AddedBlockSet = BBPredPair.second.Added;
885
342
    assert(!PrevBlockSet.empty() &&
886
342
           "At least one previous predecessor must exist.");
887
342
888
342
    // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
889
342
    // keeping this map before the loop. We can reuse already populated entries
890
342
    // if an edge is added from the same predecessor to two different blocks,
891
342
    // and this does happen in rotate. Note that the map needs to be updated
892
342
    // when deleting non-necessary phis below, if the phi is in the map by
893
342
    // replacing the value with DefP1.
894
342
    SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;
895
342
    for (auto *AddedPred : AddedBlockSet) {
896
342
      auto *DefPn = GetLastDef(AddedPred);
897
342
      assert(DefPn != nullptr && "Unable to find last definition.");
898
342
      LastDefAddedPred[AddedPred] = DefPn;
899
342
    }
900
342
901
342
    MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
902
342
    // If Phi is not empty, add an incoming edge from each added pred. Must
903
342
    // still compute blocks with defs to replace for this block below.
904
342
    if (NewPhi->getNumOperands()) {
905
4
      for (auto *Pred : AddedBlockSet) {
906
4
        auto *LastDefForPred = LastDefAddedPred[Pred];
907
8
        for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; 
++I4
)
908
4
          NewPhi->addIncoming(LastDefForPred, Pred);
909
4
      }
910
338
    } else {
911
338
      // Pick any existing predecessor and get its definition. All other
912
338
      // existing predecessors should have the same one, since no phi existed.
913
338
      auto *P1 = *PrevBlockSet.begin();
914
338
      MemoryAccess *DefP1 = GetLastDef(P1);
915
338
916
338
      // Check DefP1 against all Defs in LastDefPredPair. If all the same,
917
338
      // nothing to add.
918
338
      bool InsertPhi = false;
919
338
      for (auto LastDefPredPair : LastDefAddedPred)
920
338
        if (DefP1 != LastDefPredPair.second) {
921
187
          InsertPhi = true;
922
187
          break;
923
187
        }
924
338
      if (!InsertPhi) {
925
151
        // Since NewPhi may be used in other newly added Phis, replace all uses
926
151
        // of NewPhi with the definition coming from all predecessors (DefP1),
927
151
        // before deleting it.
928
151
        NewPhi->replaceAllUsesWith(DefP1);
929
151
        removeMemoryAccess(NewPhi);
930
151
        continue;
931
151
      }
932
187
933
187
      // Update Phi with new values for new predecessors and old value for all
934
187
      // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
935
187
      // sets, the order of entries in NewPhi is deterministic.
936
187
      for (auto *Pred : AddedBlockSet) {
937
187
        auto *LastDefForPred = LastDefAddedPred[Pred];
938
379
        for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; 
++I192
)
939
192
          NewPhi->addIncoming(LastDefForPred, Pred);
940
187
      }
941
187
      for (auto *Pred : PrevBlockSet)
942
385
        
for (int I = 0, E = EdgeCountMap[{Pred, BB}]; 191
I < E;
++I194
)
943
194
          NewPhi->addIncoming(DefP1, Pred);
944
187
    }
945
342
946
342
    // Get all blocks that used to dominate BB and no longer do after adding
947
342
    // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
948
342
    assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
949
191
    BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
950
191
    assert(PrevIDom && "Previous IDom should exists");
951
191
    BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
952
191
    assert(NewIDom && "BB should have a new valid idom");
953
191
    assert(DT.dominates(NewIDom, PrevIDom) &&
954
191
           "New idom should dominate old idom");
955
191
    GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
956
191
  }
957
275
958
275
  tryRemoveTrivialPhis(InsertedPhis);
959
275
  // Create the set of blocks that now have a definition. We'll use this to
960
275
  // compute IDF and add Phis there next.
961
275
  SmallVector<BasicBlock *, 8> BlocksToProcess;
962
275
  for (auto &VH : InsertedPhis)
963
338
    if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
964
155
      BlocksToProcess.push_back(MPhi->getBlock());
965
275
966
275
  // Compute IDF and add Phis in all IDF blocks that do not have one.
967
275
  SmallVector<BasicBlock *, 32> IDFBlocks;
968
275
  if (!BlocksToProcess.empty()) {
969
115
    ForwardIDFCalculator IDFs(DT, GD);
970
115
    SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
971
115
                                                 BlocksToProcess.end());
972
115
    IDFs.setDefiningBlocks(DefiningBlocks);
973
115
    IDFs.calculate(IDFBlocks);
974
115
975
115
    SmallSetVector<MemoryPhi *, 4> PhisToFill;
976
115
    // First create all needed Phis.
977
115
    for (auto *BBIDF : IDFBlocks)
978
125
      if (!MSSA->getMemoryAccess(BBIDF)) {
979
5
        auto *IDFPhi = MSSA->createMemoryPhi(BBIDF);
980
5
        InsertedPhis.push_back(IDFPhi);
981
5
        PhisToFill.insert(IDFPhi);
982
5
      }
983
115
    // Then update or insert their correct incoming values.
984
125
    for (auto *BBIDF : IDFBlocks) {
985
125
      auto *IDFPhi = MSSA->getMemoryAccess(BBIDF);
986
125
      assert(IDFPhi && "Phi must exist");
987
125
      if (!PhisToFill.count(IDFPhi)) {
988
120
        // Update existing Phi.
989
120
        // FIXME: some updates may be redundant, try to optimize and skip some.
990
362
        for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; 
++I242
)
991
242
          IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
992
120
      } else {
993
10
        for (auto &Pair : children<GraphDiffInvBBPair>({GD, BBIDF})) {
994
10
          BasicBlock *Pi = Pair.second;
995
10
          IDFPhi->addIncoming(GetLastDef(Pi), Pi);
996
10
        }
997
5
      }
998
125
    }
999
115
  }
1000
275
1001
275
  // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
1002
275
  // longer dominate, replace those with the closest dominating def.
1003
275
  // This will also update optimized accesses, as they're also uses.
1004
575
  for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
1005
575
    if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
1006
354
      for (auto &DefToReplaceUses : *DefsList) {
1007
354
        BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
1008
354
        Value::use_iterator UI = DefToReplaceUses.use_begin(),
1009
354
                            E = DefToReplaceUses.use_end();
1010
1.14k
        for (; UI != E;) {
1011
788
          Use &U = *UI;
1012
788
          ++UI;
1013
788
          MemoryAccess *Usr = dyn_cast<MemoryAccess>(U.getUser());
1014
788
          if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
1015
387
            BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
1016
387
            if (!DT.dominates(DominatingBlock, DominatedBlock))
1017
2
              U.set(GetLastDef(DominatedBlock));
1018
401
          } else {
1019
401
            BasicBlock *DominatedBlock = Usr->getBlock();
1020
401
            if (!DT.dominates(DominatingBlock, DominatedBlock)) {
1021
59
              if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
1022
55
                U.set(DomBlPhi);
1023
4
              else {
1024
4
                auto *IDom = DT.getNode(DominatedBlock)->getIDom();
1025
4
                assert(IDom && "Block must have a valid IDom.");
1026
4
                U.set(GetLastDef(IDom->getBlock()));
1027
4
              }
1028
59
              cast<MemoryUseOrDef>(Usr)->resetOptimized();
1029
59
            }
1030
401
          }
1031
788
        }
1032
354
      }
1033
239
    }
1034
575
  }
1035
275
  tryRemoveTrivialPhis(InsertedPhis);
1036
275
}
1037
1038
// Move What before Where in the MemorySSA IR.
1039
template <class WhereType>
1040
void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1041
122
                              WhereType Where) {
1042
122
  // Mark MemoryPhi users of What not to be optimized.
1043
122
  for (auto *U : What->users())
1044
42
    if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
1045
32
      NonOptPhis.insert(PhiUser);
1046
122
1047
122
  // Replace all our users with our defining access.
1048
122
  What->replaceAllUsesWith(What->getDefiningAccess());
1049
122
1050
122
  // Let MemorySSA take care of moving it around in the lists.
1051
122
  MSSA->moveTo(What, BB, Where);
1052
122
1053
122
  // Now reinsert it into the IR and do whatever fixups needed.
1054
122
  if (auto *MD = dyn_cast<MemoryDef>(What))
1055
39
    insertDef(MD);
1056
83
  else
1057
83
    insertUse(cast<MemoryUse>(What));
1058
122
1059
122
  // Clear dangling pointers. We added all MemoryPhi users, but not all
1060
122
  // of them are removed by fixupDefs().
1061
122
  NonOptPhis.clear();
1062
122
}
void llvm::MemorySSAUpdater::moveTo<llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::MemoryAccess, false, false, llvm::MSSAHelpers::AllAccessTag>, false, false> >(llvm::MemoryUseOrDef*, llvm::BasicBlock*, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::MemoryAccess, false, false, llvm::MSSAHelpers::AllAccessTag>, false, false>)
Line
Count
Source
1041
4
                              WhereType Where) {
1042
4
  // Mark MemoryPhi users of What not to be optimized.
1043
4
  for (auto *U : What->users())
1044
5
    if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
1045
3
      NonOptPhis.insert(PhiUser);
1046
4
1047
4
  // Replace all our users with our defining access.
1048
4
  What->replaceAllUsesWith(What->getDefiningAccess());
1049
4
1050
4
  // Let MemorySSA take care of moving it around in the lists.
1051
4
  MSSA->moveTo(What, BB, Where);
1052
4
1053
4
  // Now reinsert it into the IR and do whatever fixups needed.
1054
4
  if (auto *MD = dyn_cast<MemoryDef>(What))
1055
4
    insertDef(MD);
1056
0
  else
1057
0
    insertUse(cast<MemoryUse>(What));
1058
4
1059
4
  // Clear dangling pointers. We added all MemoryPhi users, but not all
1060
4
  // of them are removed by fixupDefs().
1061
4
  NonOptPhis.clear();
1062
4
}
void llvm::MemorySSAUpdater::moveTo<llvm::MemorySSA::InsertionPlace>(llvm::MemoryUseOrDef*, llvm::BasicBlock*, llvm::MemorySSA::InsertionPlace)
Line
Count
Source
1041
118
                              WhereType Where) {
1042
118
  // Mark MemoryPhi users of What not to be optimized.
1043
118
  for (auto *U : What->users())
1044
37
    if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
1045
29
      NonOptPhis.insert(PhiUser);
1046
118
1047
118
  // Replace all our users with our defining access.
1048
118
  What->replaceAllUsesWith(What->getDefiningAccess());
1049
118
1050
118
  // Let MemorySSA take care of moving it around in the lists.
1051
118
  MSSA->moveTo(What, BB, Where);
1052
118
1053
118
  // Now reinsert it into the IR and do whatever fixups needed.
1054
118
  if (auto *MD = dyn_cast<MemoryDef>(What))
1055
35
    insertDef(MD);
1056
83
  else
1057
83
    insertUse(cast<MemoryUse>(What));
1058
118
1059
118
  // Clear dangling pointers. We added all MemoryPhi users, but not all
1060
118
  // of them are removed by fixupDefs().
1061
118
  NonOptPhis.clear();
1062
118
}
1063
1064
// Move What before Where in the MemorySSA IR.
1065
3
void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1066
3
  moveTo(What, Where->getBlock(), Where->getIterator());
1067
3
}
1068
1069
// Move What after Where in the MemorySSA IR.
1070
1
void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1071
1
  moveTo(What, Where->getBlock(), ++Where->getIterator());
1072
1
}
1073
1074
void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
1075
118
                                   MemorySSA::InsertionPlace Where) {
1076
118
  return moveTo(What, BB, Where);
1077
118
}
1078
1079
// All accesses in To used to be in From. Move to end and update access lists.
1080
void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
1081
392
                                       Instruction *Start) {
1082
392
1083
392
  MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From);
1084
392
  if (!Accs)
1085
319
    return;
1086
73
1087
73
  MemoryAccess *FirstInNew = nullptr;
1088
73
  for (Instruction &I : make_range(Start->getIterator(), To->end()))
1089
74
    if ((FirstInNew = MSSA->getMemoryAccess(&I)))
1090
36
      break;
1091
73
  if (!FirstInNew)
1092
37
    return;
1093
36
1094
36
  auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
1095
48
  do {
1096
48
    auto NextIt = ++MUD->getIterator();
1097
48
    MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
1098
48
                                  ? 
nullptr36
1099
48
                                  : 
cast<MemoryUseOrDef>(&*NextIt)12
;
1100
48
    MSSA->moveTo(MUD, To, MemorySSA::End);
1101
48
    // Moving MUD from Accs in the moveTo above, may delete Accs, so we need to
1102
48
    // retrieve it again.
1103
48
    Accs = MSSA->getWritableBlockAccesses(From);
1104
48
    MUD = NextMUD;
1105
48
  } while (MUD);
1106
36
}
1107
1108
void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,
1109
                                                BasicBlock *To,
1110
342
                                                Instruction *Start) {
1111
342
  assert(MSSA->getBlockAccesses(To) == nullptr &&
1112
342
         "To block is expected to be free of MemoryAccesses.");
1113
342
  moveAllAccesses(From, To, Start);
1114
342
  for (BasicBlock *Succ : successors(To))
1115
307
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1116
130
      MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1117
342
}
1118
1119
void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
1120
50
                                               Instruction *Start) {
1121
50
  assert(From->getSinglePredecessor() == To &&
1122
50
         "From block is expected to have a single predecessor (To).");
1123
50
  moveAllAccesses(From, To, Start);
1124
50
  for (BasicBlock *Succ : successors(From))
1125
86
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1126
21
      MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1127
50
}
1128
1129
/// If all arguments of a MemoryPHI are defined by the same incoming
1130
/// argument, return that argument.
1131
810
static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
1132
810
  MemoryAccess *MA = nullptr;
1133
810
1134
968
  for (auto &Arg : MP->operands()) {
1135
968
    if (!MA)
1136
652
      MA = cast<MemoryAccess>(Arg);
1137
316
    else if (MA != Arg)
1138
0
      return nullptr;
1139
968
  }
1140
810
  return MA;
1141
810
}
1142
1143
void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
1144
    BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
1145
446
    bool IdenticalEdgesWereMerged) {
1146
446
  assert(!MSSA->getWritableBlockAccesses(New) &&
1147
446
         "Access list should be null for a new block.");
1148
446
  MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
1149
446
  if (!Phi)
1150
318
    return;
1151
128
  if (Old->hasNPredecessors(1)) {
1152
2
    assert(pred_size(New) == Preds.size() &&
1153
2
           "Should have moved all predecessors.");
1154
2
    MSSA->moveTo(Phi, New, MemorySSA::Beginning);
1155
126
  } else {
1156
126
    assert(!Preds.empty() && "Must be moving at least one predecessor to the "
1157
126
                             "new immediate predecessor.");
1158
126
    MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
1159
126
    SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
1160
126
    // Currently only support the case of removing a single incoming edge when
1161
126
    // identical edges were not merged.
1162
126
    if (!IdenticalEdgesWereMerged)
1163
126
      assert(PredsSet.size() == Preds.size() &&
1164
126
             "If identical edges were not merged, we cannot have duplicate "
1165
126
             "blocks in the predecessors");
1166
265
    Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
1167
265
      if (PredsSet.count(B)) {
1168
128
        NewPhi->addIncoming(MA, B);
1169
128
        if (!IdenticalEdgesWereMerged)
1170
32
          PredsSet.erase(B);
1171
128
        return true;
1172
128
      }
1173
137
      return false;
1174
137
    });
1175
126
    Phi->addIncoming(NewPhi, New);
1176
126
    if (onlySingleValue(NewPhi))
1177
126
      removeMemoryAccess(NewPhi);
1178
126
  }
1179
128
}
1180
1181
111k
void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {
1182
111k
  assert(!MSSA->isLiveOnEntryDef(MA) &&
1183
111k
         "Trying to remove the live on entry def");
1184
111k
  // We can only delete phi nodes if they have no uses, or we can replace all
1185
111k
  // uses with a single definition.
1186
111k
  MemoryAccess *NewDefTarget = nullptr;
1187
111k
  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
1188
684
    // Note that it is sufficient to know that all edges of the phi node have
1189
684
    // the same argument.  If they do, by the definition of dominance frontiers
1190
684
    // (which we used to place this phi), that argument must dominate this phi,
1191
684
    // and thus, must dominate the phi's uses, and so we will not hit the assert
1192
684
    // below.
1193
684
    NewDefTarget = onlySingleValue(MP);
1194
684
    assert((NewDefTarget || MP->use_empty()) &&
1195
684
           "We can't delete this memory phi");
1196
110k
  } else {
1197
110k
    NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
1198
110k
  }
1199
111k
1200
111k
  SmallSetVector<MemoryPhi *, 4> PhisToCheck;
1201
111k
1202
111k
  // Re-point the uses at our defining access
1203
111k
  if (!isa<MemoryUse>(MA) && 
!MA->use_empty()8.32k
) {
1204
7.81k
    // Reset optimized on users of this store, and reset the uses.
1205
7.81k
    // A few notes:
1206
7.81k
    // 1. This is a slightly modified version of RAUW to avoid walking the
1207
7.81k
    // uses twice here.
1208
7.81k
    // 2. If we wanted to be complete, we would have to reset the optimized
1209
7.81k
    // flags on users of phi nodes if doing the below makes a phi node have all
1210
7.81k
    // the same arguments. Instead, we prefer users to removeMemoryAccess those
1211
7.81k
    // phi nodes, because doing it here would be N^3.
1212
7.81k
    if (MA->hasValueHandle())
1213
0
      ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
1214
7.81k
    // Note: We assume MemorySSA is not used in metadata since it's not really
1215
7.81k
    // part of the IR.
1216
7.81k
1217
15.7k
    while (!MA->use_empty()) {
1218
7.91k
      Use &U = *MA->use_begin();
1219
7.91k
      if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
1220
7.16k
        MUD->resetOptimized();
1221
7.91k
      if (OptimizePhis)
1222
7.61k
        if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))
1223
524
          PhisToCheck.insert(MP);
1224
7.91k
      U.set(NewDefTarget);
1225
7.91k
    }
1226
7.81k
  }
1227
111k
1228
111k
  // The call below to erase will destroy MA, so we can't change the order we
1229
111k
  // are doing things here
1230
111k
  MSSA->removeFromLookups(MA);
1231
111k
  MSSA->removeFromLists(MA);
1232
111k
1233
111k
  // Optionally optimize Phi uses. This will recursively remove trivial phis.
1234
111k
  if (!PhisToCheck.empty()) {
1235
514
    SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),
1236
514
                                           PhisToCheck.end()};
1237
514
    PhisToCheck.clear();
1238
514
1239
514
    unsigned PhisSize = PhisToOptimize.size();
1240
1.03k
    while (PhisSize-- > 0)
1241
521
      if (MemoryPhi *MP =
1242
520
              cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val())) {
1243
520
        auto OperRange = MP->operands();
1244
520
        tryRemoveTrivialPhi(MP, OperRange);
1245
520
      }
1246
514
  }
1247
111k
}
1248
1249
void MemorySSAUpdater::removeBlocks(
1250
127
    const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {
1251
127
  // First delete all uses of BB in MemoryPhis.
1252
127
  for (BasicBlock *BB : DeadBlocks) {
1253
110
    Instruction *TI = BB->getTerminator();
1254
110
    assert(TI && "Basic block expected to have a terminator instruction");
1255
110
    for (BasicBlock *Succ : successors(TI))
1256
139
      if (!DeadBlocks.count(Succ))
1257
70
        if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
1258
48
          MP->unorderedDeleteIncomingBlock(BB);
1259
48
          if (MP->getNumIncomingValues() == 1)
1260
42
            removeMemoryAccess(MP);
1261
48
        }
1262
110
    // Drop all references of all accesses in BB
1263
110
    if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))
1264
42
      for (MemoryAccess &MA : *Acc)
1265
82
        MA.dropAllReferences();
1266
110
  }
1267
127
1268
127
  // Next, delete all memory accesses in each block
1269
127
  for (BasicBlock *BB : DeadBlocks) {
1270
110
    MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
1271
110
    if (!Acc)
1272
68
      continue;
1273
124
    
for (auto AB = Acc->begin(), AE = Acc->end(); 42
AB != AE;) {
1274
82
      MemoryAccess *MA = &*AB;
1275
82
      ++AB;
1276
82
      MSSA->removeFromLookups(MA);
1277
82
      MSSA->removeFromLists(MA);
1278
82
    }
1279
42
  }
1280
127
}
1281
1282
552
void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {
1283
552
  for (auto &VH : UpdatedPHIs)
1284
683
    if (auto *MPhi = cast_or_null<MemoryPhi>(VH)) {
1285
349
      auto OperRange = MPhi->operands();
1286
349
      tryRemoveTrivialPhi(MPhi, OperRange);
1287
349
    }
1288
552
}
1289
1290
0
void MemorySSAUpdater::changeToUnreachable(const Instruction *I) {
1291
0
  const BasicBlock *BB = I->getParent();
1292
0
  // Remove memory accesses in BB for I and all following instructions.
1293
0
  auto BBI = I->getIterator(), BBE = BB->end();
1294
0
  // FIXME: If this becomes too expensive, iterate until the first instruction
1295
0
  // with a memory access, then iterate over MemoryAccesses.
1296
0
  while (BBI != BBE)
1297
0
    removeMemoryAccess(&*(BBI++));
1298
0
  // Update phis in BB's successors to remove BB.
1299
0
  SmallVector<WeakVH, 16> UpdatedPHIs;
1300
0
  for (const BasicBlock *Successor : successors(BB)) {
1301
0
    removeDuplicatePhiEdgesBetween(BB, Successor);
1302
0
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Successor)) {
1303
0
      MPhi->unorderedDeleteIncomingBlock(BB);
1304
0
      UpdatedPHIs.push_back(MPhi);
1305
0
    }
1306
0
  }
1307
0
  // Optimize trivial phis.
1308
0
  tryRemoveTrivialPhis(UpdatedPHIs);
1309
0
}
1310
1311
void MemorySSAUpdater::changeCondBranchToUnconditionalTo(const BranchInst *BI,
1312
0
                                                         const BasicBlock *To) {
1313
0
  const BasicBlock *BB = BI->getParent();
1314
0
  SmallVector<WeakVH, 16> UpdatedPHIs;
1315
0
  for (const BasicBlock *Succ : successors(BB)) {
1316
0
    removeDuplicatePhiEdgesBetween(BB, Succ);
1317
0
    if (Succ != To)
1318
0
      if (auto *MPhi = MSSA->getMemoryAccess(Succ)) {
1319
0
        MPhi->unorderedDeleteIncomingBlock(BB);
1320
0
        UpdatedPHIs.push_back(MPhi);
1321
0
      }
1322
0
  }
1323
0
  // Optimize trivial phis.
1324
0
  tryRemoveTrivialPhis(UpdatedPHIs);
1325
0
}
1326
1327
MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
1328
    Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
1329
37
    MemorySSA::InsertionPlace Point) {
1330
37
  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1331
37
  MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
1332
37
  return NewAccess;
1333
37
}
1334
1335
MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
1336
10
    Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
1337
10
  assert(I->getParent() == InsertPt->getBlock() &&
1338
10
         "New and old access must be in the same block");
1339
10
  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1340
10
  MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1341
10
                              InsertPt->getIterator());
1342
10
  return NewAccess;
1343
10
}
1344
1345
MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
1346
2
    Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
1347
2
  assert(I->getParent() == InsertPt->getBlock() &&
1348
2
         "New and old access must be in the same block");
1349
2
  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1350
2
  MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1351
2
                              ++InsertPt->getIterator());
1352
2
  return NewAccess;
1353
2
}