1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -reassociate -S | FileCheck %s 3 4; PR37098 - https://bugs.llvm.org/show_bug.cgi?id=37098 5; In all positive tests, we should reassociate binops 6; to allow more factoring folds. 7 8; There are 5 associative integer binops * 9; 13 integer binops * 10; 4 operand commutes = 11; 260 potential variations of this fold 12; for integer binops. There are another 40 for FP. 13; Mix the commutation options to provide coverage using less tests. 14 15define i8 @and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) { 16; CHECK-LABEL: @and_shl( 17; CHECK-NEXT: [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]] 18; CHECK-NEXT: [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]] 19; CHECK-NEXT: [[A:%.*]] = and i8 [[SX]], [[Z:%.*]] 20; CHECK-NEXT: [[R:%.*]] = and i8 [[A]], [[SY]] 21; CHECK-NEXT: ret i8 [[R]] 22; 23 %sx = shl i8 %x, %shamt 24 %sy = shl i8 %y, %shamt 25 %a = and i8 %sx, %z 26 %r = and i8 %sy, %a 27 ret i8 %r 28} 29 30define i8 @or_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) { 31; CHECK-LABEL: @or_shl( 32; CHECK-NEXT: [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]] 33; CHECK-NEXT: [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]] 34; CHECK-NEXT: [[A:%.*]] = or i8 [[SX]], [[Z:%.*]] 35; CHECK-NEXT: [[R:%.*]] = or i8 [[A]], [[SY]] 36; CHECK-NEXT: ret i8 [[R]] 37; 38 %sx = shl i8 %x, %shamt 39 %sy = shl i8 %y, %shamt 40 %a = or i8 %sx, %z 41 %r = or i8 %a, %sy 42 ret i8 %r 43} 44 45define i8 @xor_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) { 46; CHECK-LABEL: @xor_shl( 47; CHECK-NEXT: [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]] 48; CHECK-NEXT: [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]] 49; CHECK-NEXT: [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]] 50; CHECK-NEXT: [[R:%.*]] = xor i8 [[A]], [[SY]] 51; CHECK-NEXT: ret i8 [[R]] 52; 53 %sx = shl i8 %x, %shamt 54 %sy = shl i8 %y, %shamt 55 %a = xor i8 %z, %sx 56 %r = xor i8 %a, %sy 57 ret i8 %r 58} 59 60define i8 @and_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) { 61; CHECK-LABEL: @and_lshr( 62; CHECK-NEXT: [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]] 63; CHECK-NEXT: [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]] 64; CHECK-NEXT: [[A:%.*]] = and i8 [[SX]], [[Z:%.*]] 65; CHECK-NEXT: [[R:%.*]] = and i8 [[A]], [[SY]] 66; CHECK-NEXT: ret i8 [[R]] 67; 68 %sx = lshr i8 %x, %shamt 69 %sy = lshr i8 %y, %shamt 70 %a = and i8 %z, %sx 71 %r = and i8 %sy, %a 72 ret i8 %r 73} 74 75define i8 @or_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) { 76; CHECK-LABEL: @or_lshr( 77; CHECK-NEXT: [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]] 78; CHECK-NEXT: [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]] 79; CHECK-NEXT: [[A:%.*]] = or i8 [[SX]], [[Z:%.*]] 80; CHECK-NEXT: [[R:%.*]] = or i8 [[A]], [[SY]] 81; CHECK-NEXT: ret i8 [[R]] 82; 83 %sx = lshr i8 %x, %shamt 84 %sy = lshr i8 %y, %shamt 85 %a = or i8 %sx, %z 86 %r = or i8 %sy, %a 87 ret i8 %r 88} 89 90define i8 @xor_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) { 91; CHECK-LABEL: @xor_lshr( 92; CHECK-NEXT: [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]] 93; CHECK-NEXT: [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]] 94; CHECK-NEXT: [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]] 95; CHECK-NEXT: [[R:%.*]] = xor i8 [[A]], [[SY]] 96; CHECK-NEXT: ret i8 [[R]] 97; 98 %sx = lshr i8 %x, %shamt 99 %sy = lshr i8 %y, %shamt 100 %a = xor i8 %sx, %z 101 %r = xor i8 %a, %sy 102 ret i8 %r 103} 104 105define i8 @and_ashr(i8 %x, i8 %y, i8 %z, i8 %shamt) { 106; CHECK-LABEL: @and_ashr( 107; CHECK-NEXT: [[SX:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]] 108; CHECK-NEXT: [[SY:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]] 109; CHECK-NEXT: [[A:%.*]] = and i8 [[SX]], [[Z:%.*]] 110; CHECK-NEXT: [[R:%.*]] = and i8 [[A]], [[SY]] 111; CHECK-NEXT: ret i8 [[R]] 112; 113 %sx = ashr i8 %x, %shamt 114 %sy = ashr i8 %y, %shamt 115 %a = and i8 %z, %sx 116 %r = and i8 %a, %sy 117 ret i8 %r 118} 119 120define i8 @or_ashr(i8 %x, i8 %y, i8 %z, i8 %shamt) { 121; CHECK-LABEL: @or_ashr( 122; CHECK-NEXT: [[SX:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]] 123; CHECK-NEXT: [[SY:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]] 124; CHECK-NEXT: [[A:%.*]] = or i8 [[SX]], [[Z:%.*]] 125; CHECK-NEXT: [[R:%.*]] = or i8 [[A]], [[SY]] 126; CHECK-NEXT: ret i8 [[R]] 127; 128 %sx = ashr i8 %x, %shamt 129 %sy = ashr i8 %y, %shamt 130 %a = or i8 %z, %sx 131 %r = or i8 %sy, %a 132 ret i8 %r 133} 134 135; Vectors work too. 136 137define <2 x i8> @xor_ashr(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z, <2 x i8> %shamt) { 138; CHECK-LABEL: @xor_ashr( 139; CHECK-NEXT: [[SX:%.*]] = ashr <2 x i8> [[X:%.*]], [[SHAMT:%.*]] 140; CHECK-NEXT: [[SY:%.*]] = ashr <2 x i8> [[Y:%.*]], [[SHAMT]] 141; CHECK-NEXT: [[A:%.*]] = xor <2 x i8> [[SX]], [[Z:%.*]] 142; CHECK-NEXT: [[R:%.*]] = xor <2 x i8> [[A]], [[SY]] 143; CHECK-NEXT: ret <2 x i8> [[R]] 144; 145 %sx = ashr <2 x i8> %x, %shamt 146 %sy = ashr <2 x i8> %y, %shamt 147 %a = xor <2 x i8> %sx, %z 148 %r = xor <2 x i8> %a, %sy 149 ret <2 x i8> %r 150} 151 152; Negative test - different logic ops 153 154define i8 @or_and_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) { 155; CHECK-LABEL: @or_and_shl( 156; CHECK-NEXT: [[SX:%.*]] = shl i8 [[X:%.*]], [[SHAMT:%.*]] 157; CHECK-NEXT: [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]] 158; CHECK-NEXT: [[A:%.*]] = or i8 [[SX]], [[Z:%.*]] 159; CHECK-NEXT: [[R:%.*]] = and i8 [[A]], [[SY]] 160; CHECK-NEXT: ret i8 [[R]] 161; 162 %sx = shl i8 %x, %shamt 163 %sy = shl i8 %y, %shamt 164 %a = or i8 %sx, %z 165 %r = and i8 %sy, %a 166 ret i8 %r 167} 168 169; Negative test - different shift ops 170 171define i8 @or_lshr_shl(i8 %x, i8 %y, i8 %z, i8 %shamt) { 172; CHECK-LABEL: @or_lshr_shl( 173; CHECK-NEXT: [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]] 174; CHECK-NEXT: [[SY:%.*]] = shl i8 [[Y:%.*]], [[SHAMT]] 175; CHECK-NEXT: [[A:%.*]] = or i8 [[SX]], [[Z:%.*]] 176; CHECK-NEXT: [[R:%.*]] = or i8 [[A]], [[SY]] 177; CHECK-NEXT: ret i8 [[R]] 178; 179 %sx = lshr i8 %x, %shamt 180 %sy = shl i8 %y, %shamt 181 %a = or i8 %sx, %z 182 %r = or i8 %a, %sy 183 ret i8 %r 184} 185 186; Negative test - multi-use 187 188define i8 @xor_lshr_multiuse(i8 %x, i8 %y, i8 %z, i8 %shamt) { 189; CHECK-LABEL: @xor_lshr_multiuse( 190; CHECK-NEXT: [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]] 191; CHECK-NEXT: [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]] 192; CHECK-NEXT: [[A:%.*]] = xor i8 [[SX]], [[Z:%.*]] 193; CHECK-NEXT: [[R:%.*]] = xor i8 [[A]], [[SY]] 194; CHECK-NEXT: [[R2:%.*]] = sdiv i8 [[A]], [[R]] 195; CHECK-NEXT: ret i8 [[R2]] 196; 197 %sx = lshr i8 %x, %shamt 198 %sy = lshr i8 %y, %shamt 199 %a = xor i8 %sx, %z 200 %r = xor i8 %a, %sy 201 %r2 = sdiv i8 %a, %r 202 ret i8 %r2 203} 204 205; Math ops work too. Change instruction positions too to verify placement. 206 207define i8 @add_lshr(i8 %x, i8 %y, i8 %z, i8 %shamt) { 208; CHECK-LABEL: @add_lshr( 209; CHECK-NEXT: [[SX:%.*]] = lshr i8 [[X:%.*]], [[SHAMT:%.*]] 210; CHECK-NEXT: [[A:%.*]] = add i8 [[SX]], [[Z:%.*]] 211; CHECK-NEXT: [[SY:%.*]] = lshr i8 [[Y:%.*]], [[SHAMT]] 212; CHECK-NEXT: [[R:%.*]] = add i8 [[A]], [[SY]] 213; CHECK-NEXT: ret i8 [[R]] 214; 215 %sx = lshr i8 %x, %shamt 216 %a = add i8 %sx, %z 217 %sy = lshr i8 %y, %shamt 218 %r = add i8 %a, %sy 219 ret i8 %r 220} 221 222; Make sure wrapping flags are cleared. 223 224define i8 @mul_sub(i8 %x, i8 %y, i8 %z, i8 %m) { 225; CHECK-LABEL: @mul_sub( 226; CHECK-NEXT: [[SX:%.*]] = sub i8 [[X:%.*]], [[M:%.*]] 227; CHECK-NEXT: [[SY:%.*]] = sub i8 [[Y:%.*]], [[M]] 228; CHECK-NEXT: [[A:%.*]] = mul nsw i8 [[SX]], [[Z:%.*]] 229; CHECK-NEXT: [[R:%.*]] = mul nuw i8 [[A]], [[SY]] 230; CHECK-NEXT: ret i8 [[R]] 231; 232 %sx = sub i8 %x, %m 233 %sy = sub i8 %y, %m 234 %a = mul nsw i8 %sx, %z 235 %r = mul nuw i8 %a, %sy 236 ret i8 %r 237} 238 239define i8 @add_mul(i8 %x, i8 %y, i8 %z, i8 %m) { 240; CHECK-LABEL: @add_mul( 241; CHECK-NEXT: [[SX:%.*]] = mul nuw i8 [[X:%.*]], 42 242; CHECK-NEXT: [[A:%.*]] = add nuw i8 [[Z:%.*]], [[SX]] 243; CHECK-NEXT: [[SY:%.*]] = mul nsw i8 [[M:%.*]], [[Y:%.*]] 244; CHECK-NEXT: [[R:%.*]] = add nsw i8 [[A]], [[SY]] 245; CHECK-NEXT: ret i8 [[R]] 246; 247 %sx = mul nuw i8 %x, 42 248 %a = add nuw i8 %sx, %z 249 %sy = mul nsw i8 %y, %m 250 %r = add nsw i8 %sy, %a 251 ret i8 %r 252} 253 254; Floating-point works too if it's not strict. 255; TODO: These should not require the full 'fast' FMF. 256 257define float @fadd_fmul(float %x, float %y, float %z, float %m) { 258; CHECK-LABEL: @fadd_fmul( 259; CHECK-NEXT: [[SX:%.*]] = fmul float [[X:%.*]], [[M:%.*]] 260; CHECK-NEXT: [[A:%.*]] = fadd fast float [[SX]], [[Z:%.*]] 261; CHECK-NEXT: [[SY:%.*]] = fmul float [[Y:%.*]], [[M]] 262; CHECK-NEXT: [[R:%.*]] = fadd fast float [[A]], [[SY]] 263; CHECK-NEXT: ret float [[R]] 264; 265 %sx = fmul float %x, %m 266 %a = fadd fast float %sx, %z 267 %sy = fmul float %y, %m 268 %r = fadd fast float %sy, %a 269 ret float %r 270} 271 272define float @fmul_fdiv(float %x, float %y, float %z, float %m) { 273; CHECK-LABEL: @fmul_fdiv( 274; CHECK-NEXT: [[SX:%.*]] = fdiv float [[X:%.*]], [[M:%.*]] 275; CHECK-NEXT: [[SY:%.*]] = fdiv float [[Y:%.*]], 4.200000e+01 276; CHECK-NEXT: [[A:%.*]] = fmul fast float [[SY]], [[Z:%.*]] 277; CHECK-NEXT: [[R:%.*]] = fmul fast float [[A]], [[SX]] 278; CHECK-NEXT: ret float [[R]] 279; 280 %sx = fdiv float %x, %m 281 %sy = fdiv float %y, 42.0 282 %a = fmul fast float %z, %sx 283 %r = fmul fast float %sy, %a 284 ret float %r 285} 286 287; Verify that debug info for modified instructions gets discarded (references become undef). 288 289define i32 @and_shl_dbg(i32 %x, i32 %y, i32 %z, i32 %shamt) { 290; CHECK-LABEL: @and_shl_dbg( 291; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[X:%.*]], metadata !7, metadata !DIExpression()), !dbg !20 292; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[Y:%.*]], metadata !13, metadata !DIExpression()), !dbg !21 293; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[Z:%.*]], metadata !14, metadata !DIExpression()), !dbg !22 294; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[SHAMT:%.*]], metadata !15, metadata !DIExpression()), !dbg !23 295; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[X]], [[SHAMT]], !dbg !24 296; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[SHL]], metadata !16, metadata !DIExpression()), !dbg !25 297; CHECK-NEXT: [[SHL1:%.*]] = shl i32 [[Y]], [[SHAMT]], !dbg !26 298; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[SHL1]], metadata !17, metadata !DIExpression()), !dbg !27 299; CHECK-NEXT: [[AND:%.*]] = and i32 [[SHL]], [[Z]], !dbg !28 300; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[AND]], metadata !18, metadata !DIExpression()), !dbg !29 301; CHECK-NEXT: [[AND2:%.*]] = and i32 [[AND]], [[SHL1]], !dbg !30 302; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[AND2]], metadata !19, metadata !DIExpression()), !dbg !31 303; CHECK-NEXT: ret i32 [[AND2]], !dbg !32 304; 305 call void @llvm.dbg.value(metadata i32 %x, metadata !13, metadata !DIExpression()), !dbg !21 306 call void @llvm.dbg.value(metadata i32 %y, metadata !14, metadata !DIExpression()), !dbg !22 307 call void @llvm.dbg.value(metadata i32 %z, metadata !15, metadata !DIExpression()), !dbg !23 308 call void @llvm.dbg.value(metadata i32 %shamt, metadata !16, metadata !DIExpression()), !dbg !24 309 %shl = shl i32 %x, %shamt, !dbg !25 310 call void @llvm.dbg.value(metadata i32 %shl, metadata !17, metadata !DIExpression()), !dbg !26 311 %shl1 = shl i32 %y, %shamt, !dbg !27 312 call void @llvm.dbg.value(metadata i32 %shl1, metadata !18, metadata !DIExpression()), !dbg !28 313 %and = and i32 %shl, %z, !dbg !29 314 call void @llvm.dbg.value(metadata i32 %and, metadata !19, metadata !DIExpression()), !dbg !30 315 %and2 = and i32 %and, %shl1, !dbg !31 316 call void @llvm.dbg.value(metadata i32 %and2, metadata !20, metadata !DIExpression()), !dbg !32 317 ret i32 %and2, !dbg !33 318} 319 320declare void @llvm.dbg.value(metadata, metadata, metadata) 321 322!llvm.dbg.cu = !{!0} 323!llvm.module.flags = !{!3, !4, !5, !6} 324 325!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 7.0.0 (trunk 331069)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2) 326!1 = !DIFile(filename: "ass.c", directory: "/Users/spatel/myllvm/release/bin") 327!2 = !{} 328!3 = !{i32 2, !"Dwarf Version", i32 4} 329!4 = !{i32 2, !"Debug Info Version", i32 3} 330!5 = !{i32 1, !"wchar_size", i32 4} 331!6 = !{i32 7, !"PIC Level", i32 2} 332!7 = !{!"clang version 7.0.0 (trunk 331069)"} 333!8 = distinct !DISubprogram(name: "and_shl_dbg", scope: !1, file: !1, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !12) 334!9 = !DISubroutineType(types: !10) 335!10 = !{!11, !11, !11, !11, !11} 336!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) 337!12 = !{!13, !14, !15, !16, !17, !18, !19, !20} 338!13 = !DILocalVariable(name: "x", arg: 1, scope: !8, file: !1, line: 1, type: !11) 339!14 = !DILocalVariable(name: "y", arg: 2, scope: !8, file: !1, line: 1, type: !11) 340!15 = !DILocalVariable(name: "z", arg: 3, scope: !8, file: !1, line: 1, type: !11) 341!16 = !DILocalVariable(name: "shamt", arg: 4, scope: !8, file: !1, line: 1, type: !11) 342!17 = !DILocalVariable(name: "sx", scope: !8, file: !1, line: 2, type: !11) 343!18 = !DILocalVariable(name: "sy", scope: !8, file: !1, line: 3, type: !11) 344!19 = !DILocalVariable(name: "a", scope: !8, file: !1, line: 4, type: !11) 345!20 = !DILocalVariable(name: "r", scope: !8, file: !1, line: 5, type: !11) 346!21 = !DILocation(line: 1, column: 21, scope: !8) 347!22 = !DILocation(line: 1, column: 28, scope: !8) 348!23 = !DILocation(line: 1, column: 35, scope: !8) 349!24 = !DILocation(line: 1, column: 42, scope: !8) 350!25 = !DILocation(line: 2, column: 14, scope: !8) 351!26 = !DILocation(line: 2, column: 7, scope: !8) 352!27 = !DILocation(line: 3, column: 14, scope: !8) 353!28 = !DILocation(line: 3, column: 7, scope: !8) 354!29 = !DILocation(line: 4, column: 14, scope: !8) 355!30 = !DILocation(line: 4, column: 7, scope: !8) 356!31 = !DILocation(line: 5, column: 14, scope: !8) 357!32 = !DILocation(line: 5, column: 7, scope: !8) 358!33 = !DILocation(line: 6, column: 3, scope: !8) 359 360