Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/AliasSetTracker.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
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 AliasSetTracker and AliasSet classes.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Analysis/AliasSetTracker.h"
14
#include "llvm/Analysis/AliasAnalysis.h"
15
#include "llvm/Analysis/GuardUtils.h"
16
#include "llvm/Analysis/LoopInfo.h"
17
#include "llvm/Analysis/MemoryLocation.h"
18
#include "llvm/Analysis/MemorySSA.h"
19
#include "llvm/Config/llvm-config.h"
20
#include "llvm/IR/Constants.h"
21
#include "llvm/IR/DataLayout.h"
22
#include "llvm/IR/Function.h"
23
#include "llvm/IR/InstIterator.h"
24
#include "llvm/IR/Instruction.h"
25
#include "llvm/IR/Instructions.h"
26
#include "llvm/IR/IntrinsicInst.h"
27
#include "llvm/IR/Module.h"
28
#include "llvm/IR/PatternMatch.h"
29
#include "llvm/IR/Value.h"
30
#include "llvm/Pass.h"
31
#include "llvm/Support/AtomicOrdering.h"
32
#include "llvm/Support/Casting.h"
33
#include "llvm/Support/CommandLine.h"
34
#include "llvm/Support/Compiler.h"
35
#include "llvm/Support/Debug.h"
36
#include "llvm/Support/ErrorHandling.h"
37
#include "llvm/Support/raw_ostream.h"
38
#include <cassert>
39
#include <cstdint>
40
#include <vector>
41
42
using namespace llvm;
43
44
static cl::opt<unsigned>
45
    SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
46
                        cl::init(250),
47
                        cl::desc("The maximum number of pointers may-alias "
48
                                 "sets may contain before degradation"));
49
50
/// mergeSetIn - Merge the specified alias set into this alias set.
51
///
52
138k
void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
53
138k
  assert(!AS.Forward && "Alias set is already forwarding!");
54
138k
  assert(!Forward && "This set is a forwarding set!!");
55
138k
56
138k
  bool WasMustAlias = (Alias == SetMustAlias);
57
138k
  // Update the alias and access types of this set...
58
138k
  Access |= AS.Access;
59
138k
  Alias  |= AS.Alias;
60
138k
61
138k
  if (Alias == SetMustAlias) {
62
48.1k
    // Check that these two merged sets really are must aliases.  Since both
63
48.1k
    // used to be must-alias sets, we can just check any pointer from each set
64
48.1k
    // for aliasing.
65
48.1k
    AliasAnalysis &AA = AST.getAliasAnalysis();
66
48.1k
    PointerRec *L = getSomePointer();
67
48.1k
    PointerRec *R = AS.getSomePointer();
68
48.1k
69
48.1k
    // If the pointers are not a must-alias pair, this set becomes a may alias.
70
48.1k
    if (AA.alias(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
71
48.1k
                 MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
72
48.1k
        MustAlias)
73
48.1k
      Alias = SetMayAlias;
74
48.1k
  }
75
138k
76
138k
  if (Alias == SetMayAlias) {
77
138k
    if (WasMustAlias)
78
50.9k
      AST.TotalMayAliasSetSize += size();
79
138k
    if (AS.Alias == SetMustAlias)
80
128k
      AST.TotalMayAliasSetSize += AS.size();
81
138k
  }
82
138k
83
138k
  bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
84
138k
  if (UnknownInsts.empty()) {            // Merge call sites...
85
136k
    if (ASHadUnknownInsts) {
86
666
      std::swap(UnknownInsts, AS.UnknownInsts);
87
666
      addRef();
88
666
    }
89
136k
  } else 
if (2.29k
ASHadUnknownInsts2.29k
) {
90
182
    UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
91
182
    AS.UnknownInsts.clear();
92
182
  }
93
138k
94
138k
  AS.Forward = this; // Forward across AS now...
95
138k
  addRef();          // AS is now pointing to us...
96
138k
97
138k
  // Merge the list of constituent pointers...
98
138k
  if (AS.PtrList) {
99
138k
    SetSize += AS.size();
100
138k
    AS.SetSize = 0;
101
138k
    *PtrListEnd = AS.PtrList;
102
138k
    AS.PtrList->setPrevInList(PtrListEnd);
103
138k
    PtrListEnd = AS.PtrListEnd;
104
138k
105
138k
    AS.PtrList = nullptr;
106
138k
    AS.PtrListEnd = &AS.PtrList;
107
138k
    assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
108
138k
  }
109
138k
  if (ASHadUnknownInsts)
110
848
    AS.dropRef(AST);
111
138k
}
112
113
60.7k
void AliasSetTracker::removeAliasSet(AliasSet *AS) {
114
60.7k
  if (AliasSet *Fwd = AS->Forward) {
115
60.6k
    Fwd->dropRef(*this);
116
60.6k
    AS->Forward = nullptr;
117
60.6k
  } else // Update TotalMayAliasSetSize only if not forwarding.
118
43
      if (AS->Alias == AliasSet::SetMayAlias)
119
5
        TotalMayAliasSetSize -= AS->size();
120
60.7k
121
60.7k
  AliasSets.erase(AS);
122
60.7k
}
123
124
60.7k
void AliasSet::removeFromTracker(AliasSetTracker &AST) {
125
60.7k
  assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
126
60.7k
  AST.removeAliasSet(this);
127
60.7k
}
128
129
void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
130
                          LocationSize Size, const AAMDNodes &AAInfo,
131
2.65M
                          bool KnownMustAlias, bool SkipSizeUpdate) {
132
2.65M
  assert(!Entry.hasAliasSet() && "Entry already in set!");
133
2.65M
134
2.65M
  // Check to see if we have to downgrade to _may_ alias.
135
2.65M
  if (isMustAlias())
136
1.08M
    if (PointerRec *P = getSomePointer()) {
137
188k
      if (!KnownMustAlias) {
138
179k
        AliasAnalysis &AA = AST.getAliasAnalysis();
139
179k
        AliasResult Result = AA.alias(
140
179k
            MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
141
179k
            MemoryLocation(Entry.getValue(), Size, AAInfo));
142
179k
        if (Result != MustAlias) {
143
179k
          Alias = SetMayAlias;
144
179k
          AST.TotalMayAliasSetSize += size();
145
179k
        }
146
179k
        assert(Result != NoAlias && "Cannot be part of must set!");
147
179k
      } else 
if (8.81k
!SkipSizeUpdate8.81k
)
148
8.69k
        P->updateSizeAndAAInfo(Size, AAInfo);
149
188k
    }
150
2.65M
151
2.65M
  Entry.setAliasSet(this);
152
2.65M
  Entry.updateSizeAndAAInfo(Size, AAInfo);
153
2.65M
154
2.65M
  // Add it to the end of the list...
155
2.65M
  ++SetSize;
156
2.65M
  assert(*PtrListEnd == nullptr && "End of list is not null?");
157
2.65M
  *PtrListEnd = &Entry;
158
2.65M
  PtrListEnd = Entry.setPrevInList(PtrListEnd);
159
2.65M
  assert(*PtrListEnd == nullptr && "End of list is not null?");
160
2.65M
  // Entry points to alias set.
161
2.65M
  addRef();
162
2.65M
163
2.65M
  if (Alias == SetMayAlias)
164
1.75M
    AST.TotalMayAliasSetSize++;
165
2.65M
}
166
167
1.00M
void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
168
1.00M
  if (UnknownInsts.empty())
169
261k
    addRef();
170
1.00M
  UnknownInsts.emplace_back(I);
171
1.00M
172
1.00M
  // Guards are marked as modifying memory for control flow modelling purposes,
173
1.00M
  // but don't actually modify any specific memory location.
174
1.00M
  using namespace PatternMatch;
175
1.00M
  bool MayWriteMemory = I->mayWriteToMemory() && 
!isGuard(I)990k
&&
176
1.00M
    
!(990k
I->use_empty()990k
&&
match(I, m_Intrinsic<Intrinsic::invariant_start>())309k
);
177
1.00M
  if (!MayWriteMemory) {
178
10.1k
    Alias = SetMayAlias;
179
10.1k
    Access |= RefAccess;
180
10.1k
    return;
181
10.1k
  }
182
990k
183
990k
  // FIXME: This should use mod/ref information to make this not suck so bad
184
990k
  Alias = SetMayAlias;
185
990k
  Access = ModRefAccess;
186
990k
}
187
188
/// aliasesPointer - If the specified pointer "may" (or must) alias one of the
189
/// members in the set return the appropriate AliasResult. Otherwise return
190
/// NoAlias.
191
///
192
AliasResult AliasSet::aliasesPointer(const Value *Ptr, LocationSize Size,
193
                                     const AAMDNodes &AAInfo,
194
10.9M
                                     AliasAnalysis &AA) const {
195
10.9M
  if (AliasAny)
196
0
    return MayAlias;
197
10.9M
198
10.9M
  if (Alias == SetMustAlias) {
199
9.17M
    assert(UnknownInsts.empty() && "Illegal must alias set!");
200
9.17M
201
9.17M
    // If this is a set of MustAliases, only check to see if the pointer aliases
202
9.17M
    // SOME value in the set.
203
9.17M
    PointerRec *SomePtr = getSomePointer();
204
9.17M
    assert(SomePtr && "Empty must-alias set??");
205
9.17M
    return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
206
9.17M
                                   SomePtr->getAAInfo()),
207
9.17M
                    MemoryLocation(Ptr, Size, AAInfo));
208
9.17M
  }
209
1.79M
210
1.79M
  // If this is a may-alias set, we have to check all of the pointers in the set
211
1.79M
  // to be sure it doesn't alias the set...
212
7.76M
  
for (iterator I = begin(), E = end(); 1.79M
I != E;
++I5.96M
)
213
7.21M
    if (AliasResult AR = AA.alias(
214
1.24M
            MemoryLocation(Ptr, Size, AAInfo),
215
1.24M
            MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
216
1.24M
      return AR;
217
1.79M
218
1.79M
  // Check the unknown instructions...
219
1.79M
  
if (547k
!UnknownInsts.empty()547k
) {
220
324k
    for (unsigned i = 0, e = UnknownInsts.size(); i != e; 
++i37.1k
)
221
316k
      if (auto *Inst = getUnknownInst(i))
222
316k
        if (isModOrRefSet(
223
316k
                AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo))))
224
279k
          return MayAlias;
225
287k
  }
226
547k
227
547k
  
return NoAlias267k
;
228
547k
}
229
230
bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
231
1.00M
                                  AliasAnalysis &AA) const {
232
1.00M
233
1.00M
  if (AliasAny)
234
7.19k
    return true;
235
993k
236
993k
  assert(Inst->mayReadOrWriteMemory() &&
237
993k
         "Instruction must either read or write memory.");
238
993k
239
1.01M
  for (unsigned i = 0, e = UnknownInsts.size(); i != e; 
++i17.1k
) {
240
747k
    if (auto *UnknownInst = getUnknownInst(i)) {
241
747k
      const auto *C1 = dyn_cast<CallBase>(UnknownInst);
242
747k
      const auto *C2 = dyn_cast<CallBase>(Inst);
243
747k
      if (!C1 || 
!C2744k
||
isModOrRefSet(AA.getModRefInfo(C1, C2))741k
||
244
747k
          
isModOrRefSet(AA.getModRefInfo(C2, C1))17.1k
)
245
730k
        return true;
246
747k
    }
247
747k
  }
248
993k
249
993k
  
for (iterator I = begin(), E = end(); 262k
I != E300k
;
++I37.5k
)
250
284k
    if (isModOrRefSet(AA.getModRefInfo(
251
284k
            Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()))))
252
247k
      return true;
253
262k
254
262k
  
return false15.5k
;
255
262k
}
256
257
286k
Instruction* AliasSet::getUniqueInstruction() {
258
286k
  if (AliasAny)
259
0
    // May have collapses alias set
260
0
    return nullptr;
261
286k
  if (begin() != end()) {
262
286k
    if (!UnknownInsts.empty())
263
9.68k
      // Another instruction found
264
9.68k
      return nullptr;
265
276k
    if (std::next(begin()) != end())
266
948
      // Another instruction found
267
948
      return nullptr;
268
275k
    Value *Addr = begin()->getValue();
269
275k
    assert(!Addr->user_empty() &&
270
275k
           "where's the instruction which added this pointer?");
271
275k
    if (std::next(Addr->user_begin()) != Addr->user_end())
272
10.3k
      // Another instruction found -- this is really restrictive
273
10.3k
      // TODO: generalize!
274
10.3k
      return nullptr;
275
265k
    return cast<Instruction>(*(Addr->user_begin()));
276
265k
  }
277
24
  if (1 != UnknownInsts.size())
278
8
    return nullptr;
279
16
  return cast<Instruction>(UnknownInsts[0]);
280
16
}
281
282
573k
void AliasSetTracker::clear() {
283
573k
  // Delete all the PointerRec entries.
284
573k
  for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
285
3.23M
       I != E; 
++I2.65M
)
286
2.65M
    I->second->eraseFromList();
287
573k
288
573k
  PointerMap.clear();
289
573k
290
573k
  // The alias sets should all be clear now.
291
573k
  AliasSets.clear();
292
573k
}
293
294
/// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
295
/// alias the pointer. Return the unified set, or nullptr if no set that aliases
296
/// the pointer was found. MustAliasAll is updated to true/false if the pointer
297
/// is found to MustAlias all the sets it merged.
298
AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
299
                                                    LocationSize Size,
300
                                                    const AAMDNodes &AAInfo,
301
2.62M
                                                    bool &MustAliasAll) {
302
2.62M
  AliasSet *FoundSet = nullptr;
303
2.62M
  AliasResult AllAR = MustAlias;
304
14.5M
  for (iterator I = begin(), E = end(); I != E;) {
305
11.9M
    iterator Cur = I++;
306
11.9M
    if (Cur->Forward)
307
936k
      continue;
308
10.9M
309
10.9M
    AliasResult AR = Cur->aliasesPointer(Ptr, Size, AAInfo, AA);
310
10.9M
    if (AR == NoAlias)
311
9.20M
      continue;
312
1.77M
313
1.77M
    AllAR =
314
1.77M
        AliasResult(AllAR & AR); // Possible downgrade to May/Partial, even No
315
1.77M
316
1.77M
    if (!FoundSet) {
317
1.72M
      // If this is the first alias set ptr can go into, remember it.
318
1.72M
      FoundSet = &*Cur;
319
1.72M
    } else {
320
43.8k
      // Otherwise, we must merge the sets.
321
43.8k
      FoundSet->mergeSetIn(*Cur, *this);
322
43.8k
    }
323
1.77M
  }
324
2.62M
325
2.62M
  MustAliasAll = (AllAR == MustAlias);
326
2.62M
  return FoundSet;
327
2.62M
}
328
329
1.00M
AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
330
1.00M
  AliasSet *FoundSet = nullptr;
331
2.30M
  for (iterator I = begin(), E = end(); I != E;) {
332
1.30M
    iterator Cur = I++;
333
1.30M
    if (Cur->Forward || 
!Cur->aliasesUnknownInst(Inst, AA)1.00M
)
334
318k
      continue;
335
984k
    if (!FoundSet) {
336
890k
      // If this is the first alias set ptr can go into, remember it.
337
890k
      FoundSet = &*Cur;
338
890k
    } else {
339
93.8k
      // Otherwise, we must merge the sets.
340
93.8k
      FoundSet->mergeSetIn(*Cur, *this);
341
93.8k
    }
342
984k
  }
343
1.00M
  return FoundSet;
344
1.00M
}
345
346
4.67M
AliasSet &AliasSetTracker::getAliasSetFor(const MemoryLocation &MemLoc) {
347
4.67M
348
4.67M
  Value * const Pointer = const_cast<Value*>(MemLoc.Ptr);
349
4.67M
  const LocationSize Size = MemLoc.Size;
350
4.67M
  const AAMDNodes &AAInfo = MemLoc.AATags;
351
4.67M
352
4.67M
  AliasSet::PointerRec &Entry = getEntryFor(Pointer);
353
4.67M
354
4.67M
  if (AliasAnyAS) {
355
114k
    // At this point, the AST is saturated, so we only have one active alias
356
114k
    // set. That means we already know which alias set we want to return, and
357
114k
    // just need to add the pointer to that set to keep the data structure
358
114k
    // consistent.
359
114k
    // This, of course, means that we will never need a merge here.
360
114k
    if (Entry.hasAliasSet()) {
361
78.8k
      Entry.updateSizeAndAAInfo(Size, AAInfo);
362
78.8k
      assert(Entry.getAliasSet(*this) == AliasAnyAS &&
363
78.8k
             "Entry in saturated AST must belong to only alias set");
364
78.8k
    } else {
365
35.7k
      AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
366
35.7k
    }
367
114k
    return *AliasAnyAS;
368
114k
  }
369
4.56M
370
4.56M
  bool MustAliasAll = false;
371
4.56M
  // Check to see if the pointer is already known.
372
4.56M
  if (Entry.hasAliasSet()) {
373
1.93M
    // If the size changed, we may need to merge several alias sets.
374
1.93M
    // Note that we can *not* return the result of mergeAliasSetsForPointer
375
1.93M
    // due to a quirk of alias analysis behavior. Since alias(undef, undef)
376
1.93M
    // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
377
1.93M
    // the right set for undef, even if it exists.
378
1.93M
    if (Entry.updateSizeAndAAInfo(Size, AAInfo))
379
2.44k
      mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll);
380
1.93M
    // Return the set!
381
1.93M
    return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
382
1.93M
  }
383
2.62M
384
2.62M
  if (AliasSet *AS =
385
1.72M
          mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll)) {
386
1.72M
    // Add it to the alias set it aliases.
387
1.72M
    AS->addPointer(*this, Entry, Size, AAInfo, MustAliasAll);
388
1.72M
    return *AS;
389
1.72M
  }
390
897k
391
897k
  // Otherwise create a new alias set to hold the loaded pointer.
392
897k
  AliasSets.push_back(new AliasSet());
393
897k
  AliasSets.back().addPointer(*this, Entry, Size, AAInfo, true);
394
897k
  return AliasSets.back();
395
897k
}
396
397
void AliasSetTracker::add(Value *Ptr, LocationSize Size,
398
178k
                          const AAMDNodes &AAInfo) {
399
178k
  addPointer(MemoryLocation(Ptr, Size, AAInfo), AliasSet::NoAccess);
400
178k
}
401
402
1.78M
void AliasSetTracker::add(LoadInst *LI) {
403
1.78M
  if (isStrongerThanMonotonic(LI->getOrdering()))
404
279
    return addUnknown(LI);
405
1.78M
  addPointer(MemoryLocation::get(LI), AliasSet::RefAccess);
406
1.78M
}
407
408
848k
void AliasSetTracker::add(StoreInst *SI) {
409
848k
  if (isStrongerThanMonotonic(SI->getOrdering()))
410
20
    return addUnknown(SI);
411
848k
  addPointer(MemoryLocation::get(SI), AliasSet::ModAccess);
412
848k
}
413
414
343
void AliasSetTracker::add(VAArgInst *VAAI) {
415
343
  addPointer(MemoryLocation::get(VAAI), AliasSet::ModRefAccess);
416
343
}
417
418
11.7k
void AliasSetTracker::add(AnyMemSetInst *MSI) {
419
11.7k
  addPointer(MemoryLocation::getForDest(MSI), AliasSet::ModAccess);
420
11.7k
}
421
422
19.8k
void AliasSetTracker::add(AnyMemTransferInst *MTI) {
423
19.8k
  addPointer(MemoryLocation::getForDest(MTI), AliasSet::ModAccess);
424
19.8k
  addPointer(MemoryLocation::getForSource(MTI), AliasSet::RefAccess);
425
19.8k
}
426
427
10.6M
void AliasSetTracker::addUnknown(Instruction *Inst) {
428
10.6M
  if (isa<DbgInfoIntrinsic>(Inst))
429
93
    return; // Ignore DbgInfo Intrinsics.
430
10.6M
431
10.6M
  if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
432
18.6k
    // These intrinsics will show up as affecting memory, but they are just
433
18.6k
    // markers.
434
18.6k
    switch (II->getIntrinsicID()) {
435
18.6k
    default:
436
18.6k
      break;
437
18.6k
      // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
438
18.6k
    case Intrinsic::assume:
439
21
    case Intrinsic::sideeffect:
440
21
      return;
441
10.6M
    }
442
10.6M
  }
443
10.6M
  if (!Inst->mayReadOrWriteMemory())
444
9.64M
    return; // doesn't alias anything
445
1.00M
446
1.00M
  if (AliasSet *AS = findAliasSetForUnknownInst(Inst)) {
447
890k
    AS->addUnknownInst(Inst, AA);
448
890k
    return;
449
890k
  }
450
109k
  AliasSets.push_back(new AliasSet());
451
109k
  AliasSets.back().addUnknownInst(Inst, AA);
452
109k
}
453
454
13.3M
void AliasSetTracker::add(Instruction *I) {
455
13.3M
  // Dispatch to one of the other add methods.
456
13.3M
  if (LoadInst *LI = dyn_cast<LoadInst>(I))
457
1.78M
    return add(LI);
458
11.6M
  if (StoreInst *SI = dyn_cast<StoreInst>(I))
459
848k
    return add(SI);
460
10.7M
  if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
461
343
    return add(VAAI);
462
10.7M
  if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
463
11.7k
    return add(MSI);
464
10.7M
  if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
465
19.8k
    return add(MTI);
466
10.7M
467
10.7M
  // Handle all calls with known mod/ref sets genericall
468
10.7M
  if (auto *Call = dyn_cast<CallBase>(I))
469
1.05M
    if (Call->onlyAccessesArgMemory()) {
470
79.9k
      auto getAccessFromModRef = [](ModRefInfo MRI) {
471
79.9k
        if (isRefSet(MRI) && 
isModSet(MRI)78.1k
)
472
73.2k
          return AliasSet::ModRefAccess;
473
6.67k
        else if (isModSet(MRI))
474
1.82k
          return AliasSet::ModAccess;
475
4.84k
        else if (isRefSet(MRI))
476
4.84k
          return AliasSet::RefAccess;
477
0
        else
478
0
          return AliasSet::NoAccess;
479
79.9k
      };
480
78.1k
481
78.1k
      ModRefInfo CallMask = createModRefInfo(AA.getModRefBehavior(Call));
482
78.1k
483
78.1k
      // Some intrinsics are marked as modifying memory for control flow
484
78.1k
      // modelling purposes, but don't actually modify any specific memory
485
78.1k
      // location.
486
78.1k
      using namespace PatternMatch;
487
78.1k
      if (Call->use_empty() &&
488
78.1k
          
match(Call, m_Intrinsic<Intrinsic::invariant_start>())75.1k
)
489
32
        CallMask = clearMod(CallMask);
490
78.1k
491
155k
      for (auto IdxArgPair : enumerate(Call->args())) {
492
155k
        int ArgIdx = IdxArgPair.index();
493
155k
        const Value *Arg = IdxArgPair.value();
494
155k
        if (!Arg->getType()->isPointerTy())
495
75.8k
          continue;
496
79.9k
        MemoryLocation ArgLoc =
497
79.9k
            MemoryLocation::getForArgument(Call, ArgIdx, nullptr);
498
79.9k
        ModRefInfo ArgMask = AA.getArgModRefInfo(Call, ArgIdx);
499
79.9k
        ArgMask = intersectModRef(CallMask, ArgMask);
500
79.9k
        if (!isNoModRef(ArgMask))
501
79.9k
          addPointer(ArgLoc, getAccessFromModRef(ArgMask));
502
79.9k
      }
503
78.1k
      return;
504
78.1k
    }
505
10.6M
506
10.6M
  return addUnknown(I);
507
10.6M
}
508
509
2.06M
void AliasSetTracker::add(BasicBlock &BB) {
510
2.06M
  for (auto &I : BB)
511
13.2M
    add(&I);
512
2.06M
}
513
514
68.3k
void AliasSetTracker::add(const AliasSetTracker &AST) {
515
68.3k
  assert(&AA == &AST.AA &&
516
68.3k
         "Merging AliasSetTracker objects with different Alias Analyses!");
517
68.3k
518
68.3k
  // Loop over all of the alias sets in AST, adding the pointers contained
519
68.3k
  // therein into the current alias sets.  This can cause alias sets to be
520
68.3k
  // merged together in the current AST.
521
77.9k
  for (const AliasSet &AS : AST) {
522
77.9k
    if (AS.Forward)
523
4.92k
      continue; // Ignore forwarding alias sets
524
73.0k
525
73.0k
    // If there are any call sites in the alias set, add them to this AST.
526
232k
    
for (unsigned i = 0, e = AS.UnknownInsts.size(); 73.0k
i != e;
++i159k
)
527
159k
      if (auto *Inst = AS.getUnknownInst(i))
528
159k
        add(Inst);
529
73.0k
530
73.0k
    // Loop over all of the pointers in this alias set.
531
318k
    for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; 
++ASI245k
)
532
245k
      addPointer(
533
245k
          MemoryLocation(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo()),
534
245k
          (AliasSet::AccessLattice)AS.Access);
535
73.0k
  }
536
68.3k
}
537
538
156
void AliasSetTracker::addAllInstructionsInLoopUsingMSSA() {
539
156
  assert(MSSA && L && "MSSA and L must be available");
540
156
  for (const BasicBlock *BB : L->blocks())
541
461
    if (auto *Accesses = MSSA->getBlockAccesses(BB))
542
305
      for (auto &Access : *Accesses)
543
499
        if (auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
544
297
          add(MUD->getMemoryInst());
545
156
}
546
547
// deleteValue method - This method is used to remove a pointer value from the
548
// AliasSetTracker entirely.  It should be used when an instruction is deleted
549
// from the program to update the AST.  If you don't use this, you would have
550
// dangling pointers to deleted instructions.
551
//
552
10.1k
void AliasSetTracker::deleteValue(Value *PtrVal) {
553
10.1k
  // First, look up the PointerRec for this pointer.
554
10.1k
  PointerMapType::iterator I = PointerMap.find_as(PtrVal);
555
10.1k
  if (I == PointerMap.end()) 
return9.74k
; // Noop
556
450
557
450
  // If we found one, remove the pointer from the alias set it is in.
558
450
  AliasSet::PointerRec *PtrValEnt = I->second;
559
450
  AliasSet *AS = PtrValEnt->getAliasSet(*this);
560
450
561
450
  // Unlink and delete from the list of values.
562
450
  PtrValEnt->eraseFromList();
563
450
564
450
  if (AS->Alias == AliasSet::SetMayAlias) {
565
255
    AS->SetSize--;
566
255
    TotalMayAliasSetSize--;
567
255
  }
568
450
569
450
  // Stop using the alias set.
570
450
  AS->dropRef(*this);
571
450
572
450
  PointerMap.erase(I);
573
450
}
574
575
// copyValue - This method should be used whenever a preexisting value in the
576
// program is copied or cloned, introducing a new value.  Note that it is ok for
577
// clients that use this method to introduce the same value multiple times: if
578
// the tracker already knows about a value, it will ignore the request.
579
//
580
17.1k
void AliasSetTracker::copyValue(Value *From, Value *To) {
581
17.1k
  // First, look up the PointerRec for this pointer.
582
17.1k
  PointerMapType::iterator I = PointerMap.find_as(From);
583
17.1k
  if (I == PointerMap.end())
584
16.1k
    return;  // Noop
585
965
  assert(I->second->hasAliasSet() && "Dead entry?");
586
965
587
965
  AliasSet::PointerRec &Entry = getEntryFor(To);
588
965
  if (Entry.hasAliasSet()) 
return546
; // Already in the tracker!
589
419
590
419
  // getEntryFor above may invalidate iterator \c I, so reinitialize it.
591
419
  I = PointerMap.find_as(From);
592
419
  // Add it to the alias set it aliases...
593
419
  AliasSet *AS = I->second->getAliasSet(*this);
594
419
  AS->addPointer(*this, Entry, I->second->getSize(), I->second->getAAInfo(),
595
419
                 true, true);
596
419
}
597
598
189
AliasSet &AliasSetTracker::mergeAllAliasSets() {
599
189
  assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
600
189
         "Full merge should happen once, when the saturation threshold is "
601
189
         "reached");
602
189
603
189
  // Collect all alias sets, so that we can drop references with impunity
604
189
  // without worrying about iterator invalidation.
605
189
  std::vector<AliasSet *> ASVector;
606
189
  ASVector.reserve(SaturationThreshold);
607
1.61k
  for (iterator I = begin(), E = end(); I != E; 
I++1.42k
)
608
1.42k
    ASVector.push_back(&*I);
609
189
610
189
  // Copy all instructions and pointers into a new set, and forward all other
611
189
  // sets to it.
612
189
  AliasSets.push_back(new AliasSet());
613
189
  AliasAnyAS = &AliasSets.back();
614
189
  AliasAnyAS->Alias = AliasSet::SetMayAlias;
615
189
  AliasAnyAS->Access = AliasSet::ModRefAccess;
616
189
  AliasAnyAS->AliasAny = true;
617
189
618
1.42k
  for (auto Cur : ASVector) {
619
1.42k
    // If Cur was already forwarding, just forward to the new AS instead.
620
1.42k
    AliasSet *FwdTo = Cur->Forward;
621
1.42k
    if (FwdTo) {
622
672
      Cur->Forward = AliasAnyAS;
623
672
      AliasAnyAS->addRef();
624
672
      FwdTo->dropRef(*this);
625
672
      continue;
626
672
    }
627
750
628
750
    // Otherwise, perform the actual merge.
629
750
    AliasAnyAS->mergeSetIn(*Cur, *this);
630
750
  }
631
189
632
189
  return *AliasAnyAS;
633
189
}
634
635
AliasSet &AliasSetTracker::addPointer(MemoryLocation Loc,
636
3.19M
                                      AliasSet::AccessLattice E) {
637
3.19M
  AliasSet &AS = getAliasSetFor(Loc);
638
3.19M
  AS.Access |= E;
639
3.19M
640
3.19M
  if (!AliasAnyAS && 
(TotalMayAliasSetSize > SaturationThreshold)3.13M
) {
641
189
    // The AST is now saturated. From here on, we conservatively consider all
642
189
    // pointers to alias each-other.
643
189
    return mergeAllAliasSets();
644
189
  }
645
3.19M
646
3.19M
  return AS;
647
3.19M
}
648
649
//===----------------------------------------------------------------------===//
650
//               AliasSet/AliasSetTracker Printing Support
651
//===----------------------------------------------------------------------===//
652
653
270
void AliasSet::print(raw_ostream &OS) const {
654
270
  OS << "  AliasSet[" << (const void*)this << ", " << RefCount << "] ";
655
270
  OS << (Alias == SetMustAlias ? 
"must"143
:
"may"127
) << " alias, ";
656
270
  switch (Access) {
657
270
  
case NoAccess: OS << "No access "; break0
;
658
270
  
case RefAccess: OS << "Ref "; break94
;
659
270
  
case ModAccess: OS << "Mod "; break91
;
660
270
  
case ModRefAccess: OS << "Mod/Ref "; break85
;
661
270
  
default: 0
llvm_unreachable0
("Bad value for Access!");
662
270
  }
663
270
  if (Forward)
664
5
    OS << " forwarding to " << (void*)Forward;
665
270
666
270
  if (!empty()) {
667
252
    OS << "Pointers: ";
668
642
    for (iterator I = begin(), E = end(); I != E; 
++I390
) {
669
390
      if (I != begin()) 
OS << ", "138
;
670
390
      I.getPointer()->printAsOperand(OS << "(");
671
390
      if (I.getSize() == LocationSize::unknown())
672
22
        OS << ", unknown)";
673
368
      else 
674
368
        OS << ", " << I.getSize() << ")";
675
390
    }
676
252
  }
677
270
  if (!UnknownInsts.empty()) {
678
111
    OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
679
258
    for (unsigned i = 0, e = UnknownInsts.size(); i != e; 
++i147
) {
680
147
      if (i) 
OS << ", "36
;
681
147
      if (auto *I = getUnknownInst(i)) {
682
147
        if (I->hasName())
683
0
          I->printAsOperand(OS);
684
147
        else
685
147
          I->print(OS);
686
147
      }
687
147
    }
688
111
  }
689
270
  OS << "\n";
690
270
}
691
692
148
void AliasSetTracker::print(raw_ostream &OS) const {
693
148
  OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
694
148
     << PointerMap.size() << " pointer values.\n";
695
148
  for (const AliasSet &AS : *this)
696
270
    AS.print(OS);
697
148
  OS << "\n";
698
148
}
699
700
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
701
LLVM_DUMP_METHOD void AliasSet::dump() const { print(dbgs()); }
702
LLVM_DUMP_METHOD void AliasSetTracker::dump() const { print(dbgs()); }
703
#endif
704
705
//===----------------------------------------------------------------------===//
706
//                     ASTCallbackVH Class Implementation
707
//===----------------------------------------------------------------------===//
708
709
44
void AliasSetTracker::ASTCallbackVH::deleted() {
710
44
  assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
711
44
  AST->deleteValue(getValPtr());
712
44
  // this now dangles!
713
44
}
714
715
694
void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
716
694
  AST->copyValue(getValPtr(), V);
717
694
}
718
719
AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
720
26.4M
  : CallbackVH(V), AST(ast) {}
721
722
AliasSetTracker::ASTCallbackVH &
723
0
AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
724
0
  return *this = ASTCallbackVH(V, AST);
725
0
}
726
727
//===----------------------------------------------------------------------===//
728
//                            AliasSetPrinter Pass
729
//===----------------------------------------------------------------------===//
730
731
namespace {
732
733
  class AliasSetPrinter : public FunctionPass {
734
    AliasSetTracker *Tracker;
735
736
  public:
737
    static char ID; // Pass identification, replacement for typeid
738
739
8
    AliasSetPrinter() : FunctionPass(ID) {
740
8
      initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry());
741
8
    }
742
743
8
    void getAnalysisUsage(AnalysisUsage &AU) const override {
744
8
      AU.setPreservesAll();
745
8
      AU.addRequired<AAResultsWrapperPass>();
746
8
    }
747
748
148
    bool runOnFunction(Function &F) override {
749
148
      auto &AAWP = getAnalysis<AAResultsWrapperPass>();
750
148
      Tracker = new AliasSetTracker(AAWP.getAAResults());
751
148
      errs() << "Alias sets for function '" << F.getName() << "':\n";
752
985
      for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; 
++I837
)
753
837
        Tracker->add(&*I);
754
148
      Tracker->print(errs());
755
148
      delete Tracker;
756
148
      return false;
757
148
    }
758
  };
759
760
} // end anonymous namespace
761
762
char AliasSetPrinter::ID = 0;
763
764
11.0k
INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
765
11.0k
                "Alias Set Printer", false, true)
766
11.0k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
767
11.0k
INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
768
                "Alias Set Printer", false, true)