LLVM  10.0.0svn
HexagonConstExtenders.cpp
Go to the documentation of this file.
1 //===- HexagonConstExtenders.cpp ------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "HexagonInstrInfo.h"
10 #include "HexagonRegisterInfo.h"
11 #include "HexagonSubtarget.h"
12 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/CodeGen/Register.h"
18 #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 && !llvm::Register::isStackSlot(Reg) &&
246  }
247  bool isSlot() const {
248  return Reg != 0 && llvm::Register::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  llvm::Register 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.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:484
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:249
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:384
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:179
static bool isStackSlot(unsigned Reg)
isStackSlot - Sometimes it is useful the be able to store a non-negative frame index in a variable th...
Definition: Register.h:45
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:1165
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:322
constexpr bool isInt< 16 >(int64_t x)
Definition: MathExtras.h:342
A debug info location.
Definition: DebugLoc.h:33
F(f)
bool isCPI() const
isCPI - Tests if this is a MO_ConstantPoolIndex operand.
Node(Kind K_, Cache RHSComponentCache_=Cache::No, Cache ArrayCache_=Cache::No, Cache FunctionCache_=Cache::No)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:418
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:476
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
return AArch64::GPR64RegClass contains(Reg)
unsigned 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:156
The address of a basic block.
Definition: Constants.h:839
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:737
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
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...
static void zero(T &Obj)
Definition: ELFEmitter.cpp:197
static MachineOperand CreateGA(const GlobalValue *GV, int64_t Offset, unsigned TargetFlags=0)
const ConstantFP * getFPImm() const
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:413
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:41
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:410
const char * getSymbolName() const
static MachineOperand CreateTargetIndex(unsigned Idx, int64_t Offset, unsigned TargetFlags=0)
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:732
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
static unsigned index2StackSlot(int FI)
Convert a non-negative frame index to a stack slot register value.
Definition: Register.h:56
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:1165
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:843
#define P(N)
Address of a global value.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
unsigned const MachineRegisterInfo * MRI
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:465
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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 int stackSlot2Index(unsigned Reg)
Compute the frame index from a register value representing a stack slot.
Definition: Register.h:50
static MachineOperand CreateJTI(unsigned Idx, unsigned TargetFlags=0)
static MachineOperand CreateFPImm(const ConstantFP *CFP)
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1184
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:30
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:263
static MachineOperand CreateCPI(unsigned Idx, int Offset, unsigned 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:1172
Address of a basic block.
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:180
constexpr double e
Definition: MathExtras.h:57
void setImm(int64_t immVal)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
self_iterator getIterator()
Definition: ilist_node.h:81
static MachineOperand CreateReg(Register 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)
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.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:40
static MachineOperand CreateES(const char *SymName, unsigned TargetFlags=0)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
bool isJTI() const
isJTI - Tests if this is a MO_JumpTableIndex operand.
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:215
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:837
hexagon cext Hexagon constant extender optimization
Promote Memory to Register
Definition: Mem2Reg.cpp:109
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:132
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:585
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
static LLVM_ATTRIBUTE_UNUSED unsigned getMemAccessSizeInBytes(MemAccessSize S)
bool mayStore() const
Return true if this instruction could possibly modify memory.
Definition: MCInstrDesc.h:424
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
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:1977
Representation of each machine instruction.
Definition: MachineInstr.h:63
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:106
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:91
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
bool isSymbol() const
isSymbol - Tests if this is a MO_ExternalSymbol operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:830
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
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:40
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
static MachineOperand CreateBA(const BlockAddress *BA, int64_t Offset, unsigned TargetFlags=0)
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
hexagon cext opt
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
APInt bitcastToAPInt() const
Definition: APFloat.h:1109
Address of indexed Constant in Constant Pool.
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1975
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
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...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19