Merge clang, llvm, lld, lldb, compiler-rt and libc++ 5.0.0 release.

MFC r309126 (by emaste):

  Correct lld llvm-tblgen dependency file name

MFC r309169:

  Get rid of separate Subversion mergeinfo properties for llvm-dwarfdump
  and llvm-lto.  The mergeinfo confuses Subversion enormously, and these
  directories will just use the mergeinfo for llvm itself.

MFC r312765:

  Pull in r276136 from upstream llvm trunk (by Wei Mi):

    Use ValueOffsetPair to enhance value reuse during SCEV expansion.

    In D12090, the ExprValueMap was added to reuse existing value during
    SCEV expansion. However, const folding and sext/zext distribution can
    make the reuse still difficult.

    A simplified case is: suppose we know S1 expands to V1 in
    ExprValueMap, and
      S1 = S2 + C_a
      S3 = S2 + C_b
    where C_a and C_b are different SCEVConstants. Then we'd like to
    expand S3 as V1 - C_a + C_b instead of expanding S2 literally. It is
    helpful when S2 is a complex SCEV expr and S2 has no entry in
    ExprValueMap, which is usually caused by the fact that S3 is
    generated from S1 after const folding.

    In order to do that, we represent ExprValueMap as a mapping from SCEV
    to ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a}
    into the ExprValueMap when we create SCEV for V1. When S3 is
    expanded, it will first expand S2 to V1 - C_a because of S2->{V1,
    C_a} in the map, then expand S3 to V1 - C_a + C_b.

    Differential Revision: https://reviews.llvm.org/D21313

  This should fix assertion failures when building OpenCV >= 3.1.

  PR:		215649

MFC r312831:

  Revert r312765 for now, since it causes assertions when building
  lang/spidermonkey24.

  Reported by:	antoine
  PR:		215649

MFC r316511 (by jhb):

  Add an implementation of __ffssi2() derived from __ffsdi2().

  Newer versions of GCC include an __ffssi2() symbol in libgcc and the
  compiler can emit calls to it in generated code.  This is true for at
  least GCC 6.2 when compiling world for mips and mips64.

  Reviewed by:	jmallett, dim
  Sponsored by:	DARPA / AFRL
  Differential Revision:	https://reviews.freebsd.org/D10086

MFC r318601 (by adrian):

  [libcompiler-rt] add bswapdi2/bswapsi2

  This is required for mips gcc 6.3 userland to build/run.

  Reviewed by:	emaste, dim
  Approved by:	emaste
  Differential Revision:	https://reviews.freebsd.org/D10838

MFC r318884 (by emaste):

  lldb: map TRAP_CAP to a trace trap

  In the absense of a more specific handler for TRAP_CAP (generated by
  ENOTCAPABLE or ECAPMODE while in capability mode) treat it as a trace
  trap.

  Example usage (testing the bug in PR219173):

  % proccontrol -m trapcap lldb usr.bin/hexdump/obj/hexdump -- -Cv -s 1 /bin/ls
  ...
  (lldb) run
  Process 12980 launching
  Process 12980 launched: '.../usr.bin/hexdump/obj/hexdump' (x86_64)
  Process 12980 stopped
  * thread #1, stop reason = trace
      frame #0: 0x0000004b80c65f1a libc.so.7`__sys_lseek + 10
  ...

  In the future we should have LLDB control the trapcap procctl itself
  (as it does with ASLR), as well as report a specific stop reason.
  This change eliminates an assertion failure from LLDB for now.

MFC r319796:

  Remove a few unneeded files from libllvm, libclang and liblldb.

MFC r319885 (by emaste):

  lld: ELF: Fix ICF crash on absolute symbol relocations.

  If two sections contained relocations to absolute symbols with the same
  value we would crash when trying to access their sections. Add a check that
  both symbols point to sections before accessing their sections, and treat
  absolute symbols as equal if their values are equal.

  Obtained from:	LLD commit r292578

MFC r319918:

  Revert r319796 for now, it can cause undefined references when linking
  in some circumstances.

  Reported by:	Shawn Webb <shawn.webb@hardenedbsd.org>

MFC r319957 (by emaste):

  lld: Add armelf emulation mode

  Obtained from:	LLD r305375

MFC r321369:

  Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to
  5.0.0 (trunk r308421).  Upstream has branched for the 5.0.0 release,
  which should be in about a month.  Please report bugs and regressions,
  so we can get them into the release.

  Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11
  support to build; see UPDATING for more information.

MFC r321420:

  Add a few more object files to liblldb, which should solve errors when
  linking the lldb executable in some cases.  In particular, when the
  -ffunction-sections -fdata-sections options are turned off, or
  ineffective.

  Reported by:	Shawn Webb, Mark Millard

MFC r321433:

  Cleanup stale Options.inc files from the previous libllvm build for
  clang 4.0.0.  Otherwise, these can get included before the two newly
  generated ones (which are different) for clang 5.0.0.

  Reported by:	Mark Millard

MFC r321439 (by bdrewery):

  Move llvm Options.inc hack from r321433 for NO_CLEAN to lib/clang/libllvm.

  The files are only ever generated to .OBJDIR, not to WORLDTMP (as a
  sysroot) and are only ever included from a compilation.  So using
  a beforebuild target here removes the file before the compilation
  tries to include it.

MFC r321664:

  Pull in r308891 from upstream llvm trunk (by Benjamin Kramer):

    [CodeGenPrepare] Cut off FindAllMemoryUses if there are too many uses.

    This avoids excessive compile time. The case I'm looking at is
    Function.cpp from an old version of LLVM that still had the giant
    memcmp string matcher in it. Before r308322 this compiled in about 2
    minutes, after it, clang takes infinite* time to compile it. With
    this patch we're at 5 min, which is still bad but this is a
    pathological case.

    The cut off at 20 uses was chosen by looking at other cut-offs in LLVM
    for user scanning. It's probably too high, but does the job and is
    very unlikely to regress anything.

    Fixes PR33900.

    * I'm impatient and aborted after 15 minutes, on the bug report it was
      killed after 2h.

  Pull in r308986 from upstream llvm trunk (by Simon Pilgrim):

    [X86][CGP] Reduce memcmp() expansion to 2 load pairs (PR33914)

    D35067/rL308322 attempted to support up to 4 load pairs for memcmp
    inlining which resulted in regressions for some optimized libc memcmp
    implementations (PR33914).

    Until we can match these more optimal cases, this patch reduces the
    memcmp expansion to a maximum of 2 load pairs (which matches what we
    do for -Os).

    This patch should be considered for the 5.0.0 release branch as well

    Differential Revision: https://reviews.llvm.org/D35830

  These fix a hang (or extremely long compile time) when building older
  LLVM ports.

  Reported by:    antoine
  PR:             219139

MFC r321719:

  Pull in r309503 from upstream clang trunk (by Richard Smith):

    PR33902: Invalidate line number cache when adding more text to
    existing buffer.

    This led to crashes as the line number cache would report a bogus
    line number for a line of code, and we'd try to find a nonexistent
    column within the line when printing diagnostics.

  This fixes an assertion when building the graphics/champlain port.

  Reported by:	antoine, kwm
  PR:		219139

MFC r321723:

  Upgrade our copies of clang, llvm, lld and lldb to r309439 from the
  upstream release_50 branch.  This is just after upstream's 5.0.0-rc1.

MFC r322320:

  Upgrade our copies of clang, llvm and libc++ to r310316 from the
  upstream release_50 branch.

MFC r322326 (by emaste):

  lldb: Make i386-*-freebsd expression work on JIT path

  * Enable i386 ABI creation for freebsd
  * Added an extra argument in ABISysV_i386::PrepareTrivialCall for mmap
    syscall
  * Unlike linux, the last argument of mmap is actually 64-bit(off_t).
    This requires us to push an additional word for the higher order bits.
  * Prior to this change, ktrace dump will show mmap failures due to
    invalid argument coming from the 6th mmap argument.

  Submitted by:	Karnajit Wangkhem
  Differential Revision:	https://reviews.llvm.org/D34776

MFC r322360 (by emaste):

  lldb: Report inferior signals as signals, not exceptions, on FreeBSD

  This is the FreeBSD equivalent of LLVM r238549.

  This serves 2 purposes:

  * LLDB should handle inferior process signals SIGSEGV/SIGILL/SIGBUS/
    SIGFPE the way it is suppose to be handled. Prior to this fix these
    signals will neither create a coredump, nor exit from the debugger
    or work for signal handling scenario.
  * eInvalidCrashReason need not report "unknown crash reason" if we have
    a valid si_signo

  llvm.org/pr23699

  Patch by Karnajit Wangkhem

  Differential Revision:  https://reviews.llvm.org/D35223

  Submitted by:	Karnajit Wangkhem
  Obtained from:	LLVM r310591

MFC r322474 (by emaste):

  lld: Add `-z muldefs` option.

  Obtained from:	LLVM r310757

MFC r322740:

  Upgrade our copies of clang, llvm, lld and libc++ to r311219 from the
  upstream release_50 branch.

MFC r322855:

  Upgrade our copies of clang, llvm, lldb and compiler-rt to r311606 from
  the upstream release_50 branch.

  As of this version, lib/msun's trig test should also work correctly
  again (see bug 220989 for more information).

  PR:		220989

MFC r323112:

  Upgrade our copies of clang, llvm, lldb and compiler-rt to r312293 from
  the upstream release_50 branch.  This corresponds to 5.0.0 rc4.

  As of this version, the cad/stepcode port should now compile in a more
  reasonable time on i386 (see bug 221836 for more information).

  PR:		221836

MFC r323245:

  Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to
  5.0.0 release (upstream r312559).

  Release notes for llvm, clang and lld will be available here soon:
  <http://releases.llvm.org/5.0.0/docs/ReleaseNotes.html>
  <http://releases.llvm.org/5.0.0/tools/clang/docs/ReleaseNotes.html>
  <http://releases.llvm.org/5.0.0/tools/lld/docs/ReleaseNotes.html>

  Relnotes:	yes

(cherry picked from commit 12cd91cf4c6b96a24427c0de5374916f2808d263)

1 files changed, 2341 insertions, 0 deletions

diff --git a/contrib/llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp b/contrib/llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp
new file mode 100644
index 0000000..f82ad6c
--- /dev/null
+++ b/contrib/llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp
@@ -0,0 +1,2341 @@
+//===--- HexagonLoopIdiomRecognition.cpp ----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "hexagon-lir"
+
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/KnownBits.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
+
+#include <algorithm>
+#include <array>
+
+using namespace llvm;
+
+static cl::opt<bool> DisableMemcpyIdiom("disable-memcpy-idiom",
+  cl::Hidden, cl::init(false),
+  cl::desc("Disable generation of memcpy in loop idiom recognition"));
+
+static cl::opt<bool> DisableMemmoveIdiom("disable-memmove-idiom",
+  cl::Hidden, cl::init(false),
+  cl::desc("Disable generation of memmove in loop idiom recognition"));
+
+static cl::opt<unsigned> RuntimeMemSizeThreshold("runtime-mem-idiom-threshold",
+  cl::Hidden, cl::init(0), cl::desc("Threshold (in bytes) for the runtime "
+  "check guarding the memmove."));
+
+static cl::opt<unsigned> CompileTimeMemSizeThreshold(
+  "compile-time-mem-idiom-threshold", cl::Hidden, cl::init(64),
+  cl::desc("Threshold (in bytes) to perform the transformation, if the "
+    "runtime loop count (mem transfer size) is known at compile-time."));
+
+static cl::opt<bool> OnlyNonNestedMemmove("only-nonnested-memmove-idiom",
+  cl::Hidden, cl::init(true),
+  cl::desc("Only enable generating memmove in non-nested loops"));
+
+cl::opt<bool> HexagonVolatileMemcpy("disable-hexagon-volatile-memcpy",
+  cl::Hidden, cl::init(false),
+  cl::desc("Enable Hexagon-specific memcpy for volatile destination."));
+
+static cl::opt<unsigned> SimplifyLimit("hlir-simplify-limit", cl::init(10000),
+  cl::Hidden, cl::desc("Maximum number of simplification steps in HLIR"));
+
+static const char *HexagonVolatileMemcpyName
+  = "hexagon_memcpy_forward_vp4cp4n2";
+
+
+namespace llvm {
+  void initializeHexagonLoopIdiomRecognizePass(PassRegistry&);
+  Pass *createHexagonLoopIdiomPass();
+}
+
+namespace {
+  class HexagonLoopIdiomRecognize : public LoopPass {
+  public:
+    static char ID;
+    explicit HexagonLoopIdiomRecognize() : LoopPass(ID) {
+      initializeHexagonLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
+    }
+    StringRef getPassName() const override {
+      return "Recognize Hexagon-specific loop idioms";
+    }
+
+   void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addRequired<LoopInfoWrapperPass>();
+      AU.addRequiredID(LoopSimplifyID);
+      AU.addRequiredID(LCSSAID);
+      AU.addRequired<AAResultsWrapperPass>();
+      AU.addPreserved<AAResultsWrapperPass>();
+      AU.addRequired<ScalarEvolutionWrapperPass>();
+      AU.addRequired<DominatorTreeWrapperPass>();
+      AU.addRequired<TargetLibraryInfoWrapperPass>();
+      AU.addPreserved<TargetLibraryInfoWrapperPass>();
+    }
+
+    bool runOnLoop(Loop *L, LPPassManager &LPM) override;
+
+  private:
+    unsigned getStoreSizeInBytes(StoreInst *SI);
+    int getSCEVStride(const SCEVAddRecExpr *StoreEv);
+    bool isLegalStore(Loop *CurLoop, StoreInst *SI);
+    void collectStores(Loop *CurLoop, BasicBlock *BB,
+        SmallVectorImpl<StoreInst*> &Stores);
+    bool processCopyingStore(Loop *CurLoop, StoreInst *SI, const SCEV *BECount);
+    bool coverLoop(Loop *L, SmallVectorImpl<Instruction*> &Insts) const;
+    bool runOnLoopBlock(Loop *CurLoop, BasicBlock *BB, const SCEV *BECount,
+        SmallVectorImpl<BasicBlock*> &ExitBlocks);
+    bool runOnCountableLoop(Loop *L);
+
+    AliasAnalysis *AA;
+    const DataLayout *DL;
+    DominatorTree *DT;
+    LoopInfo *LF;
+    const TargetLibraryInfo *TLI;
+    ScalarEvolution *SE;
+    bool HasMemcpy, HasMemmove;
+  };
+}
+
+char HexagonLoopIdiomRecognize::ID = 0;
+
+INITIALIZE_PASS_BEGIN(HexagonLoopIdiomRecognize, "hexagon-loop-idiom",
+    "Recognize Hexagon-specific loop idioms", false, false)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
+INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_END(HexagonLoopIdiomRecognize, "hexagon-loop-idiom",
+    "Recognize Hexagon-specific loop idioms", false, false)
+
+
+namespace {
+  struct Simplifier {
+    typedef std::function<Value* (Instruction*, LLVMContext&)> Rule;
+
+    void addRule(const Rule &R) { Rules.push_back(R); }
+
+  private:
+    struct WorkListType {
+      WorkListType() = default;
+
+      void push_back(Value* V) {
+        // Do not push back duplicates.
+        if (!S.count(V)) { Q.push_back(V); S.insert(V); }
+      }
+      Value *pop_front_val() {
+        Value *V = Q.front(); Q.pop_front(); S.erase(V);
+        return V;
+      }
+      bool empty() const { return Q.empty(); }
+
+    private:
+      std::deque<Value*> Q;
+      std::set<Value*> S;
+    };
+
+    typedef std::set<Value*> ValueSetType;
+    std::vector<Rule> Rules;
+
+  public:
+    struct Context {
+      typedef DenseMap<Value*,Value*> ValueMapType;
+
+      Value *Root;
+      ValueSetType Used;    // The set of all cloned values used by Root.
+      ValueSetType Clones;  // The set of all cloned values.
+      LLVMContext &Ctx;
+
+      Context(Instruction *Exp)
+        : Ctx(Exp->getParent()->getParent()->getContext()) {
+        initialize(Exp);
+      }
+      ~Context() { cleanup(); }
+      void print(raw_ostream &OS, const Value *V) const;
+
+      Value *materialize(BasicBlock *B, BasicBlock::iterator At);
+
+    private:
+      void initialize(Instruction *Exp);
+      void cleanup();
+
+      template <typename FuncT> void traverse(Value *V, FuncT F);
+      void record(Value *V);
+      void use(Value *V);
+      void unuse(Value *V);
+
+      bool equal(const Instruction *I, const Instruction *J) const;
+      Value *find(Value *Tree, Value *Sub) const;
+      Value *subst(Value *Tree, Value *OldV, Value *NewV);
+      void replace(Value *OldV, Value *NewV);
+      void link(Instruction *I, BasicBlock *B, BasicBlock::iterator At);
+
+      friend struct Simplifier;
+    };
+
+    Value *simplify(Context &C);
+  };
+
+  struct PE {
+    PE(const Simplifier::Context &c, Value *v = nullptr) : C(c), V(v) {}
+    const Simplifier::Context &C;
+    const Value *V;
+  };
+
+  raw_ostream &operator<< (raw_ostream &OS, const PE &P) LLVM_ATTRIBUTE_USED;
+  raw_ostream &operator<< (raw_ostream &OS, const PE &P) {
+    P.C.print(OS, P.V ? P.V : P.C.Root);
+    return OS;
+  }
+}
+
+
+template <typename FuncT>
+void Simplifier::Context::traverse(Value *V, FuncT F) {
+  WorkListType Q;
+  Q.push_back(V);
+
+  while (!Q.empty()) {
+    Instruction *U = dyn_cast<Instruction>(Q.pop_front_val());
+    if (!U || U->getParent())
+      continue;
+    if (!F(U))
+      continue;
+    for (Value *Op : U->operands())
+      Q.push_back(Op);
+  }
+}
+
+
+void Simplifier::Context::print(raw_ostream &OS, const Value *V) const {
+  const auto *U = dyn_cast<const Instruction>(V);
+  if (!U) {
+    OS << V << '(' << *V << ')';
+    return;
+  }
+
+  if (U->getParent()) {
+    OS << U << '(';
+    U->printAsOperand(OS, true);
+    OS << ')';
+    return;
+  }
+
+  unsigned N = U->getNumOperands();
+  if (N != 0)
+    OS << U << '(';
+  OS << U->getOpcodeName();
+  for (const Value *Op : U->operands()) {
+    OS << ' ';
+    print(OS, Op);
+  }
+  if (N != 0)
+    OS << ')';
+}
+
+
+void Simplifier::Context::initialize(Instruction *Exp) {
+  // Perform a deep clone of the expression, set Root to the root
+  // of the clone, and build a map from the cloned values to the
+  // original ones.
+  ValueMapType M;
+  BasicBlock *Block = Exp->getParent();
+  WorkListType Q;
+  Q.push_back(Exp);
+
+  while (!Q.empty()) {
+    Value *V = Q.pop_front_val();
+    if (M.find(V) != M.end())
+      continue;
+    if (Instruction *U = dyn_cast<Instruction>(V)) {
+      if (isa<PHINode>(U) || U->getParent() != Block)
+        continue;
+      for (Value *Op : U->operands())
+        Q.push_back(Op);
+      M.insert({U, U->clone()});
+    }
+  }
+
+  for (std::pair<Value*,Value*> P : M) {
+    Instruction *U = cast<Instruction>(P.second);
+    for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i) {
+      auto F = M.find(U->getOperand(i));
+      if (F != M.end())
+        U->setOperand(i, F->second);
+    }
+  }
+
+  auto R = M.find(Exp);
+  assert(R != M.end());
+  Root = R->second;
+
+  record(Root);
+  use(Root);
+}
+
+
+void Simplifier::Context::record(Value *V) {
+  auto Record = [this](Instruction *U) -> bool {
+    Clones.insert(U);
+    return true;
+  };
+  traverse(V, Record);
+}
+
+
+void Simplifier::Context::use(Value *V) {
+  auto Use = [this](Instruction *U) -> bool {
+    Used.insert(U);
+    return true;
+  };
+  traverse(V, Use);
+}
+
+
+void Simplifier::Context::unuse(Value *V) {
+  if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != nullptr)
+    return;
+
+  auto Unuse = [this](Instruction *U) -> bool {
+    if (!U->use_empty())
+      return false;
+    Used.erase(U);
+    return true;
+  };
+  traverse(V, Unuse);
+}
+
+
+Value *Simplifier::Context::subst(Value *Tree, Value *OldV, Value *NewV) {
+  if (Tree == OldV)
+    return NewV;
+  if (OldV == NewV)
+    return Tree;
+
+  WorkListType Q;
+  Q.push_back(Tree);
+  while (!Q.empty()) {
+    Instruction *U = dyn_cast<Instruction>(Q.pop_front_val());
+    // If U is not an instruction, or it's not a clone, skip it.
+    if (!U || U->getParent())
+      continue;
+    for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i) {
+      Value *Op = U->getOperand(i);
+      if (Op == OldV) {
+        U->setOperand(i, NewV);
+        unuse(OldV);
+      } else {
+        Q.push_back(Op);
+      }
+    }
+  }
+  return Tree;
+}
+
+
+void Simplifier::Context::replace(Value *OldV, Value *NewV) {
+  if (Root == OldV) {
+    Root = NewV;
+    use(Root);
+    return;
+  }
+
+  // NewV may be a complex tree that has just been created by one of the
+  // transformation rules. We need to make sure that it is commoned with
+  // the existing Root to the maximum extent possible.
+  // Identify all subtrees of NewV (including NewV itself) that have
+  // equivalent counterparts in Root, and replace those subtrees with
+  // these counterparts.
+  WorkListType Q;
+  Q.push_back(NewV);
+  while (!Q.empty()) {
+    Value *V = Q.pop_front_val();
+    Instruction *U = dyn_cast<Instruction>(V);
+    if (!U || U->getParent())
+      continue;
+    if (Value *DupV = find(Root, V)) {
+      if (DupV != V)
+        NewV = subst(NewV, V, DupV);
+    } else {
+      for (Value *Op : U->operands())
+        Q.push_back(Op);
+    }
+  }
+
+  // Now, simply replace OldV with NewV in Root.
+  Root = subst(Root, OldV, NewV);
+  use(Root);
+}
+
+
+void Simplifier::Context::cleanup() {
+  for (Value *V : Clones) {
+    Instruction *U = cast<Instruction>(V);
+    if (!U->getParent())
+      U->dropAllReferences();
+  }
+
+  for (Value *V : Clones) {
+    Instruction *U = cast<Instruction>(V);
+    if (!U->getParent())
+      U->deleteValue();
+  }
+}
+
+
+bool Simplifier::Context::equal(const Instruction *I,
+                                const Instruction *J) const {
+  if (I == J)
+    return true;
+  if (!I->isSameOperationAs(J))
+    return false;
+  if (isa<PHINode>(I))
+    return I->isIdenticalTo(J);
+
+  for (unsigned i = 0, n = I->getNumOperands(); i != n; ++i) {
+    Value *OpI = I->getOperand(i), *OpJ = J->getOperand(i);
+    if (OpI == OpJ)
+      continue;
+    auto *InI = dyn_cast<const Instruction>(OpI);
+    auto *InJ = dyn_cast<const Instruction>(OpJ);
+    if (InI && InJ) {
+      if (!equal(InI, InJ))
+        return false;
+    } else if (InI != InJ || !InI)
+      return false;
+  }
+  return true;
+}
+
+
+Value *Simplifier::Context::find(Value *Tree, Value *Sub) const {
+  Instruction *SubI = dyn_cast<Instruction>(Sub);
+  WorkListType Q;
+  Q.push_back(Tree);
+
+  while (!Q.empty()) {
+    Value *V = Q.pop_front_val();
+    if (V == Sub)
+      return V;
+    Instruction *U = dyn_cast<Instruction>(V);
+    if (!U || U->getParent())
+      continue;
+    if (SubI && equal(SubI, U))
+      return U;
+    assert(!isa<PHINode>(U));
+    for (Value *Op : U->operands())
+      Q.push_back(Op);
+  }
+  return nullptr;
+}
+
+
+void Simplifier::Context::link(Instruction *I, BasicBlock *B,
+      BasicBlock::iterator At) {
+  if (I->getParent())
+    return;
+
+  for (Value *Op : I->operands()) {
+    if (Instruction *OpI = dyn_cast<Instruction>(Op))
+      link(OpI, B, At);
+  }
+
+  B->getInstList().insert(At, I);
+}
+
+
+Value *Simplifier::Context::materialize(BasicBlock *B,
+      BasicBlock::iterator At) {
+  if (Instruction *RootI = dyn_cast<Instruction>(Root))
+    link(RootI, B, At);
+  return Root;
+}
+
+
+Value *Simplifier::simplify(Context &C) {
+  WorkListType Q;
+  Q.push_back(C.Root);
+  unsigned Count = 0;
+  const unsigned Limit = SimplifyLimit;
+
+  while (!Q.empty()) {
+    if (Count++ >= Limit)
+      break;
+    Instruction *U = dyn_cast<Instruction>(Q.pop_front_val());
+    if (!U || U->getParent() || !C.Used.count(U))
+      continue;
+    bool Changed = false;
+    for (Rule &R : Rules) {
+      Value *W = R(U, C.Ctx);
+      if (!W)
+        continue;
+      Changed = true;
+      C.record(W);
+      C.replace(U, W);
+      Q.push_back(C.Root);
+      break;
+    }
+    if (!Changed) {
+      for (Value *Op : U->operands())
+        Q.push_back(Op);
+    }
+  }
+  return Count < Limit ? C.Root : nullptr;
+}
+
+
+//===----------------------------------------------------------------------===//
+//
+//          Implementation of PolynomialMultiplyRecognize
+//
+//===----------------------------------------------------------------------===//
+
+namespace {
+  class PolynomialMultiplyRecognize {
+  public:
+    explicit PolynomialMultiplyRecognize(Loop *loop, const DataLayout &dl,
+        const DominatorTree &dt, const TargetLibraryInfo &tli,
+        ScalarEvolution &se)
+      : CurLoop(loop), DL(dl), DT(dt), TLI(tli), SE(se) {}
+
+    bool recognize();
+  private:
+    typedef SetVector<Value*> ValueSeq;
+
+    IntegerType *getPmpyType() const {
+      LLVMContext &Ctx = CurLoop->getHeader()->getParent()->getContext();
+      return IntegerType::get(Ctx, 32);
+    }
+    bool isPromotableTo(Value *V, IntegerType *Ty);
+    void promoteTo(Instruction *In, IntegerType *DestTy, BasicBlock *LoopB);
+    bool promoteTypes(BasicBlock *LoopB, BasicBlock *ExitB);
+
+    Value *getCountIV(BasicBlock *BB);
+    bool findCycle(Value *Out, Value *In, ValueSeq &Cycle);
+    void classifyCycle(Instruction *DivI, ValueSeq &Cycle, ValueSeq &Early,
+          ValueSeq &Late);
+    bool classifyInst(Instruction *UseI, ValueSeq &Early, ValueSeq &Late);
+    bool commutesWithShift(Instruction *I);
+    bool highBitsAreZero(Value *V, unsigned IterCount);
+    bool keepsHighBitsZero(Value *V, unsigned IterCount);
+    bool isOperandShifted(Instruction *I, Value *Op);
+    bool convertShiftsToLeft(BasicBlock *LoopB, BasicBlock *ExitB,
+          unsigned IterCount);
+    void cleanupLoopBody(BasicBlock *LoopB);
+
+    struct ParsedValues {
+      ParsedValues() : M(nullptr), P(nullptr), Q(nullptr), R(nullptr),
+          X(nullptr), Res(nullptr), IterCount(0), Left(false), Inv(false) {}
+      Value *M, *P, *Q, *R, *X;
+      Instruction *Res;
+      unsigned IterCount;
+      bool Left, Inv;
+    };
+
+    bool matchLeftShift(SelectInst *SelI, Value *CIV, ParsedValues &PV);
+    bool matchRightShift(SelectInst *SelI, ParsedValues &PV);
+    bool scanSelect(SelectInst *SI, BasicBlock *LoopB, BasicBlock *PrehB,
+          Value *CIV, ParsedValues &PV, bool PreScan);
+    unsigned getInverseMxN(unsigned QP);
+    Value *generate(BasicBlock::iterator At, ParsedValues &PV);
+
+    void setupSimplifier();
+
+    Simplifier Simp;
+    Loop *CurLoop;
+    const DataLayout &DL;
+    const DominatorTree &DT;
+    const TargetLibraryInfo &TLI;
+    ScalarEvolution &SE;
+  };
+}
+
+
+Value *PolynomialMultiplyRecognize::getCountIV(BasicBlock *BB) {
+  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+  if (std::distance(PI, PE) != 2)
+    return nullptr;
+  BasicBlock *PB = (*PI == BB) ? *std::next(PI) : *PI;
+
+  for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
+    auto *PN = cast<PHINode>(I);
+    Value *InitV = PN->getIncomingValueForBlock(PB);
+    if (!isa<ConstantInt>(InitV) || !cast<ConstantInt>(InitV)->isZero())
+      continue;
+    Value *IterV = PN->getIncomingValueForBlock(BB);
+    if (!isa<BinaryOperator>(IterV))
+      continue;
+    auto *BO = dyn_cast<BinaryOperator>(IterV);
+    if (BO->getOpcode() != Instruction::Add)
+      continue;
+    Value *IncV = nullptr;
+    if (BO->getOperand(0) == PN)
+      IncV = BO->getOperand(1);
+    else if (BO->getOperand(1) == PN)
+      IncV = BO->getOperand(0);
+    if (IncV == nullptr)
+      continue;
+
+    if (auto *T = dyn_cast<ConstantInt>(IncV))
+      if (T->getZExtValue() == 1)
+        return PN;
+  }
+  return nullptr;
+}
+
+
+static void replaceAllUsesOfWithIn(Value *I, Value *J, BasicBlock *BB) {
+  for (auto UI = I->user_begin(), UE = I->user_end(); UI != UE;) {
+    Use &TheUse = UI.getUse();
+    ++UI;
+    if (auto *II = dyn_cast<Instruction>(TheUse.getUser()))
+      if (BB == II->getParent())
+        II->replaceUsesOfWith(I, J);
+  }
+}
+
+
+bool PolynomialMultiplyRecognize::matchLeftShift(SelectInst *SelI,
+      Value *CIV, ParsedValues &PV) {
+  // Match the following:
+  //   select (X & (1 << i)) != 0 ? R ^ (Q << i) : R
+  //   select (X & (1 << i)) == 0 ? R : R ^ (Q << i)
+  // The condition may also check for equality with the masked value, i.e
+  //   select (X & (1 << i)) == (1 << i) ? R ^ (Q << i) : R
+  //   select (X & (1 << i)) != (1 << i) ? R : R ^ (Q << i);
+
+  Value *CondV = SelI->getCondition();
+  Value *TrueV = SelI->getTrueValue();
+  Value *FalseV = SelI->getFalseValue();
+
+  using namespace PatternMatch;
+
+  CmpInst::Predicate P;
+  Value *A = nullptr, *B = nullptr, *C = nullptr;
+
+  if (!match(CondV, m_ICmp(P, m_And(m_Value(A), m_Value(B)), m_Value(C))) &&
+      !match(CondV, m_ICmp(P, m_Value(C), m_And(m_Value(A), m_Value(B)))))
+    return false;
+  if (P != CmpInst::ICMP_EQ && P != CmpInst::ICMP_NE)
+    return false;
+  // Matched: select (A & B) == C ? ... : ...
+  //          select (A & B) != C ? ... : ...
+
+  Value *X = nullptr, *Sh1 = nullptr;
+  // Check (A & B) for (X & (1 << i)):
+  if (match(A, m_Shl(m_One(), m_Specific(CIV)))) {
+    Sh1 = A;
+    X = B;
+  } else if (match(B, m_Shl(m_One(), m_Specific(CIV)))) {
+    Sh1 = B;
+    X = A;
+  } else {
+    // TODO: Could also check for an induction variable containing single
+    // bit shifted left by 1 in each iteration.
+    return false;
+  }
+
+  bool TrueIfZero;
+
+  // Check C against the possible values for comparison: 0 and (1 << i):
+  if (match(C, m_Zero()))
+    TrueIfZero = (P == CmpInst::ICMP_EQ);
+  else if (C == Sh1)
+    TrueIfZero = (P == CmpInst::ICMP_NE);
+  else
+    return false;
+
+  // So far, matched:
+  //   select (X & (1 << i)) ? ... : ...
+  // including variations of the check against zero/non-zero value.
+
+  Value *ShouldSameV = nullptr, *ShouldXoredV = nullptr;
+  if (TrueIfZero) {
+    ShouldSameV = TrueV;
+    ShouldXoredV = FalseV;
+  } else {
+    ShouldSameV = FalseV;
+    ShouldXoredV = TrueV;
+  }
+
+  Value *Q = nullptr, *R = nullptr, *Y = nullptr, *Z = nullptr;
+  Value *T = nullptr;
+  if (match(ShouldXoredV, m_Xor(m_Value(Y), m_Value(Z)))) {
+    // Matched: select +++ ? ... : Y ^ Z
+    //          select +++ ? Y ^ Z : ...
+    // where +++ denotes previously checked matches.
+    if (ShouldSameV == Y)
+      T = Z;
+    else if (ShouldSameV == Z)
+      T = Y;
+    else
+      return false;
+    R = ShouldSameV;
+    // Matched: select +++ ? R : R ^ T
+    //          select +++ ? R ^ T : R
+    // depending on TrueIfZero.
+
+  } else if (match(ShouldSameV, m_Zero())) {
+    // Matched: select +++ ? 0 : ...
+    //          select +++ ? ... : 0
+    if (!SelI->hasOneUse())
+      return false;
+    T = ShouldXoredV;
+    // Matched: select +++ ? 0 : T
+    //          select +++ ? T : 0
+
+    Value *U = *SelI->user_begin();
+    if (!match(U, m_Xor(m_Specific(SelI), m_Value(R))) &&
+        !match(U, m_Xor(m_Value(R), m_Specific(SelI))))
+      return false;
+    // Matched: xor (select +++ ? 0 : T), R
+    //          xor (select +++ ? T : 0), R
+  } else
+    return false;
+
+  // The xor input value T is isolated into its own match so that it could
+  // be checked against an induction variable containing a shifted bit
+  // (todo).
+  // For now, check against (Q << i).
+  if (!match(T, m_Shl(m_Value(Q), m_Specific(CIV))) &&
+      !match(T, m_Shl(m_ZExt(m_Value(Q)), m_ZExt(m_Specific(CIV)))))
+    return false;
+  // Matched: select +++ ? R : R ^ (Q << i)
+  //          select +++ ? R ^ (Q << i) : R
+
+  PV.X = X;
+  PV.Q = Q;
+  PV.R = R;
+  PV.Left = true;
+  return true;
+}
+
+
+bool PolynomialMultiplyRecognize::matchRightShift(SelectInst *SelI,
+      ParsedValues &PV) {
+  // Match the following:
+  //   select (X & 1) != 0 ? (R >> 1) ^ Q : (R >> 1)
+  //   select (X & 1) == 0 ? (R >> 1) : (R >> 1) ^ Q
+  // The condition may also check for equality with the masked value, i.e
+  //   select (X & 1) == 1 ? (R >> 1) ^ Q : (R >> 1)
+  //   select (X & 1) != 1 ? (R >> 1) : (R >> 1) ^ Q
+
+  Value *CondV = SelI->getCondition();
+  Value *TrueV = SelI->getTrueValue();
+  Value *FalseV = SelI->getFalseValue();
+
+  using namespace PatternMatch;
+
+  Value *C = nullptr;
+  CmpInst::Predicate P;
+  bool TrueIfZero;
+
+  if (match(CondV, m_ICmp(P, m_Value(C), m_Zero())) ||
+      match(CondV, m_ICmp(P, m_Zero(), m_Value(C)))) {
+    if (P != CmpInst::ICMP_EQ && P != CmpInst::ICMP_NE)
+      return false;
+    // Matched: select C == 0 ? ... : ...
+    //          select C != 0 ? ... : ...
+    TrueIfZero = (P == CmpInst::ICMP_EQ);
+  } else if (match(CondV, m_ICmp(P, m_Value(C), m_One())) ||
+             match(CondV, m_ICmp(P, m_One(), m_Value(C)))) {
+    if (P != CmpInst::ICMP_EQ && P != CmpInst::ICMP_NE)
+      return false;
+    // Matched: select C == 1 ? ... : ...
+    //          select C != 1 ? ... : ...
+    TrueIfZero = (P == CmpInst::ICMP_NE);
+  } else
+    return false;
+
+  Value *X = nullptr;
+  if (!match(C, m_And(m_Value(X), m_One())) &&
+      !match(C, m_And(m_One(), m_Value(X))))
+    return false;
+  // Matched: select (X & 1) == +++ ? ... : ...
+  //          select (X & 1) != +++ ? ... : ...
+
+  Value *R = nullptr, *Q = nullptr;
+  if (TrueIfZero) {
+    // The select's condition is true if the tested bit is 0.
+    // TrueV must be the shift, FalseV must be the xor.
+    if (!match(TrueV, m_LShr(m_Value(R), m_One())))
+      return false;
+    // Matched: select +++ ? (R >> 1) : ...
+    if (!match(FalseV, m_Xor(m_Specific(TrueV), m_Value(Q))) &&
+        !match(FalseV, m_Xor(m_Value(Q), m_Specific(TrueV))))
+      return false;
+    // Matched: select +++ ? (R >> 1) : (R >> 1) ^ Q
+    // with commuting ^.
+  } else {
+    // The select's condition is true if the tested bit is 1.
+    // TrueV must be the xor, FalseV must be the shift.
+    if (!match(FalseV, m_LShr(m_Value(R), m_One())))
+      return false;
+    // Matched: select +++ ? ... : (R >> 1)
+    if (!match(TrueV, m_Xor(m_Specific(FalseV), m_Value(Q))) &&
+        !match(TrueV, m_Xor(m_Value(Q), m_Specific(FalseV))))
+      return false;
+    // Matched: select +++ ? (R >> 1) ^ Q : (R >> 1)
+    // with commuting ^.
+  }
+
+  PV.X = X;
+  PV.Q = Q;
+  PV.R = R;
+  PV.Left = false;
+  return true;
+}
+
+
+bool PolynomialMultiplyRecognize::scanSelect(SelectInst *SelI,
+      BasicBlock *LoopB, BasicBlock *PrehB, Value *CIV, ParsedValues &PV,
+      bool PreScan) {
+  using namespace PatternMatch;
+  // The basic pattern for R = P.Q is:
+  // for i = 0..31
+  //   R = phi (0, R')
+  //   if (P & (1 << i))        ; test-bit(P, i)
+  //     R' = R ^ (Q << i)
+  //
+  // Similarly, the basic pattern for R = (P/Q).Q - P
+  // for i = 0..31
+  //   R = phi(P, R')
+  //   if (R & (1 << i))
+  //     R' = R ^ (Q << i)
+
+  // There exist idioms, where instead of Q being shifted left, P is shifted
+  // right. This produces a result that is shifted right by 32 bits (the
+  // non-shifted result is 64-bit).
+  //
+  // For R = P.Q, this would be:
+  // for i = 0..31
+  //   R = phi (0, R')
+  //   if ((P >> i) & 1)
+  //     R' = (R >> 1) ^ Q      ; R is cycled through the loop, so it must
+  //   else                     ; be shifted by 1, not i.
+  //     R' = R >> 1
+  //
+  // And for the inverse:
+  // for i = 0..31
+  //   R = phi (P, R')
+  //   if (R & 1)
+  //     R' = (R >> 1) ^ Q
+  //   else
+  //     R' = R >> 1
+
+  // The left-shifting idioms share the same pattern:
+  //   select (X & (1 << i)) ? R ^ (Q << i) : R
+  // Similarly for right-shifting idioms:
+  //   select (X & 1) ? (R >> 1) ^ Q
+
+  if (matchLeftShift(SelI, CIV, PV)) {
+    // If this is a pre-scan, getting this far is sufficient.
+    if (PreScan)
+      return true;
+
+    // Need to make sure that the SelI goes back into R.
+    auto *RPhi = dyn_cast<PHINode>(PV.R);
+    if (!RPhi)
+      return false;
+    if (SelI != RPhi->getIncomingValueForBlock(LoopB))
+      return false;
+    PV.Res = SelI;
+
+    // If X is loop invariant, it must be the input polynomial, and the
+    // idiom is the basic polynomial multiply.
+    if (CurLoop->isLoopInvariant(PV.X)) {
+      PV.P = PV.X;
+      PV.Inv = false;
+    } else {
+      // X is not loop invariant. If X == R, this is the inverse pmpy.
+      // Otherwise, check for an xor with an invariant value. If the
+      // variable argument to the xor is R, then this is still a valid
+      // inverse pmpy.
+      PV.Inv = true;
+      if (PV.X != PV.R) {
+        Value *Var = nullptr, *Inv = nullptr, *X1 = nullptr, *X2 = nullptr;
+        if (!match(PV.X, m_Xor(m_Value(X1), m_Value(X2))))
+          return false;
+        auto *I1 = dyn_cast<Instruction>(X1);
+        auto *I2 = dyn_cast<Instruction>(X2);
+        if (!I1 || I1->getParent() != LoopB) {
+          Var = X2;
+          Inv = X1;
+        } else if (!I2 || I2->getParent() != LoopB) {
+          Var = X1;
+          Inv = X2;
+        } else
+          return false;
+        if (Var != PV.R)
+          return false;
+        PV.M = Inv;
+      }
+      // The input polynomial P still needs to be determined. It will be
+      // the entry value of R.
+      Value *EntryP = RPhi->getIncomingValueForBlock(PrehB);
+      PV.P = EntryP;
+    }
+
+    return true;
+  }
+
+  if (matchRightShift(SelI, PV)) {
+    // If this is an inverse pattern, the Q polynomial must be known at
+    // compile time.
+    if (PV.Inv && !isa<ConstantInt>(PV.Q))
+      return false;
+    if (PreScan)
+      return true;
+    // There is no exact matching of right-shift pmpy.
+    return false;
+  }
+
+  return false;
+}
+
+
+bool PolynomialMultiplyRecognize::isPromotableTo(Value *Val,
+      IntegerType *DestTy) {
+  IntegerType *T = dyn_cast<IntegerType>(Val->getType());
+  if (!T || T->getBitWidth() > DestTy->getBitWidth())
+    return false;
+  if (T->getBitWidth() == DestTy->getBitWidth())
+    return true;
+  // Non-instructions are promotable. The reason why an instruction may not
+  // be promotable is that it may produce a different result if its operands
+  // and the result are promoted, for example, it may produce more non-zero
+  // bits. While it would still be possible to represent the proper result
+  // in a wider type, it may require adding additional instructions (which
+  // we don't want to do).
+  Instruction *In = dyn_cast<Instruction>(Val);
+  if (!In)
+    return true;
+  // The bitwidth of the source type is smaller than the destination.
+  // Check if the individual operation can be promoted.
+  switch (In->getOpcode()) {
+    case Instruction::PHI:
+    case Instruction::ZExt:
+    case Instruction::And:
+    case Instruction::Or:
+    case Instruction::Xor:
+    case Instruction::LShr: // Shift right is ok.
+    case Instruction::Select:
+      return true;
+    case Instruction::ICmp:
+      if (CmpInst *CI = cast<CmpInst>(In))
+        return CI->isEquality() || CI->isUnsigned();
+      llvm_unreachable("Cast failed unexpectedly");
+    case Instruction::Add:
+      return In->hasNoSignedWrap() && In->hasNoUnsignedWrap();
+  }
+  return false;
+}
+
+
+void PolynomialMultiplyRecognize::promoteTo(Instruction *In,
+      IntegerType *DestTy, BasicBlock *LoopB) {
+  // Leave boolean values alone.
+  if (!In->getType()->isIntegerTy(1))
+    In->mutateType(DestTy);
+  unsigned DestBW = DestTy->getBitWidth();
+
+  // Handle PHIs.
+  if (PHINode *P = dyn_cast<PHINode>(In)) {
+    unsigned N = P->getNumIncomingValues();
+    for (unsigned i = 0; i != N; ++i) {
+      BasicBlock *InB = P->getIncomingBlock(i);
+      if (InB == LoopB)
+        continue;
+      Value *InV = P->getIncomingValue(i);
+      IntegerType *Ty = cast<IntegerType>(InV->getType());
+      // Do not promote values in PHI nodes of type i1.
+      if (Ty != P->getType()) {
+        // If the value type does not match the PHI type, the PHI type
+        // must have been promoted.
+        assert(Ty->getBitWidth() < DestBW);
+        InV = IRBuilder<>(InB->getTerminator()).CreateZExt(InV, DestTy);
+        P->setIncomingValue(i, InV);
+      }
+    }
+  } else if (ZExtInst *Z = dyn_cast<ZExtInst>(In)) {
+    Value *Op = Z->getOperand(0);
+    if (Op->getType() == Z->getType())
+      Z->replaceAllUsesWith(Op);
+    Z->eraseFromParent();
+    return;
+  }
+
+  // Promote immediates.
+  for (unsigned i = 0, n = In->getNumOperands(); i != n; ++i) {
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(In->getOperand(i)))
+      if (CI->getType()->getBitWidth() < DestBW)
+        In->setOperand(i, ConstantInt::get(DestTy, CI->getZExtValue()));
+  }
+}
+
+
+bool PolynomialMultiplyRecognize::promoteTypes(BasicBlock *LoopB,
+      BasicBlock *ExitB) {
+  assert(LoopB);
+  // Skip loops where the exit block has more than one predecessor. The values
+  // coming from the loop block will be promoted to another type, and so the
+  // values coming into the exit block from other predecessors would also have
+  // to be promoted.
+  if (!ExitB || (ExitB->getSinglePredecessor() != LoopB))
+    return false;
+  IntegerType *DestTy = getPmpyType();
+  // Check if the exit values have types that are no wider than the type
+  // that we want to promote to.
+  unsigned DestBW = DestTy->getBitWidth();
+  for (Instruction &In : *ExitB) {
+    PHINode *P = dyn_cast<PHINode>(&In);
+    if (!P)
+      break;
+    if (P->getNumIncomingValues() != 1)
+      return false;
+    assert(P->getIncomingBlock(0) == LoopB);
+    IntegerType *T = dyn_cast<IntegerType>(P->getType());
+    if (!T || T->getBitWidth() > DestBW)
+      return false;
+  }
+
+  // Check all instructions in the loop.
+  for (Instruction &In : *LoopB)
+    if (!In.isTerminator() && !isPromotableTo(&In, DestTy))
+      return false;
+
+  // Perform the promotion.
+  std::vector<Instruction*> LoopIns;
+  std::transform(LoopB->begin(), LoopB->end(), std::back_inserter(LoopIns),
+                 [](Instruction &In) { return &In; });
+  for (Instruction *In : LoopIns)
+    promoteTo(In, DestTy, LoopB);
+
+  // Fix up the PHI nodes in the exit block.
+  Instruction *EndI = ExitB->getFirstNonPHI();
+  BasicBlock::iterator End = EndI ? EndI->getIterator() : ExitB->end();
+  for (auto I = ExitB->begin(); I != End; ++I) {
+    PHINode *P = dyn_cast<PHINode>(I);
+    if (!P)
+      break;
+    Type *Ty0 = P->getIncomingValue(0)->getType();
+    Type *PTy = P->getType();
+    if (PTy != Ty0) {
+      assert(Ty0 == DestTy);
+      // In order to create the trunc, P must have the promoted type.
+      P->mutateType(Ty0);
+      Value *T = IRBuilder<>(ExitB, End).CreateTrunc(P, PTy);
+      // In order for the RAUW to work, the types of P and T must match.
+      P->mutateType(PTy);
+      P->replaceAllUsesWith(T);
+      // Final update of the P's type.
+      P->mutateType(Ty0);
+      cast<Instruction>(T)->setOperand(0, P);
+    }
+  }
+
+  return true;
+}
+
+
+bool PolynomialMultiplyRecognize::findCycle(Value *Out, Value *In,
+      ValueSeq &Cycle) {
+  // Out = ..., In, ...
+  if (Out == In)
+    return true;
+
+  auto *BB = cast<Instruction>(Out)->getParent();
+  bool HadPhi = false;
+
+  for (auto U : Out->users()) {
+    auto *I = dyn_cast<Instruction>(&*U);
+    if (I == nullptr || I->getParent() != BB)
+      continue;
+    // Make sure that there are no multi-iteration cycles, e.g.
+    //   p1 = phi(p2)
+    //   p2 = phi(p1)
+    // The cycle p1->p2->p1 would span two loop iterations.
+    // Check that there is only one phi in the cycle.
+    bool IsPhi = isa<PHINode>(I);
+    if (IsPhi && HadPhi)
+      return false;
+    HadPhi |= IsPhi;
+    if (Cycle.count(I))
+      return false;
+    Cycle.insert(I);
+    if (findCycle(I, In, Cycle))
+      break;
+    Cycle.remove(I);
+  }
+  return !Cycle.empty();
+}
+
+
+void PolynomialMultiplyRecognize::classifyCycle(Instruction *DivI,
+      ValueSeq &Cycle, ValueSeq &Early, ValueSeq &Late) {
+  // All the values in the cycle that are between the phi node and the
+  // divider instruction will be classified as "early", all other values
+  // will be "late".
+
+  bool IsE = true;
+  unsigned I, N = Cycle.size();
+  for (I = 0; I < N; ++I) {
+    Value *V = Cycle[I];
+    if (DivI == V)
+      IsE = false;
+    else if (!isa<PHINode>(V))
+      continue;
+    // Stop if found either.
+    break;
+  }
+  // "I" is the index of either DivI or the phi node, whichever was first.
+  // "E" is "false" or "true" respectively.
+  ValueSeq &First = !IsE ? Early : Late;
+  for (unsigned J = 0; J < I; ++J)
+    First.insert(Cycle[J]);
+
+  ValueSeq &Second = IsE ? Early : Late;
+  Second.insert(Cycle[I]);
+  for (++I; I < N; ++I) {
+    Value *V = Cycle[I];
+    if (DivI == V || isa<PHINode>(V))
+      break;
+    Second.insert(V);
+  }
+
+  for (; I < N; ++I)
+    First.insert(Cycle[I]);
+}
+
+
+bool PolynomialMultiplyRecognize::classifyInst(Instruction *UseI,
+      ValueSeq &Early, ValueSeq &Late) {
+  // Select is an exception, since the condition value does not have to be
+  // classified in the same way as the true/false values. The true/false
+  // values do have to be both early or both late.
+  if (UseI->getOpcode() == Instruction::Select) {
+    Value *TV = UseI->getOperand(1), *FV = UseI->getOperand(2);
+    if (Early.count(TV) || Early.count(FV)) {
+      if (Late.count(TV) || Late.count(FV))
+        return false;
+      Early.insert(UseI);
+    } else if (Late.count(TV) || Late.count(FV)) {
+      if (Early.count(TV) || Early.count(FV))
+        return false;
+      Late.insert(UseI);
+    }
+    return true;
+  }
+
+  // Not sure what would be the example of this, but the code below relies
+  // on having at least one operand.
+  if (UseI->getNumOperands() == 0)
+    return true;
+
+  bool AE = true, AL = true;
+  for (auto &I : UseI->operands()) {
+    if (Early.count(&*I))
+      AL = false;
+    else if (Late.count(&*I))
+      AE = false;
+  }
+  // If the operands appear "all early" and "all late" at the same time,
+  // then it means that none of them are actually classified as either.
+  // This is harmless.
+  if (AE && AL)
+    return true;
+  // Conversely, if they are neither "all early" nor "all late", then
+  // we have a mixture of early and late operands that is not a known
+  // exception.
+  if (!AE && !AL)
+    return false;
+
+  // Check that we have covered the two special cases.
+  assert(AE != AL);
+
+  if (AE)
+    Early.insert(UseI);
+  else
+    Late.insert(UseI);
+  return true;
+}
+
+
+bool PolynomialMultiplyRecognize::commutesWithShift(Instruction *I) {
+  switch (I->getOpcode()) {
+    case Instruction::And:
+    case Instruction::Or:
+    case Instruction::Xor:
+    case Instruction::LShr:
+    case Instruction::Shl:
+    case Instruction::Select:
+    case Instruction::ICmp:
+    case Instruction::PHI:
+      break;
+    default:
+      return false;
+  }
+  return true;
+}
+
+
+bool PolynomialMultiplyRecognize::highBitsAreZero(Value *V,
+      unsigned IterCount) {
+  auto *T = dyn_cast<IntegerType>(V->getType());
+  if (!T)
+    return false;
+
+  KnownBits Known(T->getBitWidth());
+  computeKnownBits(V, Known, DL);
+  return Known.countMinLeadingZeros() >= IterCount;
+}
+
+
+bool PolynomialMultiplyRecognize::keepsHighBitsZero(Value *V,
+      unsigned IterCount) {
+  // Assume that all inputs to the value have the high bits zero.
+  // Check if the value itself preserves the zeros in the high bits.
+  if (auto *C = dyn_cast<ConstantInt>(V))
+    return C->getValue().countLeadingZeros() >= IterCount;
+
+  if (auto *I = dyn_cast<Instruction>(V)) {
+    switch (I->getOpcode()) {
+      case Instruction::And:
+      case Instruction::Or:
+      case Instruction::Xor:
+      case Instruction::LShr:
+      case Instruction::Select:
+      case Instruction::ICmp:
+      case Instruction::PHI:
+      case Instruction::ZExt:
+        return true;
+    }
+  }
+
+  return false;
+}
+
+
+bool PolynomialMultiplyRecognize::isOperandShifted(Instruction *I, Value *Op) {
+  unsigned Opc = I->getOpcode();
+  if (Opc == Instruction::Shl || Opc == Instruction::LShr)
+    return Op != I->getOperand(1);
+  return true;
+}
+
+
+bool PolynomialMultiplyRecognize::convertShiftsToLeft(BasicBlock *LoopB,
+      BasicBlock *ExitB, unsigned IterCount) {
+  Value *CIV = getCountIV(LoopB);
+  if (CIV == nullptr)
+    return false;
+  auto *CIVTy = dyn_cast<IntegerType>(CIV->getType());
+  if (CIVTy == nullptr)
+    return false;
+
+  ValueSeq RShifts;
+  ValueSeq Early, Late, Cycled;
+
+  // Find all value cycles that contain logical right shifts by 1.
+  for (Instruction &I : *LoopB) {
+    using namespace PatternMatch;
+    Value *V = nullptr;
+    if (!match(&I, m_LShr(m_Value(V), m_One())))
+      continue;
+    ValueSeq C;
+    if (!findCycle(&I, V, C))
+      continue;
+
+    // Found a cycle.
+    C.insert(&I);
+    classifyCycle(&I, C, Early, Late);
+    Cycled.insert(C.begin(), C.end());
+    RShifts.insert(&I);
+  }
+
+  // Find the set of all values affected by the shift cycles, i.e. all
+  // cycled values, and (recursively) all their users.
+  ValueSeq Users(Cycled.begin(), Cycled.end());
+  for (unsigned i = 0; i < Users.size(); ++i) {
+    Value *V = Users[i];
+    if (!isa<IntegerType>(V->getType()))
+      return false;
+    auto *R = cast<Instruction>(V);
+    // If the instruction does not commute with shifts, the loop cannot
+    // be unshifted.
+    if (!commutesWithShift(R))
+      return false;
+    for (auto I = R->user_begin(), E = R->user_end(); I != E; ++I) {
+      auto *T = cast<Instruction>(*I);
+      // Skip users from outside of the loop. They will be handled later.
+      // Also, skip the right-shifts and phi nodes, since they mix early
+      // and late values.
+      if (T->getParent() != LoopB || RShifts.count(T) || isa<PHINode>(T))
+        continue;
+
+      Users.insert(T);
+      if (!classifyInst(T, Early, Late))
+        return false;
+    }
+  }
+
+  if (Users.size() == 0)
+    return false;
+
+  // Verify that high bits remain zero.
+  ValueSeq Internal(Users.begin(), Users.end());
+  ValueSeq Inputs;
+  for (unsigned i = 0; i < Internal.size(); ++i) {
+    auto *R = dyn_cast<Instruction>(Internal[i]);
+    if (!R)
+      continue;
+    for (Value *Op : R->operands()) {
+      auto *T = dyn_cast<Instruction>(Op);
+      if (T && T->getParent() != LoopB)
+        Inputs.insert(Op);
+      else
+        Internal.insert(Op);
+    }
+  }
+  for (Value *V : Inputs)
+    if (!highBitsAreZero(V, IterCount))
+      return false;
+  for (Value *V : Internal)
+    if (!keepsHighBitsZero(V, IterCount))
+      return false;
+
+  // Finally, the work can be done. Unshift each user.
+  IRBuilder<> IRB(LoopB);
+  std::map<Value*,Value*> ShiftMap;
+  typedef std::map<std::pair<Value*,Type*>,Value*> CastMapType;
+  CastMapType CastMap;
+
+  auto upcast = [] (CastMapType &CM, IRBuilder<> &IRB, Value *V,
+        IntegerType *Ty) -> Value* {
+    auto H = CM.find(std::make_pair(V, Ty));
+    if (H != CM.end())
+      return H->second;
+    Value *CV = IRB.CreateIntCast(V, Ty, false);
+    CM.insert(std::make_pair(std::make_pair(V, Ty), CV));
+    return CV;
+  };
+
+  for (auto I = LoopB->begin(), E = LoopB->end(); I != E; ++I) {
+    if (isa<PHINode>(I) || !Users.count(&*I))
+      continue;
+    using namespace PatternMatch;
+    // Match lshr x, 1.
+    Value *V = nullptr;
+    if (match(&*I, m_LShr(m_Value(V), m_One()))) {
+      replaceAllUsesOfWithIn(&*I, V, LoopB);
+      continue;
+    }
+    // For each non-cycled operand, replace it with the corresponding
+    // value shifted left.
+    for (auto &J : I->operands()) {
+      Value *Op = J.get();
+      if (!isOperandShifted(&*I, Op))
+        continue;
+      if (Users.count(Op))
+        continue;
+      // Skip shifting zeros.
+      if (isa<ConstantInt>(Op) && cast<ConstantInt>(Op)->isZero())
+        continue;
+      // Check if we have already generated a shift for this value.
+      auto F = ShiftMap.find(Op);
+      Value *W = (F != ShiftMap.end()) ? F->second : nullptr;
+      if (W == nullptr) {
+        IRB.SetInsertPoint(&*I);
+        // First, the shift amount will be CIV or CIV+1, depending on
+        // whether the value is early or late. Instead of creating CIV+1,
+        // do a single shift of the value.
+        Value *ShAmt = CIV, *ShVal = Op;
+        auto *VTy = cast<IntegerType>(ShVal->getType());
+        auto *ATy = cast<IntegerType>(ShAmt->getType());
+        if (Late.count(&*I))
+          ShVal = IRB.CreateShl(Op, ConstantInt::get(VTy, 1));
+        // Second, the types of the shifted value and the shift amount
+        // must match.
+        if (VTy != ATy) {
+          if (VTy->getBitWidth() < ATy->getBitWidth())
+            ShVal = upcast(CastMap, IRB, ShVal, ATy);
+          else
+            ShAmt = upcast(CastMap, IRB, ShAmt, VTy);
+        }
+        // Ready to generate the shift and memoize it.
+        W = IRB.CreateShl(ShVal, ShAmt);
+        ShiftMap.insert(std::make_pair(Op, W));
+      }
+      I->replaceUsesOfWith(Op, W);
+    }
+  }
+
+  // Update the users outside of the loop to account for having left
+  // shifts. They would normally be shifted right in the loop, so shift
+  // them right after the loop exit.
+  // Take advantage of the loop-closed SSA form, which has all the post-
+  // loop values in phi nodes.
+  IRB.SetInsertPoint(ExitB, ExitB->getFirstInsertionPt());
+  for (auto P = ExitB->begin(), Q = ExitB->end(); P != Q; ++P) {
+    if (!isa<PHINode>(P))
+      break;
+    auto *PN = cast<PHINode>(P);
+    Value *U = PN->getIncomingValueForBlock(LoopB);
+    if (!Users.count(U))
+      continue;
+    Value *S = IRB.CreateLShr(PN, ConstantInt::get(PN->getType(), IterCount));
+    PN->replaceAllUsesWith(S);
+    // The above RAUW will create
+    //   S = lshr S, IterCount
+    // so we need to fix it back into
+    //   S = lshr PN, IterCount
+    cast<User>(S)->replaceUsesOfWith(S, PN);
+  }
+
+  return true;
+}
+
+
+void PolynomialMultiplyRecognize::cleanupLoopBody(BasicBlock *LoopB) {
+  for (auto &I : *LoopB)
+    if (Value *SV = SimplifyInstruction(&I, {DL, &TLI, &DT}))
+      I.replaceAllUsesWith(SV);
+
+  for (auto I = LoopB->begin(), N = I; I != LoopB->end(); I = N) {
+    N = std::next(I);
+    RecursivelyDeleteTriviallyDeadInstructions(&*I, &TLI);
+  }
+}
+
+
+unsigned PolynomialMultiplyRecognize::getInverseMxN(unsigned QP) {
+  // Arrays of coefficients of Q and the inverse, C.
+  // Q[i] = coefficient at x^i.
+  std::array<char,32> Q, C;
+
+  for (unsigned i = 0; i < 32; ++i) {
+    Q[i] = QP & 1;
+    QP >>= 1;
+  }
+  assert(Q[0] == 1);
+
+  // Find C, such that
+  // (Q[n]*x^n + ... + Q[1]*x + Q[0]) * (C[n]*x^n + ... + C[1]*x + C[0]) = 1
+  //
+  // For it to have a solution, Q[0] must be 1. Since this is Z2[x], the
+  // operations * and + are & and ^ respectively.
+  //
+  // Find C[i] recursively, by comparing i-th coefficient in the product
+  // with 0 (or 1 for i=0).
+  //
+  // C[0] = 1, since C[0] = Q[0], and Q[0] = 1.
+  C[0] = 1;
+  for (unsigned i = 1; i < 32; ++i) {
+    // Solve for C[i] in:
+    //   C[0]Q[i] ^ C[1]Q[i-1] ^ ... ^ C[i-1]Q[1] ^ C[i]Q[0] = 0
+    // This is equivalent to
+    //   C[0]Q[i] ^ C[1]Q[i-1] ^ ... ^ C[i-1]Q[1] ^ C[i] = 0
+    // which is
+    //   C[0]Q[i] ^ C[1]Q[i-1] ^ ... ^ C[i-1]Q[1] = C[i]
+    unsigned T = 0;
+    for (unsigned j = 0; j < i; ++j)
+      T = T ^ (C[j] & Q[i-j]);
+    C[i] = T;
+  }
+
+  unsigned QV = 0;
+  for (unsigned i = 0; i < 32; ++i)
+    if (C[i])
+      QV |= (1 << i);
+
+  return QV;
+}
+
+
+Value *PolynomialMultiplyRecognize::generate(BasicBlock::iterator At,
+      ParsedValues &PV) {
+  IRBuilder<> B(&*At);
+  Module *M = At->getParent()->getParent()->getParent();
+  Value *PMF = Intrinsic::getDeclaration(M, Intrinsic::hexagon_M4_pmpyw);
+
+  Value *P = PV.P, *Q = PV.Q, *P0 = P;
+  unsigned IC = PV.IterCount;
+
+  if (PV.M != nullptr)
+    P0 = P = B.CreateXor(P, PV.M);
+
+  // Create a bit mask to clear the high bits beyond IterCount.
+  auto *BMI = ConstantInt::get(P->getType(), APInt::getLowBitsSet(32, IC));
+
+  if (PV.IterCount != 32)
+    P = B.CreateAnd(P, BMI);
+
+  if (PV.Inv) {
+    auto *QI = dyn_cast<ConstantInt>(PV.Q);
+    assert(QI && QI->getBitWidth() <= 32);
+
+    // Again, clearing bits beyond IterCount.
+    unsigned M = (1 << PV.IterCount) - 1;
+    unsigned Tmp = (QI->getZExtValue() | 1) & M;
+    unsigned QV = getInverseMxN(Tmp) & M;
+    auto *QVI = ConstantInt::get(QI->getType(), QV);
+    P = B.CreateCall(PMF, {P, QVI});
+    P = B.CreateTrunc(P, QI->getType());
+    if (IC != 32)
+      P = B.CreateAnd(P, BMI);
+  }
+
+  Value *R = B.CreateCall(PMF, {P, Q});
+
+  if (PV.M != nullptr)
+    R = B.CreateXor(R, B.CreateIntCast(P0, R->getType(), false));
+
+  return R;
+}
+
+
+void PolynomialMultiplyRecognize::setupSimplifier() {
+  Simp.addRule(
+    // Sink zext past bitwise operations.
+    [](Instruction *I, LLVMContext &Ctx) -> Value* {
+      if (I->getOpcode() != Instruction::ZExt)
+        return nullptr;
+      Instruction *T = dyn_cast<Instruction>(I->getOperand(0));
+      if (!T)
+        return nullptr;
+      switch (T->getOpcode()) {
+        case Instruction::And:
+        case Instruction::Or:
+        case Instruction::Xor:
+          break;
+        default:
+          return nullptr;
+      }
+      IRBuilder<> B(Ctx);
+      return B.CreateBinOp(cast<BinaryOperator>(T)->getOpcode(),
+                           B.CreateZExt(T->getOperand(0), I->getType()),
+                           B.CreateZExt(T->getOperand(1), I->getType()));
+    });
+  Simp.addRule(
+    // (xor (and x a) (and y a)) -> (and (xor x y) a)
+    [](Instruction *I, LLVMContext &Ctx) -> Value* {
+      if (I->getOpcode() != Instruction::Xor)
+        return nullptr;
+      Instruction *And0 = dyn_cast<Instruction>(I->getOperand(0));
+      Instruction *And1 = dyn_cast<Instruction>(I->getOperand(1));
+      if (!And0 || !And1)
+        return nullptr;
+      if (And0->getOpcode() != Instruction::And ||
+          And1->getOpcode() != Instruction::And)
+        return nullptr;
+      if (And0->getOperand(1) != And1->getOperand(1))
+        return nullptr;
+      IRBuilder<> B(Ctx);
+      return B.CreateAnd(B.CreateXor(And0->getOperand(0), And1->getOperand(0)),
+                         And0->getOperand(1));
+    });
+  Simp.addRule(
+    // (Op (select c x y) z) -> (select c (Op x z) (Op y z))
+    // (Op x (select c y z)) -> (select c (Op x y) (Op x z))
+    [](Instruction *I, LLVMContext &Ctx) -> Value* {
+      BinaryOperator *BO = dyn_cast<BinaryOperator>(I);
+      if (!BO)
+        return nullptr;
+      Instruction::BinaryOps Op = BO->getOpcode();
+      if (SelectInst *Sel = dyn_cast<SelectInst>(BO->getOperand(0))) {
+        IRBuilder<> B(Ctx);
+        Value *X = Sel->getTrueValue(), *Y = Sel->getFalseValue();
+        Value *Z = BO->getOperand(1);
+        return B.CreateSelect(Sel->getCondition(),
+                              B.CreateBinOp(Op, X, Z),
+                              B.CreateBinOp(Op, Y, Z));
+      }
+      if (SelectInst *Sel = dyn_cast<SelectInst>(BO->getOperand(1))) {
+        IRBuilder<> B(Ctx);
+        Value *X = BO->getOperand(0);
+        Value *Y = Sel->getTrueValue(), *Z = Sel->getFalseValue();
+        return B.CreateSelect(Sel->getCondition(),
+                              B.CreateBinOp(Op, X, Y),
+                              B.CreateBinOp(Op, X, Z));
+      }
+      return nullptr;
+    });
+  Simp.addRule(
+    // (select c (select c x y) z) -> (select c x z)
+    // (select c x (select c y z)) -> (select c x z)
+    [](Instruction *I, LLVMContext &Ctx) -> Value* {
+      SelectInst *Sel = dyn_cast<SelectInst>(I);
+      if (!Sel)
+        return nullptr;
+      IRBuilder<> B(Ctx);
+      Value *C = Sel->getCondition();
+      if (SelectInst *Sel0 = dyn_cast<SelectInst>(Sel->getTrueValue())) {
+        if (Sel0->getCondition() == C)
+          return B.CreateSelect(C, Sel0->getTrueValue(), Sel->getFalseValue());
+      }
+      if (SelectInst *Sel1 = dyn_cast<SelectInst>(Sel->getFalseValue())) {
+        if (Sel1->getCondition() == C)
+          return B.CreateSelect(C, Sel->getTrueValue(), Sel1->getFalseValue());
+      }
+      return nullptr;
+    });
+  Simp.addRule(
+    // (or (lshr x 1) 0x800.0) -> (xor (lshr x 1) 0x800.0)
+    [](Instruction *I, LLVMContext &Ctx) -> Value* {
+      if (I->getOpcode() != Instruction::Or)
+        return nullptr;
+      Instruction *LShr = dyn_cast<Instruction>(I->getOperand(0));
+      if (!LShr || LShr->getOpcode() != Instruction::LShr)
+        return nullptr;
+      ConstantInt *One = dyn_cast<ConstantInt>(LShr->getOperand(1));
+      if (!One || One->getZExtValue() != 1)
+        return nullptr;
+      ConstantInt *Msb = dyn_cast<ConstantInt>(I->getOperand(1));
+      if (!Msb || Msb->getZExtValue() != Msb->getType()->getSignBit())
+        return nullptr;
+      return IRBuilder<>(Ctx).CreateXor(LShr, Msb);
+    });
+  Simp.addRule(
+    // (lshr (BitOp x y) c) -> (BitOp (lshr x c) (lshr y c))
+    [](Instruction *I, LLVMContext &Ctx) -> Value* {
+      if (I->getOpcode() != Instruction::LShr)
+        return nullptr;
+      BinaryOperator *BitOp = dyn_cast<BinaryOperator>(I->getOperand(0));
+      if (!BitOp)
+        return nullptr;
+      switch (BitOp->getOpcode()) {
+        case Instruction::And:
+        case Instruction::Or:
+        case Instruction::Xor:
+          break;
+        default:
+          return nullptr;
+      }
+      IRBuilder<> B(Ctx);
+      Value *S = I->getOperand(1);
+      return B.CreateBinOp(BitOp->getOpcode(),
+                B.CreateLShr(BitOp->getOperand(0), S),
+                B.CreateLShr(BitOp->getOperand(1), S));
+    });
+  Simp.addRule(
+    // (BitOp1 (BitOp2 x a) b) -> (BitOp2 x (BitOp1 a b))
+    [](Instruction *I, LLVMContext &Ctx) -> Value* {
+      auto IsBitOp = [](unsigned Op) -> bool {
+        switch (Op) {
+          case Instruction::And:
+          case Instruction::Or:
+          case Instruction::Xor:
+            return true;
+        }
+        return false;
+      };
+      BinaryOperator *BitOp1 = dyn_cast<BinaryOperator>(I);
+      if (!BitOp1 || !IsBitOp(BitOp1->getOpcode()))
+        return nullptr;
+      BinaryOperator *BitOp2 = dyn_cast<BinaryOperator>(BitOp1->getOperand(0));
+      if (!BitOp2 || !IsBitOp(BitOp2->getOpcode()))
+        return nullptr;
+      ConstantInt *CA = dyn_cast<ConstantInt>(BitOp2->getOperand(1));
+      ConstantInt *CB = dyn_cast<ConstantInt>(BitOp1->getOperand(1));
+      if (!CA || !CB)
+        return nullptr;
+      IRBuilder<> B(Ctx);
+      Value *X = BitOp2->getOperand(0);
+      return B.CreateBinOp(BitOp2->getOpcode(), X,
+                B.CreateBinOp(BitOp1->getOpcode(), CA, CB));
+    });
+}
+
+
+bool PolynomialMultiplyRecognize::recognize() {
+  DEBUG(dbgs() << "Starting PolynomialMultiplyRecognize on loop\n"
+               << *CurLoop << '\n');
+  // Restrictions:
+  // - The loop must consist of a single block.
+  // - The iteration count must be known at compile-time.
+  // - The loop must have an induction variable starting from 0, and
+  //   incremented in each iteration of the loop.
+  BasicBlock *LoopB = CurLoop->getHeader();
+  DEBUG(dbgs() << "Loop header:\n" << *LoopB);
+
+  if (LoopB != CurLoop->getLoopLatch())
+    return false;
+  BasicBlock *ExitB = CurLoop->getExitBlock();
+  if (ExitB == nullptr)
+    return false;
+  BasicBlock *EntryB = CurLoop->getLoopPreheader();
+  if (EntryB == nullptr)
+    return false;
+
+  unsigned IterCount = 0;
+  const SCEV *CT = SE.getBackedgeTakenCount(CurLoop);
+  if (isa<SCEVCouldNotCompute>(CT))
+    return false;
+  if (auto *CV = dyn_cast<SCEVConstant>(CT))
+    IterCount = CV->getValue()->getZExtValue() + 1;
+
+  Value *CIV = getCountIV(LoopB);
+  ParsedValues PV;
+  PV.IterCount = IterCount;
+  DEBUG(dbgs() << "Loop IV: " << *CIV << "\nIterCount: " << IterCount << '\n');
+
+  setupSimplifier();
+
+  // Perform a preliminary scan of select instructions to see if any of them
+  // looks like a generator of the polynomial multiply steps. Assume that a
+  // loop can only contain a single transformable operation, so stop the
+  // traversal after the first reasonable candidate was found.
+  // XXX: Currently this approach can modify the loop before being 100% sure
+  // that the transformation can be carried out.
+  bool FoundPreScan = false;
+  for (Instruction &In : *LoopB) {
+    SelectInst *SI = dyn_cast<SelectInst>(&In);
+    if (!SI)
+      continue;
+
+    Simplifier::Context C(SI);
+    Value *T = Simp.simplify(C);
+    SelectInst *SelI = (T && isa<SelectInst>(T)) ? cast<SelectInst>(T) : SI;
+    DEBUG(dbgs() << "scanSelect(pre-scan): " << PE(C, SelI) << '\n');
+    if (scanSelect(SelI, LoopB, EntryB, CIV, PV, true)) {
+      FoundPreScan = true;
+      if (SelI != SI) {
+        Value *NewSel = C.materialize(LoopB, SI->getIterator());
+        SI->replaceAllUsesWith(NewSel);
+        RecursivelyDeleteTriviallyDeadInstructions(SI, &TLI);
+      }
+      break;
+    }
+  }
+
+  if (!FoundPreScan) {
+    DEBUG(dbgs() << "Have not found candidates for pmpy\n");
+    return false;
+  }
+
+  if (!PV.Left) {
+    // The right shift version actually only returns the higher bits of
+    // the result (each iteration discards the LSB). If we want to convert it
+    // to a left-shifting loop, the working data type must be at least as
+    // wide as the target's pmpy instruction.
+    if (!promoteTypes(LoopB, ExitB))
+      return false;
+    if (!convertShiftsToLeft(LoopB, ExitB, IterCount))
+      return false;
+    cleanupLoopBody(LoopB);
+  }
+
+  // Scan the loop again, find the generating select instruction.
+  bool FoundScan = false;
+  for (Instruction &In : *LoopB) {
+    SelectInst *SelI = dyn_cast<SelectInst>(&In);
+    if (!SelI)
+      continue;
+    DEBUG(dbgs() << "scanSelect: " << *SelI << '\n');
+    FoundScan = scanSelect(SelI, LoopB, EntryB, CIV, PV, false);
+    if (FoundScan)
+      break;
+  }
+  assert(FoundScan);
+
+  DEBUG({
+    StringRef PP = (PV.M ? "(P+M)" : "P");
+    if (!PV.Inv)
+      dbgs() << "Found pmpy idiom: R = " << PP << ".Q\n";
+    else
+      dbgs() << "Found inverse pmpy idiom: R = (" << PP << "/Q).Q) + "
+             << PP << "\n";
+    dbgs() << "  Res:" << *PV.Res << "\n  P:" << *PV.P << "\n";
+    if (PV.M)
+      dbgs() << "  M:" << *PV.M << "\n";
+    dbgs() << "  Q:" << *PV.Q << "\n";
+    dbgs() << "  Iteration count:" << PV.IterCount << "\n";
+  });
+
+  BasicBlock::iterator At(EntryB->getTerminator());
+  Value *PM = generate(At, PV);
+  if (PM == nullptr)
+    return false;
+
+  if (PM->getType() != PV.Res->getType())
+    PM = IRBuilder<>(&*At).CreateIntCast(PM, PV.Res->getType(), false);
+
+  PV.Res->replaceAllUsesWith(PM);
+  PV.Res->eraseFromParent();
+  return true;
+}
+
+
+unsigned HexagonLoopIdiomRecognize::getStoreSizeInBytes(StoreInst *SI) {
+  uint64_t SizeInBits = DL->getTypeSizeInBits(SI->getValueOperand()->getType());
+  assert(((SizeInBits & 7) || (SizeInBits >> 32) == 0) &&
+         "Don't overflow unsigned.");
+  return (unsigned)SizeInBits >> 3;
+}
+
+
+int HexagonLoopIdiomRecognize::getSCEVStride(const SCEVAddRecExpr *S) {
+  if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
+    return SC->getAPInt().getSExtValue();
+  return 0;
+}
+
+
+bool HexagonLoopIdiomRecognize::isLegalStore(Loop *CurLoop, StoreInst *SI) {
+  // Allow volatile stores if HexagonVolatileMemcpy is enabled.
+  if (!(SI->isVolatile() && HexagonVolatileMemcpy) && !SI->isSimple())
+    return false;
+
+  Value *StoredVal = SI->getValueOperand();
+  Value *StorePtr = SI->getPointerOperand();
+
+  // Reject stores that are so large that they overflow an unsigned.
+  uint64_t SizeInBits = DL->getTypeSizeInBits(StoredVal->getType());
+  if ((SizeInBits & 7) || (SizeInBits >> 32) != 0)
+    return false;
+
+  // See if the pointer expression is an AddRec like {base,+,1} on the current
+  // loop, which indicates a strided store.  If we have something else, it's a
+  // random store we can't handle.
+  auto *StoreEv = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
+  if (!StoreEv || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine())
+    return false;
+
+  // Check to see if the stride matches the size of the store.  If so, then we
+  // know that every byte is touched in the loop.
+  int Stride = getSCEVStride(StoreEv);
+  if (Stride == 0)
+    return false;
+  unsigned StoreSize = getStoreSizeInBytes(SI);
+  if (StoreSize != unsigned(std::abs(Stride)))
+    return false;
+
+  // The store must be feeding a non-volatile load.
+  LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand());
+  if (!LI || !LI->isSimple())
+    return false;
+
+  // See if the pointer expression is an AddRec like {base,+,1} on the current
+  // loop, which indicates a strided load.  If we have something else, it's a
+  // random load we can't handle.
+  Value *LoadPtr = LI->getPointerOperand();
+  auto *LoadEv = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LoadPtr));
+  if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine())
+    return false;
+
+  // The store and load must share the same stride.
+  if (StoreEv->getOperand(1) != LoadEv->getOperand(1))
+    return false;
+
+  // Success.  This store can be converted into a memcpy.
+  return true;
+}
+
+
+/// mayLoopAccessLocation - Return true if the specified loop might access the
+/// specified pointer location, which is a loop-strided access.  The 'Access'
+/// argument specifies what the verboten forms of access are (read or write).
+static bool
+mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
+                      const SCEV *BECount, unsigned StoreSize,
+                      AliasAnalysis &AA,
+                      SmallPtrSetImpl<Instruction *> &Ignored) {
+  // Get the location that may be stored across the loop.  Since the access
+  // is strided positively through memory, we say that the modified location
+  // starts at the pointer and has infinite size.
+  uint64_t AccessSize = MemoryLocation::UnknownSize;
+
+  // If the loop iterates a fixed number of times, we can refine the access
+  // size to be exactly the size of the memset, which is (BECount+1)*StoreSize
+  if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
+    AccessSize = (BECst->getValue()->getZExtValue() + 1) * StoreSize;
+
+  // TODO: For this to be really effective, we have to dive into the pointer
+  // operand in the store.  Store to &A[i] of 100 will always return may alias
+  // with store of &A[100], we need to StoreLoc to be "A" with size of 100,
+  // which will then no-alias a store to &A[100].
+  MemoryLocation StoreLoc(Ptr, AccessSize);
+
+  for (auto *B : L->blocks())
+    for (auto &I : *B)
+      if (Ignored.count(&I) == 0 && (AA.getModRefInfo(&I, StoreLoc) & Access))
+        return true;
+
+  return false;
+}
+
+
+void HexagonLoopIdiomRecognize::collectStores(Loop *CurLoop, BasicBlock *BB,
+      SmallVectorImpl<StoreInst*> &Stores) {
+  Stores.clear();
+  for (Instruction &I : *BB)
+    if (StoreInst *SI = dyn_cast<StoreInst>(&I))
+      if (isLegalStore(CurLoop, SI))
+        Stores.push_back(SI);
+}
+
+
+bool HexagonLoopIdiomRecognize::processCopyingStore(Loop *CurLoop,
+      StoreInst *SI, const SCEV *BECount) {
+  assert((SI->isSimple() || (SI->isVolatile() && HexagonVolatileMemcpy)) &&
+         "Expected only non-volatile stores, or Hexagon-specific memcpy"
+         "to volatile destination.");
+
+  Value *StorePtr = SI->getPointerOperand();
+  auto *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
+  unsigned Stride = getSCEVStride(StoreEv);
+  unsigned StoreSize = getStoreSizeInBytes(SI);
+  if (Stride != StoreSize)
+    return false;
+
+  // See if the pointer expression is an AddRec like {base,+,1} on the current
+  // loop, which indicates a strided load.  If we have something else, it's a
+  // random load we can't handle.
+  LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand());
+  auto *LoadEv = cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand()));
+
+  // The trip count of the loop and the base pointer of the addrec SCEV is
+  // guaranteed to be loop invariant, which means that it should dominate the
+  // header.  This allows us to insert code for it in the preheader.
+  BasicBlock *Preheader = CurLoop->getLoopPreheader();
+  Instruction *ExpPt = Preheader->getTerminator();
+  IRBuilder<> Builder(ExpPt);
+  SCEVExpander Expander(*SE, *DL, "hexagon-loop-idiom");
+
+  Type *IntPtrTy = Builder.getIntPtrTy(*DL, SI->getPointerAddressSpace());
+
+  // Okay, we have a strided store "p[i]" of a loaded value.  We can turn
+  // this into a memcpy/memmove in the loop preheader now if we want.  However,
+  // this would be unsafe to do if there is anything else in the loop that may
+  // read or write the memory region we're storing to.  For memcpy, this
+  // includes the load that feeds the stores.  Check for an alias by generating
+  // the base address and checking everything.
+  Value *StoreBasePtr = Expander.expandCodeFor(StoreEv->getStart(),
+      Builder.getInt8PtrTy(SI->getPointerAddressSpace()), ExpPt);
+  Value *LoadBasePtr = nullptr;
+
+  bool Overlap = false;
+  bool DestVolatile = SI->isVolatile();
+  Type *BECountTy = BECount->getType();
+
+  if (DestVolatile) {
+    // The trip count must fit in i32, since it is the type of the "num_words"
+    // argument to hexagon_memcpy_forward_vp4cp4n2.
+    if (StoreSize != 4 || DL->getTypeSizeInBits(BECountTy) > 32) {
+CleanupAndExit:
+      // If we generated new code for the base pointer, clean up.
+      Expander.clear();
+      if (StoreBasePtr && (LoadBasePtr != StoreBasePtr)) {
+        RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
+        StoreBasePtr = nullptr;
+      }
+      if (LoadBasePtr) {
+        RecursivelyDeleteTriviallyDeadInstructions(LoadBasePtr, TLI);
+        LoadBasePtr = nullptr;
+      }
+      return false;
+    }
+  }
+
+  SmallPtrSet<Instruction*, 2> Ignore1;
+  Ignore1.insert(SI);
+  if (mayLoopAccessLocation(StoreBasePtr, MRI_ModRef, CurLoop, BECount,
+                            StoreSize, *AA, Ignore1)) {
+    // Check if the load is the offending instruction.
+    Ignore1.insert(LI);
+    if (mayLoopAccessLocation(StoreBasePtr, MRI_ModRef, CurLoop, BECount,
+                              StoreSize, *AA, Ignore1)) {
+      // Still bad. Nothing we can do.
+      goto CleanupAndExit;
+    }
+    // It worked with the load ignored.
+    Overlap = true;
+  }
+
+  if (!Overlap) {
+    if (DisableMemcpyIdiom || !HasMemcpy)
+      goto CleanupAndExit;
+  } else {
+    // Don't generate memmove if this function will be inlined. This is
+    // because the caller will undergo this transformation after inlining.
+    Function *Func = CurLoop->getHeader()->getParent();
+    if (Func->hasFnAttribute(Attribute::AlwaysInline))
+      goto CleanupAndExit;
+
+    // In case of a memmove, the call to memmove will be executed instead
+    // of the loop, so we need to make sure that there is nothing else in
+    // the loop than the load, store and instructions that these two depend
+    // on.
+    SmallVector<Instruction*,2> Insts;
+    Insts.push_back(SI);
+    Insts.push_back(LI);
+    if (!coverLoop(CurLoop, Insts))
+      goto CleanupAndExit;
+
+    if (DisableMemmoveIdiom || !HasMemmove)
+      goto CleanupAndExit;
+    bool IsNested = CurLoop->getParentLoop() != 0;
+    if (IsNested && OnlyNonNestedMemmove)
+      goto CleanupAndExit;
+  }
+
+  // For a memcpy, we have to make sure that the input array is not being
+  // mutated by the loop.
+  LoadBasePtr = Expander.expandCodeFor(LoadEv->getStart(),
+      Builder.getInt8PtrTy(LI->getPointerAddressSpace()), ExpPt);
+
+  SmallPtrSet<Instruction*, 2> Ignore2;
+  Ignore2.insert(SI);
+  if (mayLoopAccessLocation(LoadBasePtr, MRI_Mod, CurLoop, BECount, StoreSize,
+                            *AA, Ignore2))
+    goto CleanupAndExit;
+
+  // Check the stride.
+  bool StridePos = getSCEVStride(LoadEv) >= 0;
+
+  // Currently, the volatile memcpy only emulates traversing memory forward.
+  if (!StridePos && DestVolatile)
+    goto CleanupAndExit;
+
+  bool RuntimeCheck = (Overlap || DestVolatile);
+
+  BasicBlock *ExitB;
+  if (RuntimeCheck) {
+    // The runtime check needs a single exit block.
+    SmallVector<BasicBlock*, 8> ExitBlocks;
+    CurLoop->getUniqueExitBlocks(ExitBlocks);
+    if (ExitBlocks.size() != 1)
+      goto CleanupAndExit;
+    ExitB = ExitBlocks[0];
+  }
+
+  // The # stored bytes is (BECount+1)*Size.  Expand the trip count out to
+  // pointer size if it isn't already.
+  LLVMContext &Ctx = SI->getContext();
+  BECount = SE->getTruncateOrZeroExtend(BECount, IntPtrTy);
+  unsigned Alignment = std::min(SI->getAlignment(), LI->getAlignment());
+  DebugLoc DLoc = SI->getDebugLoc();
+
+  const SCEV *NumBytesS =
+      SE->getAddExpr(BECount, SE->getOne(IntPtrTy), SCEV::FlagNUW);
+  if (StoreSize != 1)
+    NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtrTy, StoreSize),
+                               SCEV::FlagNUW);
+  Value *NumBytes = Expander.expandCodeFor(NumBytesS, IntPtrTy, ExpPt);
+  if (Instruction *In = dyn_cast<Instruction>(NumBytes))
+    if (Value *Simp = SimplifyInstruction(In, {*DL, TLI, DT}))
+      NumBytes = Simp;
+
+  CallInst *NewCall;
+
+  if (RuntimeCheck) {
+    unsigned Threshold = RuntimeMemSizeThreshold;
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(NumBytes)) {
+      uint64_t C = CI->getZExtValue();
+      if (Threshold != 0 && C < Threshold)
+        goto CleanupAndExit;
+      if (C < CompileTimeMemSizeThreshold)
+        goto CleanupAndExit;
+    }
+
+    BasicBlock *Header = CurLoop->getHeader();
+    Function *Func = Header->getParent();
+    Loop *ParentL = LF->getLoopFor(Preheader);
+    StringRef HeaderName = Header->getName();
+
+    // Create a new (empty) preheader, and update the PHI nodes in the
+    // header to use the new preheader.
+    BasicBlock *NewPreheader = BasicBlock::Create(Ctx, HeaderName+".rtli.ph",
+                                                  Func, Header);
+    if (ParentL)
+      ParentL->addBasicBlockToLoop(NewPreheader, *LF);
+    IRBuilder<>(NewPreheader).CreateBr(Header);
+    for (auto &In : *Header) {
+      PHINode *PN = dyn_cast<PHINode>(&In);
+      if (!PN)
+        break;
+      int bx = PN->getBasicBlockIndex(Preheader);
+      if (bx >= 0)
+        PN->setIncomingBlock(bx, NewPreheader);
+    }
+    DT->addNewBlock(NewPreheader, Preheader);
+    DT->changeImmediateDominator(Header, NewPreheader);
+
+    // Check for safe conditions to execute memmove.
+    // If stride is positive, copying things from higher to lower addresses
+    // is equivalent to memmove.  For negative stride, it's the other way
+    // around.  Copying forward in memory with positive stride may not be
+    // same as memmove since we may be copying values that we just stored
+    // in some previous iteration.
+    Value *LA = Builder.CreatePtrToInt(LoadBasePtr, IntPtrTy);
+    Value *SA = Builder.CreatePtrToInt(StoreBasePtr, IntPtrTy);
+    Value *LowA = StridePos ? SA : LA;
+    Value *HighA = StridePos ? LA : SA;
+    Value *CmpA = Builder.CreateICmpULT(LowA, HighA);
+    Value *Cond = CmpA;
+
+    // Check for distance between pointers.
+    Value *Dist = Builder.CreateSub(HighA, LowA);
+    Value *CmpD = Builder.CreateICmpSLT(NumBytes, Dist);
+    Value *CmpEither = Builder.CreateOr(Cond, CmpD);
+    Cond = CmpEither;
+
+    if (Threshold != 0) {
+      Type *Ty = NumBytes->getType();
+      Value *Thr = ConstantInt::get(Ty, Threshold);
+      Value *CmpB = Builder.CreateICmpULT(Thr, NumBytes);
+      Value *CmpBoth = Builder.CreateAnd(Cond, CmpB);
+      Cond = CmpBoth;
+    }
+    BasicBlock *MemmoveB = BasicBlock::Create(Ctx, Header->getName()+".rtli",
+                                              Func, NewPreheader);
+    if (ParentL)
+      ParentL->addBasicBlockToLoop(MemmoveB, *LF);
+    Instruction *OldT = Preheader->getTerminator();
+    Builder.CreateCondBr(Cond, MemmoveB, NewPreheader);
+    OldT->eraseFromParent();
+    Preheader->setName(Preheader->getName()+".old");
+    DT->addNewBlock(MemmoveB, Preheader);
+    // Find the new immediate dominator of the exit block.
+    BasicBlock *ExitD = Preheader;
+    for (auto PI = pred_begin(ExitB), PE = pred_end(ExitB); PI != PE; ++PI) {
+      BasicBlock *PB = *PI;
+      ExitD = DT->findNearestCommonDominator(ExitD, PB);
+      if (!ExitD)
+        break;
+    }
+    // If the prior immediate dominator of ExitB was dominated by the
+    // old preheader, then the old preheader becomes the new immediate
+    // dominator.  Otherwise don't change anything (because the newly
+    // added blocks are dominated by the old preheader).
+    if (ExitD && DT->dominates(Preheader, ExitD)) {
+      DomTreeNode *BN = DT->getNode(ExitB);
+      DomTreeNode *DN = DT->getNode(ExitD);
+      BN->setIDom(DN);
+    }
+
+    // Add a call to memmove to the conditional block.
+    IRBuilder<> CondBuilder(MemmoveB);
+    CondBuilder.CreateBr(ExitB);
+    CondBuilder.SetInsertPoint(MemmoveB->getTerminator());
+
+    if (DestVolatile) {
+      Type *Int32Ty = Type::getInt32Ty(Ctx);
+      Type *Int32PtrTy = Type::getInt32PtrTy(Ctx);
+      Type *VoidTy = Type::getVoidTy(Ctx);
+      Module *M = Func->getParent();
+      Constant *CF = M->getOrInsertFunction(HexagonVolatileMemcpyName, VoidTy,
+                                            Int32PtrTy, Int32PtrTy, Int32Ty);
+      Function *Fn = cast<Function>(CF);
+      Fn->setLinkage(Function::ExternalLinkage);
+
+      const SCEV *OneS = SE->getConstant(Int32Ty, 1);
+      const SCEV *BECount32 = SE->getTruncateOrZeroExtend(BECount, Int32Ty);
+      const SCEV *NumWordsS = SE->getAddExpr(BECount32, OneS, SCEV::FlagNUW);
+      Value *NumWords = Expander.expandCodeFor(NumWordsS, Int32Ty,
+                                               MemmoveB->getTerminator());
+      if (Instruction *In = dyn_cast<Instruction>(NumWords))
+        if (Value *Simp = SimplifyInstruction(In, {*DL, TLI, DT}))
+          NumWords = Simp;
+
+      Value *Op0 = (StoreBasePtr->getType() == Int32PtrTy)
+                      ? StoreBasePtr
+                      : CondBuilder.CreateBitCast(StoreBasePtr, Int32PtrTy);
+      Value *Op1 = (LoadBasePtr->getType() == Int32PtrTy)
+                      ? LoadBasePtr
+                      : CondBuilder.CreateBitCast(LoadBasePtr, Int32PtrTy);
+      NewCall = CondBuilder.CreateCall(Fn, {Op0, Op1, NumWords});
+    } else {
+      NewCall = CondBuilder.CreateMemMove(StoreBasePtr, LoadBasePtr,
+                                          NumBytes, Alignment);
+    }
+  } else {
+    NewCall = Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr,
+                                   NumBytes, Alignment);
+    // Okay, the memcpy has been formed.  Zap the original store and
+    // anything that feeds into it.
+    RecursivelyDeleteTriviallyDeadInstructions(SI, TLI);
+  }
+
+  NewCall->setDebugLoc(DLoc);
+
+  DEBUG(dbgs() << "  Formed " << (Overlap ? "memmove: " : "memcpy: ")
+               << *NewCall << "\n"
+               << "    from load ptr=" << *LoadEv << " at: " << *LI << "\n"
+               << "    from store ptr=" << *StoreEv << " at: " << *SI << "\n");
+
+  return true;
+}
+
+
+// \brief Check if the instructions in Insts, together with their dependencies
+// cover the loop in the sense that the loop could be safely eliminated once
+// the instructions in Insts are removed.
+bool HexagonLoopIdiomRecognize::coverLoop(Loop *L,
+      SmallVectorImpl<Instruction*> &Insts) const {
+  SmallSet<BasicBlock*,8> LoopBlocks;
+  for (auto *B : L->blocks())
+    LoopBlocks.insert(B);
+
+  SetVector<Instruction*> Worklist(Insts.begin(), Insts.end());
+
+  // Collect all instructions from the loop that the instructions in Insts
+  // depend on (plus their dependencies, etc.).  These instructions will
+  // constitute the expression trees that feed those in Insts, but the trees
+  // will be limited only to instructions contained in the loop.
+  for (unsigned i = 0; i < Worklist.size(); ++i) {
+    Instruction *In = Worklist[i];
+    for (auto I = In->op_begin(), E = In->op_end(); I != E; ++I) {
+      Instruction *OpI = dyn_cast<Instruction>(I);
+      if (!OpI)
+        continue;
+      BasicBlock *PB = OpI->getParent();
+      if (!LoopBlocks.count(PB))
+        continue;
+      Worklist.insert(OpI);
+    }
+  }
+
+  // Scan all instructions in the loop, if any of them have a user outside
+  // of the loop, or outside of the expressions collected above, then either
+  // the loop has a side-effect visible outside of it, or there are
+  // instructions in it that are not involved in the original set Insts.
+  for (auto *B : L->blocks()) {
+    for (auto &In : *B) {
+      if (isa<BranchInst>(In) || isa<DbgInfoIntrinsic>(In))
+        continue;
+      if (!Worklist.count(&In) && In.mayHaveSideEffects())
+        return false;
+      for (const auto &K : In.users()) {
+        Instruction *UseI = dyn_cast<Instruction>(K);
+        if (!UseI)
+          continue;
+        BasicBlock *UseB = UseI->getParent();
+        if (LF->getLoopFor(UseB) != L)
+          return false;
+      }
+    }
+  }
+
+  return true;
+}
+
+/// runOnLoopBlock - Process the specified block, which lives in a counted loop
+/// with the specified backedge count.  This block is known to be in the current
+/// loop and not in any subloops.
+bool HexagonLoopIdiomRecognize::runOnLoopBlock(Loop *CurLoop, BasicBlock *BB,
+      const SCEV *BECount, SmallVectorImpl<BasicBlock*> &ExitBlocks) {
+  // We can only promote stores in this block if they are unconditionally
+  // executed in the loop.  For a block to be unconditionally executed, it has
+  // to dominate all the exit blocks of the loop.  Verify this now.
+  auto DominatedByBB = [this,BB] (BasicBlock *EB) -> bool {
+    return DT->dominates(BB, EB);
+  };
+  if (!std::all_of(ExitBlocks.begin(), ExitBlocks.end(), DominatedByBB))
+    return false;
+
+  bool MadeChange = false;
+  // Look for store instructions, which may be optimized to memset/memcpy.
+  SmallVector<StoreInst*,8> Stores;
+  collectStores(CurLoop, BB, Stores);
+
+  // Optimize the store into a memcpy, if it feeds an similarly strided load.
+  for (auto &SI : Stores)
+    MadeChange |= processCopyingStore(CurLoop, SI, BECount);
+
+  return MadeChange;
+}
+
+
+bool HexagonLoopIdiomRecognize::runOnCountableLoop(Loop *L) {
+  PolynomialMultiplyRecognize PMR(L, *DL, *DT, *TLI, *SE);
+  if (PMR.recognize())
+    return true;
+
+  if (!HasMemcpy && !HasMemmove)
+    return false;
+
+  const SCEV *BECount = SE->getBackedgeTakenCount(L);
+  assert(!isa<SCEVCouldNotCompute>(BECount) &&
+         "runOnCountableLoop() called on a loop without a predictable"
+         "backedge-taken count");
+
+  SmallVector<BasicBlock *, 8> ExitBlocks;
+  L->getUniqueExitBlocks(ExitBlocks);
+
+  bool Changed = false;
+
+  // Scan all the blocks in the loop that are not in subloops.
+  for (auto *BB : L->getBlocks()) {
+    // Ignore blocks in subloops.
+    if (LF->getLoopFor(BB) != L)
+      continue;
+    Changed |= runOnLoopBlock(L, BB, BECount, ExitBlocks);
+  }
+
+  return Changed;
+}
+
+
+bool HexagonLoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
+  const Module &M = *L->getHeader()->getParent()->getParent();
+  if (Triple(M.getTargetTriple()).getArch() != Triple::hexagon)
+    return false;
+
+  if (skipLoop(L))
+    return false;
+
+  // If the loop could not be converted to canonical form, it must have an
+  // indirectbr in it, just give up.
+  if (!L->getLoopPreheader())
+    return false;
+
+  // Disable loop idiom recognition if the function's name is a common idiom.
+  StringRef Name = L->getHeader()->getParent()->getName();
+  if (Name == "memset" || Name == "memcpy" || Name == "memmove")
+    return false;
+
+  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+  DL = &L->getHeader()->getModule()->getDataLayout();
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  LF = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+
+  HasMemcpy = TLI->has(LibFunc_memcpy);
+  HasMemmove = TLI->has(LibFunc_memmove);
+
+  if (SE->hasLoopInvariantBackedgeTakenCount(L))
+    return runOnCountableLoop(L);
+  return false;
+}
+
+
+Pass *llvm::createHexagonLoopIdiomPass() {
+  return new HexagonLoopIdiomRecognize();
+}
+