From a4a7b8d69e9fa5b6fb0b919d7c6f48bb95459ebf Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Fri, 3 Mar 2017 18:19:15 +0000
Subject: [PATCH] [LoopUnrolling] Peel loops with invariant backedge Phi input

Summary:
If a loop contains a Phi node which has an invariant input from back
edge, it is profitable to peel such loops (rather than unroll them) to
use the advantage that this Phi is always invariant starting from 2nd
iteration. After the 1st iteration is peeled, other optimizations can
potentially simplify calculations with this invariant.

Patch by Max Kazantsev!

Reviewers: sanjoy, apilipenko, igor-laevsky, anna, mkuper, reames

Reviewed By: mkuper

Subscribers: mkuper, mzolotukhin, llvm-commits

Differential Revision: https://reviews.llvm.org/D30161

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@296898 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Utils/LoopUnrollPeel.cpp       | 25 +++++++++++++++++++
 .../LoopUnroll/peel-loop-not-forced.ll        | 25 +++++++++++++++++++
 2 files changed, 50 insertions(+)
 create mode 100644 test/Transforms/LoopUnroll/peel-loop-not-forced.ll

diff --git a/lib/Transforms/Utils/LoopUnrollPeel.cpp b/lib/Transforms/Utils/LoopUnrollPeel.cpp
index 0227f8a5d13..e45aef88722 100644
--- a/lib/Transforms/Utils/LoopUnrollPeel.cpp
+++ b/lib/Transforms/Utils/LoopUnrollPeel.cpp
@@ -71,6 +71,31 @@ void llvm::computePeelCount(Loop *L, unsigned LoopSize,
   if (!L->empty())
     return;
 
+  // Try to find a Phi node that has the same loop invariant as an input from
+  // its only back edge. If there is such Phi, peeling 1 iteration from the
+  // loop is profitable, because starting from 2nd iteration we will have an
+  // invariant instead of this Phi.
+  if (auto *BackEdge = L->getLoopLatch()) {
+    BasicBlock *Header = L->getHeader();
+    // Iterate over Phis to find one with invariant input on back edge.
+    bool FoundCandidate = false;
+    PHINode *Phi;
+    for (auto BI = Header->begin(); Phi = dyn_cast<PHINode>(&*BI); ++BI) {
+      Value *Input = Phi->getIncomingValueForBlock(BackEdge);
+      if (L->isLoopInvariant(Input)) {
+        FoundCandidate = true;
+        break;
+      }
+    }
+    if (FoundCandidate) {
+      DEBUG(dbgs() << "Peel one iteration to get rid of " << *Phi
+                   << " because starting from 2nd iteration it is always"
+                   << " an invariant\n");
+      UP.PeelCount = 1;
+      return;
+    }
+  }
+
   // Bail if we know the statically calculated trip count.
   // In this case we rather prefer partial unrolling.
   if (TripCount)
diff --git a/test/Transforms/LoopUnroll/peel-loop-not-forced.ll b/test/Transforms/LoopUnroll/peel-loop-not-forced.ll
new file mode 100644
index 00000000000..afb03a22900
--- /dev/null
+++ b/test/Transforms/LoopUnroll/peel-loop-not-forced.ll
@@ -0,0 +1,25 @@
+; RUN: opt < %s -S -loop-unroll | FileCheck %s
+
+define i32 @invariant_backedge_1(i32 %a, i32 %b) {
+; CHECK-LABEL: @invariant_backedge_1
+; CHECK-NOT:     %plus = phi
+; CHECK:       loop.peel:
+; CHECK:       loop:
+; CHECK:         %i = phi
+; CHECK:         %sum = phi
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
+  %sum = phi i32 [ 0, %entry ], [ %incsum, %loop ]
+  %plus = phi i32 [ %a, %entry ], [ %b, %loop ]
+
+  %incsum = add i32 %sum, %plus
+  %inc = add i32 %i, 1
+  %cmp = icmp slt i32 %i, 1000
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret i32 %sum
+}
-- 
2.50.1