llvm/test/Transforms/NaryReassociate/nary-add.ll

   1 ; RUN: opt < %s -passes=nary-reassociate -S | FileCheck %s
   2 ; RUN: opt < %s -passes='nary-reassociate' -S | FileCheck %s
   3
   4 target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
   5
   6 declare void @foo(i32)
   7
   8 ; foo(a + c);
   9 ; foo((a + (b + c));
  10 ;   =>
  11 ; t = a + c;
  12 ; foo(t);
  13 ; foo(t + b);
  14 define void @left_reassociate(i32 %a, i32 %b, i32 %c) {
  15 ; CHECK-LABEL: @left_reassociate(
  16   %1 = add i32 %a, %c
  17 ; CHECK: [[BASE:%[a-zA-Z0-9]+]] = add i32 %a, %c
  18   call void @foo(i32 %1)
  19   %2 = add i32 %b, %c
  20   %3 = add i32 %a, %2
  21 ; CHECK: [[RESULT:%[a-zA-Z0-9]+]] = add i32 [[BASE]], %b
  22   call void @foo(i32 %3)
  23 ; CHECK-NEXT: call void @foo(i32 [[RESULT]])
  24   ret void
  25 }
  26
  27 ; foo(a + c);
  28 ; foo((a + b) + c);
  29 ;   =>
  30 ; t = a + c;
  31 ; foo(t);
  32 ; foo(t + b);
  33 define void @right_reassociate(i32 %a, i32 %b, i32 %c) {
  34 ; CHECK-LABEL: @right_reassociate(
  35   %1 = add i32 %a, %c
  36 ; CHECK: [[BASE:%[a-zA-Z0-9]+]] = add i32 %a, %c
  37   call void @foo(i32 %1)
  38   %2 = add i32 %a, %b
  39   %3 = add i32 %2, %c
  40 ; CHECK: [[RESULT:%[a-zA-Z0-9]+]] = add i32 [[BASE]], %b
  41   call void @foo(i32 %3)
  42 ; CHECK-NEXT: call void @foo(i32 [[RESULT]])
  43   ret void
  44 }
  45
  46 ; t1 = a + c;
  47 ; foo(t1);
  48 ; t2 = a + b;
  49 ; foo(t2);
  50 ; t3 = t2 + c;
  51 ; foo(t3);
  52 ;
  53 ; Do not rewrite t3 into t1 + b because t2 is used elsewhere and is likely free.
  54 define void @no_reassociate(i32 %a, i32 %b, i32 %c) {
  55 ; CHECK-LABEL: @no_reassociate(
  56   %1 = add i32 %a, %c
  57 ; CHECK: add i32 %a, %c
  58   call void @foo(i32 %1)
  59   %2 = add i32 %a, %b
  60 ; CHECK: add i32 %a, %b
  61   call void @foo(i32 %2)
  62   %3 = add i32 %2, %c
  63 ; CHECK: add i32 %2, %c
  64   call void @foo(i32 %3)
  65   ret void
  66 }
  67
  68 ; if (p1)
  69 ;   foo(a + c);
  70 ; if (p2)
  71 ;   foo(a + c);
  72 ; if (p3)
  73 ;   foo((a + b) + c);
  74 ;
  75 ; No action because (a + c) does not dominate ((a + b) + c).
  76 define void @conditional(i1 %p1, i1 %p2, i1 %p3, i32 %a, i32 %b, i32 %c) {
  77 ; CHECK-LABEL: @conditional(
  78 entry:
  79   br i1 %p1, label %then1, label %branch1
  80
  81 then1:
  82   %0 = add i32 %a, %c
  83 ; CHECK: add i32 %a, %c
  84   call void @foo(i32 %0)
  85   br label %branch1
  86
  87 branch1:
  88   br i1 %p2, label %then2, label %branch2
  89
  90 then2:
  91   %1 = add i32 %a, %c
  92 ; CHECK: add i32 %a, %c
  93   call void @foo(i32 %1)
  94   br label %branch2
  95
  96 branch2:
  97   br i1 %p3, label %then3, label %return
  98
  99 then3:
 100   %2 = add i32 %a, %b
 101 ; CHECK: %2 = add i32 %a, %b
 102   %3 = add i32 %2, %c
 103 ; CHECK: add i32 %2, %c
 104   call void @foo(i32 %3)
 105   br label %return
 106
 107 return:
 108   ret void
 109 }
 110
 111 ; This test involves more conditional reassociation candidates. It exercises
 112 ; the stack optimization in tryReassociatedAdd that pops the candidates that
 113 ; do not dominate the current instruction.
 114 ;
 115 ;       def1
 116 ;      cond1
 117 ;      /  \
 118 ;     /    \
 119 ;   cond2  use2
 120 ;   /  \
 121 ;  /    \
 122 ; def2  def3
 123 ;      cond3
 124 ;       /  \
 125 ;      /    \
 126 ;    def4   use1
 127 ;
 128 ; NaryReassociate should match use1 with def3, and use2 with def1.
 129 define void @conditional2(i32 %a, i32 %b, i32 %c, i1 %cond1, i1 %cond2, i1 %cond3) {
 130 entry:
 131   %def1 = add i32 %a, %b
 132   br i1 %cond1, label %bb1, label %bb6
 133 bb1:
 134   br i1 %cond2, label %bb2, label %bb3
 135 bb2:
 136   %def2 = add i32 %a, %b
 137   call void @foo(i32 %def2)
 138   ret void
 139 bb3:
 140   %def3 = add i32 %a, %b
 141   br i1 %cond3, label %bb4, label %bb5
 142 bb4:
 143   %def4 = add i32 %a, %b
 144   call void @foo(i32 %def4)
 145   ret void
 146 bb5:
 147   %0 = add i32 %a, %c
 148   %1 = add i32 %0, %b
 149 ; CHECK: [[t1:%[0-9]+]] = add i32 %def3, %c
 150   call void @foo(i32 %1) ; foo((a + c) + b);
 151 ; CHECK-NEXT: call void @foo(i32 [[t1]])
 152   ret void
 153 bb6:
 154   %2 = add i32 %a, %c
 155   %3 = add i32 %2, %b
 156 ; CHECK: [[t2:%[0-9]+]] = add i32 %def1, %c
 157   call void @foo(i32 %3) ; foo((a + c) + b);
 158 ; CHECK-NEXT: call void @foo(i32 [[t2]])
 159   ret void
 160 }
 161
 162 ; foo((a + b) + c)
 163 ; foo(((a + d) + b) + c)
 164 ;   =>
 165 ; t = (a + b) + c;
 166 ; foo(t);
 167 ; foo(t + d);
 168 define void @quaternary(i32 %a, i32 %b, i32 %c, i32 %d) {
 169 ; CHECK-LABEL: @quaternary(
 170   %1 = add i32 %a, %b
 171   %2 = add i32 %1, %c
 172   call void @foo(i32 %2)
 173 ; CHECK: call void @foo(i32 [[TMP1:%[a-zA-Z0-9]]])
 174   %3 = add i32 %a, %d
 175   %4 = add i32 %3, %b
 176   %5 = add i32 %4, %c
 177 ; CHECK: [[TMP2:%[a-zA-Z0-9]]] = add i32 [[TMP1]], %d
 178   call void @foo(i32 %5)
 179 ; CHECK: call void @foo(i32 [[TMP2]]
 180   ret void
 181 }
 182
 183 define void @iterative(i32 %a, i32 %b, i32 %c) {
 184   %ab = add i32 %a, %b
 185   %abc = add i32 %ab, %c
 186   call void @foo(i32 %abc)
 187
 188   %ab2 = add i32 %ab, %b
 189   %ab2c = add i32 %ab2, %c
 190 ; CHECK: %ab2c = add i32 %abc, %b
 191   call void @foo(i32 %ab2c)
 192 ; CHECK-NEXT: call void @foo(i32 %ab2c)
 193
 194   %ab3 = add i32 %ab2, %b
 195   %ab3c = add i32 %ab3, %c
 196 ; CHECK-NEXT: %ab3c = add i32 %ab2c, %b
 197   call void @foo(i32 %ab3c)
 198 ; CHECK-NEXT: call void @foo(i32 %ab3c)
 199
 200   ret void
 201 }
 202
 203 define void @avoid_infinite_loop(i32 %a, i32 %b) {
 204 ; CHECK-LABEL: @avoid_infinite_loop
 205   %ab = add i32 %a, %b
 206 ; CHECK-NEXT: %ab
 207   %ab2 = add i32 %ab, %b
 208 ; CHECK-NEXT: %ab2
 209   call void @foo(i32 %ab2)
 210 ; CHECK-NEXT: @foo(i32 %ab2)
 211   ret void
 212 }