diff options
| author | Hal Finkel <hfinkel@anl.gov> | 2016-12-15 02:53:42 +0000 |
|---|---|---|
| committer | Hal Finkel <hfinkel@anl.gov> | 2016-12-15 02:53:42 +0000 |
| commit | cb9f78e1c3951337de4ba24902eced2c72184319 (patch) | |
| tree | a2290a1daa25da9cc6b1d3a9d9c59564bef3792c /llvm/test/Transforms/JumpThreading | |
| parent | dfe85e2d88cdc7684abdeff6c91356d16a394849 (diff) | |
| download | bcm5719-llvm-cb9f78e1c3951337de4ba24902eced2c72184319.tar.gz bcm5719-llvm-cb9f78e1c3951337de4ba24902eced2c72184319.zip | |
Make processing @llvm.assume more efficient by using operand bundles
There was an efficiency problem with how we processed @llvm.assume in
ValueTracking (and other places). The AssumptionCache tracked all of the
assumptions in a given function. In order to find assumptions relevant to
computing known bits, etc. we searched every assumption in the function. For
ValueTracking, that means that we did O(#assumes * #values) work in InstCombine
and other passes (with a constant factor that can be quite large because we'd
repeat this search at every level of recursion of the analysis).
Several of us discussed this situation at the last developers' meeting, and
this implements the discussed solution: Make the values that an assume might
affect operands of the assume itself. To avoid exposing this detail to
frontends and passes that need not worry about it, I've used the new
operand-bundle feature to add these extra call "operands" in a way that does
not affect the intrinsic's signature. I think this solution is relatively
clean. InstCombine adds these extra operands based on what ValueTracking, LVI,
etc. will need and then those passes need only search the users of the values
under consideration. This should fix the computational-complexity problem.
At this point, no passes depend on the AssumptionCache, and so I'll remove
that as a follow-up change.
Differential Revision: https://reviews.llvm.org/D27259
llvm-svn: 289755
Diffstat (limited to 'llvm/test/Transforms/JumpThreading')
| -rw-r--r-- | llvm/test/Transforms/JumpThreading/assume-edge-dom.ll | 4 | ||||
| -rw-r--r-- | llvm/test/Transforms/JumpThreading/assume.ll | 4 |
2 files changed, 4 insertions, 4 deletions
diff --git a/llvm/test/Transforms/JumpThreading/assume-edge-dom.ll b/llvm/test/Transforms/JumpThreading/assume-edge-dom.ll index f1d0f41e250..ff087693ea8 100644 --- a/llvm/test/Transforms/JumpThreading/assume-edge-dom.ll +++ b/llvm/test/Transforms/JumpThreading/assume-edge-dom.ll @@ -14,12 +14,12 @@ entry: taken: %res1 = call i8* @escape() %a = icmp eq i8* %res1, null - tail call void @llvm.assume(i1 %a) + tail call void @llvm.assume(i1 %a) [ "affected"(i8* %res1) ] br label %done not_taken: %res2 = call i8* @escape() %b = icmp ne i8* %res2, null - tail call void @llvm.assume(i1 %b) + tail call void @llvm.assume(i1 %b) [ "affected"(i8* %res2) ] br label %done ; An assume that can be used to simplify this comparison dominates each diff --git a/llvm/test/Transforms/JumpThreading/assume.ll b/llvm/test/Transforms/JumpThreading/assume.ll index 53010b71c72..fdaa07ff131 100644 --- a/llvm/test/Transforms/JumpThreading/assume.ll +++ b/llvm/test/Transforms/JumpThreading/assume.ll @@ -6,7 +6,7 @@ target triple = "x86_64-unknown-linux-gnu" define i32 @test1(i32 %a, i32 %b) #0 { entry: %cmp = icmp sgt i32 %a, 5 - tail call void @llvm.assume(i1 %cmp) + tail call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ] %cmp1 = icmp sgt i32 %b, 1234 br i1 %cmp1, label %if.then, label %if.else @@ -36,7 +36,7 @@ return: ; preds = %if.else, %if.then, define i32 @test2(i32 %a) #0 { entry: %cmp = icmp sgt i32 %a, 5 - tail call void @llvm.assume(i1 %cmp) + tail call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ] %cmp1 = icmp sgt i32 %a, 3 br i1 %cmp1, label %if.then, label %return |
