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 ; Test rule : (x & c1) ^ (x & c2) = (x & (c1^c2))
  23 ; Real testing case : (x & 123) ^ y ^ (x & 345) => (x & 435) ^ y
  24 define i32 @xor2(i32 %x, i32 %y) {
  25   %and = and i32 %x, 123
  26   %xor = xor i32 %and, %y
  27   %and1 = and i32 %x, 456
  28   %xor2 = xor i32 %xor, %and1
  29   ret i32 %xor2
  30
  31 ;CHECK-LABEL: @xor2(
  32 ;CHECK: %and.ra = and i32 %x, 435
  33 ;CHECK: %xor2 = xor i32 %and.ra, %y
  34 }
  35
  36 ; Test rule: (x | c1) ^ (x & c2) = (x & c3) ^ c1, where c3 = ~c1 ^ c2
  37 ;  c3 = ~c1 ^ c2
  38 define i32 @xor3(i32 %x, i32 %y) {
  39   %or = or i32 %x, 123
  40   %xor = xor i32 %or, %y
  41   %and = and i32 %x, 456
  42   %xor1 = xor i32 %xor, %and
  43   ret i32 %xor1
  44
  45 ;CHECK-LABEL: @xor3(
  46 ;CHECK: %and.ra = and i32 %x, -436
  47 ;CHECK: %xor = xor i32 %y, 123
  48 ;CHECK: %xor1 = xor i32 %xor, %and.ra
  49 }
  50
  51 ; Test rule: (x | c1) ^ c2 = (x & ~c1) ^ (c1 ^ c2)
  52 define i32 @xor4(i32 %x, i32 %y) {
  53   %and = and i32 %x, -124
  54   %xor = xor i32 %y, 435
  55   %xor1 = xor i32 %xor, %and
  56   ret i32 %xor1
  57 ; CHECK-LABEL: @xor4(
  58 ; CHECK: %and = and i32 %x, -124
  59 ; CHECK: %xor = xor i32 %y, 435
  60 ; CHECK: %xor1 = xor i32 %xor, %and
  61 }
  62
  63 ; ==========================================================================
  64 ;
  65 ;  Xor reassociation special cases
  66 ;
  67 ; ==========================================================================
  68
  69 ; Special case1:
  70 ;  (x | c1) ^ (x & ~c1) = c1
  71 define i32 @xor_special1(i32 %x, i32 %y) {
  72   %or = or i32 %x, 123
  73   %xor = xor i32 %or, %y
  74   %and = and i32 %x, -124
  75   %xor1 = xor i32 %xor, %and
  76   ret i32 %xor1
  77 ; CHECK-LABEL: @xor_special1(
  78 ; CHECK: %xor1 = xor i32 %y, 123
  79 ; CHECK: ret i32 %xor1
  80 }
  81
  82 ; Special case1:
  83 ;  (x | c1) ^ (x & c1) = x ^ c1
  84 define i32 @xor_special2(i32 %x, i32 %y) {
  85   %or = or i32 %x, 123
  86   %xor = xor i32 %or, %y
  87   %and = and i32 %x, 123
  88   %xor1 = xor i32 %xor, %and
  89   ret i32 %xor1
  90 ; CHECK-LABEL: @xor_special2(
  91 ; CHECK: %xor = xor i32 %y, 123
  92 ; CHECK: %xor1 = xor i32 %xor, %x
  93 ; CHECK: ret i32 %xor1
  94 }
  95
  96 ; (x | c1) ^ (x | c1) => 0
  97 define i32 @xor_special3(i32 %x) {
  98   %or = or i32 %x, 123
  99   %or1 = or i32 %x, 123
 100   %xor = xor i32 %or, %or1
 101   ret i32 %xor
 102 ;CHECK-LABEL: @xor_special3(
 103 ;CHECK: ret i32 0
 104 }
 105
 106 ; (x & c1) ^ (x & c1) => 0
 107 define i32 @xor_special4(i32 %x) {
 108   %or = and i32 %x, 123
 109   %or1 = and i32 123, %x
 110   %xor = xor i32 %or, %or1
 111   ret i32 %xor
 112 ;CHECK-LABEL: @xor_special4(
 113 ;CHECK: ret i32 0
 114 }
 115
 116 ; ==========================================================================
 117 ;
 118 ;  Xor reassociation curtail code size
 119 ;
 120 ; ==========================================================================
 121
 122 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3
 123 ; is enabled if one of operands has multiple uses
 124 ;
 125 define i32 @xor_ra_size1(i32 %x) {
 126   %or = or i32 %x, 123
 127   %or1 = or i32 %x, 456
 128   %xor = xor i32 %or, %or1
 129
 130   %add = add i32 %xor, %or
 131   ret i32 %add
 132 ;CHECK-LABEL: @xor_ra_size1(
 133 ;CHECK: %xor = xor i32 %and.ra, 435
 134 }
 135
 136 ; (x | c1) ^ (x | c2) => (x & c3) ^ c3
 137 ; is disenabled if bothf operands has multiple uses.
 138 ;
 139 define i32 @xor_ra_size2(i32 %x) {
 140   %or = or i32 %x, 123
 141   %or1 = or i32 %x, 456
 142   %xor = xor i32 %or, %or1
 143
 144   %add = add i32 %xor, %or
 145   %add2 = add i32 %add, %or1
 146   ret i32 %add2
 147
 148 ;CHECK-LABEL: @xor_ra_size2(
 149 ;CHECK: %or1 = or i32 %x, 456
 150 ;CHECK: %xor = xor i32 %or, %or1
 151 }
 152
 153
 154 ; ==========================================================================
 155 ;
 156 ;  Xor reassociation bugs
 157 ;
 158 ; ==========================================================================
 159
 160 @xor_bug1_data = external global <{}>, align 4
 161 define void @xor_bug1() {
 162   %1 = ptrtoint i32* undef to i64
 163   %2 = xor i64 %1, ptrtoint (<{}>* @xor_bug1_data to i64)
 164   %3 = and i64 undef, %2
 165   ret void
 166 }
 167
 168 ; The bug was that when the compiler optimize "(x | c1)" ^ "(x & c2)", it may
 169 ; swap the two xor-subexpressions if they are not in canoninical order; however,
 170 ; when optimizer swaps two sub-expressions, if forgot to swap the cached value
 171 ; of c1 and c2 accordingly, hence cause the problem.
 172 ;
 173 define i32 @xor_bug2(i32, i32, i32, i32) {
 174   %5 = mul i32 %0, 123
 175   %6 = add i32 %2, 24
 176   %7 = add i32 %1, 8
 177   %8 = and i32 %1, 3456789
 178   %9 = or i32 %8,  4567890
 179   %10 = and i32 %1, 543210987
 180   %11 = or i32 %1, 891034567
 181   %12 = and i32 %2, 255
 182   %13 = xor i32 %9, %10
 183   %14 = xor i32 %11, %13
 184   %15 = xor i32 %5, %14
 185   %16 = and i32 %3, 255
 186   %17 = xor i32 %16, 42
 187   %18 = add i32 %6, %7
 188   %19 = add i32 %18, %12
 189   %20 = add i32 %19, %15
 190   ret i32 %20
 191 ;CHECK-LABEL: @xor_bug2(
 192 ;CHECK: xor i32 %5, 891034567
 193 }