Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp =================================================================== --- llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -559,14 +559,18 @@ } }; -/// Helper function to accumulate uses. +/// Helper function to accumulate known information from uses. +/// Track Uses must be executed in context of \p CtxI +/// Additionally tracked Uses are finally removed and \p Uses is not changed by +/// this function. template static void followUsesInContext(AAType &AA, Attributor &A, MustBeExecutedContextExplorer &Explorer, - const Instruction *CtxI, + const Instruction &CtxI, SetVector &Uses, StateType &State) { - auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI); + auto EIt = Explorer.begin(&CtxI), EEnd = Explorer.end(&CtxI); + size_t BeforeSize = Uses.size(); for (unsigned u = 0; u < Uses.size(); ++u) { const Use *U = Uses[u]; if (const Instruction *UserI = dyn_cast(U->getUser())) { @@ -576,34 +580,30 @@ Uses.insert(&Us); } } + for (auto It = Uses.begin() + BeforeSize; It != Uses.end();) + It = Uses.erase(It); } -/// 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. -/// I - The user of the \p U. -/// Returns true if the value should be tracked transitively. -/// +/// Helper function for path exploration in followUsesInMBEC template -static void followUsesInMBEC(AAType &AA, Attributor &A, StateType &S, - Instruction &CtxI) { - - // Container for (transitive) uses of the associated value. - SetVector Uses; - for (const Use &U : AA.getIRPosition().getAssociatedValue().uses()) - Uses.insert(&U); - - MustBeExecutedContextExplorer &Explorer = - A.getInfoCache().getMustBeExecutedContextExplorer(); - - followUsesInContext(AA, A, Explorer, &CtxI, Uses, S); - - if (S.isAtFixpoint()) - return; - +static StateType +exploreInst(AAType &AA, Attributor &A, MustBeExecutedContextExplorer &Explorer, + const Instruction &CtxI, SetVector &Uses, + DenseMap &StateMap) { + + // Insert initial (pessimistic) state. If the key is already in the map, the + // value corresponds to the key will not be updated. + std::pair::iterator, bool> + StateMapInsertResult = + StateMap.insert(std::make_pair(&CtxI, StateType())); + StateType &State = StateMapInsertResult.first->second; + + // To avoid exploring the same instruction twice or more, return the value + // immediately if the key is already in the map. + if (!StateMapInsertResult.second) + return State; + + // Collect branch instructions which must be executed. SmallVector BrInsts; auto Pred = [&](const Instruction *I) { if (const BranchInst *Br = dyn_cast(I)) @@ -611,63 +611,57 @@ 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; + StateType ConjunctionState; + ConjunctionState.indicateOptimisticFixpoint(); + for (const BasicBlock *BB : Br->successors()) { + ConjunctionState &= + exploreInst(AA, A, Explorer, BB->front(), Uses, StateMap); + } + State += ConjunctionState; + } - // 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(); + followUsesInContext(AA, A, Explorer, CtxI, Uses, State); - for (const BasicBlock *BB : Br->successors()) { - StateType ChildState; + return State; +} + +/// Use the must-be-executed-context around \p I to clamp known states 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. +/// I - The user of the \p U. +/// Returns true if the value should be tracked transitively. +/// +/// If instructions Q_1,...Q_N must be executed in context of instruction P, +/// the known state at P can be improved by the disjunction of known +/// states at Q_1,...,Q_N. +/// +/// To propagate known states more aggressively, we use the fact that +/// a known state at a branch instruction can be improved by the conjunction of +/// known states at entry points of its successors. +/// +/// TODO: initialize states optimistically +template +static void followUsesInMBEC(AAType &AA, Attributor &A, StateType &S, + Instruction &CtxI) { + MustBeExecutedContextExplorer &Explorer = + A.getInfoCache().getMustBeExecutedContextExplorer(); - size_t BeforeSize = Uses.size(); - followUsesInContext(AA, A, Explorer, &BB->front(), Uses, ChildState); + // Map from context instruction to state + DenseMap StateMap; - // Erase uses which only appear in the child. - for (auto It = Uses.begin() + BeforeSize; It != Uses.end();) - It = Uses.erase(It); + // Container for (transitive) uses of the associated value. + SetVector Uses; - ParentState &= ChildState; - } + for (const Use &U : AA.getIRPosition().getAssociatedValue().uses()) + Uses.insert(&U); - // Use only known state. - S += ParentState; - } + S += exploreInst(AA, A, Explorer, CtxI, Uses, StateMap); } /// -----------------------NoUnwind Function Attribute-------------------------- Index: llvm/test/Transforms/Attributor/dereferenceable-1.ll =================================================================== --- llvm/test/Transforms/Attributor/dereferenceable-1.ll +++ llvm/test/Transforms/Attributor/dereferenceable-1.ll @@ -788,11 +788,10 @@ ; } ; } ; -; FIXME: %ptr should be dereferenceable(4) define dso_local void @rec-branch-1(i32 %a, i32 %b, i32 %c, i32* %ptr) { ; IS__TUNIT____: Function Attrs: argmemonly nofree nosync nounwind willreturn writeonly ; IS__TUNIT____-LABEL: define {{[^@]+}}@rec-branch-1 -; IS__TUNIT____-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32* nocapture nofree writeonly [[PTR:%.*]]) +; IS__TUNIT____-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[PTR:%.*]]) ; IS__TUNIT____-NEXT: entry: ; IS__TUNIT____-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[A]], 0 ; IS__TUNIT____-NEXT: br i1 [[TOBOOL]], label [[IF_ELSE3:%.*]], label [[IF_THEN:%.*]] @@ -819,7 +818,7 @@ ; ; IS__CGSCC____: Function Attrs: argmemonly nofree norecurse nosync nounwind willreturn writeonly ; IS__CGSCC____-LABEL: define {{[^@]+}}@rec-branch-1 -; IS__CGSCC____-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32* nocapture nofree writeonly [[PTR:%.*]]) +; IS__CGSCC____-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[PTR:%.*]]) ; IS__CGSCC____-NEXT: entry: ; IS__CGSCC____-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[A]], 0 ; IS__CGSCC____-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 @@ -717,7 +717,7 @@ define i32 @require_cfg_analysis(i32 %c, i32* %p) { ; IS__TUNIT_OPM: Function Attrs: argmemonly nofree nosync nounwind willreturn writeonly ; IS__TUNIT_OPM-LABEL: define {{[^@]+}}@require_cfg_analysis -; IS__TUNIT_OPM-SAME: (i32 [[C:%.*]], i32* nocapture nofree writeonly [[P:%.*]]) +; IS__TUNIT_OPM-SAME: (i32 [[C:%.*]], i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[P:%.*]]) ; IS__TUNIT_OPM-NEXT: [[TOBOOL1:%.*]] = icmp eq i32 [[C]], 0 ; IS__TUNIT_OPM-NEXT: br i1 [[TOBOOL1]], label [[L1:%.*]], label [[L2:%.*]] ; IS__TUNIT_OPM: l1: @@ -770,7 +770,7 @@ ; ; IS__CGSCC_OPM: Function Attrs: argmemonly nofree norecurse nosync nounwind willreturn writeonly ; IS__CGSCC_OPM-LABEL: define {{[^@]+}}@require_cfg_analysis -; IS__CGSCC_OPM-SAME: (i32 [[C:%.*]], i32* nocapture nofree writeonly [[P:%.*]]) +; IS__CGSCC_OPM-SAME: (i32 [[C:%.*]], i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[P:%.*]]) ; IS__CGSCC_OPM-NEXT: [[TOBOOL1:%.*]] = icmp eq i32 [[C]], 0 ; IS__CGSCC_OPM-NEXT: br i1 [[TOBOOL1]], label [[L1:%.*]], label [[L2:%.*]] ; IS__CGSCC_OPM: l1: