1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=div-rem-pairs -S -mtriple=mips-unknown-unknown | FileCheck %s 3 4declare void @foo(i32, i32) 5 6define void @decompose_illegal_srem_same_block(i32 %a, i32 %b) { 7; CHECK-LABEL: @decompose_illegal_srem_same_block( 8; CHECK-NEXT: [[REM:%.*]] = srem i32 [[A:%.*]], [[B:%.*]] 9; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[A]], [[B]] 10; CHECK-NEXT: call void @foo(i32 [[REM]], i32 [[DIV]]) 11; CHECK-NEXT: ret void 12; 13 %rem = srem i32 %a, %b 14 %div = sdiv i32 %a, %b 15 call void @foo(i32 %rem, i32 %div) 16 ret void 17} 18 19define void @decompose_illegal_urem_same_block(i32 %a, i32 %b) { 20; CHECK-LABEL: @decompose_illegal_urem_same_block( 21; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[A:%.*]], [[B:%.*]] 22; CHECK-NEXT: [[REM:%.*]] = urem i32 [[A]], [[B]] 23; CHECK-NEXT: call void @foo(i32 [[REM]], i32 [[DIV]]) 24; CHECK-NEXT: ret void 25; 26 %div = udiv i32 %a, %b 27 %rem = urem i32 %a, %b 28 call void @foo(i32 %rem, i32 %div) 29 ret void 30} 31 32; Hoist and optionally decompose the sdiv because it's safe and free. 33; PR31028 - https://bugs.llvm.org/show_bug.cgi?id=31028 34 35define i32 @hoist_sdiv(i32 %a, i32 %b) { 36; CHECK-LABEL: @hoist_sdiv( 37; CHECK-NEXT: entry: 38; CHECK-NEXT: [[REM:%.*]] = srem i32 [[A:%.*]], [[B:%.*]] 39; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[A]], [[B]] 40; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 41; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]] 42; CHECK: if: 43; CHECK-NEXT: br label [[END]] 44; CHECK: end: 45; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[DIV]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] 46; CHECK-NEXT: ret i32 [[RET]] 47; 48entry: 49 %rem = srem i32 %a, %b 50 %cmp = icmp eq i32 %rem, 42 51 br i1 %cmp, label %if, label %end 52 53if: 54 %div = sdiv i32 %a, %b 55 br label %end 56 57end: 58 %ret = phi i32 [ %div, %if ], [ 3, %entry ] 59 ret i32 %ret 60} 61 62; Hoist and optionally decompose the udiv because it's safe and free. 63 64define i64 @hoist_udiv(i64 %a, i64 %b) { 65; CHECK-LABEL: @hoist_udiv( 66; CHECK-NEXT: entry: 67; CHECK-NEXT: [[A_FROZEN:%.*]] = freeze i64 [[A:%.*]] 68; CHECK-NEXT: [[B_FROZEN:%.*]] = freeze i64 [[B:%.*]] 69; CHECK-NEXT: [[DIV:%.*]] = udiv i64 [[A_FROZEN]], [[B_FROZEN]] 70; CHECK-NEXT: [[TMP0:%.*]] = mul i64 [[DIV]], [[B_FROZEN]] 71; CHECK-NEXT: [[REM_DECOMPOSED:%.*]] = sub i64 [[A_FROZEN]], [[TMP0]] 72; CHECK-NEXT: [[CMP:%.*]] = icmp eq i64 [[REM_DECOMPOSED]], 42 73; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]] 74; CHECK: if: 75; CHECK-NEXT: br label [[END]] 76; CHECK: end: 77; CHECK-NEXT: [[RET:%.*]] = phi i64 [ [[DIV]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] 78; CHECK-NEXT: ret i64 [[RET]] 79; 80entry: 81 %rem = urem i64 %a, %b 82 %cmp = icmp eq i64 %rem, 42 83 br i1 %cmp, label %if, label %end 84 85if: 86 %div = udiv i64 %a, %b 87 br label %end 88 89end: 90 %ret = phi i64 [ %div, %if ], [ 3, %entry ] 91 ret i64 %ret 92} 93 94; Hoist the srem if it's safe and free, otherwise decompose it. 95 96define i16 @hoist_srem(i16 %a, i16 %b) { 97; CHECK-LABEL: @hoist_srem( 98; CHECK-NEXT: entry: 99; CHECK-NEXT: [[A_FROZEN:%.*]] = freeze i16 [[A:%.*]] 100; CHECK-NEXT: [[B_FROZEN:%.*]] = freeze i16 [[B:%.*]] 101; CHECK-NEXT: [[DIV:%.*]] = sdiv i16 [[A_FROZEN]], [[B_FROZEN]] 102; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[DIV]], 42 103; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]] 104; CHECK: if: 105; CHECK-NEXT: [[TMP0:%.*]] = mul i16 [[DIV]], [[B_FROZEN]] 106; CHECK-NEXT: [[REM_DECOMPOSED:%.*]] = sub i16 [[A_FROZEN]], [[TMP0]] 107; CHECK-NEXT: br label [[END]] 108; CHECK: end: 109; CHECK-NEXT: [[RET:%.*]] = phi i16 [ [[REM_DECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] 110; CHECK-NEXT: ret i16 [[RET]] 111; 112entry: 113 %div = sdiv i16 %a, %b 114 %cmp = icmp eq i16 %div, 42 115 br i1 %cmp, label %if, label %end 116 117if: 118 %rem = srem i16 %a, %b 119 br label %end 120 121end: 122 %ret = phi i16 [ %rem, %if ], [ 3, %entry ] 123 ret i16 %ret 124} 125 126; Hoist the urem if it's safe and free, otherwise decompose it. 127 128define i8 @hoist_urem(i8 %a, i8 %b) { 129; CHECK-LABEL: @hoist_urem( 130; CHECK-NEXT: entry: 131; CHECK-NEXT: [[A_FROZEN:%.*]] = freeze i8 [[A:%.*]] 132; CHECK-NEXT: [[B_FROZEN:%.*]] = freeze i8 [[B:%.*]] 133; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[A_FROZEN]], [[B_FROZEN]] 134; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[DIV]], 42 135; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]] 136; CHECK: if: 137; CHECK-NEXT: [[TMP0:%.*]] = mul i8 [[DIV]], [[B_FROZEN]] 138; CHECK-NEXT: [[REM_DECOMPOSED:%.*]] = sub i8 [[A_FROZEN]], [[TMP0]] 139; CHECK-NEXT: br label [[END]] 140; CHECK: end: 141; CHECK-NEXT: [[RET:%.*]] = phi i8 [ [[REM_DECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] 142; CHECK-NEXT: ret i8 [[RET]] 143; 144entry: 145 %div = udiv i8 %a, %b 146 %cmp = icmp eq i8 %div, 42 147 br i1 %cmp, label %if, label %end 148 149if: 150 %rem = urem i8 %a, %b 151 br label %end 152 153end: 154 %ret = phi i8 [ %rem, %if ], [ 3, %entry ] 155 ret i8 %ret 156} 157 158; Be careful with RAUW/invalidation if this is a srem-of-srem. 159 160define i32 @srem_of_srem_unexpanded(i32 %X, i32 %Y, i32 %Z) { 161; CHECK-LABEL: @srem_of_srem_unexpanded( 162; CHECK-NEXT: [[T0:%.*]] = mul nsw i32 [[Z:%.*]], [[Y:%.*]] 163; CHECK-NEXT: [[T1:%.*]] = sdiv i32 [[X:%.*]], [[T0]] 164; CHECK-NEXT: [[T2:%.*]] = mul nsw i32 [[T0]], [[T1]] 165; CHECK-NEXT: [[T3:%.*]] = srem i32 [[X]], [[T0]] 166; CHECK-NEXT: [[T4:%.*]] = sdiv i32 [[T3]], [[Y]] 167; CHECK-NEXT: [[T5:%.*]] = mul nsw i32 [[T4]], [[Y]] 168; CHECK-NEXT: [[T6:%.*]] = srem i32 [[T3]], [[Y]] 169; CHECK-NEXT: ret i32 [[T6]] 170; 171 %t0 = mul nsw i32 %Z, %Y 172 %t1 = sdiv i32 %X, %t0 173 %t2 = mul nsw i32 %t0, %t1 174 %t3 = srem i32 %X, %t0 175 %t4 = sdiv i32 %t3, %Y 176 %t5 = mul nsw i32 %t4, %Y 177 %t6 = srem i32 %t3, %Y 178 ret i32 %t6 179} 180define i32 @srem_of_srem_expanded(i32 %X, i32 %Y, i32 %Z) { 181; CHECK-LABEL: @srem_of_srem_expanded( 182; CHECK-NEXT: [[T0:%.*]] = mul nsw i32 [[Z:%.*]], [[Y:%.*]] 183; CHECK-NEXT: [[T1:%.*]] = sdiv i32 [[X:%.*]], [[T0]] 184; CHECK-NEXT: [[T2:%.*]] = mul nsw i32 [[T0]], [[T1]] 185; CHECK-NEXT: [[T3_RECOMPOSED:%.*]] = srem i32 [[X]], [[T0]] 186; CHECK-NEXT: [[T4:%.*]] = sdiv i32 [[T3_RECOMPOSED]], [[Y]] 187; CHECK-NEXT: [[T5:%.*]] = mul nsw i32 [[T4]], [[Y]] 188; CHECK-NEXT: [[T6_RECOMPOSED:%.*]] = srem i32 [[T3_RECOMPOSED]], [[Y]] 189; CHECK-NEXT: ret i32 [[T6_RECOMPOSED]] 190; 191 %t0 = mul nsw i32 %Z, %Y 192 %t1 = sdiv i32 %X, %t0 193 %t2 = mul nsw i32 %t0, %t1 194 %t3 = sub nsw i32 %X, %t2 195 %t4 = sdiv i32 %t3, %Y 196 %t5 = mul nsw i32 %t4, %Y 197 %t6 = sub nsw i32 %t3, %t5 198 ret i32 %t6 199} 200 201; If the ops don't match, don't do anything: signedness. 202 203define i32 @dont_hoist_udiv(i32 %a, i32 %b) { 204; CHECK-LABEL: @dont_hoist_udiv( 205; CHECK-NEXT: entry: 206; CHECK-NEXT: [[REM:%.*]] = srem i32 [[A:%.*]], [[B:%.*]] 207; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 208; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]] 209; CHECK: if: 210; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[A]], [[B]] 211; CHECK-NEXT: br label [[END]] 212; CHECK: end: 213; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[DIV]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] 214; CHECK-NEXT: ret i32 [[RET]] 215; 216entry: 217 %rem = srem i32 %a, %b 218 %cmp = icmp eq i32 %rem, 42 219 br i1 %cmp, label %if, label %end 220 221if: 222 %div = udiv i32 %a, %b 223 br label %end 224 225end: 226 %ret = phi i32 [ %div, %if ], [ 3, %entry ] 227 ret i32 %ret 228} 229 230; If the ops don't match, don't do anything: operation. 231 232define i32 @dont_hoist_srem(i32 %a, i32 %b) { 233; CHECK-LABEL: @dont_hoist_srem( 234; CHECK-NEXT: entry: 235; CHECK-NEXT: [[REM:%.*]] = urem i32 [[A:%.*]], [[B:%.*]] 236; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 237; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]] 238; CHECK: if: 239; CHECK-NEXT: [[REM2:%.*]] = srem i32 [[A]], [[B]] 240; CHECK-NEXT: br label [[END]] 241; CHECK: end: 242; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[REM2]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] 243; CHECK-NEXT: ret i32 [[RET]] 244; 245entry: 246 %rem = urem i32 %a, %b 247 %cmp = icmp eq i32 %rem, 42 248 br i1 %cmp, label %if, label %end 249 250if: 251 %rem2 = srem i32 %a, %b 252 br label %end 253 254end: 255 %ret = phi i32 [ %rem2, %if ], [ 3, %entry ] 256 ret i32 %ret 257} 258 259; If the ops don't match, don't do anything: operands. 260 261define i32 @dont_hoist_sdiv(i32 %a, i32 %b, i32 %c) { 262; CHECK-LABEL: @dont_hoist_sdiv( 263; CHECK-NEXT: entry: 264; CHECK-NEXT: [[REM:%.*]] = srem i32 [[A:%.*]], [[B:%.*]] 265; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 266; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]] 267; CHECK: if: 268; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[A]], [[C:%.*]] 269; CHECK-NEXT: br label [[END]] 270; CHECK: end: 271; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[DIV]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] 272; CHECK-NEXT: ret i32 [[RET]] 273; 274entry: 275 %rem = srem i32 %a, %b 276 %cmp = icmp eq i32 %rem, 42 277 br i1 %cmp, label %if, label %end 278 279if: 280 %div = sdiv i32 %a, %c 281 br label %end 282 283end: 284 %ret = phi i32 [ %div, %if ], [ 3, %entry ] 285 ret i32 %ret 286} 287 288; If the target doesn't have a unified div/rem op for the type, decompose rem in-place to mul+sub. 289 290define i128 @dont_hoist_urem(i128 %a, i128 %b) { 291; CHECK-LABEL: @dont_hoist_urem( 292; CHECK-NEXT: entry: 293; CHECK-NEXT: [[A_FROZEN:%.*]] = freeze i128 [[A:%.*]] 294; CHECK-NEXT: [[B_FROZEN:%.*]] = freeze i128 [[B:%.*]] 295; CHECK-NEXT: [[DIV:%.*]] = udiv i128 [[A_FROZEN]], [[B_FROZEN]] 296; CHECK-NEXT: [[CMP:%.*]] = icmp eq i128 [[DIV]], 42 297; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]] 298; CHECK: if: 299; CHECK-NEXT: [[TMP0:%.*]] = mul i128 [[DIV]], [[B_FROZEN]] 300; CHECK-NEXT: [[REM_DECOMPOSED:%.*]] = sub i128 [[A_FROZEN]], [[TMP0]] 301; CHECK-NEXT: br label [[END]] 302; CHECK: end: 303; CHECK-NEXT: [[RET:%.*]] = phi i128 [ [[REM_DECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] 304; CHECK-NEXT: ret i128 [[RET]] 305; 306entry: 307 %div = udiv i128 %a, %b 308 %cmp = icmp eq i128 %div, 42 309 br i1 %cmp, label %if, label %end 310 311if: 312 %rem = urem i128 %a, %b 313 br label %end 314 315end: 316 %ret = phi i128 [ %rem, %if ], [ 3, %entry ] 317 ret i128 %ret 318} 319 320; Hoist both ops to the common predecessor block. 321 322define i32 @no_domination(i1 %cmp, i32 %a, i32 %b) { 323; CHECK-LABEL: @no_domination( 324; CHECK-NEXT: entry: 325; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] 326; CHECK-NEXT: [[REM:%.*]] = srem i32 [[A]], [[B]] 327; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF:%.*]], label [[ELSE:%.*]] 328; CHECK: if: 329; CHECK-NEXT: br label [[END:%.*]] 330; CHECK: else: 331; CHECK-NEXT: br label [[END]] 332; CHECK: end: 333; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[DIV]], [[IF]] ], [ [[REM]], [[ELSE]] ] 334; CHECK-NEXT: ret i32 [[RET]] 335; 336entry: 337 br i1 %cmp, label %if, label %else 338 339if: 340 %div = sdiv i32 %a, %b 341 br label %end 342 343else: 344 %rem = srem i32 %a, %b 345 br label %end 346 347end: 348 %ret = phi i32 [ %div, %if ], [ %rem, %else ] 349 ret i32 %ret 350} 351 352