1 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===// 2 // 3 // This file implements the AliasSetTracker and AliasSet classes. 4 // 5 //===----------------------------------------------------------------------===// 6 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" 12 13 /// updateAccessTypes - Depending on what type of accesses are in this set, 14 /// decide whether the set contains just references, just modifications, or a 15 /// mix. 16 /// 17 void AliasSet::updateAccessType() { 18 if (!Calls.empty() || !Invokes.empty()) { 19 AccessTy = ModRef; 20 } else if (!Loads.empty()) { 21 if (Stores.empty()) 22 AccessTy = Refs; 23 else 24 AccessTy = ModRef; 25 } else { 26 AccessTy = Mods; 27 } 28 } 29 30 /// mergeSetIn - Merge the specified alias set into this alias set... 31 /// 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()); 38 39 // Update the alias and access types of this set... 40 if (AS.getAliasType() == MayAlias) 41 AliasTy = MayAlias; 42 updateAccessType(); 43 } 44 45 /// pointerAliasesSet - Return true if the specified pointer "may" (or must) 46 /// alias one of the members in the set. 47 /// 48 bool AliasSet::pointerAliasesSet(const Value *Ptr, AliasAnalysis &AA) const { 49 if (!Calls.empty() || !Invokes.empty()) 50 return true; 51 for (unsigned i = 0, e = Loads.size(); i != e; ++i) 52 if (AA.alias(Ptr, Loads[i]->getOperand(0))) 53 return true; 54 for (unsigned i = 0, e = Stores.size(); i != e; ++i) 55 if (AA.alias(Ptr, Stores[i]->getOperand(1))) 56 return true; 57 return false; 58 } 59 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. 64 /// 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!"); 69 70 if (!Loads.empty()) 71 return Loads[0]->getOperand(0); 72 assert(!Stores.empty() && "There are no instructions in this set!"); 73 return Stores[0]->getOperand(1); 74 } 75 76 77 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. 81 /// 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 92 } 93 } 94 } 95 96 return FoundSet; 97 } 98 99 100 void AliasSetTracker::add(LoadInst *LI) { 101 Value *Pointer = LI->getOperand(0); 102 103 // Check to see if the loaded pointer aliases any sets... 104 AliasSet *AS = findAliasSetForPointer(Pointer); 105 if (AS) { 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(); 112 } else { 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; 117 } 118 } 119 120 void AliasSetTracker::add(StoreInst *SI) { 121 Value *Pointer = SI->getOperand(1); 122 123 // Check to see if the loaded pointer aliases any sets... 124 AliasSet *AS = findAliasSetForPointer(Pointer); 125 if (AS) { 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(); 132 } else { 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; 137 } 138 } 139 140 141 void AliasSetTracker::mergeAllSets() { 142 if (AliasSets.size() < 2) return; // Noop 143 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]); 147 148 // Delete extraneous sets... 149 AliasSets.erase(AliasSets.begin()+1, AliasSets.end()); 150 } 151 152 void AliasSetTracker::add(CallInst *CI) { 153 if (!AliasSets.empty()) { 154 mergeAllSets(); 155 } else { 156 AliasSets.push_back(AliasSet()); 157 } 158 AliasSets[0].AccessTy = AliasSet::ModRef; 159 AliasSets[0].AliasTy = AliasSet::MayAlias; 160 AliasSets[0].Calls.push_back(CI); 161 } 162 163 void AliasSetTracker::add(InvokeInst *II) { 164 if (!AliasSets.empty()) { 165 mergeAllSets(); 166 } else { 167 AliasSets.push_back(AliasSet()); 168 } 169 AliasSets[0].AccessTy = AliasSet::ModRef; 170 AliasSets[0].AliasTy = AliasSet::MayAlias; 171 AliasSets[0].Invokes.push_back(II); 172 } 173