From 88554df4a2b801a11964a2668acfac2d68ab14bc Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Sun, 31 May 2009 09:03:40 +0000
Subject: [PATCH] Be more aggressive in doing LoadPRE by tracing backwards when
 a block only has a single predecessor.

Patch by Jakub Staszak.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72661 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/GVN.cpp          | 43 +++++++++++++++++++++++---
 test/Transforms/GVN/pre-single-pred.ll | 32 +++++++++++++++++++
 2 files changed, 71 insertions(+), 4 deletions(-)
 create mode 100644 test/Transforms/GVN/pre-single-pred.ll

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index 810ef6b5622..733dfa97a15 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -1055,11 +1055,29 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
   // that we only have to insert *one* load (which means we're basically moving
   // the load, not inserting a new one).
   
-  // Everything we do here is based on local predecessors of LI's block.  If it
-  // only has one predecessor, bail now.
+  SmallPtrSet<BasicBlock *, 4> Blockers;
+  for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i)
+    Blockers.insert(UnavailableBlocks[i]);
+
+  // Lets find first basic block with more than one predecessor.  Walk backwards
+  // through predecessors if needed.
   BasicBlock *LoadBB = LI->getParent();
-  if (LoadBB->getSinglePredecessor())
-    return false;
+  BasicBlock *TmpBB = LoadBB;
+
+  bool isSinglePred = false;
+  while (TmpBB->getSinglePredecessor()) {
+    isSinglePred = true;
+    TmpBB = TmpBB->getSinglePredecessor();
+    if (!TmpBB) // If haven't found any, bail now.
+      return false;
+    if (TmpBB == LoadBB) // Infinite (unreachable) loop.
+      return false;
+    if (Blockers.count(TmpBB))
+      return false;
+  }
+  
+  assert(TmpBB);
+  LoadBB = TmpBB;
   
   // If we have a repl set with LI itself in it, this means we have a loop where
   // at least one of the values is LI.  Since this means that we won't be able
@@ -1069,6 +1087,23 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
     if (ValuesPerBlock[i].second == LI)
       return false;
   
+  if (isSinglePred) {
+    bool isHot = false;
+    for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i)
+      if (Instruction *I = dyn_cast<Instruction>(ValuesPerBlock[i].second))
+	// "Hot" Instruction is in some loop (because it dominates its dep. 
+	// instruction).
+	if (DT->dominates(LI, I)) { 
+	  isHot = true;
+	  break;
+	}
+
+    // We are interested only in "hot" instructions. We don't want to do any
+    // mis-optimizations here.
+    if (!isHot)
+      return false;
+  }
+
   // Okay, we have some hope :).  Check to see if the loaded value is fully
   // available in all but one predecessor.
   // FIXME: If we could restructure the CFG, we could make a common pred with
diff --git a/test/Transforms/GVN/pre-single-pred.ll b/test/Transforms/GVN/pre-single-pred.ll
new file mode 100644
index 00000000000..b735ea9827c
--- /dev/null
+++ b/test/Transforms/GVN/pre-single-pred.ll
@@ -0,0 +1,32 @@
+; RUN: llvm-as < %s | opt -gvn -enable-load-pre | llvm-dis | not grep {tmp3 = load}
+
+define i32 @f(i32* nocapture %p, i32 %n) nounwind {
+entry:
+	br label %for.cond
+
+for.cond:		; preds = %for.inc, %entry
+	%i.0 = phi i32 [ 0, %entry ], [ %indvar.next, %for.inc ]		; <i32> [#uses=2]
+	%cmp = icmp slt i32 %i.0, %n		; <i1> [#uses=1]
+	br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:		; preds = %for.cond
+	br label %for.end
+
+for.body:		; preds = %for.cond
+	%tmp3 = load i32* %p		; <i32> [#uses=1]
+	%dec = add i32 %tmp3, -1		; <i32> [#uses=2]
+	store i32 %dec, i32* %p
+	%cmp6 = icmp slt i32 %dec, 0		; <i1> [#uses=1]
+	br i1 %cmp6, label %for.body.for.end_crit_edge, label %for.inc
+
+for.body.for.end_crit_edge:		; preds = %for.body
+	br label %for.end
+
+for.inc:		; preds = %for.body
+	%indvar.next = add i32 %i.0, 1		; <i32> [#uses=1]
+	br label %for.cond
+
+for.end:		; preds = %for.body.for.end_crit_edge, %for.cond.for.end_crit_edge
+	%tmp9 = load i32* %p		; <i32> [#uses=1]
+	ret i32 %tmp9
+}
-- 
2.34.1