diff options
author | Sanjoy Das <sanjoy@playingwithpointers.com> | 2016-06-26 05:10:45 +0000 |
---|---|---|
committer | Sanjoy Das <sanjoy@playingwithpointers.com> | 2016-06-26 05:10:45 +0000 |
commit | 075766d9d08fa936297c68074c76cb1c5c08a83b (patch) | |
tree | a066fb33251a31537ac5e4456d1eb3160035fce6 | |
parent | e6932065228001fe73a23cbb747ee90197403534 (diff) |
[LoopUnswitch] Unswitch on conditions feeding into guards
Summary:
This is a straightforward extension of what LoopUnswitch does to
branches to guards. That is, we unswitch
```
for (;;) {
...
guard(loop_invariant_cond);
...
}
```
into
```
if (loop_invariant_cond) {
for (;;) {
...
// There is no need to emit guard(true)
...
}
} else {
for (;;) {
...
guard(false);
// SimplifyCFG will clean this up by adding an
// unreachable after the guard(false)
...
}
}
```
Reviewers: majnemer
Subscribers: mcrosier, llvm-commits, mzolotukhin
Differential Revision: http://reviews.llvm.org/D21725
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@273801 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | lib/Transforms/Scalar/LoopUnswitch.cpp | 40 | ||||
-rw-r--r-- | test/Transforms/LoopUnswitch/guards.ll | 97 |
2 files changed, 130 insertions, 7 deletions
diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index 7aa730474d7..0b128a16183 100644 --- a/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -65,6 +65,7 @@ using namespace llvm; STATISTIC(NumBranches, "Number of branches unswitched"); STATISTIC(NumSwitches, "Number of switches unswitched"); +STATISTIC(NumGuards, "Number of guards unswitched"); STATISTIC(NumSelects , "Number of selects unswitched"); STATISTIC(NumTrivial , "Number of unswitches that are trivial"); STATISTIC(NumSimplify, "Number of simplifications of unswitched code"); @@ -514,22 +515,34 @@ bool LoopUnswitch::processCurrentLoop() { return true; } - // Do not unswitch loops containing convergent operations, as we might be - // making them control dependent on the unswitch value when they were not - // before. - // FIXME: This could be refined to only bail if the convergent operation is - // not already control-dependent on the unswitch value. + // Run through the instructions in the loop, keeping track of three things: + // + // - That we do not unswitch loops containing convergent operations, as we + // might be making them control dependent on the unswitch value when they + // were not before. + // FIXME: This could be refined to only bail if the convergent operation is + // not already control-dependent on the unswitch value. + // + // - That basic blocks in the loop contain invokes whose predecessor edges we + // cannot split. + // + // - The set of guard intrinsics encountered (these are non terminator + // instructions that are also profitable to be unswitched). + + SmallVector<IntrinsicInst *, 4> Guards; + for (const auto BB : currentLoop->blocks()) { for (auto &I : *BB) { auto CS = CallSite(&I); if (!CS) continue; if (CS.hasFnAttr(Attribute::Convergent)) return false; - // Return false if any loop blocks contain invokes whose predecessor edges - // we cannot split. if (auto *II = dyn_cast<InvokeInst>(&I)) if (!II->getUnwindDest()->canSplitPredecessors()) return false; + if (auto *II = dyn_cast<IntrinsicInst>(&I)) + if (II->getIntrinsicID() == Intrinsic::experimental_guard) + Guards.push_back(II); } } @@ -549,6 +562,19 @@ bool LoopUnswitch::processCurrentLoop() { return false; } + for (IntrinsicInst *Guard : Guards) { + Value *LoopCond = + FindLIVLoopCondition(Guard->getOperand(0), currentLoop, Changed); + if (LoopCond && + UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) { + // NB! Unswitching (if successful) could have erased some of the + // instructions in Guards leaving dangling pointers there. This is fine + // because we're returning now, and won't look at Guards again. + ++NumGuards; + return true; + } + } + // Loop over all of the basic blocks in the loop. If we find an interior // block that is branching on a loop-invariant condition, we can unswitch this // loop. diff --git a/test/Transforms/LoopUnswitch/guards.ll b/test/Transforms/LoopUnswitch/guards.ll new file mode 100644 index 00000000000..55885338960 --- /dev/null +++ b/test/Transforms/LoopUnswitch/guards.ll @@ -0,0 +1,97 @@ +; RUN: opt -S -loop-unswitch < %s | FileCheck %s + +declare void @llvm.experimental.guard(i1, ...) + +define void @f_0(i32 %n, i32* %ptr, i1 %c) { +; CHECK-LABEL: @f_0( +; CHECK: loop.us: +; CHECK-NOT: guard +; CHECK: loop: +; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ] +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.inc = add i32 %iv, 1 + call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ] + store volatile i32 0, i32* %ptr + %becond = icmp ult i32 %iv.inc, %n + br i1 %becond, label %leave, label %loop + +leave: + ret void +} + +define void @f_1(i32 %n, i32* %ptr, i1 %c_0, i1 %c_1) { +; CHECK-LABEL: @f_1( +; CHECK: loop.us.us: +; CHECK-NOT: guard +; CHECK: loop.us: +; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 2) ] +; CHECK-NOT: guard +; CHECK: loop.us1: +; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 1) ] +; CHECK-NOT: guard +; CHECK: loop: +; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 1) ] +; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 2) ] +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.inc = add i32 %iv, 1 + call void(i1, ...) @llvm.experimental.guard(i1 %c_0) [ "deopt"(i32 1) ] + store volatile i32 0, i32* %ptr + call void(i1, ...) @llvm.experimental.guard(i1 %c_1) [ "deopt"(i32 2) ] + %becond = icmp ult i32 %iv.inc, %n + br i1 %becond, label %leave, label %loop + +leave: + ret void +} + +; Basic negative test + +define void @f_3(i32 %n, i32* %ptr, i1* %c_ptr) { +; CHECK-LABEL: @f_3( +; CHECK-NOT: loop.us: +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.inc = add i32 %iv, 1 + %c = load volatile i1, i1* %c_ptr + call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ] + store volatile i32 0, i32* %ptr + %becond = icmp ult i32 %iv.inc, %n + br i1 %becond, label %leave, label %loop + +leave: + ret void +} + +define void @f_4(i32 %n, i32* %ptr, i1 %c) { +; CHECK-LABEL: @f_4( +; +; Demonstrate that unswitching on one guard can cause another guard to +; be erased (this has implications on what guards we can keep raw +; pointers to). +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.inc = add i32 %iv, 1 + call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"(i32 1) ] + store volatile i32 0, i32* %ptr + %neg = xor i1 %c, 1 + call void(i1, ...) @llvm.experimental.guard(i1 %neg) [ "deopt"(i32 2) ] + %becond = icmp ult i32 %iv.inc, %n + br i1 %becond, label %leave, label %loop + +leave: + ret void +} |