LLVM  8.0.0svn
HexagonConstExtenders.cpp
Go to the documentation of this file.
1 //===- HexagonConstExtenders.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 #include "HexagonInstrInfo.h"
11 #include "HexagonRegisterInfo.h"
12 #include "HexagonSubtarget.h"
13 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/Pass.h"
21 #include <map>
22 #include <set>
23 #include <utility>
24 #include <vector>
25 
26 #define DEBUG_TYPE "hexagon-cext-opt"
27 
28 using namespace llvm;
29 
30 static cl::opt<unsigned> CountThreshold("hexagon-cext-threshold",
32  cl::desc("Minimum number of extenders to trigger replacement"));
33 
34 static cl::opt<unsigned> ReplaceLimit("hexagon-cext-limit", cl::init(0),
35  cl::Hidden, cl::ZeroOrMore, cl::desc("Maximum number of replacements"));
36 
37 namespace llvm {
40 }
41 
42 static int32_t adjustUp(int32_t V, uint8_t A, uint8_t O) {
44  int32_t U = (V & -A) + O;
45  return U >= V ? U : U+A;
46 }
47 
48 static int32_t adjustDown(int32_t V, uint8_t A, uint8_t O) {
50  int32_t U = (V & -A) + O;
51  return U <= V ? U : U-A;
52 }
53 
54 namespace {
55  struct OffsetRange {
56  // The range of values between Min and Max that are of form Align*N+Offset,
57  // for some integer N. Min and Max are required to be of that form as well,
58  // except in the case of an empty range.
59  int32_t Min = INT_MIN, Max = INT_MAX;
60  uint8_t Align = 1;
61  uint8_t Offset = 0;
62 
63  OffsetRange() = default;
64  OffsetRange(int32_t L, int32_t H, uint8_t A, uint8_t O = 0)
65  : Min(L), Max(H), Align(A), Offset(O) {}
66  OffsetRange &intersect(OffsetRange A) {
67  if (Align < A.Align)
68  std::swap(*this, A);
69 
70  // Align >= A.Align.
71  if (Offset >= A.Offset && (Offset - A.Offset) % A.Align == 0) {
72  Min = adjustUp(std::max(Min, A.Min), Align, Offset);
73  Max = adjustDown(std::min(Max, A.Max), Align, Offset);
74  } else {
75  // Make an empty range.
76  Min = 0;
77  Max = -1;
78  }
79  // Canonicalize empty ranges.
80  if (Min > Max)
81  std::tie(Min, Max, Align) = std::make_tuple(0, -1, 1);
82  return *this;
83  }
84  OffsetRange &shift(int32_t S) {
85  Min += S;
86  Max += S;
87  Offset = (Offset+S) % Align;
88  return *this;
89  }
90  OffsetRange &extendBy(int32_t D) {
91  // If D < 0, extend Min, otherwise extend Max.
92  assert(D % Align == 0);
93  if (D < 0)
94  Min = (INT_MIN-D < Min) ? Min+D : INT_MIN;
95  else
96  Max = (INT_MAX-D > Max) ? Max+D : INT_MAX;
97  return *this;
98  }
99  bool empty() const {
100  return Min > Max;
101  }
102  bool contains(int32_t V) const {
103  return Min <= V && V <= Max && (V-Offset) % Align == 0;
104  }
105  bool operator==(const OffsetRange &R) const {
106  return Min == R.Min && Max == R.Max && Align == R.Align;
107  }
108  bool operator!=(const OffsetRange &R) const {
109  return !operator==(R);
110  }
111  bool operator<(const OffsetRange &R) const {
112  if (Min != R.Min)
113  return Min < R.Min;
114  if (Max != R.Max)
115  return Max < R.Max;
116  return Align < R.Align;
117  }
118  static OffsetRange zero() { return {0, 0, 1}; }
119  };
120 
121  struct RangeTree {
122  struct Node {
123  Node(const OffsetRange &R) : MaxEnd(R.Max), Range(R) {}
124  unsigned Height = 1;
125  unsigned Count = 1;
126  int32_t MaxEnd;
127  const OffsetRange &Range;
128  Node *Left = nullptr, *Right = nullptr;
129  };
130 
131  Node *Root = nullptr;
132 
133  void add(const OffsetRange &R) {
134  Root = add(Root, R);
135  }
136  void erase(const Node *N) {
137  Root = remove(Root, N);
138  delete N;
139  }
140  void order(SmallVectorImpl<Node*> &Seq) const {
141  order(Root, Seq);
142  }
143  SmallVector<Node*,8> nodesWith(int32_t P, bool CheckAlign = true) {
144  SmallVector<Node*,8> Nodes;
145  nodesWith(Root, P, CheckAlign, Nodes);
146  return Nodes;
147  }
148  void dump() const;
149  ~RangeTree() {
150  SmallVector<Node*,8> Nodes;
151  order(Nodes);
152  for (Node *N : Nodes)
153  delete N;
154  }
155 
156  private:
157  void dump(const Node *N) const;
158  void order(Node *N, SmallVectorImpl<Node*> &Seq) const;
159  void nodesWith(Node *N, int32_t P, bool CheckA,
160  SmallVectorImpl<Node*> &Seq) const;
161 
162  Node *add(Node *N, const OffsetRange &R);
163  Node *remove(Node *N, const Node *D);
164  Node *rotateLeft(Node *Lower, Node *Higher);
165  Node *rotateRight(Node *Lower, Node *Higher);
166  unsigned height(Node *N) {
167  return N != nullptr ? N->Height : 0;
168  }
169  Node *update(Node *N) {
170  assert(N != nullptr);
171  N->Height = 1 + std::max(height(N->Left), height(N->Right));
172  if (N->Left)
173  N->MaxEnd = std::max(N->MaxEnd, N->Left->MaxEnd);
174  if (N->Right)
175  N->MaxEnd = std::max(N->MaxEnd, N->Right->MaxEnd);
176  return N;
177  }
178  Node *rebalance(Node *N) {
179  assert(N != nullptr);
180  int32_t Balance = height(N->Right) - height(N->Left);
181  if (Balance < -1)
182  return rotateRight(N->Left, N);
183  if (Balance > 1)
184  return rotateLeft(N->Right, N);
185  return N;
186  }
187  };
188 
189  struct Loc {
190  MachineBasicBlock *Block = nullptr;
192 
194  : Block(B), At(It) {
195  if (B->end() == It) {
196  Pos = -1;
197  } else {
198  assert(It->getParent() == B);
199  Pos = std::distance(B->begin(), It);
200  }
201  }
202  bool operator<(Loc A) const {
203  if (Block != A.Block)
204  return Block->getNumber() < A.Block->getNumber();
205  if (A.Pos == -1)
206  return Pos != A.Pos;
207  return Pos != -1 && Pos < A.Pos;
208  }
209  private:
210  int Pos = 0;
211  };
212 
213  struct HexagonConstExtenders : public MachineFunctionPass {
214  static char ID;
215  HexagonConstExtenders() : MachineFunctionPass(ID) {}
216 
217  void getAnalysisUsage(AnalysisUsage &AU) const override {
221  }
222 
223  StringRef getPassName() const override {
224  return "Hexagon constant-extender optimization";
225  }
226  bool runOnMachineFunction(MachineFunction &MF) override;
227 
228  private:
229  struct Register {
230  Register() = default;
231  Register(unsigned R, unsigned S) : Reg(R), Sub(S) {}
232  Register(const MachineOperand &Op)
233  : Reg(Op.getReg()), Sub(Op.getSubReg()) {}
234  Register &operator=(const MachineOperand &Op) {
235  if (Op.isReg()) {
236  Reg = Op.getReg();
237  Sub = Op.getSubReg();
238  } else if (Op.isFI()) {
240  }
241  return *this;
242  }
243  bool isVReg() const {
244  return Reg != 0 && !TargetRegisterInfo::isStackSlot(Reg) &&
246  }
247  bool isSlot() const {
248  return Reg != 0 && TargetRegisterInfo::isStackSlot(Reg);
249  }
250  operator MachineOperand() const {
251  if (isVReg())
252  return MachineOperand::CreateReg(Reg, /*Def*/false, /*Imp*/false,
253  /*Kill*/false, /*Dead*/false, /*Undef*/false,
254  /*EarlyClobber*/false, Sub);
257  return MachineOperand::CreateFI(FI);
258  }
259  llvm_unreachable("Cannot create MachineOperand");
260  }
261  bool operator==(Register R) const { return Reg == R.Reg && Sub == R.Sub; }
262  bool operator!=(Register R) const { return !operator==(R); }
263  bool operator<(Register R) const {
264  // For std::map.
265  return Reg < R.Reg || (Reg == R.Reg && Sub < R.Sub);
266  }
267  unsigned Reg = 0, Sub = 0;
268  };
269 
270  struct ExtExpr {
271  // A subexpression in which the extender is used. In general, this
272  // represents an expression where adding D to the extender will be
273  // equivalent to adding D to the expression as a whole. In other
274  // words, expr(add(##V,D) = add(expr(##V),D).
275 
276  // The original motivation for this are the io/ur addressing modes,
277  // where the offset is extended. Consider the io example:
278  // In memw(Rs+##V), the ##V could be replaced by a register Rt to
279  // form the rr mode: memw(Rt+Rs<<0). In such case, however, the
280  // register Rt must have exactly the value of ##V. If there was
281  // another instruction memw(Rs+##V+4), it would need a different Rt.
282  // Now, if Rt was initialized as "##V+Rs<<0", both of these
283  // instructions could use the same Rt, just with different offsets.
284  // Here it's clear that "initializer+4" should be the same as if
285  // the offset 4 was added to the ##V in the initializer.
286 
287  // The only kinds of expressions that support the requirement of
288  // commuting with addition are addition and subtraction from ##V.
289  // Include shifting the Rs to account for the ur addressing mode:
290  // ##Val + Rs << S
291  // ##Val - Rs
292  Register Rs;
293  unsigned S = 0;
294  bool Neg = false;
295 
296  ExtExpr() = default;
297  ExtExpr(Register RS, bool NG, unsigned SH) : Rs(RS), S(SH), Neg(NG) {}
298  // Expression is trivial if it does not modify the extender.
299  bool trivial() const {
300  return Rs.Reg == 0;
301  }
302  bool operator==(const ExtExpr &Ex) const {
303  return Rs == Ex.Rs && S == Ex.S && Neg == Ex.Neg;
304  }
305  bool operator!=(const ExtExpr &Ex) const {
306  return !operator==(Ex);
307  }
308  bool operator<(const ExtExpr &Ex) const {
309  if (Rs != Ex.Rs)
310  return Rs < Ex.Rs;
311  if (S != Ex.S)
312  return S < Ex.S;
313  return !Neg && Ex.Neg;
314  }
315  };
316 
317  struct ExtDesc {
318  MachineInstr *UseMI = nullptr;
319  unsigned OpNum = -1u;
320  // The subexpression in which the extender is used (e.g. address
321  // computation).
322  ExtExpr Expr;
323  // Optional register that is assigned the value of Expr.
324  Register Rd;
325  // Def means that the output of the instruction may differ from the
326  // original by a constant c, and that the difference can be corrected
327  // by adding/subtracting c in all users of the defined register.
328  bool IsDef = false;
329 
330  MachineOperand &getOp() {
331  return UseMI->getOperand(OpNum);
332  }
333  const MachineOperand &getOp() const {
334  return UseMI->getOperand(OpNum);
335  }
336  };
337 
338  struct ExtRoot {
339  union {
340  const ConstantFP *CFP; // MO_FPImmediate
341  const char *SymbolName; // MO_ExternalSymbol
342  const GlobalValue *GV; // MO_GlobalAddress
343  const BlockAddress *BA; // MO_BlockAddress
344  int64_t ImmVal; // MO_Immediate, MO_TargetIndex,
345  // and MO_ConstantPoolIndex
346  } V;
347  unsigned Kind; // Same as in MachineOperand.
348  unsigned char TF; // TargetFlags.
349 
350  ExtRoot(const MachineOperand &Op);
351  bool operator==(const ExtRoot &ER) const {
352  return Kind == ER.Kind && V.ImmVal == ER.V.ImmVal;
353  }
354  bool operator!=(const ExtRoot &ER) const {
355  return !operator==(ER);
356  }
357  bool operator<(const ExtRoot &ER) const;
358  };
359 
360  struct ExtValue : public ExtRoot {
361  int32_t Offset;
362 
363  ExtValue(const MachineOperand &Op);
364  ExtValue(const ExtDesc &ED) : ExtValue(ED.getOp()) {}
365  ExtValue(const ExtRoot &ER, int32_t Off) : ExtRoot(ER), Offset(Off) {}
366  bool operator<(const ExtValue &EV) const;
367  bool operator==(const ExtValue &EV) const {
368  return ExtRoot(*this) == ExtRoot(EV) && Offset == EV.Offset;
369  }
370  bool operator!=(const ExtValue &EV) const {
371  return !operator==(EV);
372  }
373  explicit operator MachineOperand() const;
374  };
375 
376  using IndexList = SetVector<unsigned>;
377  using ExtenderInit = std::pair<ExtValue, ExtExpr>;
378  using AssignmentMap = std::map<ExtenderInit, IndexList>;
379  using LocDefList = std::vector<std::pair<Loc, IndexList>>;
380 
381  const HexagonInstrInfo *HII = nullptr;
382  const HexagonRegisterInfo *HRI = nullptr;
383  MachineDominatorTree *MDT = nullptr;
384  MachineRegisterInfo *MRI = nullptr;
385  std::vector<ExtDesc> Extenders;
386  std::vector<unsigned> NewRegs;
387 
388  bool isStoreImmediate(unsigned Opc) const;
389  bool isRegOffOpcode(unsigned ExtOpc) const ;
390  unsigned getRegOffOpcode(unsigned ExtOpc) const;
391  unsigned getDirectRegReplacement(unsigned ExtOpc) const;
392  OffsetRange getOffsetRange(Register R, const MachineInstr &MI) const;
393  OffsetRange getOffsetRange(const ExtDesc &ED) const;
394  OffsetRange getOffsetRange(Register Rd) const;
395 
396  void recordExtender(MachineInstr &MI, unsigned OpNum);
397  void collectInstr(MachineInstr &MI);
398  void collect(MachineFunction &MF);
399  void assignInits(const ExtRoot &ER, unsigned Begin, unsigned End,
400  AssignmentMap &IMap);
401  void calculatePlacement(const ExtenderInit &ExtI, const IndexList &Refs,
402  LocDefList &Defs);
403  Register insertInitializer(Loc DefL, const ExtenderInit &ExtI);
404  bool replaceInstrExact(const ExtDesc &ED, Register ExtR);
405  bool replaceInstrExpr(const ExtDesc &ED, const ExtenderInit &ExtI,
406  Register ExtR, int32_t &Diff);
407  bool replaceInstr(unsigned Idx, Register ExtR, const ExtenderInit &ExtI);
408  bool replaceExtenders(const AssignmentMap &IMap);
409 
410  unsigned getOperandIndex(const MachineInstr &MI,
411  const MachineOperand &Op) const;
412  const MachineOperand &getPredicateOp(const MachineInstr &MI) const;
413  const MachineOperand &getLoadResultOp(const MachineInstr &MI) const;
414  const MachineOperand &getStoredValueOp(const MachineInstr &MI) const;
415 
416  friend struct PrintRegister;
417  friend struct PrintExpr;
418  friend struct PrintInit;
419  friend struct PrintIMap;
420  friend raw_ostream &operator<< (raw_ostream &OS,
421  const struct PrintRegister &P);
422  friend raw_ostream &operator<< (raw_ostream &OS, const struct PrintExpr &P);
423  friend raw_ostream &operator<< (raw_ostream &OS, const struct PrintInit &P);
424  friend raw_ostream &operator<< (raw_ostream &OS, const ExtDesc &ED);
425  friend raw_ostream &operator<< (raw_ostream &OS, const ExtRoot &ER);
426  friend raw_ostream &operator<< (raw_ostream &OS, const ExtValue &EV);
427  friend raw_ostream &operator<< (raw_ostream &OS, const OffsetRange &OR);
428  friend raw_ostream &operator<< (raw_ostream &OS, const struct PrintIMap &P);
429  };
430 
431  using HCE = HexagonConstExtenders;
432 
434  raw_ostream &operator<< (raw_ostream &OS, const OffsetRange &OR) {
435  if (OR.Min > OR.Max)
436  OS << '!';
437  OS << '[' << OR.Min << ',' << OR.Max << "]a" << unsigned(OR.Align)
438  << '+' << unsigned(OR.Offset);
439  return OS;
440  }
441 
442  struct PrintRegister {
443  PrintRegister(HCE::Register R, const HexagonRegisterInfo &I)
444  : Rs(R), HRI(I) {}
445  HCE::Register Rs;
446  const HexagonRegisterInfo &HRI;
447  };
448 
450  raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &P) {
451  if (P.Rs.Reg != 0)
452  OS << printReg(P.Rs.Reg, &P.HRI, P.Rs.Sub);
453  else
454  OS << "noreg";
455  return OS;
456  }
457 
458  struct PrintExpr {
459  PrintExpr(const HCE::ExtExpr &E, const HexagonRegisterInfo &I)
460  : Ex(E), HRI(I) {}
461  const HCE::ExtExpr &Ex;
462  const HexagonRegisterInfo &HRI;
463  };
464 
466  raw_ostream &operator<< (raw_ostream &OS, const PrintExpr &P) {
467  OS << "## " << (P.Ex.Neg ? "- " : "+ ");
468  if (P.Ex.Rs.Reg != 0)
469  OS << printReg(P.Ex.Rs.Reg, &P.HRI, P.Ex.Rs.Sub);
470  else
471  OS << "__";
472  OS << " << " << P.Ex.S;
473  return OS;
474  }
475 
476  struct PrintInit {
477  PrintInit(const HCE::ExtenderInit &EI, const HexagonRegisterInfo &I)
478  : ExtI(EI), HRI(I) {}
479  const HCE::ExtenderInit &ExtI;
480  const HexagonRegisterInfo &HRI;
481  };
482 
484  raw_ostream &operator<< (raw_ostream &OS, const PrintInit &P) {
485  OS << '[' << P.ExtI.first << ", "
486  << PrintExpr(P.ExtI.second, P.HRI) << ']';
487  return OS;
488  }
489 
491  raw_ostream &operator<< (raw_ostream &OS, const HCE::ExtDesc &ED) {
492  assert(ED.OpNum != -1u);
493  const MachineBasicBlock &MBB = *ED.getOp().getParent()->getParent();
494  const MachineFunction &MF = *MBB.getParent();
495  const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
496  OS << "bb#" << MBB.getNumber() << ": ";
497  if (ED.Rd.Reg != 0)
498  OS << printReg(ED.Rd.Reg, &HRI, ED.Rd.Sub);
499  else
500  OS << "__";
501  OS << " = " << PrintExpr(ED.Expr, HRI);
502  if (ED.IsDef)
503  OS << ", def";
504  return OS;
505  }
506 
508  raw_ostream &operator<< (raw_ostream &OS, const HCE::ExtRoot &ER) {
509  switch (ER.Kind) {
511  OS << "imm:" << ER.V.ImmVal;
512  break;
514  OS << "fpi:" << *ER.V.CFP;
515  break;
517  OS << "sym:" << *ER.V.SymbolName;
518  break;
520  OS << "gad:" << ER.V.GV->getName();
521  break;
523  OS << "blk:" << *ER.V.BA;
524  break;
526  OS << "tgi:" << ER.V.ImmVal;
527  break;
529  OS << "cpi:" << ER.V.ImmVal;
530  break;
532  OS << "jti:" << ER.V.ImmVal;
533  break;
534  default:
535  OS << "???:" << ER.V.ImmVal;
536  break;
537  }
538  return OS;
539  }
540 
542  raw_ostream &operator<< (raw_ostream &OS, const HCE::ExtValue &EV) {
543  OS << HCE::ExtRoot(EV) << " off:" << EV.Offset;
544  return OS;
545  }
546 
547  struct PrintIMap {
548  PrintIMap(const HCE::AssignmentMap &M, const HexagonRegisterInfo &I)
549  : IMap(M), HRI(I) {}
550  const HCE::AssignmentMap &IMap;
551  const HexagonRegisterInfo &HRI;
552  };
553 
555  raw_ostream &operator<< (raw_ostream &OS, const PrintIMap &P) {
556  OS << "{\n";
557  for (const std::pair<HCE::ExtenderInit,HCE::IndexList> &Q : P.IMap) {
558  OS << " " << PrintInit(Q.first, P.HRI) << " -> {";
559  for (unsigned I : Q.second)
560  OS << ' ' << I;
561  OS << " }\n";
562  }
563  OS << "}\n";
564  return OS;
565  }
566 }
567 
568 INITIALIZE_PASS_BEGIN(HexagonConstExtenders, "hexagon-cext-opt",
569  "Hexagon constant-extender optimization", false, false)
571 INITIALIZE_PASS_END(HexagonConstExtenders, "hexagon-cext-opt",
572  "Hexagon constant-extender optimization", false, false)
573 
574 static unsigned ReplaceCounter = 0;
575 
576 char HCE::ID = 0;
577 
578 #ifndef NDEBUG
579 LLVM_DUMP_METHOD void RangeTree::dump() const {
580  dbgs() << "Root: " << Root << '\n';
581  if (Root)
582  dump(Root);
583 }
584 
585 LLVM_DUMP_METHOD void RangeTree::dump(const Node *N) const {
586  dbgs() << "Node: " << N << '\n';
587  dbgs() << " Height: " << N->Height << '\n';
588  dbgs() << " Count: " << N->Count << '\n';
589  dbgs() << " MaxEnd: " << N->MaxEnd << '\n';
590  dbgs() << " Range: " << N->Range << '\n';
591  dbgs() << " Left: " << N->Left << '\n';
592  dbgs() << " Right: " << N->Right << "\n\n";
593 
594  if (N->Left)
595  dump(N->Left);
596  if (N->Right)
597  dump(N->Right);
598 }
599 #endif
600 
601 void RangeTree::order(Node *N, SmallVectorImpl<Node*> &Seq) const {
602  if (N == nullptr)
603  return;
604  order(N->Left, Seq);
605  Seq.push_back(N);
606  order(N->Right, Seq);
607 }
608 
609 void RangeTree::nodesWith(Node *N, int32_t P, bool CheckA,
610  SmallVectorImpl<Node*> &Seq) const {
611  if (N == nullptr || N->MaxEnd < P)
612  return;
613  nodesWith(N->Left, P, CheckA, Seq);
614  if (N->Range.Min <= P) {
615  if ((CheckA && N->Range.contains(P)) || (!CheckA && P <= N->Range.Max))
616  Seq.push_back(N);
617  nodesWith(N->Right, P, CheckA, Seq);
618  }
619 }
620 
621 RangeTree::Node *RangeTree::add(Node *N, const OffsetRange &R) {
622  if (N == nullptr)
623  return new Node(R);
624 
625  if (N->Range == R) {
626  N->Count++;
627  return N;
628  }
629 
630  if (R < N->Range)
631  N->Left = add(N->Left, R);
632  else
633  N->Right = add(N->Right, R);
634  return rebalance(update(N));
635 }
636 
637 RangeTree::Node *RangeTree::remove(Node *N, const Node *D) {
638  assert(N != nullptr);
639 
640  if (N != D) {
641  assert(N->Range != D->Range && "N and D should not be equal");
642  if (D->Range < N->Range)
643  N->Left = remove(N->Left, D);
644  else
645  N->Right = remove(N->Right, D);
646  return rebalance(update(N));
647  }
648 
649  // We got to the node we need to remove. If any of its children are
650  // missing, simply replace it with the other child.
651  if (N->Left == nullptr || N->Right == nullptr)
652  return (N->Left == nullptr) ? N->Right : N->Left;
653 
654  // Find the rightmost child of N->Left, remove it and plug it in place
655  // of N.
656  Node *M = N->Left;
657  while (M->Right)
658  M = M->Right;
659  M->Left = remove(N->Left, M);
660  M->Right = N->Right;
661  return rebalance(update(M));
662 }
663 
664 RangeTree::Node *RangeTree::rotateLeft(Node *Lower, Node *Higher) {
665  assert(Higher->Right == Lower);
666  // The Lower node is on the right from Higher. Make sure that Lower's
667  // balance is greater to the right. Otherwise the rotation will create
668  // an unbalanced tree again.
669  if (height(Lower->Left) > height(Lower->Right))
670  Lower = rotateRight(Lower->Left, Lower);
671  assert(height(Lower->Left) <= height(Lower->Right));
672  Higher->Right = Lower->Left;
673  update(Higher);
674  Lower->Left = Higher;
675  update(Lower);
676  return Lower;
677 }
678 
679 RangeTree::Node *RangeTree::rotateRight(Node *Lower, Node *Higher) {
680  assert(Higher->Left == Lower);
681  // The Lower node is on the left from Higher. Make sure that Lower's
682  // balance is greater to the left. Otherwise the rotation will create
683  // an unbalanced tree again.
684  if (height(Lower->Left) < height(Lower->Right))
685  Lower = rotateLeft(Lower->Right, Lower);
686  assert(height(Lower->Left) >= height(Lower->Right));
687  Higher->Left = Lower->Right;
688  update(Higher);
689  Lower->Right = Higher;
690  update(Lower);
691  return Lower;
692 }
693 
694 
695 HCE::ExtRoot::ExtRoot(const MachineOperand &Op) {
696  // Always store ImmVal, since it's the field used for comparisons.
697  V.ImmVal = 0;
698  if (Op.isImm())
699  ; // Keep 0. Do not use Op.getImm() for value here (treat 0 as the root).
700  else if (Op.isFPImm())
701  V.CFP = Op.getFPImm();
702  else if (Op.isSymbol())
703  V.SymbolName = Op.getSymbolName();
704  else if (Op.isGlobal())
705  V.GV = Op.getGlobal();
706  else if (Op.isBlockAddress())
707  V.BA = Op.getBlockAddress();
708  else if (Op.isCPI() || Op.isTargetIndex() || Op.isJTI())
709  V.ImmVal = Op.getIndex();
710  else
711  llvm_unreachable("Unexpected operand type");
712 
713  Kind = Op.getType();
714  TF = Op.getTargetFlags();
715 }
716 
717 bool HCE::ExtRoot::operator< (const HCE::ExtRoot &ER) const {
718  if (Kind != ER.Kind)
719  return Kind < ER.Kind;
720  switch (Kind) {
725  return V.ImmVal < ER.V.ImmVal;
727  const APFloat &ThisF = V.CFP->getValueAPF();
728  const APFloat &OtherF = ER.V.CFP->getValueAPF();
729  return ThisF.bitcastToAPInt().ult(OtherF.bitcastToAPInt());
730  }
732  return StringRef(V.SymbolName) < StringRef(ER.V.SymbolName);
734  // Do not use GUIDs, since they depend on the source path. Moving the
735  // source file to a different directory could cause different GUID
736  // values for a pair of given symbols. These symbols could then compare
737  // "less" in one directory, but "greater" in another.
738  assert(!V.GV->getName().empty() && !ER.V.GV->getName().empty());
739  return V.GV->getName() < ER.V.GV->getName();
741  const BasicBlock *ThisB = V.BA->getBasicBlock();
742  const BasicBlock *OtherB = ER.V.BA->getBasicBlock();
743  assert(ThisB->getParent() == OtherB->getParent());
744  const Function &F = *ThisB->getParent();
745  return std::distance(F.begin(), ThisB->getIterator()) <
746  std::distance(F.begin(), OtherB->getIterator());
747  }
748  }
749  return V.ImmVal < ER.V.ImmVal;
750 }
751 
752 HCE::ExtValue::ExtValue(const MachineOperand &Op) : ExtRoot(Op) {
753  if (Op.isImm())
754  Offset = Op.getImm();
755  else if (Op.isFPImm() || Op.isJTI())
756  Offset = 0;
757  else if (Op.isSymbol() || Op.isGlobal() || Op.isBlockAddress() ||
758  Op.isCPI() || Op.isTargetIndex())
759  Offset = Op.getOffset();
760  else
761  llvm_unreachable("Unexpected operand type");
762 }
763 
764 bool HCE::ExtValue::operator< (const HCE::ExtValue &EV) const {
765  const ExtRoot &ER = *this;
766  if (!(ER == ExtRoot(EV)))
767  return ER < EV;
768  return Offset < EV.Offset;
769 }
770 
771 HCE::ExtValue::operator MachineOperand() const {
772  switch (Kind) {
774  return MachineOperand::CreateImm(V.ImmVal + Offset);
776  assert(Offset == 0);
777  return MachineOperand::CreateFPImm(V.CFP);
779  assert(Offset == 0);
780  return MachineOperand::CreateES(V.SymbolName, TF);
782  return MachineOperand::CreateGA(V.GV, Offset, TF);
784  return MachineOperand::CreateBA(V.BA, Offset, TF);
786  return MachineOperand::CreateTargetIndex(V.ImmVal, Offset, TF);
788  return MachineOperand::CreateCPI(V.ImmVal, Offset, TF);
790  assert(Offset == 0);
791  return MachineOperand::CreateJTI(V.ImmVal, TF);
792  default:
793  llvm_unreachable("Unhandled kind");
794  }
795 }
796 
797 bool HCE::isStoreImmediate(unsigned Opc) const {
798  switch (Opc) {
799  case Hexagon::S4_storeirbt_io:
800  case Hexagon::S4_storeirbf_io:
801  case Hexagon::S4_storeirht_io:
802  case Hexagon::S4_storeirhf_io:
803  case Hexagon::S4_storeirit_io:
804  case Hexagon::S4_storeirif_io:
805  case Hexagon::S4_storeirb_io:
806  case Hexagon::S4_storeirh_io:
807  case Hexagon::S4_storeiri_io:
808  return true;
809  default:
810  break;
811  }
812  return false;
813 }
814 
815 bool HCE::isRegOffOpcode(unsigned Opc) const {
816  switch (Opc) {
817  case Hexagon::L2_loadrub_io:
818  case Hexagon::L2_loadrb_io:
819  case Hexagon::L2_loadruh_io:
820  case Hexagon::L2_loadrh_io:
821  case Hexagon::L2_loadri_io:
822  case Hexagon::L2_loadrd_io:
823  case Hexagon::L2_loadbzw2_io:
824  case Hexagon::L2_loadbzw4_io:
825  case Hexagon::L2_loadbsw2_io:
826  case Hexagon::L2_loadbsw4_io:
827  case Hexagon::L2_loadalignh_io:
828  case Hexagon::L2_loadalignb_io:
829  case Hexagon::L2_ploadrubt_io:
830  case Hexagon::L2_ploadrubf_io:
831  case Hexagon::L2_ploadrbt_io:
832  case Hexagon::L2_ploadrbf_io:
833  case Hexagon::L2_ploadruht_io:
834  case Hexagon::L2_ploadruhf_io:
835  case Hexagon::L2_ploadrht_io:
836  case Hexagon::L2_ploadrhf_io:
837  case Hexagon::L2_ploadrit_io:
838  case Hexagon::L2_ploadrif_io:
839  case Hexagon::L2_ploadrdt_io:
840  case Hexagon::L2_ploadrdf_io:
841  case Hexagon::S2_storerb_io:
842  case Hexagon::S2_storerh_io:
843  case Hexagon::S2_storerf_io:
844  case Hexagon::S2_storeri_io:
845  case Hexagon::S2_storerd_io:
846  case Hexagon::S2_pstorerbt_io:
847  case Hexagon::S2_pstorerbf_io:
848  case Hexagon::S2_pstorerht_io:
849  case Hexagon::S2_pstorerhf_io:
850  case Hexagon::S2_pstorerft_io:
851  case Hexagon::S2_pstorerff_io:
852  case Hexagon::S2_pstorerit_io:
853  case Hexagon::S2_pstorerif_io:
854  case Hexagon::S2_pstorerdt_io:
855  case Hexagon::S2_pstorerdf_io:
856  case Hexagon::A2_addi:
857  return true;
858  default:
859  break;
860  }
861  return false;
862 }
863 
864 unsigned HCE::getRegOffOpcode(unsigned ExtOpc) const {
865  // If there exists an instruction that takes a register and offset,
866  // that corresponds to the ExtOpc, return it, otherwise return 0.
867  using namespace Hexagon;
868  switch (ExtOpc) {
869  case A2_tfrsi: return A2_addi;
870  default:
871  break;
872  }
873  const MCInstrDesc &D = HII->get(ExtOpc);
874  if (D.mayLoad() || D.mayStore()) {
875  uint64_t F = D.TSFlags;
876  unsigned AM = (F >> HexagonII::AddrModePos) & HexagonII::AddrModeMask;
877  switch (AM) {
878  case HexagonII::Absolute:
881  switch (ExtOpc) {
882  case PS_loadrubabs:
883  case L4_loadrub_ap:
884  case L4_loadrub_ur: return L2_loadrub_io;
885  case PS_loadrbabs:
886  case L4_loadrb_ap:
887  case L4_loadrb_ur: return L2_loadrb_io;
888  case PS_loadruhabs:
889  case L4_loadruh_ap:
890  case L4_loadruh_ur: return L2_loadruh_io;
891  case PS_loadrhabs:
892  case L4_loadrh_ap:
893  case L4_loadrh_ur: return L2_loadrh_io;
894  case PS_loadriabs:
895  case L4_loadri_ap:
896  case L4_loadri_ur: return L2_loadri_io;
897  case PS_loadrdabs:
898  case L4_loadrd_ap:
899  case L4_loadrd_ur: return L2_loadrd_io;
900  case L4_loadbzw2_ap:
901  case L4_loadbzw2_ur: return L2_loadbzw2_io;
902  case L4_loadbzw4_ap:
903  case L4_loadbzw4_ur: return L2_loadbzw4_io;
904  case L4_loadbsw2_ap:
905  case L4_loadbsw2_ur: return L2_loadbsw2_io;
906  case L4_loadbsw4_ap:
907  case L4_loadbsw4_ur: return L2_loadbsw4_io;
908  case L4_loadalignh_ap:
909  case L4_loadalignh_ur: return L2_loadalignh_io;
910  case L4_loadalignb_ap:
911  case L4_loadalignb_ur: return L2_loadalignb_io;
912  case L4_ploadrubt_abs: return L2_ploadrubt_io;
913  case L4_ploadrubf_abs: return L2_ploadrubf_io;
914  case L4_ploadrbt_abs: return L2_ploadrbt_io;
915  case L4_ploadrbf_abs: return L2_ploadrbf_io;
916  case L4_ploadruht_abs: return L2_ploadruht_io;
917  case L4_ploadruhf_abs: return L2_ploadruhf_io;
918  case L4_ploadrht_abs: return L2_ploadrht_io;
919  case L4_ploadrhf_abs: return L2_ploadrhf_io;
920  case L4_ploadrit_abs: return L2_ploadrit_io;
921  case L4_ploadrif_abs: return L2_ploadrif_io;
922  case L4_ploadrdt_abs: return L2_ploadrdt_io;
923  case L4_ploadrdf_abs: return L2_ploadrdf_io;
924  case PS_storerbabs:
925  case S4_storerb_ap:
926  case S4_storerb_ur: return S2_storerb_io;
927  case PS_storerhabs:
928  case S4_storerh_ap:
929  case S4_storerh_ur: return S2_storerh_io;
930  case PS_storerfabs:
931  case S4_storerf_ap:
932  case S4_storerf_ur: return S2_storerf_io;
933  case PS_storeriabs:
934  case S4_storeri_ap:
935  case S4_storeri_ur: return S2_storeri_io;
936  case PS_storerdabs:
937  case S4_storerd_ap:
938  case S4_storerd_ur: return S2_storerd_io;
939  case S4_pstorerbt_abs: return S2_pstorerbt_io;
940  case S4_pstorerbf_abs: return S2_pstorerbf_io;
941  case S4_pstorerht_abs: return S2_pstorerht_io;
942  case S4_pstorerhf_abs: return S2_pstorerhf_io;
943  case S4_pstorerft_abs: return S2_pstorerft_io;
944  case S4_pstorerff_abs: return S2_pstorerff_io;
945  case S4_pstorerit_abs: return S2_pstorerit_io;
946  case S4_pstorerif_abs: return S2_pstorerif_io;
947  case S4_pstorerdt_abs: return S2_pstorerdt_io;
948  case S4_pstorerdf_abs: return S2_pstorerdf_io;
949  default:
950  break;
951  }
952  break;
954  if (!isStoreImmediate(ExtOpc))
955  return ExtOpc;
956  break;
957  default:
958  break;
959  }
960  }
961  return 0;
962 }
963 
964 unsigned HCE::getDirectRegReplacement(unsigned ExtOpc) const {
965  switch (ExtOpc) {
966  case Hexagon::A2_addi: return Hexagon::A2_add;
967  case Hexagon::A2_andir: return Hexagon::A2_and;
968  case Hexagon::A2_combineii: return Hexagon::A4_combineri;
969  case Hexagon::A2_orir: return Hexagon::A2_or;
970  case Hexagon::A2_paddif: return Hexagon::A2_paddf;
971  case Hexagon::A2_paddit: return Hexagon::A2_paddt;
972  case Hexagon::A2_subri: return Hexagon::A2_sub;
973  case Hexagon::A2_tfrsi: return TargetOpcode::COPY;
974  case Hexagon::A4_cmpbeqi: return Hexagon::A4_cmpbeq;
975  case Hexagon::A4_cmpbgti: return Hexagon::A4_cmpbgt;
976  case Hexagon::A4_cmpbgtui: return Hexagon::A4_cmpbgtu;
977  case Hexagon::A4_cmpheqi: return Hexagon::A4_cmpheq;
978  case Hexagon::A4_cmphgti: return Hexagon::A4_cmphgt;
979  case Hexagon::A4_cmphgtui: return Hexagon::A4_cmphgtu;
980  case Hexagon::A4_combineii: return Hexagon::A4_combineir;
981  case Hexagon::A4_combineir: return TargetOpcode::REG_SEQUENCE;
982  case Hexagon::A4_combineri: return TargetOpcode::REG_SEQUENCE;
983  case Hexagon::A4_rcmpeqi: return Hexagon::A4_rcmpeq;
984  case Hexagon::A4_rcmpneqi: return Hexagon::A4_rcmpneq;
985  case Hexagon::C2_cmoveif: return Hexagon::A2_tfrpf;
986  case Hexagon::C2_cmoveit: return Hexagon::A2_tfrpt;
987  case Hexagon::C2_cmpeqi: return Hexagon::C2_cmpeq;
988  case Hexagon::C2_cmpgti: return Hexagon::C2_cmpgt;
989  case Hexagon::C2_cmpgtui: return Hexagon::C2_cmpgtu;
990  case Hexagon::C2_muxii: return Hexagon::C2_muxir;
991  case Hexagon::C2_muxir: return Hexagon::C2_mux;
992  case Hexagon::C2_muxri: return Hexagon::C2_mux;
993  case Hexagon::C4_cmpltei: return Hexagon::C4_cmplte;
994  case Hexagon::C4_cmplteui: return Hexagon::C4_cmplteu;
995  case Hexagon::C4_cmpneqi: return Hexagon::C4_cmpneq;
996  case Hexagon::M2_accii: return Hexagon::M2_acci; // T -> T
997  /* No M2_macsin */
998  case Hexagon::M2_macsip: return Hexagon::M2_maci; // T -> T
999  case Hexagon::M2_mpysin: return Hexagon::M2_mpyi;
1000  case Hexagon::M2_mpysip: return Hexagon::M2_mpyi;
1001  case Hexagon::M2_mpysmi: return Hexagon::M2_mpyi;
1002  case Hexagon::M2_naccii: return Hexagon::M2_nacci; // T -> T
1003  case Hexagon::M4_mpyri_addi: return Hexagon::M4_mpyri_addr;
1004  case Hexagon::M4_mpyri_addr: return Hexagon::M4_mpyrr_addr; // _ -> T
1005  case Hexagon::M4_mpyrr_addi: return Hexagon::M4_mpyrr_addr; // _ -> T
1006  case Hexagon::S4_addaddi: return Hexagon::M2_acci; // _ -> T
1007  case Hexagon::S4_addi_asl_ri: return Hexagon::S2_asl_i_r_acc; // T -> T
1008  case Hexagon::S4_addi_lsr_ri: return Hexagon::S2_lsr_i_r_acc; // T -> T
1009  case Hexagon::S4_andi_asl_ri: return Hexagon::S2_asl_i_r_and; // T -> T
1010  case Hexagon::S4_andi_lsr_ri: return Hexagon::S2_lsr_i_r_and; // T -> T
1011  case Hexagon::S4_ori_asl_ri: return Hexagon::S2_asl_i_r_or; // T -> T
1012  case Hexagon::S4_ori_lsr_ri: return Hexagon::S2_lsr_i_r_or; // T -> T
1013  case Hexagon::S4_subaddi: return Hexagon::M2_subacc; // _ -> T
1014  case Hexagon::S4_subi_asl_ri: return Hexagon::S2_asl_i_r_nac; // T -> T
1015  case Hexagon::S4_subi_lsr_ri: return Hexagon::S2_lsr_i_r_nac; // T -> T
1016 
1017  // Store-immediates:
1018  case Hexagon::S4_storeirbf_io: return Hexagon::S2_pstorerbf_io;
1019  case Hexagon::S4_storeirb_io: return Hexagon::S2_storerb_io;
1020  case Hexagon::S4_storeirbt_io: return Hexagon::S2_pstorerbt_io;
1021  case Hexagon::S4_storeirhf_io: return Hexagon::S2_pstorerhf_io;
1022  case Hexagon::S4_storeirh_io: return Hexagon::S2_storerh_io;
1023  case Hexagon::S4_storeirht_io: return Hexagon::S2_pstorerht_io;
1024  case Hexagon::S4_storeirif_io: return Hexagon::S2_pstorerif_io;
1025  case Hexagon::S4_storeiri_io: return Hexagon::S2_storeri_io;
1026  case Hexagon::S4_storeirit_io: return Hexagon::S2_pstorerit_io;
1027 
1028  default:
1029  break;
1030  }
1031  return 0;
1032 }
1033 
1034 // Return the allowable deviation from the current value of Rb (i.e. the
1035 // range of values that can be added to the current value) which the
1036 // instruction MI can accommodate.
1037 // The instruction MI is a user of register Rb, which is defined via an
1038 // extender. It may be possible for MI to be tweaked to work for a register
1039 // defined with a slightly different value. For example
1040 // ... = L2_loadrub_io Rb, 1
1041 // can be modifed to be
1042 // ... = L2_loadrub_io Rb', 0
1043 // if Rb' = Rb+1.
1044 // The range for Rb would be [Min+1, Max+1], where [Min, Max] is a range
1045 // for L2_loadrub with offset 0. That means that Rb could be replaced with
1046 // Rc, where Rc-Rb belongs to [Min+1, Max+1].
1047 OffsetRange HCE::getOffsetRange(Register Rb, const MachineInstr &MI) const {
1048  unsigned Opc = MI.getOpcode();
1049  // Instructions that are constant-extended may be replaced with something
1050  // else that no longer offers the same range as the original.
1051  if (!isRegOffOpcode(Opc) || HII->isConstExtended(MI))
1052  return OffsetRange::zero();
1053 
1054  if (Opc == Hexagon::A2_addi) {
1055  const MachineOperand &Op1 = MI.getOperand(1), &Op2 = MI.getOperand(2);
1056  if (Rb != Register(Op1) || !Op2.isImm())
1057  return OffsetRange::zero();
1058  OffsetRange R = { -(1<<15)+1, (1<<15)-1, 1 };
1059  return R.shift(Op2.getImm());
1060  }
1061 
1062  // HII::getBaseAndOffsetPosition returns the increment position as "offset".
1063  if (HII->isPostIncrement(MI))
1064  return OffsetRange::zero();
1065 
1066  const MCInstrDesc &D = HII->get(Opc);
1067  assert(D.mayLoad() || D.mayStore());
1068 
1069  unsigned BaseP, OffP;
1070  if (!HII->getBaseAndOffsetPosition(MI, BaseP, OffP) ||
1071  Rb != Register(MI.getOperand(BaseP)) ||
1072  !MI.getOperand(OffP).isImm())
1073  return OffsetRange::zero();
1074 
1075  uint64_t F = (D.TSFlags >> HexagonII::MemAccessSizePos) &
1078  unsigned L = Log2_32(A);
1079  unsigned S = 10+L; // sint11_L
1080  int32_t Min = -alignDown((1<<S)-1, A);
1081 
1082  // The range will be shifted by Off. To prefer non-negative offsets,
1083  // adjust Max accordingly.
1084  int32_t Off = MI.getOperand(OffP).getImm();
1085  int32_t Max = Off >= 0 ? 0 : -Off;
1086 
1087  OffsetRange R = { Min, Max, A };
1088  return R.shift(Off);
1089 }
1090 
1091 // Return the allowable deviation from the current value of the extender ED,
1092 // for which the instruction corresponding to ED can be modified without
1093 // using an extender.
1094 // The instruction uses the extender directly. It will be replaced with
1095 // another instruction, say MJ, where the extender will be replaced with a
1096 // register. MJ can allow some variability with respect to the value of
1097 // that register, as is the case with indexed memory instructions.
1098 OffsetRange HCE::getOffsetRange(const ExtDesc &ED) const {
1099  // The only way that there can be a non-zero range available is if
1100  // the instruction using ED will be converted to an indexed memory
1101  // instruction.
1102  unsigned IdxOpc = getRegOffOpcode(ED.UseMI->getOpcode());
1103  switch (IdxOpc) {
1104  case 0:
1105  return OffsetRange::zero();
1106  case Hexagon::A2_addi: // s16
1107  return { -32767, 32767, 1 };
1108  case Hexagon::A2_subri: // s10
1109  return { -511, 511, 1 };
1110  }
1111 
1112  if (!ED.UseMI->mayLoad() && !ED.UseMI->mayStore())
1113  return OffsetRange::zero();
1114  const MCInstrDesc &D = HII->get(IdxOpc);
1115  uint64_t F = (D.TSFlags >> HexagonII::MemAccessSizePos) &
1118  unsigned L = Log2_32(A);
1119  unsigned S = 10+L; // sint11_L
1120  int32_t Min = -alignDown((1<<S)-1, A);
1121  int32_t Max = 0; // Force non-negative offsets.
1122  return { Min, Max, A };
1123 }
1124 
1125 // Get the allowable deviation from the current value of Rd by checking
1126 // all uses of Rd.
1127 OffsetRange HCE::getOffsetRange(Register Rd) const {
1128  OffsetRange Range;
1129  for (const MachineOperand &Op : MRI->use_operands(Rd.Reg)) {
1130  // Make sure that the register being used by this operand is identical
1131  // to the register that was defined: using a different subregister
1132  // precludes any non-trivial range.
1133  if (Rd != Register(Op))
1134  return OffsetRange::zero();
1135  Range.intersect(getOffsetRange(Rd, *Op.getParent()));
1136  }
1137  return Range;
1138 }
1139 
1140 void HCE::recordExtender(MachineInstr &MI, unsigned OpNum) {
1141  unsigned Opc = MI.getOpcode();
1142  ExtDesc ED;
1143  ED.OpNum = OpNum;
1144 
1145  bool IsLoad = MI.mayLoad();
1146  bool IsStore = MI.mayStore();
1147 
1148  // Fixed stack slots have negative indexes, and they cannot be used
1149  // with TRI::stackSlot2Index and TRI::index2StackSlot. This is somewhat
1150  // unfortunate, but should not be a frequent thing.
1151  for (MachineOperand &Op : MI.operands())
1152  if (Op.isFI() && Op.getIndex() < 0)
1153  return;
1154 
1155  if (IsLoad || IsStore) {
1156  unsigned AM = HII->getAddrMode(MI);
1157  switch (AM) {
1158  // (Re: ##Off + Rb<<S) = Rd: ##Val
1159  case HexagonII::Absolute: // (__: ## + __<<_)
1160  break;
1161  case HexagonII::AbsoluteSet: // (Rd: ## + __<<_)
1162  ED.Rd = MI.getOperand(OpNum-1);
1163  ED.IsDef = true;
1164  break;
1165  case HexagonII::BaseImmOffset: // (__: ## + Rs<<0)
1166  // Store-immediates are treated as non-memory operations, since
1167  // it's the value being stored that is extended (as opposed to
1168  // a part of the address).
1169  if (!isStoreImmediate(Opc))
1170  ED.Expr.Rs = MI.getOperand(OpNum-1);
1171  break;
1172  case HexagonII::BaseLongOffset: // (__: ## + Rs<<S)
1173  ED.Expr.Rs = MI.getOperand(OpNum-2);
1174  ED.Expr.S = MI.getOperand(OpNum-1).getImm();
1175  break;
1176  default:
1177  llvm_unreachable("Unhandled memory instruction");
1178  }
1179  } else {
1180  switch (Opc) {
1181  case Hexagon::A2_tfrsi: // (Rd: ## + __<<_)
1182  ED.Rd = MI.getOperand(0);
1183  ED.IsDef = true;
1184  break;
1185  case Hexagon::A2_combineii: // (Rd: ## + __<<_)
1186  case Hexagon::A4_combineir:
1187  ED.Rd = { MI.getOperand(0).getReg(), Hexagon::isub_hi };
1188  ED.IsDef = true;
1189  break;
1190  case Hexagon::A4_combineri: // (Rd: ## + __<<_)
1191  ED.Rd = { MI.getOperand(0).getReg(), Hexagon::isub_lo };
1192  ED.IsDef = true;
1193  break;
1194  case Hexagon::A2_addi: // (Rd: ## + Rs<<0)
1195  ED.Rd = MI.getOperand(0);
1196  ED.Expr.Rs = MI.getOperand(OpNum-1);
1197  break;
1198  case Hexagon::M2_accii: // (__: ## + Rs<<0)
1199  case Hexagon::M2_naccii:
1200  case Hexagon::S4_addaddi:
1201  ED.Expr.Rs = MI.getOperand(OpNum-1);
1202  break;
1203  case Hexagon::A2_subri: // (Rd: ## - Rs<<0)
1204  ED.Rd = MI.getOperand(0);
1205  ED.Expr.Rs = MI.getOperand(OpNum+1);
1206  ED.Expr.Neg = true;
1207  break;
1208  case Hexagon::S4_subaddi: // (__: ## - Rs<<0)
1209  ED.Expr.Rs = MI.getOperand(OpNum+1);
1210  ED.Expr.Neg = true;
1211  break;
1212  default: // (__: ## + __<<_)
1213  break;
1214  }
1215  }
1216 
1217  ED.UseMI = &MI;
1218 
1219  // Ignore unnamed globals.
1220  ExtRoot ER(ED.getOp());
1221  if (ER.Kind == MachineOperand::MO_GlobalAddress)
1222  if (ER.V.GV->getName().empty())
1223  return;
1224  Extenders.push_back(ED);
1225 }
1226 
1227 void HCE::collectInstr(MachineInstr &MI) {
1228  if (!HII->isConstExtended(MI))
1229  return;
1230 
1231  // Skip some non-convertible instructions.
1232  unsigned Opc = MI.getOpcode();
1233  switch (Opc) {
1234  case Hexagon::M2_macsin: // There is no Rx -= mpyi(Rs,Rt).
1235  case Hexagon::C4_addipc:
1236  case Hexagon::S4_or_andi:
1237  case Hexagon::S4_or_andix:
1238  case Hexagon::S4_or_ori:
1239  return;
1240  }
1241  recordExtender(MI, HII->getCExtOpNum(MI));
1242 }
1243 
1244 void HCE::collect(MachineFunction &MF) {
1245  Extenders.clear();
1246  for (MachineBasicBlock &MBB : MF) {
1247  // Skip unreachable blocks.
1248  if (MBB.getNumber() == -1)
1249  continue;
1250  for (MachineInstr &MI : MBB)
1251  collectInstr(MI);
1252  }
1253 }
1254 
1255 void HCE::assignInits(const ExtRoot &ER, unsigned Begin, unsigned End,
1256  AssignmentMap &IMap) {
1257  // Sanity check: make sure that all extenders in the range [Begin..End)
1258  // share the same root ER.
1259  for (unsigned I = Begin; I != End; ++I)
1260  assert(ER == ExtRoot(Extenders[I].getOp()));
1261 
1262  // Construct the list of ranges, such that for each P in Ranges[I],
1263  // a register Reg = ER+P can be used in place of Extender[I]. If the
1264  // instruction allows, uses in the form of Reg+Off are considered
1265  // (here, Off = required_value - P).
1266  std::vector<OffsetRange> Ranges(End-Begin);
1267 
1268  // For each extender that is a def, visit all uses of the defined register,
1269  // and produce an offset range that works for all uses. The def doesn't
1270  // have to be checked, because it can become dead if all uses can be updated
1271  // to use a different reg/offset.
1272  for (unsigned I = Begin; I != End; ++I) {
1273  const ExtDesc &ED = Extenders[I];
1274  if (!ED.IsDef)
1275  continue;
1276  ExtValue EV(ED);
1277  LLVM_DEBUG(dbgs() << " =" << I << ". " << EV << " " << ED << '\n');
1278  assert(ED.Rd.Reg != 0);
1279  Ranges[I-Begin] = getOffsetRange(ED.Rd).shift(EV.Offset);
1280  // A2_tfrsi is a special case: it will be replaced with A2_addi, which
1281  // has a 16-bit signed offset. This means that A2_tfrsi not only has a
1282  // range coming from its uses, but also from the fact that its replacement
1283  // has a range as well.
1284  if (ED.UseMI->getOpcode() == Hexagon::A2_tfrsi) {
1285  int32_t D = alignDown(32767, Ranges[I-Begin].Align); // XXX hardcoded
1286  Ranges[I-Begin].extendBy(-D).extendBy(D);
1287  }
1288  }
1289 
1290  // Visit all non-def extenders. For each one, determine the offset range
1291  // available for it.
1292  for (unsigned I = Begin; I != End; ++I) {
1293  const ExtDesc &ED = Extenders[I];
1294  if (ED.IsDef)
1295  continue;
1296  ExtValue EV(ED);
1297  LLVM_DEBUG(dbgs() << " " << I << ". " << EV << " " << ED << '\n');
1298  OffsetRange Dev = getOffsetRange(ED);
1299  Ranges[I-Begin].intersect(Dev.shift(EV.Offset));
1300  }
1301 
1302  // Here for each I there is a corresponding Range[I]. Construct the
1303  // inverse map, that to each range will assign the set of indexes in
1304  // [Begin..End) that this range corresponds to.
1305  std::map<OffsetRange, IndexList> RangeMap;
1306  for (unsigned I = Begin; I != End; ++I)
1307  RangeMap[Ranges[I-Begin]].insert(I);
1308 
1309  LLVM_DEBUG({
1310  dbgs() << "Ranges\n";
1311  for (unsigned I = Begin; I != End; ++I)
1312  dbgs() << " " << I << ". " << Ranges[I-Begin] << '\n';
1313  dbgs() << "RangeMap\n";
1314  for (auto &P : RangeMap) {
1315  dbgs() << " " << P.first << " ->";
1316  for (unsigned I : P.second)
1317  dbgs() << ' ' << I;
1318  dbgs() << '\n';
1319  }
1320  });
1321 
1322  // Select the definition points, and generate the assignment between
1323  // these points and the uses.
1324 
1325  // For each candidate offset, keep a pair CandData consisting of
1326  // the total number of ranges containing that candidate, and the
1327  // vector of corresponding RangeTree nodes.
1328  using CandData = std::pair<unsigned, SmallVector<RangeTree::Node*,8>>;
1329  std::map<int32_t, CandData> CandMap;
1330 
1331  RangeTree Tree;
1332  for (const OffsetRange &R : Ranges)
1333  Tree.add(R);
1335  Tree.order(Nodes);
1336 
1337  auto MaxAlign = [](const SmallVectorImpl<RangeTree::Node*> &Nodes,
1338  uint8_t Align, uint8_t Offset) {
1339  for (RangeTree::Node *N : Nodes) {
1340  if (N->Range.Align <= Align || N->Range.Offset < Offset)
1341  continue;
1342  if ((N->Range.Offset - Offset) % Align != 0)
1343  continue;
1344  Align = N->Range.Align;
1345  Offset = N->Range.Offset;
1346  }
1347  return std::make_pair(Align, Offset);
1348  };
1349 
1350  // Construct the set of all potential definition points from the endpoints
1351  // of the ranges. If a given endpoint also belongs to a different range,
1352  // but with a higher alignment, also consider the more-highly-aligned
1353  // value of this endpoint.
1354  std::set<int32_t> CandSet;
1355  for (RangeTree::Node *N : Nodes) {
1356  const OffsetRange &R = N->Range;
1357  auto P0 = MaxAlign(Tree.nodesWith(R.Min, false), R.Align, R.Offset);
1358  CandSet.insert(R.Min);
1359  if (R.Align < P0.first)
1360  CandSet.insert(adjustUp(R.Min, P0.first, P0.second));
1361  auto P1 = MaxAlign(Tree.nodesWith(R.Max, false), R.Align, R.Offset);
1362  CandSet.insert(R.Max);
1363  if (R.Align < P1.first)
1364  CandSet.insert(adjustDown(R.Max, P1.first, P1.second));
1365  }
1366 
1367  // Build the assignment map: candidate C -> { list of extender indexes }.
1368  // This has to be done iteratively:
1369  // - pick the candidate that covers the maximum number of extenders,
1370  // - add the candidate to the map,
1371  // - remove the extenders from the pool.
1372  while (true) {
1373  using CMap = std::map<int32_t,unsigned>;
1374  CMap Counts;
1375  for (auto It = CandSet.begin(), Et = CandSet.end(); It != Et; ) {
1376  auto &&V = Tree.nodesWith(*It);
1377  unsigned N = std::accumulate(V.begin(), V.end(), 0u,
1378  [](unsigned Acc, const RangeTree::Node *N) {
1379  return Acc + N->Count;
1380  });
1381  if (N != 0)
1382  Counts.insert({*It, N});
1383  It = (N != 0) ? std::next(It) : CandSet.erase(It);
1384  }
1385  if (Counts.empty())
1386  break;
1387 
1388  // Find the best candidate with respect to the number of extenders covered.
1389  auto BestIt = std::max_element(Counts.begin(), Counts.end(),
1390  [](const CMap::value_type &A, const CMap::value_type &B) {
1391  return A.second < B.second ||
1392  (A.second == B.second && A < B);
1393  });
1394  int32_t Best = BestIt->first;
1395  ExtValue BestV(ER, Best);
1396  for (RangeTree::Node *N : Tree.nodesWith(Best)) {
1397  for (unsigned I : RangeMap[N->Range])
1398  IMap[{BestV,Extenders[I].Expr}].insert(I);
1399  Tree.erase(N);
1400  }
1401  }
1402 
1403  LLVM_DEBUG(dbgs() << "IMap (before fixup) = " << PrintIMap(IMap, *HRI));
1404 
1405  // There is some ambiguity in what initializer should be used, if the
1406  // descriptor's subexpression is non-trivial: it can be the entire
1407  // subexpression (which is what has been done so far), or it can be
1408  // the extender's value itself, if all corresponding extenders have the
1409  // exact value of the initializer (i.e. require offset of 0).
1410 
1411  // To reduce the number of initializers, merge such special cases.
1412  for (std::pair<const ExtenderInit,IndexList> &P : IMap) {
1413  // Skip trivial initializers.
1414  if (P.first.second.trivial())
1415  continue;
1416  // If the corresponding trivial initializer does not exist, skip this
1417  // entry.
1418  const ExtValue &EV = P.first.first;
1419  AssignmentMap::iterator F = IMap.find({EV, ExtExpr()});
1420  if (F == IMap.end())
1421  continue;
1422 
1423  // Finally, check if all extenders have the same value as the initializer.
1424  // Make sure that extenders that are a part of a stack address are not
1425  // merged with those that aren't. Stack addresses need an offset field
1426  // (to be used by frame index elimination), while non-stack expressions
1427  // can be replaced with forms (such as rr) that do not have such a field.
1428  // Example:
1429  //
1430  // Collected 3 extenders
1431  // =2. imm:0 off:32968 bb#2: %7 = ## + __ << 0, def
1432  // 0. imm:0 off:267 bb#0: __ = ## + SS#1 << 0
1433  // 1. imm:0 off:267 bb#1: __ = ## + SS#1 << 0
1434  // Ranges
1435  // 0. [-756,267]a1+0
1436  // 1. [-756,267]a1+0
1437  // 2. [201,65735]a1+0
1438  // RangeMap
1439  // [-756,267]a1+0 -> 0 1
1440  // [201,65735]a1+0 -> 2
1441  // IMap (before fixup) = {
1442  // [imm:0 off:267, ## + __ << 0] -> { 2 }
1443  // [imm:0 off:267, ## + SS#1 << 0] -> { 0 1 }
1444  // }
1445  // IMap (after fixup) = {
1446  // [imm:0 off:267, ## + __ << 0] -> { 2 0 1 }
1447  // [imm:0 off:267, ## + SS#1 << 0] -> { }
1448  // }
1449  // Inserted def in bb#0 for initializer: [imm:0 off:267, ## + __ << 0]
1450  // %12:intregs = A2_tfrsi 267
1451  //
1452  // The result was
1453  // %12:intregs = A2_tfrsi 267
1454  // S4_pstorerbt_rr %3, %12, %stack.1, 0, killed %4
1455  // Which became
1456  // r0 = #267
1457  // if (p0.new) memb(r0+r29<<#4) = r2
1458 
1459  bool IsStack = any_of(F->second, [this](unsigned I) {
1460  return Extenders[I].Expr.Rs.isSlot();
1461  });
1462  auto SameValue = [&EV,this,IsStack](unsigned I) {
1463  const ExtDesc &ED = Extenders[I];
1464  return ED.Expr.Rs.isSlot() == IsStack &&
1465  ExtValue(ED).Offset == EV.Offset;
1466  };
1467  if (all_of(P.second, SameValue)) {
1468  F->second.insert(P.second.begin(), P.second.end());
1469  P.second.clear();
1470  }
1471  }
1472 
1473  LLVM_DEBUG(dbgs() << "IMap (after fixup) = " << PrintIMap(IMap, *HRI));
1474 }
1475 
1476 void HCE::calculatePlacement(const ExtenderInit &ExtI, const IndexList &Refs,
1477  LocDefList &Defs) {
1478  if (Refs.empty())
1479  return;
1480 
1481  // The placement calculation is somewhat simple right now: it finds a
1482  // single location for the def that dominates all refs. Since this may
1483  // place the def far from the uses, producing several locations for
1484  // defs that collectively dominate all refs could be better.
1485  // For now only do the single one.
1487  DenseSet<MachineInstr*> RefMIs;
1488  const ExtDesc &ED0 = Extenders[Refs[0]];
1489  MachineBasicBlock *DomB = ED0.UseMI->getParent();
1490  RefMIs.insert(ED0.UseMI);
1491  Blocks.insert(DomB);
1492  for (unsigned i = 1, e = Refs.size(); i != e; ++i) {
1493  const ExtDesc &ED = Extenders[Refs[i]];
1494  MachineBasicBlock *MBB = ED.UseMI->getParent();
1495  RefMIs.insert(ED.UseMI);
1496  DomB = MDT->findNearestCommonDominator(DomB, MBB);
1497  Blocks.insert(MBB);
1498  }
1499 
1500 #ifndef NDEBUG
1501  // The block DomB should be dominated by the def of each register used
1502  // in the initializer.
1503  Register Rs = ExtI.second.Rs; // Only one reg allowed now.
1504  const MachineInstr *DefI = Rs.isVReg() ? MRI->getVRegDef(Rs.Reg) : nullptr;
1505 
1506  // This should be guaranteed given that the entire expression is used
1507  // at each instruction in Refs. Add an assertion just in case.
1508  assert(!DefI || MDT->dominates(DefI->getParent(), DomB));
1509 #endif
1510 
1512  if (Blocks.count(DomB)) {
1513  // Try to find the latest possible location for the def.
1514  MachineBasicBlock::iterator End = DomB->end();
1515  for (It = DomB->begin(); It != End; ++It)
1516  if (RefMIs.count(&*It))
1517  break;
1518  assert(It != End && "Should have found a ref in DomB");
1519  } else {
1520  // DomB does not contain any refs.
1521  It = DomB->getFirstTerminator();
1522  }
1523  Loc DefLoc(DomB, It);
1524  Defs.emplace_back(DefLoc, Refs);
1525 }
1526 
1527 HCE::Register HCE::insertInitializer(Loc DefL, const ExtenderInit &ExtI) {
1528  unsigned DefR = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1529  MachineBasicBlock &MBB = *DefL.Block;
1530  MachineBasicBlock::iterator At = DefL.At;
1531  DebugLoc dl = DefL.Block->findDebugLoc(DefL.At);
1532  const ExtValue &EV = ExtI.first;
1533  MachineOperand ExtOp(EV);
1534 
1535  const ExtExpr &Ex = ExtI.second;
1536  const MachineInstr *InitI = nullptr;
1537 
1538  if (Ex.Rs.isSlot()) {
1539  assert(Ex.S == 0 && "Cannot have a shift of a stack slot");
1540  assert(!Ex.Neg && "Cannot subtract a stack slot");
1541  // DefR = PS_fi Rb,##EV
1542  InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::PS_fi), DefR)
1543  .add(MachineOperand(Ex.Rs))
1544  .add(ExtOp);
1545  } else {
1546  assert((Ex.Rs.Reg == 0 || Ex.Rs.isVReg()) && "Expecting virtual register");
1547  if (Ex.trivial()) {
1548  // DefR = ##EV
1549  InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_tfrsi), DefR)
1550  .add(ExtOp);
1551  } else if (Ex.S == 0) {
1552  if (Ex.Neg) {
1553  // DefR = sub(##EV,Rb)
1554  InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_subri), DefR)
1555  .add(ExtOp)
1556  .add(MachineOperand(Ex.Rs));
1557  } else {
1558  // DefR = add(Rb,##EV)
1559  InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_addi), DefR)
1560  .add(MachineOperand(Ex.Rs))
1561  .add(ExtOp);
1562  }
1563  } else {
1564  unsigned NewOpc = Ex.Neg ? Hexagon::S4_subi_asl_ri
1565  : Hexagon::S4_addi_asl_ri;
1566  // DefR = add(##EV,asl(Rb,S))
1567  InitI = BuildMI(MBB, At, dl, HII->get(NewOpc), DefR)
1568  .add(ExtOp)
1569  .add(MachineOperand(Ex.Rs))
1570  .addImm(Ex.S);
1571  }
1572  }
1573 
1574  assert(InitI);
1575  (void)InitI;
1576  LLVM_DEBUG(dbgs() << "Inserted def in bb#" << MBB.getNumber()
1577  << " for initializer: " << PrintInit(ExtI, *HRI) << "\n "
1578  << *InitI);
1579  return { DefR, 0 };
1580 }
1581 
1582 // Replace the extender at index Idx with the register ExtR.
1583 bool HCE::replaceInstrExact(const ExtDesc &ED, Register ExtR) {
1584  MachineInstr &MI = *ED.UseMI;
1585  MachineBasicBlock &MBB = *MI.getParent();
1587  DebugLoc dl = MI.getDebugLoc();
1588  unsigned ExtOpc = MI.getOpcode();
1589 
1590  // With a few exceptions, direct replacement amounts to creating an
1591  // instruction with a corresponding register opcode, with all operands
1592  // the same, except for the register used in place of the extender.
1593  unsigned RegOpc = getDirectRegReplacement(ExtOpc);
1594 
1595  if (RegOpc == TargetOpcode::REG_SEQUENCE) {
1596  if (ExtOpc == Hexagon::A4_combineri)
1597  BuildMI(MBB, At, dl, HII->get(RegOpc))
1598  .add(MI.getOperand(0))
1599  .add(MI.getOperand(1))
1600  .addImm(Hexagon::isub_hi)
1601  .add(MachineOperand(ExtR))
1602  .addImm(Hexagon::isub_lo);
1603  else if (ExtOpc == Hexagon::A4_combineir)
1604  BuildMI(MBB, At, dl, HII->get(RegOpc))
1605  .add(MI.getOperand(0))
1606  .add(MachineOperand(ExtR))
1607  .addImm(Hexagon::isub_hi)
1608  .add(MI.getOperand(2))
1609  .addImm(Hexagon::isub_lo);
1610  else
1611  llvm_unreachable("Unexpected opcode became REG_SEQUENCE");
1612  MBB.erase(MI);
1613  return true;
1614  }
1615  if (ExtOpc == Hexagon::C2_cmpgei || ExtOpc == Hexagon::C2_cmpgeui) {
1616  unsigned NewOpc = ExtOpc == Hexagon::C2_cmpgei ? Hexagon::C2_cmplt
1617  : Hexagon::C2_cmpltu;
1618  BuildMI(MBB, At, dl, HII->get(NewOpc))
1619  .add(MI.getOperand(0))
1620  .add(MachineOperand(ExtR))
1621  .add(MI.getOperand(1));
1622  MBB.erase(MI);
1623  return true;
1624  }
1625 
1626  if (RegOpc != 0) {
1627  MachineInstrBuilder MIB = BuildMI(MBB, At, dl, HII->get(RegOpc));
1628  unsigned RegN = ED.OpNum;
1629  // Copy all operands except the one that has the extender.
1630  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1631  if (i != RegN)
1632  MIB.add(MI.getOperand(i));
1633  else
1634  MIB.add(MachineOperand(ExtR));
1635  }
1636  MIB.cloneMemRefs(MI);
1637  MBB.erase(MI);
1638  return true;
1639  }
1640 
1641  if ((MI.mayLoad() || MI.mayStore()) && !isStoreImmediate(ExtOpc)) {
1642  // For memory instructions, there is an asymmetry in the addressing
1643  // modes. Addressing modes allowing extenders can be replaced with
1644  // addressing modes that use registers, but the order of operands
1645  // (or even their number) may be different.
1646  // Replacements:
1647  // BaseImmOffset (io) -> BaseRegOffset (rr)
1648  // BaseLongOffset (ur) -> BaseRegOffset (rr)
1649  unsigned RegOpc, Shift;
1650  unsigned AM = HII->getAddrMode(MI);
1651  if (AM == HexagonII::BaseImmOffset) {
1652  RegOpc = HII->changeAddrMode_io_rr(ExtOpc);
1653  Shift = 0;
1654  } else if (AM == HexagonII::BaseLongOffset) {
1655  // Loads: Rd = L4_loadri_ur Rs, S, ##
1656  // Stores: S4_storeri_ur Rs, S, ##, Rt
1657  RegOpc = HII->changeAddrMode_ur_rr(ExtOpc);
1658  Shift = MI.getOperand(MI.mayLoad() ? 2 : 1).getImm();
1659  } else {
1660  llvm_unreachable("Unexpected addressing mode");
1661  }
1662 #ifndef NDEBUG
1663  if (RegOpc == -1u) {
1664  dbgs() << "\nExtOpc: " << HII->getName(ExtOpc) << " has no rr version\n";
1665  llvm_unreachable("No corresponding rr instruction");
1666  }
1667 #endif
1668 
1669  unsigned BaseP, OffP;
1670  HII->getBaseAndOffsetPosition(MI, BaseP, OffP);
1671 
1672  // Build an rr instruction: (RegOff + RegBase<<0)
1673  MachineInstrBuilder MIB = BuildMI(MBB, At, dl, HII->get(RegOpc));
1674  // First, add the def for loads.
1675  if (MI.mayLoad())
1676  MIB.add(getLoadResultOp(MI));
1677  // Handle possible predication.
1678  if (HII->isPredicated(MI))
1679  MIB.add(getPredicateOp(MI));
1680  // Build the address.
1681  MIB.add(MachineOperand(ExtR)); // RegOff
1682  MIB.add(MI.getOperand(BaseP)); // RegBase
1683  MIB.addImm(Shift); // << Shift
1684  // Add the stored value for stores.
1685  if (MI.mayStore())
1686  MIB.add(getStoredValueOp(MI));
1687  MIB.cloneMemRefs(MI);
1688  MBB.erase(MI);
1689  return true;
1690  }
1691 
1692 #ifndef NDEBUG
1693  dbgs() << '\n' << MI;
1694 #endif
1695  llvm_unreachable("Unhandled exact replacement");
1696  return false;
1697 }
1698 
1699 // Replace the extender ED with a form corresponding to the initializer ExtI.
1700 bool HCE::replaceInstrExpr(const ExtDesc &ED, const ExtenderInit &ExtI,
1701  Register ExtR, int32_t &Diff) {
1702  MachineInstr &MI = *ED.UseMI;
1703  MachineBasicBlock &MBB = *MI.getParent();
1705  DebugLoc dl = MI.getDebugLoc();
1706  unsigned ExtOpc = MI.getOpcode();
1707 
1708  if (ExtOpc == Hexagon::A2_tfrsi) {
1709  // A2_tfrsi is a special case: it's replaced with A2_addi, which introduces
1710  // another range. One range is the one that's common to all tfrsi's uses,
1711  // this one is the range of immediates in A2_addi. When calculating ranges,
1712  // the addi's 16-bit argument was included, so now we need to make it such
1713  // that the produced value is in the range for the uses alone.
1714  // Most of the time, simply adding Diff will make the addi produce exact
1715  // result, but if Diff is outside of the 16-bit range, some adjustment
1716  // will be needed.
1717  unsigned IdxOpc = getRegOffOpcode(ExtOpc);
1718  assert(IdxOpc == Hexagon::A2_addi);
1719 
1720  // Clamp Diff to the 16 bit range.
1721  int32_t D = isInt<16>(Diff) ? Diff : (Diff > 0 ? 32767 : -32768);
1722  if (Diff > 32767) {
1723  // Split Diff into two values: one that is close to min/max int16,
1724  // and the other being the rest, and such that both have the same
1725  // "alignment" as Diff.
1726  uint32_t UD = Diff;
1727  OffsetRange R = getOffsetRange(MI.getOperand(0));
1728  uint32_t A = std::min<uint32_t>(R.Align, 1u << countTrailingZeros(UD));
1729  D &= ~(A-1);
1730  }
1731  BuildMI(MBB, At, dl, HII->get(IdxOpc))
1732  .add(MI.getOperand(0))
1733  .add(MachineOperand(ExtR))
1734  .addImm(D);
1735  Diff -= D;
1736 #ifndef NDEBUG
1737  // Make sure the output is within allowable range for uses.
1738  // "Diff" is a difference in the "opposite direction", i.e. Ext - DefV,
1739  // not DefV - Ext, as the getOffsetRange would calculate.
1740  OffsetRange Uses = getOffsetRange(MI.getOperand(0));
1741  if (!Uses.contains(-Diff))
1742  dbgs() << "Diff: " << -Diff << " out of range " << Uses
1743  << " for " << MI;
1744  assert(Uses.contains(-Diff));
1745 #endif
1746  MBB.erase(MI);
1747  return true;
1748  }
1749 
1750  const ExtValue &EV = ExtI.first; (void)EV;
1751  const ExtExpr &Ex = ExtI.second; (void)Ex;
1752 
1753  if (ExtOpc == Hexagon::A2_addi || ExtOpc == Hexagon::A2_subri) {
1754  // If addi/subri are replaced with the exactly matching initializer,
1755  // they amount to COPY.
1756  // Check that the initializer is an exact match (for simplicity).
1757 #ifndef NDEBUG
1758  bool IsAddi = ExtOpc == Hexagon::A2_addi;
1759  const MachineOperand &RegOp = MI.getOperand(IsAddi ? 1 : 2);
1760  const MachineOperand &ImmOp = MI.getOperand(IsAddi ? 2 : 1);
1761  assert(Ex.Rs == RegOp && EV == ImmOp && Ex.Neg != IsAddi &&
1762  "Initializer mismatch");
1763 #endif
1764  BuildMI(MBB, At, dl, HII->get(TargetOpcode::COPY))
1765  .add(MI.getOperand(0))
1766  .add(MachineOperand(ExtR));
1767  Diff = 0;
1768  MBB.erase(MI);
1769  return true;
1770  }
1771  if (ExtOpc == Hexagon::M2_accii || ExtOpc == Hexagon::M2_naccii ||
1772  ExtOpc == Hexagon::S4_addaddi || ExtOpc == Hexagon::S4_subaddi) {
1773  // M2_accii: add(Rt,add(Rs,V)) (tied)
1774  // M2_naccii: sub(Rt,add(Rs,V))
1775  // S4_addaddi: add(Rt,add(Rs,V))
1776  // S4_subaddi: add(Rt,sub(V,Rs))
1777  // Check that Rs and V match the initializer expression. The Rs+V is the
1778  // combination that is considered "subexpression" for V, although Rx+V
1779  // would also be valid.
1780 #ifndef NDEBUG
1781  bool IsSub = ExtOpc == Hexagon::S4_subaddi;
1782  Register Rs = MI.getOperand(IsSub ? 3 : 2);
1783  ExtValue V = MI.getOperand(IsSub ? 2 : 3);
1784  assert(EV == V && Rs == Ex.Rs && IsSub == Ex.Neg && "Initializer mismatch");
1785 #endif
1786  unsigned NewOpc = ExtOpc == Hexagon::M2_naccii ? Hexagon::A2_sub
1787  : Hexagon::A2_add;
1788  BuildMI(MBB, At, dl, HII->get(NewOpc))
1789  .add(MI.getOperand(0))
1790  .add(MI.getOperand(1))
1791  .add(MachineOperand(ExtR));
1792  MBB.erase(MI);
1793  return true;
1794  }
1795 
1796  if (MI.mayLoad() || MI.mayStore()) {
1797  unsigned IdxOpc = getRegOffOpcode(ExtOpc);
1798  assert(IdxOpc && "Expecting indexed opcode");
1799  MachineInstrBuilder MIB = BuildMI(MBB, At, dl, HII->get(IdxOpc));
1800  // Construct the new indexed instruction.
1801  // First, add the def for loads.
1802  if (MI.mayLoad())
1803  MIB.add(getLoadResultOp(MI));
1804  // Handle possible predication.
1805  if (HII->isPredicated(MI))
1806  MIB.add(getPredicateOp(MI));
1807  // Build the address.
1808  MIB.add(MachineOperand(ExtR));
1809  MIB.addImm(Diff);
1810  // Add the stored value for stores.
1811  if (MI.mayStore())
1812  MIB.add(getStoredValueOp(MI));
1813  MIB.cloneMemRefs(MI);
1814  MBB.erase(MI);
1815  return true;
1816  }
1817 
1818 #ifndef NDEBUG
1819  dbgs() << '\n' << PrintInit(ExtI, *HRI) << " " << MI;
1820 #endif
1821  llvm_unreachable("Unhandled expr replacement");
1822  return false;
1823 }
1824 
1825 bool HCE::replaceInstr(unsigned Idx, Register ExtR, const ExtenderInit &ExtI) {
1826  if (ReplaceLimit.getNumOccurrences()) {
1827  if (ReplaceLimit <= ReplaceCounter)
1828  return false;
1829  ++ReplaceCounter;
1830  }
1831  const ExtDesc &ED = Extenders[Idx];
1832  assert((!ED.IsDef || ED.Rd.Reg != 0) && "Missing Rd for def");
1833  const ExtValue &DefV = ExtI.first;
1834  assert(ExtRoot(ExtValue(ED)) == ExtRoot(DefV) && "Extender root mismatch");
1835  const ExtExpr &DefEx = ExtI.second;
1836 
1837  ExtValue EV(ED);
1838  int32_t Diff = EV.Offset - DefV.Offset;
1839  const MachineInstr &MI = *ED.UseMI;
1840  LLVM_DEBUG(dbgs() << __func__ << " Idx:" << Idx << " ExtR:"
1841  << PrintRegister(ExtR, *HRI) << " Diff:" << Diff << '\n');
1842 
1843  // These two addressing modes must be converted into indexed forms
1844  // regardless of what the initializer looks like.
1845  bool IsAbs = false, IsAbsSet = false;
1846  if (MI.mayLoad() || MI.mayStore()) {
1847  unsigned AM = HII->getAddrMode(MI);
1848  IsAbs = AM == HexagonII::Absolute;
1849  IsAbsSet = AM == HexagonII::AbsoluteSet;
1850  }
1851 
1852  // If it's a def, remember all operands that need to be updated.
1853  // If ED is a def, and Diff is not 0, then all uses of the register Rd
1854  // defined by ED must be in the form (Rd, imm), i.e. the immediate offset
1855  // must follow the Rd in the operand list.
1856  std::vector<std::pair<MachineInstr*,unsigned>> RegOps;
1857  if (ED.IsDef && Diff != 0) {
1858  for (MachineOperand &Op : MRI->use_operands(ED.Rd.Reg)) {
1859  MachineInstr &UI = *Op.getParent();
1860  RegOps.push_back({&UI, getOperandIndex(UI, Op)});
1861  }
1862  }
1863 
1864  // Replace the instruction.
1865  bool Replaced = false;
1866  if (Diff == 0 && DefEx.trivial() && !IsAbs && !IsAbsSet)
1867  Replaced = replaceInstrExact(ED, ExtR);
1868  else
1869  Replaced = replaceInstrExpr(ED, ExtI, ExtR, Diff);
1870 
1871  if (Diff != 0 && Replaced && ED.IsDef) {
1872  // Update offsets of the def's uses.
1873  for (std::pair<MachineInstr*,unsigned> P : RegOps) {
1874  unsigned J = P.second;
1875  assert(P.first->getNumOperands() > J+1 &&
1876  P.first->getOperand(J+1).isImm());
1877  MachineOperand &ImmOp = P.first->getOperand(J+1);
1878  ImmOp.setImm(ImmOp.getImm() + Diff);
1879  }
1880  // If it was an absolute-set instruction, the "set" part has been removed.
1881  // ExtR will now be the register with the extended value, and since all
1882  // users of Rd have been updated, all that needs to be done is to replace
1883  // Rd with ExtR.
1884  if (IsAbsSet) {
1885  assert(ED.Rd.Sub == 0 && ExtR.Sub == 0);
1886  MRI->replaceRegWith(ED.Rd.Reg, ExtR.Reg);
1887  }
1888  }
1889 
1890  return Replaced;
1891 }
1892 
1893 bool HCE::replaceExtenders(const AssignmentMap &IMap) {
1894  LocDefList Defs;
1895  bool Changed = false;
1896 
1897  for (const std::pair<ExtenderInit,IndexList> &P : IMap) {
1898  const IndexList &Idxs = P.second;
1899  if (Idxs.size() < CountThreshold)
1900  continue;
1901 
1902  Defs.clear();
1903  calculatePlacement(P.first, Idxs, Defs);
1904  for (const std::pair<Loc,IndexList> &Q : Defs) {
1905  Register DefR = insertInitializer(Q.first, P.first);
1906  NewRegs.push_back(DefR.Reg);
1907  for (unsigned I : Q.second)
1908  Changed |= replaceInstr(I, DefR, P.first);
1909  }
1910  }
1911  return Changed;
1912 }
1913 
1914 unsigned HCE::getOperandIndex(const MachineInstr &MI,
1915  const MachineOperand &Op) const {
1916  for (unsigned i = 0, n = MI.getNumOperands(); i != n; ++i)
1917  if (&MI.getOperand(i) == &Op)
1918  return i;
1919  llvm_unreachable("Not an operand of MI");
1920 }
1921 
1922 const MachineOperand &HCE::getPredicateOp(const MachineInstr &MI) const {
1923  assert(HII->isPredicated(MI));
1924  for (const MachineOperand &Op : MI.operands()) {
1925  if (!Op.isReg() || !Op.isUse() ||
1926  MRI->getRegClass(Op.getReg()) != &Hexagon::PredRegsRegClass)
1927  continue;
1928  assert(Op.getSubReg() == 0 && "Predicate register with a subregister");
1929  return Op;
1930  }
1931  llvm_unreachable("Predicate operand not found");
1932 }
1933 
1934 const MachineOperand &HCE::getLoadResultOp(const MachineInstr &MI) const {
1935  assert(MI.mayLoad());
1936  return MI.getOperand(0);
1937 }
1938 
1939 const MachineOperand &HCE::getStoredValueOp(const MachineInstr &MI) const {
1940  assert(MI.mayStore());
1941  return MI.getOperand(MI.getNumExplicitOperands()-1);
1942 }
1943 
1944 bool HCE::runOnMachineFunction(MachineFunction &MF) {
1945  if (skipFunction(MF.getFunction()))
1946  return false;
1947  if (MF.getFunction().hasPersonalityFn()) {
1948  LLVM_DEBUG(dbgs() << getPassName() << ": skipping " << MF.getName()
1949  << " due to exception handling\n");
1950  return false;
1951  }
1952  LLVM_DEBUG(MF.print(dbgs() << "Before " << getPassName() << '\n', nullptr));
1953 
1954  HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
1955  HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
1956  MDT = &getAnalysis<MachineDominatorTree>();
1957  MRI = &MF.getRegInfo();
1958  AssignmentMap IMap;
1959 
1960  collect(MF);
1961  llvm::sort(Extenders, [this](const ExtDesc &A, const ExtDesc &B) {
1962  ExtValue VA(A), VB(B);
1963  if (VA != VB)
1964  return VA < VB;
1965  const MachineInstr *MA = A.UseMI;
1966  const MachineInstr *MB = B.UseMI;
1967  if (MA == MB) {
1968  // If it's the same instruction, compare operand numbers.
1969  return A.OpNum < B.OpNum;
1970  }
1971 
1972  const MachineBasicBlock *BA = MA->getParent();
1973  const MachineBasicBlock *BB = MB->getParent();
1974  assert(BA->getNumber() != -1 && BB->getNumber() != -1);
1975  if (BA != BB)
1976  return BA->getNumber() < BB->getNumber();
1977  return MDT->dominates(MA, MB);
1978  });
1979 
1980  bool Changed = false;
1981  LLVM_DEBUG(dbgs() << "Collected " << Extenders.size() << " extenders\n");
1982  for (unsigned I = 0, E = Extenders.size(); I != E; ) {
1983  unsigned B = I;
1984  const ExtRoot &T = Extenders[B].getOp();
1985  while (I != E && ExtRoot(Extenders[I].getOp()) == T)
1986  ++I;
1987 
1988  IMap.clear();
1989  assignInits(T, B, I, IMap);
1990  Changed |= replaceExtenders(IMap);
1991  }
1992 
1993  LLVM_DEBUG({
1994  if (Changed)
1995  MF.print(dbgs() << "After " << getPassName() << '\n', nullptr);
1996  else
1997  dbgs() << "No changes\n";
1998  });
1999  return Changed;
2000 }
2001 
2003  return new HexagonConstExtenders();
2004 }
unsigned getTargetFlags() const
const MachineInstrBuilder & add(const MachineOperand &MO) const
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:24
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
bool isTargetIndex() const
isTargetIndex - Tests if this is a MO_TargetIndex operand.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:250
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:383
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
static MachineOperand CreateJTI(unsigned Idx, unsigned char TargetFlags=0)
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:164
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Address of indexed Jump Table for switch.
unsigned Reg
unsigned getSubReg() const
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:1186
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:299
constexpr bool isInt< 16 >(int64_t x)
Definition: MathExtras.h:306
A debug info location.
Definition: DebugLoc.h:34
F(f)
bool isCPI() const
isCPI - Tests if this is a MO_ConstantPoolIndex operand.
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:399
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:459
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
return AArch64::GPR64RegClass contains(Reg)
static MachineOperand CreateReg(unsigned Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
static int stackSlot2Index(unsigned Reg)
Compute the frame index from a register value representing a stack slot.
The address of a basic block.
Definition: Constants.h:840
uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the largest uint64_t less than or equal to Value and is Skew mod Align.
Definition: MathExtras.h:718
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
constexpr char SymbolName[]
Key for Kernel::Metadata::mSymbolName.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const ConstantFP * getFPImm() const
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:412
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Target-dependent index+offset operand.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
Name of external global symbol.
static int32_t adjustUp(int32_t V, uint8_t A, uint8_t O)
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
const char * getSymbolName() const
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
void initializeHexagonConstExtendersPass(PassRegistry &)
static cl::opt< unsigned > CountThreshold("hexagon-cext-threshold", cl::init(3), cl::Hidden, cl::ZeroOrMore, cl::desc("Minimum number of extenders to trigger replacement"))
FunctionPass * createHexagonConstExtenders()
bool isFPImm() const
isFPImm - Tests if this is a MO_FPImmediate operand.
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:702
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1166
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:820
#define P(N)
Address of a global value.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
unsigned const MachineRegisterInfo * MRI
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0&#39;s from the least significant bit to the most stopping at the first 1...
Definition: MathExtras.h:120
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:429
static MachineOperand CreateCPI(unsigned Idx, int Offset, unsigned char TargetFlags=0)
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static MachineOperand CreateFPImm(const ConstantFP *CFP)
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1185
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const GlobalValue * getGlobal() const
#define H(x, y, z)
Definition: MD5.cpp:57
static ManagedStatic< OptionRegistry > OR
Definition: Options.cpp:31
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:264
static MachineOperand CreateBA(const BlockAddress *BA, int64_t Offset, unsigned char TargetFlags=0)
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1193
Address of a basic block.
void setImm(int64_t immVal)
static MachineOperand CreateGA(const GlobalValue *GV, int64_t Offset, unsigned char TargetFlags=0)
static MachineOperand CreateTargetIndex(unsigned Idx, int64_t Offset, unsigned char TargetFlags=0)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
self_iterator getIterator()
Definition: ilist_node.h:82
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream...
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.
unsigned getNumExplicitOperands() const
Returns the number of non-implicit operands.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1116
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:210
static bool isStackSlot(unsigned Reg)
isStackSlot - Sometimes it is useful the be able to store a non-negative frame index in a variable th...
bool isJTI() const
isJTI - Tests if this is a MO_JumpTableIndex operand.
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
hexagon cext Hexagon constant extender optimization
Promote Memory to Register
Definition: Mem2Reg.cpp:110
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
int64_t getImm() const
bool isBlockAddress() const
isBlockAddress - Tests if this is a MO_BlockAddress operand.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
static int32_t adjustDown(int32_t V, uint8_t A, uint8_t O)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:539
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
static MachineOperand CreateES(const char *SymName, unsigned char TargetFlags=0)
static LLVM_ATTRIBUTE_UNUSED unsigned getMemAccessSizeInBytes(MemAccessSize S)
bool mayStore() const
Return true if this instruction could possibly modify memory.
Definition: MCInstrDesc.h:405
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1969
Representation of each machine instruction.
Definition: MachineInstr.h:64
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
static ValueLatticeElement intersect(const ValueLatticeElement &A, const ValueLatticeElement &B)
Combine two sets of facts about the same value into a single set of facts.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
int64_t getOffset() const
Return the offset from the symbol in this operand.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
const BlockAddress * getBlockAddress() const
static MachineOperand CreateImm(int64_t Val)
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
const MachineInstrBuilder & cloneMemRefs(const MachineInstr &OtherMI) const
hexagon cext Hexagon constant extender static false unsigned ReplaceCounter
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
static cl::opt< unsigned > ReplaceLimit("hexagon-cext-limit", cl::init(0), cl::Hidden, cl::ZeroOrMore, cl::desc("Maximum number of replacements"))
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:92
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2039
bool isSymbol() const
isSymbol - Tests if this is a MO_ExternalSymbol operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
const unsigned Kind
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:807
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
INITIALIZE_PASS_BEGIN(HexagonConstExtenders, "hexagon-cext-opt", "Hexagon constant-extender optimization", false, false) INITIALIZE_PASS_END(HexagonConstExtenders
Floating-point immediate operand.
A vector that has set insertion semantics.
Definition: SetVector.h:41
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
hexagon cext opt
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
APInt bitcastToAPInt() const
Definition: APFloat.h:1094
Address of indexed Constant in Constant Pool.
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:160
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1967
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
static MachineOperand CreateFI(int Idx)
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
static unsigned index2StackSlot(int FI)
Convert a non-negative frame index to a stack slot register value.