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; 12define 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; 26define <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 40define 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 55define <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 70define 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 86define <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) 101define 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) 115define <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 136define 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 150define <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 164define 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 179define <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 193define 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 204define <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 215define 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 226define <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; 245define 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; 264define 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 291define 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; 308define 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} 343