Index: lib/Analysis/InstructionSimplify.cpp =================================================================== --- lib/Analysis/InstructionSimplify.cpp +++ lib/Analysis/InstructionSimplify.cpp @@ -2122,6 +2122,64 @@ (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs))) return ConstantInt::get(GetCompareTy(LHS), !CmpInst::isTrueWhenEqual(Pred)); + + // We cannot fold comparisons between allocas and arguments in general (see + // comment above this function). However in some cases we can argue that + // it's impossible to guess the value of the alloca, and we can act as if + // the alloca and argument compare unequal. To do this, the alloca mustn't + // be observed, and we must fold *all* comparisons between pointers based + // on the alloca and argument consistently. + if ((isa(LHS) && isa(RHS)) || + (isa(RHS) && isa(LHS))) { + AllocaInst *Alloca = cast(isa(LHS) ? LHS : RHS); + Argument *Arg = cast(isa(LHS) ? LHS : RHS); + + auto CanTrackAllUses = [DL](Value *V) { + unsigned MaxDepth = 16; + SmallVector Worklist; + for (Use &U : V->uses()) + Worklist.push_back(&U); + while (!Worklist.empty()) { + if (!MaxDepth--) + return false; + Use *U = Worklist.pop_back_val(); + Instruction *I = cast(U->getUser()); + + if (auto *SI = dyn_cast(I)) { + if (SI->getValueOperand() == U->get()) + return false; + continue; + } else if (isa(I)) { + continue; + } else if (auto *Cmp = dyn_cast(I)) { + if (!Cmp->isEquality()) + return false; + continue; + } else if (isa(I)) { + // Keep tracking. + } else if (auto *GEP = dyn_cast(I)) { + Type *IntPtrTy = + DL.getIntPtrType(U->get()->getType())->getScalarType(); + APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth()); + if (!GEP->accumulateConstantOffset(DL, Offset)) + return false; + // Keep tracking. + } else if (isa(I)) { + // Intrinsics should be safe (other calls would escape the pointer). + continue; + } else { + return false; + } + for (Use &U : I->uses()) + Worklist.push_back(&U); + } + return true; + }; + + if (CanTrackAllUses(Alloca) && CanTrackAllUses(Arg)) + return ConstantInt::get(GetCompareTy(LHS), + !CmpInst::isTrueWhenEqual(Pred)); + } } // Otherwise, fail. Index: test/Transforms/InstSimplify/compare.ll =================================================================== --- test/Transforms/InstSimplify/compare.ll +++ test/Transforms/InstSimplify/compare.ll @@ -704,29 +704,119 @@ ret i1 %Y } -; It's not valid to fold a comparison of an argument with an alloca, even though -; that's tempting. An argument can't *alias* an alloca, however the aliasing rule -; relies on restrictions against guessing an object's address and dereferencing. -; There are no restrictions against guessing an object's address and comparing. +; It's not valid to fold a comparison of an argument with an alloca in the +; general case, even though that's tempting. An argument can't *alias* an +; alloca; however, the aliasing rule relies on restrictions against guessing +; an object's address and dereferencing. There are no restrictions against +; guessing an object's address and comparing. +; +; However, in cases where we can act as if the alloca yields an unguessable +; address, we *can* fold comparisons against it. This works if the alloca +; doesn't escape, as that would allow it to be observed outside the function. +; Also, we must guarantee that if we fold one comparison of an argument and +; alloca, we must fold *all* comparisons based on those pointers to maintain +; consistency. define i1 @alloca_argument_compare(i64* %arg) { %alloc = alloca i64 %cmp = icmp eq i64* %arg, %alloc ret i1 %cmp - ; CHECK: alloca_argument_compare - ; CHECK: ret i1 %cmp + ; CHECK-LABEL: alloca_argument_compare + ; CHECK: ret i1 false } -; As above, but with the operands reversed. - define i1 @alloca_argument_compare_swapped(i64* %arg) { %alloc = alloca i64 %cmp = icmp eq i64* %alloc, %arg ret i1 %cmp - ; CHECK: alloca_argument_compare_swapped + ; CHECK-LABEL: alloca_argument_compare_swapped + ; CHECK: ret i1 false +} + +define i1 @alloca_argument_compare_ne(i64* %arg) { + %alloc = alloca i64 + %cmp = icmp ne i64* %arg, %alloc + ret i1 %cmp + ; CHECK-LABEL: alloca_argument_compare_ne + ; CHECK: ret i1 true +} + +define i1 @alloca_argument_compare_derived_ptrs(i64* %arg) { + %alloc = alloca i64, i64 8 + %p = getelementptr i64, i64* %arg, i64 3 + %q = getelementptr i64, i64* %alloc, i64 42 + %cmp = icmp eq i64* %p, %q + ret i1 %cmp + ; CHECK-LABEL: alloca_argument_compare_derived_ptrs + ; CHECK: ret i1 false +} + +declare void @escape(i64*) +define i1 @alloca_argument_compare_escaped_alloca(i64* %arg) { + %alloc = alloca i64 + call void @escape(i64* %alloc) + %cmp = icmp eq i64* %arg, %alloc + ret i1 %cmp + ; CHECK-LABEL: alloca_argument_compare_escaped_alloca + ; CHECK: %cmp = icmp eq i64* %arg, %alloc + ; CHECK: ret i1 %cmp +} + +declare void @check_compares(i1, i1) +define void @alloca_argument_compare_consistency(i64* %p) { + %q = alloca i64, i64 8 + %r = getelementptr i64, i64* %p, i64 1 + %s = getelementptr i64, i64* %q, i64 2 + %cmp1 = icmp eq i64* %p, %q + %cmp2 = icmp eq i64* %r, %s + call void @check_compares(i1 %cmp1, i1 %cmp2) + ret void + ; CHECK-LABEL: alloca_argument_compare_consistency + ; CHECK: call void @check_compares(i1 false, i1 false) +} + +define void @alloca_argument_compare_inconsistency(i64* %p, i64 %x) { + %q = alloca i64, i64 8 + ; Instsimplify will not be able to track %r back to %p because the GEP has a + ; non-const offset. Since we're unable to fold the r == s comparison, we also + ; cannot fold p == q. + %r = getelementptr i64, i64* %p, i64 %x + %s = getelementptr i64, i64* %q, i64 2 + %cmp1 = icmp eq i64* %p, %q + %cmp2 = icmp eq i64* %r, %s + call void @check_compares(i1 %cmp1, i1 %cmp2) + ret void + ; CHECK-LABEL: alloca_argument_compare_inconsistency + ; CHECK: call void @check_compares(i1 %cmp1, i1 %cmp2) +} + +define i1 @alloca_argument_compare_escaped_through_store(i64* %arg, i64** %ptr) { + %alloc = alloca i64 + %cmp = icmp eq i64* %arg, %alloc + %p = getelementptr i64, i64* %alloc, i64 1 + store i64* %p, i64** %ptr + ret i1 %cmp + ; CHECK-LABEL: alloca_argument_compare_escaped_through_store + ; CHECK: %cmp = icmp eq i64* %arg, %alloc ; CHECK: ret i1 %cmp } + +declare void @llvm.lifetime.start(i64, i8* nocapture) +declare void @llvm.lifetime.end(i64, i8* nocapture) +define i1 @alloca_argument_compare_benign_instrs(i8* %arg) { + %alloc = alloca i8 + call void @llvm.lifetime.start(i64 1, i8* %alloc) + %cmp = icmp eq i8* %arg, %alloc + %x = load i8, i8* %arg + store i8 %x, i8* %alloc + call void @llvm.lifetime.end(i64 1, i8* %alloc) + ret i1 %cmp + ; CHECK-LABEL: alloca_argument_compare_benign_instrs + ; CHECK: ret i1 false +} + + ; Don't assume that a noalias argument isn't equal to a global variable's ; address. This is an example where AliasAnalysis' NoAlias concept is ; different from actual pointer inequality.