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