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