From c1d53a316d6c7f7d80908ec8b5a65172f82e9721 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Thu, 6 May 2021 16:03:51 -0500 Subject: [PATCH] [Attributor] Look through selects in genericValueTraversal If we can simplify the select condition we can avoid one value in the traversal. Differential Revision: https://reviews.llvm.org/D103861 --- llvm/lib/Transforms/IPO/AttributorAttributes.cpp | 19 +++- llvm/test/Transforms/Attributor/lvi-for-ashr.ll | 124 ++++++++++++++-------- llvm/test/Transforms/Attributor/value-simplify.ll | 8 +- 3 files changed, 100 insertions(+), 51 deletions(-) diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp index b0a36079..4da5786 100644 --- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -265,10 +265,11 @@ static bool genericValueTraversal( DepClassTy::NONE); bool AnyDead = false; + Value *InitialV = &IRP.getAssociatedValue(); using Item = std::pair; SmallSet Visited; SmallVector Worklist; - Worklist.push_back({&IRP.getAssociatedValue(), CtxI}); + Worklist.push_back({InitialV, CtxI}); int Iteration = 0; do { @@ -307,8 +308,22 @@ static bool genericValueTraversal( continue; } - // Look through select instructions, visit both potential values. + // Look through select instructions, visit assumed potential values. if (auto *SI = dyn_cast(V)) { + bool UsedAssumedInformation = false; + Optional C = A.getAssumedConstant( + *SI->getCondition(), QueryingAA, UsedAssumedInformation); + bool NoValueYet = !C.hasValue(); + if (NoValueYet || isa_and_nonnull(*C)) + continue; + if (auto *CI = dyn_cast_or_null(*C)) { + if (CI->isZero()) + Worklist.push_back({SI->getFalseValue(), CtxI}); + else + Worklist.push_back({SI->getTrueValue(), CtxI}); + continue; + } + // We could not simplify the condition, assume both values.( Worklist.push_back({SI->getTrueValue(), CtxI}); Worklist.push_back({SI->getFalseValue(), CtxI}); continue; diff --git a/llvm/test/Transforms/Attributor/lvi-for-ashr.ll b/llvm/test/Transforms/Attributor/lvi-for-ashr.ll index 51416e0..f1884f0 100644 --- a/llvm/test/Transforms/Attributor/lvi-for-ashr.ll +++ b/llvm/test/Transforms/Attributor/lvi-for-ashr.ll @@ -7,47 +7,87 @@ ; FIXME: DOT should be replaced with 3 define i32 @test-ashr(i32 %c) { -; IS__TUNIT____: Function Attrs: nofree nosync nounwind readnone willreturn -; IS__TUNIT____-LABEL: define {{[^@]+}}@test-ashr -; IS__TUNIT____-SAME: (i32 [[C:%.*]]) #[[ATTR0:[0-9]+]] { -; IS__TUNIT____-NEXT: chk65: -; IS__TUNIT____-NEXT: [[CMP:%.*]] = icmp sgt i32 [[C]], 65 -; IS__TUNIT____-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[CHK0:%.*]] -; IS__TUNIT____: chk0: -; IS__TUNIT____-NEXT: [[CMP1:%.*]] = icmp slt i32 [[C]], 0 -; IS__TUNIT____-NEXT: br i1 [[CMP]], label [[RETURN]], label [[BB_IF:%.*]] -; IS__TUNIT____: bb_if: -; IS__TUNIT____-NEXT: [[ASHR_VAL:%.*]] = ashr exact i32 [[C]], 2 -; IS__TUNIT____-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[ASHR_VAL]], 15 -; IS__TUNIT____-NEXT: br i1 [[CMP2]], label [[BB_THEN:%.*]], label [[RETURN]] -; IS__TUNIT____: bb_then: -; IS__TUNIT____-NEXT: [[CMP3:%.*]] = icmp eq i32 [[ASHR_VAL]], 16 -; IS__TUNIT____-NEXT: [[DOT:%.*]] = select i1 [[CMP3]], i32 3, i32 2 -; IS__TUNIT____-NEXT: br label [[RETURN]] -; IS__TUNIT____: return: -; IS__TUNIT____-NEXT: [[RETVAL:%.*]] = phi i32 [ 0, [[CHK65:%.*]] ], [ 1, [[CHK0]] ], [ [[DOT]], [[BB_THEN]] ], [ 4, [[BB_IF]] ] -; IS__TUNIT____-NEXT: ret i32 [[RETVAL]] +; IS__TUNIT_OPM: Function Attrs: nofree nosync nounwind readnone willreturn +; IS__TUNIT_OPM-LABEL: define {{[^@]+}}@test-ashr +; IS__TUNIT_OPM-SAME: (i32 [[C:%.*]]) #[[ATTR0:[0-9]+]] { +; IS__TUNIT_OPM-NEXT: chk65: +; IS__TUNIT_OPM-NEXT: [[CMP:%.*]] = icmp sgt i32 [[C]], 65 +; IS__TUNIT_OPM-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[CHK0:%.*]] +; IS__TUNIT_OPM: chk0: +; IS__TUNIT_OPM-NEXT: [[CMP1:%.*]] = icmp slt i32 [[C]], 0 +; IS__TUNIT_OPM-NEXT: br i1 [[CMP]], label [[RETURN]], label [[BB_IF:%.*]] +; IS__TUNIT_OPM: bb_if: +; IS__TUNIT_OPM-NEXT: [[ASHR_VAL:%.*]] = ashr exact i32 [[C]], 2 +; IS__TUNIT_OPM-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[ASHR_VAL]], 15 +; IS__TUNIT_OPM-NEXT: br i1 [[CMP2]], label [[BB_THEN:%.*]], label [[RETURN]] +; IS__TUNIT_OPM: bb_then: +; IS__TUNIT_OPM-NEXT: [[CMP3:%.*]] = icmp eq i32 [[ASHR_VAL]], 16 +; IS__TUNIT_OPM-NEXT: [[DOT:%.*]] = select i1 [[CMP3]], i32 3, i32 2 +; IS__TUNIT_OPM-NEXT: br label [[RETURN]] +; IS__TUNIT_OPM: return: +; IS__TUNIT_OPM-NEXT: [[RETVAL:%.*]] = phi i32 [ 0, [[CHK65:%.*]] ], [ 1, [[CHK0]] ], [ [[DOT]], [[BB_THEN]] ], [ 4, [[BB_IF]] ] +; IS__TUNIT_OPM-NEXT: ret i32 [[RETVAL]] ; -; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind readnone willreturn -; IS__CGSCC____-LABEL: define {{[^@]+}}@test-ashr -; IS__CGSCC____-SAME: (i32 [[C:%.*]]) #[[ATTR0:[0-9]+]] { -; IS__CGSCC____-NEXT: chk65: -; IS__CGSCC____-NEXT: [[CMP:%.*]] = icmp sgt i32 [[C]], 65 -; IS__CGSCC____-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[CHK0:%.*]] -; IS__CGSCC____: chk0: -; IS__CGSCC____-NEXT: [[CMP1:%.*]] = icmp slt i32 [[C]], 0 -; IS__CGSCC____-NEXT: br i1 [[CMP]], label [[RETURN]], label [[BB_IF:%.*]] -; IS__CGSCC____: bb_if: -; IS__CGSCC____-NEXT: [[ASHR_VAL:%.*]] = ashr exact i32 [[C]], 2 -; IS__CGSCC____-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[ASHR_VAL]], 15 -; IS__CGSCC____-NEXT: br i1 [[CMP2]], label [[BB_THEN:%.*]], label [[RETURN]] -; IS__CGSCC____: bb_then: -; IS__CGSCC____-NEXT: [[CMP3:%.*]] = icmp eq i32 [[ASHR_VAL]], 16 -; IS__CGSCC____-NEXT: [[DOT:%.*]] = select i1 [[CMP3]], i32 3, i32 2 -; IS__CGSCC____-NEXT: br label [[RETURN]] -; IS__CGSCC____: return: -; IS__CGSCC____-NEXT: [[RETVAL:%.*]] = phi i32 [ 0, [[CHK65:%.*]] ], [ 1, [[CHK0]] ], [ [[DOT]], [[BB_THEN]] ], [ 4, [[BB_IF]] ] -; IS__CGSCC____-NEXT: ret i32 [[RETVAL]] +; IS__TUNIT_NPM: Function Attrs: nofree nosync nounwind readnone willreturn +; IS__TUNIT_NPM-LABEL: define {{[^@]+}}@test-ashr +; IS__TUNIT_NPM-SAME: (i32 [[C:%.*]]) #[[ATTR0:[0-9]+]] { +; IS__TUNIT_NPM-NEXT: chk65: +; IS__TUNIT_NPM-NEXT: [[CMP:%.*]] = icmp sgt i32 [[C]], 65 +; IS__TUNIT_NPM-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[CHK0:%.*]] +; IS__TUNIT_NPM: chk0: +; IS__TUNIT_NPM-NEXT: [[CMP1:%.*]] = icmp slt i32 [[C]], 0 +; IS__TUNIT_NPM-NEXT: br i1 [[CMP]], label [[RETURN]], label [[BB_IF:%.*]] +; IS__TUNIT_NPM: bb_if: +; IS__TUNIT_NPM-NEXT: [[ASHR_VAL:%.*]] = ashr exact i32 [[C]], 2 +; IS__TUNIT_NPM-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[ASHR_VAL]], 15 +; IS__TUNIT_NPM-NEXT: br i1 [[CMP2]], label [[BB_THEN:%.*]], label [[RETURN]] +; IS__TUNIT_NPM: bb_then: +; IS__TUNIT_NPM-NEXT: [[DOT:%.*]] = select i1 true, i32 3, i32 2 +; IS__TUNIT_NPM-NEXT: br label [[RETURN]] +; IS__TUNIT_NPM: return: +; IS__TUNIT_NPM-NEXT: [[RETVAL:%.*]] = phi i32 [ 0, [[CHK65:%.*]] ], [ 1, [[CHK0]] ], [ [[DOT]], [[BB_THEN]] ], [ 4, [[BB_IF]] ] +; IS__TUNIT_NPM-NEXT: ret i32 [[RETVAL]] +; +; IS__CGSCC_OPM: Function Attrs: nofree norecurse nosync nounwind readnone willreturn +; IS__CGSCC_OPM-LABEL: define {{[^@]+}}@test-ashr +; IS__CGSCC_OPM-SAME: (i32 [[C:%.*]]) #[[ATTR0:[0-9]+]] { +; IS__CGSCC_OPM-NEXT: chk65: +; IS__CGSCC_OPM-NEXT: [[CMP:%.*]] = icmp sgt i32 [[C]], 65 +; IS__CGSCC_OPM-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[CHK0:%.*]] +; IS__CGSCC_OPM: chk0: +; IS__CGSCC_OPM-NEXT: [[CMP1:%.*]] = icmp slt i32 [[C]], 0 +; IS__CGSCC_OPM-NEXT: br i1 [[CMP]], label [[RETURN]], label [[BB_IF:%.*]] +; IS__CGSCC_OPM: bb_if: +; IS__CGSCC_OPM-NEXT: [[ASHR_VAL:%.*]] = ashr exact i32 [[C]], 2 +; IS__CGSCC_OPM-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[ASHR_VAL]], 15 +; IS__CGSCC_OPM-NEXT: br i1 [[CMP2]], label [[BB_THEN:%.*]], label [[RETURN]] +; IS__CGSCC_OPM: bb_then: +; IS__CGSCC_OPM-NEXT: [[CMP3:%.*]] = icmp eq i32 [[ASHR_VAL]], 16 +; IS__CGSCC_OPM-NEXT: [[DOT:%.*]] = select i1 [[CMP3]], i32 3, i32 2 +; IS__CGSCC_OPM-NEXT: br label [[RETURN]] +; IS__CGSCC_OPM: return: +; IS__CGSCC_OPM-NEXT: [[RETVAL:%.*]] = phi i32 [ 0, [[CHK65:%.*]] ], [ 1, [[CHK0]] ], [ [[DOT]], [[BB_THEN]] ], [ 4, [[BB_IF]] ] +; IS__CGSCC_OPM-NEXT: ret i32 [[RETVAL]] +; +; IS__CGSCC_NPM: Function Attrs: nofree norecurse nosync nounwind readnone willreturn +; IS__CGSCC_NPM-LABEL: define {{[^@]+}}@test-ashr +; IS__CGSCC_NPM-SAME: (i32 [[C:%.*]]) #[[ATTR0:[0-9]+]] { +; IS__CGSCC_NPM-NEXT: chk65: +; IS__CGSCC_NPM-NEXT: [[CMP:%.*]] = icmp sgt i32 [[C]], 65 +; IS__CGSCC_NPM-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[CHK0:%.*]] +; IS__CGSCC_NPM: chk0: +; IS__CGSCC_NPM-NEXT: [[CMP1:%.*]] = icmp slt i32 [[C]], 0 +; IS__CGSCC_NPM-NEXT: br i1 [[CMP]], label [[RETURN]], label [[BB_IF:%.*]] +; IS__CGSCC_NPM: bb_if: +; IS__CGSCC_NPM-NEXT: [[ASHR_VAL:%.*]] = ashr exact i32 [[C]], 2 +; IS__CGSCC_NPM-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[ASHR_VAL]], 15 +; IS__CGSCC_NPM-NEXT: br i1 [[CMP2]], label [[BB_THEN:%.*]], label [[RETURN]] +; IS__CGSCC_NPM: bb_then: +; IS__CGSCC_NPM-NEXT: [[DOT:%.*]] = select i1 true, i32 3, i32 2 +; IS__CGSCC_NPM-NEXT: br label [[RETURN]] +; IS__CGSCC_NPM: return: +; IS__CGSCC_NPM-NEXT: [[RETVAL:%.*]] = phi i32 [ 0, [[CHK65:%.*]] ], [ 1, [[CHK0]] ], [ [[DOT]], [[BB_THEN]] ], [ 4, [[BB_IF]] ] +; IS__CGSCC_NPM-NEXT: ret i32 [[RETVAL]] ; chk65: %cmp = icmp sgt i32 %c, 65 @@ -72,7 +112,7 @@ return: ret i32 %retval } ;. -; IS__TUNIT____: attributes #[[ATTR0]] = { nofree nosync nounwind readnone willreturn } +; IS__TUNIT____: attributes #[[ATTR0:[0-9]+]] = { nofree nosync nounwind readnone willreturn } ;. -; IS__CGSCC____: attributes #[[ATTR0]] = { nofree norecurse nosync nounwind readnone willreturn } +; IS__CGSCC____: attributes #[[ATTR0:[0-9]+]] = { nofree norecurse nosync nounwind readnone willreturn } ;. diff --git a/llvm/test/Transforms/Attributor/value-simplify.ll b/llvm/test/Transforms/Attributor/value-simplify.ll index 78575c3..8640f76 100644 --- a/llvm/test/Transforms/Attributor/value-simplify.ll +++ b/llvm/test/Transforms/Attributor/value-simplify.ll @@ -1039,8 +1039,7 @@ define i32 @test_select(i32 %c) { ; IS__TUNIT____: Function Attrs: nofree nosync nounwind readnone willreturn ; IS__TUNIT____-LABEL: define {{[^@]+}}@test_select ; IS__TUNIT____-SAME: (i32 [[C:%.*]]) #[[ATTR1]] { -; IS__TUNIT____-NEXT: [[CALL:%.*]] = call i32 @select() #[[ATTR1]] -; IS__TUNIT____-NEXT: ret i32 [[CALL]] +; IS__TUNIT____-NEXT: ret i32 42 ; ; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind readnone willreturn ; IS__CGSCC____-LABEL: define {{[^@]+}}@test_select @@ -1052,11 +1051,6 @@ define i32 @test_select(i32 %c) { } define internal i32 @select(i1 %a, i32 %b, i32 %c) { -; IS__TUNIT____: Function Attrs: nofree nosync nounwind readnone willreturn -; IS__TUNIT____-LABEL: define {{[^@]+}}@select -; IS__TUNIT____-SAME: () #[[ATTR1]] { -; IS__TUNIT____-NEXT: ret i32 42 -; ; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind readnone willreturn ; IS__CGSCC____-LABEL: define {{[^@]+}}@select ; IS__CGSCC____-SAME: () #[[ATTR1]] { -- 2.7.4