Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -1900,6 +1900,35 @@ return nullptr; } +/// Allow hoisting into the specified block for division/remainder for matching +/// siblings such as sdiv X, Y and srem X, Y. This bypasses normal safety and +/// cost checks because: +/// (1) The hoisted op is guaranteed safe to execute because any potential +/// faulting/UB caused by that op must already occur in the predecessor +/// block from the sibling. +/// (2) The true cost of the speculated div/rem will either be: +/// (a) free for a target with unified div/rem instructions. +/// (b) free when speculating a division because we are already calculating +/// the remainder (remainder requires calculating the quotient). +/// (c) low when speculating a remainder because we are already calculating +/// the division (the cost of the division dominates multiply + sub). +static bool allowSpeculationForDivRem(Instruction &I, BasicBlock &PredBB) { + unsigned SiblingOpcode; + switch (I.getOpcode()) { + case Instruction::SDiv: SiblingOpcode = Instruction::SRem; break; + case Instruction::UDiv: SiblingOpcode = Instruction::URem; break; + case Instruction::SRem: SiblingOpcode = Instruction::SDiv; break; + case Instruction::URem: SiblingOpcode = Instruction::UDiv; break; + default: return false; + } + + return any_of(PredBB, [&](Instruction &PredI) { + return PredI.getOpcode() == SiblingOpcode && + PredI.getOperand(0) == I.getOperand(0) && + PredI.getOperand(1) == I.getOperand(1); + }); +} + /// \brief Speculate a conditional basic block flattening the CFG. /// /// Note that this is a very risky transform currently. Speculating @@ -1980,15 +2009,17 @@ if (SpeculationCost > 1) return false; - // Don't hoist the instruction if it's unsafe or expensive. - if (!isSafeToSpeculativelyExecute(I) && - !(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore( - I, BB, ThenBB, EndBB)))) - return false; - if (!SpeculatedStoreValue && - ComputeSpeculationCost(I, TTI) > - PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic) - return false; + if (!allowSpeculationForDivRem(*I, *BB)) { + // Don't hoist the instruction if it's unsafe or expensive. + if (!isSafeToSpeculativelyExecute(I) && + !(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore( + I, BB, ThenBB, EndBB)))) + return false; + if (!SpeculatedStoreValue && + ComputeSpeculationCost(I, TTI) > + PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic) + return false; + } // Store the store speculation candidate. if (SpeculatedStoreValue) Index: test/Transforms/SimplifyCFG/div-rem-pairs.ll =================================================================== --- test/Transforms/SimplifyCFG/div-rem-pairs.ll +++ test/Transforms/SimplifyCFG/div-rem-pairs.ll @@ -1,6 +1,6 @@ ; RUN: opt -simplifycfg -S < %s | FileCheck %s -; FIXME: Hoist the sdiv because it's safe and free. +; Hoist the sdiv because it's safe and free. ; PR31028 - https://bugs.llvm.org/show_bug.cgi?id=31028 define i32 @hoist_sdiv(i32 %a, i32 %b) { @@ -8,13 +8,9 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[REM:%.*]] = srem i32 %a, %b ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 -; CHECK-NEXT: br i1 [[CMP]], label %if, label %end -; CHECK: if: ; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 %a, %b -; CHECK-NEXT: br label %end -; CHECK: end: -; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[DIV]], %if ], [ 3, %entry ] -; CHECK-NEXT: ret i32 [[RET]] +; CHECK-NEXT: [[DIV_:%.*]] = select i1 [[CMP]], i32 [[DIV]], i32 3 +; CHECK-NEXT: ret i32 [[DIV_]] ; entry: %rem = srem i32 %a, %b @@ -30,20 +26,16 @@ ret i32 %ret } -; FIXME: Hoist the udiv because it's safe and free. +; Hoist the udiv because it's safe and free. define i64 @hoist_udiv(i64 %a, i64 %b) { ; CHECK-LABEL: @hoist_udiv( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[REM:%.*]] = urem i64 %a, %b ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i64 [[REM]], 42 -; CHECK-NEXT: br i1 [[CMP]], label %if, label %end -; CHECK: if: ; CHECK-NEXT: [[DIV:%.*]] = udiv i64 %a, %b -; CHECK-NEXT: br label %end -; CHECK: end: -; CHECK-NEXT: [[RET:%.*]] = phi i64 [ [[DIV]], %if ], [ 3, %entry ] -; CHECK-NEXT: ret i64 [[RET]] +; CHECK-NEXT: [[DIV_:%.*]] = select i1 [[CMP]], i64 [[DIV]], i64 3 +; CHECK-NEXT: ret i64 [[DIV_]] ; entry: %rem = urem i64 %a, %b @@ -59,20 +51,16 @@ ret i64 %ret } -; FIXME: Hoist the srem because it's safe and likely free. +; Hoist the srem because it's safe and likely free. define i16 @hoist_srem(i16 %a, i16 %b) { ; CHECK-LABEL: @hoist_srem( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[DIV:%.*]] = sdiv i16 %a, %b ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[DIV]], 42 -; CHECK-NEXT: br i1 [[CMP]], label %if, label %end -; CHECK: if: ; CHECK-NEXT: [[REM:%.*]] = srem i16 %a, %b -; CHECK-NEXT: br label %end -; CHECK: end: -; CHECK-NEXT: [[RET:%.*]] = phi i16 [ [[REM]], %if ], [ 3, %entry ] -; CHECK-NEXT: ret i16 [[RET]] +; CHECK-NEXT: [[REM_:%.*]] = select i1 [[CMP]], i16 [[REM]], i16 3 +; CHECK-NEXT: ret i16 [[REM_]] ; entry: %div = sdiv i16 %a, %b @@ -88,20 +76,16 @@ ret i16 %ret } -; FIXME: Hoist the urem because it's safe and likely free. +; Hoist the urem because it's safe and likely free. define i8 @hoist_urem(i8 %a, i8 %b) { ; CHECK-LABEL: @hoist_urem( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[DIV:%.*]] = udiv i8 %a, %b ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[DIV]], 42 -; CHECK-NEXT: br i1 [[CMP]], label %if, label %end -; CHECK: if: ; CHECK-NEXT: [[REM:%.*]] = urem i8 %a, %b -; CHECK-NEXT: br label %end -; CHECK: end: -; CHECK-NEXT: [[RET:%.*]] = phi i8 [ [[REM]], %if ], [ 3, %entry ] -; CHECK-NEXT: ret i8 [[RET]] +; CHECK-NEXT: [[REM_:%.*]] = select i1 [[CMP]], i8 [[REM]], i8 3 +; CHECK-NEXT: ret i8 [[REM_]] ; entry: %div = udiv i8 %a, %b @@ -117,3 +101,90 @@ ret i8 %ret } +; If the ops don't match, don't do anything: signedness. + +define i32 @dont_hoist_urem(i32 %a, i32 %b) { +; CHECK-LABEL: @dont_hoist_urem( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[DIV]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: [[REM:%.*]] = urem i32 %a, %b +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[REM]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i32 [[RET]] +; +entry: + %div = sdiv i32 %a, %b + %cmp = icmp eq i32 %div, 42 + br i1 %cmp, label %if, label %end + +if: + %rem = urem i32 %a, %b + br label %end + +end: + %ret = phi i32 [ %rem, %if ], [ 3, %entry ] + ret i32 %ret +} + +; If the ops don't match, don't do anything: operation. + +define i32 @dont_hoist_srem(i32 %a, i32 %b) { +; CHECK-LABEL: @dont_hoist_srem( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[REM:%.*]] = urem i32 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: [[REM2:%.*]] = srem i32 %a, %b +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[REM2]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i32 [[RET]] +; +entry: + %rem = urem i32 %a, %b + %cmp = icmp eq i32 %rem, 42 + br i1 %cmp, label %if, label %end + +if: + %rem2 = srem i32 %a, %b + br label %end + +end: + %ret = phi i32 [ %rem2, %if ], [ 3, %entry ] + ret i32 %ret +} + +; If the ops don't match, don't do anything: operands. + +define i32 @dont_hoist_sdiv(i32 %a, i32 %b, i32 %c) { +; CHECK-LABEL: @dont_hoist_sdiv( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[REM:%.*]] = srem i32 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 %a, %c +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[DIV]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i32 [[RET]] +; +entry: + %rem = srem i32 %a, %b + %cmp = icmp eq i32 %rem, 42 + br i1 %cmp, label %if, label %end + +if: + %div = sdiv i32 %a, %c + br label %end + +end: + %ret = phi i32 [ %div, %if ], [ 3, %entry ] + ret i32 %ret +} +