1 files changed, 37 insertions, 50 deletions

diff --git a/lib/Transforms/Utils/BypassSlowDivision.cpp b/lib/Transforms/Utils/BypassSlowDivision.cpp
index 83ec7f55d1af..f711b192f604 100644
--- a/lib/Transforms/Utils/BypassSlowDivision.cpp
+++ b/lib/Transforms/Utils/BypassSlowDivision.cpp
@@ -1,4 +1,4 @@
-//===-- BypassSlowDivision.cpp - Bypass slow division ---------------------===//
+//===- BypassSlowDivision.cpp - Bypass slow division ----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -17,27 +17,32 @@
 
 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Transforms/Utils/Local.h"
+#include <cassert>
+#include <cstdint>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "bypass-slow-division"
 
 namespace {
-  struct DivOpInfo {
-    bool SignedOp;
-    Value *Dividend;
-    Value *Divisor;
-
-    DivOpInfo(bool InSignedOp, Value *InDividend, Value *InDivisor)
-      : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {}
-  };
 
   struct QuotRemPair {
     Value *Quotient;
@@ -55,38 +60,11 @@ namespace {
     Value *Quotient = nullptr;
     Value *Remainder = nullptr;
   };
-}
-
-namespace llvm {
-  template<>
-  struct DenseMapInfo<DivOpInfo> {
-    static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
-      return Val1.SignedOp == Val2.SignedOp &&
-             Val1.Dividend == Val2.Dividend &&
-             Val1.Divisor == Val2.Divisor;
-    }
-
-    static DivOpInfo getEmptyKey() {
-      return DivOpInfo(false, nullptr, nullptr);
-    }
 
-    static DivOpInfo getTombstoneKey() {
-      return DivOpInfo(true, nullptr, nullptr);
-    }
+using DivCacheTy = DenseMap<DivRemMapKey, QuotRemPair>;
+using BypassWidthsTy = DenseMap<unsigned, unsigned>;
+using VisitedSetTy = SmallPtrSet<Instruction *, 4>;
 
-    static unsigned getHashValue(const DivOpInfo &Val) {
-      return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^
-                        reinterpret_cast<uintptr_t>(Val.Divisor)) ^
-                        (unsigned)Val.SignedOp;
-    }
-  };
-
-  typedef DenseMap<DivOpInfo, QuotRemPair> DivCacheTy;
-  typedef DenseMap<unsigned, unsigned> BypassWidthsTy;
-  typedef SmallPtrSet<Instruction *, 4> VisitedSetTy;
-}
-
-namespace {
 enum ValueRange {
   /// Operand definitely fits into BypassType. No runtime checks are needed.
   VALRNG_KNOWN_SHORT,
@@ -116,17 +94,21 @@ class FastDivInsertionTask {
     return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
            SlowDivOrRem->getOpcode() == Instruction::SRem;
   }
+
   bool isDivisionOp() {
     return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
            SlowDivOrRem->getOpcode() == Instruction::UDiv;
   }
+
   Type *getSlowType() { return SlowDivOrRem->getType(); }
 
 public:
   FastDivInsertionTask(Instruction *I, const BypassWidthsTy &BypassWidths);
+
   Value *getReplacement(DivCacheTy &Cache);
 };
-} // anonymous namespace
+
+} // end anonymous namespace
 
 FastDivInsertionTask::FastDivInsertionTask(Instruction *I,
                                            const BypassWidthsTy &BypassWidths) {
@@ -175,7 +157,7 @@ Value *FastDivInsertionTask::getReplacement(DivCacheTy &Cache) {
   // Then, look for a value in Cache.
   Value *Dividend = SlowDivOrRem->getOperand(0);
   Value *Divisor = SlowDivOrRem->getOperand(1);
-  DivOpInfo Key(isSignedOp(), Dividend, Divisor);
+  DivRemMapKey Key(isSignedOp(), Dividend, Divisor);
   auto CacheI = Cache.find(Key);
 
   if (CacheI == Cache.end()) {
@@ -225,7 +207,7 @@ bool FastDivInsertionTask::isHashLikeValue(Value *V, VisitedSetTy &Visited) {
       C = dyn_cast<ConstantInt>(cast<BitCastInst>(Op1)->getOperand(0));
     return C && C->getValue().getMinSignedBits() > BypassType->getBitWidth();
   }
-  case Instruction::PHI: {
+  case Instruction::PHI:
     // Stop IR traversal in case of a crazy input code. This limits recursion
     // depth.
     if (Visited.size() >= 16)
@@ -241,7 +223,6 @@ bool FastDivInsertionTask::isHashLikeValue(Value *V, VisitedSetTy &Visited) {
       return getValueRange(V, Visited) == VALRNG_LIKELY_LONG ||
              isa<UndefValue>(V);
     });
-  }
   default:
     return false;
   }
@@ -371,11 +352,6 @@ Optional<QuotRemPair> FastDivInsertionTask::insertFastDivAndRem() {
   Value *Dividend = SlowDivOrRem->getOperand(0);
   Value *Divisor = SlowDivOrRem->getOperand(1);
 
-  if (isa<ConstantInt>(Divisor)) {
-    // Keep division by a constant for DAGCombiner.
-    return None;
-  }
-
   VisitedSetTy SetL;
   ValueRange DividendRange = getValueRange(Dividend, SetL);
   if (DividendRange == VALRNG_LIKELY_LONG)
@@ -391,7 +367,9 @@ Optional<QuotRemPair> FastDivInsertionTask::insertFastDivAndRem() {
 
   if (DividendShort && DivisorShort) {
     // If both operands are known to be short then just replace the long
-    // division with a short one in-place.
+    // division with a short one in-place.  Since we're not introducing control
+    // flow in this case, narrowing the division is always a win, even if the
+    // divisor is a constant (and will later get replaced by a multiplication).
 
     IRBuilder<> Builder(SlowDivOrRem);
     Value *TruncDividend = Builder.CreateTrunc(Dividend, BypassType);
@@ -401,7 +379,16 @@ Optional<QuotRemPair> FastDivInsertionTask::insertFastDivAndRem() {
     Value *ExtDiv = Builder.CreateZExt(TruncDiv, getSlowType());
     Value *ExtRem = Builder.CreateZExt(TruncRem, getSlowType());
     return QuotRemPair(ExtDiv, ExtRem);
-  } else if (DividendShort && !isSignedOp()) {
+  }
+
+  if (isa<ConstantInt>(Divisor)) {
+    // If the divisor is not a constant, DAGCombiner will convert it to a
+    // multiplication by a magic constant.  It isn't clear if it is worth
+    // introducing control flow to get a narrower multiply.
+    return None;
+  }
+
+  if (DividendShort && !isSignedOp()) {
     // If the division is unsigned and Dividend is known to be short, then
     // either
     // 1) Divisor is less or equal to Dividend, and the result can be computed