test/Transforms/Reassociate/xor_reassoc.ll

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