test/Transforms/Reassociate/xor_reassoc.ll

   1 ;RUN: opt -S -reassociate < %s | FileCheck %s
   2
   3 ; ==========================================================================
   4 ;
   5 ;   Xor reassociation general cases
   6 ;
   7 ; ==========================================================================
   8
   9 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3, where c3 = c1^c2
  10 ;
  11 define i32 @xor1(i32 %x) {
  12   %or = or i32 %x, 123
  13   %or1 = or i32 %x, 456
  14   %xor = xor i32 %or, %or1
  15   ret i32 %xor
  16
  17 ;CHECK-LABEL: @xor1(
  18 ;CHECK: %and.ra = and i32 %x, 435
  19 ;CHECK: %xor = xor i32 %and.ra, 435
  20 }
  21
  22 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3, where c3 = c1^c2
  23 ;
  24 define <2 x i32> @xor1_vec(<2 x i32> %x) {
  25   %or = or <2 x i32> %x, <i32 123, i32 123>
  26   %or1 = or <2 x i32> %x, <i32 456, i32 456>
  27   %xor = xor <2 x i32> %or, %or1
  28   ret <2 x i32> %xor
  29
  30 ;CHECK-LABEL: @xor1_vec(
  31 ;CHECK: %and.ra = and <2 x i32> %x, <i32 435, i32 435>
  32 ;CHECK: %xor = xor <2 x i32> %and.ra, <i32 435, i32 435>
  33 }
  34
  35 ; Test rule : (x & c1) ^ (x & c2) = (x & (c1^c2))
  36 ; Real testing case : (x & 123) ^ y ^ (x & 345) => (x & 435) ^ y
  37 define i32 @xor2(i32 %x, i32 %y) {
  38   %and = and i32 %x, 123
  39   %xor = xor i32 %and, %y
  40   %and1 = and i32 %x, 456
  41   %xor2 = xor i32 %xor, %and1
  42   ret i32 %xor2
  43
  44 ;CHECK-LABEL: @xor2(
  45 ;CHECK: %and.ra = and i32 %x, 435
  46 ;CHECK: %xor2 = xor i32 %and.ra, %y
  47 }
  48
  49 ; Test rule : (x & c1) ^ (x & c2) = (x & (c1^c2))
  50 ; Real testing case : (x & 123) ^ y ^ (x & 345) => (x & 435) ^ y
  51 define <2 x i32> @xor2_vec(<2 x i32> %x, <2 x i32> %y) {
  52   %and = and <2 x i32> %x, <i32 123, i32 123>
  53   %xor = xor <2 x i32> %and, %y
  54   %and1 = and <2 x i32> %x, <i32 456, i32 456>
  55   %xor2 = xor <2 x i32> %xor, %and1
  56   ret <2 x i32> %xor2
  57
  58 ;CHECK-LABEL: @xor2_vec(
  59 ;CHECK: %and.ra = and <2 x i32> %x, <i32 435, i32 435>
  60 ;CHECK: %xor2 = xor <2 x i32> %and.ra, %y
  61 }
  62
  63 ; Test rule: (x | c1) ^ (x & c2) = (x & c3) ^ c1, where c3 = ~c1 ^ c2
  64 ;  c3 = ~c1 ^ c2
  65 define i32 @xor3(i32 %x, i32 %y) {
  66   %or = or i32 %x, 123
  67   %xor = xor i32 %or, %y
  68   %and = and i32 %x, 456
  69   %xor1 = xor i32 %xor, %and
  70   ret i32 %xor1
  71
  72 ;CHECK-LABEL: @xor3(
  73 ;CHECK: %and.ra = and i32 %x, -436
  74 ;CHECK: %xor = xor i32 %y, 123
  75 ;CHECK: %xor1 = xor i32 %xor, %and.ra
  76 }
  77
  78 ; Test rule: (x | c1) ^ (x & c2) = (x & c3) ^ c1, where c3 = ~c1 ^ c2
  79 ;  c3 = ~c1 ^ c2
  80 define <2 x i32> @xor3_vec(<2 x i32> %x, <2 x i32> %y) {
  81   %or = or <2 x i32> %x, <i32 123, i32 123>
  82   %xor = xor <2 x i32> %or, %y
  83   %and = and <2 x i32> %x, <i32 456, i32 456>
  84   %xor1 = xor <2 x i32> %xor, %and
  85   ret <2 x i32> %xor1
  86
  87 ;CHECK-LABEL: @xor3_vec(
  88 ;CHECK: %and.ra = and <2 x i32> %x, <i32 -436, i32 -436>
  89 ;CHECK: %xor = xor <2 x i32> %y, <i32 123, i32 123>
  90 ;CHECK: %xor1 = xor <2 x i32> %xor, %and.ra
  91 }
  92
  93 ; Test rule: (x | c1) ^ c2 = (x & ~c1) ^ (c1 ^ c2)
  94 define i32 @xor4(i32 %x, i32 %y) {
  95   %and = and i32 %x, -124
  96   %xor = xor i32 %y, 435
  97   %xor1 = xor i32 %xor, %and
  98   ret i32 %xor1
  99 ; CHECK-LABEL: @xor4(
 100 ; CHECK: %and = and i32 %x, -124
 101 ; CHECK: %xor = xor i32 %y, 435
 102 ; CHECK: %xor1 = xor i32 %xor, %and
 103 }
 104
 105 ; Test rule: (x | c1) ^ c2 = (x & ~c1) ^ (c1 ^ c2)
 106 define <2 x i32> @xor4_vec(<2 x i32> %x, <2 x i32> %y) {
 107   %and = and <2 x i32> %x, <i32 -124, i32 -124>
 108   %xor = xor <2 x i32> %y, <i32 435, i32 435>
 109   %xor1 = xor <2 x i32> %xor, %and
 110   ret <2 x i32> %xor1
 111 ; CHECK-LABEL: @xor4_vec(
 112 ; CHECK: %and = and <2 x i32> %x, <i32 -124, i32 -124>
 113 ; CHECK: %xor = xor <2 x i32> %y, <i32 435, i32 435>
 114 ; CHECK: %xor1 = xor <2 x i32> %xor, %and
 115 }
 116
 117 ; ==========================================================================
 118 ;
 119 ;  Xor reassociation special cases
 120 ;
 121 ; ==========================================================================
 122
 123 ; Special case1:
 124 ;  (x | c1) ^ (x & ~c1) = c1
 125 define i32 @xor_special1(i32 %x, i32 %y) {
 126   %or = or i32 %x, 123
 127   %xor = xor i32 %or, %y
 128   %and = and i32 %x, -124
 129   %xor1 = xor i32 %xor, %and
 130   ret i32 %xor1
 131 ; CHECK-LABEL: @xor_special1(
 132 ; CHECK: %xor1 = xor i32 %y, 123
 133 ; CHECK: ret i32 %xor1
 134 }
 135
 136 ; Special case1:
 137 ;  (x | c1) ^ (x & ~c1) = c1
 138 define <2 x i32> @xor_special1_vec(<2 x i32> %x, <2 x i32> %y) {
 139   %or = or <2 x i32> %x, <i32 123, i32 123>
 140   %xor = xor <2 x i32> %or, %y
 141   %and = and <2 x i32> %x, <i32 -124, i32 -124>
 142   %xor1 = xor <2 x i32> %xor, %and
 143   ret <2 x i32> %xor1
 144 ; CHECK-LABEL: @xor_special1_vec(
 145 ; CHECK: %xor1 = xor <2 x i32> %y, <i32 123, i32 123>
 146 ; CHECK: ret <2 x i32> %xor1
 147 }
 148
 149 ; Special case1:
 150 ;  (x | c1) ^ (x & c1) = x ^ c1
 151 define i32 @xor_special2(i32 %x, i32 %y) {
 152   %or = or i32 %x, 123
 153   %xor = xor i32 %or, %y
 154   %and = and i32 %x, 123
 155   %xor1 = xor i32 %xor, %and
 156   ret i32 %xor1
 157 ; CHECK-LABEL: @xor_special2(
 158 ; CHECK: %xor = xor i32 %x, 123
 159 ; CHECK: %xor1 = xor i32 %xor, %y
 160 ; CHECK: ret i32 %xor1
 161 }
 162
 163 ; Special case1:
 164 ;  (x | c1) ^ (x & c1) = x ^ c1
 165 define <2 x i32> @xor_special2_vec(<2 x i32> %x, <2 x i32> %y) {
 166   %or = or <2 x i32> %x, <i32 123, i32 123>
 167   %xor = xor <2 x i32> %or, %y
 168   %and = and <2 x i32> %x, <i32 123, i32 123>
 169   %xor1 = xor <2 x i32> %xor, %and
 170   ret <2 x i32> %xor1
 171 ; CHECK-LABEL: @xor_special2_vec(
 172 ; CHECK: %xor = xor <2 x i32> %x, <i32 123, i32 123>
 173 ; CHECK: %xor1 = xor <2 x i32> %xor, %y
 174 ; CHECK: ret <2 x i32> %xor1
 175 }
 176
 177 ; (x | c1) ^ (x | c1) => 0
 178 define i32 @xor_special3(i32 %x) {
 179   %or = or i32 %x, 123
 180   %or1 = or i32 %x, 123
 181   %xor = xor i32 %or, %or1
 182   ret i32 %xor
 183 ;CHECK-LABEL: @xor_special3(
 184 ;CHECK: ret i32 0
 185 }
 186
 187 ; (x | c1) ^ (x | c1) => 0
 188 define <2 x i32> @xor_special3_vec(<2 x i32> %x) {
 189   %or = or <2 x i32> %x, <i32 123, i32 123>
 190   %or1 = or <2 x i32> %x, <i32 123, i32 123>
 191   %xor = xor <2 x i32> %or, %or1
 192   ret <2 x i32> %xor
 193 ;CHECK-LABEL: @xor_special3_vec(
 194 ;CHECK: ret <2 x i32> zeroinitializer
 195 }
 196
 197 ; (x & c1) ^ (x & c1) => 0
 198 define i32 @xor_special4(i32 %x) {
 199   %or = and i32 %x, 123
 200   %or1 = and i32 123, %x
 201   %xor = xor i32 %or, %or1
 202   ret i32 %xor
 203 ;CHECK-LABEL: @xor_special4(
 204 ;CHECK: ret i32 0
 205 }
 206
 207 ; (x & c1) ^ (x & c1) => 0
 208 define <2 x i32> @xor_special4_vec(<2 x i32> %x) {
 209   %or = and <2 x i32> %x, <i32 123, i32 123>
 210   %or1 = and <2 x i32> <i32 123, i32 123>, %x
 211   %xor = xor <2 x i32> %or, %or1
 212   ret <2 x i32> %xor
 213 ;CHECK-LABEL: @xor_special4_vec(
 214 ;CHECK: ret <2 x i32> zeroinitializer
 215 }
 216
 217 ; ==========================================================================
 218 ;
 219 ;  Xor reassociation curtail code size
 220 ;
 221 ; ==========================================================================
 222
 223 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3
 224 ; is enabled if one of operands has multiple uses
 225 ;
 226 define i32 @xor_ra_size1(i32 %x) {
 227   %or = or i32 %x, 123
 228   %or1 = or i32 %x, 456
 229   %xor = xor i32 %or, %or1
 230
 231   %add = add i32 %xor, %or
 232   ret i32 %add
 233 ;CHECK-LABEL: @xor_ra_size1(
 234 ;CHECK: %xor = xor i32 %and.ra, 435
 235 }
 236
 237 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3
 238 ; is disenabled if bothf operands has multiple uses.
 239 ;
 240 define i32 @xor_ra_size2(i32 %x) {
 241   %or = or i32 %x, 123
 242   %or1 = or i32 %x, 456
 243   %xor = xor i32 %or, %or1
 244
 245   %add = add i32 %xor, %or
 246   %add2 = add i32 %add, %or1
 247   ret i32 %add2
 248
 249 ;CHECK-LABEL: @xor_ra_size2(
 250 ;CHECK: %or1 = or i32 %x, 456
 251 ;CHECK: %xor = xor i32 %or, %or1
 252 }
 253
 254
 255 ; ==========================================================================
 256 ;
 257 ;  Xor reassociation bugs
 258 ;
 259 ; ==========================================================================
 260
 261 @xor_bug1_data = external global <{}>, align 4
 262 define void @xor_bug1() {
 263   %1 = ptrtoint i32* undef to i64
 264   %2 = xor i64 %1, ptrtoint (<{}>* @xor_bug1_data to i64)
 265   %3 = and i64 undef, %2
 266   ret void
 267 }
 268
 269 ; The bug was that when the compiler optimize "(x | c1)" ^ "(x & c2)", it may
 270 ; swap the two xor-subexpressions if they are not in canoninical order; however,
 271 ; when optimizer swaps two sub-expressions, if forgot to swap the cached value
 272 ; of c1 and c2 accordingly, hence cause the problem.
 273 ;
 274 define i32 @xor_bug2(i32, i32, i32, i32) {
 275   %5 = mul i32 %0, 123
 276   %6 = add i32 %2, 24
 277   %7 = add i32 %1, 8
 278   %8 = and i32 %1, 3456789
 279   %9 = or i32 %8,  4567890
 280   %10 = and i32 %1, 543210987
 281   %11 = or i32 %1, 891034567
 282   %12 = and i32 %2, 255
 283   %13 = xor i32 %9, %10
 284   %14 = xor i32 %11, %13
 285   %15 = xor i32 %5, %14
 286   %16 = and i32 %3, 255
 287   %17 = xor i32 %16, 42
 288   %18 = add i32 %6, %7
 289   %19 = add i32 %18, %12
 290   %20 = add i32 %19, %15
 291   ret i32 %20
 292 ;CHECK-LABEL: @xor_bug2(
 293 ;CHECK: xor i32 %5, 891034567
 294 }