+//===----------------------------------------------------------------------===//
+// Useful predicates
+//===----------------------------------------------------------------------===//
+
+static const User *isGEP(const Value *V) {
+ if (isa<GetElementPtrInst>(V) ||
+ (isa<ConstantExpr>(V) &&
+ cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
+ return cast<User>(V);
+ return 0;
+}
+
+static const Value *GetGEPOperands(const Value *V,
+ SmallVector<Value*, 16> &GEPOps) {
+ assert(GEPOps.empty() && "Expect empty list to populate!");
+ GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
+ cast<User>(V)->op_end());
+
+ // Accumulate all of the chained indexes into the operand array
+ V = cast<User>(V)->getOperand(0);
+
+ while (const User *G = isGEP(V)) {
+ if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
+ !cast<Constant>(GEPOps[0])->isNullValue())
+ break; // Don't handle folding arbitrary pointer offsets yet...
+ GEPOps.erase(GEPOps.begin()); // Drop the zero index
+ GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
+ V = G->getOperand(0);
+ }
+ return V;
+}
+
+/// isKnownNonNull - Return true if we know that the specified value is never
+/// null.
+static bool isKnownNonNull(const Value *V) {
+ // Alloca never returns null, malloc might.
+ if (isa<AllocaInst>(V)) return true;
+
+ // A byval argument is never null.
+ if (const Argument *A = dyn_cast<Argument>(V))
+ return A->hasByValAttr();
+
+ // Global values are not null unless extern weak.
+ if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
+ return !GV->hasExternalWeakLinkage();
+ return false;
+}
+
+/// isNonEscapingLocalObject - Return true if the pointer is to a function-local
+/// object that never escapes from the function.
+static bool isNonEscapingLocalObject(const Value *V) {
+ // If this is a local allocation, check to see if it escapes.
+ if (isa<AllocationInst>(V) || isNoAliasCall(V))
+ return !PointerMayBeCaptured(V, false);
+
+ // If this is an argument that corresponds to a byval or noalias argument,
+ // then it has not escaped before entering the function. Check if it escapes
+ // inside the function.
+ if (const Argument *A = dyn_cast<Argument>(V))
+ if (A->hasByValAttr() || A->hasNoAliasAttr()) {
+ // Don't bother analyzing arguments already known not to escape.
+ if (A->hasNoCaptureAttr())
+ return true;
+ return !PointerMayBeCaptured(V, false);
+ }
+ return false;
+}
+
+
+/// isObjectSmallerThan - Return true if we can prove that the object specified
+/// by V is smaller than Size.
+static bool isObjectSmallerThan(const Value *V, unsigned Size,
+ const TargetData &TD) {
+ const Type *AccessTy;
+ if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
+ AccessTy = GV->getType()->getElementType();
+ } else if (const AllocationInst *AI = dyn_cast<AllocationInst>(V)) {
+ if (!AI->isArrayAllocation())
+ AccessTy = AI->getType()->getElementType();
+ else
+ return false;
+ } else if (const Argument *A = dyn_cast<Argument>(V)) {
+ if (A->hasByValAttr())
+ AccessTy = cast<PointerType>(A->getType())->getElementType();
+ else
+ return false;
+ } else {
+ return false;
+ }
+
+ if (AccessTy->isSized())
+ return TD.getTypeAllocSize(AccessTy) < Size;
+ return false;
+}
+
+//===----------------------------------------------------------------------===//
+// NoAA Pass
+//===----------------------------------------------------------------------===//
+