Chris Lattner | 9d7c9ea | 2003-11-25 20:11:47 +0000 | [diff] [blame] | 1 | //===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 9 | // |
| 10 | // This file defines the default implementation of the Alias Analysis interface |
| 11 | // that simply implements a few identities (two different globals cannot alias, |
| 12 | // etc), but otherwise does no analysis. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #include "llvm/Analysis/AliasAnalysis.h" |
Jeff Cohen | 534927d | 2005-01-08 22:01:16 +0000 | [diff] [blame] | 17 | #include "llvm/Analysis/Passes.h" |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 18 | #include "llvm/Constants.h" |
| 19 | #include "llvm/DerivedTypes.h" |
| 20 | #include "llvm/Function.h" |
| 21 | #include "llvm/GlobalVariable.h" |
Alkis Evlogimenos | eb62bc7 | 2004-07-29 12:17:34 +0000 | [diff] [blame] | 22 | #include "llvm/Instructions.h" |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 23 | #include "llvm/Pass.h" |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 24 | #include "llvm/Target/TargetData.h" |
Chris Lattner | a77600e | 2007-02-10 22:15:31 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/SmallVector.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 26 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 27 | #include "llvm/Support/GetElementPtrTypeIterator.h" |
| 28 | #include "llvm/Support/ManagedStatic.h" |
Alkis Evlogimenos | 20aa474 | 2004-09-03 18:19:51 +0000 | [diff] [blame] | 29 | #include <algorithm> |
Chris Lattner | ec4e808 | 2003-11-25 18:33:40 +0000 | [diff] [blame] | 30 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 31 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 32 | namespace { |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 33 | /// NoAA - This class implements the -no-aa pass, which always returns "I |
| 34 | /// don't know" for alias queries. NoAA is unlike other alias analysis |
| 35 | /// implementations, in that it does not chain to a previous analysis. As |
| 36 | /// such it doesn't follow many of the rules that other alias analyses must. |
| 37 | /// |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 38 | struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis { |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 39 | static char ID; // Class identification, replacement for typeinfo |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 40 | NoAA() : ImmutablePass((intptr_t)&ID) {} |
Dan Gohman | a6900c7 | 2007-07-02 14:53:37 +0000 | [diff] [blame] | 41 | explicit NoAA(intptr_t PID) : ImmutablePass(PID) { } |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 42 | |
Chris Lattner | 689835a | 2004-06-19 08:05:58 +0000 | [diff] [blame] | 43 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 44 | AU.addRequired<TargetData>(); |
| 45 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 46 | |
Chris Lattner | 689835a | 2004-06-19 08:05:58 +0000 | [diff] [blame] | 47 | virtual void initializePass() { |
| 48 | TD = &getAnalysis<TargetData>(); |
| 49 | } |
| 50 | |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 51 | virtual AliasResult alias(const Value *V1, unsigned V1Size, |
| 52 | const Value *V2, unsigned V2Size) { |
| 53 | return MayAlias; |
| 54 | } |
| 55 | |
Chris Lattner | 5226f6a | 2004-12-15 17:13:24 +0000 | [diff] [blame] | 56 | virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, |
| 57 | std::vector<PointerAccessInfo> *Info) { |
Chris Lattner | 0af024c | 2004-12-15 07:22:13 +0000 | [diff] [blame] | 58 | return UnknownModRefBehavior; |
| 59 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 60 | |
Chris Lattner | 0af024c | 2004-12-15 07:22:13 +0000 | [diff] [blame] | 61 | virtual void getArgumentAccesses(Function *F, CallSite CS, |
| 62 | std::vector<PointerAccessInfo> &Info) { |
| 63 | assert(0 && "This method may not be called on this function!"); |
| 64 | } |
| 65 | |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 66 | virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } |
| 67 | virtual bool pointsToConstantMemory(const Value *P) { return false; } |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 68 | virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { |
| 69 | return ModRef; |
| 70 | } |
| 71 | virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { |
| 72 | return ModRef; |
| 73 | } |
| 74 | virtual bool hasNoModRefInfoForCalls() const { return true; } |
| 75 | |
| 76 | virtual void deleteValue(Value *V) {} |
| 77 | virtual void copyValue(Value *From, Value *To) {} |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 78 | }; |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 79 | |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 80 | // Register this pass... |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 81 | char NoAA::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 82 | RegisterPass<NoAA> |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 83 | U("no-aa", "No Alias Analysis (always returns 'may' alias)"); |
| 84 | |
| 85 | // Declare that we implement the AliasAnalysis interface |
Chris Lattner | a537017 | 2006-08-28 00:42:29 +0000 | [diff] [blame] | 86 | RegisterAnalysisGroup<AliasAnalysis> V(U); |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 87 | } // End of anonymous namespace |
| 88 | |
Jeff Cohen | 534927d | 2005-01-08 22:01:16 +0000 | [diff] [blame] | 89 | ImmutablePass *llvm::createNoAAPass() { return new NoAA(); } |
Chris Lattner | b52f440 | 2004-05-23 21:15:12 +0000 | [diff] [blame] | 90 | |
| 91 | namespace { |
| 92 | /// BasicAliasAnalysis - This is the default alias analysis implementation. |
| 93 | /// Because it doesn't chain to a previous alias analysis (like -no-aa), it |
| 94 | /// derives from the NoAA class. |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 95 | struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA { |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 96 | static char ID; // Class identification, replacement for typeinfo |
Anton Korobeynikov | 03265f9 | 2007-06-18 17:13:29 +0000 | [diff] [blame] | 97 | BasicAliasAnalysis() : NoAA((intptr_t)&ID) { } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 98 | AliasResult alias(const Value *V1, unsigned V1Size, |
| 99 | const Value *V2, unsigned V2Size); |
Chris Lattner | bc1daaa | 2004-01-30 22:17:24 +0000 | [diff] [blame] | 100 | |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 101 | ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); |
Reid Spencer | 4a7ebfa | 2004-12-07 08:11:24 +0000 | [diff] [blame] | 102 | ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { |
| 103 | return NoAA::getModRefInfo(CS1,CS2); |
| 104 | } |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 105 | |
Chris Lattner | e181b94 | 2004-07-27 02:13:55 +0000 | [diff] [blame] | 106 | /// hasNoModRefInfoForCalls - We can provide mod/ref information against |
| 107 | /// non-escaping allocations. |
| 108 | virtual bool hasNoModRefInfoForCalls() const { return false; } |
Chris Lattner | 65585aa | 2004-04-11 16:43:07 +0000 | [diff] [blame] | 109 | |
Chris Lattner | bc1daaa | 2004-01-30 22:17:24 +0000 | [diff] [blame] | 110 | /// pointsToConstantMemory - Chase pointers until we find a (constant |
| 111 | /// global) or not. |
| 112 | bool pointsToConstantMemory(const Value *P); |
| 113 | |
Chris Lattner | 0af024c | 2004-12-15 07:22:13 +0000 | [diff] [blame] | 114 | virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, |
Chris Lattner | 241607d | 2007-01-14 05:57:53 +0000 | [diff] [blame] | 115 | std::vector<PointerAccessInfo> *Info); |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 116 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 117 | private: |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 118 | // CheckGEPInstructions - Check two GEP instructions with known |
| 119 | // must-aliasing base pointers. This checks to see if the index expressions |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 120 | // preclude the pointers from aliasing... |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 121 | AliasResult |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 122 | CheckGEPInstructions(const Type* BasePtr1Ty, |
| 123 | Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size, |
| 124 | const Type *BasePtr2Ty, |
| 125 | Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size); |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 126 | }; |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 127 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 128 | // Register this pass... |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 129 | char BasicAliasAnalysis::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 130 | RegisterPass<BasicAliasAnalysis> |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 131 | X("basicaa", "Basic Alias Analysis (default AA impl)"); |
| 132 | |
| 133 | // Declare that we implement the AliasAnalysis interface |
Chris Lattner | a537017 | 2006-08-28 00:42:29 +0000 | [diff] [blame] | 134 | RegisterAnalysisGroup<AliasAnalysis, true> Y(X); |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 135 | } // End of anonymous namespace |
| 136 | |
Jeff Cohen | 534927d | 2005-01-08 22:01:16 +0000 | [diff] [blame] | 137 | ImmutablePass *llvm::createBasicAliasAnalysisPass() { |
| 138 | return new BasicAliasAnalysis(); |
| 139 | } |
| 140 | |
Chris Lattner | c182003 | 2003-09-20 03:08:47 +0000 | [diff] [blame] | 141 | // getUnderlyingObject - This traverses the use chain to figure out what object |
| 142 | // the specified value points to. If the value points to, or is derived from, a |
| 143 | // unique object or an argument, return it. |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 144 | static const Value *getUnderlyingObject(const Value *V) { |
| 145 | if (!isa<PointerType>(V->getType())) return 0; |
| 146 | |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 147 | // If we are at some type of object, return it. GlobalValues and Allocations |
| 148 | // have unique addresses. |
| 149 | if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V)) |
| 150 | return V; |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 151 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 152 | // Traverse through different addressing mechanisms... |
| 153 | if (const Instruction *I = dyn_cast<Instruction>(V)) { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 154 | if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 155 | return getUnderlyingObject(I->getOperand(0)); |
Chris Lattner | 388f669 | 2003-06-17 15:25:37 +0000 | [diff] [blame] | 156 | } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 157 | if (CE->getOpcode() == Instruction::BitCast || |
Chris Lattner | 388f669 | 2003-06-17 15:25:37 +0000 | [diff] [blame] | 158 | CE->getOpcode() == Instruction::GetElementPtr) |
| 159 | return getUnderlyingObject(CE->getOperand(0)); |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 160 | } |
| 161 | return 0; |
| 162 | } |
| 163 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 164 | static const User *isGEP(const Value *V) { |
| 165 | if (isa<GetElementPtrInst>(V) || |
| 166 | (isa<ConstantExpr>(V) && |
| 167 | cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr)) |
| 168 | return cast<User>(V); |
| 169 | return 0; |
| 170 | } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 171 | |
Chris Lattner | a77600e | 2007-02-10 22:15:31 +0000 | [diff] [blame] | 172 | static const Value *GetGEPOperands(const Value *V, |
| 173 | SmallVector<Value*, 16> &GEPOps){ |
Chris Lattner | 4a83088 | 2003-12-11 23:20:16 +0000 | [diff] [blame] | 174 | assert(GEPOps.empty() && "Expect empty list to populate!"); |
| 175 | GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, |
| 176 | cast<User>(V)->op_end()); |
| 177 | |
| 178 | // Accumulate all of the chained indexes into the operand array |
| 179 | V = cast<User>(V)->getOperand(0); |
| 180 | |
| 181 | while (const User *G = isGEP(V)) { |
Reid Spencer | e840434 | 2004-07-18 00:18:30 +0000 | [diff] [blame] | 182 | if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || |
Chris Lattner | 4a83088 | 2003-12-11 23:20:16 +0000 | [diff] [blame] | 183 | !cast<Constant>(GEPOps[0])->isNullValue()) |
| 184 | break; // Don't handle folding arbitrary pointer offsets yet... |
| 185 | GEPOps.erase(GEPOps.begin()); // Drop the zero index |
| 186 | GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); |
| 187 | V = G->getOperand(0); |
| 188 | } |
| 189 | return V; |
| 190 | } |
| 191 | |
Chris Lattner | bc1daaa | 2004-01-30 22:17:24 +0000 | [diff] [blame] | 192 | /// pointsToConstantMemory - Chase pointers until we find a (constant |
| 193 | /// global) or not. |
| 194 | bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { |
Chris Lattner | a4dd674 | 2004-01-30 22:48:02 +0000 | [diff] [blame] | 195 | if (const Value *V = getUnderlyingObject(P)) |
| 196 | if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) |
| 197 | return GV->isConstant(); |
Chris Lattner | bc1daaa | 2004-01-30 22:17:24 +0000 | [diff] [blame] | 198 | return false; |
| 199 | } |
Chris Lattner | 4a83088 | 2003-12-11 23:20:16 +0000 | [diff] [blame] | 200 | |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 201 | // Determine if an AllocationInst instruction escapes from the function it is |
| 202 | // contained in. If it does not escape, there is no way for another function to |
| 203 | // mod/ref it. We do this by looking at its uses and determining if the uses |
| 204 | // can escape (recursively). |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 205 | static bool AddressMightEscape(const Value *V) { |
| 206 | for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); |
| 207 | UI != E; ++UI) { |
| 208 | const Instruction *I = cast<Instruction>(*UI); |
| 209 | switch (I->getOpcode()) { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 210 | case Instruction::Load: |
| 211 | break; //next use. |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 212 | case Instruction::Store: |
| 213 | if (I->getOperand(0) == V) |
| 214 | return true; // Escapes if the pointer is stored. |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 215 | break; // next use. |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 216 | case Instruction::GetElementPtr: |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 217 | if (AddressMightEscape(I)) |
| 218 | return true; |
| 219 | case Instruction::BitCast: |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 220 | if (!isa<PointerType>(I->getType())) |
| 221 | return true; |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 222 | if (AddressMightEscape(I)) |
| 223 | return true; |
| 224 | break; // next use |
Chris Lattner | db5b80a | 2004-07-27 02:18:52 +0000 | [diff] [blame] | 225 | case Instruction::Ret: |
| 226 | // If returned, the address will escape to calling functions, but no |
| 227 | // callees could modify it. |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 228 | break; // next use |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 229 | default: |
| 230 | return true; |
| 231 | } |
| 232 | } |
| 233 | return false; |
| 234 | } |
| 235 | |
| 236 | // getModRefInfo - Check to see if the specified callsite can clobber the |
| 237 | // specified memory object. Since we only look at local properties of this |
| 238 | // function, we really can't say much about this query. We do, however, use |
| 239 | // simple "address taken" analysis on local objects. |
| 240 | // |
| 241 | AliasAnalysis::ModRefResult |
| 242 | BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { |
Reid Spencer | e840434 | 2004-07-18 00:18:30 +0000 | [diff] [blame] | 243 | if (!isa<Constant>(P)) |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 244 | if (const AllocationInst *AI = |
Chris Lattner | 7a82ba0 | 2004-03-12 23:12:55 +0000 | [diff] [blame] | 245 | dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) { |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 246 | // Okay, the pointer is to a stack allocated object. If we can prove that |
| 247 | // the pointer never "escapes", then we know the call cannot clobber it, |
| 248 | // because it simply can't get its address. |
| 249 | if (!AddressMightEscape(AI)) |
| 250 | return NoModRef; |
Chris Lattner | 42e3c81 | 2005-05-08 23:58:12 +0000 | [diff] [blame] | 251 | |
| 252 | // If this is a tail call and P points to a stack location, we know that |
| 253 | // the tail call cannot access or modify the local stack. |
| 254 | if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) |
| 255 | if (CI->isTailCall() && isa<AllocaInst>(AI)) |
| 256 | return NoModRef; |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 257 | } |
| 258 | |
Chris Lattner | bbcc147 | 2004-03-15 04:18:28 +0000 | [diff] [blame] | 259 | // The AliasAnalysis base class has some smarts, lets use them. |
| 260 | return AliasAnalysis::getModRefInfo(CS, P, Size); |
Chris Lattner | 04b7593 | 2004-03-12 22:39:00 +0000 | [diff] [blame] | 261 | } |
| 262 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 263 | // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such |
| 264 | // as array references. Note that this function is heavily tail recursive. |
| 265 | // Hopefully we have a smart C++ compiler. :) |
| 266 | // |
| 267 | AliasAnalysis::AliasResult |
| 268 | BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, |
| 269 | const Value *V2, unsigned V2Size) { |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 270 | // Strip off any constant expression casts if they exist |
| 271 | if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 272 | if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 273 | V1 = CE->getOperand(0); |
| 274 | if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 275 | if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 276 | V2 = CE->getOperand(0); |
| 277 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 278 | // Are we checking for alias of the same value? |
| 279 | if (V1 == V2) return MustAlias; |
| 280 | |
| 281 | if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && |
Reid Spencer | c5b206b | 2006-12-31 05:48:39 +0000 | [diff] [blame] | 282 | V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty) |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 283 | return NoAlias; // Scalars cannot alias each other |
| 284 | |
| 285 | // Strip off cast instructions... |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 286 | if (const BitCastInst *I = dyn_cast<BitCastInst>(V1)) |
Chris Lattner | 241607d | 2007-01-14 05:57:53 +0000 | [diff] [blame] | 287 | return alias(I->getOperand(0), V1Size, V2, V2Size); |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 288 | if (const BitCastInst *I = dyn_cast<BitCastInst>(V2)) |
Chris Lattner | 241607d | 2007-01-14 05:57:53 +0000 | [diff] [blame] | 289 | return alias(V1, V1Size, I->getOperand(0), V2Size); |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 290 | |
| 291 | // Figure out what objects these things are pointing to if we can... |
| 292 | const Value *O1 = getUnderlyingObject(V1); |
| 293 | const Value *O2 = getUnderlyingObject(V2); |
| 294 | |
Misha Brukman | 2f2d065 | 2003-09-11 18:14:24 +0000 | [diff] [blame] | 295 | // Pointing at a discernible object? |
Chris Lattner | 0a1ac90 | 2004-11-26 19:20:01 +0000 | [diff] [blame] | 296 | if (O1) { |
| 297 | if (O2) { |
| 298 | if (isa<Argument>(O1)) { |
| 299 | // Incoming argument cannot alias locally allocated object! |
| 300 | if (isa<AllocationInst>(O2)) return NoAlias; |
| 301 | // Otherwise, nothing is known... |
| 302 | } else if (isa<Argument>(O2)) { |
| 303 | // Incoming argument cannot alias locally allocated object! |
| 304 | if (isa<AllocationInst>(O1)) return NoAlias; |
| 305 | // Otherwise, nothing is known... |
| 306 | } else if (O1 != O2) { |
| 307 | // If they are two different objects, we know that we have no alias... |
| 308 | return NoAlias; |
| 309 | } |
| 310 | |
| 311 | // If they are the same object, they we can look at the indexes. If they |
| 312 | // index off of the object is the same for both pointers, they must alias. |
| 313 | // If they are provably different, they must not alias. Otherwise, we |
| 314 | // can't tell anything. |
Chris Lattner | c182003 | 2003-09-20 03:08:47 +0000 | [diff] [blame] | 315 | } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 316 | |
Chris Lattner | 0a1ac90 | 2004-11-26 19:20:01 +0000 | [diff] [blame] | 317 | |
| 318 | if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) |
| 319 | return NoAlias; // Unique values don't alias null |
| 320 | |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 321 | if (isa<GlobalVariable>(O1) || |
Chris Lattner | 50bc9ef | 2005-03-09 16:29:52 +0000 | [diff] [blame] | 322 | (isa<AllocationInst>(O1) && |
| 323 | !cast<AllocationInst>(O1)->isArrayAllocation())) |
Chris Lattner | 4e61676 | 2004-11-26 20:01:48 +0000 | [diff] [blame] | 324 | if (cast<PointerType>(O1->getType())->getElementType()->isSized()) { |
Chris Lattner | 0a1ac90 | 2004-11-26 19:20:01 +0000 | [diff] [blame] | 325 | // If the size of the other access is larger than the total size of the |
Chris Lattner | 4e61676 | 2004-11-26 20:01:48 +0000 | [diff] [blame] | 326 | // global/alloca/malloc, it cannot be accessing the global (it's |
| 327 | // undefined to load or store bytes before or after an object). |
| 328 | const Type *ElTy = cast<PointerType>(O1->getType())->getElementType(); |
| 329 | unsigned GlobalSize = getTargetData().getTypeSize(ElTy); |
Chris Lattner | eaf8f9c | 2004-11-28 20:30:15 +0000 | [diff] [blame] | 330 | if (GlobalSize < V2Size && V2Size != ~0U) |
Chris Lattner | 0a1ac90 | 2004-11-26 19:20:01 +0000 | [diff] [blame] | 331 | return NoAlias; |
| 332 | } |
| 333 | } |
| 334 | |
| 335 | if (O2) { |
| 336 | if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) |
| 337 | return NoAlias; // Unique values don't alias null |
| 338 | |
Chris Lattner | 50bc9ef | 2005-03-09 16:29:52 +0000 | [diff] [blame] | 339 | if (isa<GlobalVariable>(O2) || |
| 340 | (isa<AllocationInst>(O2) && |
| 341 | !cast<AllocationInst>(O2)->isArrayAllocation())) |
Chris Lattner | 4e61676 | 2004-11-26 20:01:48 +0000 | [diff] [blame] | 342 | if (cast<PointerType>(O2->getType())->getElementType()->isSized()) { |
Chris Lattner | 0a1ac90 | 2004-11-26 19:20:01 +0000 | [diff] [blame] | 343 | // If the size of the other access is larger than the total size of the |
Chris Lattner | 4e61676 | 2004-11-26 20:01:48 +0000 | [diff] [blame] | 344 | // global/alloca/malloc, it cannot be accessing the object (it's |
| 345 | // undefined to load or store bytes before or after an object). |
| 346 | const Type *ElTy = cast<PointerType>(O2->getType())->getElementType(); |
| 347 | unsigned GlobalSize = getTargetData().getTypeSize(ElTy); |
Chris Lattner | eaf8f9c | 2004-11-28 20:30:15 +0000 | [diff] [blame] | 348 | if (GlobalSize < V1Size && V1Size != ~0U) |
Chris Lattner | 0a1ac90 | 2004-11-26 19:20:01 +0000 | [diff] [blame] | 349 | return NoAlias; |
| 350 | } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 351 | } |
| 352 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 353 | // If we have two gep instructions with must-alias'ing base pointers, figure |
| 354 | // out if the indexes to the GEP tell us anything about the derived pointer. |
| 355 | // Note that we also handle chains of getelementptr instructions as well as |
| 356 | // constant expression getelementptrs here. |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 357 | // |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 358 | if (isGEP(V1) && isGEP(V2)) { |
| 359 | // Drill down into the first non-gep value, to test for must-aliasing of |
| 360 | // the base pointers. |
| 361 | const Value *BasePtr1 = V1, *BasePtr2 = V2; |
| 362 | do { |
| 363 | BasePtr1 = cast<User>(BasePtr1)->getOperand(0); |
| 364 | } while (isGEP(BasePtr1) && |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 365 | cast<User>(BasePtr1)->getOperand(1) == |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 366 | Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType())); |
| 367 | do { |
| 368 | BasePtr2 = cast<User>(BasePtr2)->getOperand(0); |
| 369 | } while (isGEP(BasePtr2) && |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 370 | cast<User>(BasePtr2)->getOperand(1) == |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 371 | Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType())); |
| 372 | |
| 373 | // Do the base pointers alias? |
Chris Lattner | 241607d | 2007-01-14 05:57:53 +0000 | [diff] [blame] | 374 | AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U); |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 375 | if (BaseAlias == NoAlias) return NoAlias; |
| 376 | if (BaseAlias == MustAlias) { |
| 377 | // If the base pointers alias each other exactly, check to see if we can |
| 378 | // figure out anything about the resultant pointers, to try to prove |
| 379 | // non-aliasing. |
| 380 | |
| 381 | // Collect all of the chained GEP operands together into one simple place |
Chris Lattner | a77600e | 2007-02-10 22:15:31 +0000 | [diff] [blame] | 382 | SmallVector<Value*, 16> GEP1Ops, GEP2Ops; |
Chris Lattner | 4a83088 | 2003-12-11 23:20:16 +0000 | [diff] [blame] | 383 | BasePtr1 = GetGEPOperands(V1, GEP1Ops); |
| 384 | BasePtr2 = GetGEPOperands(V2, GEP2Ops); |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 385 | |
Chris Lattner | 730b1ad | 2004-07-29 07:56:39 +0000 | [diff] [blame] | 386 | // If GetGEPOperands were able to fold to the same must-aliased pointer, |
| 387 | // do the comparison. |
| 388 | if (BasePtr1 == BasePtr2) { |
| 389 | AliasResult GAlias = |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 390 | CheckGEPInstructions(BasePtr1->getType(), |
| 391 | &GEP1Ops[0], GEP1Ops.size(), V1Size, |
| 392 | BasePtr2->getType(), |
| 393 | &GEP2Ops[0], GEP2Ops.size(), V2Size); |
Chris Lattner | 730b1ad | 2004-07-29 07:56:39 +0000 | [diff] [blame] | 394 | if (GAlias != MayAlias) |
| 395 | return GAlias; |
| 396 | } |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 397 | } |
| 398 | } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 399 | |
| 400 | // Check to see if these two pointers are related by a getelementptr |
| 401 | // instruction. If one pointer is a GEP with a non-zero index of the other |
| 402 | // pointer, we know they cannot alias. |
| 403 | // |
Chris Lattner | 4a83088 | 2003-12-11 23:20:16 +0000 | [diff] [blame] | 404 | if (isGEP(V2)) { |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 405 | std::swap(V1, V2); |
| 406 | std::swap(V1Size, V2Size); |
| 407 | } |
| 408 | |
Chris Lattner | c330ee6 | 2003-02-26 21:57:23 +0000 | [diff] [blame] | 409 | if (V1Size != ~0U && V2Size != ~0U) |
Reid Spencer | 3ed469c | 2006-11-02 20:25:50 +0000 | [diff] [blame] | 410 | if (isGEP(V1)) { |
Chris Lattner | a77600e | 2007-02-10 22:15:31 +0000 | [diff] [blame] | 411 | SmallVector<Value*, 16> GEPOperands; |
Chris Lattner | 4a83088 | 2003-12-11 23:20:16 +0000 | [diff] [blame] | 412 | const Value *BasePtr = GetGEPOperands(V1, GEPOperands); |
| 413 | |
| 414 | AliasResult R = alias(BasePtr, V1Size, V2, V2Size); |
Chris Lattner | c330ee6 | 2003-02-26 21:57:23 +0000 | [diff] [blame] | 415 | if (R == MustAlias) { |
| 416 | // If there is at least one non-zero constant index, we know they cannot |
| 417 | // alias. |
| 418 | bool ConstantFound = false; |
Chris Lattner | 88d3e03 | 2003-12-11 06:02:00 +0000 | [diff] [blame] | 419 | bool AllZerosFound = true; |
Chris Lattner | 4a83088 | 2003-12-11 23:20:16 +0000 | [diff] [blame] | 420 | for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) |
| 421 | if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { |
Chris Lattner | c330ee6 | 2003-02-26 21:57:23 +0000 | [diff] [blame] | 422 | if (!C->isNullValue()) { |
| 423 | ConstantFound = true; |
Chris Lattner | c54735e | 2003-12-11 06:06:28 +0000 | [diff] [blame] | 424 | AllZerosFound = false; |
Chris Lattner | c330ee6 | 2003-02-26 21:57:23 +0000 | [diff] [blame] | 425 | break; |
Chris Lattner | 88d3e03 | 2003-12-11 06:02:00 +0000 | [diff] [blame] | 426 | } |
| 427 | } else { |
| 428 | AllZerosFound = false; |
Chris Lattner | c330ee6 | 2003-02-26 21:57:23 +0000 | [diff] [blame] | 429 | } |
Chris Lattner | 88d3e03 | 2003-12-11 06:02:00 +0000 | [diff] [blame] | 430 | |
| 431 | // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases |
| 432 | // the ptr, the end result is a must alias also. |
| 433 | if (AllZerosFound) |
| 434 | return MustAlias; |
| 435 | |
Chris Lattner | c330ee6 | 2003-02-26 21:57:23 +0000 | [diff] [blame] | 436 | if (ConstantFound) { |
| 437 | if (V2Size <= 1 && V1Size <= 1) // Just pointer check? |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 438 | return NoAlias; |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 439 | |
Chris Lattner | c330ee6 | 2003-02-26 21:57:23 +0000 | [diff] [blame] | 440 | // Otherwise we have to check to see that the distance is more than |
| 441 | // the size of the argument... build an index vector that is equal to |
| 442 | // the arguments provided, except substitute 0's for any variable |
| 443 | // indexes we find... |
Alkis Evlogimenos | a95cf30 | 2004-12-08 23:42:11 +0000 | [diff] [blame] | 444 | if (cast<PointerType>( |
| 445 | BasePtr->getType())->getElementType()->isSized()) { |
| 446 | for (unsigned i = 0; i != GEPOperands.size(); ++i) |
Chris Lattner | 0bb3831 | 2007-01-12 18:20:48 +0000 | [diff] [blame] | 447 | if (!isa<ConstantInt>(GEPOperands[i])) |
Alkis Evlogimenos | a95cf30 | 2004-12-08 23:42:11 +0000 | [diff] [blame] | 448 | GEPOperands[i] = |
| 449 | Constant::getNullValue(GEPOperands[i]->getType()); |
| 450 | int64_t Offset = |
Chris Lattner | 829621c | 2007-02-10 20:35:22 +0000 | [diff] [blame] | 451 | getTargetData().getIndexedOffset(BasePtr->getType(), |
| 452 | &GEPOperands[0], |
| 453 | GEPOperands.size()); |
Alkis Evlogimenos | a95cf30 | 2004-12-08 23:42:11 +0000 | [diff] [blame] | 454 | |
| 455 | if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) |
| 456 | return NoAlias; |
| 457 | } |
Chris Lattner | c330ee6 | 2003-02-26 21:57:23 +0000 | [diff] [blame] | 458 | } |
| 459 | } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 460 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 461 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 462 | return MayAlias; |
| 463 | } |
| 464 | |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 465 | // This function is used to determin if the indices of two GEP instructions are |
| 466 | // equal. V1 and V2 are the indices. |
| 467 | static bool IndexOperandsEqual(Value *V1, Value *V2) { |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 468 | if (V1->getType() == V2->getType()) |
| 469 | return V1 == V2; |
| 470 | if (Constant *C1 = dyn_cast<Constant>(V1)) |
| 471 | if (Constant *C2 = dyn_cast<Constant>(V2)) { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 472 | // Sign extend the constants to long types, if necessary |
Reid Spencer | c5b206b | 2006-12-31 05:48:39 +0000 | [diff] [blame] | 473 | if (C1->getType() != Type::Int64Ty) |
| 474 | C1 = ConstantExpr::getSExt(C1, Type::Int64Ty); |
| 475 | if (C2->getType() != Type::Int64Ty) |
| 476 | C2 = ConstantExpr::getSExt(C2, Type::Int64Ty); |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 477 | return C1 == C2; |
| 478 | } |
| 479 | return false; |
| 480 | } |
| 481 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 482 | /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing |
| 483 | /// base pointers. This checks to see if the index expressions preclude the |
| 484 | /// pointers from aliasing... |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 485 | AliasAnalysis::AliasResult |
| 486 | BasicAliasAnalysis::CheckGEPInstructions( |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 487 | const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S, |
| 488 | const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) { |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 489 | // We currently can't handle the case when the base pointers have different |
| 490 | // primitive types. Since this is uncommon anyway, we are happy being |
| 491 | // extremely conservative. |
| 492 | if (BasePtr1Ty != BasePtr2Ty) |
| 493 | return MayAlias; |
| 494 | |
Alkis Evlogimenos | c49741d | 2004-12-08 23:56:15 +0000 | [diff] [blame] | 495 | const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 496 | |
| 497 | // Find the (possibly empty) initial sequence of equal values... which are not |
| 498 | // necessarily constants. |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 499 | unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops; |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 500 | unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); |
| 501 | unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); |
| 502 | unsigned UnequalOper = 0; |
| 503 | while (UnequalOper != MinOperands && |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 504 | IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 505 | // Advance through the type as we go... |
| 506 | ++UnequalOper; |
| 507 | if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) |
| 508 | BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); |
| 509 | else { |
| 510 | // If all operands equal each other, then the derived pointers must |
| 511 | // alias each other... |
| 512 | BasePtr1Ty = 0; |
| 513 | assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && |
| 514 | "Ran out of type nesting, but not out of operands?"); |
| 515 | return MustAlias; |
Chris Lattner | 920bd79 | 2003-06-02 05:42:39 +0000 | [diff] [blame] | 516 | } |
| 517 | } |
Chris Lattner | 920bd79 | 2003-06-02 05:42:39 +0000 | [diff] [blame] | 518 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 519 | // If we have seen all constant operands, and run out of indexes on one of the |
| 520 | // getelementptrs, check to see if the tail of the leftover one is all zeros. |
| 521 | // If so, return mustalias. |
Chris Lattner | 4a83088 | 2003-12-11 23:20:16 +0000 | [diff] [blame] | 522 | if (UnequalOper == MinOperands) { |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 523 | if (NumGEP1Ops < NumGEP2Ops) { |
| 524 | std::swap(GEP1Ops, GEP2Ops); |
| 525 | std::swap(NumGEP1Ops, NumGEP2Ops); |
| 526 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 527 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 528 | bool AllAreZeros = true; |
| 529 | for (unsigned i = UnequalOper; i != MaxOperands; ++i) |
Chris Lattner | a35339d | 2004-10-16 16:07:10 +0000 | [diff] [blame] | 530 | if (!isa<Constant>(GEP1Ops[i]) || |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 531 | !cast<Constant>(GEP1Ops[i])->isNullValue()) { |
| 532 | AllAreZeros = false; |
| 533 | break; |
| 534 | } |
| 535 | if (AllAreZeros) return MustAlias; |
| 536 | } |
| 537 | |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 538 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 539 | // So now we know that the indexes derived from the base pointers, |
| 540 | // which are known to alias, are different. We can still determine a |
| 541 | // no-alias result if there are differing constant pairs in the index |
| 542 | // chain. For example: |
| 543 | // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) |
| 544 | // |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 545 | // We have to be careful here about array accesses. In particular, consider: |
| 546 | // A[1][0] vs A[0][i] |
| 547 | // In this case, we don't *know* that the array will be accessed in bounds: |
| 548 | // the index could even be negative. Because of this, we have to |
| 549 | // conservatively *give up* and return may alias. We disregard differing |
| 550 | // array subscripts that are followed by a variable index without going |
| 551 | // through a struct. |
| 552 | // |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 553 | unsigned SizeMax = std::max(G1S, G2S); |
Chris Lattner | eaf8f9c | 2004-11-28 20:30:15 +0000 | [diff] [blame] | 554 | if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. |
Chris Lattner | 920bd79 | 2003-06-02 05:42:39 +0000 | [diff] [blame] | 555 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 556 | // Scan for the first operand that is constant and unequal in the |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 557 | // two getelementptrs... |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 558 | unsigned FirstConstantOper = UnequalOper; |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 559 | for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { |
| 560 | const Value *G1Oper = GEP1Ops[FirstConstantOper]; |
| 561 | const Value *G2Oper = GEP2Ops[FirstConstantOper]; |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 562 | |
Chris Lattner | 6eb88d4 | 2004-01-12 17:57:32 +0000 | [diff] [blame] | 563 | if (G1Oper != G2Oper) // Found non-equal constant indexes... |
Chris Lattner | a35339d | 2004-10-16 16:07:10 +0000 | [diff] [blame] | 564 | if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) |
| 565 | if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 566 | if (G1OC->getType() != G2OC->getType()) { |
| 567 | // Sign extend both operands to long. |
Reid Spencer | c5b206b | 2006-12-31 05:48:39 +0000 | [diff] [blame] | 568 | if (G1OC->getType() != Type::Int64Ty) |
| 569 | G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty); |
| 570 | if (G2OC->getType() != Type::Int64Ty) |
| 571 | G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty); |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 572 | GEP1Ops[FirstConstantOper] = G1OC; |
| 573 | GEP2Ops[FirstConstantOper] = G2OC; |
| 574 | } |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 575 | |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 576 | if (G1OC != G2OC) { |
Dan Gohman | 07a9676 | 2007-07-16 14:29:03 +0000 | [diff] [blame] | 577 | // Handle the "be careful" case above: if this is an array/vector |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 578 | // subscript, scan for a subsequent variable array index. |
Chris Lattner | 7765d71 | 2006-11-03 21:58:48 +0000 | [diff] [blame] | 579 | if (isa<SequentialType>(BasePtr1Ty)) { |
| 580 | const Type *NextTy = |
| 581 | cast<SequentialType>(BasePtr1Ty)->getElementType(); |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 582 | bool isBadCase = false; |
| 583 | |
| 584 | for (unsigned Idx = FirstConstantOper+1; |
Chris Lattner | 7765d71 | 2006-11-03 21:58:48 +0000 | [diff] [blame] | 585 | Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 586 | const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; |
| 587 | if (!isa<Constant>(V1) || !isa<Constant>(V2)) { |
| 588 | isBadCase = true; |
| 589 | break; |
| 590 | } |
Chris Lattner | 7765d71 | 2006-11-03 21:58:48 +0000 | [diff] [blame] | 591 | NextTy = cast<SequentialType>(NextTy)->getElementType(); |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 592 | } |
| 593 | |
| 594 | if (isBadCase) G1OC = 0; |
| 595 | } |
| 596 | |
Chris Lattner | a35339d | 2004-10-16 16:07:10 +0000 | [diff] [blame] | 597 | // Make sure they are comparable (ie, not constant expressions), and |
| 598 | // make sure the GEP with the smaller leading constant is GEP1. |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 599 | if (G1OC) { |
Reid Spencer | e4d87aa | 2006-12-23 06:05:41 +0000 | [diff] [blame] | 600 | Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, |
| 601 | G1OC, G2OC); |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 602 | if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) { |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 603 | if (CV->getZExtValue()) { // If they are comparable and G2 > G1 |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 604 | std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 605 | std::swap(NumGEP1Ops, NumGEP2Ops); |
| 606 | } |
Chris Lattner | 5a3cf8d | 2006-03-04 02:06:34 +0000 | [diff] [blame] | 607 | break; |
| 608 | } |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 609 | } |
Chris Lattner | 6eb88d4 | 2004-01-12 17:57:32 +0000 | [diff] [blame] | 610 | } |
| 611 | } |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 612 | BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 613 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 614 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 615 | // No shared constant operands, and we ran out of common operands. At this |
| 616 | // point, the GEP instructions have run through all of their operands, and we |
| 617 | // haven't found evidence that there are any deltas between the GEP's. |
| 618 | // However, one GEP may have more operands than the other. If this is the |
Chris Lattner | 28977af | 2004-04-05 01:30:19 +0000 | [diff] [blame] | 619 | // case, there may still be hope. Check this now. |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 620 | if (FirstConstantOper == MinOperands) { |
| 621 | // Make GEP1Ops be the longer one if there is a longer one. |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 622 | if (NumGEP1Ops < NumGEP2Ops) { |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 623 | std::swap(GEP1Ops, GEP2Ops); |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 624 | std::swap(NumGEP1Ops, NumGEP2Ops); |
| 625 | } |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 626 | |
| 627 | // Is there anything to check? |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 628 | if (NumGEP1Ops > MinOperands) { |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 629 | for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 630 | if (isa<ConstantInt>(GEP1Ops[i]) && |
Zhou Sheng | 843f0767 | 2007-04-19 05:39:12 +0000 | [diff] [blame] | 631 | !cast<ConstantInt>(GEP1Ops[i])->isZero()) { |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 632 | // Yup, there's a constant in the tail. Set all variables to |
| 633 | // constants in the GEP instruction to make it suiteable for |
| 634 | // TargetData::getIndexedOffset. |
| 635 | for (i = 0; i != MaxOperands; ++i) |
Chris Lattner | 0bb3831 | 2007-01-12 18:20:48 +0000 | [diff] [blame] | 636 | if (!isa<ConstantInt>(GEP1Ops[i])) |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 637 | GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); |
| 638 | // Okay, now get the offset. This is the relative offset for the full |
| 639 | // instruction. |
| 640 | const TargetData &TD = getTargetData(); |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 641 | int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, |
| 642 | NumGEP1Ops); |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 643 | |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 644 | // Now check without any constants at the end. |
| 645 | int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, |
| 646 | MinOperands); |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 647 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 648 | // If the tail provided a bit enough offset, return noalias! |
| 649 | if ((uint64_t)(Offset2-Offset1) >= SizeMax) |
| 650 | return NoAlias; |
| 651 | } |
| 652 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 653 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 654 | // Couldn't find anything useful. |
| 655 | return MayAlias; |
| 656 | } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 657 | |
| 658 | // If there are non-equal constants arguments, then we can figure |
| 659 | // out a minimum known delta between the two index expressions... at |
| 660 | // this point we know that the first constant index of GEP1 is less |
| 661 | // than the first constant index of GEP2. |
Chris Lattner | 1af55e1 | 2003-11-25 20:10:07 +0000 | [diff] [blame] | 662 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 663 | // Advance BasePtr[12]Ty over this first differing constant operand. |
Chris Lattner | 2cfdd28 | 2006-03-04 21:48:01 +0000 | [diff] [blame] | 664 | BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> |
| 665 | getTypeAtIndex(GEP2Ops[FirstConstantOper]); |
| 666 | BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> |
| 667 | getTypeAtIndex(GEP1Ops[FirstConstantOper]); |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 668 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 669 | // We are going to be using TargetData::getIndexedOffset to determine the |
| 670 | // offset that each of the GEP's is reaching. To do this, we have to convert |
| 671 | // all variable references to constant references. To do this, we convert the |
Chris Lattner | 2cfdd28 | 2006-03-04 21:48:01 +0000 | [diff] [blame] | 672 | // initial sequence of array subscripts into constant zeros to start with. |
| 673 | const Type *ZeroIdxTy = GEPPointerTy; |
| 674 | for (unsigned i = 0; i != FirstConstantOper; ++i) { |
| 675 | if (!isa<StructType>(ZeroIdxTy)) |
Reid Spencer | c5b206b | 2006-12-31 05:48:39 +0000 | [diff] [blame] | 676 | GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty); |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 677 | |
Chris Lattner | 2cfdd28 | 2006-03-04 21:48:01 +0000 | [diff] [blame] | 678 | if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) |
| 679 | ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); |
| 680 | } |
| 681 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 682 | // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 683 | |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 684 | // Loop over the rest of the operands... |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 685 | for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 686 | const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0; |
| 687 | const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0; |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 688 | // If they are equal, use a zero index... |
| 689 | if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { |
Chris Lattner | 0bb3831 | 2007-01-12 18:20:48 +0000 | [diff] [blame] | 690 | if (!isa<ConstantInt>(Op1)) |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 691 | GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); |
| 692 | // Otherwise, just keep the constants we have. |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 693 | } else { |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 694 | if (Op1) { |
| 695 | if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { |
| 696 | // If this is an array index, make sure the array element is in range. |
Chris Lattner | 7765d71 | 2006-11-03 21:58:48 +0000 | [diff] [blame] | 697 | if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 698 | if (Op1C->getZExtValue() >= AT->getNumElements()) |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 699 | return MayAlias; // Be conservative with out-of-range accesses |
Reid Spencer | 9d6565a | 2007-02-15 02:26:10 +0000 | [diff] [blame] | 700 | } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) { |
Chris Lattner | 7765d71 | 2006-11-03 21:58:48 +0000 | [diff] [blame] | 701 | if (Op1C->getZExtValue() >= PT->getNumElements()) |
| 702 | return MayAlias; // Be conservative with out-of-range accesses |
| 703 | } |
| 704 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 705 | } else { |
| 706 | // GEP1 is known to produce a value less than GEP2. To be |
| 707 | // conservatively correct, we must assume the largest possible |
| 708 | // constant is used in this position. This cannot be the initial |
| 709 | // index to the GEP instructions (because we know we have at least one |
| 710 | // element before this one with the different constant arguments), so |
| 711 | // we know that the current index must be into either a struct or |
| 712 | // array. Because we know it's not constant, this cannot be a |
| 713 | // structure index. Because of this, we can calculate the maximum |
| 714 | // value possible. |
| 715 | // |
| 716 | if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) |
Chris Lattner | 241607d | 2007-01-14 05:57:53 +0000 | [diff] [blame] | 717 | GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1); |
Reid Spencer | 9d6565a | 2007-02-15 02:26:10 +0000 | [diff] [blame] | 718 | else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) |
Chris Lattner | 241607d | 2007-01-14 05:57:53 +0000 | [diff] [blame] | 719 | GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1); |
Chris Lattner | 7765d71 | 2006-11-03 21:58:48 +0000 | [diff] [blame] | 720 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 721 | } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 722 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 723 | |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 724 | if (Op2) { |
| 725 | if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { |
| 726 | // If this is an array index, make sure the array element is in range. |
Chris Lattner | 7765d71 | 2006-11-03 21:58:48 +0000 | [diff] [blame] | 727 | if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 728 | if (Op2C->getZExtValue() >= AT->getNumElements()) |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 729 | return MayAlias; // Be conservative with out-of-range accesses |
Reid Spencer | 9d6565a | 2007-02-15 02:26:10 +0000 | [diff] [blame] | 730 | } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) { |
Chris Lattner | 7765d71 | 2006-11-03 21:58:48 +0000 | [diff] [blame] | 731 | if (Op2C->getZExtValue() >= PT->getNumElements()) |
| 732 | return MayAlias; // Be conservative with out-of-range accesses |
| 733 | } |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 734 | } else { // Conservatively assume the minimum value for this index |
| 735 | GEP2Ops[i] = Constant::getNullValue(Op2->getType()); |
| 736 | } |
Chris Lattner | 920bd79 | 2003-06-02 05:42:39 +0000 | [diff] [blame] | 737 | } |
Chris Lattner | b307c88 | 2003-12-11 22:44:13 +0000 | [diff] [blame] | 738 | } |
| 739 | |
| 740 | if (BasePtr1Ty && Op1) { |
| 741 | if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) |
| 742 | BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); |
| 743 | else |
| 744 | BasePtr1Ty = 0; |
| 745 | } |
| 746 | |
| 747 | if (BasePtr2Ty && Op2) { |
| 748 | if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) |
| 749 | BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); |
| 750 | else |
| 751 | BasePtr2Ty = 0; |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 752 | } |
| 753 | } |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 754 | |
Alkis Evlogimenos | c49741d | 2004-12-08 23:56:15 +0000 | [diff] [blame] | 755 | if (GEPPointerTy->getElementType()->isSized()) { |
Chris Lattner | 829621c | 2007-02-10 20:35:22 +0000 | [diff] [blame] | 756 | int64_t Offset1 = |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 757 | getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); |
Chris Lattner | 829621c | 2007-02-10 20:35:22 +0000 | [diff] [blame] | 758 | int64_t Offset2 = |
Chris Lattner | fd1ad3b | 2007-02-10 22:12:53 +0000 | [diff] [blame] | 759 | getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); |
Alkis Evlogimenos | c49741d | 2004-12-08 23:56:15 +0000 | [diff] [blame] | 760 | assert(Offset1<Offset2 && "There is at least one different constant here!"); |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 761 | |
Alkis Evlogimenos | c49741d | 2004-12-08 23:56:15 +0000 | [diff] [blame] | 762 | if ((uint64_t)(Offset2-Offset1) >= SizeMax) { |
Bill Wendling | e815619 | 2006-12-07 01:30:32 +0000 | [diff] [blame] | 763 | //cerr << "Determined that these two GEP's don't alias [" |
| 764 | // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; |
Alkis Evlogimenos | c49741d | 2004-12-08 23:56:15 +0000 | [diff] [blame] | 765 | return NoAlias; |
| 766 | } |
Chris Lattner | d501c13 | 2003-02-26 19:41:54 +0000 | [diff] [blame] | 767 | } |
| 768 | return MayAlias; |
| 769 | } |
| 770 | |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 771 | namespace { |
Reid Spencer | d7d83db | 2007-02-05 23:42:17 +0000 | [diff] [blame] | 772 | struct VISIBILITY_HIDDEN StringCompare { |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 773 | bool operator()(const char *LHS, const char *RHS) { |
| 774 | return strcmp(LHS, RHS) < 0; |
| 775 | } |
| 776 | }; |
| 777 | } |
| 778 | |
| 779 | // Note that this list cannot contain libm functions (such as acos and sqrt) |
| 780 | // that set errno on a domain or other error. |
Chris Lattner | cad2537 | 2006-03-09 22:31:29 +0000 | [diff] [blame] | 781 | static const char *DoesntAccessMemoryFns[] = { |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 782 | "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl", |
| 783 | "trunc", "truncf", "truncl", "ldexp", |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 784 | |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 785 | "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l", |
| 786 | "cbrt", |
Chris Lattner | 5b103c2 | 2005-04-28 21:52:31 +0000 | [diff] [blame] | 787 | "cos", "cosf", "cosl", |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 788 | "exp", "expf", "expl", |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 789 | "hypot", |
Chris Lattner | 5b103c2 | 2005-04-28 21:52:31 +0000 | [diff] [blame] | 790 | "sin", "sinf", "sinl", |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 791 | "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl", |
Chris Lattner | ab466d7 | 2005-08-24 16:58:56 +0000 | [diff] [blame] | 792 | |
| 793 | "floor", "floorf", "floorl", "ceil", "ceilf", "ceill", |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 794 | |
Chris Lattner | bbcc147 | 2004-03-15 04:18:28 +0000 | [diff] [blame] | 795 | // ctype.h |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 796 | "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint" |
| 797 | "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper", |
| 798 | |
Chris Lattner | bbcc147 | 2004-03-15 04:18:28 +0000 | [diff] [blame] | 799 | // wctype.h" |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 800 | "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower", |
| 801 | "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit", |
| 802 | |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 803 | "iswctype", "towctrans", "towlower", "towupper", |
Chris Lattner | bbcc147 | 2004-03-15 04:18:28 +0000 | [diff] [blame] | 804 | |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 805 | "btowc", "wctob", |
Chris Lattner | 002be76 | 2004-03-16 03:41:35 +0000 | [diff] [blame] | 806 | |
| 807 | "isinf", "isnan", "finite", |
| 808 | |
| 809 | // C99 math functions |
| 810 | "copysign", "copysignf", "copysignd", |
| 811 | "nexttoward", "nexttowardf", "nexttowardd", |
| 812 | "nextafter", "nextafterf", "nextafterd", |
| 813 | |
Andrew Lenharth | d3513e0 | 2005-07-11 20:35:20 +0000 | [diff] [blame] | 814 | // ISO C99: |
Chris Lattner | 002be76 | 2004-03-16 03:41:35 +0000 | [diff] [blame] | 815 | "__signbit", "__signbitf", "__signbitl", |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 816 | }; |
| 817 | |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 818 | |
Chris Lattner | cad2537 | 2006-03-09 22:31:29 +0000 | [diff] [blame] | 819 | static const char *OnlyReadsMemoryFns[] = { |
Chris Lattner | 002be76 | 2004-03-16 03:41:35 +0000 | [diff] [blame] | 820 | "atoi", "atol", "atof", "atoll", "atoq", "a64l", |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 821 | "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr", |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 822 | |
| 823 | // Strings |
| 824 | "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp", |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 825 | "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr", |
Chris Lattner | 002be76 | 2004-03-16 03:41:35 +0000 | [diff] [blame] | 826 | "index", "rindex", |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 827 | |
| 828 | // Wide char strings |
| 829 | "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk", |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 830 | "wcsrchr", "wcsspn", "wcsstr", |
Chris Lattner | 002be76 | 2004-03-16 03:41:35 +0000 | [diff] [blame] | 831 | |
| 832 | // glibc |
| 833 | "alphasort", "alphasort64", "versionsort", "versionsort64", |
| 834 | |
| 835 | // C99 |
| 836 | "nan", "nanf", "nand", |
Chris Lattner | b903fc5 | 2004-04-10 06:55:27 +0000 | [diff] [blame] | 837 | |
| 838 | // File I/O |
| 839 | "feof", "ferror", "fileno", |
| 840 | "feof_unlocked", "ferror_unlocked", "fileno_unlocked" |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 841 | }; |
| 842 | |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 843 | static ManagedStatic<std::vector<const char*> > NoMemoryTable; |
| 844 | static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable; |
| 845 | |
| 846 | |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 847 | AliasAnalysis::ModRefBehavior |
Chris Lattner | 0af024c | 2004-12-15 07:22:13 +0000 | [diff] [blame] | 848 | BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS, |
| 849 | std::vector<PointerAccessInfo> *Info) { |
Reid Spencer | 5cbf985 | 2007-01-30 20:08:39 +0000 | [diff] [blame] | 850 | if (!F->isDeclaration()) return UnknownModRefBehavior; |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 851 | |
| 852 | static bool Initialized = false; |
| 853 | if (!Initialized) { |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 854 | NoMemoryTable->insert(NoMemoryTable->end(), |
| 855 | DoesntAccessMemoryFns, |
| 856 | DoesntAccessMemoryFns+ |
Chris Lattner | cad2537 | 2006-03-09 22:31:29 +0000 | [diff] [blame] | 857 | sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0])); |
| 858 | |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 859 | OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(), |
Chris Lattner | cad2537 | 2006-03-09 22:31:29 +0000 | [diff] [blame] | 860 | OnlyReadsMemoryFns, |
| 861 | OnlyReadsMemoryFns+ |
| 862 | sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0])); |
| 863 | #define GET_MODREF_BEHAVIOR |
| 864 | #include "llvm/Intrinsics.gen" |
| 865 | #undef GET_MODREF_BEHAVIOR |
| 866 | |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 867 | // Sort the table the first time through. |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 868 | std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare()); |
| 869 | std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(), |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 870 | StringCompare()); |
| 871 | Initialized = true; |
| 872 | } |
| 873 | |
Chris Lattner | cad2537 | 2006-03-09 22:31:29 +0000 | [diff] [blame] | 874 | std::vector<const char*>::iterator Ptr = |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 875 | std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(), |
Chris Lattner | cad2537 | 2006-03-09 22:31:29 +0000 | [diff] [blame] | 876 | F->getName().c_str(), StringCompare()); |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 877 | if (Ptr != NoMemoryTable->end() && *Ptr == F->getName()) |
Chris Lattner | 0af024c | 2004-12-15 07:22:13 +0000 | [diff] [blame] | 878 | return DoesNotAccessMemory; |
Misha Brukman | 2b37d7c | 2005-04-21 21:13:18 +0000 | [diff] [blame] | 879 | |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 880 | Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(), |
| 881 | OnlyReadsMemoryTable->end(), |
Chris Lattner | 0af024c | 2004-12-15 07:22:13 +0000 | [diff] [blame] | 882 | F->getName().c_str(), StringCompare()); |
Chris Lattner | 90aa839 | 2006-10-04 21:52:35 +0000 | [diff] [blame] | 883 | if (Ptr != OnlyReadsMemoryTable->end() && *Ptr == F->getName()) |
Chris Lattner | 0af024c | 2004-12-15 07:22:13 +0000 | [diff] [blame] | 884 | return OnlyReadsMemory; |
| 885 | |
| 886 | return UnknownModRefBehavior; |
Chris Lattner | 4244bb5 | 2004-03-15 03:36:49 +0000 | [diff] [blame] | 887 | } |
Reid Spencer | 4f1bd9e | 2006-06-07 22:00:26 +0000 | [diff] [blame] | 888 | |
| 889 | // Make sure that anything that uses AliasAnalysis pulls in this file... |
| 890 | DEFINING_FILE_FOR(BasicAliasAnalysis) |