From 1962621a7e3350ed3677645dba6d0f20a765db4f Mon Sep 17 00:00:00 2001 From: Anna Thomas Date: Fri, 17 Aug 2018 13:44:00 +0000 Subject: [LICM] Add a diagnostic analysis for identifying alias information Summary: Currently, in LICM, we use the alias set tracker to identify if the instruction (we're interested in hoisting) aliases with instruction that modifies that memory location. This patch adds an LICM alias analysis diagnostic tool that checks the mod ref info of the instruction we are interested in hoisting/sinking, with every instruction in the loop. Because of O(N^2) complexity this is now only a diagnostic tool to show the limitation we have with the alias set tracker and is OFF by default. Test cases show the difference with the diagnostic analysis tool, where we're able to hoist out loads and readonly + argmemonly calls from the loop, where the alias set tracker analysis is not able to hoist these instructions out. Reviewers: reames, mkazantsev, fedor.sergeev, hfinkel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D50854 llvm-svn: 340026 --- llvm/test/Transforms/LICM/argmemonly-call.ll | 31 +++++++++- llvm/test/Transforms/LICM/invariant.start.ll | 42 ++++++++++++-- llvm/test/Transforms/LICM/read-only-calls.ll | 85 ++++++++++++++++++++++++++++ 3 files changed, 150 insertions(+), 8 deletions(-) create mode 100644 llvm/test/Transforms/LICM/read-only-calls.ll (limited to 'llvm/test') diff --git a/llvm/test/Transforms/LICM/argmemonly-call.ll b/llvm/test/Transforms/LICM/argmemonly-call.ll index fe7c6af6d6d..b7d7d6a3953 100644 --- a/llvm/test/Transforms/LICM/argmemonly-call.ll +++ b/llvm/test/Transforms/LICM/argmemonly-call.ll @@ -1,5 +1,8 @@ -; RUN: opt -S -basicaa -licm %s | FileCheck %s -; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s +; RUN: opt -S -basicaa -licm -licm-n2-threshold=0 %s | FileCheck %s +; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2 +; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2 + declare i32 @foo() readonly argmemonly nounwind declare i32 @foo2() readonly nounwind declare i32 @bar(i32* %loc2) readonly argmemonly nounwind @@ -68,3 +71,27 @@ loop: store i32 %res, i32* %loc br label %loop } + +declare i32 @foo_new(i32*) readonly +; With the default AST mechanism used by LICM for alias analysis, +; we clump foo_new with bar. +; With the N2 Alias analysis diagnostic tool, we are able to hoist the +; argmemonly bar call out of the loop. + +define void @test5(i32* %loc2, i32* noalias %loc) { +; ALIAS-N2-LABEL: @test5 +; ALIAS-N2: @bar +; ALIAS-N2-LABEL: loop: + +; CHECK-LABEL: @test5 +; CHECK-LABEL: loop: +; CHECK: @bar + br label %loop + +loop: + %res1 = call i32 @bar(i32* %loc2) + %res = call i32 @foo_new(i32* %loc2) + store volatile i32 %res1, i32* %loc + br label %loop +} + diff --git a/llvm/test/Transforms/LICM/invariant.start.ll b/llvm/test/Transforms/LICM/invariant.start.ll index ff17bd096ce..3ac6793d185 100644 --- a/llvm/test/Transforms/LICM/invariant.start.ll +++ b/llvm/test/Transforms/LICM/invariant.start.ll @@ -1,7 +1,9 @@ -; RUN: opt -licm -basicaa < %s -S | FileCheck %s -; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s +; RUN: opt -licm -basicaa -licm-n2-threshold=0 < %s -S | FileCheck %s +; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2 +; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2 -; TODO: should be able to hoist both load and invariant.start +; TODO: By default (without the -licm-n2-threshold value), we should be able to hoist both load and invariant.start define void @test1(i1 %cond, i32* %ptr) { ; CHECK-LABEL: @test1( ; CHECK-LABEL: entry: @@ -9,6 +11,12 @@ define void @test1(i1 %cond, i32* %ptr) { ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr) ; CHECK: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: @test1( +; ALIAS-N2-LABEL: entry: +; ALIAS-N2: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: loop: +; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr) + entry: br label %loop @@ -20,7 +28,7 @@ loop: br label %loop } -;; TODO: despite the loop varying invariant.start, we should be +;; TODO: By default, despite the loop varying invariant.start, we should be ;; able to hoist the load define void @test2(i1 %cond, i32* %ptr) { ; CHECK-LABEL: @test2( @@ -28,7 +36,12 @@ define void @test2(i1 %cond, i32* %ptr) { ; CHECK-LABEL: loop: ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %piv) ; CHECK: %val = load i32, i32* %ptr - + +; ALIAS-N2-LABEL: @test2( +; ALIAS-N2-LABEL: entry: +; ALIAS-N2: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: loop: +; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %piv) entry: br label %loop @@ -41,7 +54,7 @@ loop: br label %loop } -; Should be able to hoist since store doesn't alias +; By default, should be able to hoist since store doesn't alias define void @test3(i1 %cond, i32* %ptr) { ; CHECK-LABEL: @test3( ; CHECK-LABEL: entry: @@ -49,6 +62,11 @@ define void @test3(i1 %cond, i32* %ptr) { ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr) ; CHECK: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: @test3( +; ALIAS-N2-LABEL: entry: +; ALIAS-N2: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: loop: +; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr) entry: br label %loop @@ -72,6 +90,12 @@ define void @test4(i1 %cond, i32* %ptr) { ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr) ; CHECK: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: @test4( +; ALIAS-N2-LABEL: entry: +; ALIAS-N2-LABEL: loop: +; ALIAS-N2: store i32 0, i32* %ptr +; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr) +; ALIAS-N2: %val = load i32, i32* %ptr entry: br label %loop @@ -93,6 +117,12 @@ define void @test5(i1 %cond, i32* %ptr) { ; CHECK: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr) ; CHECK: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: @test5( +; ALIAS-N2-LABEL: entry: +; ALIAS-N2-LABEL: loop: +; ALIAS-N2: store i32 0, i32* %ptr +; ALIAS-N2: call {}* @llvm.invariant.start.p0i32(i64 4, i32* %ptr) +; ALIAS-N2: %val = load i32, i32* %ptr entry: br label %loop diff --git a/llvm/test/Transforms/LICM/read-only-calls.ll b/llvm/test/Transforms/LICM/read-only-calls.ll new file mode 100644 index 00000000000..0a378144fb7 --- /dev/null +++ b/llvm/test/Transforms/LICM/read-only-calls.ll @@ -0,0 +1,85 @@ +; RUN: opt -S -basicaa -licm -licm-n2-threshold=0 %s | FileCheck %s +; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2 +; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2 + +; We should be able to hoist loads in presence of read only calls and stores +; that do not alias. + +; Since LICM uses the AST mechanism for alias analysis, we will clump +; together all loads and stores in one set along with the read-only call. +; This prevents hoisting load that doesn't alias with any other memory +; operations. + +declare void @foo(i64, i32*) readonly + +; hoist the load out with the n2-threshold +; since it doesn't alias with the store. +; default AST mechanism clumps all memory locations in one set because of the +; readonly call +define void @test1(i32* %ptr) { +; CHECK-LABEL: @test1( +; CHECK-LABEL: entry: +; CHECK-LABEL: loop: +; CHECK: %val = load i32, i32* %ptr + +; ALIAS-N2-LABEL: @test1( +; ALIAS-N2-LABEL: entry: +; ALIAS-N2: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: loop: +entry: + br label %loop + +loop: + %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ] + %val = load i32, i32* %ptr + call void @foo(i64 4, i32* %ptr) + %p2 = getelementptr i32, i32* %ptr, i32 1 + store volatile i32 0, i32* %p2 + %x.inc = add i32 %x, %val + br label %loop +} + +; can hoist out load with the default AST and the alias analysis mechanism. +define void @test2(i32* %ptr) { +; CHECK-LABEL: @test2( +; CHECK-LABEL: entry: +; CHECK: %val = load i32, i32* %ptr +; CHECK-LABEL: loop: + +; ALIAS-N2-LABEL: @test2( +; ALIAS-N2-LABEL: entry: +; ALIAS-N2: %val = load i32, i32* %ptr +; ALIAS-N2-LABEL: loop: +entry: + br label %loop + +loop: + %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ] + %val = load i32, i32* %ptr + call void @foo(i64 4, i32* %ptr) + %x.inc = add i32 %x, %val + br label %loop +} + +; cannot hoist load since not guaranteed to execute +define void @test3(i32* %ptr) { +; CHECK-LABEL: @test3( +; CHECK-LABEL: entry: +; CHECK-LABEL: loop: +; CHECK: %val = load i32, i32* %ptr + +; ALIAS-N2-LABEL: @test3( +; ALIAS-N2-LABEL: entry: +; ALIAS-N2-LABEL: loop: +; ALIAS-N2: %val = load i32, i32* %ptr +entry: + br label %loop + +loop: + %x = phi i32 [ 0, %entry ], [ %x.inc, %loop ] + call void @foo(i64 4, i32* %ptr) + %val = load i32, i32* %ptr + %x.inc = add i32 %x, %val + br label %loop +} -- cgit v1.2.3