Index: llvm/include/llvm/Analysis/MustExecute.h =================================================================== --- llvm/include/llvm/Analysis/MustExecute.h +++ llvm/include/llvm/Analysis/MustExecute.h @@ -461,6 +461,18 @@ } ///} + /// Check \p Pred on all instructions in the context. + /// + /// This method will evaluate \p Pred and return + /// true if \p Pred holds in every instruction. + bool checkForAllContext(const Instruction *PP, + const function_ref &Pred) { + for (auto EIt = begin(PP), EEnd = end(PP); EIt != EEnd; EIt++) + if (!Pred(*EIt)) + return false; + return true; + } + /// Helper to look for \p I in the context of \p PP. /// /// The context is expanded until \p I was found or no more expansion is Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -1339,6 +1339,13 @@ handleNewAssumedValue(R.getAssumed()); } + /// "Clamp" this state with \p R. The result is subtype dependent but it is + /// intended that information known in either state will be known in + /// this one afterwards. + void operator+=(const IntegerStateBase &R) { + handleNewKnownValue(R.getKnown()); + } + void operator|=(const IntegerStateBase &R) { joinOR(R.getAssumed(), R.getKnown()); } @@ -2294,6 +2301,13 @@ return *this; } + /// See IntegerStateBase::operator+= + DerefState operator+=(const DerefState &R) { + DerefBytesState += R.DerefBytesState; + GlobalState += R.GlobalState; + return *this; + } + /// See IntegerStateBase::operator&= DerefState operator&=(const DerefState &R) { DerefBytesState &= R.DerefBytesState; Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -980,6 +980,23 @@ Uses.insert(&U); } + /// Helper function to accumulate uses. + void followUsesInContext(Attributor &A, + MustBeExecutedContextExplorer &Explorer, + const Instruction *CtxI, + SetVector &Uses, StateType &State) { + auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI); + for (unsigned u = 0; u < Uses.size(); ++u) { + const Use *U = Uses[u]; + if (const Instruction *UserI = dyn_cast(U->getUser())) { + bool Found = Explorer.findInContextOf(UserI, EIt, EEnd); + if (Found && Base::followUse(A, U, UserI, State)) + for (const Use &Us : UserI->uses()) + Uses.insert(&Us); + } + } + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { auto BeforeState = this->getState(); @@ -991,15 +1008,54 @@ MustBeExecutedContextExplorer &Explorer = A.getInfoCache().getMustBeExecutedContextExplorer(); - auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI); - for (unsigned u = 0; u < Uses.size(); ++u) { - const Use *U = Uses[u]; - if (const Instruction *UserI = dyn_cast(U->getUser())) { - bool Found = Explorer.findInContextOf(UserI, EIt, EEnd); - if (Found && Base::followUse(A, U, UserI)) - for (const Use &Us : UserI->uses()) - Uses.insert(&Us); + followUsesInContext(A, Explorer, CtxI, Uses, S); + + if (this->isAtFixpoint()) + return ChangeStatus::CHANGED; + + SmallVector BrInsts; + auto Pred = [&](const Instruction *I) { + if (const BranchInst *Br = dyn_cast(I)) + if (Br->isConditional()) + BrInsts.push_back(Br); + return true; + }; + + // Here, accumulate conditional branch instructions in the context. We + // explore the child paths and collect the known states. The disjunction of + // those states can be merged to its own state. + // + // ParentState_1 = ChildState_{1, 1} /\ ChildState_{1, 2} /\ ... /\ + // ChildState_{1, n_1} + // ... + // ParentState_m = ChildState_{m, 1} /\ ChildState_{2, 2} /\ ... /\ + // ChildState_{1, n_m} + // + // Known State |= ParentState_1 \/ ... \/ ParentState_m + + Explorer.checkForAllContext(CtxI, Pred); + for (const BranchInst *Br : BrInsts) { + StateType ParentState; + + // The known state of the parent state is a conjunction of children's + // known states so it is initialized with a best state. + ParentState.indicateOptimisticFixpoint(); + + for (const BasicBlock *BB : Br->successors()) { + StateType ChildState; + + size_t BeforeSize = Uses.size(); + followUsesInContext(A, Explorer, &BB->front(), Uses, ChildState); + + // Erase uses which only appear in the child. + for (auto It = Uses.begin() + BeforeSize; It != Uses.end();) + It = Uses.erase(It); + + ParentState &= ChildState; } + + // Use only known state. + S += ParentState; } return BeforeState == S ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED; @@ -1900,7 +1956,7 @@ /// ------------------------ NonNull Argument Attribute ------------------------ static int64_t getKnownNonNullAndDerefBytesForUse( - Attributor &A, AbstractAttribute &QueryingAA, Value &AssociatedValue, + Attributor &A, const AbstractAttribute &QueryingAA, Value &AssociatedValue, const Use *U, const Instruction *I, bool &IsNonNull, bool &TrackUse) { TrackUse = false; @@ -1991,12 +2047,13 @@ } /// See AAFromMustBeExecutedContext - bool followUse(Attributor &A, const Use *U, const Instruction *I) { + bool followUse(Attributor &A, const Use *U, const Instruction *I, + AANonNull::StateType &State) { bool IsNonNull = false; bool TrackUse = false; getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse); - setKnown(IsNonNull); + State.setKnown(IsNonNull); return TrackUse; } @@ -3546,8 +3603,8 @@ /// } /// Helper function for collecting accessed bytes in must-be-executed-context - void addAccessedBytesForUse(Attributor &A, const Use *U, - const Instruction *I) { + void addAccessedBytesForUse(Attributor &A, const Use *U, const Instruction *I, + DerefState &State) { const Value *UseV = U->get(); if (!UseV->getType()->isPointerTy()) return; @@ -3560,21 +3617,22 @@ if (Base == &getAssociatedValue() && getPointerOperand(I, /* AllowVolatile */ false) == UseV) { uint64_t Size = DL.getTypeStoreSize(PtrTy->getPointerElementType()); - addAccessedBytes(Offset, Size); + State.addAccessedBytes(Offset, Size); } } return; } /// See AAFromMustBeExecutedContext - bool followUse(Attributor &A, const Use *U, const Instruction *I) { + bool followUse(Attributor &A, const Use *U, const Instruction *I, + AADereferenceable::StateType &State) { bool IsNonNull = false; bool TrackUse = false; int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse( A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse); - addAccessedBytesForUse(A, U, I); - takeKnownDerefBytesMaximum(DerefBytes); + addAccessedBytesForUse(A, U, I, State); + State.takeKnownDerefBytesMaximum(DerefBytes); return TrackUse; } @@ -3868,12 +3926,13 @@ Attribute::getWithAlignment(Ctx, Align(getAssumedAlign()))); } /// See AAFromMustBeExecutedContext - bool followUse(Attributor &A, const Use *U, const Instruction *I) { + bool followUse(Attributor &A, const Use *U, const Instruction *I, + AAAlign::StateType &State) { bool TrackUse = false; unsigned int KnownAlign = getKnownAlignForUse(A, *this, getAssociatedValue(), U, I, TrackUse); - takeKnownMaximum(KnownAlign); + State.takeKnownMaximum(KnownAlign); return TrackUse; } Index: llvm/test/Transforms/Attributor/IPConstantProp/openmp_parallel_for.ll =================================================================== --- llvm/test/Transforms/Attributor/IPConstantProp/openmp_parallel_for.ll +++ llvm/test/Transforms/Attributor/IPConstantProp/openmp_parallel_for.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes -; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s +; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s ; ; void bar(int, float, double); ; Index: llvm/test/Transforms/Attributor/dereferenceable-1.ll =================================================================== --- llvm/test/Transforms/Attributor/dereferenceable-1.ll +++ llvm/test/Transforms/Attributor/dereferenceable-1.ll @@ -308,5 +308,57 @@ ret void } +declare void @use0() #0 +declare void @use1(i8*) #0 +declare void @use2(i8*, i8*) #0 +declare void @use3(i8*, i8*, i8*) #0 +; simple path test +; if(..) +; fun2(dereferenceable(8) %a, dereferenceable(8) %b) +; else +; fun2(dereferenceable(4) %a, %b) +; We can say that %a is dereferenceable(4) but %b is not. +define void @simple-path(i8* %a, i8 * %b, i8 %c) { +; ATTRIBUTOR: define void @simple-path(i8* nonnull dereferenceable(4) %a, i8* %b, i8 %c) + %cmp = icmp eq i8 %c, 0 + br i1 %cmp, label %if.then, label %if.else +if.then: + tail call void @use2(i8* dereferenceable(8) %a, i8* dereferenceable(8) %b) + ret void +if.else: + tail call void @use2(i8* dereferenceable(4) %a, i8* %b) + ret void +} +; More complex test +; { +; fun1(dereferenceable(4) %a) +; if(..) +; ... (willreturn & nounwind) +; fun1(dereferenceable(12) %a) +; else +; ... (willreturn & nounwind) +; fun1(dereferenceable(16) %a) +; fun1(dereferenceable(8) %a) +; } +; %a is dereferenceable(12) + +define void @complex-path(i8* %a, i8* %b, i8 %c) { +; ATTRIBUTOR: define void @complex-path(i8* nonnull dereferenceable(12) %a, i8* nocapture nofree readnone %b, i8 %c) + %cmp = icmp eq i8 %c, 0 + tail call void @use1(i8* dereferenceable(4) %a) + br i1 %cmp, label %cont.then, label %cont.else +cont.then: + tail call void @use1(i8* dereferenceable(12) %a) + br label %cont2 +cont.else: + tail call void @use1(i8* dereferenceable(16) %a) + br label %cont2 +cont2: + tail call void @use1(i8* dereferenceable(8) %a) + ret void +} + +attributes #0 = { nounwind willreturn} + !0 = !{i64 10, i64 100} Index: llvm/test/Transforms/Attributor/nonnull.ll =================================================================== --- llvm/test/Transforms/Attributor/nonnull.ll +++ llvm/test/Transforms/Attributor/nonnull.ll @@ -257,8 +257,7 @@ ; fun2(nonnull %a, %b) ; We can say that %a is nonnull but %b is not. define void @f16(i8* %a, i8 * %b, i8 %c) { -; FIXME: missing nonnull on %a -; ATTRIBUTOR: define void @f16(i8* %a, i8* %b, i8 %c) +; ATTRIBUTOR: define void @f16(i8* nonnull %a, i8* %b, i8 %c) %cmp = icmp eq i8 %c, 0 br i1 %cmp, label %if.then, label %if.else if.then: @@ -327,8 +326,7 @@ ; TEST 19: Loop define void @f19(i8* %a, i8* %b, i8 %c) { -; FIXME: missing nonnull on %b -; ATTRIBUTOR: define void @f19(i8* %a, i8* %b, i8 %c) +; ATTRIBUTOR: define void @f19(i8* %a, i8* nonnull %b, i8 %c) br label %loop.header loop.header: %cmp2 = icmp eq i8 %c, 0 @@ -658,7 +656,7 @@ define i32 @nonnull_exec_ctx_2(i32* %a, i32 %b) willreturn nounwind { ; ; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2 -; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) +; ATTRIBUTOR-SAME: (i32* nonnull [[A:%.*]], i32 [[B:%.*]]) ; ATTRIBUTOR-NEXT: en: ; ATTRIBUTOR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B]], 0 ; ATTRIBUTOR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] @@ -691,7 +689,7 @@ define i32 @nonnull_exec_ctx_2b(i32* %a, i32 %b) willreturn nounwind { ; ; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2b -; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) +; ATTRIBUTOR-SAME: (i32* nonnull [[A:%.*]], i32 [[B:%.*]]) ; ATTRIBUTOR-NEXT: en: ; ATTRIBUTOR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B]], 0 ; ATTRIBUTOR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]