1 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
3 // This file implements the AliasSetTracker and AliasSet classes.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/Analysis/AliasSetTracker.h"
8 #include "llvm/Analysis/AliasAnalysis.h"
9 #include "llvm/iMemory.h"
10 #include "llvm/iOther.h"
11 #include "llvm/iTerminators.h"
13 /// updateAccessTypes - Depending on what type of accesses are in this set,
14 /// decide whether the set contains just references, just modifications, or a
17 void AliasSet::updateAccessType() {
18 if (!Calls.empty() || !Invokes.empty()) {
20 } else if (!Loads.empty()) {
30 /// mergeSetIn - Merge the specified alias set into this alias set...
32 void AliasSet::mergeSetIn(const AliasSet &AS) {
33 // Merge instruction sets...
34 Loads.insert( Loads.end(), AS.Loads.begin() , AS.Loads.end());
35 Stores.insert( Stores.end(), AS.Stores.begin() , AS.Stores.end());
36 Calls.insert( Calls.end(), AS.Calls.begin() , AS.Calls.end());
37 Invokes.insert(Invokes.end(), AS.Invokes.begin(), AS.Invokes.end());
39 // Update the alias and access types of this set...
40 if (AS.getAliasType() == MayAlias)
45 /// pointerAliasesSet - Return true if the specified pointer "may" (or must)
46 /// alias one of the members in the set.
48 bool AliasSet::pointerAliasesSet(const Value *Ptr, AliasAnalysis &AA) const {
49 if (!Calls.empty() || !Invokes.empty())
51 for (unsigned i = 0, e = Loads.size(); i != e; ++i)
52 if (AA.alias(Ptr, Loads[i]->getOperand(0)))
54 for (unsigned i = 0, e = Stores.size(); i != e; ++i)
55 if (AA.alias(Ptr, Stores[i]->getOperand(1)))
60 /// getSomePointer - This method may only be called when the AliasType of the
61 /// set is MustAlias. This is used to return any old pointer (which must alias
62 /// all other pointers in the set) so that the caller can decide whether to turn
63 /// this set into a may alias set or not.
65 Value *AliasSet::getSomePointer() const {
66 assert(getAliasType() == MustAlias &&
67 "Cannot call getSomePointer on a 'MayAlias' set!");
68 assert(Calls.empty() && Invokes.empty() && "Call/invokes mean may alias!");
71 return Loads[0]->getOperand(0);
72 assert(!Stores.empty() && "There are no instructions in this set!");
73 return Stores[0]->getOperand(1);
78 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the
79 /// instruction referring to the pointer into. If there are multiple alias sets
80 /// that may alias the pointer, merge them together and return the unified set.
82 AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr) {
83 AliasSet *FoundSet = 0;
84 for (unsigned i = 0; i != AliasSets.size(); ++i) {
85 if (AliasSets[i].pointerAliasesSet(Ptr, AA)) {
86 if (FoundSet == 0) { // If this is the first alias set ptr can go into...
87 FoundSet = &AliasSets[i]; // Remember it.
88 } else { // Otherwise, we must merge the sets...
89 FoundSet->mergeSetIn(AliasSets[i]); // Merge in contents...
90 AliasSets.erase(AliasSets.begin()+i); // Remove the set...
91 --i; // Don't skip the next set
100 void AliasSetTracker::add(LoadInst *LI) {
101 Value *Pointer = LI->getOperand(0);
103 // Check to see if the loaded pointer aliases any sets...
104 AliasSet *AS = findAliasSetForPointer(Pointer);
106 AS->Loads.push_back(LI);
107 // Check to see if we need to change this into a MayAlias set now...
108 if (AS->getAliasType() == AliasSet::MustAlias)
109 if (AA.alias(AS->getSomePointer(), Pointer) != AliasAnalysis::MustAlias)
110 AS->AliasTy = AliasSet::MayAlias;
111 AS->updateAccessType();
113 // Otherwise create a new alias set to hold the load...
114 AliasSets.push_back(AliasSet());
115 AliasSets.back().Loads.push_back(LI);
116 AliasSets.back().AccessTy = AliasSet::Refs;
120 void AliasSetTracker::add(StoreInst *SI) {
121 Value *Pointer = SI->getOperand(1);
123 // Check to see if the loaded pointer aliases any sets...
124 AliasSet *AS = findAliasSetForPointer(Pointer);
126 AS->Stores.push_back(SI);
127 // Check to see if we need to change this into a MayAlias set now...
128 if (AS->getAliasType() == AliasSet::MustAlias)
129 if (AA.alias(AS->getSomePointer(), Pointer) != AliasAnalysis::MustAlias)
130 AS->AliasTy = AliasSet::MayAlias;
131 AS->updateAccessType();
133 // Otherwise create a new alias set to hold the load...
134 AliasSets.push_back(AliasSet());
135 AliasSets.back().Stores.push_back(SI);
136 AliasSets.back().AccessTy = AliasSet::Mods;
141 void AliasSetTracker::mergeAllSets() {
142 if (AliasSets.size() < 2) return; // Noop
144 // Merge all of the sets into set #0
145 for (unsigned i = 1, e = AliasSets.size(); i != e; ++i)
146 AliasSets[0].mergeSetIn(AliasSets[i]);
148 // Delete extraneous sets...
149 AliasSets.erase(AliasSets.begin()+1, AliasSets.end());
152 void AliasSetTracker::add(CallInst *CI) {
153 if (!AliasSets.empty()) {
156 AliasSets.push_back(AliasSet());
158 AliasSets[0].AccessTy = AliasSet::ModRef;
159 AliasSets[0].AliasTy = AliasSet::MayAlias;
160 AliasSets[0].Calls.push_back(CI);
163 void AliasSetTracker::add(InvokeInst *II) {
164 if (!AliasSets.empty()) {
167 AliasSets.push_back(AliasSet());
169 AliasSets[0].AccessTy = AliasSet::ModRef;
170 AliasSets[0].AliasTy = AliasSet::MayAlias;
171 AliasSets[0].Invokes.push_back(II);