contrib/llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp

   1 //===--- HexagonLoopIdiomRecognition.cpp ----------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #define DEBUG_TYPE "hexagon-lir"
  11
  12 #include "llvm/ADT/SetVector.h"
  13 #include "llvm/ADT/SmallSet.h"
  14 #include "llvm/Analysis/AliasAnalysis.h"
  15 #include "llvm/Analysis/InstructionSimplify.h"
  16 #include "llvm/Analysis/LoopPass.h"
  17 #include "llvm/Analysis/ScalarEvolution.h"
  18 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  20 #include "llvm/Analysis/TargetLibraryInfo.h"
  21 #include "llvm/Analysis/ValueTracking.h"
  22 #include "llvm/IR/DataLayout.h"
  23 #include "llvm/IR/Dominators.h"
  24 #include "llvm/IR/IRBuilder.h"
  25 #include "llvm/IR/PatternMatch.h"
  26 #include "llvm/Transforms/Scalar.h"
  27 #include "llvm/Transforms/Utils/Local.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/KnownBits.h"
  30 #include "llvm/Support/raw_ostream.h"
  31
  32 #include <algorithm>
  33 #include <array>
  34
  35 using namespace llvm;
  36
  37 static cl::opt<bool> DisableMemcpyIdiom("disable-memcpy-idiom",
  38   cl::Hidden, cl::init(false),
  39   cl::desc("Disable generation of memcpy in loop idiom recognition"));
  40
  41 static cl::opt<bool> DisableMemmoveIdiom("disable-memmove-idiom",
  42   cl::Hidden, cl::init(false),
  43   cl::desc("Disable generation of memmove in loop idiom recognition"));
  44
  45 static cl::opt<unsigned> RuntimeMemSizeThreshold("runtime-mem-idiom-threshold",
  46   cl::Hidden, cl::init(0), cl::desc("Threshold (in bytes) for the runtime "
  47   "check guarding the memmove."));
  48
  49 static cl::opt<unsigned> CompileTimeMemSizeThreshold(
  50   "compile-time-mem-idiom-threshold", cl::Hidden, cl::init(64),
  51   cl::desc("Threshold (in bytes) to perform the transformation, if the "
  52     "runtime loop count (mem transfer size) is known at compile-time."));
  53
  54 static cl::opt<bool> OnlyNonNestedMemmove("only-nonnested-memmove-idiom",
  55   cl::Hidden, cl::init(true),
  56   cl::desc("Only enable generating memmove in non-nested loops"));
  57
  58 cl::opt<bool> HexagonVolatileMemcpy("disable-hexagon-volatile-memcpy",
  59   cl::Hidden, cl::init(false),
  60   cl::desc("Enable Hexagon-specific memcpy for volatile destination."));
  61
  62 static const char *HexagonVolatileMemcpyName
  63   = "hexagon_memcpy_forward_vp4cp4n2";
  64
  65
  66 namespace llvm {
  67   void initializeHexagonLoopIdiomRecognizePass(PassRegistry&);
  68   Pass *createHexagonLoopIdiomPass();
  69 }
  70
  71 namespace {
  72   class HexagonLoopIdiomRecognize : public LoopPass {
  73   public:
  74     static char ID;
  75     explicit HexagonLoopIdiomRecognize() : LoopPass(ID) {
  76       initializeHexagonLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
  77     }
  78     StringRef getPassName() const override {
  79       return "Recognize Hexagon-specific loop idioms";
  80     }
  81
  82    void getAnalysisUsage(AnalysisUsage &AU) const override {
  83       AU.addRequired<LoopInfoWrapperPass>();
  84       AU.addRequiredID(LoopSimplifyID);
  85       AU.addRequiredID(LCSSAID);
  86       AU.addRequired<AAResultsWrapperPass>();
  87       AU.addPreserved<AAResultsWrapperPass>();
  88       AU.addRequired<ScalarEvolutionWrapperPass>();
  89       AU.addRequired<DominatorTreeWrapperPass>();
  90       AU.addRequired<TargetLibraryInfoWrapperPass>();
  91       AU.addPreserved<TargetLibraryInfoWrapperPass>();
  92     }
  93
  94     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
  95
  96   private:
  97     unsigned getStoreSizeInBytes(StoreInst *SI);
  98     int getSCEVStride(const SCEVAddRecExpr *StoreEv);
  99     bool isLegalStore(Loop *CurLoop, StoreInst *SI);
 100     void collectStores(Loop *CurLoop, BasicBlock *BB,
 101         SmallVectorImpl<StoreInst*> &Stores);
 102     bool processCopyingStore(Loop *CurLoop, StoreInst *SI, const SCEV *BECount);
 103     bool coverLoop(Loop *L, SmallVectorImpl<Instruction*> &Insts) const;
 104     bool runOnLoopBlock(Loop *CurLoop, BasicBlock *BB, const SCEV *BECount,
 105         SmallVectorImpl<BasicBlock*> &ExitBlocks);
 106     bool runOnCountableLoop(Loop *L);
 107
 108     AliasAnalysis *AA;
 109     const DataLayout *DL;
 110     DominatorTree *DT;
 111     LoopInfo *LF;
 112     const TargetLibraryInfo *TLI;
 113     ScalarEvolution *SE;
 114     bool HasMemcpy, HasMemmove;
 115   };
 116 }
 117
 118 char HexagonLoopIdiomRecognize::ID = 0;
 119
 120 INITIALIZE_PASS_BEGIN(HexagonLoopIdiomRecognize, "hexagon-loop-idiom",
 121     "Recognize Hexagon-specific loop idioms", false, false)
 122 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 123 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 124 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 125 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 126 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 127 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 128 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 129 INITIALIZE_PASS_END(HexagonLoopIdiomRecognize, "hexagon-loop-idiom",
 130     "Recognize Hexagon-specific loop idioms", false, false)
 131
 132
 133 namespace {
 134   struct Simplifier {
 135     typedef std::function<Value* (Instruction*, LLVMContext&)> Rule;
 136
 137     void addRule(const Rule &R) { Rules.push_back(R); }
 138
 139   private:
 140     struct WorkListType {
 141       WorkListType() = default;
 142
 143       void push_back(Value* V) {
 144         // Do not push back duplicates.
 145         if (!S.count(V)) { Q.push_back(V); S.insert(V); }
 146       }
 147       Value *pop_front_val() {
 148         Value *V = Q.front(); Q.pop_front(); S.erase(V);
 149         return V;
 150       }
 151       bool empty() const { return Q.empty(); }
 152
 153     private:
 154       std::deque<Value*> Q;
 155       std::set<Value*> S;
 156     };
 157
 158     typedef std::set<Value*> ValueSetType;
 159     std::vector<Rule> Rules;
 160
 161   public:
 162     struct Context {
 163       typedef DenseMap<Value*,Value*> ValueMapType;
 164
 165       Value *Root;
 166       ValueSetType Used;    // The set of all cloned values used by Root.
 167       ValueSetType Clones;  // The set of all cloned values.
 168       LLVMContext &Ctx;
 169
 170       Context(Instruction *Exp)
 171         : Ctx(Exp->getParent()->getParent()->getContext()) {
 172         initialize(Exp);
 173       }
 174       ~Context() { cleanup(); }
 175       void print(raw_ostream &OS, const Value *V) const;
 176
 177       Value *materialize(BasicBlock *B, BasicBlock::iterator At);
 178
 179     private:
 180       void initialize(Instruction *Exp);
 181       void cleanup();
 182
 183       template <typename FuncT> void traverse(Value *V, FuncT F);
 184       void record(Value *V);
 185       void use(Value *V);
 186       void unuse(Value *V);
 187
 188       bool equal(const Instruction *I, const Instruction *J) const;
 189       Value *find(Value *Tree, Value *Sub) const;
 190       Value *subst(Value *Tree, Value *OldV, Value *NewV);
 191       void replace(Value *OldV, Value *NewV);
 192       void link(Instruction *I, BasicBlock *B, BasicBlock::iterator At);
 193
 194       friend struct Simplifier;
 195     };
 196
 197     Value *simplify(Context &C);
 198   };
 199
 200   struct PE {
 201     PE(const Simplifier::Context &c, Value *v = nullptr) : C(c), V(v) {}
 202     const Simplifier::Context &C;
 203     const Value *V;
 204   };
 205
 206   raw_ostream &operator<< (raw_ostream &OS, const PE &P) LLVM_ATTRIBUTE_USED;
 207   raw_ostream &operator<< (raw_ostream &OS, const PE &P) {
 208     P.C.print(OS, P.V ? P.V : P.C.Root);
 209     return OS;
 210   }
 211 }
 212
 213
 214 template <typename FuncT>
 215 void Simplifier::Context::traverse(Value *V, FuncT F) {
 216   WorkListType Q;
 217   Q.push_back(V);
 218
 219   while (!Q.empty()) {
 220     Instruction *U = dyn_cast<Instruction>(Q.pop_front_val());
 221     if (!U || U->getParent())
 222       continue;
 223     if (!F(U))
 224       continue;
 225     for (Value *Op : U->operands())
 226       Q.push_back(Op);
 227   }
 228 }
 229
 230
 231 void Simplifier::Context::print(raw_ostream &OS, const Value *V) const {
 232   const auto *U = dyn_cast<const Instruction>(V);
 233   if (!U) {
 234     OS << V << '(' << *V << ')';
 235     return;
 236   }
 237
 238   if (U->getParent()) {
 239     OS << U << '(';
 240     U->printAsOperand(OS, true);
 241     OS << ')';
 242     return;
 243   }
 244
 245   unsigned N = U->getNumOperands();
 246   if (N != 0)
 247     OS << U << '(';
 248   OS << U->getOpcodeName();
 249   for (const Value *Op : U->operands()) {
 250     OS << ' ';
 251     print(OS, Op);
 252   }
 253   if (N != 0)
 254     OS << ')';
 255 }
 256
 257
 258 void Simplifier::Context::initialize(Instruction *Exp) {
 259   // Perform a deep clone of the expression, set Root to the root
 260   // of the clone, and build a map from the cloned values to the
 261   // original ones.
 262   ValueMapType M;
 263   BasicBlock *Block = Exp->getParent();
 264   WorkListType Q;
 265   Q.push_back(Exp);
 266
 267   while (!Q.empty()) {
 268     Value *V = Q.pop_front_val();
 269     if (M.find(V) != M.end())
 270       continue;
 271     if (Instruction *U = dyn_cast<Instruction>(V)) {
 272       if (isa<PHINode>(U) || U->getParent() != Block)
 273         continue;
 274       for (Value *Op : U->operands())
 275         Q.push_back(Op);
 276       M.insert({U, U->clone()});
 277     }
 278   }
 279
 280   for (std::pair<Value*,Value*> P : M) {
 281     Instruction *U = cast<Instruction>(P.second);
 282     for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i) {
 283       auto F = M.find(U->getOperand(i));
 284       if (F != M.end())
 285         U->setOperand(i, F->second);
 286     }
 287   }
 288
 289   auto R = M.find(Exp);
 290   assert(R != M.end());
 291   Root = R->second;
 292
 293   record(Root);
 294   use(Root);
 295 }
 296
 297
 298 void Simplifier::Context::record(Value *V) {
 299   auto Record = [this](Instruction *U) -> bool {
 300     Clones.insert(U);
 301     return true;
 302   };
 303   traverse(V, Record);
 304 }
 305
 306
 307 void Simplifier::Context::use(Value *V) {
 308   auto Use = [this](Instruction *U) -> bool {
 309     Used.insert(U);
 310     return true;
 311   };
 312   traverse(V, Use);
 313 }
 314
 315
 316 void Simplifier::Context::unuse(Value *V) {
 317   if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != nullptr)
 318     return;
 319
 320   auto Unuse = [this](Instruction *U) -> bool {
 321     if (!U->use_empty())
 322       return false;
 323     Used.erase(U);
 324     return true;
 325   };
 326   traverse(V, Unuse);
 327 }
 328
 329
 330 Value *Simplifier::Context::subst(Value *Tree, Value *OldV, Value *NewV) {
 331   if (Tree == OldV)
 332     return NewV;
 333   if (OldV == NewV)
 334     return Tree;
 335
 336   WorkListType Q;
 337   Q.push_back(Tree);
 338   while (!Q.empty()) {
 339     Instruction *U = dyn_cast<Instruction>(Q.pop_front_val());
 340     // If U is not an instruction, or it's not a clone, skip it.
 341     if (!U || U->getParent())
 342       continue;
 343     for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i) {
 344       Value *Op = U->getOperand(i);
 345       if (Op == OldV) {
 346         U->setOperand(i, NewV);
 347         unuse(OldV);
 348       } else {
 349         Q.push_back(Op);
 350       }
 351     }
 352   }
 353   return Tree;
 354 }
 355
 356
 357 void Simplifier::Context::replace(Value *OldV, Value *NewV) {
 358   if (Root == OldV) {
 359     Root = NewV;
 360     use(Root);
 361     return;
 362   }
 363
 364   // NewV may be a complex tree that has just been created by one of the
 365   // transformation rules. We need to make sure that it is commoned with
 366   // the existing Root to the maximum extent possible.
 367   // Identify all subtrees of NewV (including NewV itself) that have
 368   // equivalent counterparts in Root, and replace those subtrees with
 369   // these counterparts.
 370   WorkListType Q;
 371   Q.push_back(NewV);
 372   while (!Q.empty()) {
 373     Value *V = Q.pop_front_val();
 374     Instruction *U = dyn_cast<Instruction>(V);
 375     if (!U || U->getParent())
 376       continue;
 377     if (Value *DupV = find(Root, V)) {
 378       if (DupV != V)
 379         NewV = subst(NewV, V, DupV);
 380     } else {
 381       for (Value *Op : U->operands())
 382         Q.push_back(Op);
 383     }
 384   }
 385
 386   // Now, simply replace OldV with NewV in Root.
 387   Root = subst(Root, OldV, NewV);
 388   use(Root);
 389 }
 390
 391
 392 void Simplifier::Context::cleanup() {
 393   for (Value *V : Clones) {
 394     Instruction *U = cast<Instruction>(V);
 395     if (!U->getParent())
 396       U->dropAllReferences();
 397   }
 398
 399   for (Value *V : Clones) {
 400     Instruction *U = cast<Instruction>(V);
 401     if (!U->getParent())
 402       U->deleteValue();
 403   }
 404 }
 405
 406
 407 bool Simplifier::Context::equal(const Instruction *I,
 408                                 const Instruction *J) const {
 409   if (I == J)
 410     return true;
 411   if (!I->isSameOperationAs(J))
 412     return false;
 413   if (isa<PHINode>(I))
 414     return I->isIdenticalTo(J);
 415
 416   for (unsigned i = 0, n = I->getNumOperands(); i != n; ++i) {
 417     Value *OpI = I->getOperand(i), *OpJ = J->getOperand(i);
 418     if (OpI == OpJ)
 419       continue;
 420     auto *InI = dyn_cast<const Instruction>(OpI);
 421     auto *InJ = dyn_cast<const Instruction>(OpJ);
 422     if (InI && InJ) {
 423       if (!equal(InI, InJ))
 424         return false;
 425     } else if (InI != InJ || !InI)
 426       return false;
 427   }
 428   return true;
 429 }
 430
 431
 432 Value *Simplifier::Context::find(Value *Tree, Value *Sub) const {
 433   Instruction *SubI = dyn_cast<Instruction>(Sub);
 434   WorkListType Q;
 435   Q.push_back(Tree);
 436
 437   while (!Q.empty()) {
 438     Value *V = Q.pop_front_val();
 439     if (V == Sub)
 440       return V;
 441     Instruction *U = dyn_cast<Instruction>(V);
 442     if (!U || U->getParent())
 443       continue;
 444     if (SubI && equal(SubI, U))
 445       return U;
 446     assert(!isa<PHINode>(U));
 447     for (Value *Op : U->operands())
 448       Q.push_back(Op);
 449   }
 450   return nullptr;
 451 }
 452
 453
 454 void Simplifier::Context::link(Instruction *I, BasicBlock *B,
 455       BasicBlock::iterator At) {
 456   if (I->getParent())
 457     return;
 458
 459   for (Value *Op : I->operands()) {
 460     if (Instruction *OpI = dyn_cast<Instruction>(Op))
 461       link(OpI, B, At);
 462   }
 463
 464   B->getInstList().insert(At, I);
 465 }
 466
 467
 468 Value *Simplifier::Context::materialize(BasicBlock *B,
 469       BasicBlock::iterator At) {
 470   if (Instruction *RootI = dyn_cast<Instruction>(Root))
 471     link(RootI, B, At);
 472   return Root;
 473 }
 474
 475
 476 Value *Simplifier::simplify(Context &C) {
 477   WorkListType Q;
 478   Q.push_back(C.Root);
 479   unsigned Count = 0;
 480   const unsigned Limit = 100000;
 481
 482   while (!Q.empty()) {
 483     if (Count++ >= Limit)
 484       break;
 485     Instruction *U = dyn_cast<Instruction>(Q.pop_front_val());
 486     if (!U || U->getParent() || !C.Used.count(U))
 487       continue;
 488     bool Changed = false;
 489     for (Rule &R : Rules) {
 490       Value *W = R(U, C.Ctx);
 491       if (!W)
 492         continue;
 493       Changed = true;
 494       C.record(W);
 495       C.replace(U, W);
 496       Q.push_back(C.Root);
 497       break;
 498     }
 499     if (!Changed) {
 500       for (Value *Op : U->operands())
 501         Q.push_back(Op);
 502     }
 503   }
 504   assert(Count < Limit && "Infinite loop in HLIR/simplify?");
 505   return C.Root;
 506 }
 507
 508
 509 //===----------------------------------------------------------------------===//
 510 //
 511 //          Implementation of PolynomialMultiplyRecognize
 512 //
 513 //===----------------------------------------------------------------------===//
 514
 515 namespace {
 516   class PolynomialMultiplyRecognize {
 517   public:
 518     explicit PolynomialMultiplyRecognize(Loop *loop, const DataLayout &dl,
 519         const DominatorTree &dt, const TargetLibraryInfo &tli,
 520         ScalarEvolution &se)
 521       : CurLoop(loop), DL(dl), DT(dt), TLI(tli), SE(se) {}
 522
 523     bool recognize();
 524   private:
 525     typedef SetVector<Value*> ValueSeq;
 526
 527     IntegerType *getPmpyType() const {
 528       LLVMContext &Ctx = CurLoop->getHeader()->getParent()->getContext();
 529       return IntegerType::get(Ctx, 32);
 530     }
 531     bool isPromotableTo(Value *V, IntegerType *Ty);
 532     void promoteTo(Instruction *In, IntegerType *DestTy, BasicBlock *LoopB);
 533     bool promoteTypes(BasicBlock *LoopB, BasicBlock *ExitB);
 534
 535     Value *getCountIV(BasicBlock *BB);
 536     bool findCycle(Value *Out, Value *In, ValueSeq &Cycle);
 537     void classifyCycle(Instruction *DivI, ValueSeq &Cycle, ValueSeq &Early,
 538           ValueSeq &Late);
 539     bool classifyInst(Instruction *UseI, ValueSeq &Early, ValueSeq &Late);
 540     bool commutesWithShift(Instruction *I);
 541     bool highBitsAreZero(Value *V, unsigned IterCount);
 542     bool keepsHighBitsZero(Value *V, unsigned IterCount);
 543     bool isOperandShifted(Instruction *I, Value *Op);
 544     bool convertShiftsToLeft(BasicBlock *LoopB, BasicBlock *ExitB,
 545           unsigned IterCount);
 546     void cleanupLoopBody(BasicBlock *LoopB);
 547
 548     struct ParsedValues {
 549       ParsedValues() : M(nullptr), P(nullptr), Q(nullptr), R(nullptr),
 550           X(nullptr), Res(nullptr), IterCount(0), Left(false), Inv(false) {}
 551       Value *M, *P, *Q, *R, *X;
 552       Instruction *Res;
 553       unsigned IterCount;
 554       bool Left, Inv;
 555     };
 556
 557     bool matchLeftShift(SelectInst *SelI, Value *CIV, ParsedValues &PV);
 558     bool matchRightShift(SelectInst *SelI, ParsedValues &PV);
 559     bool scanSelect(SelectInst *SI, BasicBlock *LoopB, BasicBlock *PrehB,
 560           Value *CIV, ParsedValues &PV, bool PreScan);
 561     unsigned getInverseMxN(unsigned QP);
 562     Value *generate(BasicBlock::iterator At, ParsedValues &PV);
 563
 564     void setupSimplifier();
 565
 566     Simplifier Simp;
 567     Loop *CurLoop;
 568     const DataLayout &DL;
 569     const DominatorTree &DT;
 570     const TargetLibraryInfo &TLI;
 571     ScalarEvolution &SE;
 572   };
 573 }
 574
 575
 576 Value *PolynomialMultiplyRecognize::getCountIV(BasicBlock *BB) {
 577   pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 578   if (std::distance(PI, PE) != 2)
 579     return nullptr;
 580   BasicBlock *PB = (*PI == BB) ? *std::next(PI) : *PI;
 581
 582   for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
 583     auto *PN = cast<PHINode>(I);
 584     Value *InitV = PN->getIncomingValueForBlock(PB);
 585     if (!isa<ConstantInt>(InitV) || !cast<ConstantInt>(InitV)->isZero())
 586       continue;
 587     Value *IterV = PN->getIncomingValueForBlock(BB);
 588     if (!isa<BinaryOperator>(IterV))
 589       continue;
 590     auto *BO = dyn_cast<BinaryOperator>(IterV);
 591     if (BO->getOpcode() != Instruction::Add)
 592       continue;
 593     Value *IncV = nullptr;
 594     if (BO->getOperand(0) == PN)
 595       IncV = BO->getOperand(1);
 596     else if (BO->getOperand(1) == PN)
 597       IncV = BO->getOperand(0);
 598     if (IncV == nullptr)
 599       continue;
 600
 601     if (auto *T = dyn_cast<ConstantInt>(IncV))
 602       if (T->getZExtValue() == 1)
 603         return PN;
 604   }
 605   return nullptr;
 606 }
 607
 608
 609 static void replaceAllUsesOfWithIn(Value *I, Value *J, BasicBlock *BB) {
 610   for (auto UI = I->user_begin(), UE = I->user_end(); UI != UE;) {
 611     Use &TheUse = UI.getUse();
 612     ++UI;
 613     if (auto *II = dyn_cast<Instruction>(TheUse.getUser()))
 614       if (BB == II->getParent())
 615         II->replaceUsesOfWith(I, J);
 616   }
 617 }
 618
 619
 620 bool PolynomialMultiplyRecognize::matchLeftShift(SelectInst *SelI,
 621       Value *CIV, ParsedValues &PV) {
 622   // Match the following:
 623   //   select (X & (1 << i)) != 0 ? R ^ (Q << i) : R
 624   //   select (X & (1 << i)) == 0 ? R : R ^ (Q << i)
 625   // The condition may also check for equality with the masked value, i.e
 626   //   select (X & (1 << i)) == (1 << i) ? R ^ (Q << i) : R
 627   //   select (X & (1 << i)) != (1 << i) ? R : R ^ (Q << i);
 628
 629   Value *CondV = SelI->getCondition();
 630   Value *TrueV = SelI->getTrueValue();
 631   Value *FalseV = SelI->getFalseValue();
 632
 633   using namespace PatternMatch;
 634
 635   CmpInst::Predicate P;
 636   Value *A = nullptr, *B = nullptr, *C = nullptr;
 637
 638   if (!match(CondV, m_ICmp(P, m_And(m_Value(A), m_Value(B)), m_Value(C))) &&
 639       !match(CondV, m_ICmp(P, m_Value(C), m_And(m_Value(A), m_Value(B)))))
 640     return false;
 641   if (P != CmpInst::ICMP_EQ && P != CmpInst::ICMP_NE)
 642     return false;
 643   // Matched: select (A & B) == C ? ... : ...
 644   //          select (A & B) != C ? ... : ...
 645
 646   Value *X = nullptr, *Sh1 = nullptr;
 647   // Check (A & B) for (X & (1 << i)):
 648   if (match(A, m_Shl(m_One(), m_Specific(CIV)))) {
 649     Sh1 = A;
 650     X = B;
 651   } else if (match(B, m_Shl(m_One(), m_Specific(CIV)))) {
 652     Sh1 = B;
 653     X = A;
 654   } else {
 655     // TODO: Could also check for an induction variable containing single
 656     // bit shifted left by 1 in each iteration.
 657     return false;
 658   }
 659
 660   bool TrueIfZero;
 661
 662   // Check C against the possible values for comparison: 0 and (1 << i):
 663   if (match(C, m_Zero()))
 664     TrueIfZero = (P == CmpInst::ICMP_EQ);
 665   else if (C == Sh1)
 666     TrueIfZero = (P == CmpInst::ICMP_NE);
 667   else
 668     return false;
 669
 670   // So far, matched:
 671   //   select (X & (1 << i)) ? ... : ...
 672   // including variations of the check against zero/non-zero value.
 673
 674   Value *ShouldSameV = nullptr, *ShouldXoredV = nullptr;
 675   if (TrueIfZero) {
 676     ShouldSameV = TrueV;
 677     ShouldXoredV = FalseV;
 678   } else {
 679     ShouldSameV = FalseV;
 680     ShouldXoredV = TrueV;
 681   }
 682
 683   Value *Q = nullptr, *R = nullptr, *Y = nullptr, *Z = nullptr;
 684   Value *T = nullptr;
 685   if (match(ShouldXoredV, m_Xor(m_Value(Y), m_Value(Z)))) {
 686     // Matched: select +++ ? ... : Y ^ Z
 687     //          select +++ ? Y ^ Z : ...
 688     // where +++ denotes previously checked matches.
 689     if (ShouldSameV == Y)
 690       T = Z;
 691     else if (ShouldSameV == Z)
 692       T = Y;
 693     else
 694       return false;
 695     R = ShouldSameV;
 696     // Matched: select +++ ? R : R ^ T
 697     //          select +++ ? R ^ T : R
 698     // depending on TrueIfZero.
 699
 700   } else if (match(ShouldSameV, m_Zero())) {
 701     // Matched: select +++ ? 0 : ...
 702     //          select +++ ? ... : 0
 703     if (!SelI->hasOneUse())
 704       return false;
 705     T = ShouldXoredV;
 706     // Matched: select +++ ? 0 : T
 707     //          select +++ ? T : 0
 708
 709     Value *U = *SelI->user_begin();
 710     if (!match(U, m_Xor(m_Specific(SelI), m_Value(R))) &&
 711         !match(U, m_Xor(m_Value(R), m_Specific(SelI))))
 712       return false;
 713     // Matched: xor (select +++ ? 0 : T), R
 714     //          xor (select +++ ? T : 0), R
 715   } else
 716     return false;
 717
 718   // The xor input value T is isolated into its own match so that it could
 719   // be checked against an induction variable containing a shifted bit
 720   // (todo).
 721   // For now, check against (Q << i).
 722   if (!match(T, m_Shl(m_Value(Q), m_Specific(CIV))) &&
 723       !match(T, m_Shl(m_ZExt(m_Value(Q)), m_ZExt(m_Specific(CIV)))))
 724     return false;
 725   // Matched: select +++ ? R : R ^ (Q << i)
 726   //          select +++ ? R ^ (Q << i) : R
 727
 728   PV.X = X;
 729   PV.Q = Q;
 730   PV.R = R;
 731   PV.Left = true;
 732   return true;
 733 }
 734
 735
 736 bool PolynomialMultiplyRecognize::matchRightShift(SelectInst *SelI,
 737       ParsedValues &PV) {
 738   // Match the following:
 739   //   select (X & 1) != 0 ? (R >> 1) ^ Q : (R >> 1)
 740   //   select (X & 1) == 0 ? (R >> 1) : (R >> 1) ^ Q
 741   // The condition may also check for equality with the masked value, i.e
 742   //   select (X & 1) == 1 ? (R >> 1) ^ Q : (R >> 1)
 743   //   select (X & 1) != 1 ? (R >> 1) : (R >> 1) ^ Q
 744
 745   Value *CondV = SelI->getCondition();
 746   Value *TrueV = SelI->getTrueValue();
 747   Value *FalseV = SelI->getFalseValue();
 748
 749   using namespace PatternMatch;
 750
 751   Value *C = nullptr;
 752   CmpInst::Predicate P;
 753   bool TrueIfZero;
 754
 755   if (match(CondV, m_ICmp(P, m_Value(C), m_Zero())) ||
 756       match(CondV, m_ICmp(P, m_Zero(), m_Value(C)))) {
 757     if (P != CmpInst::ICMP_EQ && P != CmpInst::ICMP_NE)
 758       return false;
 759     // Matched: select C == 0 ? ... : ...
 760     //          select C != 0 ? ... : ...
 761     TrueIfZero = (P == CmpInst::ICMP_EQ);
 762   } else if (match(CondV, m_ICmp(P, m_Value(C), m_One())) ||
 763              match(CondV, m_ICmp(P, m_One(), m_Value(C)))) {
 764     if (P != CmpInst::ICMP_EQ && P != CmpInst::ICMP_NE)
 765       return false;
 766     // Matched: select C == 1 ? ... : ...
 767     //          select C != 1 ? ... : ...
 768     TrueIfZero = (P == CmpInst::ICMP_NE);
 769   } else
 770     return false;
 771
 772   Value *X = nullptr;
 773   if (!match(C, m_And(m_Value(X), m_One())) &&
 774       !match(C, m_And(m_One(), m_Value(X))))
 775     return false;
 776   // Matched: select (X & 1) == +++ ? ... : ...
 777   //          select (X & 1) != +++ ? ... : ...
 778
 779   Value *R = nullptr, *Q = nullptr;
 780   if (TrueIfZero) {
 781     // The select's condition is true if the tested bit is 0.
 782     // TrueV must be the shift, FalseV must be the xor.
 783     if (!match(TrueV, m_LShr(m_Value(R), m_One())))
 784       return false;
 785     // Matched: select +++ ? (R >> 1) : ...
 786     if (!match(FalseV, m_Xor(m_Specific(TrueV), m_Value(Q))) &&
 787         !match(FalseV, m_Xor(m_Value(Q), m_Specific(TrueV))))
 788       return false;
 789     // Matched: select +++ ? (R >> 1) : (R >> 1) ^ Q
 790     // with commuting ^.
 791   } else {
 792     // The select's condition is true if the tested bit is 1.
 793     // TrueV must be the xor, FalseV must be the shift.
 794     if (!match(FalseV, m_LShr(m_Value(R), m_One())))
 795       return false;
 796     // Matched: select +++ ? ... : (R >> 1)
 797     if (!match(TrueV, m_Xor(m_Specific(FalseV), m_Value(Q))) &&
 798         !match(TrueV, m_Xor(m_Value(Q), m_Specific(FalseV))))
 799       return false;
 800     // Matched: select +++ ? (R >> 1) ^ Q : (R >> 1)
 801     // with commuting ^.
 802   }
 803
 804   PV.X = X;
 805   PV.Q = Q;
 806   PV.R = R;
 807   PV.Left = false;
 808   return true;
 809 }
 810
 811
 812 bool PolynomialMultiplyRecognize::scanSelect(SelectInst *SelI,
 813       BasicBlock *LoopB, BasicBlock *PrehB, Value *CIV, ParsedValues &PV,
 814       bool PreScan) {
 815   using namespace PatternMatch;
 816   // The basic pattern for R = P.Q is:
 817   // for i = 0..31
 818   //   R = phi (0, R')
 819   //   if (P & (1 << i))        ; test-bit(P, i)
 820   //     R' = R ^ (Q << i)
 821   //
 822   // Similarly, the basic pattern for R = (P/Q).Q - P
 823   // for i = 0..31
 824   //   R = phi(P, R')
 825   //   if (R & (1 << i))
 826   //     R' = R ^ (Q << i)
 827
 828   // There exist idioms, where instead of Q being shifted left, P is shifted
 829   // right. This produces a result that is shifted right by 32 bits (the
 830   // non-shifted result is 64-bit).
 831   //
 832   // For R = P.Q, this would be:
 833   // for i = 0..31
 834   //   R = phi (0, R')
 835   //   if ((P >> i) & 1)
 836   //     R' = (R >> 1) ^ Q      ; R is cycled through the loop, so it must
 837   //   else                     ; be shifted by 1, not i.
 838   //     R' = R >> 1
 839   //
 840   // And for the inverse:
 841   // for i = 0..31
 842   //   R = phi (P, R')
 843   //   if (R & 1)
 844   //     R' = (R >> 1) ^ Q
 845   //   else
 846   //     R' = R >> 1
 847
 848   // The left-shifting idioms share the same pattern:
 849   //   select (X & (1 << i)) ? R ^ (Q << i) : R
 850   // Similarly for right-shifting idioms:
 851   //   select (X & 1) ? (R >> 1) ^ Q
 852
 853   if (matchLeftShift(SelI, CIV, PV)) {
 854     // If this is a pre-scan, getting this far is sufficient.
 855     if (PreScan)
 856       return true;
 857
 858     // Need to make sure that the SelI goes back into R.
 859     auto *RPhi = dyn_cast<PHINode>(PV.R);
 860     if (!RPhi)
 861       return false;
 862     if (SelI != RPhi->getIncomingValueForBlock(LoopB))
 863       return false;
 864     PV.Res = SelI;
 865
 866     // If X is loop invariant, it must be the input polynomial, and the
 867     // idiom is the basic polynomial multiply.
 868     if (CurLoop->isLoopInvariant(PV.X)) {
 869       PV.P = PV.X;
 870       PV.Inv = false;
 871     } else {
 872       // X is not loop invariant. If X == R, this is the inverse pmpy.
 873       // Otherwise, check for an xor with an invariant value. If the
 874       // variable argument to the xor is R, then this is still a valid
 875       // inverse pmpy.
 876       PV.Inv = true;
 877       if (PV.X != PV.R) {
 878         Value *Var = nullptr, *Inv = nullptr, *X1 = nullptr, *X2 = nullptr;
 879         if (!match(PV.X, m_Xor(m_Value(X1), m_Value(X2))))
 880           return false;
 881         auto *I1 = dyn_cast<Instruction>(X1);
 882         auto *I2 = dyn_cast<Instruction>(X2);
 883         if (!I1 || I1->getParent() != LoopB) {
 884           Var = X2;
 885           Inv = X1;
 886         } else if (!I2 || I2->getParent() != LoopB) {
 887           Var = X1;
 888           Inv = X2;
 889         } else
 890           return false;
 891         if (Var != PV.R)
 892           return false;
 893         PV.M = Inv;
 894       }
 895       // The input polynomial P still needs to be determined. It will be
 896       // the entry value of R.
 897       Value *EntryP = RPhi->getIncomingValueForBlock(PrehB);
 898       PV.P = EntryP;
 899     }
 900
 901     return true;
 902   }
 903
 904   if (matchRightShift(SelI, PV)) {
 905     // If this is an inverse pattern, the Q polynomial must be known at
 906     // compile time.
 907     if (PV.Inv && !isa<ConstantInt>(PV.Q))
 908       return false;
 909     if (PreScan)
 910       return true;
 911     // There is no exact matching of right-shift pmpy.
 912     return false;
 913   }
 914
 915   return false;
 916 }
 917
 918
 919 bool PolynomialMultiplyRecognize::isPromotableTo(Value *Val,
 920       IntegerType *DestTy) {
 921   IntegerType *T = dyn_cast<IntegerType>(Val->getType());
 922   if (!T || T->getBitWidth() > DestTy->getBitWidth())
 923     return false;
 924   if (T->getBitWidth() == DestTy->getBitWidth())
 925     return true;
 926   // Non-instructions are promotable. The reason why an instruction may not
 927   // be promotable is that it may produce a different result if its operands
 928   // and the result are promoted, for example, it may produce more non-zero
 929   // bits. While it would still be possible to represent the proper result
 930   // in a wider type, it may require adding additional instructions (which
 931   // we don't want to do).
 932   Instruction *In = dyn_cast<Instruction>(Val);
 933   if (!In)
 934     return true;
 935   // The bitwidth of the source type is smaller than the destination.
 936   // Check if the individual operation can be promoted.
 937   switch (In->getOpcode()) {
 938     case Instruction::PHI:
 939     case Instruction::ZExt:
 940     case Instruction::And:
 941     case Instruction::Or:
 942     case Instruction::Xor:
 943     case Instruction::LShr: // Shift right is ok.
 944     case Instruction::Select:
 945       return true;
 946     case Instruction::ICmp:
 947       if (CmpInst *CI = cast<CmpInst>(In))
 948         return CI->isEquality() || CI->isUnsigned();
 949       llvm_unreachable("Cast failed unexpectedly");
 950     case Instruction::Add:
 951       return In->hasNoSignedWrap() && In->hasNoUnsignedWrap();
 952   }
 953   return false;
 954 }
 955
 956
 957 void PolynomialMultiplyRecognize::promoteTo(Instruction *In,
 958       IntegerType *DestTy, BasicBlock *LoopB) {
 959   // Leave boolean values alone.
 960   if (!In->getType()->isIntegerTy(1))
 961     In->mutateType(DestTy);
 962   unsigned DestBW = DestTy->getBitWidth();
 963
 964   // Handle PHIs.
 965   if (PHINode *P = dyn_cast<PHINode>(In)) {
 966     unsigned N = P->getNumIncomingValues();
 967     for (unsigned i = 0; i != N; ++i) {
 968       BasicBlock *InB = P->getIncomingBlock(i);
 969       if (InB == LoopB)
 970         continue;
 971       Value *InV = P->getIncomingValue(i);
 972       IntegerType *Ty = cast<IntegerType>(InV->getType());
 973       // Do not promote values in PHI nodes of type i1.
 974       if (Ty != P->getType()) {
 975         // If the value type does not match the PHI type, the PHI type
 976         // must have been promoted.
 977         assert(Ty->getBitWidth() < DestBW);
 978         InV = IRBuilder<>(InB->getTerminator()).CreateZExt(InV, DestTy);
 979         P->setIncomingValue(i, InV);
 980       }
 981     }
 982   } else if (ZExtInst *Z = dyn_cast<ZExtInst>(In)) {
 983     Value *Op = Z->getOperand(0);
 984     if (Op->getType() == Z->getType())
 985       Z->replaceAllUsesWith(Op);
 986     Z->eraseFromParent();
 987     return;
 988   }
 989
 990   // Promote immediates.
 991   for (unsigned i = 0, n = In->getNumOperands(); i != n; ++i) {
 992     if (ConstantInt *CI = dyn_cast<ConstantInt>(In->getOperand(i)))
 993       if (CI->getType()->getBitWidth() < DestBW)
 994         In->setOperand(i, ConstantInt::get(DestTy, CI->getZExtValue()));
 995   }
 996 }
 997
 998
 999 bool PolynomialMultiplyRecognize::promoteTypes(BasicBlock *LoopB,
1000       BasicBlock *ExitB) {
1001   assert(LoopB);
1002   // Skip loops where the exit block has more than one predecessor. The values
1003   // coming from the loop block will be promoted to another type, and so the
1004   // values coming into the exit block from other predecessors would also have
1005   // to be promoted.
1006   if (!ExitB || (ExitB->getSinglePredecessor() != LoopB))
1007     return false;
1008   IntegerType *DestTy = getPmpyType();
1009   // Check if the exit values have types that are no wider than the type
1010   // that we want to promote to.
1011   unsigned DestBW = DestTy->getBitWidth();
1012   for (Instruction &In : *ExitB) {
1013     PHINode *P = dyn_cast<PHINode>(&In);
1014     if (!P)
1015       break;
1016     if (P->getNumIncomingValues() != 1)
1017       return false;
1018     assert(P->getIncomingBlock(0) == LoopB);
1019     IntegerType *T = dyn_cast<IntegerType>(P->getType());
1020     if (!T || T->getBitWidth() > DestBW)
1021       return false;
1022   }
1023
1024   // Check all instructions in the loop.
1025   for (Instruction &In : *LoopB)
1026     if (!In.isTerminator() && !isPromotableTo(&In, DestTy))
1027       return false;
1028
1029   // Perform the promotion.
1030   std::vector<Instruction*> LoopIns;
1031   std::transform(LoopB->begin(), LoopB->end(), std::back_inserter(LoopIns),
1032                  [](Instruction &In) { return &In; });
1033   for (Instruction *In : LoopIns)
1034     promoteTo(In, DestTy, LoopB);
1035
1036   // Fix up the PHI nodes in the exit block.
1037   Instruction *EndI = ExitB->getFirstNonPHI();
1038   BasicBlock::iterator End = EndI ? EndI->getIterator() : ExitB->end();
1039   for (auto I = ExitB->begin(); I != End; ++I) {
1040     PHINode *P = dyn_cast<PHINode>(I);
1041     if (!P)
1042       break;
1043     Type *Ty0 = P->getIncomingValue(0)->getType();
1044     Type *PTy = P->getType();
1045     if (PTy != Ty0) {
1046       assert(Ty0 == DestTy);
1047       // In order to create the trunc, P must have the promoted type.
1048       P->mutateType(Ty0);
1049       Value *T = IRBuilder<>(ExitB, End).CreateTrunc(P, PTy);
1050       // In order for the RAUW to work, the types of P and T must match.
1051       P->mutateType(PTy);
1052       P->replaceAllUsesWith(T);
1053       // Final update of the P's type.
1054       P->mutateType(Ty0);
1055       cast<Instruction>(T)->setOperand(0, P);
1056     }
1057   }
1058
1059   return true;
1060 }
1061
1062
1063 bool PolynomialMultiplyRecognize::findCycle(Value *Out, Value *In,
1064       ValueSeq &Cycle) {
1065   // Out = ..., In, ...
1066   if (Out == In)
1067     return true;
1068
1069   auto *BB = cast<Instruction>(Out)->getParent();
1070   bool HadPhi = false;
1071
1072   for (auto U : Out->users()) {
1073     auto *I = dyn_cast<Instruction>(&*U);
1074     if (I == nullptr || I->getParent() != BB)
1075       continue;
1076     // Make sure that there are no multi-iteration cycles, e.g.
1077     //   p1 = phi(p2)
1078     //   p2 = phi(p1)
1079     // The cycle p1->p2->p1 would span two loop iterations.
1080     // Check that there is only one phi in the cycle.
1081     bool IsPhi = isa<PHINode>(I);
1082     if (IsPhi && HadPhi)
1083       return false;
1084     HadPhi |= IsPhi;
1085     if (Cycle.count(I))
1086       return false;
1087     Cycle.insert(I);
1088     if (findCycle(I, In, Cycle))
1089       break;
1090     Cycle.remove(I);
1091   }
1092   return !Cycle.empty();
1093 }
1094
1095
1096 void PolynomialMultiplyRecognize::classifyCycle(Instruction *DivI,
1097       ValueSeq &Cycle, ValueSeq &Early, ValueSeq &Late) {
1098   // All the values in the cycle that are between the phi node and the
1099   // divider instruction will be classified as "early", all other values
1100   // will be "late".
1101
1102   bool IsE = true;
1103   unsigned I, N = Cycle.size();
1104   for (I = 0; I < N; ++I) {
1105     Value *V = Cycle[I];
1106     if (DivI == V)
1107       IsE = false;
1108     else if (!isa<PHINode>(V))
1109       continue;
1110     // Stop if found either.
1111     break;
1112   }
1113   // "I" is the index of either DivI or the phi node, whichever was first.
1114   // "E" is "false" or "true" respectively.
1115   ValueSeq &First = !IsE ? Early : Late;
1116   for (unsigned J = 0; J < I; ++J)
1117     First.insert(Cycle[J]);
1118
1119   ValueSeq &Second = IsE ? Early : Late;
1120   Second.insert(Cycle[I]);
1121   for (++I; I < N; ++I) {
1122     Value *V = Cycle[I];
1123     if (DivI == V || isa<PHINode>(V))
1124       break;
1125     Second.insert(V);
1126   }
1127
1128   for (; I < N; ++I)
1129     First.insert(Cycle[I]);
1130 }
1131
1132
1133 bool PolynomialMultiplyRecognize::classifyInst(Instruction *UseI,
1134       ValueSeq &Early, ValueSeq &Late) {
1135   // Select is an exception, since the condition value does not have to be
1136   // classified in the same way as the true/false values. The true/false
1137   // values do have to be both early or both late.
1138   if (UseI->getOpcode() == Instruction::Select) {
1139     Value *TV = UseI->getOperand(1), *FV = UseI->getOperand(2);
1140     if (Early.count(TV) || Early.count(FV)) {
1141       if (Late.count(TV) || Late.count(FV))
1142         return false;
1143       Early.insert(UseI);
1144     } else if (Late.count(TV) || Late.count(FV)) {
1145       if (Early.count(TV) || Early.count(FV))
1146         return false;
1147       Late.insert(UseI);
1148     }
1149     return true;
1150   }
1151
1152   // Not sure what would be the example of this, but the code below relies
1153   // on having at least one operand.
1154   if (UseI->getNumOperands() == 0)
1155     return true;
1156
1157   bool AE = true, AL = true;
1158   for (auto &I : UseI->operands()) {
1159     if (Early.count(&*I))
1160       AL = false;
1161     else if (Late.count(&*I))
1162       AE = false;
1163   }
1164   // If the operands appear "all early" and "all late" at the same time,
1165   // then it means that none of them are actually classified as either.
1166   // This is harmless.
1167   if (AE && AL)
1168     return true;
1169   // Conversely, if they are neither "all early" nor "all late", then
1170   // we have a mixture of early and late operands that is not a known
1171   // exception.
1172   if (!AE && !AL)
1173     return false;
1174
1175   // Check that we have covered the two special cases.
1176   assert(AE != AL);
1177
1178   if (AE)
1179     Early.insert(UseI);
1180   else
1181     Late.insert(UseI);
1182   return true;
1183 }
1184
1185
1186 bool PolynomialMultiplyRecognize::commutesWithShift(Instruction *I) {
1187   switch (I->getOpcode()) {
1188     case Instruction::And:
1189     case Instruction::Or:
1190     case Instruction::Xor:
1191     case Instruction::LShr:
1192     case Instruction::Shl:
1193     case Instruction::Select:
1194     case Instruction::ICmp:
1195     case Instruction::PHI:
1196       break;
1197     default:
1198       return false;
1199   }
1200   return true;
1201 }
1202
1203
1204 bool PolynomialMultiplyRecognize::highBitsAreZero(Value *V,
1205       unsigned IterCount) {
1206   auto *T = dyn_cast<IntegerType>(V->getType());
1207   if (!T)
1208     return false;
1209
1210   KnownBits Known(T->getBitWidth());
1211   computeKnownBits(V, Known, DL);
1212   return Known.countMinLeadingZeros() >= IterCount;
1213 }
1214
1215
1216 bool PolynomialMultiplyRecognize::keepsHighBitsZero(Value *V,
1217       unsigned IterCount) {
1218   // Assume that all inputs to the value have the high bits zero.
1219   // Check if the value itself preserves the zeros in the high bits.
1220   if (auto *C = dyn_cast<ConstantInt>(V))
1221     return C->getValue().countLeadingZeros() >= IterCount;
1222
1223   if (auto *I = dyn_cast<Instruction>(V)) {
1224     switch (I->getOpcode()) {
1225       case Instruction::And:
1226       case Instruction::Or:
1227       case Instruction::Xor:
1228       case Instruction::LShr:
1229       case Instruction::Select:
1230       case Instruction::ICmp:
1231       case Instruction::PHI:
1232       case Instruction::ZExt:
1233         return true;
1234     }
1235   }
1236
1237   return false;
1238 }
1239
1240
1241 bool PolynomialMultiplyRecognize::isOperandShifted(Instruction *I, Value *Op) {
1242   unsigned Opc = I->getOpcode();
1243   if (Opc == Instruction::Shl || Opc == Instruction::LShr)
1244     return Op != I->getOperand(1);
1245   return true;
1246 }
1247
1248
1249 bool PolynomialMultiplyRecognize::convertShiftsToLeft(BasicBlock *LoopB,
1250       BasicBlock *ExitB, unsigned IterCount) {
1251   Value *CIV = getCountIV(LoopB);
1252   if (CIV == nullptr)
1253     return false;
1254   auto *CIVTy = dyn_cast<IntegerType>(CIV->getType());
1255   if (CIVTy == nullptr)
1256     return false;
1257
1258   ValueSeq RShifts;
1259   ValueSeq Early, Late, Cycled;
1260
1261   // Find all value cycles that contain logical right shifts by 1.
1262   for (Instruction &I : *LoopB) {
1263     using namespace PatternMatch;
1264     Value *V = nullptr;
1265     if (!match(&I, m_LShr(m_Value(V), m_One())))
1266       continue;
1267     ValueSeq C;
1268     if (!findCycle(&I, V, C))
1269       continue;
1270
1271     // Found a cycle.
1272     C.insert(&I);
1273     classifyCycle(&I, C, Early, Late);
1274     Cycled.insert(C.begin(), C.end());
1275     RShifts.insert(&I);
1276   }
1277
1278   // Find the set of all values affected by the shift cycles, i.e. all
1279   // cycled values, and (recursively) all their users.
1280   ValueSeq Users(Cycled.begin(), Cycled.end());
1281   for (unsigned i = 0; i < Users.size(); ++i) {
1282     Value *V = Users[i];
1283     if (!isa<IntegerType>(V->getType()))
1284       return false;
1285     auto *R = cast<Instruction>(V);
1286     // If the instruction does not commute with shifts, the loop cannot
1287     // be unshifted.
1288     if (!commutesWithShift(R))
1289       return false;
1290     for (auto I = R->user_begin(), E = R->user_end(); I != E; ++I) {
1291       auto *T = cast<Instruction>(*I);
1292       // Skip users from outside of the loop. They will be handled later.
1293       // Also, skip the right-shifts and phi nodes, since they mix early
1294       // and late values.
1295       if (T->getParent() != LoopB || RShifts.count(T) || isa<PHINode>(T))
1296         continue;
1297
1298       Users.insert(T);
1299       if (!classifyInst(T, Early, Late))
1300         return false;
1301     }
1302   }
1303
1304   if (Users.size() == 0)
1305     return false;
1306
1307   // Verify that high bits remain zero.
1308   ValueSeq Internal(Users.begin(), Users.end());
1309   ValueSeq Inputs;
1310   for (unsigned i = 0; i < Internal.size(); ++i) {
1311     auto *R = dyn_cast<Instruction>(Internal[i]);
1312     if (!R)
1313       continue;
1314     for (Value *Op : R->operands()) {
1315       auto *T = dyn_cast<Instruction>(Op);
1316       if (T && T->getParent() != LoopB)
1317         Inputs.insert(Op);
1318       else
1319         Internal.insert(Op);
1320     }
1321   }
1322   for (Value *V : Inputs)
1323     if (!highBitsAreZero(V, IterCount))
1324       return false;
1325   for (Value *V : Internal)
1326     if (!keepsHighBitsZero(V, IterCount))
1327       return false;
1328
1329   // Finally, the work can be done. Unshift each user.
1330   IRBuilder<> IRB(LoopB);
1331   std::map<Value*,Value*> ShiftMap;
1332   typedef std::map<std::pair<Value*,Type*>,Value*> CastMapType;
1333   CastMapType CastMap;
1334
1335   auto upcast = [] (CastMapType &CM, IRBuilder<> &IRB, Value *V,
1336         IntegerType *Ty) -> Value* {
1337     auto H = CM.find(std::make_pair(V, Ty));
1338     if (H != CM.end())
1339       return H->second;
1340     Value *CV = IRB.CreateIntCast(V, Ty, false);
1341     CM.insert(std::make_pair(std::make_pair(V, Ty), CV));
1342     return CV;
1343   };
1344
1345   for (auto I = LoopB->begin(), E = LoopB->end(); I != E; ++I) {
1346     if (isa<PHINode>(I) || !Users.count(&*I))
1347       continue;
1348     using namespace PatternMatch;
1349     // Match lshr x, 1.
1350     Value *V = nullptr;
1351     if (match(&*I, m_LShr(m_Value(V), m_One()))) {
1352       replaceAllUsesOfWithIn(&*I, V, LoopB);
1353       continue;
1354     }
1355     // For each non-cycled operand, replace it with the corresponding
1356     // value shifted left.
1357     for (auto &J : I->operands()) {
1358       Value *Op = J.get();
1359       if (!isOperandShifted(&*I, Op))
1360         continue;
1361       if (Users.count(Op))
1362         continue;
1363       // Skip shifting zeros.
1364       if (isa<ConstantInt>(Op) && cast<ConstantInt>(Op)->isZero())
1365         continue;
1366       // Check if we have already generated a shift for this value.
1367       auto F = ShiftMap.find(Op);
1368       Value *W = (F != ShiftMap.end()) ? F->second : nullptr;
1369       if (W == nullptr) {
1370         IRB.SetInsertPoint(&*I);
1371         // First, the shift amount will be CIV or CIV+1, depending on
1372         // whether the value is early or late. Instead of creating CIV+1,
1373         // do a single shift of the value.
1374         Value *ShAmt = CIV, *ShVal = Op;
1375         auto *VTy = cast<IntegerType>(ShVal->getType());
1376         auto *ATy = cast<IntegerType>(ShAmt->getType());
1377         if (Late.count(&*I))
1378           ShVal = IRB.CreateShl(Op, ConstantInt::get(VTy, 1));
1379         // Second, the types of the shifted value and the shift amount
1380         // must match.
1381         if (VTy != ATy) {
1382           if (VTy->getBitWidth() < ATy->getBitWidth())
1383             ShVal = upcast(CastMap, IRB, ShVal, ATy);
1384           else
1385             ShAmt = upcast(CastMap, IRB, ShAmt, VTy);
1386         }
1387         // Ready to generate the shift and memoize it.
1388         W = IRB.CreateShl(ShVal, ShAmt);
1389         ShiftMap.insert(std::make_pair(Op, W));
1390       }
1391       I->replaceUsesOfWith(Op, W);
1392     }
1393   }
1394
1395   // Update the users outside of the loop to account for having left
1396   // shifts. They would normally be shifted right in the loop, so shift
1397   // them right after the loop exit.
1398   // Take advantage of the loop-closed SSA form, which has all the post-
1399   // loop values in phi nodes.
1400   IRB.SetInsertPoint(ExitB, ExitB->getFirstInsertionPt());
1401   for (auto P = ExitB->begin(), Q = ExitB->end(); P != Q; ++P) {
1402     if (!isa<PHINode>(P))
1403       break;
1404     auto *PN = cast<PHINode>(P);
1405     Value *U = PN->getIncomingValueForBlock(LoopB);
1406     if (!Users.count(U))
1407       continue;
1408     Value *S = IRB.CreateLShr(PN, ConstantInt::get(PN->getType(), IterCount));
1409     PN->replaceAllUsesWith(S);
1410     // The above RAUW will create
1411     //   S = lshr S, IterCount
1412     // so we need to fix it back into
1413     //   S = lshr PN, IterCount
1414     cast<User>(S)->replaceUsesOfWith(S, PN);
1415   }
1416
1417   return true;
1418 }
1419
1420
1421 void PolynomialMultiplyRecognize::cleanupLoopBody(BasicBlock *LoopB) {
1422   for (auto &I : *LoopB)
1423     if (Value *SV = SimplifyInstruction(&I, {DL, &TLI, &DT}))
1424       I.replaceAllUsesWith(SV);
1425
1426   for (auto I = LoopB->begin(), N = I; I != LoopB->end(); I = N) {
1427     N = std::next(I);
1428     RecursivelyDeleteTriviallyDeadInstructions(&*I, &TLI);
1429   }
1430 }
1431
1432
1433 unsigned PolynomialMultiplyRecognize::getInverseMxN(unsigned QP) {
1434   // Arrays of coefficients of Q and the inverse, C.
1435   // Q[i] = coefficient at x^i.
1436   std::array<char,32> Q, C;
1437
1438   for (unsigned i = 0; i < 32; ++i) {
1439     Q[i] = QP & 1;
1440     QP >>= 1;
1441   }
1442   assert(Q[0] == 1);
1443
1444   // Find C, such that
1445   // (Q[n]*x^n + ... + Q[1]*x + Q[0]) * (C[n]*x^n + ... + C[1]*x + C[0]) = 1
1446   //
1447   // For it to have a solution, Q[0] must be 1. Since this is Z2[x], the
1448   // operations * and + are & and ^ respectively.
1449   //
1450   // Find C[i] recursively, by comparing i-th coefficient in the product
1451   // with 0 (or 1 for i=0).
1452   //
1453   // C[0] = 1, since C[0] = Q[0], and Q[0] = 1.
1454   C[0] = 1;
1455   for (unsigned i = 1; i < 32; ++i) {
1456     // Solve for C[i] in:
1457     //   C[0]Q[i] ^ C[1]Q[i-1] ^ ... ^ C[i-1]Q[1] ^ C[i]Q[0] = 0
1458     // This is equivalent to
1459     //   C[0]Q[i] ^ C[1]Q[i-1] ^ ... ^ C[i-1]Q[1] ^ C[i] = 0
1460     // which is
1461     //   C[0]Q[i] ^ C[1]Q[i-1] ^ ... ^ C[i-1]Q[1] = C[i]
1462     unsigned T = 0;
1463     for (unsigned j = 0; j < i; ++j)
1464       T = T ^ (C[j] & Q[i-j]);
1465     C[i] = T;
1466   }
1467
1468   unsigned QV = 0;
1469   for (unsigned i = 0; i < 32; ++i)
1470     if (C[i])
1471       QV |= (1 << i);
1472
1473   return QV;
1474 }
1475
1476
1477 Value *PolynomialMultiplyRecognize::generate(BasicBlock::iterator At,
1478       ParsedValues &PV) {
1479   IRBuilder<> B(&*At);
1480   Module *M = At->getParent()->getParent()->getParent();
1481   Value *PMF = Intrinsic::getDeclaration(M, Intrinsic::hexagon_M4_pmpyw);
1482
1483   Value *P = PV.P, *Q = PV.Q, *P0 = P;
1484   unsigned IC = PV.IterCount;
1485
1486   if (PV.M != nullptr)
1487     P0 = P = B.CreateXor(P, PV.M);
1488
1489   // Create a bit mask to clear the high bits beyond IterCount.
1490   auto *BMI = ConstantInt::get(P->getType(), APInt::getLowBitsSet(32, IC));
1491
1492   if (PV.IterCount != 32)
1493     P = B.CreateAnd(P, BMI);
1494
1495   if (PV.Inv) {
1496     auto *QI = dyn_cast<ConstantInt>(PV.Q);
1497     assert(QI && QI->getBitWidth() <= 32);
1498
1499     // Again, clearing bits beyond IterCount.
1500     unsigned M = (1 << PV.IterCount) - 1;
1501     unsigned Tmp = (QI->getZExtValue() | 1) & M;
1502     unsigned QV = getInverseMxN(Tmp) & M;
1503     auto *QVI = ConstantInt::get(QI->getType(), QV);
1504     P = B.CreateCall(PMF, {P, QVI});
1505     P = B.CreateTrunc(P, QI->getType());
1506     if (IC != 32)
1507       P = B.CreateAnd(P, BMI);
1508   }
1509
1510   Value *R = B.CreateCall(PMF, {P, Q});
1511
1512   if (PV.M != nullptr)
1513     R = B.CreateXor(R, B.CreateIntCast(P0, R->getType(), false));
1514
1515   return R;
1516 }
1517
1518
1519 void PolynomialMultiplyRecognize::setupSimplifier() {
1520   Simp.addRule(
1521     // Sink zext past bitwise operations.
1522     [](Instruction *I, LLVMContext &Ctx) -> Value* {
1523       if (I->getOpcode() != Instruction::ZExt)
1524         return nullptr;
1525       Instruction *T = dyn_cast<Instruction>(I->getOperand(0));
1526       if (!T)
1527         return nullptr;
1528       switch (T->getOpcode()) {
1529         case Instruction::And:
1530         case Instruction::Or:
1531         case Instruction::Xor:
1532           break;
1533         default:
1534           return nullptr;
1535       }
1536       IRBuilder<> B(Ctx);
1537       return B.CreateBinOp(cast<BinaryOperator>(T)->getOpcode(),
1538                            B.CreateZExt(T->getOperand(0), I->getType()),
1539                            B.CreateZExt(T->getOperand(1), I->getType()));
1540     });
1541   Simp.addRule(
1542     // (xor (and x a) (and y a)) -> (and (xor x y) a)
1543     [](Instruction *I, LLVMContext &Ctx) -> Value* {
1544       if (I->getOpcode() != Instruction::Xor)
1545         return nullptr;
1546       Instruction *And0 = dyn_cast<Instruction>(I->getOperand(0));
1547       Instruction *And1 = dyn_cast<Instruction>(I->getOperand(1));
1548       if (!And0 || !And1)
1549         return nullptr;
1550       if (And0->getOpcode() != Instruction::And ||
1551           And1->getOpcode() != Instruction::And)
1552         return nullptr;
1553       if (And0->getOperand(1) != And1->getOperand(1))
1554         return nullptr;
1555       IRBuilder<> B(Ctx);
1556       return B.CreateAnd(B.CreateXor(And0->getOperand(0), And1->getOperand(0)),
1557                          And0->getOperand(1));
1558     });
1559   Simp.addRule(
1560     // (Op (select c x y) z) -> (select c (Op x z) (Op y z))
1561     // (Op x (select c y z)) -> (select c (Op x y) (Op x z))
1562     [](Instruction *I, LLVMContext &Ctx) -> Value* {
1563       BinaryOperator *BO = dyn_cast<BinaryOperator>(I);
1564       if (!BO)
1565         return nullptr;
1566       Instruction::BinaryOps Op = BO->getOpcode();
1567       if (SelectInst *Sel = dyn_cast<SelectInst>(BO->getOperand(0))) {
1568         IRBuilder<> B(Ctx);
1569         Value *X = Sel->getTrueValue(), *Y = Sel->getFalseValue();
1570         Value *Z = BO->getOperand(1);
1571         return B.CreateSelect(Sel->getCondition(),
1572                               B.CreateBinOp(Op, X, Z),
1573                               B.CreateBinOp(Op, Y, Z));
1574       }
1575       if (SelectInst *Sel = dyn_cast<SelectInst>(BO->getOperand(1))) {
1576         IRBuilder<> B(Ctx);
1577         Value *X = BO->getOperand(0);
1578         Value *Y = Sel->getTrueValue(), *Z = Sel->getFalseValue();
1579         return B.CreateSelect(Sel->getCondition(),
1580                               B.CreateBinOp(Op, X, Y),
1581                               B.CreateBinOp(Op, X, Z));
1582       }
1583       return nullptr;
1584     });
1585   Simp.addRule(
1586     // (select c (select c x y) z) -> (select c x z)
1587     // (select c x (select c y z)) -> (select c x z)
1588     [](Instruction *I, LLVMContext &Ctx) -> Value* {
1589       SelectInst *Sel = dyn_cast<SelectInst>(I);
1590       if (!Sel)
1591         return nullptr;
1592       IRBuilder<> B(Ctx);
1593       Value *C = Sel->getCondition();
1594       if (SelectInst *Sel0 = dyn_cast<SelectInst>(Sel->getTrueValue())) {
1595         if (Sel0->getCondition() == C)
1596           return B.CreateSelect(C, Sel0->getTrueValue(), Sel->getFalseValue());
1597       }
1598       if (SelectInst *Sel1 = dyn_cast<SelectInst>(Sel->getFalseValue())) {
1599         if (Sel1->getCondition() == C)
1600           return B.CreateSelect(C, Sel->getTrueValue(), Sel1->getFalseValue());
1601       }
1602       return nullptr;
1603     });
1604   Simp.addRule(
1605     // (or (lshr x 1) 0x800.0) -> (xor (lshr x 1) 0x800.0)
1606     [](Instruction *I, LLVMContext &Ctx) -> Value* {
1607       if (I->getOpcode() != Instruction::Or)
1608         return nullptr;
1609       Instruction *LShr = dyn_cast<Instruction>(I->getOperand(0));
1610       if (!LShr || LShr->getOpcode() != Instruction::LShr)
1611         return nullptr;
1612       ConstantInt *One = dyn_cast<ConstantInt>(LShr->getOperand(1));
1613       if (!One || One->getZExtValue() != 1)
1614         return nullptr;
1615       ConstantInt *Msb = dyn_cast<ConstantInt>(I->getOperand(1));
1616       if (!Msb || Msb->getZExtValue() != Msb->getType()->getSignBit())
1617         return nullptr;
1618       return IRBuilder<>(Ctx).CreateXor(LShr, Msb);
1619     });
1620   Simp.addRule(
1621     // (lshr (BitOp x y) c) -> (BitOp (lshr x c) (lshr y c))
1622     [](Instruction *I, LLVMContext &Ctx) -> Value* {
1623       if (I->getOpcode() != Instruction::LShr)
1624         return nullptr;
1625       BinaryOperator *BitOp = dyn_cast<BinaryOperator>(I->getOperand(0));
1626       if (!BitOp)
1627         return nullptr;
1628       switch (BitOp->getOpcode()) {
1629         case Instruction::And:
1630         case Instruction::Or:
1631         case Instruction::Xor:
1632           break;
1633         default:
1634           return nullptr;
1635       }
1636       IRBuilder<> B(Ctx);
1637       Value *S = I->getOperand(1);
1638       return B.CreateBinOp(BitOp->getOpcode(),
1639                 B.CreateLShr(BitOp->getOperand(0), S),
1640                 B.CreateLShr(BitOp->getOperand(1), S));
1641     });
1642   Simp.addRule(
1643     // (BitOp1 (BitOp2 x a) b) -> (BitOp2 x (BitOp1 a b))
1644     [](Instruction *I, LLVMContext &Ctx) -> Value* {
1645       auto IsBitOp = [](unsigned Op) -> bool {
1646         switch (Op) {
1647           case Instruction::And:
1648           case Instruction::Or:
1649           case Instruction::Xor:
1650             return true;
1651         }
1652         return false;
1653       };
1654       BinaryOperator *BitOp1 = dyn_cast<BinaryOperator>(I);
1655       if (!BitOp1 || !IsBitOp(BitOp1->getOpcode()))
1656         return nullptr;
1657       BinaryOperator *BitOp2 = dyn_cast<BinaryOperator>(BitOp1->getOperand(0));
1658       if (!BitOp2 || !IsBitOp(BitOp2->getOpcode()))
1659         return nullptr;
1660       ConstantInt *CA = dyn_cast<ConstantInt>(BitOp2->getOperand(1));
1661       ConstantInt *CB = dyn_cast<ConstantInt>(BitOp1->getOperand(1));
1662       if (!CA || !CB)
1663         return nullptr;
1664       IRBuilder<> B(Ctx);
1665       Value *X = BitOp2->getOperand(0);
1666       return B.CreateBinOp(BitOp2->getOpcode(), X,
1667                 B.CreateBinOp(BitOp1->getOpcode(), CA, CB));
1668     });
1669 }
1670
1671
1672 bool PolynomialMultiplyRecognize::recognize() {
1673   DEBUG(dbgs() << "Starting PolynomialMultiplyRecognize on loop\n"
1674                << *CurLoop << '\n');
1675   // Restrictions:
1676   // - The loop must consist of a single block.
1677   // - The iteration count must be known at compile-time.
1678   // - The loop must have an induction variable starting from 0, and
1679   //   incremented in each iteration of the loop.
1680   BasicBlock *LoopB = CurLoop->getHeader();
1681   DEBUG(dbgs() << "Loop header:\n" << *LoopB);
1682
1683   if (LoopB != CurLoop->getLoopLatch())
1684     return false;
1685   BasicBlock *ExitB = CurLoop->getExitBlock();
1686   if (ExitB == nullptr)
1687     return false;
1688   BasicBlock *EntryB = CurLoop->getLoopPreheader();
1689   if (EntryB == nullptr)
1690     return false;
1691
1692   unsigned IterCount = 0;
1693   const SCEV *CT = SE.getBackedgeTakenCount(CurLoop);
1694   if (isa<SCEVCouldNotCompute>(CT))
1695     return false;
1696   if (auto *CV = dyn_cast<SCEVConstant>(CT))
1697     IterCount = CV->getValue()->getZExtValue() + 1;
1698
1699   Value *CIV = getCountIV(LoopB);
1700   ParsedValues PV;
1701   PV.IterCount = IterCount;
1702   DEBUG(dbgs() << "Loop IV: " << *CIV << "\nIterCount: " << IterCount << '\n');
1703
1704   setupSimplifier();
1705
1706   // Perform a preliminary scan of select instructions to see if any of them
1707   // looks like a generator of the polynomial multiply steps. Assume that a
1708   // loop can only contain a single transformable operation, so stop the
1709   // traversal after the first reasonable candidate was found.
1710   // XXX: Currently this approach can modify the loop before being 100% sure
1711   // that the transformation can be carried out.
1712   bool FoundPreScan = false;
1713   for (Instruction &In : *LoopB) {
1714     SelectInst *SI = dyn_cast<SelectInst>(&In);
1715     if (!SI)
1716       continue;
1717
1718     Simplifier::Context C(SI);
1719     Value *T = Simp.simplify(C);
1720     SelectInst *SelI = (T && isa<SelectInst>(T)) ? cast<SelectInst>(T) : SI;
1721     DEBUG(dbgs() << "scanSelect(pre-scan): " << PE(C, SelI) << '\n');
1722     if (scanSelect(SelI, LoopB, EntryB, CIV, PV, true)) {
1723       FoundPreScan = true;
1724       if (SelI != SI) {
1725         Value *NewSel = C.materialize(LoopB, SI->getIterator());
1726         SI->replaceAllUsesWith(NewSel);
1727         RecursivelyDeleteTriviallyDeadInstructions(SI, &TLI);
1728       }
1729       break;
1730     }
1731   }
1732
1733   if (!FoundPreScan) {
1734     DEBUG(dbgs() << "Have not found candidates for pmpy\n");
1735     return false;
1736   }
1737
1738   if (!PV.Left) {
1739     // The right shift version actually only returns the higher bits of
1740     // the result (each iteration discards the LSB). If we want to convert it
1741     // to a left-shifting loop, the working data type must be at least as
1742     // wide as the target's pmpy instruction.
1743     if (!promoteTypes(LoopB, ExitB))
1744       return false;
1745     convertShiftsToLeft(LoopB, ExitB, IterCount);
1746     cleanupLoopBody(LoopB);
1747   }
1748
1749   // Scan the loop again, find the generating select instruction.
1750   bool FoundScan = false;
1751   for (Instruction &In : *LoopB) {
1752     SelectInst *SelI = dyn_cast<SelectInst>(&In);
1753     if (!SelI)
1754       continue;
1755     DEBUG(dbgs() << "scanSelect: " << *SelI << '\n');
1756     FoundScan = scanSelect(SelI, LoopB, EntryB, CIV, PV, false);
1757     if (FoundScan)
1758       break;
1759   }
1760   assert(FoundScan);
1761
1762   DEBUG({
1763     StringRef PP = (PV.M ? "(P+M)" : "P");
1764     if (!PV.Inv)
1765       dbgs() << "Found pmpy idiom: R = " << PP << ".Q\n";
1766     else
1767       dbgs() << "Found inverse pmpy idiom: R = (" << PP << "/Q).Q) + "
1768              << PP << "\n";
1769     dbgs() << "  Res:" << *PV.Res << "\n  P:" << *PV.P << "\n";
1770     if (PV.M)
1771       dbgs() << "  M:" << *PV.M << "\n";
1772     dbgs() << "  Q:" << *PV.Q << "\n";
1773     dbgs() << "  Iteration count:" << PV.IterCount << "\n";
1774   });
1775
1776   BasicBlock::iterator At(EntryB->getTerminator());
1777   Value *PM = generate(At, PV);
1778   if (PM == nullptr)
1779     return false;
1780
1781   if (PM->getType() != PV.Res->getType())
1782     PM = IRBuilder<>(&*At).CreateIntCast(PM, PV.Res->getType(), false);
1783
1784   PV.Res->replaceAllUsesWith(PM);
1785   PV.Res->eraseFromParent();
1786   return true;
1787 }
1788
1789
1790 unsigned HexagonLoopIdiomRecognize::getStoreSizeInBytes(StoreInst *SI) {
1791   uint64_t SizeInBits = DL->getTypeSizeInBits(SI->getValueOperand()->getType());
1792   assert(((SizeInBits & 7) || (SizeInBits >> 32) == 0) &&
1793          "Don't overflow unsigned.");
1794   return (unsigned)SizeInBits >> 3;
1795 }
1796
1797
1798 int HexagonLoopIdiomRecognize::getSCEVStride(const SCEVAddRecExpr *S) {
1799   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
1800     return SC->getAPInt().getSExtValue();
1801   return 0;
1802 }
1803
1804
1805 bool HexagonLoopIdiomRecognize::isLegalStore(Loop *CurLoop, StoreInst *SI) {
1806   // Allow volatile stores if HexagonVolatileMemcpy is enabled.
1807   if (!(SI->isVolatile() && HexagonVolatileMemcpy) && !SI->isSimple())
1808     return false;
1809
1810   Value *StoredVal = SI->getValueOperand();
1811   Value *StorePtr = SI->getPointerOperand();
1812
1813   // Reject stores that are so large that they overflow an unsigned.
1814   uint64_t SizeInBits = DL->getTypeSizeInBits(StoredVal->getType());
1815   if ((SizeInBits & 7) || (SizeInBits >> 32) != 0)
1816     return false;
1817
1818   // See if the pointer expression is an AddRec like {base,+,1} on the current
1819   // loop, which indicates a strided store.  If we have something else, it's a
1820   // random store we can't handle.
1821   auto *StoreEv = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
1822   if (!StoreEv || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine())
1823     return false;
1824
1825   // Check to see if the stride matches the size of the store.  If so, then we
1826   // know that every byte is touched in the loop.
1827   int Stride = getSCEVStride(StoreEv);
1828   if (Stride == 0)
1829     return false;
1830   unsigned StoreSize = getStoreSizeInBytes(SI);
1831   if (StoreSize != unsigned(std::abs(Stride)))
1832     return false;
1833
1834   // The store must be feeding a non-volatile load.
1835   LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand());
1836   if (!LI || !LI->isSimple())
1837     return false;
1838
1839   // See if the pointer expression is an AddRec like {base,+,1} on the current
1840   // loop, which indicates a strided load.  If we have something else, it's a
1841   // random load we can't handle.
1842   Value *LoadPtr = LI->getPointerOperand();
1843   auto *LoadEv = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LoadPtr));
1844   if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine())
1845     return false;
1846
1847   // The store and load must share the same stride.
1848   if (StoreEv->getOperand(1) != LoadEv->getOperand(1))
1849     return false;
1850
1851   // Success.  This store can be converted into a memcpy.
1852   return true;
1853 }
1854
1855
1856 /// mayLoopAccessLocation - Return true if the specified loop might access the
1857 /// specified pointer location, which is a loop-strided access.  The 'Access'
1858 /// argument specifies what the verboten forms of access are (read or write).
1859 static bool
1860 mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
1861                       const SCEV *BECount, unsigned StoreSize,
1862                       AliasAnalysis &AA,
1863                       SmallPtrSetImpl<Instruction *> &Ignored) {
1864   // Get the location that may be stored across the loop.  Since the access
1865   // is strided positively through memory, we say that the modified location
1866   // starts at the pointer and has infinite size.
1867   uint64_t AccessSize = MemoryLocation::UnknownSize;
1868
1869   // If the loop iterates a fixed number of times, we can refine the access
1870   // size to be exactly the size of the memset, which is (BECount+1)*StoreSize
1871   if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
1872     AccessSize = (BECst->getValue()->getZExtValue() + 1) * StoreSize;
1873
1874   // TODO: For this to be really effective, we have to dive into the pointer
1875   // operand in the store.  Store to &A[i] of 100 will always return may alias
1876   // with store of &A[100], we need to StoreLoc to be "A" with size of 100,
1877   // which will then no-alias a store to &A[100].
1878   MemoryLocation StoreLoc(Ptr, AccessSize);
1879
1880   for (auto *B : L->blocks())
1881     for (auto &I : *B)
1882       if (Ignored.count(&I) == 0 && (AA.getModRefInfo(&I, StoreLoc) & Access))
1883         return true;
1884
1885   return false;
1886 }
1887
1888
1889 void HexagonLoopIdiomRecognize::collectStores(Loop *CurLoop, BasicBlock *BB,
1890       SmallVectorImpl<StoreInst*> &Stores) {
1891   Stores.clear();
1892   for (Instruction &I : *BB)
1893     if (StoreInst *SI = dyn_cast<StoreInst>(&I))
1894       if (isLegalStore(CurLoop, SI))
1895         Stores.push_back(SI);
1896 }
1897
1898
1899 bool HexagonLoopIdiomRecognize::processCopyingStore(Loop *CurLoop,
1900       StoreInst *SI, const SCEV *BECount) {
1901   assert((SI->isSimple() || (SI->isVolatile() && HexagonVolatileMemcpy)) &&
1902          "Expected only non-volatile stores, or Hexagon-specific memcpy"
1903          "to volatile destination.");
1904
1905   Value *StorePtr = SI->getPointerOperand();
1906   auto *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
1907   unsigned Stride = getSCEVStride(StoreEv);
1908   unsigned StoreSize = getStoreSizeInBytes(SI);
1909   if (Stride != StoreSize)
1910     return false;
1911
1912   // See if the pointer expression is an AddRec like {base,+,1} on the current
1913   // loop, which indicates a strided load.  If we have something else, it's a
1914   // random load we can't handle.
1915   LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand());
1916   auto *LoadEv = cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand()));
1917
1918   // The trip count of the loop and the base pointer of the addrec SCEV is
1919   // guaranteed to be loop invariant, which means that it should dominate the
1920   // header.  This allows us to insert code for it in the preheader.
1921   BasicBlock *Preheader = CurLoop->getLoopPreheader();
1922   Instruction *ExpPt = Preheader->getTerminator();
1923   IRBuilder<> Builder(ExpPt);
1924   SCEVExpander Expander(*SE, *DL, "hexagon-loop-idiom");
1925
1926   Type *IntPtrTy = Builder.getIntPtrTy(*DL, SI->getPointerAddressSpace());
1927
1928   // Okay, we have a strided store "p[i]" of a loaded value.  We can turn
1929   // this into a memcpy/memmove in the loop preheader now if we want.  However,
1930   // this would be unsafe to do if there is anything else in the loop that may
1931   // read or write the memory region we're storing to.  For memcpy, this
1932   // includes the load that feeds the stores.  Check for an alias by generating
1933   // the base address and checking everything.
1934   Value *StoreBasePtr = Expander.expandCodeFor(StoreEv->getStart(),
1935       Builder.getInt8PtrTy(SI->getPointerAddressSpace()), ExpPt);
1936   Value *LoadBasePtr = nullptr;
1937
1938   bool Overlap = false;
1939   bool DestVolatile = SI->isVolatile();
1940   Type *BECountTy = BECount->getType();
1941
1942   if (DestVolatile) {
1943     // The trip count must fit in i32, since it is the type of the "num_words"
1944     // argument to hexagon_memcpy_forward_vp4cp4n2.
1945     if (StoreSize != 4 || DL->getTypeSizeInBits(BECountTy) > 32) {
1946 CleanupAndExit:
1947       // If we generated new code for the base pointer, clean up.
1948       Expander.clear();
1949       if (StoreBasePtr && (LoadBasePtr != StoreBasePtr)) {
1950         RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
1951         StoreBasePtr = nullptr;
1952       }
1953       if (LoadBasePtr) {
1954         RecursivelyDeleteTriviallyDeadInstructions(LoadBasePtr, TLI);
1955         LoadBasePtr = nullptr;
1956       }
1957       return false;
1958     }
1959   }
1960
1961   SmallPtrSet<Instruction*, 2> Ignore1;
1962   Ignore1.insert(SI);
1963   if (mayLoopAccessLocation(StoreBasePtr, MRI_ModRef, CurLoop, BECount,
1964                             StoreSize, *AA, Ignore1)) {
1965     // Check if the load is the offending instruction.
1966     Ignore1.insert(LI);
1967     if (mayLoopAccessLocation(StoreBasePtr, MRI_ModRef, CurLoop, BECount,
1968                               StoreSize, *AA, Ignore1)) {
1969       // Still bad. Nothing we can do.
1970       goto CleanupAndExit;
1971     }
1972     // It worked with the load ignored.
1973     Overlap = true;
1974   }
1975
1976   if (!Overlap) {
1977     if (DisableMemcpyIdiom || !HasMemcpy)
1978       goto CleanupAndExit;
1979   } else {
1980     // Don't generate memmove if this function will be inlined. This is
1981     // because the caller will undergo this transformation after inlining.
1982     Function *Func = CurLoop->getHeader()->getParent();
1983     if (Func->hasFnAttribute(Attribute::AlwaysInline))
1984       goto CleanupAndExit;
1985
1986     // In case of a memmove, the call to memmove will be executed instead
1987     // of the loop, so we need to make sure that there is nothing else in
1988     // the loop than the load, store and instructions that these two depend
1989     // on.
1990     SmallVector<Instruction*,2> Insts;
1991     Insts.push_back(SI);
1992     Insts.push_back(LI);
1993     if (!coverLoop(CurLoop, Insts))
1994       goto CleanupAndExit;
1995
1996     if (DisableMemmoveIdiom || !HasMemmove)
1997       goto CleanupAndExit;
1998     bool IsNested = CurLoop->getParentLoop() != 0;
1999     if (IsNested && OnlyNonNestedMemmove)
2000       goto CleanupAndExit;
2001   }
2002
2003   // For a memcpy, we have to make sure that the input array is not being
2004   // mutated by the loop.
2005   LoadBasePtr = Expander.expandCodeFor(LoadEv->getStart(),
2006       Builder.getInt8PtrTy(LI->getPointerAddressSpace()), ExpPt);
2007
2008   SmallPtrSet<Instruction*, 2> Ignore2;
2009   Ignore2.insert(SI);
2010   if (mayLoopAccessLocation(LoadBasePtr, MRI_Mod, CurLoop, BECount, StoreSize,
2011                             *AA, Ignore2))
2012     goto CleanupAndExit;
2013
2014   // Check the stride.
2015   bool StridePos = getSCEVStride(LoadEv) >= 0;
2016
2017   // Currently, the volatile memcpy only emulates traversing memory forward.
2018   if (!StridePos && DestVolatile)
2019     goto CleanupAndExit;
2020
2021   bool RuntimeCheck = (Overlap || DestVolatile);
2022
2023   BasicBlock *ExitB;
2024   if (RuntimeCheck) {
2025     // The runtime check needs a single exit block.
2026     SmallVector<BasicBlock*, 8> ExitBlocks;
2027     CurLoop->getUniqueExitBlocks(ExitBlocks);
2028     if (ExitBlocks.size() != 1)
2029       goto CleanupAndExit;
2030     ExitB = ExitBlocks[0];
2031   }
2032
2033   // The # stored bytes is (BECount+1)*Size.  Expand the trip count out to
2034   // pointer size if it isn't already.
2035   LLVMContext &Ctx = SI->getContext();
2036   BECount = SE->getTruncateOrZeroExtend(BECount, IntPtrTy);
2037   unsigned Alignment = std::min(SI->getAlignment(), LI->getAlignment());
2038   DebugLoc DLoc = SI->getDebugLoc();
2039
2040   const SCEV *NumBytesS =
2041       SE->getAddExpr(BECount, SE->getOne(IntPtrTy), SCEV::FlagNUW);
2042   if (StoreSize != 1)
2043     NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtrTy, StoreSize),
2044                                SCEV::FlagNUW);
2045   Value *NumBytes = Expander.expandCodeFor(NumBytesS, IntPtrTy, ExpPt);
2046   if (Instruction *In = dyn_cast<Instruction>(NumBytes))
2047     if (Value *Simp = SimplifyInstruction(In, {*DL, TLI, DT}))
2048       NumBytes = Simp;
2049
2050   CallInst *NewCall;
2051
2052   if (RuntimeCheck) {
2053     unsigned Threshold = RuntimeMemSizeThreshold;
2054     if (ConstantInt *CI = dyn_cast<ConstantInt>(NumBytes)) {
2055       uint64_t C = CI->getZExtValue();
2056       if (Threshold != 0 && C < Threshold)
2057         goto CleanupAndExit;
2058       if (C < CompileTimeMemSizeThreshold)
2059         goto CleanupAndExit;
2060     }
2061
2062     BasicBlock *Header = CurLoop->getHeader();
2063     Function *Func = Header->getParent();
2064     Loop *ParentL = LF->getLoopFor(Preheader);
2065     StringRef HeaderName = Header->getName();
2066
2067     // Create a new (empty) preheader, and update the PHI nodes in the
2068     // header to use the new preheader.
2069     BasicBlock *NewPreheader = BasicBlock::Create(Ctx, HeaderName+".rtli.ph",
2070                                                   Func, Header);
2071     if (ParentL)
2072       ParentL->addBasicBlockToLoop(NewPreheader, *LF);
2073     IRBuilder<>(NewPreheader).CreateBr(Header);
2074     for (auto &In : *Header) {
2075       PHINode *PN = dyn_cast<PHINode>(&In);
2076       if (!PN)
2077         break;
2078       int bx = PN->getBasicBlockIndex(Preheader);
2079       if (bx >= 0)
2080         PN->setIncomingBlock(bx, NewPreheader);
2081     }
2082     DT->addNewBlock(NewPreheader, Preheader);
2083     DT->changeImmediateDominator(Header, NewPreheader);
2084
2085     // Check for safe conditions to execute memmove.
2086     // If stride is positive, copying things from higher to lower addresses
2087     // is equivalent to memmove.  For negative stride, it's the other way
2088     // around.  Copying forward in memory with positive stride may not be
2089     // same as memmove since we may be copying values that we just stored
2090     // in some previous iteration.
2091     Value *LA = Builder.CreatePtrToInt(LoadBasePtr, IntPtrTy);
2092     Value *SA = Builder.CreatePtrToInt(StoreBasePtr, IntPtrTy);
2093     Value *LowA = StridePos ? SA : LA;
2094     Value *HighA = StridePos ? LA : SA;
2095     Value *CmpA = Builder.CreateICmpULT(LowA, HighA);
2096     Value *Cond = CmpA;
2097
2098     // Check for distance between pointers.
2099     Value *Dist = Builder.CreateSub(HighA, LowA);
2100     Value *CmpD = Builder.CreateICmpSLT(NumBytes, Dist);
2101     Value *CmpEither = Builder.CreateOr(Cond, CmpD);
2102     Cond = CmpEither;
2103
2104     if (Threshold != 0) {
2105       Type *Ty = NumBytes->getType();
2106       Value *Thr = ConstantInt::get(Ty, Threshold);
2107       Value *CmpB = Builder.CreateICmpULT(Thr, NumBytes);
2108       Value *CmpBoth = Builder.CreateAnd(Cond, CmpB);
2109       Cond = CmpBoth;
2110     }
2111     BasicBlock *MemmoveB = BasicBlock::Create(Ctx, Header->getName()+".rtli",
2112                                               Func, NewPreheader);
2113     if (ParentL)
2114       ParentL->addBasicBlockToLoop(MemmoveB, *LF);
2115     Instruction *OldT = Preheader->getTerminator();
2116     Builder.CreateCondBr(Cond, MemmoveB, NewPreheader);
2117     OldT->eraseFromParent();
2118     Preheader->setName(Preheader->getName()+".old");
2119     DT->addNewBlock(MemmoveB, Preheader);
2120     // Find the new immediate dominator of the exit block.
2121     BasicBlock *ExitD = Preheader;
2122     for (auto PI = pred_begin(ExitB), PE = pred_end(ExitB); PI != PE; ++PI) {
2123       BasicBlock *PB = *PI;
2124       ExitD = DT->findNearestCommonDominator(ExitD, PB);
2125       if (!ExitD)
2126         break;
2127     }
2128     // If the prior immediate dominator of ExitB was dominated by the
2129     // old preheader, then the old preheader becomes the new immediate
2130     // dominator.  Otherwise don't change anything (because the newly
2131     // added blocks are dominated by the old preheader).
2132     if (ExitD && DT->dominates(Preheader, ExitD)) {
2133       DomTreeNode *BN = DT->getNode(ExitB);
2134       DomTreeNode *DN = DT->getNode(ExitD);
2135       BN->setIDom(DN);
2136     }
2137
2138     // Add a call to memmove to the conditional block.
2139     IRBuilder<> CondBuilder(MemmoveB);
2140     CondBuilder.CreateBr(ExitB);
2141     CondBuilder.SetInsertPoint(MemmoveB->getTerminator());
2142
2143     if (DestVolatile) {
2144       Type *Int32Ty = Type::getInt32Ty(Ctx);
2145       Type *Int32PtrTy = Type::getInt32PtrTy(Ctx);
2146       Type *VoidTy = Type::getVoidTy(Ctx);
2147       Module *M = Func->getParent();
2148       Constant *CF = M->getOrInsertFunction(HexagonVolatileMemcpyName, VoidTy,
2149                                             Int32PtrTy, Int32PtrTy, Int32Ty);
2150       Function *Fn = cast<Function>(CF);
2151       Fn->setLinkage(Function::ExternalLinkage);
2152
2153       const SCEV *OneS = SE->getConstant(Int32Ty, 1);
2154       const SCEV *BECount32 = SE->getTruncateOrZeroExtend(BECount, Int32Ty);
2155       const SCEV *NumWordsS = SE->getAddExpr(BECount32, OneS, SCEV::FlagNUW);
2156       Value *NumWords = Expander.expandCodeFor(NumWordsS, Int32Ty,
2157                                                MemmoveB->getTerminator());
2158       if (Instruction *In = dyn_cast<Instruction>(NumWords))
2159         if (Value *Simp = SimplifyInstruction(In, {*DL, TLI, DT}))
2160           NumWords = Simp;
2161
2162       Value *Op0 = (StoreBasePtr->getType() == Int32PtrTy)
2163                       ? StoreBasePtr
2164                       : CondBuilder.CreateBitCast(StoreBasePtr, Int32PtrTy);
2165       Value *Op1 = (LoadBasePtr->getType() == Int32PtrTy)
2166                       ? LoadBasePtr
2167                       : CondBuilder.CreateBitCast(LoadBasePtr, Int32PtrTy);
2168       NewCall = CondBuilder.CreateCall(Fn, {Op0, Op1, NumWords});
2169     } else {
2170       NewCall = CondBuilder.CreateMemMove(StoreBasePtr, LoadBasePtr,
2171                                           NumBytes, Alignment);
2172     }
2173   } else {
2174     NewCall = Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr,
2175                                    NumBytes, Alignment);
2176     // Okay, the memcpy has been formed.  Zap the original store and
2177     // anything that feeds into it.
2178     RecursivelyDeleteTriviallyDeadInstructions(SI, TLI);
2179   }
2180
2181   NewCall->setDebugLoc(DLoc);
2182
2183   DEBUG(dbgs() << "  Formed " << (Overlap ? "memmove: " : "memcpy: ")
2184                << *NewCall << "\n"
2185                << "    from load ptr=" << *LoadEv << " at: " << *LI << "\n"
2186                << "    from store ptr=" << *StoreEv << " at: " << *SI << "\n");
2187
2188   return true;
2189 }
2190
2191
2192 // \brief Check if the instructions in Insts, together with their dependencies
2193 // cover the loop in the sense that the loop could be safely eliminated once
2194 // the instructions in Insts are removed.
2195 bool HexagonLoopIdiomRecognize::coverLoop(Loop *L,
2196       SmallVectorImpl<Instruction*> &Insts) const {
2197   SmallSet<BasicBlock*,8> LoopBlocks;
2198   for (auto *B : L->blocks())
2199     LoopBlocks.insert(B);
2200
2201   SetVector<Instruction*> Worklist(Insts.begin(), Insts.end());
2202
2203   // Collect all instructions from the loop that the instructions in Insts
2204   // depend on (plus their dependencies, etc.).  These instructions will
2205   // constitute the expression trees that feed those in Insts, but the trees
2206   // will be limited only to instructions contained in the loop.
2207   for (unsigned i = 0; i < Worklist.size(); ++i) {
2208     Instruction *In = Worklist[i];
2209     for (auto I = In->op_begin(), E = In->op_end(); I != E; ++I) {
2210       Instruction *OpI = dyn_cast<Instruction>(I);
2211       if (!OpI)
2212         continue;
2213       BasicBlock *PB = OpI->getParent();
2214       if (!LoopBlocks.count(PB))
2215         continue;
2216       Worklist.insert(OpI);
2217     }
2218   }
2219
2220   // Scan all instructions in the loop, if any of them have a user outside
2221   // of the loop, or outside of the expressions collected above, then either
2222   // the loop has a side-effect visible outside of it, or there are
2223   // instructions in it that are not involved in the original set Insts.
2224   for (auto *B : L->blocks()) {
2225     for (auto &In : *B) {
2226       if (isa<BranchInst>(In) || isa<DbgInfoIntrinsic>(In))
2227         continue;
2228       if (!Worklist.count(&In) && In.mayHaveSideEffects())
2229         return false;
2230       for (const auto &K : In.users()) {
2231         Instruction *UseI = dyn_cast<Instruction>(K);
2232         if (!UseI)
2233           continue;
2234         BasicBlock *UseB = UseI->getParent();
2235         if (LF->getLoopFor(UseB) != L)
2236           return false;
2237       }
2238     }
2239   }
2240
2241   return true;
2242 }
2243
2244 /// runOnLoopBlock - Process the specified block, which lives in a counted loop
2245 /// with the specified backedge count.  This block is known to be in the current
2246 /// loop and not in any subloops.
2247 bool HexagonLoopIdiomRecognize::runOnLoopBlock(Loop *CurLoop, BasicBlock *BB,
2248       const SCEV *BECount, SmallVectorImpl<BasicBlock*> &ExitBlocks) {
2249   // We can only promote stores in this block if they are unconditionally
2250   // executed in the loop.  For a block to be unconditionally executed, it has
2251   // to dominate all the exit blocks of the loop.  Verify this now.
2252   auto DominatedByBB = [this,BB] (BasicBlock *EB) -> bool {
2253     return DT->dominates(BB, EB);
2254   };
2255   if (!std::all_of(ExitBlocks.begin(), ExitBlocks.end(), DominatedByBB))
2256     return false;
2257
2258   bool MadeChange = false;
2259   // Look for store instructions, which may be optimized to memset/memcpy.
2260   SmallVector<StoreInst*,8> Stores;
2261   collectStores(CurLoop, BB, Stores);
2262
2263   // Optimize the store into a memcpy, if it feeds an similarly strided load.
2264   for (auto &SI : Stores)
2265     MadeChange |= processCopyingStore(CurLoop, SI, BECount);
2266
2267   return MadeChange;
2268 }
2269
2270
2271 bool HexagonLoopIdiomRecognize::runOnCountableLoop(Loop *L) {
2272   PolynomialMultiplyRecognize PMR(L, *DL, *DT, *TLI, *SE);
2273   if (PMR.recognize())
2274     return true;
2275
2276   if (!HasMemcpy && !HasMemmove)
2277     return false;
2278
2279   const SCEV *BECount = SE->getBackedgeTakenCount(L);
2280   assert(!isa<SCEVCouldNotCompute>(BECount) &&
2281          "runOnCountableLoop() called on a loop without a predictable"
2282          "backedge-taken count");
2283
2284   SmallVector<BasicBlock *, 8> ExitBlocks;
2285   L->getUniqueExitBlocks(ExitBlocks);
2286
2287   bool Changed = false;
2288
2289   // Scan all the blocks in the loop that are not in subloops.
2290   for (auto *BB : L->getBlocks()) {
2291     // Ignore blocks in subloops.
2292     if (LF->getLoopFor(BB) != L)
2293       continue;
2294     Changed |= runOnLoopBlock(L, BB, BECount, ExitBlocks);
2295   }
2296
2297   return Changed;
2298 }
2299
2300
2301 bool HexagonLoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
2302   const Module &M = *L->getHeader()->getParent()->getParent();
2303   if (Triple(M.getTargetTriple()).getArch() != Triple::hexagon)
2304     return false;
2305
2306   if (skipLoop(L))
2307     return false;
2308
2309   // If the loop could not be converted to canonical form, it must have an
2310   // indirectbr in it, just give up.
2311   if (!L->getLoopPreheader())
2312     return false;
2313
2314   // Disable loop idiom recognition if the function's name is a common idiom.
2315   StringRef Name = L->getHeader()->getParent()->getName();
2316   if (Name == "memset" || Name == "memcpy" || Name == "memmove")
2317     return false;
2318
2319   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2320   DL = &L->getHeader()->getModule()->getDataLayout();
2321   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2322   LF = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2323   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
2324   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2325
2326   HasMemcpy = TLI->has(LibFunc_memcpy);
2327   HasMemmove = TLI->has(LibFunc_memmove);
2328
2329   if (SE->hasLoopInvariantBackedgeTakenCount(L))
2330     return runOnCountableLoop(L);
2331   return false;
2332 }
2333
2334
2335 Pass *llvm::createHexagonLoopIdiomPass() {
2336   return new HexagonLoopIdiomRecognize();
2337 }
2338