434 lines · cpp
1//===- DivRemPairs.cpp - Hoist/[dr]ecompose division and remainder --------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass hoists and/or decomposes/recomposes integer division and remainder10// instructions to enable CFG improvements and better codegen.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Transforms/Scalar/DivRemPairs.h"15#include "llvm/ADT/DenseMap.h"16#include "llvm/ADT/MapVector.h"17#include "llvm/ADT/Statistic.h"18#include "llvm/Analysis/GlobalsModRef.h"19#include "llvm/Analysis/TargetTransformInfo.h"20#include "llvm/Analysis/ValueTracking.h"21#include "llvm/IR/Dominators.h"22#include "llvm/IR/Function.h"23#include "llvm/IR/PatternMatch.h"24#include "llvm/Support/DebugCounter.h"25#include "llvm/Transforms/Utils/BypassSlowDivision.h"26#include <optional>27 28using namespace llvm;29using namespace llvm::PatternMatch;30 31#define DEBUG_TYPE "div-rem-pairs"32STATISTIC(NumPairs, "Number of div/rem pairs");33STATISTIC(NumRecomposed, "Number of instructions recomposed");34STATISTIC(NumHoisted, "Number of instructions hoisted");35STATISTIC(NumDecomposed, "Number of instructions decomposed");36DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",37 "Controls transformations in div-rem-pairs pass");38 39namespace {40struct ExpandedMatch {41 DivRemMapKey Key;42 Instruction *Value;43};44} // namespace45 46/// See if we can match: (which is the form we expand into)47/// X - ((X ?/ Y) * Y)48/// which is equivalent to:49/// X ?% Y50static std::optional<ExpandedMatch> matchExpandedRem(Instruction &I) {51 Value *Dividend, *XroundedDownToMultipleOfY;52 if (!match(&I, m_Sub(m_Value(Dividend), m_Value(XroundedDownToMultipleOfY))))53 return std::nullopt;54 55 Value *Divisor;56 Instruction *Div;57 // Look for ((X / Y) * Y)58 if (!match(59 XroundedDownToMultipleOfY,60 m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(Dividend), m_Value(Divisor)),61 m_Instruction(Div)),62 m_Deferred(Divisor))))63 return std::nullopt;64 65 ExpandedMatch M;66 M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv;67 M.Key.Dividend = Dividend;68 M.Key.Divisor = Divisor;69 M.Value = &I;70 return M;71}72 73namespace {74/// A thin wrapper to store two values that we matched as div-rem pair.75/// We want this extra indirection to avoid dealing with RAUW'ing the map keys.76struct DivRemPairWorklistEntry {77 /// The actual udiv/sdiv instruction. Source of truth.78 AssertingVH<Instruction> DivInst;79 80 /// The instruction that we have matched as a remainder instruction.81 /// Should only be used as Value, don't introspect it.82 AssertingVH<Instruction> RemInst;83 84 DivRemPairWorklistEntry(Instruction *DivInst_, Instruction *RemInst_)85 : DivInst(DivInst_), RemInst(RemInst_) {86 assert((DivInst->getOpcode() == Instruction::UDiv ||87 DivInst->getOpcode() == Instruction::SDiv) &&88 "Not a division.");89 assert(DivInst->getType() == RemInst->getType() && "Types should match.");90 // We can't check anything else about remainder instruction,91 // it's not strictly required to be a urem/srem.92 }93 94 /// The type for this pair, identical for both the div and rem.95 Type *getType() const { return DivInst->getType(); }96 97 /// Is this pair signed or unsigned?98 bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }99 100 /// In this pair, what are the divident and divisor?101 Value *getDividend() const { return DivInst->getOperand(0); }102 Value *getDivisor() const { return DivInst->getOperand(1); }103 104 bool isRemExpanded() const {105 switch (RemInst->getOpcode()) {106 case Instruction::SRem:107 case Instruction::URem:108 return false; // single 'rem' instruction - unexpanded form.109 default:110 return true; // anything else means we have remainder in expanded form.111 }112 }113};114} // namespace115using DivRemWorklistTy = SmallVector<DivRemPairWorklistEntry, 4>;116 117/// Find matching pairs of integer div/rem ops (they have the same numerator,118/// denominator, and signedness). Place those pairs into a worklist for further119/// processing. This indirection is needed because we have to use TrackingVH<>120/// because we will be doing RAUW, and if one of the rem instructions we change121/// happens to be an input to another div/rem in the maps, we'd have problems.122static DivRemWorklistTy getWorklist(Function &F) {123 // Insert all divide and remainder instructions into maps keyed by their124 // operands and opcode (signed or unsigned).125 DenseMap<DivRemMapKey, Instruction *> DivMap;126 // Use a MapVector for RemMap so that instructions are moved/inserted in a127 // deterministic order.128 MapVector<DivRemMapKey, Instruction *> RemMap;129 for (auto &BB : F) {130 for (auto &I : BB) {131 if (I.getOpcode() == Instruction::SDiv)132 DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;133 else if (I.getOpcode() == Instruction::UDiv)134 DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;135 else if (I.getOpcode() == Instruction::SRem)136 RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;137 else if (I.getOpcode() == Instruction::URem)138 RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;139 else if (auto Match = matchExpandedRem(I))140 RemMap[Match->Key] = Match->Value;141 }142 }143 144 // We'll accumulate the matching pairs of div-rem instructions here.145 DivRemWorklistTy Worklist;146 147 // We can iterate over either map because we are only looking for matched148 // pairs. Choose remainders for efficiency because they are usually even more149 // rare than division.150 for (auto &RemPair : RemMap) {151 // Find the matching division instruction from the division map.152 auto It = DivMap.find(RemPair.first);153 if (It == DivMap.end())154 continue;155 156 // We have a matching pair of div/rem instructions.157 NumPairs++;158 Instruction *RemInst = RemPair.second;159 160 // Place it in the worklist.161 Worklist.emplace_back(It->second, RemInst);162 }163 164 return Worklist;165}166 167/// Find matching pairs of integer div/rem ops (they have the same numerator,168/// denominator, and signedness). If they exist in different basic blocks, bring169/// them together by hoisting or replace the common division operation that is170/// implicit in the remainder:171/// X % Y <--> X - ((X / Y) * Y).172///173/// We can largely ignore the normal safety and cost constraints on speculation174/// of these ops when we find a matching pair. This is because we are already175/// guaranteed that any exceptions and most cost are already incurred by the176/// first member of the pair.177///178/// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or179/// SimplifyCFG, but it's split off on its own because it's different enough180/// that it doesn't quite match the stated objectives of those passes.181static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI,182 const DominatorTree &DT) {183 bool Changed = false;184 185 // Get the matching pairs of div-rem instructions. We want this extra186 // indirection to avoid dealing with having to RAUW the keys of the maps.187 DivRemWorklistTy Worklist = getWorklist(F);188 189 // Process each entry in the worklist.190 for (DivRemPairWorklistEntry &E : Worklist) {191 if (!DebugCounter::shouldExecute(DRPCounter))192 continue;193 194 bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned());195 196 auto &DivInst = E.DivInst;197 auto &RemInst = E.RemInst;198 199 const bool RemOriginallyWasInExpandedForm = E.isRemExpanded();200 (void)RemOriginallyWasInExpandedForm; // suppress unused variable warning201 202 if (HasDivRemOp && E.isRemExpanded()) {203 // The target supports div+rem but the rem is expanded.204 // We should recompose it first.205 Value *X = E.getDividend();206 Value *Y = E.getDivisor();207 Instruction *RealRem = E.isSigned() ? BinaryOperator::CreateSRem(X, Y)208 : BinaryOperator::CreateURem(X, Y);209 // Note that we place it right next to the original expanded instruction,210 // and letting further handling to move it if needed.211 RealRem->setName(RemInst->getName() + ".recomposed");212 RealRem->insertAfter(RemInst->getIterator());213 Instruction *OrigRemInst = RemInst;214 // Update AssertingVH<> with new instruction so it doesn't assert.215 RemInst = RealRem;216 // And replace the original instruction with the new one.217 OrigRemInst->replaceAllUsesWith(RealRem);218 RealRem->setDebugLoc(OrigRemInst->getDebugLoc());219 OrigRemInst->eraseFromParent();220 NumRecomposed++;221 // Note that we have left ((X / Y) * Y) around.222 // If it had other uses we could rewrite it as X - X % Y223 Changed = true;224 }225 226 assert((!E.isRemExpanded() || !HasDivRemOp) &&227 "*If* the target supports div-rem, then by now the RemInst *is* "228 "Instruction::[US]Rem.");229 230 // If the target supports div+rem and the instructions are in the same block231 // already, there's nothing to do. The backend should handle this. If the232 // target does not support div+rem, then we will decompose the rem.233 if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())234 continue;235 236 bool DivDominates = DT.dominates(DivInst, RemInst);237 if (!DivDominates && !DT.dominates(RemInst, DivInst)) {238 // We have matching div-rem pair, but they are in two different blocks,239 // neither of which dominates one another.240 241 BasicBlock *PredBB = nullptr;242 BasicBlock *DivBB = DivInst->getParent();243 BasicBlock *RemBB = RemInst->getParent();244 245 // It's only safe to hoist if every instruction before the Div/Rem in the246 // basic block is guaranteed to transfer execution.247 auto IsSafeToHoist = [](Instruction *DivOrRem, BasicBlock *ParentBB) {248 for (auto I = ParentBB->begin(), E = DivOrRem->getIterator(); I != E;249 ++I)250 if (!isGuaranteedToTransferExecutionToSuccessor(&*I))251 return false;252 253 return true;254 };255 256 // Look for something like this257 // PredBB258 // | \259 // | Rem260 // | /261 // Div262 //263 // If the Rem block has a single predecessor and successor, and all paths264 // from PredBB go to either RemBB or DivBB, and execution of RemBB and265 // DivBB will always reach the Div/Rem, we can hoist Div to PredBB. If266 // we have a DivRem operation we can also hoist Rem. Otherwise we'll leave267 // Rem where it is and rewrite it to mul/sub.268 if (RemBB->getSingleSuccessor() == DivBB) {269 PredBB = RemBB->getUniquePredecessor();270 271 // Look for something like this272 // PredBB273 // / \274 // Div Rem275 //276 // If the Rem and Din blocks share a unique predecessor, and all277 // paths from PredBB go to either RemBB or DivBB, and execution of RemBB278 // and DivBB will always reach the Div/Rem, we can hoist Div to PredBB.279 // If we have a DivRem operation we can also hoist Rem. By hoisting both280 // ops to the same block, we reduce code size and allow the DivRem to281 // issue sooner. Without a DivRem op, this transformation is282 // unprofitable because we would end up performing an extra Mul+Sub on283 // the Rem path.284 } else if (BasicBlock *RemPredBB = RemBB->getUniquePredecessor()) {285 // This hoist is only profitable when the target has a DivRem op.286 if (HasDivRemOp && RemPredBB == DivBB->getUniquePredecessor())287 PredBB = RemPredBB;288 }289 // FIXME: We could handle more hoisting cases.290 291 if (PredBB && !isa<CatchSwitchInst>(PredBB->getTerminator()) &&292 isGuaranteedToTransferExecutionToSuccessor(PredBB->getTerminator()) &&293 IsSafeToHoist(RemInst, RemBB) && IsSafeToHoist(DivInst, DivBB) &&294 all_of(successors(PredBB),295 [&](BasicBlock *BB) { return BB == DivBB || BB == RemBB; }) &&296 all_of(predecessors(DivBB),297 [&](BasicBlock *BB) { return BB == RemBB || BB == PredBB; })) {298 DivDominates = true;299 DivInst->moveBefore(PredBB->getTerminator()->getIterator());300 Changed = true;301 if (HasDivRemOp) {302 RemInst->moveBefore(PredBB->getTerminator()->getIterator());303 continue;304 }305 } else306 continue;307 }308 309 // The target does not have a single div/rem operation,310 // and the rem is already in expanded form. Nothing to do.311 if (!HasDivRemOp && E.isRemExpanded())312 continue;313 314 if (HasDivRemOp) {315 // The target has a single div/rem operation. Hoist the lower instruction316 // to make the matched pair visible to the backend.317 if (DivDominates)318 RemInst->moveAfter(DivInst);319 else320 DivInst->moveAfter(RemInst);321 NumHoisted++;322 } else {323 // The target does not have a single div/rem operation,324 // and the rem is *not* in a already-expanded form.325 // Decompose the remainder calculation as:326 // X % Y --> X - ((X / Y) * Y).327 328 assert(!RemOriginallyWasInExpandedForm &&329 "We should not be expanding if the rem was in expanded form to "330 "begin with.");331 332 Value *X = E.getDividend();333 Value *Y = E.getDivisor();334 Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y);335 Instruction *Sub = BinaryOperator::CreateSub(X, Mul);336 337 // If the remainder dominates, then hoist the division up to that block:338 //339 // bb1:340 // %rem = srem %x, %y341 // bb2:342 // %div = sdiv %x, %y343 // -->344 // bb1:345 // %div = sdiv %x, %y346 // %mul = mul %div, %y347 // %rem = sub %x, %mul348 //349 // If the division dominates, it's already in the right place. The mul+sub350 // will be in a different block because we don't assume that they are351 // cheap to speculatively execute:352 //353 // bb1:354 // %div = sdiv %x, %y355 // bb2:356 // %rem = srem %x, %y357 // -->358 // bb1:359 // %div = sdiv %x, %y360 // bb2:361 // %mul = mul %div, %y362 // %rem = sub %x, %mul363 //364 // If the div and rem are in the same block, we do the same transform,365 // but any code movement would be within the same block.366 367 if (!DivDominates)368 DivInst->moveBefore(RemInst->getIterator());369 Mul->insertAfter(RemInst->getIterator());370 Mul->setDebugLoc(RemInst->getDebugLoc());371 Sub->insertAfter(Mul->getIterator());372 Sub->setDebugLoc(RemInst->getDebugLoc());373 374 // If DivInst has the exact flag, remove it. Otherwise this optimization375 // may replace a well-defined value 'X % Y' with poison.376 DivInst->dropPoisonGeneratingFlags();377 378 // If X can be undef, X should be frozen first.379 // For example, let's assume that Y = 1 & X = undef:380 // %div = sdiv undef, 1 // %div = undef381 // %rem = srem undef, 1 // %rem = 0382 // =>383 // %div = sdiv undef, 1 // %div = undef384 // %mul = mul %div, 1 // %mul = undef385 // %rem = sub %x, %mul // %rem = undef - undef = undef386 // If X is not frozen, %rem becomes undef after transformation.387 if (!isGuaranteedNotToBeUndef(X, nullptr, DivInst, &DT)) {388 auto *FrX =389 new FreezeInst(X, X->getName() + ".frozen", DivInst->getIterator());390 FrX->setDebugLoc(DivInst->getDebugLoc());391 DivInst->setOperand(0, FrX);392 Sub->setOperand(0, FrX);393 }394 // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,395 // but %rem in tgt can be one of many integer values.396 if (!isGuaranteedNotToBeUndef(Y, nullptr, DivInst, &DT)) {397 auto *FrY =398 new FreezeInst(Y, Y->getName() + ".frozen", DivInst->getIterator());399 FrY->setDebugLoc(DivInst->getDebugLoc());400 DivInst->setOperand(1, FrY);401 Mul->setOperand(1, FrY);402 }403 404 // Now kill the explicit remainder. We have replaced it with:405 // (sub X, (mul (div X, Y), Y)406 Sub->setName(RemInst->getName() + ".decomposed");407 Instruction *OrigRemInst = RemInst;408 // Update AssertingVH<> with new instruction so it doesn't assert.409 RemInst = Sub;410 // And replace the original instruction with the new one.411 OrigRemInst->replaceAllUsesWith(Sub);412 OrigRemInst->eraseFromParent();413 NumDecomposed++;414 }415 Changed = true;416 }417 418 return Changed;419}420 421// Pass manager boilerplate below here.422 423PreservedAnalyses DivRemPairsPass::run(Function &F,424 FunctionAnalysisManager &FAM) {425 TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F);426 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);427 if (!optimizeDivRem(F, TTI, DT))428 return PreservedAnalyses::all();429 // TODO: This pass just hoists/replaces math ops - all analyses are preserved?430 PreservedAnalyses PA;431 PA.preserveSet<CFGAnalyses>();432 return PA;433}434