Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -1701,6 +1701,9 @@ /// Return true if "undefined behavior" is known. bool isKnownToCauseUB() const { return getKnown(); } + /// Return true if "undefined behavior" is known for a specific instruction. + virtual bool isKnownToCauseUB(Instruction *I) const = 0; + /// Return an IR position, see struct IRPosition. const IRPosition &getIRPosition() const override { return *this; } Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -1996,16 +1996,17 @@ // TODO: We should not only check instructions that access memory // through a pointer (i.e. also branches etc.) ChangeStatus updateImpl(Attributor &A) override { - const size_t PrevSize = NoUBMemAccessInsts.size(); + const size_t PrevSize = KnownNoUBInsts.size(); auto InspectMemAccessInstForUB = [&](Instruction &I) { // Skip instructions that are already saved. - if (NoUBMemAccessInsts.count(&I) || UBMemAccessInsts.count(&I)) + if (KnownNoUBInsts.count(&I) || KnownUBInsts.count(&I)) return true; - // `InspectMemAccessInstForUB` is only called on instructions - // for which getPointerOperand() should give us their - // pointer operand unless they're volatile. + // If we reach here, we know we have an instruction + // that accesses memory through a pointer operand, + // for which getPointerOperand() should give it to us, + // it is volatile. const Value *PtrOp = getPointerOperand(&I); if (!PtrOp) return true; @@ -2014,7 +2015,7 @@ // only if the pointer has constant null value. // TODO: Expand it to not only check constant values. if (!isa(PtrOp)) { - NoUBMemAccessInsts.insert(&I); + KnownNoUBInsts.insert(&I); return true; } const Type *PtrTy = PtrOp->getType(); @@ -2025,10 +2026,58 @@ // A memory access using constant null pointer is only considered UB // if null pointer is _not_ defined for the target platform. - if (!llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace())) - UBMemAccessInsts.insert(&I); + if (llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace())) + KnownNoUBInsts.insert(&I); else - NoUBMemAccessInsts.insert(&I); + KnownUBInsts.insert(&I); + return true; + }; + + auto InspectBrInstForUB = [&](Instruction &I) { + // Skip instructions that are already saved. + if (KnownNoUBInsts.count(&I) || KnownUBInsts.count(&I)) + return true; + + // We know we have a branch instruction. + auto BrInst = cast(&I); + + // A conditional branch instruction is considered UB if it has `undef` + // condition. + // TODO: Right now, this is a very simplistic check. It only + // identifies UB in cases like: br i1 undef, ... + // This should be better when AAValueSimplfiy gets improved. + if (BrInst->isUnconditional()) + return true; + const Value *Cond = BrInst->getCondition(); + + // Try with the simple LLVM value. + if (isa(Cond)) { + KnownUBInsts.insert(&I); + return true; + } + + // Try to get the simplified value. + const auto &ValueSimplifyAA = + A.getAAFor(*this, IRPosition::value(*Cond)); + Optional SimplifiedV = + ValueSimplifyAA.getAssumedSimplifiedValue(A); + + if (!ValueSimplifyAA.isKnown()) { + // Don't depend on assumed values. + return true; + } + if (!SimplifiedV.hasValue()) { + // If it is known (which we tested above) but it doesn't have a value, + // then we can assume `undef` and hence the instruction is UB. + KnownUBInsts.insert(&I); + return true; + } + const Value *CondVal = SimplifiedV.getValue(); + if (!isa(CondVal)) { + KnownNoUBInsts.insert(&I); + return true; + } + KnownUBInsts.insert(&I); return true; }; @@ -2036,20 +2085,46 @@ {Instruction::Load, Instruction::Store, Instruction::AtomicCmpXchg, Instruction::AtomicRMW}); - if (PrevSize != NoUBMemAccessInsts.size()) + A.checkForAllInstructions(InspectBrInstForUB, *this, {Instruction::Br}); + if (PrevSize != KnownNoUBInsts.size()) return ChangeStatus::CHANGED; return ChangeStatus::UNCHANGED; } + bool isKnownToCauseUB(Instruction *I) const override { + return KnownUBInsts.count(I); + } + bool isAssumedToCauseUB(Instruction *I) const override { - return UBMemAccessInsts.count(I); + // In simple words, if an instruction is not the known to _not_ + // cause UB, then it is assumed UB. The rest is boilerplate + // is to ensure that it is one of the instructions we test + // for UB. + + switch (I->getOpcode()) { + case Instruction::Load: + case Instruction::Store: + case Instruction::AtomicCmpXchg: + case Instruction::AtomicRMW: + return !KnownNoUBInsts.count(I); + case Instruction::Br: { + auto BrInst = cast(I); + if (BrInst->isUnconditional()) + return false; + return !KnownNoUBInsts.count(I); + } break; + default: + return false; + } + return false; } ChangeStatus manifest(Attributor &A) override { - if (!UBMemAccessInsts.size()) + if (KnownUBInsts.empty()) return ChangeStatus::UNCHANGED; - for (Instruction *I : UBMemAccessInsts) + for (Instruction *I : KnownUBInsts) { changeToUnreachable(I, /* UseLLVMTrap */ false); + } return ChangeStatus::CHANGED; } @@ -2059,21 +2134,19 @@ } protected: - // A set of all the (live) memory accessing instructions that _are_ assumed to - // cause UB. - SmallPtrSet UBMemAccessInsts; + // A set of all live instructions _known_ to cause UB. + SmallPtrSet KnownUBInsts; private: - // A set of all the (live) memory accessing instructions - // that are _not_ assumed to cause UB. + // A set of all the (live) instructions that are known to _not_ cause UB. // Note: The correctness of the procedure depends on the fact that this // set stops changing after some point. "Change" here means that the size // of the set changes. The size of this set is monotonically increasing - // (we only add items to it) and is upper bounded by the number of memory - // accessing instructions in the processed function (we can never save more + // (we only add items to it) and is upper bounded by the number of + // instructions in the processed function (we can never save more // elements in this set than this number). Hence, the size of this set, at // some point, will stop increasing, effectively reaching a fixpoint. - SmallPtrSet NoUBMemAccessInsts; + SmallPtrSet KnownNoUBInsts; }; struct AAUndefinedBehaviorFunction final : AAUndefinedBehaviorImpl { @@ -2085,7 +2158,7 @@ STATS_DECL(UndefinedBehaviorInstruction, Instruction, "Number of instructions known to have UB"); BUILD_STAT_NAME(UndefinedBehaviorInstruction, Instruction) += - UBMemAccessInsts.size(); + KnownUBInsts.size(); } }; @@ -5580,6 +5653,7 @@ // The alignment of a pointer is interesting for stores. case Instruction::Call: case Instruction::CallBr: + case Instruction::Br: case Instruction::Invoke: case Instruction::CleanupRet: case Instruction::CatchSwitch: Index: llvm/test/Transforms/Attributor/undefined_behavior.ll =================================================================== --- llvm/test/Transforms/Attributor/undefined_behavior.ll +++ llvm/test/Transforms/Attributor/undefined_behavior.ll @@ -8,9 +8,10 @@ ; -- Load tests -- -; ATTRIBUTOR-LABEL: define void @load_wholly_unreachable() define void @load_wholly_unreachable() { -; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR-LABEL: @load_wholly_unreachable( +; ATTRIBUTOR-NEXT: unreachable +; %a = load i32, i32* null ret void } @@ -144,3 +145,135 @@ %a = cmpxchg i32* null, i32 2, i32 3 acq_rel monotonic ret void } + +; Note: The unreachable on %t and %e is _not_ from AAUndefinedBehavior + +define i32 @cond_br_on_undef() { +; ATTRIBUTOR-LABEL: @cond_br_on_undef( +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: t: +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: e: +; ATTRIBUTOR-NEXT: unreachable +; + + br i1 undef, label %t, label %e +t: + ret i32 1 +e: + ret i32 2 +} + +; More complicated branching +define void @cond_br_on_undef2(i1 %cond) { +; ATTRIBUTOR-LABEL: @cond_br_on_undef2( +; ATTRIBUTOR-NEXT: br i1 [[COND:%.*]], label [[T1:%.*]], label [[E1:%.*]] +; ATTRIBUTOR: t1: +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: t2: +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: e2: +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: e1: +; ATTRIBUTOR-NEXT: ret void +; + + ; Valid branch - verify that this is not converted + ; to unreachable. + br i1 %cond, label %t1, label %e1 +t1: + br i1 undef, label %t2, label %e2 +t2: + ret void +e2: + ret void +e1: + ret void +} + +define i1 @ret_undef() { + ret i1 undef +} + +define void @cond_br_on_undef_interproc() { +; ATTRIBUTOR-LABEL: @cond_br_on_undef_interproc( +; ATTRIBUTOR-NEXT: %cond = call i1 @ret_undef() +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: t: +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: e: +; ATTRIBUTOR-NEXT: unreachable + + %cond = call i1 @ret_undef() + br i1 %cond, label %t, label %e +t: + ret void +e: + ret void +} + +define i1 @ret_undef2() { + br i1 true, label %t, label %e +t: + ret i1 undef +e: + ret i1 undef +} + +; More complicated interproc deduction of undef +define void @cond_br_on_undef_interproc2() { +; ATTRIBUTOR-LABEL: @cond_br_on_undef_interproc2( +; ATTRIBUTOR-NEXT: %cond = call i1 @ret_undef2() +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: t: +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR: e: +; ATTRIBUTOR-NEXT: unreachable + %cond = call i1 @ret_undef2() + br i1 %cond, label %t, label %e +t: + ret void +e: + ret void +} + +; Branch on undef that depends on propagation of +; undef of a previous instruction. +; FIXME: Currently it doesn't propagate the undef. +define i32 @cond_br_on_undef3() { +; ATTRIBUTOR-LABEL: @cond_br_on_undef3( +; ATTRIBUTOR-NEXT: %cond = icmp ne i32 1, undef +; ATTRIBUTOR-NEXT: br i1 %cond, label %t, label %e +; ATTRIBUTOR: t: +; ATTRIBUTOR-NEXT: ret i32 1 +; ATTRIBUTOR: e: +; ATTRIBUTOR-NEXT: ret i32 2 + + %cond = icmp ne i32 1, undef + br i1 %cond, label %t, label %e +t: + ret i32 1 +e: + ret i32 2 +} + +; Branch on undef because of uninitialized value. +; FIXME: Currently it doesn't propagate the undef. +define i32 @cond_br_on_undef_uninit() { +; ATTRIBUTOR-LABEL: @cond_br_on_undef_uninit( +; ATTRIBUTOR-NEXT: %alloc = alloca i1 +; ATTRIBUTOR-NEXT: %cond = load i1, i1* %alloc +; ATTRIBUTOR-NEXT: br i1 %cond, label %t, label %e +; ATTRIBUTOR: t: +; ATTRIBUTOR-NEXT: ret i32 1 +; ATTRIBUTOR: e: +; ATTRIBUTOR-NEXT: ret i32 2 + + %alloc = alloca i1 + %cond = load i1, i1* %alloc + br i1 %cond, label %t, label %e +t: + ret i32 1 +e: + ret i32 2 +}