Completely rework the datastructure GVN uses to represent the value number to leader mapping. Previously,

this was a tree of hashtables, and a query recursed into the table for the immediate dominator ad infinitum
if the initial lookup failed.  This led to really bad performance on tall, narrow CFGs.

We can instead replace it with what is conceptually a multimap of value numbers to leaders (actually
represented by a hashtable with a list of Value*'s as the value type), and then
determine which leader from that set to use very cheaply thanks to the DFS numberings maintained by
DominatorTree.  Because there are typically few duplicates of a given value, this scan tends to be
quite fast.  Additionally, we use a custom linked list and BumpPtr allocation to avoid any unnecessary
allocation in representing the value-side of the multimap.

This change brings with it a 15% (!) improvement in the total running time of GVN on 403.gcc, which I
think is pretty good considering that includes all the "real work" being done by MemDep as well.

The one downside to this approach is that we can no longer use GVN to perform simple conditional progation,
but that seems like an acceptable loss since we now have LVI and CorrelatedValuePropagation to pick up
the slack.  If you see conditional propagation that's not happening, please file bugs against LVI or CVP.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119714 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 0 insertions, 52 deletions

diff --git a/test/Transforms/GVN/condprop.ll b/test/Transforms/GVN/condprop.ll
deleted file mode 100644
index f7bcacd613..0000000000
--- a/test/Transforms/GVN/condprop.ll
+++ /dev/null
@@ -1,52 +0,0 @@
-; RUN: opt < %s -basicaa -gvn -S | grep {br i1 false}
-
-@a = external global i32		; <i32*> [#uses=7]
-
-define i32 @foo() nounwind {
-entry:
-	%0 = load i32* @a, align 4		; <i32> [#uses=1]
-	%1 = icmp eq i32 %0, 4		; <i1> [#uses=1]
-	br i1 %1, label %bb, label %bb1
-
-bb:		; preds = %entry
-	br label %bb8
-
-bb1:		; preds = %entry
-	%2 = load i32* @a, align 4		; <i32> [#uses=1]
-	%3 = icmp eq i32 %2, 5		; <i1> [#uses=1]
-	br i1 %3, label %bb2, label %bb3
-
-bb2:		; preds = %bb1
-	br label %bb8
-
-bb3:		; preds = %bb1
-	%4 = load i32* @a, align 4		; <i32> [#uses=1]
-	%5 = icmp eq i32 %4, 4		; <i1> [#uses=1]
-	br i1 %5, label %bb4, label %bb5
-
-bb4:		; preds = %bb3
-	%6 = load i32* @a, align 4		; <i32> [#uses=1]
-	%7 = add i32 %6, 5		; <i32> [#uses=1]
-	br label %bb8
-
-bb5:		; preds = %bb3
-	%8 = load i32* @a, align 4		; <i32> [#uses=1]
-	%9 = icmp eq i32 %8, 5		; <i1> [#uses=1]
-	br i1 %9, label %bb6, label %bb7
-
-bb6:		; preds = %bb5
-	%10 = load i32* @a, align 4		; <i32> [#uses=1]
-	%11 = add i32 %10, 4		; <i32> [#uses=1]
-	br label %bb8
-
-bb7:		; preds = %bb5
-	%12 = load i32* @a, align 4		; <i32> [#uses=1]
-	br label %bb8
-
-bb8:		; preds = %bb7, %bb6, %bb4, %bb2, %bb
-	%.0 = phi i32 [ %12, %bb7 ], [ %11, %bb6 ], [ %7, %bb4 ], [ 4, %bb2 ], [ 5, %bb ]		; <i32> [#uses=1]
-	br label %return
-
-return:		; preds = %bb8
-	ret i32 %.0
-}