Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp =================================================================== --- llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -42,6 +42,9 @@ static cl::opt MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128), cl::Hidden); +static cl::opt MaxIterationFollowUse("max-iteration-follow-use", + cl::init(10), cl::Hidden); + STATISTIC(NumAAs, "Number of abstract attributes created"); // Some helper macros to deal with statistics tracking. @@ -560,6 +563,9 @@ }; /// Helper function to accumulate uses. +/// Track Uses must be executed in context of \p CtxI +/// Additional tracked Uses are finally removed and \p Uses is not changed by +/// this function. template static void followUsesInContext(AAType &AA, Attributor &A, MustBeExecutedContextExplorer &Explorer, @@ -567,6 +573,7 @@ SetVector &Uses, StateType &State) { 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,98 +583,131 @@ 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: +/// 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, + MapVector &StateMap, + SetVector &AddInsts) { + StateType ConjunctionState; + ConjunctionState.indicateOptimisticFixpoint(); + for (const BasicBlock *BB : Br->successors()) { + const Instruction *DependInst = &BB->front(); + typename MapVector::iterator StateMapIt = + StateMap.find(DependInst); + if (StateMapIt == StateMap.end()) { + AddInsts.insert(DependInst); + ConjunctionState &= StateType(); + } else { + ConjunctionState &= StateMapIt->second; + } + } + State += ConjunctionState; + updateInst(AA, A, Explorer, CtxI, Uses, State, StateMap, AddInsts); +} + +/// Helper function for update in followUsesInMBEC +template +static void updateInst(AAType &AA, Attributor &A, + MustBeExecutedContextExplorer &Explorer, + const Instruction *CtxI, SetVector &Uses, + StateType &State, + MapVector &StateMap, + SetVector &AddInsts) { + 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) { + typename MapVector::iterator StateMapIt = + StateMap.find(I); + if (StateMapIt == StateMap.end()) + AddInsts.insert(I); + else + State += StateMapIt->second; + } + + followUsesInContext(AA, A, Explorer, CtxI, Uses, 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. +/// +/// We propagate known states repeatedly with above two logics until no change +/// happens. To do that, we keep a mapping from Instruction to state in +/// \p StateMap. The maximum limit of iteration is given as command line option +/// \p MaxIterationFollowUse. +/// +/// TODO: initialize states optimistically template static void followUsesInMBEC(AAType &AA, Attributor &A, StateType &S, Instruction &CtxI) { + MustBeExecutedContextExplorer &Explorer = + A.getInfoCache().getMustBeExecutedContextExplorer(); + + // Map from context instruction to state + MapVector StateMap; // 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; - - SmallVector BrInsts; - auto Pred = [&](const Instruction *I) { - if (const BranchInst *Br = dyn_cast(I)) - if (Br->isConditional()) - BrInsts.push_back(Br); - return true; - }; + StateMap.insert(std::make_pair(&CtxI, StateType())); - // 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; + unsigned Iteration = 0; + do { + Iteration += 1; + CS = ChangeStatus::UNCHANGED; + // Set for instructions to be added for the next iteration + SetVector AddInsts; + for (auto& StateMapIt : StateMap) { + const Instruction *I = StateMapIt.first; + StateType &State = StateMapIt.second; + if (State.isAtFixpoint()) + continue; + StateType BeforeState = State; + if (const BranchInst *Br = dyn_cast(I)) + 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; } - - // Use only known state. - S += ParentState; - } + if (AddInsts.size() > 0) + CS = ChangeStatus::CHANGED; + for (const Instruction *I : AddInsts) + StateMap.insert(std::make_pair(I, StateType())); + } while (CS == ChangeStatus::CHANGED && Iteration < MaxIterationFollowUse); + + StateType T = StateMap.lookup(&CtxI); + S += T; } /// -----------------------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 @@ -792,7 +792,7 @@ 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 +819,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: