Consolidate invariant loads

  If a (assumed) invariant location is loaded multiple times we
  generated a parameter for each location. However, this caused compile
  time problems for several benchmarks (e.g., 445_gobmk in SPEC2006 and
  BT in the NAS benchmarks). Additionally, the code we generate is
  suboptimal as we preload the same location multiple times and perform
  the same checks on all the parameters that refere to the same value.

  With this patch we consolidate the invariant loads in three steps:
    1) During SCoP initialization required invariant loads are put in
       equivalence classes based on their pointer operand. One
       representing load is used to generate a parameter for the whole
       class, thus we never generate multiple parameters for the same
       location.
    2) During the SCoP simplification we remove invariant memory
       accesses that are in the same equivalence class. While doing so
       we build the union of all execution domains as it is only
       important that the location is at least accessed once.
    3) During code generation we only preload one element of each
       equivalence class with the unified execution domain. All others
       are mapped to that preloaded value.

Differential Revision: http://reviews.llvm.org/D13338

llvm-svn: 249853

1 files changed, 37 insertions, 0 deletions

diff --git a/polly/test/Isl/CodeGen/invariant_load_outermost.ll b/polly/test/Isl/CodeGen/invariant_load_outermost.ll
new file mode 100644
index 00000000000..49623fd7824
--- /dev/null
+++ b/polly/test/Isl/CodeGen/invariant_load_outermost.ll
@@ -0,0 +1,37 @@
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+
+; CHECK: polly.start
+
+;    void f(int *A) {
+;      if (*A > 42)
+;        *A = *A + 1;
+;      else
+;        *A = *A - 1;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+entry:
+  br label %entry.split
+
+entry.split:
+  %tmp = load i32, i32* %A, align 4
+  %cmp = icmp sgt i32 %tmp, 42
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %tmp1 = load i32, i32* %A, align 4
+  %add = add nsw i32 %tmp1, 1
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %tmp2 = load i32, i32* %A, align 4
+  %sub = add nsw i32 %tmp2, -1
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %storemerge = phi i32 [ %sub, %if.else ], [ %add, %if.then ]
+  store i32 %storemerge, i32* %A, align 4
+  ret void
+}