From f2411744214dad8c71044aac2977ca77e9ebf028 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 20 Jul 2009 17:43:30 +0000 Subject: [PATCH] Revert the addition of hasNoPointerOverflow to GEPOperator. Getelementptrs that are defined to wrap are virtually useless to optimization, and getelementptrs that are undefined on any kind of overflow are too restrictive -- it's difficult to ensure that all intermediate addresses are within bounds. I'm going to take a different approach. Remove a few optimizations that depended on this flag. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76437 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Operator.h | 18 --- lib/Analysis/BasicAliasAnalysis.cpp | 9 +- lib/Analysis/ScalarEvolution.cpp | 13 +-- .../Scalar/InstructionCombining.cpp | 85 +------------- lib/VMCore/Constants.cpp | 7 +- lib/VMCore/Instructions.cpp | 10 -- lib/VMCore/Value.cpp | 2 - test/CodeGen/X86/iv-users-in-other-loops.ll | 4 +- test/Transforms/IndVarSimplify/max-pointer.ll | 106 ------------------ test/Transforms/InstCombine/add2.ll | 24 +--- test/Transforms/InstCombine/add3.ll | 21 ++++ test/Transforms/InstCombine/cast_ptr.ll | 12 +- 12 files changed, 44 insertions(+), 267 deletions(-) create mode 100644 test/Transforms/InstCombine/add3.ll diff --git a/include/llvm/Operator.h b/include/llvm/Operator.h index 2f9f9ca12ce..a26d9400796 100644 --- a/include/llvm/Operator.h +++ b/include/llvm/Operator.h @@ -171,24 +171,6 @@ public: return true; } - /// hasNoPointerOverflow - Return true if this GetElementPtr is known to - /// never have overflow in the pointer addition portions of its effective - /// computation. GetElementPtr computation involves several phases; - /// overflow can be considered to occur in index typecasting, array index - /// scaling, and the addition of the base pointer with offsets. This flag - /// only applies to the last of these. The operands are added to the base - /// pointer one at a time from left to right. This function returns false - /// if any of these additions results in an address value which is not - /// known to be within the allocated address space that the base pointer - /// points into, or within one element (of the original allocation) past - /// the end. - bool hasNoPointerOverflow() const { - return SubclassOptionalData & (1 << 0); - } - void setHasNoPointerOverflow(bool B) { - SubclassOptionalData = (SubclassOptionalData & ~(1 << 0)) | (B << 0); - } - // Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const GEPOperator *) { return true; } static inline bool classof(const GetElementPtrInst *) { return true; } diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index dcb5903a14e..308c69a87ee 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -38,13 +38,8 @@ using namespace llvm; // Useful predicates //===----------------------------------------------------------------------===// -static const User *isGEP(const Value *V) { - if (const GEPOperator *GEP = dyn_cast(V)) - // For the purposes of BasicAliasAnalysis, if the GEP has overflow it - // could do crazy things. - if (GEP->hasNoPointerOverflow()) - return GEP; - return 0; +static const GEPOperator *isGEP(const Value *V) { + return dyn_cast(V); } static const Value *GetGEPOperands(const Value *V, diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 6c23f401c5b..aadba9d9d3d 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -2938,15 +2938,10 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { return getSCEV(U->getOperand(0)); break; - case Instruction::IntToPtr: - if (!TD) break; // Without TD we can't analyze pointers. - return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)), - TD->getIntPtrType()); - - case Instruction::PtrToInt: - if (!TD) break; // Without TD we can't analyze pointers. - return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)), - U->getType()); + // It's tempting to handle inttoptr and ptrtoint, however this can + // lead to pointer expressions which cannot be expanded to GEPs + // (because they may overflow). For now, the only pointer-typed + // expressions we handle are GEPs and address literals. case Instruction::GetElementPtr: if (!TD) break; // Without TD we can't analyze pointers. diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index 94547b48bb5..d2ed1e14e3f 100644 --- a/lib/Transforms/Scalar/InstructionCombining.cpp +++ b/lib/Transforms/Scalar/InstructionCombining.cpp @@ -2276,31 +2276,6 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { return R; } - // add (cast *A to intptrtype) B -> - // cast (GEP (cast *A to i8*) B) --> intptrtype - { - CastInst *CI = dyn_cast(LHS); - Value *Other = RHS; - if (!CI) { - CI = dyn_cast(RHS); - Other = LHS; - } - if (CI && CI->getType()->isSized() && - (CI->getType()->getScalarSizeInBits() == - TD->getIntPtrType()->getPrimitiveSizeInBits()) - && isa(CI->getOperand(0)->getType())) { - unsigned AS = - cast(CI->getOperand(0)->getType())->getAddressSpace(); - Value *I2 = InsertBitCastBefore(CI->getOperand(0), - Context->getPointerType(Type::Int8Ty, AS), I); - GetElementPtrInst *GEP = GetElementPtrInst::Create(I2, Other, "ctg2"); - // A GEP formed from an arbitrary add may overflow. - cast(GEP)->setHasNoPointerOverflow(false); - I2 = InsertNewInstBefore(GEP, I); - return new PtrToIntInst(I2, CI->getType()); - } - } - // add (select X 0 (sub n A)) A --> select X A n { SelectInst *SI = dyn_cast(LHS); @@ -8914,65 +8889,7 @@ Instruction *InstCombiner::visitIntToPtr(IntToPtrInst &CI) { if (Instruction *I = commonCastTransforms(CI)) return I; - - const Type *DestPointee = cast(CI.getType())->getElementType(); - if (!DestPointee->isSized()) return 0; - - // If this is inttoptr(add (ptrtoint x), cst), try to turn this into a GEP. - ConstantInt *Cst; - Value *X; - if (match(CI.getOperand(0), m_Add(m_Cast(m_Value(X)), - m_ConstantInt(Cst)), *Context)) { - // If the source and destination operands have the same type, see if this - // is a single-index GEP. - if (X->getType() == CI.getType()) { - // Get the size of the pointee type. - uint64_t Size = TD->getTypeAllocSize(DestPointee); - - // Convert the constant to intptr type. - APInt Offset = Cst->getValue(); - Offset.sextOrTrunc(TD->getPointerSizeInBits()); - - // If Offset is evenly divisible by Size, we can do this xform. - if (Size && !APIntOps::srem(Offset, APInt(Offset.getBitWidth(), Size))){ - Offset = APIntOps::sdiv(Offset, APInt(Offset.getBitWidth(), Size)); - GetElementPtrInst *GEP = - GetElementPtrInst::Create(X, Context->getConstantInt(Offset)); - // A gep synthesized from inttoptr+add+ptrtoint must be assumed to - // potentially overflow, in the absense of further analysis. - cast(GEP)->setHasNoPointerOverflow(false); - return GEP; - } - } - // TODO: Could handle other cases, e.g. where add is indexing into field of - // struct etc. - } else if (CI.getOperand(0)->hasOneUse() && - match(CI.getOperand(0), m_Add(m_Value(X), - m_ConstantInt(Cst)), *Context)) { - // Otherwise, if this is inttoptr(add x, cst), try to turn this into an - // "inttoptr+GEP" instead of "add+intptr". - - // Get the size of the pointee type. - uint64_t Size = TD->getTypeAllocSize(DestPointee); - - // Convert the constant to intptr type. - APInt Offset = Cst->getValue(); - Offset.sextOrTrunc(TD->getPointerSizeInBits()); - - // If Offset is evenly divisible by Size, we can do this xform. - if (Size && !APIntOps::srem(Offset, APInt(Offset.getBitWidth(), Size))){ - Offset = APIntOps::sdiv(Offset, APInt(Offset.getBitWidth(), Size)); - - Instruction *P = InsertNewInstBefore(new IntToPtrInst(X, CI.getType(), - "tmp"), CI); - GetElementPtrInst *GEP = - GetElementPtrInst::Create(P, Context->getConstantInt(Offset), "tmp"); - // A gep synthesized from inttoptr+add+ptrtoint must be assumed to - // potentially overflow, in the absense of further analysis. - cast(GEP)->setHasNoPointerOverflow(false); - return GEP; - } - } + return 0; } diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp index f6d8e86850f..71e98377738 100644 --- a/lib/VMCore/Constants.cpp +++ b/lib/VMCore/Constants.cpp @@ -475,11 +475,8 @@ public: static GetElementPtrConstantExpr *Create(Constant *C, const std::vector&IdxList, const Type *DestTy) { - GetElementPtrConstantExpr *Result = new(IdxList.size() + 1) - GetElementPtrConstantExpr(C, IdxList, DestTy); - // Getelementptr defaults to having no pointer overflow. - cast(Result)->setHasNoPointerOverflow(true); - return Result; + return + new(IdxList.size() + 1) GetElementPtrConstantExpr(C, IdxList, DestTy); } /// Transparently provide more efficient getOperand methods. DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); diff --git a/lib/VMCore/Instructions.cpp b/lib/VMCore/Instructions.cpp index c1b57a6e1e4..e04d54cee37 100644 --- a/lib/VMCore/Instructions.cpp +++ b/lib/VMCore/Instructions.cpp @@ -1023,9 +1023,6 @@ void GetElementPtrInst::init(Value *Ptr, Value* const *Idx, unsigned NumIdx, OL[i+1] = Idx[i]; setName(Name); - - // GetElementPtr instructions have undefined results on overflow by default. - cast(this)->setHasNoPointerOverflow(true); } void GetElementPtrInst::init(Value *Ptr, Value *Idx, const std::string &Name) { @@ -1035,9 +1032,6 @@ void GetElementPtrInst::init(Value *Ptr, Value *Idx, const std::string &Name) { OL[1] = Idx; setName(Name); - - // GetElementPtr instructions have undefined results on overflow by default. - cast(this)->setHasNoPointerOverflow(true); } GetElementPtrInst::GetElementPtrInst(const GetElementPtrInst &GEPI) @@ -1049,10 +1043,6 @@ GetElementPtrInst::GetElementPtrInst(const GetElementPtrInst &GEPI) Use *GEPIOL = GEPI.OperandList; for (unsigned i = 0, E = NumOperands; i != E; ++i) OL[i] = GEPIOL[i]; - - // Transfer the hasNoPointerOverflow() value from the original GEPI. - cast(this) - ->setHasNoPointerOverflow(cast(GEPI).hasNoPointerOverflow()); } GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx, diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp index 279eabb0ec4..ab2e35c1af7 100644 --- a/lib/VMCore/Value.cpp +++ b/lib/VMCore/Value.cpp @@ -363,8 +363,6 @@ Value *Value::getUnderlyingObject() { unsigned MaxLookup = 6; do { if (GEPOperator *GEP = dyn_cast(V)) { - if (!GEP->hasNoPointerOverflow()) - return V; V = GEP->getPointerOperand(); } else if (Operator::getOpcode(V) == Instruction::BitCast) { V = cast(V)->getOperand(0); diff --git a/test/CodeGen/X86/iv-users-in-other-loops.ll b/test/CodeGen/X86/iv-users-in-other-loops.ll index a48f0616291..af1434ad1ae 100644 --- a/test/CodeGen/X86/iv-users-in-other-loops.ll +++ b/test/CodeGen/X86/iv-users-in-other-loops.ll @@ -3,8 +3,8 @@ ; RUN: grep dec %t | count 2 ; RUN: grep addq %t | count 13 ; RUN: not grep addb %t -; RUN: grep leaq %t | count 8 -; RUN: grep leal %t | count 4 +; RUN: grep leaq %t | count 9 +; RUN: grep leal %t | count 3 ; RUN: grep movq %t | count 5 ; IV users in each of the loops from other loops shouldn't cause LSR diff --git a/test/Transforms/IndVarSimplify/max-pointer.ll b/test/Transforms/IndVarSimplify/max-pointer.ll index ba2b2fa8348..2ee08dbc38b 100644 --- a/test/Transforms/IndVarSimplify/max-pointer.ll +++ b/test/Transforms/IndVarSimplify/max-pointer.ll @@ -22,58 +22,6 @@ return: ; preds = %bb2 ret void } -define void @bar(i8* %str1Ptr, i64 %s, i8* %inLastBytePtr) nounwind { -entry: - %str2Ptr = inttoptr i64 %s to i8* - %0 = icmp ult i8* %str2Ptr, %str1Ptr ; [#uses=1] - %str2Ptr_addr.0 = select i1 %0, i8* %str1Ptr, i8* %str2Ptr ; [#uses=1] - br label %bb2 - -bb2: ; preds = %bb2, %entry - %str2Ptr_addr.1 = phi i8* [ %str2Ptr_addr.0, %entry ], [ %1, %bb2 ] ; [#uses=1] - %1 = getelementptr i8* %str2Ptr_addr.1, i64 1 ; [#uses=2] - %2 = icmp ult i8* %1, %inLastBytePtr ; [#uses=0] - br i1 false, label %bb2, label %return - -return: ; preds = %bb2 - ret void -} - -define void @qux(i64 %t, i64 %s, i8* %inLastBytePtr) nounwind { -entry: - %str1Ptr = inttoptr i64 %t to i8* - %str2Ptr = inttoptr i64 %s to i8* - %0 = icmp ult i8* %str2Ptr, %str1Ptr ; [#uses=1] - %str2Ptr_addr.0 = select i1 %0, i8* %str1Ptr, i8* %str2Ptr ; [#uses=1] - br label %bb2 - -bb2: ; preds = %bb2, %entry - %str2Ptr_addr.1 = phi i8* [ %str2Ptr_addr.0, %entry ], [ %1, %bb2 ] ; [#uses=1] - %1 = getelementptr i8* %str2Ptr_addr.1, i64 1 ; [#uses=2] - %2 = icmp ult i8* %1, %inLastBytePtr ; [#uses=0] - br i1 false, label %bb2, label %return - -return: ; preds = %bb2 - ret void -} - -define void @vor(i64 %t, i8* %str2Ptr, i8* %inLastBytePtr) nounwind { -entry: - %str1Ptr = inttoptr i64 %t to i8* - %0 = icmp ult i8* %str2Ptr, %str1Ptr ; [#uses=1] - %str2Ptr_addr.0 = select i1 %0, i8* %str1Ptr, i8* %str2Ptr ; [#uses=1] - br label %bb2 - -bb2: ; preds = %bb2, %entry - %str2Ptr_addr.1 = phi i8* [ %str2Ptr_addr.0, %entry ], [ %1, %bb2 ] ; [#uses=1] - %1 = getelementptr i8* %str2Ptr_addr.1, i64 1 ; [#uses=2] - %2 = icmp ult i8* %1, %inLastBytePtr ; [#uses=0] - br i1 false, label %bb2, label %return - -return: ; preds = %bb2 - ret void -} - define void @sfoo(i8* %str1Ptr, i8* %str2Ptr, i8* %inLastBytePtr) nounwind { entry: %0 = icmp slt i8* %str2Ptr, %str1Ptr ; [#uses=1] @@ -89,57 +37,3 @@ bb2: ; preds = %bb2, %entry return: ; preds = %bb2 ret void } - -define void @sbar(i8* %str1Ptr, i64 %s, i8* %inLastBytePtr) nounwind { -entry: - %str2Ptr = inttoptr i64 %s to i8* - %0 = icmp slt i8* %str2Ptr, %str1Ptr ; [#uses=1] - %str2Ptr_addr.0 = select i1 %0, i8* %str1Ptr, i8* %str2Ptr ; [#uses=1] - br label %bb2 - -bb2: ; preds = %bb2, %entry - %str2Ptr_addr.1 = phi i8* [ %str2Ptr_addr.0, %entry ], [ %1, %bb2 ] ; [#uses=1] - %1 = getelementptr i8* %str2Ptr_addr.1, i64 1 ; [#uses=2] - %2 = icmp slt i8* %1, %inLastBytePtr ; [#uses=0] - br i1 false, label %bb2, label %return - -return: ; preds = %bb2 - ret void -} - -define void @squx(i64 %t, i64 %s, i8* %inLastBytePtr) nounwind { -entry: - %str1Ptr = inttoptr i64 %t to i8* - %str2Ptr = inttoptr i64 %s to i8* - %0 = icmp slt i8* %str2Ptr, %str1Ptr ; [#uses=1] - %str2Ptr_addr.0 = select i1 %0, i8* %str1Ptr, i8* %str2Ptr ; [#uses=1] - br label %bb2 - -bb2: ; preds = %bb2, %entry - %str2Ptr_addr.1 = phi i8* [ %str2Ptr_addr.0, %entry ], [ %1, %bb2 ] ; [#uses=1] - %1 = getelementptr i8* %str2Ptr_addr.1, i64 1 ; [#uses=2] - %2 = icmp slt i8* %1, %inLastBytePtr ; [#uses=0] - br i1 false, label %bb2, label %return - -return: ; preds = %bb2 - ret void -} - -define void @svor(i64 %t, i8* %str2Ptr, i8* %inLastBytePtr) nounwind { -entry: - %str1Ptr = inttoptr i64 %t to i8* - %0 = icmp slt i8* %str2Ptr, %str1Ptr ; [#uses=1] - %str2Ptr_addr.0 = select i1 %0, i8* %str1Ptr, i8* %str2Ptr ; [#uses=1] - br label %bb2 - -bb2: ; preds = %bb2, %entry - %str2Ptr_addr.1 = phi i8* [ %str2Ptr_addr.0, %entry ], [ %1, %bb2 ] ; [#uses=1] - %1 = getelementptr i8* %str2Ptr_addr.1, i64 1 ; [#uses=2] - %2 = icmp slt i8* %1, %inLastBytePtr ; [#uses=0] - br i1 false, label %bb2, label %return - -return: ; preds = %bb2 - ret void -} - - diff --git a/test/Transforms/InstCombine/add2.ll b/test/Transforms/InstCombine/add2.ll index 161d56b40b5..cd67d96a01a 100644 --- a/test/Transforms/InstCombine/add2.ll +++ b/test/Transforms/InstCombine/add2.ll @@ -1,9 +1,4 @@ -; RUN: llvm-as < %s | opt -instcombine | llvm-dis | \ -; RUN: grep -v OK | not grep add - -;; Target triple for gep raising case below. -target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128" -target triple = "i686-apple-darwin8" +; RUN: llvm-as < %s | opt -instcombine | llvm-dis | not grep add define i64 @test1(i64 %A, i32 %B) { %tmp12 = zext i32 %B to i64 @@ -13,23 +8,6 @@ define i64 @test1(i64 %A, i32 %B) { ret i64 %tmp6 } -; PR1795 -define void @test2(i32 %.val24) { -EntryBlock: - add i32 %.val24, -12 - inttoptr i32 %0 to i32* - store i32 1, i32* %1 - add i32 %.val24, -16 - inttoptr i32 %2 to i32* - getelementptr i32* %3, i32 1 - load i32* %4 - tail call i32 @callee( i32 %5 ) - ret void -} - -declare i32 @callee(i32) - - define i32 @test3(i32 %A) { %B = and i32 %A, 7 %C = and i32 %A, 32 diff --git a/test/Transforms/InstCombine/add3.ll b/test/Transforms/InstCombine/add3.ll new file mode 100644 index 00000000000..55e7ec7a1db --- /dev/null +++ b/test/Transforms/InstCombine/add3.ll @@ -0,0 +1,21 @@ +; RUN: llvm-as < %s | opt -instcombine | llvm-dis | grep inttoptr | count 2 + +;; Target triple for gep raising case below. +target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128" +target triple = "i686-apple-darwin8" + +; PR1795 +define void @test2(i32 %.val24) { +EntryBlock: + add i32 %.val24, -12 + inttoptr i32 %0 to i32* + store i32 1, i32* %1 + add i32 %.val24, -16 + inttoptr i32 %2 to i32* + getelementptr i32* %3, i32 1 + load i32* %4 + tail call i32 @callee( i32 %5 ) + ret void +} + +declare i32 @callee(i32) diff --git a/test/Transforms/InstCombine/cast_ptr.ll b/test/Transforms/InstCombine/cast_ptr.ll index fd600a88304..9b87ed094ea 100644 --- a/test/Transforms/InstCombine/cast_ptr.ll +++ b/test/Transforms/InstCombine/cast_ptr.ll @@ -1,8 +1,15 @@ ; Tests to make sure elimination of casts is working correctly -; RUN: llvm-as < %s | opt -instcombine | llvm-dis | notcast +; RUN: llvm-as < %s | opt -instcombine | llvm-dis | FileCheck %s target datalayout = "p:32:32" +; This shouldn't convert to getelementptr because the relationship +; between the arithmetic and the layout of allocated memory is +; entirely unknown. +; CHECK: @test1 +; CHECK: ptrtoint +; CHECK: add +; CHECK: inttoptr define i8* @test1(i8* %t) { %tmpc = ptrtoint i8* %t to i32 ; [#uses=1] %tmpa = add i32 %tmpc, 32 ; [#uses=1] @@ -10,6 +17,9 @@ define i8* @test1(i8* %t) { ret i8* %tv } +; These casts should be folded away. +; CHECK: @test2 +; CHECK: icmp eq i8* %a, %b define i1 @test2(i8* %a, i8* %b) { %tmpa = ptrtoint i8* %a to i32 ; [#uses=1] %tmpb = ptrtoint i8* %b to i32 ; [#uses=1] -- 2.34.1