Lines Matching +full:sub +full:- +full:blocks
1 //===- DivRemPairs.cpp - Hoist/[dr]ecompose division and remainder --------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
31 #define DEBUG_TYPE "div-rem-pairs"
36 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
37 "Controls transformations in div-rem-pairs pass");
47 /// X - ((X ?/ Y) * Y)
66 M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv;
74 /// A thin wrapper to store two values that we matched as div-rem pair.
86 assert((DivInst->getOpcode() == Instruction::UDiv ||
87 DivInst->getOpcode() == Instruction::SDiv) &&
89 assert(DivInst->getType() == RemInst->getType() && "Types should match.");
95 Type *getType() const { return DivInst->getType(); }
98 bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }
101 Value *getDividend() const { return DivInst->getOperand(0); }
102 Value *getDivisor() const { return DivInst->getOperand(1); }
105 switch (RemInst->getOpcode()) {
108 return false; // single 'rem' instruction - unexpanded form.
140 RemMap[Match->Key] = Match->Value;
144 // We'll accumulate the matching pairs of div-rem instructions here.
161 Worklist.emplace_back(It->second, RemInst);
168 /// denominator, and signedness). If they exist in different basic blocks, bring
171 /// X % Y <--> X - ((X / Y) * Y).
185 // Get the matching pairs of div-rem instructions. We want this extra
211 RealRem->setName(RemInst->getName() + ".recomposed");
212 RealRem->insertAfter(RemInst);
217 OrigRemInst->replaceAllUsesWith(RealRem);
218 RealRem->setDebugLoc(OrigRemInst->getDebugLoc());
219 OrigRemInst->eraseFromParent();
222 // If it had other uses we could rewrite it as X - X % Y
227 "*If* the target supports div-rem, then by now the RemInst *is* "
233 if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())
238 // We have matching div-rem pair, but they are in two different blocks,
242 BasicBlock *DivBB = DivInst->getParent();
243 BasicBlock *RemBB = RemInst->getParent();
248 for (auto I = ParentBB->begin(), E = DivOrRem->getIterator(); I != E;
267 // Rem where it is and rewrite it to mul/sub.
268 if (RemBB->getSingleSuccessor() == DivBB) {
269 PredBB = RemBB->getUniquePredecessor();
276 // If the Rem and Din blocks share a unique predecessor, and all
282 // unprofitable because we would end up performing an extra Mul+Sub on
284 } else if (BasicBlock *RemPredBB = RemBB->getUniquePredecessor()) {
286 if (HasDivRemOp && RemPredBB == DivBB->getUniquePredecessor())
291 if (PredBB && !isa<CatchSwitchInst>(PredBB->getTerminator()) &&
292 isGuaranteedToTransferExecutionToSuccessor(PredBB->getTerminator()) &&
299 DivInst->moveBefore(PredBB->getTerminator());
302 RemInst->moveBefore(PredBB->getTerminator());
318 RemInst->moveAfter(DivInst);
320 DivInst->moveAfter(RemInst);
324 // and the rem is *not* in a already-expanded form.
326 // X % Y --> X - ((X / Y) * Y).
335 Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
343 // -->
347 // %rem = sub %x, %mul
349 // If the division dominates, it's already in the right place. The mul+sub
357 // -->
362 // %rem = sub %x, %mul
368 DivInst->moveBefore(RemInst);
369 Mul->insertAfter(RemInst);
370 Mul->setDebugLoc(RemInst->getDebugLoc());
371 Sub->insertAfter(Mul);
372 Sub->setDebugLoc(RemInst->getDebugLoc());
375 // may replace a well-defined value 'X % Y' with poison.
376 DivInst->dropPoisonGeneratingFlags();
385 // %rem = sub %x, %mul // %rem = undef - undef = undef
389 new FreezeInst(X, X->getName() + ".frozen", DivInst->getIterator());
390 FrX->setDebugLoc(DivInst->getDebugLoc());
391 DivInst->setOperand(0, FrX);
392 Sub->setOperand(0, FrX);
398 new FreezeInst(Y, Y->getName() + ".frozen", DivInst->getIterator());
399 FrY->setDebugLoc(DivInst->getDebugLoc());
400 DivInst->setOperand(1, FrY);
401 Mul->setOperand(1, FrY);
405 // (sub X, (mul (div X, Y), Y)
406 Sub->setName(RemInst->getName() + ".decomposed");
409 RemInst = Sub;
411 OrigRemInst->replaceAllUsesWith(Sub);
412 OrigRemInst->eraseFromParent();
429 // TODO: This pass just hoists/replaces math ops - all analyses are preserved?