Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Utils/SSAUpdater.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This file implements the SSAUpdater class.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/Transforms/Utils/SSAUpdater.h"
15
#include "llvm/ADT/DenseMap.h"
16
#include "llvm/ADT/STLExtras.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/StringRef.h"
19
#include "llvm/ADT/TinyPtrVector.h"
20
#include "llvm/Analysis/InstructionSimplify.h"
21
#include "llvm/IR/BasicBlock.h"
22
#include "llvm/IR/CFG.h"
23
#include "llvm/IR/Constants.h"
24
#include "llvm/IR/DebugLoc.h"
25
#include "llvm/IR/Instruction.h"
26
#include "llvm/IR/Instructions.h"
27
#include "llvm/IR/Module.h"
28
#include "llvm/IR/Use.h"
29
#include "llvm/IR/Value.h"
30
#include "llvm/IR/ValueHandle.h"
31
#include "llvm/Support/Casting.h"
32
#include "llvm/Support/Debug.h"
33
#include "llvm/Support/raw_ostream.h"
34
#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
35
#include <cassert>
36
#include <utility>
37
38
using namespace llvm;
39
40
#define DEBUG_TYPE "ssaupdater"
41
42
typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
43
5.68M
static AvailableValsTy &getAvailableVals(void *AV) {
44
5.68M
  return *static_cast<AvailableValsTy*>(AV);
45
5.68M
}
46
47
SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
48
1.21M
  : InsertedPHIs(NewPHI) {}
49
50
1.21M
SSAUpdater::~SSAUpdater() {
51
1.21M
  delete static_cast<AvailableValsTy*>(AV);
52
1.21M
}
53
54
1.32M
void SSAUpdater::Initialize(Type *Ty, StringRef Name) {
55
1.32M
  if (!AV)
56
1.19M
    AV = new AvailableValsTy();
57
1.32M
  else
58
132k
    getAvailableVals(AV).clear();
59
1.32M
  ProtoType = Ty;
60
1.32M
  ProtoName = Name;
61
1.32M
}
62
63
2.39M
bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
64
2.39M
  return getAvailableVals(AV).count(BB);
65
2.39M
}
66
67
1.95M
void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
68
1.95M
  assert(ProtoType && "Need to initialize SSAUpdater");
69
1.95M
  assert(ProtoType == V->getType() &&
70
1.95M
         "All rewritten values must have the same type");
71
1.95M
  getAvailableVals(AV)[BB] = V;
72
1.95M
}
73
74
static bool IsEquivalentPHI(PHINode *PHI,
75
79.8k
                          SmallDenseMap<BasicBlock*, Value*, 8> &ValueMapping) {
76
79.8k
  unsigned PHINumValues = PHI->getNumIncomingValues();
77
79.8k
  if (PHINumValues != ValueMapping.size())
78
20
    return false;
79
79.7k
80
79.7k
  // Scan the phi to see if it matches.
81
204k
  
for (unsigned i = 0, e = PHINumValues; 79.7k
i != e204k
;
++i124k
)
82
143k
    
if (143k
ValueMapping[PHI->getIncomingBlock(i)] !=
83
143k
        PHI->getIncomingValue(i)) {
84
18.0k
      return false;
85
18.0k
    }
86
79.7k
87
61.7k
  return true;
88
79.8k
}
89
90
1.19M
Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
91
1.19M
  Value *Res = GetValueAtEndOfBlockInternal(BB);
92
1.19M
  return Res;
93
1.19M
}
94
95
772k
Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
96
772k
  // If there is no definition of the renamed variable in this block, just use
97
772k
  // GetValueAtEndOfBlock to do our work.
98
772k
  if (!HasValueForBlock(BB))
99
500k
    return GetValueAtEndOfBlock(BB);
100
271k
101
271k
  // Otherwise, we have the hard case.  Get the live-in values for each
102
271k
  // predecessor.
103
271k
  SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues;
104
271k
  Value *SingularValue = nullptr;
105
271k
106
271k
  // We can get our predecessor info by walking the pred_iterator list, but it
107
271k
  // is relatively slow.  If we already have PHI nodes in this block, walk one
108
271k
  // of them to get the predecessor list instead.
109
271k
  if (PHINode *
SomePhi271k
= dyn_cast<PHINode>(BB->begin())) {
110
270k
    for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); 
i != e270k
;
++i182k
) {
111
182k
      BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
112
182k
      Value *PredVal = GetValueAtEndOfBlock(PredBB);
113
182k
      PredValues.push_back(std::make_pair(PredBB, PredVal));
114
182k
115
182k
      // Compute SingularValue.
116
182k
      if (i == 0)
117
88.0k
        SingularValue = PredVal;
118
94.1k
      else 
if (94.1k
PredVal != SingularValue94.1k
)
119
69.7k
        SingularValue = nullptr;
120
182k
    }
121
271k
  } else {
122
183k
    bool isFirstPred = true;
123
453k
    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); 
PI != E453k
;
++PI269k
) {
124
269k
      BasicBlock *PredBB = *PI;
125
269k
      Value *PredVal = GetValueAtEndOfBlock(PredBB);
126
269k
      PredValues.push_back(std::make_pair(PredBB, PredVal));
127
269k
128
269k
      // Compute SingularValue.
129
269k
      if (
isFirstPred269k
) {
130
183k
        SingularValue = PredVal;
131
183k
        isFirstPred = false;
132
269k
      } else 
if (85.7k
PredVal != SingularValue85.7k
)
133
2.16k
        SingularValue = nullptr;
134
269k
    }
135
183k
  }
136
271k
137
271k
  // If there are no predecessors, just return undef.
138
271k
  if (PredValues.empty())
139
0
    return UndefValue::get(ProtoType);
140
271k
141
271k
  // Otherwise, if all the merged values are the same, just use it.
142
271k
  
if (271k
SingularValue271k
)
143
201k
    return SingularValue;
144
70.3k
145
70.3k
  // Otherwise, we do need a PHI: check to see if we already have one available
146
70.3k
  // in this block that produces the right value.
147
70.3k
  
if (70.3k
isa<PHINode>(BB->begin())70.3k
) {
148
68.2k
    SmallDenseMap<BasicBlock*, Value*, 8> ValueMapping(PredValues.begin(),
149
68.2k
                                                       PredValues.end());
150
68.2k
    PHINode *SomePHI;
151
68.2k
    for (BasicBlock::iterator It = BB->begin();
152
86.3k
         
(SomePHI = dyn_cast<PHINode>(It))86.3k
;
++It18.0k
) {
153
79.8k
      if (IsEquivalentPHI(SomePHI, ValueMapping))
154
61.7k
        return SomePHI;
155
79.8k
    }
156
68.2k
  }
157
70.3k
158
70.3k
  // Ok, we have no way out, insert a new one now.
159
8.56k
  PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(),
160
8.56k
                                         ProtoName, &BB->front());
161
8.56k
162
8.56k
  // Fill in all the predecessors of the PHI.
163
8.56k
  for (const auto &PredValue : PredValues)
164
18.0k
    InsertedPHI->addIncoming(PredValue.second, PredValue.first);
165
8.56k
166
8.56k
  // See if the PHI node can be merged to a single value.  This can happen in
167
8.56k
  // loop cases when we get a PHI of itself and one other value.
168
8.56k
  if (Value *V =
169
0
          SimplifyInstruction(InsertedPHI, BB->getModule()->getDataLayout())) {
170
0
    InsertedPHI->eraseFromParent();
171
0
    return V;
172
0
  }
173
8.56k
174
8.56k
  // Set the DebugLoc of the inserted PHI, if available.
175
8.56k
  DebugLoc DL;
176
8.56k
  if (const Instruction *I = BB->getFirstNonPHI())
177
8.56k
      DL = I->getDebugLoc();
178
8.56k
  InsertedPHI->setDebugLoc(DL);
179
8.56k
180
8.56k
  // If the client wants to know about all new instructions, tell it.
181
8.56k
  if (
InsertedPHIs8.56k
)
InsertedPHIs->push_back(InsertedPHI)8.42k
;
182
8.56k
183
8.56k
  DEBUG(dbgs() << "  Inserted PHI: " << *InsertedPHI << "\n");
184
772k
  return InsertedPHI;
185
772k
}
186
187
971k
void SSAUpdater::RewriteUse(Use &U) {
188
971k
  Instruction *User = cast<Instruction>(U.getUser());
189
971k
190
971k
  Value *V;
191
971k
  if (PHINode *UserPN = dyn_cast<PHINode>(User))
192
244k
    V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
193
971k
  else
194
727k
    V = GetValueInMiddleOfBlock(User->getParent());
195
971k
196
971k
  // Notify that users of the existing value that it is being replaced.
197
971k
  Value *OldVal = U.get();
198
971k
  if (
OldVal != V && 971k
OldVal->hasValueHandle()917k
)
199
89.9k
    ValueHandleBase::ValueIsRAUWd(OldVal, V);
200
971k
201
971k
  U.set(V);
202
971k
}
203
204
47
void SSAUpdater::RewriteUseAfterInsertions(Use &U) {
205
47
  Instruction *User = cast<Instruction>(U.getUser());
206
47
  
207
47
  Value *V;
208
47
  if (PHINode *UserPN = dyn_cast<PHINode>(User))
209
35
    V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
210
47
  else
211
12
    V = GetValueAtEndOfBlock(User->getParent());
212
47
  
213
47
  U.set(V);
214
47
}
215
216
namespace llvm {
217
218
template<>
219
class SSAUpdaterTraits<SSAUpdater> {
220
public:
221
  typedef BasicBlock BlkT;
222
  typedef Value *ValT;
223
  typedef PHINode PhiT;
224
225
  typedef succ_iterator BlkSucc_iterator;
226
4.40M
  static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); }
227
4.40M
  static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); }
228
229
  class PHI_iterator {
230
  private:
231
    PHINode *PHI;
232
    unsigned idx;
233
234
  public:
235
    explicit PHI_iterator(PHINode *P) // begin iterator
236
437k
      : PHI(P), idx(0) {}
237
    PHI_iterator(PHINode *P, bool) // end iterator
238
437k
      : PHI(P), idx(PHI->getNumIncomingValues()) {}
239
240
180k
    PHI_iterator &operator++() { ++idx; return *this; } 
241
618k
    bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
242
618k
    bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
243
244
559k
    Value *getIncomingValue() { return PHI->getIncomingValue(idx); }
245
559k
    BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); }
246
  };
247
248
437k
  static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
249
437k
  static PHI_iterator PHI_end(PhiT *PHI) {
250
437k
    return PHI_iterator(PHI, true);
251
437k
  }
252
253
  /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
254
  /// vector, set Info->NumPreds, and allocate space in Info->Preds.
255
  static void FindPredecessorBlocks(BasicBlock *BB,
256
3.37M
                                    SmallVectorImpl<BasicBlock*> *Preds) {
257
3.37M
    // We can get our predecessor info by walking the pred_iterator list,
258
3.37M
    // but it is relatively slow.  If we already have PHI nodes in this
259
3.37M
    // block, walk one of them to get the predecessor list instead.
260
3.37M
    if (PHINode *
SomePhi3.37M
= dyn_cast<PHINode>(BB->begin())) {
261
752k
      Preds->append(SomePhi->block_begin(), SomePhi->block_end());
262
3.37M
    } else {
263
5.63M
      for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); 
PI != E5.63M
;
++PI3.01M
)
264
3.01M
        Preds->push_back(*PI);
265
2.62M
    }
266
3.37M
  }
267
268
  /// GetUndefVal - Get an undefined value of the same type as the value
269
  /// being handled.
270
13
  static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) {
271
13
    return UndefValue::get(Updater->ProtoType);
272
13
  }
273
274
  /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
275
  /// Reserve space for the operands but do not fill them in yet.
276
  static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,
277
171k
                               SSAUpdater *Updater) {
278
171k
    PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds,
279
171k
                                   Updater->ProtoName, &BB->front());
280
171k
    return PHI;
281
171k
  }
282
283
  /// AddPHIOperand - Add the specified value as an operand of the PHI for
284
  /// the specified predecessor block.
285
380k
  static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {
286
380k
    PHI->addIncoming(Val, Pred);
287
380k
  }
288
289
  /// InstrIsPHI - Check if an instruction is a PHI.
290
  ///
291
566k
  static PHINode *InstrIsPHI(Instruction *I) {
292
566k
    return dyn_cast<PHINode>(I);
293
566k
  }
294
295
  /// ValueIsPHI - Check if a value is a PHI.
296
  ///
297
318k
  static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
298
318k
    return dyn_cast<PHINode>(Val);
299
318k
  }
300
301
  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
302
  /// operands, i.e., it was just added.
303
187k
  static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {
304
187k
    PHINode *PHI = ValueIsPHI(Val, Updater);
305
187k
    if (
PHI && 187k
PHI->getNumIncomingValues() == 0187k
)
306
171k
      return PHI;
307
16.2k
    return nullptr;
308
16.2k
  }
309
310
  /// GetPHIValue - For the specified PHI instruction, return the value
311
  /// that it defines.
312
58.6k
  static Value *GetPHIValue(PHINode *PHI) {
313
58.6k
    return PHI;
314
58.6k
  }
315
};
316
317
} // end namespace llvm
318
319
/// Check to see if AvailableVals has an entry for the specified BB and if so,
320
/// return it.  If not, construct SSA form by first calculating the required
321
/// placement of PHIs and then inserting new PHIs where needed.
322
1.19M
Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
323
1.19M
  AvailableValsTy &AvailableVals = getAvailableVals(AV);
324
1.19M
  if (Value *V = AvailableVals[BB])
325
351k
    return V;
326
847k
327
847k
  SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
328
847k
  return Impl.GetValue(BB);
329
847k
}
330
331
//===----------------------------------------------------------------------===//
332
// LoadAndStorePromoter Implementation
333
//===----------------------------------------------------------------------===//
334
335
LoadAndStorePromoter::
336
LoadAndStorePromoter(ArrayRef<const Instruction*> Insts,
337
2.54k
                     SSAUpdater &S, StringRef BaseName) : SSA(S) {
338
2.54k
  if (
Insts.empty()2.54k
)
return0
;
339
2.54k
  
340
2.54k
  const Value *SomeVal;
341
2.54k
  if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0]))
342
393
    SomeVal = LI;
343
2.54k
  else
344
2.15k
    SomeVal = cast<StoreInst>(Insts[0])->getOperand(0);
345
2.54k
346
2.54k
  if (BaseName.empty())
347
2.54k
    BaseName = SomeVal->getName();
348
2.54k
  SSA.Initialize(SomeVal->getType(), BaseName);
349
2.54k
}
350
351
void LoadAndStorePromoter::
352
2.54k
run(const SmallVectorImpl<Instruction*> &Insts) const {
353
2.54k
  // First step: bucket up uses of the alloca by the block they occur in.
354
2.54k
  // This is important because we have to handle multiple defs/uses in a block
355
2.54k
  // ourselves: SSAUpdater is purely for cross-block references.
356
2.54k
  DenseMap<BasicBlock*, TinyPtrVector<Instruction*>> UsesByBlock;
357
2.54k
358
2.54k
  for (Instruction *User : Insts)
359
4.88k
    UsesByBlock[User->getParent()].push_back(User);
360
2.54k
  
361
2.54k
  // Okay, now we can iterate over all the blocks in the function with uses,
362
2.54k
  // processing them.  Keep track of which loads are loading a live-in value.
363
2.54k
  // Walk the uses in the use-list order to be determinstic.
364
2.54k
  SmallVector<LoadInst*, 32> LiveInLoads;
365
2.54k
  DenseMap<Value*, Value*> ReplacedLoads;
366
2.54k
367
4.88k
  for (Instruction *User : Insts) {
368
4.88k
    BasicBlock *BB = User->getParent();
369
4.88k
    TinyPtrVector<Instruction*> &BlockUses = UsesByBlock[BB];
370
4.88k
    
371
4.88k
    // If this block has already been processed, ignore this repeat use.
372
4.88k
    if (
BlockUses.empty()4.88k
)
continue1.69k
;
373
3.19k
    
374
3.19k
    // Okay, this is the first use in the block.  If this block just has a
375
3.19k
    // single user in it, we can rewrite it trivially.
376
3.19k
    
if (3.19k
BlockUses.size() == 13.19k
) {
377
1.94k
      // If it is a store, it is a trivial def of the value in the block.
378
1.94k
      if (StoreInst *
SI1.94k
= dyn_cast<StoreInst>(User)) {
379
1.65k
        updateDebugInfo(SI);
380
1.65k
        SSA.AddAvailableValue(BB, SI->getOperand(0));
381
1.65k
      } else 
382
1.94k
        // Otherwise it is a load, queue it to rewrite as a live-in load.
383
294
        LiveInLoads.push_back(cast<LoadInst>(User));
384
1.94k
      BlockUses.clear();
385
1.94k
      continue;
386
1.94k
    }
387
1.24k
    
388
1.24k
    // Otherwise, check to see if this block is all loads.
389
1.24k
    bool HasStore = false;
390
1.61k
    for (Instruction *I : BlockUses) {
391
1.61k
      if (
isa<StoreInst>(I)1.61k
) {
392
1.20k
        HasStore = true;
393
1.20k
        break;
394
1.20k
      }
395
1.24k
    }
396
1.24k
    
397
1.24k
    // If so, we can queue them all as live in loads.  We don't have an
398
1.24k
    // efficient way to tell which on is first in the block and don't want to
399
1.24k
    // scan large blocks, so just add all loads as live ins.
400
1.24k
    if (
!HasStore1.24k
) {
401
38
      for (Instruction *I : BlockUses)
402
76
        LiveInLoads.push_back(cast<LoadInst>(I));
403
38
      BlockUses.clear();
404
38
      continue;
405
38
    }
406
1.20k
    
407
1.20k
    // Otherwise, we have mixed loads and stores (or just a bunch of stores).
408
1.20k
    // Since SSAUpdater is purely for cross-block values, we need to determine
409
1.20k
    // the order of these instructions in the block.  If the first use in the
410
1.20k
    // block is a load, then it uses the live in value.  The last store defines
411
1.20k
    // the live out value.  We handle this by doing a linear scan of the block.
412
1.20k
    Value *StoredValue = nullptr;
413
53.2k
    for (Instruction &I : *BB) {
414
53.2k
      if (LoadInst *
L53.2k
= dyn_cast<LoadInst>(&I)) {
415
9.43k
        // If this is a load from an unrelated pointer, ignore it.
416
9.43k
        if (
!isInstInList(L, Insts)9.43k
)
continue8.23k
;
417
1.20k
        
418
1.20k
        // If we haven't seen a store yet, this is a live in use, otherwise
419
1.20k
        // use the stored value.
420
1.20k
        
if (1.20k
StoredValue1.20k
) {
421
149
          replaceLoadWithValue(L, StoredValue);
422
149
          L->replaceAllUsesWith(StoredValue);
423
149
          ReplacedLoads[L] = StoredValue;
424
1.20k
        } else {
425
1.05k
          LiveInLoads.push_back(L);
426
1.05k
        }
427
9.43k
        continue;
428
9.43k
      }
429
43.8k
430
43.8k
      
if (StoreInst *43.8k
SI43.8k
= dyn_cast<StoreInst>(&I)) {
431
5.36k
        // If this is a store to an unrelated pointer, ignore it.
432
5.36k
        if (
!isInstInList(SI, Insts)5.36k
)
continue3.69k
;
433
1.66k
        updateDebugInfo(SI);
434
1.66k
435
1.66k
        // Remember that this is the active value in the block.
436
1.66k
        StoredValue = SI->getOperand(0);
437
1.66k
      }
438
53.2k
    }
439
4.88k
    
440
4.88k
    // The last stored value that happened is the live-out for the block.
441
4.88k
    assert(StoredValue && "Already checked that there is a store in block");
442
4.88k
    SSA.AddAvailableValue(BB, StoredValue);
443
4.88k
    BlockUses.clear();
444
4.88k
  }
445
2.54k
  
446
2.54k
  // Okay, now we rewrite all loads that use live-in values in the loop,
447
2.54k
  // inserting PHI nodes as necessary.
448
1.42k
  for (LoadInst *ALoad : LiveInLoads) {
449
1.42k
    Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent());
450
1.42k
    replaceLoadWithValue(ALoad, NewVal);
451
1.42k
452
1.42k
    // Avoid assertions in unreachable code.
453
1.42k
    if (
NewVal == ALoad1.42k
)
NewVal = UndefValue::get(NewVal->getType())0
;
454
1.42k
    ALoad->replaceAllUsesWith(NewVal);
455
1.42k
    ReplacedLoads[ALoad] = NewVal;
456
1.42k
  }
457
2.54k
  
458
2.54k
  // Allow the client to do stuff before we start nuking things.
459
2.54k
  doExtraRewritesBeforeFinalDeletion();
460
2.54k
  
461
2.54k
  // Now that everything is rewritten, delete the old instructions from the
462
2.54k
  // function.  They should all be dead now.
463
4.88k
  for (Instruction *User : Insts) {
464
4.88k
    // If this is a load that still has uses, then the load must have been added
465
4.88k
    // as a live value in the SSAUpdate data structure for a block (e.g. because
466
4.88k
    // the loaded value was stored later).  In this case, we need to recursively
467
4.88k
    // propagate the updates until we get to the real value.
468
4.88k
    if (
!User->use_empty()4.88k
) {
469
5
      Value *NewVal = ReplacedLoads[User];
470
5
      assert(NewVal && "not a replaced load?");
471
5
      
472
5
      // Propagate down to the ultimate replacee.  The intermediately loads
473
5
      // could theoretically already have been deleted, so we don't want to
474
5
      // dereference the Value*'s.
475
5
      DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal);
476
5
      while (
RLI != ReplacedLoads.end()5
) {
477
0
        NewVal = RLI->second;
478
0
        RLI = ReplacedLoads.find(NewVal);
479
0
      }
480
5
      
481
5
      replaceLoadWithValue(cast<LoadInst>(User), NewVal);
482
5
      User->replaceAllUsesWith(NewVal);
483
5
    }
484
4.88k
    
485
4.88k
    instructionDeleted(User);
486
4.88k
    User->eraseFromParent();
487
4.88k
  }
488
2.54k
}
489
490
bool
491
LoadAndStorePromoter::isInstInList(Instruction *I,
492
                                   const SmallVectorImpl<Instruction*> &Insts)
493
124
                                   const {
494
124
  return is_contained(Insts, I);
495
124
}