Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp =================================================================== --- llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -578,9 +578,58 @@ } } -/// Use the must-be-executed-context around \p I to add information into \p S. -/// The AAType class is required to have `followUseInMBEC` method with the -/// following signature and behaviour: +/// Helper function for update in followUsesInMBEC +template +static void +updateBrInst(AAType &AA, Attributor &A, MustBeExecutedContextExplorer &Explorer, + const Instruction *CtxI, const BranchInst *Br, + SetVector &Uses, StateType &State, + DenseMap &StateMap, + SetVector &AddInsts) { + State.indicateOptimisticFixpoint(); + for (const BasicBlock *BB : Br->successors()) { + const Instruction *DependInst = &BB->front(); + auto Iter = StateMap.find(DependInst); + if (Iter == StateMap.end()) { + AddInsts.insert(DependInst); + State &= StateType(); + } else { + State &= Iter->second; + } + } + followUsesInContext(AA, A, Explorer, CtxI, Uses, State); +} + +/// Helper function for update in followUsesInMBEC +template +static void +updateInst(AAType &AA, Attributor &A, MustBeExecutedContextExplorer &Explorer, + const Instruction *CtxI, SetVector &Uses, + StateType &State, DenseMap &StateMap, + SetVector &AddInsts) { + State = StateType(); + followUsesInContext(AA, A, Explorer, CtxI, Uses, State); + SmallVector BrInsts; + auto Pred = [&](const Instruction *I) { + if (const BranchInst *Br = dyn_cast(I)) + if (Br->isConditional()) + BrInsts.push_back(I); + return true; + }; + Explorer.checkForAllContext(CtxI, Pred); + for (const Instruction *I : BrInsts) { + auto Iter = StateMap.find(I); + if (Iter == StateMap.end()) { + AddInsts.insert(I); + } else { + State += Iter->second; + } + } +} + +/// Use the must-be-executed-context around \p I to add information into \p +/// S. The AAType class is required to have `followUseInMBEC` method with +/// the following signature and behaviour: /// /// bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I) /// U - Underlying use. @@ -590,84 +639,53 @@ template static void followUsesInMBEC(AAType &AA, Attributor &A, StateType &S, Instruction &CtxI) { + // Map from context instruction to state + DenseMap StateMap; // Container for (transitive) uses of the associated value. SetVector Uses; - for (const Use &U : AA.getIRPosition().getAssociatedValue().uses()) + + // Register context instructions + StateMap.insert(std::make_pair(&CtxI, StateType())); + + for (const Use &U : AA.getIRPosition().getAssociatedValue().uses()) { Uses.insert(&U); + if (const Instruction *UserI = dyn_cast(U.getUser())) { + StateMap.insert(std::make_pair(UserI, StateType())); + } + } MustBeExecutedContextExplorer &Explorer = A.getInfoCache().getMustBeExecutedContextExplorer(); - followUsesInContext(AA, A, Explorer, &CtxI, Uses, S); - - if (S.isAtFixpoint()) - return; - - 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. Let ParentState_i be a state - // to indicate the known information for an i-th branch instruction in the - // context. ChildStates are created for its successors respectively. - // - // ParentS_1 = ChildS_{1, 1} /\ ChildS_{1, 2} /\ ... /\ ChildS_{1, n_1} - // ParentS_2 = ChildS_{2, 1} /\ ChildS_{2, 2} /\ ... /\ ChildS_{2, n_2} - // ... - // ParentS_m = ChildS_{m, 1} /\ ChildS_{m, 2} /\ ... /\ ChildS_{m, n_m} - // - // Known State |= ParentS_1 \/ ParentS_2 \/... \/ ParentS_m - // - // FIXME: Currently, recursive branches are not handled. For example, we - // can't deduce that ptr must be dereferenced in below function. - // - // void f(int a, int c, int *ptr) { - // if(a) - // if (b) { - // *ptr = 0; - // } else { - // *ptr = 1; - // } - // else { - // if (b) { - // *ptr = 0; - // } else { - // *ptr = 1; - // } - // } - // } - - 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(AA, 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; + ChangeStatus CS; + // TODO: set upper bound of number of iteration as command line option + unsigned Iteration = 0; + do { + Iteration += 1; + CS = ChangeStatus::UNCHANGED; + SetVector AddInsts; + for (auto &InstStatePair : StateMap) { + const Instruction *I = InstStatePair.first; + StateType &State = InstStatePair.second; + StateType BeforeState = State; + const BranchInst *Br = dyn_cast(I); + if (Br && Br->isConditional()) { + updateBrInst(AA, A, Explorer, I, Br, Uses, State, StateMap, AddInsts); + } else { + updateInst(AA, A, Explorer, I, Uses, State, StateMap, AddInsts); + } + if (State != BeforeState) { + CS = ChangeStatus::CHANGED; + } } + if (AddInsts.size() > 0) + CS = ChangeStatus::CHANGED; + for (const Instruction *I : AddInsts) + StateMap.insert(std::make_pair(I, StateType())); + } while (CS == ChangeStatus::CHANGED); - // Use only known state. - S += ParentState; - } + S += StateMap.lookup(&CtxI); } /// -----------------------NoUnwind Function Attribute-------------------------- Index: llvm/test/Transforms/Attributor/ArgumentPromotion/2008-09-08-CGUpdateSelfEdge.ll =================================================================== --- llvm/test/Transforms/Attributor/ArgumentPromotion/2008-09-08-CGUpdateSelfEdge.ll +++ llvm/test/Transforms/Attributor/ArgumentPromotion/2008-09-08-CGUpdateSelfEdge.ll @@ -5,16 +5,6 @@ ; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM define internal fastcc i32 @term_SharingList(i32* %Term, i32* %List) nounwind { -; IS__TUNIT____-LABEL: define {{[^@]+}}@term_SharingList -; IS__TUNIT____-SAME: (i32* [[TERM:%.*]], i32* [[LIST:%.*]]) -; IS__TUNIT____-NEXT: entry: -; IS__TUNIT____-NEXT: br i1 false, label [[BB:%.*]], label [[BB5:%.*]] -; IS__TUNIT____: bb: -; IS__TUNIT____-NEXT: [[TMP0:%.*]] = call fastcc i32 @term_SharingList(i32* null, i32* [[LIST]]) -; IS__TUNIT____-NEXT: unreachable -; IS__TUNIT____: bb5: -; IS__TUNIT____-NEXT: ret i32 0 -; ; IS__CGSCC____-LABEL: define {{[^@]+}}@term_SharingList() ; IS__CGSCC____-NEXT: entry: ; IS__CGSCC____-NEXT: br i1 false, label [[BB:%.*]], label [[BB5:%.*]] Index: llvm/test/Transforms/Attributor/ArgumentPromotion/dbg.ll =================================================================== --- llvm/test/Transforms/Attributor/ArgumentPromotion/dbg.ll +++ llvm/test/Transforms/Attributor/ArgumentPromotion/dbg.ll @@ -1,6 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes -; RUN: opt -attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM -; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM +; RUN: opt -attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=5 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM +; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=5 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM ; RUN: opt -attributor-cgscc -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_NPM,IS__CGSCC____,IS________OPM,IS__CGSCC_OPM ; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM Index: llvm/test/Transforms/Attributor/dereferenceable-1.ll =================================================================== --- llvm/test/Transforms/Attributor/dereferenceable-1.ll +++ llvm/test/Transforms/Attributor/dereferenceable-1.ll @@ -548,7 +548,7 @@ ; FIXME: %ptr should be dereferenceable(4) define dso_local void @rec-branch-1(i32 %a, i32 %b, i32 %c, i32* %ptr) { ; CHECK-LABEL: define {{[^@]+}}@rec-branch-1 -; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32* nocapture nofree writeonly [[PTR:%.*]]) +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[PTR:%.*]]) ; CHECK-NEXT: entry: ; CHECK-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[A]], 0 ; CHECK-NEXT: br i1 [[TOBOOL]], label [[IF_ELSE3:%.*]], label [[IF_THEN:%.*]] Index: llvm/test/Transforms/Attributor/dereferenceable-2.ll =================================================================== --- llvm/test/Transforms/Attributor/dereferenceable-2.ll +++ llvm/test/Transforms/Attributor/dereferenceable-2.ll @@ -510,7 +510,7 @@ ; ATTRIBUTOR_CGSCC_NPM-LABEL: define i32 @require_cfg_analysis(i32 %c, i32* {{.*}} dereferenceable(4) %p) define i32 @require_cfg_analysis(i32 %c, i32* %p) { ; IS________OPM-LABEL: define {{[^@]+}}@require_cfg_analysis -; IS________OPM-SAME: (i32 [[C:%.*]], i32* nocapture nofree writeonly [[P:%.*]]) +; IS________OPM-SAME: (i32 [[C:%.*]], i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[P:%.*]]) ; IS________OPM-NEXT: [[TOBOOL1:%.*]] = icmp eq i32 [[C]], 0 ; IS________OPM-NEXT: br i1 [[TOBOOL1]], label [[L1:%.*]], label [[L2:%.*]] ; IS________OPM: l1: Index: llvm/test/Transforms/Attributor/misc.ll =================================================================== --- llvm/test/Transforms/Attributor/misc.ll +++ llvm/test/Transforms/Attributor/misc.ll @@ -19,7 +19,7 @@ ; IS__TUNIT____-NEXT: call void @callback2(void (i8*)* nonnull bitcast (void (i32*)* @foo to void (i8*)*)) ; IS__TUNIT____-NEXT: call void @callback2(void (i8*)* nonnull [[FP]]) ; IS__TUNIT____-NEXT: [[TMP1:%.*]] = bitcast i32* [[A]] to i8* -; IS__TUNIT____-NEXT: call void [[FP]](i8* [[TMP1]]) +; IS__TUNIT____-NEXT: call void [[FP]](i8* nonnull align 4 dereferenceable(4) [[TMP1]]) ; IS__TUNIT____-NEXT: ret void ; ; IS__CGSCC____-LABEL: define {{[^@]+}}@internal @@ -32,7 +32,7 @@ ; IS__CGSCC____-NEXT: call void @callback2(void (i8*)* bitcast (void (i32*)* @foo to void (i8*)*)) ; IS__CGSCC____-NEXT: call void @callback2(void (i8*)* nonnull [[FP]]) ; IS__CGSCC____-NEXT: [[TMP1:%.*]] = bitcast i32* [[A]] to i8* -; IS__CGSCC____-NEXT: call void [[FP]](i8* [[TMP1]]) +; IS__CGSCC____-NEXT: call void [[FP]](i8* nonnull align 4 dereferenceable(4) [[TMP1]]) ; IS__CGSCC____-NEXT: ret void ; entry: @@ -61,7 +61,7 @@ ; IS__TUNIT____-NEXT: call void @callback2(void (i8*)* [[FP]]) ; IS__TUNIT____-NEXT: call void [[FP]](i8* bitcast (void (i32*)* @foo to i8*)) ; IS__TUNIT____-NEXT: [[TMP1:%.*]] = bitcast i32* [[A]] to i8* -; IS__TUNIT____-NEXT: call void [[FP]](i8* [[TMP1]]) +; IS__TUNIT____-NEXT: call void [[FP]](i8* nonnull align 4 dereferenceable(4) [[TMP1]]) ; IS__TUNIT____-NEXT: call void @internal(void (i8*)* nonnull [[FP]]) ; IS__TUNIT____-NEXT: ret void ; @@ -75,7 +75,7 @@ ; IS__CGSCC____-NEXT: call void @callback2(void (i8*)* [[FP]]) ; IS__CGSCC____-NEXT: call void [[FP]](i8* bitcast (void (i32*)* @foo to i8*)) ; IS__CGSCC____-NEXT: [[TMP1:%.*]] = bitcast i32* [[A]] to i8* -; IS__CGSCC____-NEXT: call void [[FP]](i8* [[TMP1]]) +; IS__CGSCC____-NEXT: call void [[FP]](i8* nonnull align 4 dereferenceable(4) [[TMP1]]) ; IS__CGSCC____-NEXT: call void @internal(void (i8*)* nonnull [[FP]]) ; IS__CGSCC____-NEXT: ret void ; Index: llvm/test/Transforms/Attributor/noalias.ll =================================================================== --- llvm/test/Transforms/Attributor/noalias.ll +++ llvm/test/Transforms/Attributor/noalias.ll @@ -666,22 +666,39 @@ ; Therefore, only one of the two conditions of if statementes will be fulfilled. define internal void @test16_sub(i32* noalias %p, i32 %c1, i32 %c2) { -; NOT_CGSCC_NPM-LABEL: define {{[^@]+}}@test16_sub -; NOT_CGSCC_NPM-SAME: (i32* noalias nofree writeonly [[P:%.*]], i32 [[C1:%.*]], i32 [[C2:%.*]]) -; NOT_CGSCC_NPM-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[C1]], 0 -; NOT_CGSCC_NPM-NEXT: br i1 [[TOBOOL]], label [[IF_END:%.*]], label [[IF_THEN:%.*]] -; NOT_CGSCC_NPM: if.then: -; NOT_CGSCC_NPM-NEXT: tail call void @only_store(i32* noalias nocapture nofree writeonly align 4 [[P]]) -; NOT_CGSCC_NPM-NEXT: tail call void @make_alias(i32* nofree writeonly align 4 [[P]]) -; NOT_CGSCC_NPM-NEXT: br label [[IF_END]] -; NOT_CGSCC_NPM: if.end: -; NOT_CGSCC_NPM-NEXT: [[TOBOOL1:%.*]] = icmp eq i32 [[C2]], 0 -; NOT_CGSCC_NPM-NEXT: br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_END3:%.*]] -; NOT_CGSCC_NPM: if.then2: -; NOT_CGSCC_NPM-NEXT: tail call void @only_store(i32* nocapture nofree writeonly align 4 [[P]]) -; NOT_CGSCC_NPM-NEXT: br label [[IF_END3]] -; NOT_CGSCC_NPM: if.end3: -; NOT_CGSCC_NPM-NEXT: ret void +; IS________OPM-LABEL: define {{[^@]+}}@test16_sub +; IS________OPM-SAME: (i32* noalias nofree writeonly [[P:%.*]], i32 [[C1:%.*]], i32 [[C2:%.*]]) +; IS________OPM-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[C1]], 0 +; IS________OPM-NEXT: br i1 [[TOBOOL]], label [[IF_END:%.*]], label [[IF_THEN:%.*]] +; IS________OPM: if.then: +; IS________OPM-NEXT: tail call void @only_store(i32* noalias nocapture nofree writeonly align 4 [[P]]) +; IS________OPM-NEXT: tail call void @make_alias(i32* nofree writeonly align 4 [[P]]) +; IS________OPM-NEXT: br label [[IF_END]] +; IS________OPM: if.end: +; IS________OPM-NEXT: [[TOBOOL1:%.*]] = icmp eq i32 [[C2]], 0 +; IS________OPM-NEXT: br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_END3:%.*]] +; IS________OPM: if.then2: +; IS________OPM-NEXT: tail call void @only_store(i32* nocapture nofree writeonly align 4 [[P]]) +; IS________OPM-NEXT: br label [[IF_END3]] +; IS________OPM: if.end3: +; IS________OPM-NEXT: ret void +; +; IS__TUNIT_NPM-LABEL: define {{[^@]+}}@test16_sub +; IS__TUNIT_NPM-SAME: (i32* noalias nofree writeonly [[P:%.*]], i32 [[C1:%.*]], i32 [[C2:%.*]]) +; IS__TUNIT_NPM-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[C1]], 0 +; IS__TUNIT_NPM-NEXT: br i1 [[TOBOOL]], label [[IF_END:%.*]], label [[IF_THEN:%.*]] +; IS__TUNIT_NPM: if.then: +; IS__TUNIT_NPM-NEXT: tail call void @only_store(i32* noalias nocapture nofree writeonly align 4 [[P]]) +; IS__TUNIT_NPM-NEXT: tail call void @make_alias(i32* nofree writeonly [[P]]) +; IS__TUNIT_NPM-NEXT: br label [[IF_END]] +; IS__TUNIT_NPM: if.end: +; IS__TUNIT_NPM-NEXT: [[TOBOOL1:%.*]] = icmp eq i32 [[C2]], 0 +; IS__TUNIT_NPM-NEXT: br i1 [[TOBOOL1]], label [[IF_THEN2:%.*]], label [[IF_END3:%.*]] +; IS__TUNIT_NPM: if.then2: +; IS__TUNIT_NPM-NEXT: tail call void @only_store(i32* nocapture nofree writeonly align 4 [[P]]) +; IS__TUNIT_NPM-NEXT: br label [[IF_END3]] +; IS__TUNIT_NPM: if.end3: +; IS__TUNIT_NPM-NEXT: ret void ; ; IS__CGSCC____-LABEL: define {{[^@]+}}@test16_sub ; IS__CGSCC____-SAME: (i32* noalias nofree writeonly [[P:%.*]], i32 [[C1:%.*]], i32 [[C2:%.*]])