Clarify that the bypassSlowDivision optimization operates on a single BB [v2]

[jlebar]

Summary

Update some comments to be more explicit.

Change bypassSlowDivision and the functions it calls so that they take
BasicBlock*s and Instruction*s, rather than Function::iterator&s and
BasicBlock::iterator&s.

Change the APIs so that the caller is responsible for updating the
iterator, rather than the callee. This makes control flow much easier
to follow.

[tyler.nowicki]

LGTM!

Sorry for the delayed response. Holidays getting in the way.

[jlebar]

Sync to HEAD.

[echristo]

Committed thusly for jlebar:

dzur:~/sources/llvm> git svn dcommit
Committing to https://llvm.org/svn/llvm-project/llvm/trunk ...
M include/llvm/Transforms/Utils/BypassSlowDivision.h
M lib/CodeGen/CodeGenPrepare.cpp
M lib/Transforms/Utils/BypassSlowDivision.cpp
Committed r256789

include/llvm/Transforms/Utils/BypassSlowDivision.h

 #ifndef LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H
 #define LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/Function.h"
 
 namespace llvm {
 
-/// This optimization identifies DIV instructions that can be
+/// This optimization identifies DIV instructions in a BB that can be
 /// profitably bypassed and carried out with a shorter, faster divide.
-bool bypassSlowDivision(Function &F,
-                        Function::iterator &I,
-                        const DenseMap<unsigned int, unsigned int> &BypassWidth);
+///
+/// This optimization may add basic blocks immediately after BB; for obvious
+/// reasons, you shouldn't pass those blocks to bypassSlowDivision.
+bool bypassSlowDivision(
+    BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth);
 
 } // End llvm namespace
 
 #endif

lib/CodeGen/CodeGenPrepare.cpp

bool CodeGenPrepare::runOnFunction(Function &F) {
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   OptSize = F.optForSize();
 
   /// This optimization identifies DIV instructions that can be
   /// profitably bypassed and carried out with a shorter, faster divide.
   if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
     const DenseMap<unsigned int, unsigned int> &BypassWidths =
        TLI->getBypassSlowDivWidths();
-    for (Function::iterator I = F.begin(); I != F.end(); I++)
-      EverMadeChange |= bypassSlowDivision(F, I, BypassWidths);
+    BasicBlock* BB = &*F.begin();
+    while (BB != nullptr) {
+      // bypassSlowDivision may create new BBs, but we don't want to reapply the
+      // optimization to those blocks.
+      BasicBlock* Next = BB->getNextNode();
+      EverMadeChange |= bypassSlowDivision(BB, BypassWidths);
+      BB = Next;
+    }
   }
 
   // Eliminate blocks that contain only PHI nodes and an
   // unconditional branch.
   EverMadeChange |= eliminateMostlyEmptyBlocks(F);
 
   // llvm.dbg.value is far away from the value then iSel may not be able
   // handle it properly. iSel will drop llvm.dbg.value if it can not

lib/Transforms/Utils/BypassSlowDivision.cpp

namespace llvm {
   };
 
   typedef DenseMap<DivOpInfo, DivPhiNodes> DivCacheTy;
 }
 
 // insertFastDiv - Substitutes the div/rem instruction with code that checks the
 // value of the operands and uses a shorter-faster div/rem instruction when
 // possible and the longer-slower div/rem instruction otherwise.
-static bool insertFastDiv(Function &F,
-                          Function::iterator &I,
-                          BasicBlock::iterator &J,
-                          IntegerType *BypassType,
-                          bool UseDivOp,
-                          bool UseSignedOp,
+static bool insertFastDiv(Instruction *I, IntegerType *BypassType,
+                          bool UseDivOp, bool UseSignedOp,
                           DivCacheTy &PerBBDivCache) {
+  Function *F = I->getParent()->getParent();
   // Get instruction operands
-  Instruction *Instr = &*J;
-  Value *Dividend = Instr->getOperand(0);
-  Value *Divisor = Instr->getOperand(1);
+  Value *Dividend = I->getOperand(0);
+  Value *Divisor = I->getOperand(1);
 
   if (isa<ConstantInt>(Divisor) ||
       (isa<ConstantInt>(Dividend) && isa<ConstantInt>(Divisor))) {
     // Operations with immediate values should have
     // been solved and replaced during compile time.
     return false;
   }
 
   // Basic Block is split before divide
-  BasicBlock *MainBB = &*I;
-  BasicBlock *SuccessorBB = I->splitBasicBlock(J);
-  ++I; //advance iterator I to successorBB
+  BasicBlock *MainBB = &*I->getParent();
+  BasicBlock *SuccessorBB = MainBB->splitBasicBlock(I);
 
   // Add new basic block for slow divide operation
-  BasicBlock *SlowBB = BasicBlock::Create(F.getContext(), "",
-                                          MainBB->getParent(), SuccessorBB);
+  BasicBlock *SlowBB =
+      BasicBlock::Create(F->getContext(), "", MainBB->getParent(), SuccessorBB);
   SlowBB->moveBefore(SuccessorBB);
   IRBuilder<> SlowBuilder(SlowBB, SlowBB->begin());
   Value *SlowQuotientV;
   Value *SlowRemainderV;
   if (UseSignedOp) {
     SlowQuotientV = SlowBuilder.CreateSDiv(Dividend, Divisor);
     SlowRemainderV = SlowBuilder.CreateSRem(Dividend, Divisor);
   } else {
     SlowQuotientV = SlowBuilder.CreateUDiv(Dividend, Divisor);
     SlowRemainderV = SlowBuilder.CreateURem(Dividend, Divisor);
   }
   SlowBuilder.CreateBr(SuccessorBB);
 
   // Add new basic block for fast divide operation
-  BasicBlock *FastBB = BasicBlock::Create(F.getContext(), "",
-                                          MainBB->getParent(), SuccessorBB);
+  BasicBlock *FastBB =
+      BasicBlock::Create(F->getContext(), "", MainBB->getParent(), SuccessorBB);
   FastBB->moveBefore(SlowBB);
   IRBuilder<> FastBuilder(FastBB, FastBB->begin());
   Value *ShortDivisorV = FastBuilder.CreateCast(Instruction::Trunc, Divisor,
                                                 BypassType);
   Value *ShortDividendV = FastBuilder.CreateCast(Instruction::Trunc, Dividend,
                                                  BypassType);
 
   // udiv/urem because optimization only handles positive numbers
   Value *ShortQuotientV = FastBuilder.CreateExactUDiv(ShortDividendV,
                                                       ShortDivisorV);
   Value *ShortRemainderV = FastBuilder.CreateURem(ShortDividendV,
                                                   ShortDivisorV);
   Value *FastQuotientV = FastBuilder.CreateCast(Instruction::ZExt,
                                                 ShortQuotientV,
                                                 Dividend->getType());
   Value *FastRemainderV = FastBuilder.CreateCast(Instruction::ZExt,
                                                  ShortRemainderV,
                                                  Dividend->getType());
   FastBuilder.CreateBr(SuccessorBB);
 
   // Phi nodes for result of div and rem
   IRBuilder<> SuccessorBuilder(SuccessorBB, SuccessorBB->begin());
-  PHINode *QuoPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2);
+  PHINode *QuoPhi = SuccessorBuilder.CreatePHI(I->getType(), 2);
   QuoPhi->addIncoming(SlowQuotientV, SlowBB);
   QuoPhi->addIncoming(FastQuotientV, FastBB);
-  PHINode *RemPhi = SuccessorBuilder.CreatePHI(Instr->getType(), 2);
+  PHINode *RemPhi = SuccessorBuilder.CreatePHI(I->getType(), 2);
   RemPhi->addIncoming(SlowRemainderV, SlowBB);
   RemPhi->addIncoming(FastRemainderV, FastBB);
 
-  // Replace Instr with appropriate phi node
+  // Replace I with appropriate phi node
   if (UseDivOp)
-    Instr->replaceAllUsesWith(QuoPhi);
+    I->replaceAllUsesWith(QuoPhi);
   else
-    Instr->replaceAllUsesWith(RemPhi);
-  Instr->eraseFromParent();
+    I->replaceAllUsesWith(RemPhi);
+  I->eraseFromParent();
 
   // Combine operands into a single value with OR for value testing below
   MainBB->getInstList().back().eraseFromParent();
   IRBuilder<> MainBuilder(MainBB, MainBB->end());
   Value *OrV = MainBuilder.CreateOr(Dividend, Divisor);
 
   // BitMask is inverted to check if the operands are
   // larger than the bypass type
   uint64_t BitMask = ~BypassType->getBitMask();
   Value *AndV = MainBuilder.CreateAnd(OrV, BitMask);
 
   // Compare operand values and branch
   Value *ZeroV = ConstantInt::getSigned(Dividend->getType(), 0);
   Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV);
   MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB);
 
-  // point iterator J at first instruction of successorBB
-  J = I->begin();
-
   // Cache phi nodes to be used later in place of other instances
   // of div or rem with the same sign, dividend, and divisor
   DivOpInfo Key(UseSignedOp, Dividend, Divisor);
   DivPhiNodes Value(QuoPhi, RemPhi);
   PerBBDivCache.insert(std::pair<DivOpInfo, DivPhiNodes>(Key, Value));
   return true;
 }
 
-// reuseOrInsertFastDiv - Reuses previously computed dividend or remainder if
-// operands and operation are identical. Otherwise call insertFastDiv to perform
-// the optimization and cache the resulting dividend and remainder.
-static bool reuseOrInsertFastDiv(Function &F,
-                                 Function::iterator &I,
-                                 BasicBlock::iterator &J,
-                                 IntegerType *BypassType,
-                                 bool UseDivOp,
-                                 bool UseSignedOp,
+// reuseOrInsertFastDiv - Reuses previously computed dividend or remainder from
+// the current BB if operands and operation are identical. Otherwise calls
+// insertFastDiv to perform the optimization and caches the resulting dividend
+// and remainder.
+static bool reuseOrInsertFastDiv(Instruction *I, IntegerType *BypassType,
+                                 bool UseDivOp, bool UseSignedOp,
                                  DivCacheTy &PerBBDivCache) {
   // Get instruction operands
-  Instruction *Instr = &*J;
-  DivOpInfo Key(UseSignedOp, Instr->getOperand(0), Instr->getOperand(1));
+  DivOpInfo Key(UseSignedOp, I->getOperand(0), I->getOperand(1));
   DivCacheTy::iterator CacheI = PerBBDivCache.find(Key);
 
   if (CacheI == PerBBDivCache.end()) {
     // If previous instance does not exist, insert fast div
-    return insertFastDiv(F, I, J, BypassType, UseDivOp, UseSignedOp,
-                         PerBBDivCache);
+    return insertFastDiv(I, BypassType, UseDivOp, UseSignedOp, PerBBDivCache);
   }
 
   // Replace operation value with previously generated phi node
   DivPhiNodes &Value = CacheI->second;
   if (UseDivOp) {
     // Replace all uses of div instruction with quotient phi node
-    J->replaceAllUsesWith(Value.Quotient);
+    I->replaceAllUsesWith(Value.Quotient);
   } else {
     // Replace all uses of rem instruction with remainder phi node
-    J->replaceAllUsesWith(Value.Remainder);
+    I->replaceAllUsesWith(Value.Remainder);
   }
 
-  // Advance to next operation
-  ++J;
-
   // Remove redundant operation
-  Instr->eraseFromParent();
+  I->eraseFromParent();
   return true;
 }
 
-// bypassSlowDivision - This optimization identifies DIV instructions that can
-// be profitably bypassed and carried out with a shorter, faster divide.
-bool llvm::bypassSlowDivision(Function &F,
-                              Function::iterator &I,
-                              const DenseMap<unsigned int, unsigned int> &BypassWidths) {
+// bypassSlowDivision - This optimization identifies DIV instructions in a BB
+// that can be profitably bypassed and carried out with a shorter, faster
+// divide.
+bool llvm::bypassSlowDivision(
+    BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidths) {
   DivCacheTy DivCache;
 
   bool MadeChange = false;
-  for (BasicBlock::iterator J = I->begin(); J != I->end(); J++) {
+  Instruction* Next = &*BB->begin();
+  while (Next != nullptr) {
+    // We may add instructions immediately after I, but we want to skip over
+    // them.
+    Instruction* I = Next;
+    Next = Next->getNextNode();
 
     // Get instruction details
-    unsigned Opcode = J->getOpcode();
+    unsigned Opcode = I->getOpcode();
     bool UseDivOp = Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
     bool UseRemOp = Opcode == Instruction::SRem || Opcode == Instruction::URem;
     bool UseSignedOp = Opcode == Instruction::SDiv ||
                        Opcode == Instruction::SRem;
 
     // Only optimize div or rem ops
     if (!UseDivOp && !UseRemOp)
       continue;
 
     // Skip division on vector types, only optimize integer instructions
-    if (!J->getType()->isIntegerTy())
+    if (!I->getType()->isIntegerTy())
       continue;
 
     // Get bitwidth of div/rem instruction
-    IntegerType *T = cast<IntegerType>(J->getType());
+    IntegerType *T = cast<IntegerType>(I->getType());
     unsigned int bitwidth = T->getBitWidth();
 
     // Continue if bitwidth is not bypassed
     DenseMap<unsigned int, unsigned int>::const_iterator BI = BypassWidths.find(bitwidth);
     if (BI == BypassWidths.end())
       continue;
 
     // Get type for div/rem instruction with bypass bitwidth
-    IntegerType *BT = IntegerType::get(J->getContext(), BI->second);
+    IntegerType *BT = IntegerType::get(I->getContext(), BI->second);
 
-    MadeChange |= reuseOrInsertFastDiv(F, I, J, BT, UseDivOp,
-                                       UseSignedOp, DivCache);
+    MadeChange |= reuseOrInsertFastDiv(I, BT, UseDivOp, UseSignedOp, DivCache);
   }
 
   return MadeChange;
 }