test/Transforms/NaryReassociate/nary-add.ll

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