LLVM  16.0.0git
HexagonConstPropagation.cpp
Go to the documentation of this file.
1 //===- HexagonConstPropagation.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/APFloat.h"
13 #include "llvm/ADT/APInt.h"
15 #include "llvm/ADT/SetVector.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/StringRef.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/Type.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/Casting.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/Debug.h"
36 #include <cassert>
37 #include <cstdint>
38 #include <cstring>
39 #include <iterator>
40 #include <map>
41 #include <queue>
42 #include <set>
43 #include <utility>
44 #include <vector>
45 
46 #define DEBUG_TYPE "hcp"
47 
48 using namespace llvm;
49 
50 namespace {
51 
52  // Properties of a value that are tracked by the propagation.
53  // A property that is marked as present (i.e. bit is set) dentes that the
54  // value is known (proven) to have this property. Not all combinations
55  // of bits make sense, for example Zero and NonZero are mutually exclusive,
56  // but on the other hand, Zero implies Finite. In this case, whenever
57  // the Zero property is present, Finite should also be present.
58  class ConstantProperties {
59  public:
60  enum {
61  Unknown = 0x0000,
62  Zero = 0x0001,
63  NonZero = 0x0002,
64  Finite = 0x0004,
65  Infinity = 0x0008,
66  NaN = 0x0010,
67  SignedZero = 0x0020,
68  NumericProperties = (Zero|NonZero|Finite|Infinity|NaN|SignedZero),
69  PosOrZero = 0x0100,
70  NegOrZero = 0x0200,
71  SignProperties = (PosOrZero|NegOrZero),
72  Everything = (NumericProperties|SignProperties)
73  };
74 
75  // For a given constant, deduce the set of trackable properties that this
76  // constant has.
77  static uint32_t deduce(const Constant *C);
78  };
79 
80  // A representation of a register as it can appear in a MachineOperand,
81  // i.e. a pair register:subregister.
82 
83  // FIXME: Use TargetInstrInfo::RegSubRegPair. Also duplicated in
84  // HexagonGenPredicate
85  struct RegisterSubReg {
86  Register Reg;
87  unsigned SubReg;
88 
89  explicit RegisterSubReg(unsigned R, unsigned SR = 0) : Reg(R), SubReg(SR) {}
90  explicit RegisterSubReg(const MachineOperand &MO)
91  : Reg(MO.getReg()), SubReg(MO.getSubReg()) {}
92 
93  void print(const TargetRegisterInfo *TRI = nullptr) const {
94  dbgs() << printReg(Reg, TRI, SubReg);
95  }
96 
97  bool operator== (const RegisterSubReg &R) const {
98  return (Reg == R.Reg) && (SubReg == R.SubReg);
99  }
100  };
101 
102  // Lattice cell, based on that was described in the W-Z paper on constant
103  // propagation.
104  // Latice cell will be allowed to hold multiple constant values. While
105  // multiple values would normally indicate "bottom", we can still derive
106  // some useful information from them. For example, comparison X > 0
107  // could be folded if all the values in the cell associated with X are
108  // positive.
109  class LatticeCell {
110  private:
111  enum { Normal, Top, Bottom };
112 
113  static const unsigned MaxCellSize = 4;
114 
115  unsigned Kind:2;
116  unsigned Size:3;
117  unsigned IsSpecial:1;
118  unsigned :0;
119 
120  public:
121  union {
122  uint32_t Properties;
123  const Constant *Value;
124  const Constant *Values[MaxCellSize];
125  };
126 
127  LatticeCell() : Kind(Top), Size(0), IsSpecial(false) {
128  for (const Constant *&Value : Values)
129  Value = nullptr;
130  }
131 
132  bool meet(const LatticeCell &L);
133  bool add(const Constant *C);
134  bool add(uint32_t Property);
135  uint32_t properties() const;
136  unsigned size() const { return Size; }
137 
138  LatticeCell(const LatticeCell &L) {
139  // This memcpy also copies Properties (when L.Size == 0).
140  uint32_t N =
141  L.IsSpecial ? sizeof L.Properties : L.Size * sizeof(const Constant *);
142  memcpy(Values, L.Values, N);
143  Kind = L.Kind;
144  Size = L.Size;
145  IsSpecial = L.IsSpecial;
146  }
147 
148  LatticeCell &operator=(const LatticeCell &L) {
149  if (this != &L) {
150  // This memcpy also copies Properties (when L.Size == 0).
151  uint32_t N = L.IsSpecial ? sizeof L.Properties
152  : L.Size * sizeof(const Constant *);
153  memcpy(Values, L.Values, N);
154  Kind = L.Kind;
155  Size = L.Size;
156  IsSpecial = L.IsSpecial;
157  }
158  return *this;
159  }
160 
161  bool isSingle() const { return size() == 1; }
162  bool isProperty() const { return IsSpecial; }
163  bool isTop() const { return Kind == Top; }
164  bool isBottom() const { return Kind == Bottom; }
165 
166  bool setBottom() {
167  bool Changed = (Kind != Bottom);
168  Kind = Bottom;
169  Size = 0;
170  IsSpecial = false;
171  return Changed;
172  }
173 
174  void print(raw_ostream &os) const;
175 
176  private:
177  void setProperty() {
178  IsSpecial = true;
179  Size = 0;
180  Kind = Normal;
181  }
182 
183  bool convertToProperty();
184  };
185 
186 #ifndef NDEBUG
187  raw_ostream &operator<< (raw_ostream &os, const LatticeCell &L) {
188  L.print(os);
189  return os;
190  }
191 #endif
192 
193  class MachineConstEvaluator;
194 
195  class MachineConstPropagator {
196  public:
197  MachineConstPropagator(MachineConstEvaluator &E) : MCE(E) {
198  Bottom.setBottom();
199  }
200 
201  // Mapping: vreg -> cell
202  // The keys are registers _without_ subregisters. This won't allow
203  // definitions in the form of "vreg:subreg = ...". Such definitions
204  // would be questionable from the point of view of SSA, since the "vreg"
205  // could not be initialized in its entirety (specifically, an instruction
206  // defining the "other part" of "vreg" would also count as a definition
207  // of "vreg", which would violate the SSA).
208  // If a value of a pair vreg:subreg needs to be obtained, the cell for
209  // "vreg" needs to be looked up, and then the value of subregister "subreg"
210  // needs to be evaluated.
211  class CellMap {
212  public:
213  CellMap() {
214  assert(Top.isTop());
215  Bottom.setBottom();
216  }
217 
218  void clear() { Map.clear(); }
219 
220  bool has(Register R) const {
221  // All non-virtual registers are considered "bottom".
222  if (!R.isVirtual())
223  return true;
224  MapType::const_iterator F = Map.find(R);
225  return F != Map.end();
226  }
227 
228  const LatticeCell &get(Register R) const {
229  if (!R.isVirtual())
230  return Bottom;
231  MapType::const_iterator F = Map.find(R);
232  if (F != Map.end())
233  return F->second;
234  return Top;
235  }
236 
237  // Invalidates any const references.
238  void update(Register R, const LatticeCell &L) { Map[R] = L; }
239 
240  void print(raw_ostream &os, const TargetRegisterInfo &TRI) const;
241 
242  private:
243  using MapType = std::map<Register, LatticeCell>;
244 
245  MapType Map;
246  // To avoid creating "top" entries, return a const reference to
247  // this cell in "get". Also, have a "Bottom" cell to return from
248  // get when a value of a physical register is requested.
249  LatticeCell Top, Bottom;
250 
251  public:
252  using const_iterator = MapType::const_iterator;
253 
254  const_iterator begin() const { return Map.begin(); }
255  const_iterator end() const { return Map.end(); }
256  };
257 
258  bool run(MachineFunction &MF);
259 
260  private:
261  void visitPHI(const MachineInstr &PN);
262  void visitNonBranch(const MachineInstr &MI);
263  void visitBranchesFrom(const MachineInstr &BrI);
264  void visitUsesOf(unsigned R);
265  bool computeBlockSuccessors(const MachineBasicBlock *MB,
267  void removeCFGEdge(MachineBasicBlock *From, MachineBasicBlock *To);
268 
269  void propagate(MachineFunction &MF);
270  bool rewrite(MachineFunction &MF);
271 
272  MachineRegisterInfo *MRI = nullptr;
273  MachineConstEvaluator &MCE;
274 
275  using CFGEdge = std::pair<unsigned, unsigned>;
276  using SetOfCFGEdge = std::set<CFGEdge>;
277  using SetOfInstr = std::set<const MachineInstr *>;
278  using QueueOfCFGEdge = std::queue<CFGEdge>;
279 
280  LatticeCell Bottom;
281  CellMap Cells;
282  SetOfCFGEdge EdgeExec;
283  SetOfInstr InstrExec;
284  QueueOfCFGEdge FlowQ;
285  };
286 
287  // The "evaluator/rewriter" of machine instructions. This is an abstract
288  // base class that provides the interface that the propagator will use,
289  // as well as some helper functions that are target-independent.
290  class MachineConstEvaluator {
291  public:
292  MachineConstEvaluator(MachineFunction &Fn)
293  : TRI(*Fn.getSubtarget().getRegisterInfo()),
294  MF(Fn), CX(Fn.getFunction().getContext()) {}
295  virtual ~MachineConstEvaluator() = default;
296 
297  // The required interface:
298  // - A set of three "evaluate" functions. Each returns "true" if the
299  // computation succeeded, "false" otherwise.
300  // (1) Given an instruction MI, and the map with input values "Inputs",
301  // compute the set of output values "Outputs". An example of when
302  // the computation can "fail" is if MI is not an instruction that
303  // is recognized by the evaluator.
304  // (2) Given a register R (as reg:subreg), compute the cell that
305  // corresponds to the "subreg" part of the given register.
306  // (3) Given a branch instruction BrI, compute the set of target blocks.
307  // If the branch can fall-through, add null (0) to the list of
308  // possible targets.
309  // - A function "rewrite", that given the cell map after propagation,
310  // could rewrite instruction MI in a more beneficial form. Return
311  // "true" if a change has been made, "false" otherwise.
312  using CellMap = MachineConstPropagator::CellMap;
313  virtual bool evaluate(const MachineInstr &MI, const CellMap &Inputs,
314  CellMap &Outputs) = 0;
315  virtual bool evaluate(const RegisterSubReg &R, const LatticeCell &SrcC,
316  LatticeCell &Result) = 0;
317  virtual bool evaluate(const MachineInstr &BrI, const CellMap &Inputs,
319  bool &CanFallThru) = 0;
320  virtual bool rewrite(MachineInstr &MI, const CellMap &Inputs) = 0;
321 
322  const TargetRegisterInfo &TRI;
323 
324  protected:
325  MachineFunction &MF;
326  LLVMContext &CX;
327 
328  struct Comparison {
329  enum {
330  Unk = 0x00,
331  EQ = 0x01,
332  NE = 0x02,
333  L = 0x04, // Less-than property.
334  G = 0x08, // Greater-than property.
335  U = 0x40, // Unsigned property.
336  LTs = L,
337  LEs = L | EQ,
338  GTs = G,
339  GEs = G | EQ,
340  LTu = L | U,
341  LEu = L | EQ | U,
342  GTu = G | U,
343  GEu = G | EQ | U
344  };
345 
346  static uint32_t negate(uint32_t Cmp) {
347  if (Cmp == EQ)
348  return NE;
349  if (Cmp == NE)
350  return EQ;
351  assert((Cmp & (L|G)) != (L|G));
352  return Cmp ^ (L|G);
353  }
354  };
355 
356  // Helper functions.
357 
358  bool getCell(const RegisterSubReg &R, const CellMap &Inputs, LatticeCell &RC);
359  bool constToInt(const Constant *C, APInt &Val) const;
360  bool constToFloat(const Constant *C, APFloat &Val) const;
361  const ConstantInt *intToConst(const APInt &Val) const;
362 
363  // Compares.
364  bool evaluateCMPrr(uint32_t Cmp, const RegisterSubReg &R1, const RegisterSubReg &R2,
365  const CellMap &Inputs, bool &Result);
366  bool evaluateCMPri(uint32_t Cmp, const RegisterSubReg &R1, const APInt &A2,
367  const CellMap &Inputs, bool &Result);
368  bool evaluateCMPrp(uint32_t Cmp, const RegisterSubReg &R1, uint64_t Props2,
369  const CellMap &Inputs, bool &Result);
370  bool evaluateCMPii(uint32_t Cmp, const APInt &A1, const APInt &A2,
371  bool &Result);
372  bool evaluateCMPpi(uint32_t Cmp, uint32_t Props, const APInt &A2,
373  bool &Result);
374  bool evaluateCMPpp(uint32_t Cmp, uint32_t Props1, uint32_t Props2,
375  bool &Result);
376 
377  bool evaluateCOPY(const RegisterSubReg &R1, const CellMap &Inputs,
378  LatticeCell &Result);
379 
380  // Logical operations.
381  bool evaluateANDrr(const RegisterSubReg &R1, const RegisterSubReg &R2,
382  const CellMap &Inputs, LatticeCell &Result);
383  bool evaluateANDri(const RegisterSubReg &R1, const APInt &A2,
384  const CellMap &Inputs, LatticeCell &Result);
385  bool evaluateANDii(const APInt &A1, const APInt &A2, APInt &Result);
386  bool evaluateORrr(const RegisterSubReg &R1, const RegisterSubReg &R2,
387  const CellMap &Inputs, LatticeCell &Result);
388  bool evaluateORri(const RegisterSubReg &R1, const APInt &A2,
389  const CellMap &Inputs, LatticeCell &Result);
390  bool evaluateORii(const APInt &A1, const APInt &A2, APInt &Result);
391  bool evaluateXORrr(const RegisterSubReg &R1, const RegisterSubReg &R2,
392  const CellMap &Inputs, LatticeCell &Result);
393  bool evaluateXORri(const RegisterSubReg &R1, const APInt &A2,
394  const CellMap &Inputs, LatticeCell &Result);
395  bool evaluateXORii(const APInt &A1, const APInt &A2, APInt &Result);
396 
397  // Extensions.
398  bool evaluateZEXTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,
399  const CellMap &Inputs, LatticeCell &Result);
400  bool evaluateZEXTi(const APInt &A1, unsigned Width, unsigned Bits,
401  APInt &Result);
402  bool evaluateSEXTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,
403  const CellMap &Inputs, LatticeCell &Result);
404  bool evaluateSEXTi(const APInt &A1, unsigned Width, unsigned Bits,
405  APInt &Result);
406 
407  // Leading/trailing bits.
408  bool evaluateCLBr(const RegisterSubReg &R1, bool Zeros, bool Ones,
409  const CellMap &Inputs, LatticeCell &Result);
410  bool evaluateCLBi(const APInt &A1, bool Zeros, bool Ones, APInt &Result);
411  bool evaluateCTBr(const RegisterSubReg &R1, bool Zeros, bool Ones,
412  const CellMap &Inputs, LatticeCell &Result);
413  bool evaluateCTBi(const APInt &A1, bool Zeros, bool Ones, APInt &Result);
414 
415  // Bitfield extract.
416  bool evaluateEXTRACTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,
417  unsigned Offset, bool Signed, const CellMap &Inputs,
418  LatticeCell &Result);
419  bool evaluateEXTRACTi(const APInt &A1, unsigned Bits, unsigned Offset,
420  bool Signed, APInt &Result);
421  // Vector operations.
422  bool evaluateSplatr(const RegisterSubReg &R1, unsigned Bits, unsigned Count,
423  const CellMap &Inputs, LatticeCell &Result);
424  bool evaluateSplati(const APInt &A1, unsigned Bits, unsigned Count,
425  APInt &Result);
426  };
427 
428 } // end anonymous namespace
429 
430 uint32_t ConstantProperties::deduce(const Constant *C) {
431  if (isa<ConstantInt>(C)) {
432  const ConstantInt *CI = cast<ConstantInt>(C);
433  if (CI->isZero())
434  return Zero | PosOrZero | NegOrZero | Finite;
435  uint32_t Props = (NonZero | Finite);
436  if (CI->isNegative())
437  return Props | NegOrZero;
438  return Props | PosOrZero;
439  }
440 
441  if (isa<ConstantFP>(C)) {
442  const ConstantFP *CF = cast<ConstantFP>(C);
443  uint32_t Props = CF->isNegative() ? (NegOrZero|NonZero)
444  : PosOrZero;
445  if (CF->isZero())
446  return (Props & ~NumericProperties) | (Zero|Finite);
447  Props = (Props & ~NumericProperties) | NonZero;
448  if (CF->isNaN())
449  return (Props & ~NumericProperties) | NaN;
450  const APFloat &Val = CF->getValueAPF();
451  if (Val.isInfinity())
452  return (Props & ~NumericProperties) | Infinity;
453  Props |= Finite;
454  return Props;
455  }
456 
457  return Unknown;
458 }
459 
460 // Convert a cell from a set of specific values to a cell that tracks
461 // properties.
462 bool LatticeCell::convertToProperty() {
463  if (isProperty())
464  return false;
465  // Corner case: converting a fresh (top) cell to "special".
466  // This can happen, when adding a property to a top cell.
467  uint32_t Everything = ConstantProperties::Everything;
468  uint32_t Ps = !isTop() ? properties()
469  : Everything;
470  if (Ps != ConstantProperties::Unknown) {
471  Properties = Ps;
472  setProperty();
473  } else {
474  setBottom();
475  }
476  return true;
477 }
478 
479 #ifndef NDEBUG
480 void LatticeCell::print(raw_ostream &os) const {
481  if (isProperty()) {
482  os << "{ ";
483  uint32_t Ps = properties();
484  if (Ps & ConstantProperties::Zero)
485  os << "zero ";
486  if (Ps & ConstantProperties::NonZero)
487  os << "nonzero ";
488  if (Ps & ConstantProperties::Finite)
489  os << "finite ";
490  if (Ps & ConstantProperties::Infinity)
491  os << "infinity ";
492  if (Ps & ConstantProperties::NaN)
493  os << "nan ";
494  if (Ps & ConstantProperties::PosOrZero)
495  os << "poz ";
496  if (Ps & ConstantProperties::NegOrZero)
497  os << "nez ";
498  os << '}';
499  return;
500  }
501 
502  os << "{ ";
503  if (isBottom()) {
504  os << "bottom";
505  } else if (isTop()) {
506  os << "top";
507  } else {
508  for (unsigned i = 0; i < size(); ++i) {
509  const Constant *C = Values[i];
510  if (i != 0)
511  os << ", ";
512  C->print(os);
513  }
514  }
515  os << " }";
516 }
517 #endif
518 
519 // "Meet" operation on two cells. This is the key of the propagation
520 // algorithm.
521 bool LatticeCell::meet(const LatticeCell &L) {
522  bool Changed = false;
523  if (L.isBottom())
524  Changed = setBottom();
525  if (isBottom() || L.isTop())
526  return Changed;
527  if (isTop()) {
528  *this = L;
529  // L can be neither Top nor Bottom, so *this must have changed.
530  return true;
531  }
532 
533  // Top/bottom cases covered. Need to integrate L's set into ours.
534  if (L.isProperty())
535  return add(L.properties());
536  for (unsigned i = 0; i < L.size(); ++i) {
537  const Constant *LC = L.Values[i];
538  Changed |= add(LC);
539  }
540  return Changed;
541 }
542 
543 // Add a new constant to the cell. This is actually where the cell update
544 // happens. If a cell has room for more constants, the new constant is added.
545 // Otherwise, the cell is converted to a "property" cell (i.e. a cell that
546 // will track properties of the associated values, and not the values
547 // themselves. Care is taken to handle special cases, like "bottom", etc.
548 bool LatticeCell::add(const Constant *LC) {
549  assert(LC);
550  if (isBottom())
551  return false;
552 
553  if (!isProperty()) {
554  // Cell is not special. Try to add the constant here first,
555  // if there is room.
556  unsigned Index = 0;
557  while (Index < Size) {
558  const Constant *C = Values[Index];
559  // If the constant is already here, no change is needed.
560  if (C == LC)
561  return false;
562  Index++;
563  }
564  if (Index < MaxCellSize) {
565  Values[Index] = LC;
566  Kind = Normal;
567  Size++;
568  return true;
569  }
570  }
571 
572  bool Changed = false;
573 
574  // This cell is special, or is not special, but is full. After this
575  // it will be special.
576  Changed = convertToProperty();
577  uint32_t Ps = properties();
578  uint32_t NewPs = Ps & ConstantProperties::deduce(LC);
579  if (NewPs == ConstantProperties::Unknown) {
580  setBottom();
581  return true;
582  }
583  if (Ps != NewPs) {
584  Properties = NewPs;
585  Changed = true;
586  }
587  return Changed;
588 }
589 
590 // Add a property to the cell. This will force the cell to become a property-
591 // tracking cell.
592 bool LatticeCell::add(uint32_t Property) {
593  bool Changed = convertToProperty();
594  uint32_t Ps = properties();
595  if (Ps == (Ps & Property))
596  return Changed;
597  Properties = Property & Ps;
598  return true;
599 }
600 
601 // Return the properties of the values in the cell. This is valid for any
602 // cell, and does not alter the cell itself.
603 uint32_t LatticeCell::properties() const {
604  if (isProperty())
605  return Properties;
606  assert(!isTop() && "Should not call this for a top cell");
607  if (isBottom())
609 
610  assert(size() > 0 && "Empty cell");
611  uint32_t Ps = ConstantProperties::deduce(Values[0]);
612  for (unsigned i = 1; i < size(); ++i) {
613  if (Ps == ConstantProperties::Unknown)
614  break;
615  Ps &= ConstantProperties::deduce(Values[i]);
616  }
617  return Ps;
618 }
619 
620 #ifndef NDEBUG
622  const TargetRegisterInfo &TRI) const {
623  for (auto &I : Map)
624  dbgs() << " " << printReg(I.first, &TRI) << " -> " << I.second << '\n';
625 }
626 #endif
627 
628 void MachineConstPropagator::visitPHI(const MachineInstr &PN) {
629  const MachineBasicBlock *MB = PN.getParent();
630  unsigned MBN = MB->getNumber();
631  LLVM_DEBUG(dbgs() << "Visiting FI(" << printMBBReference(*MB) << "): " << PN);
632 
633  const MachineOperand &MD = PN.getOperand(0);
634  RegisterSubReg DefR(MD);
635  assert(DefR.Reg.isVirtual());
636 
637  bool Changed = false;
638 
639  // If the def has a sub-register, set the corresponding cell to "bottom".
640  if (DefR.SubReg) {
641 Bottomize:
642  const LatticeCell &T = Cells.get(DefR.Reg);
643  Changed = !T.isBottom();
644  Cells.update(DefR.Reg, Bottom);
645  if (Changed)
646  visitUsesOf(DefR.Reg);
647  return;
648  }
649 
650  LatticeCell DefC = Cells.get(DefR.Reg);
651 
652  for (unsigned i = 1, n = PN.getNumOperands(); i < n; i += 2) {
653  const MachineBasicBlock *PB = PN.getOperand(i+1).getMBB();
654  unsigned PBN = PB->getNumber();
655  if (!EdgeExec.count(CFGEdge(PBN, MBN))) {
656  LLVM_DEBUG(dbgs() << " edge " << printMBBReference(*PB) << "->"
657  << printMBBReference(*MB) << " not executable\n");
658  continue;
659  }
660  const MachineOperand &SO = PN.getOperand(i);
661  RegisterSubReg UseR(SO);
662  // If the input is not a virtual register, we don't really know what
663  // value it holds.
664  if (!UseR.Reg.isVirtual())
665  goto Bottomize;
666  // If there is no cell for an input register, it means top.
667  if (!Cells.has(UseR.Reg))
668  continue;
669 
670  LatticeCell SrcC;
671  bool Eval = MCE.evaluate(UseR, Cells.get(UseR.Reg), SrcC);
672  LLVM_DEBUG(dbgs() << " edge from " << printMBBReference(*PB) << ": "
673  << printReg(UseR.Reg, &MCE.TRI, UseR.SubReg) << SrcC
674  << '\n');
675  Changed |= Eval ? DefC.meet(SrcC)
676  : DefC.setBottom();
677  Cells.update(DefR.Reg, DefC);
678  if (DefC.isBottom())
679  break;
680  }
681  if (Changed)
682  visitUsesOf(DefR.Reg);
683 }
684 
685 void MachineConstPropagator::visitNonBranch(const MachineInstr &MI) {
686  LLVM_DEBUG(dbgs() << "Visiting MI(" << printMBBReference(*MI.getParent())
687  << "): " << MI);
688  CellMap Outputs;
689  bool Eval = MCE.evaluate(MI, Cells, Outputs);
690  LLVM_DEBUG({
691  if (Eval) {
692  dbgs() << " outputs:";
693  for (auto &I : Outputs)
694  dbgs() << ' ' << I.second;
695  dbgs() << '\n';
696  }
697  });
698 
699  // Update outputs. If the value was not computed, set all the
700  // def cells to bottom.
701  for (const MachineOperand &MO : MI.operands()) {
702  if (!MO.isReg() || !MO.isDef())
703  continue;
704  RegisterSubReg DefR(MO);
705  // Only track virtual registers.
706  if (!DefR.Reg.isVirtual())
707  continue;
708  bool Changed = false;
709  // If the evaluation failed, set cells for all output registers to bottom.
710  if (!Eval) {
711  const LatticeCell &T = Cells.get(DefR.Reg);
712  Changed = !T.isBottom();
713  Cells.update(DefR.Reg, Bottom);
714  } else {
715  // Find the corresponding cell in the computed outputs.
716  // If it's not there, go on to the next def.
717  if (!Outputs.has(DefR.Reg))
718  continue;
719  LatticeCell RC = Cells.get(DefR.Reg);
720  Changed = RC.meet(Outputs.get(DefR.Reg));
721  Cells.update(DefR.Reg, RC);
722  }
723  if (Changed)
724  visitUsesOf(DefR.Reg);
725  }
726 }
727 
728 // Starting at a given branch, visit remaining branches in the block.
729 // Traverse over the subsequent branches for as long as the preceding one
730 // can fall through. Add all the possible targets to the flow work queue,
731 // including the potential fall-through to the layout-successor block.
732 void MachineConstPropagator::visitBranchesFrom(const MachineInstr &BrI) {
733  const MachineBasicBlock &B = *BrI.getParent();
734  unsigned MBN = B.getNumber();
737 
739  bool EvalOk = true, FallsThru = true;
740  while (It != End) {
741  const MachineInstr &MI = *It;
742  InstrExec.insert(&MI);
743  LLVM_DEBUG(dbgs() << "Visiting " << (EvalOk ? "BR" : "br") << "("
744  << printMBBReference(B) << "): " << MI);
745  // Do not evaluate subsequent branches if the evaluation of any of the
746  // previous branches failed. Keep iterating over the branches only
747  // to mark them as executable.
748  EvalOk = EvalOk && MCE.evaluate(MI, Cells, Targets, FallsThru);
749  if (!EvalOk)
750  FallsThru = true;
751  if (!FallsThru)
752  break;
753  ++It;
754  }
755 
756  if (B.mayHaveInlineAsmBr())
757  EvalOk = false;
758 
759  if (EvalOk) {
760  // Need to add all CFG successors that lead to EH landing pads.
761  // There won't be explicit branches to these blocks, but they must
762  // be processed.
763  for (const MachineBasicBlock *SB : B.successors()) {
764  if (SB->isEHPad())
765  Targets.insert(SB);
766  }
767  if (FallsThru) {
768  const MachineFunction &MF = *B.getParent();
769  MachineFunction::const_iterator BI = B.getIterator();
770  MachineFunction::const_iterator Next = std::next(BI);
771  if (Next != MF.end())
772  Targets.insert(&*Next);
773  }
774  } else {
775  // If the evaluation of the branches failed, make "Targets" to be the
776  // set of all successors of the block from the CFG.
777  // If the evaluation succeeded for all visited branches, then if the
778  // last one set "FallsThru", then add an edge to the layout successor
779  // to the targets.
780  Targets.clear();
781  LLVM_DEBUG(dbgs() << " failed to evaluate a branch...adding all CFG "
782  "successors\n");
783  for (const MachineBasicBlock *SB : B.successors())
784  Targets.insert(SB);
785  }
786 
787  for (const MachineBasicBlock *TB : Targets) {
788  unsigned TBN = TB->getNumber();
789  LLVM_DEBUG(dbgs() << " pushing edge " << printMBBReference(B) << " -> "
790  << printMBBReference(*TB) << "\n");
791  FlowQ.push(CFGEdge(MBN, TBN));
792  }
793 }
794 
795 void MachineConstPropagator::visitUsesOf(unsigned Reg) {
796  LLVM_DEBUG(dbgs() << "Visiting uses of " << printReg(Reg, &MCE.TRI)
797  << Cells.get(Reg) << '\n');
799  // Do not process non-executable instructions. They can become exceutable
800  // later (via a flow-edge in the work queue). In such case, the instruc-
801  // tion will be visited at that time.
802  if (!InstrExec.count(&MI))
803  continue;
804  if (MI.isPHI())
805  visitPHI(MI);
806  else if (!MI.isBranch())
807  visitNonBranch(MI);
808  else
809  visitBranchesFrom(MI);
810  }
811 }
812 
813 bool MachineConstPropagator::computeBlockSuccessors(const MachineBasicBlock *MB,
815  Targets.clear();
816 
817  MachineBasicBlock::const_iterator FirstBr = MB->end();
818  for (const MachineInstr &MI : *MB) {
819  if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)
820  return false;
821  if (MI.isDebugInstr())
822  continue;
823  if (MI.isBranch()) {
824  FirstBr = MI.getIterator();
825  break;
826  }
827  }
828 
829  MachineBasicBlock::const_iterator End = MB->end();
830 
831  bool DoNext = true;
832  for (MachineBasicBlock::const_iterator I = FirstBr; I != End; ++I) {
833  const MachineInstr &MI = *I;
834  // Can there be debug instructions between branches?
835  if (MI.isDebugInstr())
836  continue;
837  if (!InstrExec.count(&MI))
838  continue;
839  bool Eval = MCE.evaluate(MI, Cells, Targets, DoNext);
840  if (!Eval)
841  return false;
842  if (!DoNext)
843  break;
844  }
845  // If the last branch could fall-through, add block's layout successor.
846  if (DoNext) {
847  MachineFunction::const_iterator BI = MB->getIterator();
848  MachineFunction::const_iterator NextI = std::next(BI);
849  if (NextI != MB->getParent()->end())
850  Targets.insert(&*NextI);
851  }
852 
853  // Add all the EH landing pads.
854  for (const MachineBasicBlock *SB : MB->successors())
855  if (SB->isEHPad())
856  Targets.insert(SB);
857 
858  return true;
859 }
860 
861 void MachineConstPropagator::removeCFGEdge(MachineBasicBlock *From,
862  MachineBasicBlock *To) {
863  // First, remove the CFG successor/predecessor information.
864  From->removeSuccessor(To);
865  // Remove all corresponding PHI operands in the To block.
866  for (MachineInstr &PN : To->phis()) {
867  // reg0 = PHI reg1, bb2, reg3, bb4, ...
868  int N = PN.getNumOperands() - 2;
869  while (N > 0) {
870  if (PN.getOperand(N + 1).getMBB() == From) {
871  PN.removeOperand(N + 1);
872  PN.removeOperand(N);
873  }
874  N -= 2;
875  }
876  }
877 }
878 
881  unsigned EntryNum = Entry->getNumber();
882 
883  // Start with a fake edge, just to process the entry node.
884  FlowQ.push(CFGEdge(EntryNum, EntryNum));
885 
886  while (!FlowQ.empty()) {
887  CFGEdge Edge = FlowQ.front();
888  FlowQ.pop();
889 
890  LLVM_DEBUG(
891  dbgs() << "Picked edge "
892  << printMBBReference(*MF.getBlockNumbered(Edge.first)) << "->"
893  << printMBBReference(*MF.getBlockNumbered(Edge.second)) << '\n');
894  if (Edge.first != EntryNum)
895  if (EdgeExec.count(Edge))
896  continue;
897  EdgeExec.insert(Edge);
898  MachineBasicBlock *SB = MF.getBlockNumbered(Edge.second);
899 
900  // Process the block in three stages:
901  // - visit all PHI nodes,
902  // - visit all non-branch instructions,
903  // - visit block branches.
904  MachineBasicBlock::const_iterator It = SB->begin(), End = SB->end();
905 
906  // Visit PHI nodes in the successor block.
907  while (It != End && It->isPHI()) {
908  InstrExec.insert(&*It);
909  visitPHI(*It);
910  ++It;
911  }
912 
913  // If the successor block just became executable, visit all instructions.
914  // To see if this is the first time we're visiting it, check the first
915  // non-debug instruction to see if it is executable.
916  while (It != End && It->isDebugInstr())
917  ++It;
918  assert(It == End || !It->isPHI());
919  // If this block has been visited, go on to the next one.
920  if (It != End && InstrExec.count(&*It))
921  continue;
922  // For now, scan all non-branch instructions. Branches require different
923  // processing.
924  while (It != End && !It->isBranch()) {
925  if (!It->isDebugInstr()) {
926  InstrExec.insert(&*It);
927  visitNonBranch(*It);
928  }
929  ++It;
930  }
931 
932  // Time to process the end of the block. This is different from
933  // processing regular (non-branch) instructions, because there can
934  // be multiple branches in a block, and they can cause the block to
935  // terminate early.
936  if (It != End) {
937  visitBranchesFrom(*It);
938  } else {
939  // If the block didn't have a branch, add all successor edges to the
940  // work queue. (There should really be only one successor in such case.)
941  unsigned SBN = SB->getNumber();
942  for (const MachineBasicBlock *SSB : SB->successors())
943  FlowQ.push(CFGEdge(SBN, SSB->getNumber()));
944  }
945  } // while (FlowQ)
946 
947  LLVM_DEBUG({
948  dbgs() << "Cells after propagation:\n";
949  Cells.print(dbgs(), MCE.TRI);
950  dbgs() << "Dead CFG edges:\n";
951  for (const MachineBasicBlock &B : MF) {
952  unsigned BN = B.getNumber();
953  for (const MachineBasicBlock *SB : B.successors()) {
954  unsigned SN = SB->getNumber();
955  if (!EdgeExec.count(CFGEdge(BN, SN)))
956  dbgs() << " " << printMBBReference(B) << " -> "
957  << printMBBReference(*SB) << '\n';
958  }
959  }
960  });
961 }
962 
964  bool Changed = false;
965  // Rewrite all instructions based on the collected cell information.
966  //
967  // Traverse the instructions in a post-order, so that rewriting an
968  // instruction can make changes "downstream" in terms of control-flow
969  // without affecting the rewriting process. (We should not change
970  // instructions that have not yet been visited by the rewriter.)
971  // The reason for this is that the rewriter can introduce new vregs,
972  // and replace uses of old vregs (which had corresponding cells
973  // computed during propagation) with these new vregs (which at this
974  // point would not have any cells, and would appear to be "top").
975  // If an attempt was made to evaluate an instruction with a fresh
976  // "top" vreg, it would cause an error (abend) in the evaluator.
977 
978  // Collect the post-order-traversal block ordering. The subsequent
979  // traversal/rewrite will update block successors, so it's safer
980  // if the visiting order it computed ahead of time.
981  std::vector<MachineBasicBlock*> POT;
982  for (MachineBasicBlock *B : post_order(&MF))
983  if (!B->empty())
984  POT.push_back(B);
985 
986  for (MachineBasicBlock *B : POT) {
987  // Walk the block backwards (which usually begin with the branches).
988  // If any branch is rewritten, we may need to update the successor
989  // information for this block. Unless the block's successors can be
990  // precisely determined (which may not be the case for indirect
991  // branches), we cannot modify any branch.
992 
993  // Compute the successor information.
995  bool HaveTargets = computeBlockSuccessors(B, Targets);
996  // Rewrite the executable instructions. Skip branches if we don't
997  // have block successor information.
998  for (MachineInstr &MI : llvm::reverse(*B)) {
999  if (InstrExec.count(&MI)) {
1000  if (MI.isBranch() && !HaveTargets)
1001  continue;
1002  Changed |= MCE.rewrite(MI, Cells);
1003  }
1004  }
1005  // The rewriting could rewrite PHI nodes to non-PHI nodes, causing
1006  // regular instructions to appear in between PHI nodes. Bring all
1007  // the PHI nodes to the beginning of the block.
1008  for (auto I = B->begin(), E = B->end(); I != E; ++I) {
1009  if (I->isPHI())
1010  continue;
1011  // I is not PHI. Find the next PHI node P.
1012  auto P = I;
1013  while (++P != E)
1014  if (P->isPHI())
1015  break;
1016  // Not found.
1017  if (P == E)
1018  break;
1019  // Splice P right before I.
1020  B->splice(I, B, P);
1021  // Reset I to point at the just spliced PHI node.
1022  --I;
1023  }
1024  // Update the block successor information: remove unnecessary successors.
1025  if (HaveTargets) {
1027  for (MachineBasicBlock *SB : B->successors()) {
1028  if (!Targets.count(SB))
1029  ToRemove.push_back(const_cast<MachineBasicBlock*>(SB));
1030  Targets.remove(SB);
1031  }
1032  for (MachineBasicBlock *MBB : ToRemove)
1033  removeCFGEdge(B, MBB);
1034  // If there are any blocks left in the computed targets, it means that
1035  // we think that the block could go somewhere, but the CFG does not.
1036  // This could legitimately happen in blocks that have non-returning
1037  // calls---we would think that the execution can continue, but the
1038  // CFG will not have a successor edge.
1039  }
1040  }
1041  // Need to do some final post-processing.
1042  // If a branch was not executable, it will not get rewritten, but should
1043  // be removed (or replaced with something equivalent to a A2_nop). We can't
1044  // erase instructions during rewriting, so this needs to be delayed until
1045  // now.
1046  for (MachineBasicBlock &B : MF) {
1048  if (MI.isBranch() && !InstrExec.count(&MI))
1049  B.erase(&MI);
1050  }
1051  return Changed;
1052 }
1053 
1054 // This is the constant propagation algorithm as described by Wegman-Zadeck.
1055 // Most of the terminology comes from there.
1057  LLVM_DEBUG(MF.print(dbgs() << "Starting MachineConstPropagator\n", nullptr));
1058 
1059  MRI = &MF.getRegInfo();
1060 
1061  Cells.clear();
1062  EdgeExec.clear();
1063  InstrExec.clear();
1064  assert(FlowQ.empty());
1065 
1066  propagate(MF);
1067  bool Changed = rewrite(MF);
1068 
1069  LLVM_DEBUG({
1070  dbgs() << "End of MachineConstPropagator (Changed=" << Changed << ")\n";
1071  if (Changed)
1072  MF.print(dbgs(), nullptr);
1073  });
1074  return Changed;
1075 }
1076 
1077 // --------------------------------------------------------------------
1078 // Machine const evaluator.
1079 
1080 bool MachineConstEvaluator::getCell(const RegisterSubReg &R, const CellMap &Inputs,
1081  LatticeCell &RC) {
1082  if (!R.Reg.isVirtual())
1083  return false;
1084  const LatticeCell &L = Inputs.get(R.Reg);
1085  if (!R.SubReg) {
1086  RC = L;
1087  return !RC.isBottom();
1088  }
1089  bool Eval = evaluate(R, L, RC);
1090  return Eval && !RC.isBottom();
1091 }
1092 
1093 bool MachineConstEvaluator::constToInt(const Constant *C,
1094  APInt &Val) const {
1095  const ConstantInt *CI = dyn_cast<ConstantInt>(C);
1096  if (!CI)
1097  return false;
1098  Val = CI->getValue();
1099  return true;
1100 }
1101 
1102 const ConstantInt *MachineConstEvaluator::intToConst(const APInt &Val) const {
1103  return ConstantInt::get(CX, Val);
1104 }
1105 
1106 bool MachineConstEvaluator::evaluateCMPrr(uint32_t Cmp, const RegisterSubReg &R1,
1107  const RegisterSubReg &R2, const CellMap &Inputs, bool &Result) {
1108  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1109  LatticeCell LS1, LS2;
1110  if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2))
1111  return false;
1112 
1113  bool IsProp1 = LS1.isProperty();
1114  bool IsProp2 = LS2.isProperty();
1115  if (IsProp1) {
1116  uint32_t Prop1 = LS1.properties();
1117  if (IsProp2)
1118  return evaluateCMPpp(Cmp, Prop1, LS2.properties(), Result);
1119  uint32_t NegCmp = Comparison::negate(Cmp);
1120  return evaluateCMPrp(NegCmp, R2, Prop1, Inputs, Result);
1121  }
1122  if (IsProp2) {
1123  uint32_t Prop2 = LS2.properties();
1124  return evaluateCMPrp(Cmp, R1, Prop2, Inputs, Result);
1125  }
1126 
1127  APInt A;
1128  bool IsTrue = true, IsFalse = true;
1129  for (unsigned i = 0; i < LS2.size(); ++i) {
1130  bool Res;
1131  bool Computed = constToInt(LS2.Values[i], A) &&
1132  evaluateCMPri(Cmp, R1, A, Inputs, Res);
1133  if (!Computed)
1134  return false;
1135  IsTrue &= Res;
1136  IsFalse &= !Res;
1137  }
1138  assert(!IsTrue || !IsFalse);
1139  // The actual logical value of the comparison is same as IsTrue.
1140  Result = IsTrue;
1141  // Return true if the result was proven to be true or proven to be false.
1142  return IsTrue || IsFalse;
1143 }
1144 
1145 bool MachineConstEvaluator::evaluateCMPri(uint32_t Cmp, const RegisterSubReg &R1,
1146  const APInt &A2, const CellMap &Inputs, bool &Result) {
1147  assert(Inputs.has(R1.Reg));
1148  LatticeCell LS;
1149  if (!getCell(R1, Inputs, LS))
1150  return false;
1151  if (LS.isProperty())
1152  return evaluateCMPpi(Cmp, LS.properties(), A2, Result);
1153 
1154  APInt A;
1155  bool IsTrue = true, IsFalse = true;
1156  for (unsigned i = 0; i < LS.size(); ++i) {
1157  bool Res;
1158  bool Computed = constToInt(LS.Values[i], A) &&
1159  evaluateCMPii(Cmp, A, A2, Res);
1160  if (!Computed)
1161  return false;
1162  IsTrue &= Res;
1163  IsFalse &= !Res;
1164  }
1165  assert(!IsTrue || !IsFalse);
1166  // The actual logical value of the comparison is same as IsTrue.
1167  Result = IsTrue;
1168  // Return true if the result was proven to be true or proven to be false.
1169  return IsTrue || IsFalse;
1170 }
1171 
1172 bool MachineConstEvaluator::evaluateCMPrp(uint32_t Cmp, const RegisterSubReg &R1,
1173  uint64_t Props2, const CellMap &Inputs, bool &Result) {
1174  assert(Inputs.has(R1.Reg));
1175  LatticeCell LS;
1176  if (!getCell(R1, Inputs, LS))
1177  return false;
1178  if (LS.isProperty())
1179  return evaluateCMPpp(Cmp, LS.properties(), Props2, Result);
1180 
1181  APInt A;
1182  uint32_t NegCmp = Comparison::negate(Cmp);
1183  bool IsTrue = true, IsFalse = true;
1184  for (unsigned i = 0; i < LS.size(); ++i) {
1185  bool Res;
1186  bool Computed = constToInt(LS.Values[i], A) &&
1187  evaluateCMPpi(NegCmp, Props2, A, Res);
1188  if (!Computed)
1189  return false;
1190  IsTrue &= Res;
1191  IsFalse &= !Res;
1192  }
1193  assert(!IsTrue || !IsFalse);
1194  Result = IsTrue;
1195  return IsTrue || IsFalse;
1196 }
1197 
1198 bool MachineConstEvaluator::evaluateCMPii(uint32_t Cmp, const APInt &A1,
1199  const APInt &A2, bool &Result) {
1200  // NE is a special kind of comparison (not composed of smaller properties).
1201  if (Cmp == Comparison::NE) {
1202  Result = !APInt::isSameValue(A1, A2);
1203  return true;
1204  }
1205  if (Cmp == Comparison::EQ) {
1206  Result = APInt::isSameValue(A1, A2);
1207  return true;
1208  }
1209  if (Cmp & Comparison::EQ) {
1210  if (APInt::isSameValue(A1, A2))
1211  return (Result = true);
1212  }
1213  assert((Cmp & (Comparison::L | Comparison::G)) && "Malformed comparison");
1214  Result = false;
1215 
1216  unsigned W1 = A1.getBitWidth();
1217  unsigned W2 = A2.getBitWidth();
1218  unsigned MaxW = (W1 >= W2) ? W1 : W2;
1219  if (Cmp & Comparison::U) {
1220  APInt Zx1 = A1.zext(MaxW);
1221  APInt Zx2 = A2.zext(MaxW);
1222  if (Cmp & Comparison::L)
1223  Result = Zx1.ult(Zx2);
1224  else if (Cmp & Comparison::G)
1225  Result = Zx2.ult(Zx1);
1226  return true;
1227  }
1228 
1229  // Signed comparison.
1230  APInt Sx1 = A1.sext(MaxW);
1231  APInt Sx2 = A2.sext(MaxW);
1232  if (Cmp & Comparison::L)
1233  Result = Sx1.slt(Sx2);
1234  else if (Cmp & Comparison::G)
1235  Result = Sx2.slt(Sx1);
1236  return true;
1237 }
1238 
1239 bool MachineConstEvaluator::evaluateCMPpi(uint32_t Cmp, uint32_t Props,
1240  const APInt &A2, bool &Result) {
1241  if (Props == ConstantProperties::Unknown)
1242  return false;
1243 
1244  // Should never see NaN here, but check for it for completeness.
1245  if (Props & ConstantProperties::NaN)
1246  return false;
1247  // Infinity could theoretically be compared to a number, but the
1248  // presence of infinity here would be very suspicious. If we don't
1249  // know for sure that the number is finite, bail out.
1250  if (!(Props & ConstantProperties::Finite))
1251  return false;
1252 
1253  // Let X be a number that has properties Props.
1254 
1255  if (Cmp & Comparison::U) {
1256  // In case of unsigned comparisons, we can only compare against 0.
1257  if (A2 == 0) {
1258  // Any x!=0 will be considered >0 in an unsigned comparison.
1259  if (Props & ConstantProperties::Zero)
1260  Result = (Cmp & Comparison::EQ);
1261  else if (Props & ConstantProperties::NonZero)
1262  Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE);
1263  else
1264  return false;
1265  return true;
1266  }
1267  // A2 is not zero. The only handled case is if X = 0.
1268  if (Props & ConstantProperties::Zero) {
1269  Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE);
1270  return true;
1271  }
1272  return false;
1273  }
1274 
1275  // Signed comparisons are different.
1276  if (Props & ConstantProperties::Zero) {
1277  if (A2 == 0)
1278  Result = (Cmp & Comparison::EQ);
1279  else
1280  Result = (Cmp == Comparison::NE) ||
1281  ((Cmp & Comparison::L) && !A2.isNegative()) ||
1282  ((Cmp & Comparison::G) && A2.isNegative());
1283  return true;
1284  }
1285  if (Props & ConstantProperties::PosOrZero) {
1286  // X >= 0 and !(A2 < 0) => cannot compare
1287  if (!A2.isNegative())
1288  return false;
1289  // X >= 0 and A2 < 0
1290  Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE);
1291  return true;
1292  }
1293  if (Props & ConstantProperties::NegOrZero) {
1294  // X <= 0 and Src1 < 0 => cannot compare
1295  if (A2 == 0 || A2.isNegative())
1296  return false;
1297  // X <= 0 and A2 > 0
1298  Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE);
1299  return true;
1300  }
1301 
1302  return false;
1303 }
1304 
1305 bool MachineConstEvaluator::evaluateCMPpp(uint32_t Cmp, uint32_t Props1,
1306  uint32_t Props2, bool &Result) {
1307  using P = ConstantProperties;
1308 
1309  if ((Props1 & P::NaN) && (Props2 & P::NaN))
1310  return false;
1311  if (!(Props1 & P::Finite) || !(Props2 & P::Finite))
1312  return false;
1313 
1314  bool Zero1 = (Props1 & P::Zero), Zero2 = (Props2 & P::Zero);
1315  bool NonZero1 = (Props1 & P::NonZero), NonZero2 = (Props2 & P::NonZero);
1316  if (Zero1 && Zero2) {
1317  Result = (Cmp & Comparison::EQ);
1318  return true;
1319  }
1320  if (Cmp == Comparison::NE) {
1321  if ((Zero1 && NonZero2) || (NonZero1 && Zero2))
1322  return (Result = true);
1323  return false;
1324  }
1325 
1326  if (Cmp & Comparison::U) {
1327  // In unsigned comparisons, we can only compare against a known zero,
1328  // or a known non-zero.
1329  if (Zero1 && NonZero2) {
1330  Result = (Cmp & Comparison::L);
1331  return true;
1332  }
1333  if (NonZero1 && Zero2) {
1334  Result = (Cmp & Comparison::G);
1335  return true;
1336  }
1337  return false;
1338  }
1339 
1340  // Signed comparison. The comparison is not NE.
1341  bool Poz1 = (Props1 & P::PosOrZero), Poz2 = (Props2 & P::PosOrZero);
1342  bool Nez1 = (Props1 & P::NegOrZero), Nez2 = (Props2 & P::NegOrZero);
1343  if (Nez1 && Poz2) {
1344  if (NonZero1 || NonZero2) {
1345  Result = (Cmp & Comparison::L);
1346  return true;
1347  }
1348  // Either (or both) could be zero. Can only say that X <= Y.
1349  if ((Cmp & Comparison::EQ) && (Cmp & Comparison::L))
1350  return (Result = true);
1351  }
1352  if (Poz1 && Nez2) {
1353  if (NonZero1 || NonZero2) {
1354  Result = (Cmp & Comparison::G);
1355  return true;
1356  }
1357  // Either (or both) could be zero. Can only say that X >= Y.
1358  if ((Cmp & Comparison::EQ) && (Cmp & Comparison::G))
1359  return (Result = true);
1360  }
1361 
1362  return false;
1363 }
1364 
1365 bool MachineConstEvaluator::evaluateCOPY(const RegisterSubReg &R1,
1366  const CellMap &Inputs, LatticeCell &Result) {
1367  return getCell(R1, Inputs, Result);
1368 }
1369 
1370 bool MachineConstEvaluator::evaluateANDrr(const RegisterSubReg &R1,
1371  const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) {
1372  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1373  const LatticeCell &L1 = Inputs.get(R2.Reg);
1374  const LatticeCell &L2 = Inputs.get(R2.Reg);
1375  // If both sources are bottom, exit. Otherwise try to evaluate ANDri
1376  // with the non-bottom argument passed as the immediate. This is to
1377  // catch cases of ANDing with 0.
1378  if (L2.isBottom()) {
1379  if (L1.isBottom())
1380  return false;
1381  return evaluateANDrr(R2, R1, Inputs, Result);
1382  }
1383  LatticeCell LS2;
1384  if (!evaluate(R2, L2, LS2))
1385  return false;
1386  if (LS2.isBottom() || LS2.isProperty())
1387  return false;
1388 
1389  APInt A;
1390  for (unsigned i = 0; i < LS2.size(); ++i) {
1391  LatticeCell RC;
1392  bool Eval = constToInt(LS2.Values[i], A) &&
1393  evaluateANDri(R1, A, Inputs, RC);
1394  if (!Eval)
1395  return false;
1396  Result.meet(RC);
1397  }
1398  return !Result.isBottom();
1399 }
1400 
1401 bool MachineConstEvaluator::evaluateANDri(const RegisterSubReg &R1,
1402  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1403  assert(Inputs.has(R1.Reg));
1404  if (A2 == -1)
1405  return getCell(R1, Inputs, Result);
1406  if (A2 == 0) {
1407  LatticeCell RC;
1408  RC.add(intToConst(A2));
1409  // Overwrite Result.
1410  Result = RC;
1411  return true;
1412  }
1413  LatticeCell LS1;
1414  if (!getCell(R1, Inputs, LS1))
1415  return false;
1416  if (LS1.isBottom() || LS1.isProperty())
1417  return false;
1418 
1419  APInt A, ResA;
1420  for (unsigned i = 0; i < LS1.size(); ++i) {
1421  bool Eval = constToInt(LS1.Values[i], A) &&
1422  evaluateANDii(A, A2, ResA);
1423  if (!Eval)
1424  return false;
1425  const Constant *C = intToConst(ResA);
1426  Result.add(C);
1427  }
1428  return !Result.isBottom();
1429 }
1430 
1431 bool MachineConstEvaluator::evaluateANDii(const APInt &A1,
1432  const APInt &A2, APInt &Result) {
1433  Result = A1 & A2;
1434  return true;
1435 }
1436 
1437 bool MachineConstEvaluator::evaluateORrr(const RegisterSubReg &R1,
1438  const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) {
1439  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1440  const LatticeCell &L1 = Inputs.get(R2.Reg);
1441  const LatticeCell &L2 = Inputs.get(R2.Reg);
1442  // If both sources are bottom, exit. Otherwise try to evaluate ORri
1443  // with the non-bottom argument passed as the immediate. This is to
1444  // catch cases of ORing with -1.
1445  if (L2.isBottom()) {
1446  if (L1.isBottom())
1447  return false;
1448  return evaluateORrr(R2, R1, Inputs, Result);
1449  }
1450  LatticeCell LS2;
1451  if (!evaluate(R2, L2, LS2))
1452  return false;
1453  if (LS2.isBottom() || LS2.isProperty())
1454  return false;
1455 
1456  APInt A;
1457  for (unsigned i = 0; i < LS2.size(); ++i) {
1458  LatticeCell RC;
1459  bool Eval = constToInt(LS2.Values[i], A) &&
1460  evaluateORri(R1, A, Inputs, RC);
1461  if (!Eval)
1462  return false;
1463  Result.meet(RC);
1464  }
1465  return !Result.isBottom();
1466 }
1467 
1468 bool MachineConstEvaluator::evaluateORri(const RegisterSubReg &R1,
1469  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1470  assert(Inputs.has(R1.Reg));
1471  if (A2 == 0)
1472  return getCell(R1, Inputs, Result);
1473  if (A2 == -1) {
1474  LatticeCell RC;
1475  RC.add(intToConst(A2));
1476  // Overwrite Result.
1477  Result = RC;
1478  return true;
1479  }
1480  LatticeCell LS1;
1481  if (!getCell(R1, Inputs, LS1))
1482  return false;
1483  if (LS1.isBottom() || LS1.isProperty())
1484  return false;
1485 
1486  APInt A, ResA;
1487  for (unsigned i = 0; i < LS1.size(); ++i) {
1488  bool Eval = constToInt(LS1.Values[i], A) &&
1489  evaluateORii(A, A2, ResA);
1490  if (!Eval)
1491  return false;
1492  const Constant *C = intToConst(ResA);
1493  Result.add(C);
1494  }
1495  return !Result.isBottom();
1496 }
1497 
1498 bool MachineConstEvaluator::evaluateORii(const APInt &A1,
1499  const APInt &A2, APInt &Result) {
1500  Result = A1 | A2;
1501  return true;
1502 }
1503 
1504 bool MachineConstEvaluator::evaluateXORrr(const RegisterSubReg &R1,
1505  const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) {
1506  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1507  LatticeCell LS1, LS2;
1508  if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2))
1509  return false;
1510  if (LS1.isProperty()) {
1511  if (LS1.properties() & ConstantProperties::Zero)
1512  return !(Result = LS2).isBottom();
1513  return false;
1514  }
1515  if (LS2.isProperty()) {
1516  if (LS2.properties() & ConstantProperties::Zero)
1517  return !(Result = LS1).isBottom();
1518  return false;
1519  }
1520 
1521  APInt A;
1522  for (unsigned i = 0; i < LS2.size(); ++i) {
1523  LatticeCell RC;
1524  bool Eval = constToInt(LS2.Values[i], A) &&
1525  evaluateXORri(R1, A, Inputs, RC);
1526  if (!Eval)
1527  return false;
1528  Result.meet(RC);
1529  }
1530  return !Result.isBottom();
1531 }
1532 
1533 bool MachineConstEvaluator::evaluateXORri(const RegisterSubReg &R1,
1534  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1535  assert(Inputs.has(R1.Reg));
1536  LatticeCell LS1;
1537  if (!getCell(R1, Inputs, LS1))
1538  return false;
1539  if (LS1.isProperty()) {
1540  if (LS1.properties() & ConstantProperties::Zero) {
1541  const Constant *C = intToConst(A2);
1542  Result.add(C);
1543  return !Result.isBottom();
1544  }
1545  return false;
1546  }
1547 
1548  APInt A, XA;
1549  for (unsigned i = 0; i < LS1.size(); ++i) {
1550  bool Eval = constToInt(LS1.Values[i], A) &&
1551  evaluateXORii(A, A2, XA);
1552  if (!Eval)
1553  return false;
1554  const Constant *C = intToConst(XA);
1555  Result.add(C);
1556  }
1557  return !Result.isBottom();
1558 }
1559 
1560 bool MachineConstEvaluator::evaluateXORii(const APInt &A1,
1561  const APInt &A2, APInt &Result) {
1562  Result = A1 ^ A2;
1563  return true;
1564 }
1565 
1566 bool MachineConstEvaluator::evaluateZEXTr(const RegisterSubReg &R1, unsigned Width,
1567  unsigned Bits, const CellMap &Inputs, LatticeCell &Result) {
1568  assert(Inputs.has(R1.Reg));
1569  LatticeCell LS1;
1570  if (!getCell(R1, Inputs, LS1))
1571  return false;
1572  if (LS1.isProperty())
1573  return false;
1574 
1575  APInt A, XA;
1576  for (unsigned i = 0; i < LS1.size(); ++i) {
1577  bool Eval = constToInt(LS1.Values[i], A) &&
1578  evaluateZEXTi(A, Width, Bits, XA);
1579  if (!Eval)
1580  return false;
1581  const Constant *C = intToConst(XA);
1582  Result.add(C);
1583  }
1584  return true;
1585 }
1586 
1587 bool MachineConstEvaluator::evaluateZEXTi(const APInt &A1, unsigned Width,
1588  unsigned Bits, APInt &Result) {
1589  unsigned BW = A1.getBitWidth();
1590  (void)BW;
1591  assert(Width >= Bits && BW >= Bits);
1593  Result = A1.zextOrTrunc(Width) & Mask;
1594  return true;
1595 }
1596 
1597 bool MachineConstEvaluator::evaluateSEXTr(const RegisterSubReg &R1, unsigned Width,
1598  unsigned Bits, const CellMap &Inputs, LatticeCell &Result) {
1599  assert(Inputs.has(R1.Reg));
1600  LatticeCell LS1;
1601  if (!getCell(R1, Inputs, LS1))
1602  return false;
1603  if (LS1.isBottom() || LS1.isProperty())
1604  return false;
1605 
1606  APInt A, XA;
1607  for (unsigned i = 0; i < LS1.size(); ++i) {
1608  bool Eval = constToInt(LS1.Values[i], A) &&
1609  evaluateSEXTi(A, Width, Bits, XA);
1610  if (!Eval)
1611  return false;
1612  const Constant *C = intToConst(XA);
1613  Result.add(C);
1614  }
1615  return true;
1616 }
1617 
1618 bool MachineConstEvaluator::evaluateSEXTi(const APInt &A1, unsigned Width,
1619  unsigned Bits, APInt &Result) {
1620  unsigned BW = A1.getBitWidth();
1621  assert(Width >= Bits && BW >= Bits);
1622  // Special case to make things faster for smaller source widths.
1623  // Sign extension of 0 bits generates 0 as a result. This is consistent
1624  // with what the HW does.
1625  if (Bits == 0) {
1626  Result = APInt(Width, 0);
1627  return true;
1628  }
1629  // In C, shifts by 64 invoke undefined behavior: handle that case in APInt.
1630  if (BW <= 64 && Bits != 0) {
1631  int64_t V = A1.getSExtValue();
1632  switch (Bits) {
1633  case 8:
1634  V = static_cast<int8_t>(V);
1635  break;
1636  case 16:
1637  V = static_cast<int16_t>(V);
1638  break;
1639  case 32:
1640  V = static_cast<int32_t>(V);
1641  break;
1642  default:
1643  // Shift left to lose all bits except lower "Bits" bits, then shift
1644  // the value back, replicating what was a sign bit after the first
1645  // shift.
1646  V = (V << (64-Bits)) >> (64-Bits);
1647  break;
1648  }
1649  // V is a 64-bit sign-extended value. Convert it to APInt of desired
1650  // width.
1651  Result = APInt(Width, V, true);
1652  return true;
1653  }
1654  // Slow case: the value doesn't fit in int64_t.
1655  if (Bits < BW)
1656  Result = A1.trunc(Bits).sext(Width);
1657  else // Bits == BW
1658  Result = A1.sext(Width);
1659  return true;
1660 }
1661 
1662 bool MachineConstEvaluator::evaluateCLBr(const RegisterSubReg &R1, bool Zeros,
1663  bool Ones, const CellMap &Inputs, LatticeCell &Result) {
1664  assert(Inputs.has(R1.Reg));
1665  LatticeCell LS1;
1666  if (!getCell(R1, Inputs, LS1))
1667  return false;
1668  if (LS1.isBottom() || LS1.isProperty())
1669  return false;
1670 
1671  APInt A, CA;
1672  for (unsigned i = 0; i < LS1.size(); ++i) {
1673  bool Eval = constToInt(LS1.Values[i], A) &&
1674  evaluateCLBi(A, Zeros, Ones, CA);
1675  if (!Eval)
1676  return false;
1677  const Constant *C = intToConst(CA);
1678  Result.add(C);
1679  }
1680  return true;
1681 }
1682 
1683 bool MachineConstEvaluator::evaluateCLBi(const APInt &A1, bool Zeros,
1684  bool Ones, APInt &Result) {
1685  unsigned BW = A1.getBitWidth();
1686  if (!Zeros && !Ones)
1687  return false;
1688  unsigned Count = 0;
1689  if (Zeros && (Count == 0))
1690  Count = A1.countLeadingZeros();
1691  if (Ones && (Count == 0))
1692  Count = A1.countLeadingOnes();
1693  Result = APInt(BW, static_cast<uint64_t>(Count), false);
1694  return true;
1695 }
1696 
1697 bool MachineConstEvaluator::evaluateCTBr(const RegisterSubReg &R1, bool Zeros,
1698  bool Ones, const CellMap &Inputs, LatticeCell &Result) {
1699  assert(Inputs.has(R1.Reg));
1700  LatticeCell LS1;
1701  if (!getCell(R1, Inputs, LS1))
1702  return false;
1703  if (LS1.isBottom() || LS1.isProperty())
1704  return false;
1705 
1706  APInt A, CA;
1707  for (unsigned i = 0; i < LS1.size(); ++i) {
1708  bool Eval = constToInt(LS1.Values[i], A) &&
1709  evaluateCTBi(A, Zeros, Ones, CA);
1710  if (!Eval)
1711  return false;
1712  const Constant *C = intToConst(CA);
1713  Result.add(C);
1714  }
1715  return true;
1716 }
1717 
1718 bool MachineConstEvaluator::evaluateCTBi(const APInt &A1, bool Zeros,
1719  bool Ones, APInt &Result) {
1720  unsigned BW = A1.getBitWidth();
1721  if (!Zeros && !Ones)
1722  return false;
1723  unsigned Count = 0;
1724  if (Zeros && (Count == 0))
1725  Count = A1.countTrailingZeros();
1726  if (Ones && (Count == 0))
1727  Count = A1.countTrailingOnes();
1728  Result = APInt(BW, static_cast<uint64_t>(Count), false);
1729  return true;
1730 }
1731 
1732 bool MachineConstEvaluator::evaluateEXTRACTr(const RegisterSubReg &R1,
1733  unsigned Width, unsigned Bits, unsigned Offset, bool Signed,
1734  const CellMap &Inputs, LatticeCell &Result) {
1735  assert(Inputs.has(R1.Reg));
1736  assert(Bits+Offset <= Width);
1737  LatticeCell LS1;
1738  if (!getCell(R1, Inputs, LS1))
1739  return false;
1740  if (LS1.isBottom())
1741  return false;
1742  if (LS1.isProperty()) {
1743  uint32_t Ps = LS1.properties();
1744  if (Ps & ConstantProperties::Zero) {
1745  const Constant *C = intToConst(APInt(Width, 0, false));
1746  Result.add(C);
1747  return true;
1748  }
1749  return false;
1750  }
1751 
1752  APInt A, CA;
1753  for (unsigned i = 0; i < LS1.size(); ++i) {
1754  bool Eval = constToInt(LS1.Values[i], A) &&
1755  evaluateEXTRACTi(A, Bits, Offset, Signed, CA);
1756  if (!Eval)
1757  return false;
1758  const Constant *C = intToConst(CA);
1759  Result.add(C);
1760  }
1761  return true;
1762 }
1763 
1764 bool MachineConstEvaluator::evaluateEXTRACTi(const APInt &A1, unsigned Bits,
1765  unsigned Offset, bool Signed, APInt &Result) {
1766  unsigned BW = A1.getBitWidth();
1767  assert(Bits+Offset <= BW);
1768  // Extracting 0 bits generates 0 as a result (as indicated by the HW people).
1769  if (Bits == 0) {
1770  Result = APInt(BW, 0);
1771  return true;
1772  }
1773  if (BW <= 64) {
1774  int64_t V = A1.getZExtValue();
1775  V <<= (64-Bits-Offset);
1776  if (Signed)
1777  V >>= (64-Bits);
1778  else
1779  V = static_cast<uint64_t>(V) >> (64-Bits);
1780  Result = APInt(BW, V, Signed);
1781  return true;
1782  }
1783  if (Signed)
1784  Result = A1.shl(BW-Bits-Offset).ashr(BW-Bits);
1785  else
1786  Result = A1.shl(BW-Bits-Offset).lshr(BW-Bits);
1787  return true;
1788 }
1789 
1790 bool MachineConstEvaluator::evaluateSplatr(const RegisterSubReg &R1,
1791  unsigned Bits, unsigned Count, const CellMap &Inputs,
1792  LatticeCell &Result) {
1793  assert(Inputs.has(R1.Reg));
1794  LatticeCell LS1;
1795  if (!getCell(R1, Inputs, LS1))
1796  return false;
1797  if (LS1.isBottom() || LS1.isProperty())
1798  return false;
1799 
1800  APInt A, SA;
1801  for (unsigned i = 0; i < LS1.size(); ++i) {
1802  bool Eval = constToInt(LS1.Values[i], A) &&
1803  evaluateSplati(A, Bits, Count, SA);
1804  if (!Eval)
1805  return false;
1806  const Constant *C = intToConst(SA);
1807  Result.add(C);
1808  }
1809  return true;
1810 }
1811 
1812 bool MachineConstEvaluator::evaluateSplati(const APInt &A1, unsigned Bits,
1813  unsigned Count, APInt &Result) {
1814  assert(Count > 0);
1815  unsigned BW = A1.getBitWidth(), SW = Count*Bits;
1816  APInt LoBits = (Bits < BW) ? A1.trunc(Bits) : A1.zext(Bits);
1817  if (Count > 1)
1818  LoBits = LoBits.zext(SW);
1819 
1820  APInt Res(SW, 0, false);
1821  for (unsigned i = 0; i < Count; ++i) {
1822  Res <<= Bits;
1823  Res |= LoBits;
1824  }
1825  Result = Res;
1826  return true;
1827 }
1828 
1829 // ----------------------------------------------------------------------
1830 // Hexagon-specific code.
1831 
1832 namespace llvm {
1833 
1836 
1837 } // end namespace llvm
1838 
1839 namespace {
1840 
1841  class HexagonConstEvaluator : public MachineConstEvaluator {
1842  public:
1843  HexagonConstEvaluator(MachineFunction &Fn);
1844 
1845  bool evaluate(const MachineInstr &MI, const CellMap &Inputs,
1846  CellMap &Outputs) override;
1847  bool evaluate(const RegisterSubReg &R, const LatticeCell &SrcC,
1848  LatticeCell &Result) override;
1849  bool evaluate(const MachineInstr &BrI, const CellMap &Inputs,
1850  SetVector<const MachineBasicBlock*> &Targets, bool &FallsThru)
1851  override;
1852  bool rewrite(MachineInstr &MI, const CellMap &Inputs) override;
1853 
1854  private:
1855  unsigned getRegBitWidth(unsigned Reg) const;
1856 
1857  static uint32_t getCmp(unsigned Opc);
1858  static APInt getCmpImm(unsigned Opc, unsigned OpX,
1859  const MachineOperand &MO);
1860  void replaceWithNop(MachineInstr &MI);
1861 
1862  bool evaluateHexRSEQ32(RegisterSubReg RL, RegisterSubReg RH, const CellMap &Inputs,
1863  LatticeCell &Result);
1864  bool evaluateHexCompare(const MachineInstr &MI, const CellMap &Inputs,
1865  CellMap &Outputs);
1866  // This is suitable to be called for compare-and-jump instructions.
1867  bool evaluateHexCompare2(uint32_t Cmp, const MachineOperand &Src1,
1868  const MachineOperand &Src2, const CellMap &Inputs, bool &Result);
1869  bool evaluateHexLogical(const MachineInstr &MI, const CellMap &Inputs,
1870  CellMap &Outputs);
1871  bool evaluateHexCondMove(const MachineInstr &MI, const CellMap &Inputs,
1872  CellMap &Outputs);
1873  bool evaluateHexExt(const MachineInstr &MI, const CellMap &Inputs,
1874  CellMap &Outputs);
1875  bool evaluateHexVector1(const MachineInstr &MI, const CellMap &Inputs,
1876  CellMap &Outputs);
1877  bool evaluateHexVector2(const MachineInstr &MI, const CellMap &Inputs,
1878  CellMap &Outputs);
1879 
1880  void replaceAllRegUsesWith(Register FromReg, Register ToReg);
1881  bool rewriteHexBranch(MachineInstr &BrI, const CellMap &Inputs);
1882  bool rewriteHexConstDefs(MachineInstr &MI, const CellMap &Inputs,
1883  bool &AllDefs);
1884  bool rewriteHexConstUses(MachineInstr &MI, const CellMap &Inputs);
1885 
1887  const HexagonInstrInfo &HII;
1888  const HexagonRegisterInfo &HRI;
1889  };
1890 
1891  class HexagonConstPropagation : public MachineFunctionPass {
1892  public:
1893  static char ID;
1894 
1895  HexagonConstPropagation() : MachineFunctionPass(ID) {}
1896 
1897  StringRef getPassName() const override {
1898  return "Hexagon Constant Propagation";
1899  }
1900 
1901  bool runOnMachineFunction(MachineFunction &MF) override {
1902  const Function &F = MF.getFunction();
1903  if (skipFunction(F))
1904  return false;
1905 
1906  HexagonConstEvaluator HCE(MF);
1907  return MachineConstPropagator(HCE).run(MF);
1908  }
1909  };
1910 
1911 } // end anonymous namespace
1912 
1914 
1915 INITIALIZE_PASS(HexagonConstPropagation, "hexagon-constp",
1916  "Hexagon Constant Propagation", false, false)
1917 
1918 HexagonConstEvaluator::HexagonConstEvaluator(MachineFunction &Fn)
1919  : MachineConstEvaluator(Fn),
1920  HII(*Fn.getSubtarget<HexagonSubtarget>().getInstrInfo()),
1921  HRI(*Fn.getSubtarget<HexagonSubtarget>().getRegisterInfo()) {
1922  MRI = &Fn.getRegInfo();
1923 }
1924 
1925 bool HexagonConstEvaluator::evaluate(const MachineInstr &MI,
1926  const CellMap &Inputs, CellMap &Outputs) {
1927  if (MI.isCall())
1928  return false;
1929  if (MI.getNumOperands() == 0 || !MI.getOperand(0).isReg())
1930  return false;
1931  const MachineOperand &MD = MI.getOperand(0);
1932  if (!MD.isDef())
1933  return false;
1934 
1935  unsigned Opc = MI.getOpcode();
1936  RegisterSubReg DefR(MD);
1937  assert(!DefR.SubReg);
1938  if (!DefR.Reg.isVirtual())
1939  return false;
1940 
1941  if (MI.isCopy()) {
1942  LatticeCell RC;
1943  RegisterSubReg SrcR(MI.getOperand(1));
1944  bool Eval = evaluateCOPY(SrcR, Inputs, RC);
1945  if (!Eval)
1946  return false;
1947  Outputs.update(DefR.Reg, RC);
1948  return true;
1949  }
1950  if (MI.isRegSequence()) {
1951  unsigned Sub1 = MI.getOperand(2).getImm();
1952  unsigned Sub2 = MI.getOperand(4).getImm();
1953  const TargetRegisterClass &DefRC = *MRI->getRegClass(DefR.Reg);
1954  unsigned SubLo = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_lo);
1955  unsigned SubHi = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_hi);
1956  if (Sub1 != SubLo && Sub1 != SubHi)
1957  return false;
1958  if (Sub2 != SubLo && Sub2 != SubHi)
1959  return false;
1960  assert(Sub1 != Sub2);
1961  bool LoIs1 = (Sub1 == SubLo);
1962  const MachineOperand &OpLo = LoIs1 ? MI.getOperand(1) : MI.getOperand(3);
1963  const MachineOperand &OpHi = LoIs1 ? MI.getOperand(3) : MI.getOperand(1);
1964  LatticeCell RC;
1965  RegisterSubReg SrcRL(OpLo), SrcRH(OpHi);
1966  bool Eval = evaluateHexRSEQ32(SrcRL, SrcRH, Inputs, RC);
1967  if (!Eval)
1968  return false;
1969  Outputs.update(DefR.Reg, RC);
1970  return true;
1971  }
1972  if (MI.isCompare()) {
1973  bool Eval = evaluateHexCompare(MI, Inputs, Outputs);
1974  return Eval;
1975  }
1976 
1977  switch (Opc) {
1978  default:
1979  return false;
1980  case Hexagon::A2_tfrsi:
1981  case Hexagon::A2_tfrpi:
1982  case Hexagon::CONST32:
1983  case Hexagon::CONST64:
1984  {
1985  const MachineOperand &VO = MI.getOperand(1);
1986  // The operand of CONST32 can be a blockaddress, e.g.
1987  // %0 = CONST32 <blockaddress(@eat, %l)>
1988  // Do this check for all instructions for safety.
1989  if (!VO.isImm())
1990  return false;
1991  int64_t V = MI.getOperand(1).getImm();
1992  unsigned W = getRegBitWidth(DefR.Reg);
1993  if (W != 32 && W != 64)
1994  return false;
1995  IntegerType *Ty = (W == 32) ? Type::getInt32Ty(CX)
1996  : Type::getInt64Ty(CX);
1997  const ConstantInt *CI = ConstantInt::get(Ty, V, true);
1998  LatticeCell RC = Outputs.get(DefR.Reg);
1999  RC.add(CI);
2000  Outputs.update(DefR.Reg, RC);
2001  break;
2002  }
2003 
2004  case Hexagon::PS_true:
2005  case Hexagon::PS_false:
2006  {
2007  LatticeCell RC = Outputs.get(DefR.Reg);
2008  bool NonZero = (Opc == Hexagon::PS_true);
2009  uint32_t P = NonZero ? ConstantProperties::NonZero
2010  : ConstantProperties::Zero;
2011  RC.add(P);
2012  Outputs.update(DefR.Reg, RC);
2013  break;
2014  }
2015 
2016  case Hexagon::A2_and:
2017  case Hexagon::A2_andir:
2018  case Hexagon::A2_andp:
2019  case Hexagon::A2_or:
2020  case Hexagon::A2_orir:
2021  case Hexagon::A2_orp:
2022  case Hexagon::A2_xor:
2023  case Hexagon::A2_xorp:
2024  {
2025  bool Eval = evaluateHexLogical(MI, Inputs, Outputs);
2026  if (!Eval)
2027  return false;
2028  break;
2029  }
2030 
2031  case Hexagon::A2_combineii: // combine(#s8Ext, #s8)
2032  case Hexagon::A4_combineii: // combine(#s8, #u6Ext)
2033  {
2034  if (!MI.getOperand(1).isImm() || !MI.getOperand(2).isImm())
2035  return false;
2036  uint64_t Hi = MI.getOperand(1).getImm();
2037  uint64_t Lo = MI.getOperand(2).getImm();
2038  uint64_t Res = (Hi << 32) | (Lo & 0xFFFFFFFF);
2039  IntegerType *Ty = Type::getInt64Ty(CX);
2040  const ConstantInt *CI = ConstantInt::get(Ty, Res, false);
2041  LatticeCell RC = Outputs.get(DefR.Reg);
2042  RC.add(CI);
2043  Outputs.update(DefR.Reg, RC);
2044  break;
2045  }
2046 
2047  case Hexagon::S2_setbit_i:
2048  {
2049  int64_t B = MI.getOperand(2).getImm();
2050  assert(B >=0 && B < 32);
2051  APInt A(32, (1ull << B), false);
2052  RegisterSubReg R(MI.getOperand(1));
2053  LatticeCell RC = Outputs.get(DefR.Reg);
2054  bool Eval = evaluateORri(R, A, Inputs, RC);
2055  if (!Eval)
2056  return false;
2057  Outputs.update(DefR.Reg, RC);
2058  break;
2059  }
2060 
2061  case Hexagon::C2_mux:
2062  case Hexagon::C2_muxir:
2063  case Hexagon::C2_muxri:
2064  case Hexagon::C2_muxii:
2065  {
2066  bool Eval = evaluateHexCondMove(MI, Inputs, Outputs);
2067  if (!Eval)
2068  return false;
2069  break;
2070  }
2071 
2072  case Hexagon::A2_sxtb:
2073  case Hexagon::A2_sxth:
2074  case Hexagon::A2_sxtw:
2075  case Hexagon::A2_zxtb:
2076  case Hexagon::A2_zxth:
2077  {
2078  bool Eval = evaluateHexExt(MI, Inputs, Outputs);
2079  if (!Eval)
2080  return false;
2081  break;
2082  }
2083 
2084  case Hexagon::S2_ct0:
2085  case Hexagon::S2_ct0p:
2086  case Hexagon::S2_ct1:
2087  case Hexagon::S2_ct1p:
2088  {
2089  using namespace Hexagon;
2090 
2091  bool Ones = (Opc == S2_ct1) || (Opc == S2_ct1p);
2092  RegisterSubReg R1(MI.getOperand(1));
2093  assert(Inputs.has(R1.Reg));
2094  LatticeCell T;
2095  bool Eval = evaluateCTBr(R1, !Ones, Ones, Inputs, T);
2096  if (!Eval)
2097  return false;
2098  // All of these instructions return a 32-bit value. The evaluate
2099  // will generate the same type as the operand, so truncate the
2100  // result if necessary.
2101  APInt C;
2102  LatticeCell RC = Outputs.get(DefR.Reg);
2103  for (unsigned i = 0; i < T.size(); ++i) {
2104  const Constant *CI = T.Values[i];
2105  if (constToInt(CI, C) && C.getBitWidth() > 32)
2106  CI = intToConst(C.trunc(32));
2107  RC.add(CI);
2108  }
2109  Outputs.update(DefR.Reg, RC);
2110  break;
2111  }
2112 
2113  case Hexagon::S2_cl0:
2114  case Hexagon::S2_cl0p:
2115  case Hexagon::S2_cl1:
2116  case Hexagon::S2_cl1p:
2117  case Hexagon::S2_clb:
2118  case Hexagon::S2_clbp:
2119  {
2120  using namespace Hexagon;
2121 
2122  bool OnlyZeros = (Opc == S2_cl0) || (Opc == S2_cl0p);
2123  bool OnlyOnes = (Opc == S2_cl1) || (Opc == S2_cl1p);
2124  RegisterSubReg R1(MI.getOperand(1));
2125  assert(Inputs.has(R1.Reg));
2126  LatticeCell T;
2127  bool Eval = evaluateCLBr(R1, !OnlyOnes, !OnlyZeros, Inputs, T);
2128  if (!Eval)
2129  return false;
2130  // All of these instructions return a 32-bit value. The evaluate
2131  // will generate the same type as the operand, so truncate the
2132  // result if necessary.
2133  APInt C;
2134  LatticeCell RC = Outputs.get(DefR.Reg);
2135  for (unsigned i = 0; i < T.size(); ++i) {
2136  const Constant *CI = T.Values[i];
2137  if (constToInt(CI, C) && C.getBitWidth() > 32)
2138  CI = intToConst(C.trunc(32));
2139  RC.add(CI);
2140  }
2141  Outputs.update(DefR.Reg, RC);
2142  break;
2143  }
2144 
2145  case Hexagon::S4_extract:
2146  case Hexagon::S4_extractp:
2147  case Hexagon::S2_extractu:
2148  case Hexagon::S2_extractup:
2149  {
2150  bool Signed = (Opc == Hexagon::S4_extract) ||
2151  (Opc == Hexagon::S4_extractp);
2152  RegisterSubReg R1(MI.getOperand(1));
2153  unsigned BW = getRegBitWidth(R1.Reg);
2154  unsigned Bits = MI.getOperand(2).getImm();
2155  unsigned Offset = MI.getOperand(3).getImm();
2156  LatticeCell RC = Outputs.get(DefR.Reg);
2157  if (Offset >= BW) {
2158  APInt Zero(BW, 0, false);
2159  RC.add(intToConst(Zero));
2160  break;
2161  }
2162  if (Offset+Bits > BW) {
2163  // If the requested bitfield extends beyond the most significant bit,
2164  // the extra bits are treated as 0s. To emulate this behavior, reduce
2165  // the number of requested bits, and make the extract unsigned.
2166  Bits = BW-Offset;
2167  Signed = false;
2168  }
2169  bool Eval = evaluateEXTRACTr(R1, BW, Bits, Offset, Signed, Inputs, RC);
2170  if (!Eval)
2171  return false;
2172  Outputs.update(DefR.Reg, RC);
2173  break;
2174  }
2175 
2176  case Hexagon::S2_vsplatrb:
2177  case Hexagon::S2_vsplatrh:
2178  // vabsh, vabsh:sat
2179  // vabsw, vabsw:sat
2180  // vconj:sat
2181  // vrndwh, vrndwh:sat
2182  // vsathb, vsathub, vsatwuh
2183  // vsxtbh, vsxthw
2184  // vtrunehb, vtrunohb
2185  // vzxtbh, vzxthw
2186  {
2187  bool Eval = evaluateHexVector1(MI, Inputs, Outputs);
2188  if (!Eval)
2189  return false;
2190  break;
2191  }
2192 
2193  // TODO:
2194  // A2_vaddh
2195  // A2_vaddhs
2196  // A2_vaddw
2197  // A2_vaddws
2198  }
2199 
2200  return true;
2201 }
2202 
2203 bool HexagonConstEvaluator::evaluate(const RegisterSubReg &R,
2204  const LatticeCell &Input, LatticeCell &Result) {
2205  if (!R.SubReg) {
2206  Result = Input;
2207  return true;
2208  }
2209  const TargetRegisterClass *RC = MRI->getRegClass(R.Reg);
2210  if (RC != &Hexagon::DoubleRegsRegClass)
2211  return false;
2212  if (R.SubReg != Hexagon::isub_lo && R.SubReg != Hexagon::isub_hi)
2213  return false;
2214 
2215  assert(!Input.isTop());
2216  if (Input.isBottom())
2217  return false;
2218 
2219  using P = ConstantProperties;
2220 
2221  if (Input.isProperty()) {
2222  uint32_t Ps = Input.properties();
2223  if (Ps & (P::Zero|P::NaN)) {
2224  uint32_t Ns = (Ps & (P::Zero|P::NaN|P::SignProperties));
2225  Result.add(Ns);
2226  return true;
2227  }
2228  if (R.SubReg == Hexagon::isub_hi) {
2229  uint32_t Ns = (Ps & P::SignProperties);
2230  Result.add(Ns);
2231  return true;
2232  }
2233  return false;
2234  }
2235 
2236  // The Input cell contains some known values. Pick the word corresponding
2237  // to the subregister.
2238  APInt A;
2239  for (unsigned i = 0; i < Input.size(); ++i) {
2240  const Constant *C = Input.Values[i];
2241  if (!constToInt(C, A))
2242  return false;
2243  if (!A.isIntN(64))
2244  return false;
2245  uint64_t U = A.getZExtValue();
2246  if (R.SubReg == Hexagon::isub_hi)
2247  U >>= 32;
2248  U &= 0xFFFFFFFFULL;
2249  uint32_t U32 = Lo_32(U);
2250  int32_t V32;
2251  memcpy(&V32, &U32, sizeof V32);
2252  IntegerType *Ty = Type::getInt32Ty(CX);
2253  const ConstantInt *C32 = ConstantInt::get(Ty, static_cast<int64_t>(V32));
2254  Result.add(C32);
2255  }
2256  return true;
2257 }
2258 
2259 bool HexagonConstEvaluator::evaluate(const MachineInstr &BrI,
2260  const CellMap &Inputs, SetVector<const MachineBasicBlock*> &Targets,
2261  bool &FallsThru) {
2262  // We need to evaluate one branch at a time. TII::analyzeBranch checks
2263  // all the branches in a basic block at once, so we cannot use it.
2264  unsigned Opc = BrI.getOpcode();
2265  bool SimpleBranch = false;
2266  bool Negated = false;
2267  switch (Opc) {
2268  case Hexagon::J2_jumpf:
2269  case Hexagon::J2_jumpfnew:
2270  case Hexagon::J2_jumpfnewpt:
2271  Negated = true;
2272  [[fallthrough]];
2273  case Hexagon::J2_jumpt:
2274  case Hexagon::J2_jumptnew:
2275  case Hexagon::J2_jumptnewpt:
2276  // Simple branch: if([!]Pn) jump ...
2277  // i.e. Op0 = predicate, Op1 = branch target.
2278  SimpleBranch = true;
2279  break;
2280  case Hexagon::J2_jump:
2281  Targets.insert(BrI.getOperand(0).getMBB());
2282  FallsThru = false;
2283  return true;
2284  default:
2285 Undetermined:
2286  // If the branch is of unknown type, assume that all successors are
2287  // executable.
2288  FallsThru = !BrI.isUnconditionalBranch();
2289  return false;
2290  }
2291 
2292  if (SimpleBranch) {
2293  const MachineOperand &MD = BrI.getOperand(0);
2294  RegisterSubReg PR(MD);
2295  // If the condition operand has a subregister, this is not something
2296  // we currently recognize.
2297  if (PR.SubReg)
2298  goto Undetermined;
2299  assert(Inputs.has(PR.Reg));
2300  const LatticeCell &PredC = Inputs.get(PR.Reg);
2301  if (PredC.isBottom())
2302  goto Undetermined;
2303 
2304  uint32_t Props = PredC.properties();
2305  bool CTrue = false, CFalse = false;
2306  if (Props & ConstantProperties::Zero)
2307  CFalse = true;
2308  else if (Props & ConstantProperties::NonZero)
2309  CTrue = true;
2310  // If the condition is not known to be either, bail out.
2311  if (!CTrue && !CFalse)
2312  goto Undetermined;
2313 
2314  const MachineBasicBlock *BranchTarget = BrI.getOperand(1).getMBB();
2315 
2316  FallsThru = false;
2317  if ((!Negated && CTrue) || (Negated && CFalse))
2318  Targets.insert(BranchTarget);
2319  else if ((!Negated && CFalse) || (Negated && CTrue))
2320  FallsThru = true;
2321  else
2322  goto Undetermined;
2323  }
2324 
2325  return true;
2326 }
2327 
2328 bool HexagonConstEvaluator::rewrite(MachineInstr &MI, const CellMap &Inputs) {
2329  if (MI.isBranch())
2330  return rewriteHexBranch(MI, Inputs);
2331 
2332  unsigned Opc = MI.getOpcode();
2333  switch (Opc) {
2334  default:
2335  break;
2336  case Hexagon::A2_tfrsi:
2337  case Hexagon::A2_tfrpi:
2338  case Hexagon::CONST32:
2339  case Hexagon::CONST64:
2340  case Hexagon::PS_true:
2341  case Hexagon::PS_false:
2342  return false;
2343  }
2344 
2345  unsigned NumOp = MI.getNumOperands();
2346  if (NumOp == 0)
2347  return false;
2348 
2349  bool AllDefs, Changed;
2350  Changed = rewriteHexConstDefs(MI, Inputs, AllDefs);
2351  // If not all defs have been rewritten (i.e. the instruction defines
2352  // a register that is not compile-time constant), then try to rewrite
2353  // register operands that are known to be constant with immediates.
2354  if (!AllDefs)
2355  Changed |= rewriteHexConstUses(MI, Inputs);
2356 
2357  return Changed;
2358 }
2359 
2360 unsigned HexagonConstEvaluator::getRegBitWidth(unsigned Reg) const {
2361  const TargetRegisterClass *RC = MRI->getRegClass(Reg);
2362  if (Hexagon::IntRegsRegClass.hasSubClassEq(RC))
2363  return 32;
2364  if (Hexagon::DoubleRegsRegClass.hasSubClassEq(RC))
2365  return 64;
2366  if (Hexagon::PredRegsRegClass.hasSubClassEq(RC))
2367  return 8;
2368  llvm_unreachable("Invalid register");
2369  return 0;
2370 }
2371 
2373  switch (Opc) {
2374  case Hexagon::C2_cmpeq:
2375  case Hexagon::C2_cmpeqp:
2376  case Hexagon::A4_cmpbeq:
2377  case Hexagon::A4_cmpheq:
2378  case Hexagon::A4_cmpbeqi:
2379  case Hexagon::A4_cmpheqi:
2380  case Hexagon::C2_cmpeqi:
2381  case Hexagon::J4_cmpeqn1_t_jumpnv_nt:
2382  case Hexagon::J4_cmpeqn1_t_jumpnv_t:
2383  case Hexagon::J4_cmpeqi_t_jumpnv_nt:
2384  case Hexagon::J4_cmpeqi_t_jumpnv_t:
2385  case Hexagon::J4_cmpeq_t_jumpnv_nt:
2386  case Hexagon::J4_cmpeq_t_jumpnv_t:
2387  return Comparison::EQ;
2388 
2389  case Hexagon::C4_cmpneq:
2390  case Hexagon::C4_cmpneqi:
2391  case Hexagon::J4_cmpeqn1_f_jumpnv_nt:
2392  case Hexagon::J4_cmpeqn1_f_jumpnv_t:
2393  case Hexagon::J4_cmpeqi_f_jumpnv_nt:
2394  case Hexagon::J4_cmpeqi_f_jumpnv_t:
2395  case Hexagon::J4_cmpeq_f_jumpnv_nt:
2396  case Hexagon::J4_cmpeq_f_jumpnv_t:
2397  return Comparison::NE;
2398 
2399  case Hexagon::C2_cmpgt:
2400  case Hexagon::C2_cmpgtp:
2401  case Hexagon::A4_cmpbgt:
2402  case Hexagon::A4_cmphgt:
2403  case Hexagon::A4_cmpbgti:
2404  case Hexagon::A4_cmphgti:
2405  case Hexagon::C2_cmpgti:
2406  case Hexagon::J4_cmpgtn1_t_jumpnv_nt:
2407  case Hexagon::J4_cmpgtn1_t_jumpnv_t:
2408  case Hexagon::J4_cmpgti_t_jumpnv_nt:
2409  case Hexagon::J4_cmpgti_t_jumpnv_t:
2410  case Hexagon::J4_cmpgt_t_jumpnv_nt:
2411  case Hexagon::J4_cmpgt_t_jumpnv_t:
2412  return Comparison::GTs;
2413 
2414  case Hexagon::C4_cmplte:
2415  case Hexagon::C4_cmpltei:
2416  case Hexagon::J4_cmpgtn1_f_jumpnv_nt:
2417  case Hexagon::J4_cmpgtn1_f_jumpnv_t:
2418  case Hexagon::J4_cmpgti_f_jumpnv_nt:
2419  case Hexagon::J4_cmpgti_f_jumpnv_t:
2420  case Hexagon::J4_cmpgt_f_jumpnv_nt:
2421  case Hexagon::J4_cmpgt_f_jumpnv_t:
2422  return Comparison::LEs;
2423 
2424  case Hexagon::C2_cmpgtu:
2425  case Hexagon::C2_cmpgtup:
2426  case Hexagon::A4_cmpbgtu:
2427  case Hexagon::A4_cmpbgtui:
2428  case Hexagon::A4_cmphgtu:
2429  case Hexagon::A4_cmphgtui:
2430  case Hexagon::C2_cmpgtui:
2431  case Hexagon::J4_cmpgtui_t_jumpnv_nt:
2432  case Hexagon::J4_cmpgtui_t_jumpnv_t:
2433  case Hexagon::J4_cmpgtu_t_jumpnv_nt:
2434  case Hexagon::J4_cmpgtu_t_jumpnv_t:
2435  return Comparison::GTu;
2436 
2437  case Hexagon::J4_cmpltu_f_jumpnv_nt:
2438  case Hexagon::J4_cmpltu_f_jumpnv_t:
2439  return Comparison::GEu;
2440 
2441  case Hexagon::J4_cmpltu_t_jumpnv_nt:
2442  case Hexagon::J4_cmpltu_t_jumpnv_t:
2443  return Comparison::LTu;
2444 
2445  case Hexagon::J4_cmplt_f_jumpnv_nt:
2446  case Hexagon::J4_cmplt_f_jumpnv_t:
2447  return Comparison::GEs;
2448 
2449  case Hexagon::C4_cmplteu:
2450  case Hexagon::C4_cmplteui:
2451  case Hexagon::J4_cmpgtui_f_jumpnv_nt:
2452  case Hexagon::J4_cmpgtui_f_jumpnv_t:
2453  case Hexagon::J4_cmpgtu_f_jumpnv_nt:
2454  case Hexagon::J4_cmpgtu_f_jumpnv_t:
2455  return Comparison::LEu;
2456 
2457  case Hexagon::J4_cmplt_t_jumpnv_nt:
2458  case Hexagon::J4_cmplt_t_jumpnv_t:
2459  return Comparison::LTs;
2460 
2461  default:
2462  break;
2463  }
2464  return Comparison::Unk;
2465 }
2466 
2467 APInt HexagonConstEvaluator::getCmpImm(unsigned Opc, unsigned OpX,
2468  const MachineOperand &MO) {
2469  bool Signed = false;
2470  switch (Opc) {
2471  case Hexagon::A4_cmpbgtui: // u7
2472  case Hexagon::A4_cmphgtui: // u7
2473  break;
2474  case Hexagon::A4_cmpheqi: // s8
2475  case Hexagon::C4_cmpneqi: // s8
2476  Signed = true;
2477  break;
2478  case Hexagon::A4_cmpbeqi: // u8
2479  break;
2480  case Hexagon::C2_cmpgtui: // u9
2481  case Hexagon::C4_cmplteui: // u9
2482  break;
2483  case Hexagon::C2_cmpeqi: // s10
2484  case Hexagon::C2_cmpgti: // s10
2485  case Hexagon::C4_cmpltei: // s10
2486  Signed = true;
2487  break;
2488  case Hexagon::J4_cmpeqi_f_jumpnv_nt: // u5
2489  case Hexagon::J4_cmpeqi_f_jumpnv_t: // u5
2490  case Hexagon::J4_cmpeqi_t_jumpnv_nt: // u5
2491  case Hexagon::J4_cmpeqi_t_jumpnv_t: // u5
2492  case Hexagon::J4_cmpgti_f_jumpnv_nt: // u5
2493  case Hexagon::J4_cmpgti_f_jumpnv_t: // u5
2494  case Hexagon::J4_cmpgti_t_jumpnv_nt: // u5
2495  case Hexagon::J4_cmpgti_t_jumpnv_t: // u5
2496  case Hexagon::J4_cmpgtui_f_jumpnv_nt: // u5
2497  case Hexagon::J4_cmpgtui_f_jumpnv_t: // u5
2498  case Hexagon::J4_cmpgtui_t_jumpnv_nt: // u5
2499  case Hexagon::J4_cmpgtui_t_jumpnv_t: // u5
2500  break;
2501  default:
2502  llvm_unreachable("Unhandled instruction");
2503  break;
2504  }
2505 
2506  uint64_t Val = MO.getImm();
2507  return APInt(32, Val, Signed);
2508 }
2509 
2510 void HexagonConstEvaluator::replaceWithNop(MachineInstr &MI) {
2511  MI.setDesc(HII.get(Hexagon::A2_nop));
2512  while (MI.getNumOperands() > 0)
2513  MI.removeOperand(0);
2514 }
2515 
2516 bool HexagonConstEvaluator::evaluateHexRSEQ32(RegisterSubReg RL, RegisterSubReg RH,
2517  const CellMap &Inputs, LatticeCell &Result) {
2518  assert(Inputs.has(RL.Reg) && Inputs.has(RH.Reg));
2519  LatticeCell LSL, LSH;
2520  if (!getCell(RL, Inputs, LSL) || !getCell(RH, Inputs, LSH))
2521  return false;
2522  if (LSL.isProperty() || LSH.isProperty())
2523  return false;
2524 
2525  unsigned LN = LSL.size(), HN = LSH.size();
2526  SmallVector<APInt,4> LoVs(LN), HiVs(HN);
2527  for (unsigned i = 0; i < LN; ++i) {
2528  bool Eval = constToInt(LSL.Values[i], LoVs[i]);
2529  if (!Eval)
2530  return false;
2531  assert(LoVs[i].getBitWidth() == 32);
2532  }
2533  for (unsigned i = 0; i < HN; ++i) {
2534  bool Eval = constToInt(LSH.Values[i], HiVs[i]);
2535  if (!Eval)
2536  return false;
2537  assert(HiVs[i].getBitWidth() == 32);
2538  }
2539 
2540  for (unsigned i = 0; i < HiVs.size(); ++i) {
2541  APInt HV = HiVs[i].zext(64) << 32;
2542  for (unsigned j = 0; j < LoVs.size(); ++j) {
2543  APInt LV = LoVs[j].zext(64);
2544  const Constant *C = intToConst(HV | LV);
2545  Result.add(C);
2546  if (Result.isBottom())
2547  return false;
2548  }
2549  }
2550  return !Result.isBottom();
2551 }
2552 
2553 bool HexagonConstEvaluator::evaluateHexCompare(const MachineInstr &MI,
2554  const CellMap &Inputs, CellMap &Outputs) {
2555  unsigned Opc = MI.getOpcode();
2556  bool Classic = false;
2557  switch (Opc) {
2558  case Hexagon::C2_cmpeq:
2559  case Hexagon::C2_cmpeqp:
2560  case Hexagon::C2_cmpgt:
2561  case Hexagon::C2_cmpgtp:
2562  case Hexagon::C2_cmpgtu:
2563  case Hexagon::C2_cmpgtup:
2564  case Hexagon::C2_cmpeqi:
2565  case Hexagon::C2_cmpgti:
2566  case Hexagon::C2_cmpgtui:
2567  // Classic compare: Dst0 = CMP Src1, Src2
2568  Classic = true;
2569  break;
2570  default:
2571  // Not handling other compare instructions now.
2572  return false;
2573  }
2574 
2575  if (Classic) {
2576  const MachineOperand &Src1 = MI.getOperand(1);
2577  const MachineOperand &Src2 = MI.getOperand(2);
2578 
2579  bool Result;
2580  unsigned Opc = MI.getOpcode();
2581  bool Computed = evaluateHexCompare2(Opc, Src1, Src2, Inputs, Result);
2582  if (Computed) {
2583  // Only create a zero/non-zero cell. At this time there isn't really
2584  // much need for specific values.
2585  RegisterSubReg DefR(MI.getOperand(0));
2586  LatticeCell L = Outputs.get(DefR.Reg);
2587  uint32_t P = Result ? ConstantProperties::NonZero
2588  : ConstantProperties::Zero;
2589  L.add(P);
2590  Outputs.update(DefR.Reg, L);
2591  return true;
2592  }
2593  }
2594 
2595  return false;
2596 }
2597 
2598 bool HexagonConstEvaluator::evaluateHexCompare2(unsigned Opc,
2599  const MachineOperand &Src1, const MachineOperand &Src2,
2600  const CellMap &Inputs, bool &Result) {
2601  uint32_t Cmp = getCmp(Opc);
2602  bool Reg1 = Src1.isReg(), Reg2 = Src2.isReg();
2603  bool Imm1 = Src1.isImm(), Imm2 = Src2.isImm();
2604  if (Reg1) {
2605  RegisterSubReg R1(Src1);
2606  if (Reg2) {
2607  RegisterSubReg R2(Src2);
2608  return evaluateCMPrr(Cmp, R1, R2, Inputs, Result);
2609  } else if (Imm2) {
2610  APInt A2 = getCmpImm(Opc, 2, Src2);
2611  return evaluateCMPri(Cmp, R1, A2, Inputs, Result);
2612  }
2613  } else if (Imm1) {
2614  APInt A1 = getCmpImm(Opc, 1, Src1);
2615  if (Reg2) {
2616  RegisterSubReg R2(Src2);
2617  uint32_t NegCmp = Comparison::negate(Cmp);
2618  return evaluateCMPri(NegCmp, R2, A1, Inputs, Result);
2619  } else if (Imm2) {
2620  APInt A2 = getCmpImm(Opc, 2, Src2);
2621  return evaluateCMPii(Cmp, A1, A2, Result);
2622  }
2623  }
2624  // Unknown kind of comparison.
2625  return false;
2626 }
2627 
2628 bool HexagonConstEvaluator::evaluateHexLogical(const MachineInstr &MI,
2629  const CellMap &Inputs, CellMap &Outputs) {
2630  unsigned Opc = MI.getOpcode();
2631  if (MI.getNumOperands() != 3)
2632  return false;
2633  const MachineOperand &Src1 = MI.getOperand(1);
2634  const MachineOperand &Src2 = MI.getOperand(2);
2635  RegisterSubReg R1(Src1);
2636  bool Eval = false;
2637  LatticeCell RC;
2638  switch (Opc) {
2639  default:
2640  return false;
2641  case Hexagon::A2_and:
2642  case Hexagon::A2_andp:
2643  Eval = evaluateANDrr(R1, RegisterSubReg(Src2), Inputs, RC);
2644  break;
2645  case Hexagon::A2_andir: {
2646  if (!Src2.isImm())
2647  return false;
2648  APInt A(32, Src2.getImm(), true);
2649  Eval = evaluateANDri(R1, A, Inputs, RC);
2650  break;
2651  }
2652  case Hexagon::A2_or:
2653  case Hexagon::A2_orp:
2654  Eval = evaluateORrr(R1, RegisterSubReg(Src2), Inputs, RC);
2655  break;
2656  case Hexagon::A2_orir: {
2657  if (!Src2.isImm())
2658  return false;
2659  APInt A(32, Src2.getImm(), true);
2660  Eval = evaluateORri(R1, A, Inputs, RC);
2661  break;
2662  }
2663  case Hexagon::A2_xor:
2664  case Hexagon::A2_xorp:
2665  Eval = evaluateXORrr(R1, RegisterSubReg(Src2), Inputs, RC);
2666  break;
2667  }
2668  if (Eval) {
2669  RegisterSubReg DefR(MI.getOperand(0));
2670  Outputs.update(DefR.Reg, RC);
2671  }
2672  return Eval;
2673 }
2674 
2675 bool HexagonConstEvaluator::evaluateHexCondMove(const MachineInstr &MI,
2676  const CellMap &Inputs, CellMap &Outputs) {
2677  // Dst0 = Cond1 ? Src2 : Src3
2678  RegisterSubReg CR(MI.getOperand(1));
2679  assert(Inputs.has(CR.Reg));
2680  LatticeCell LS;
2681  if (!getCell(CR, Inputs, LS))
2682  return false;
2683  uint32_t Ps = LS.properties();
2684  unsigned TakeOp;
2685  if (Ps & ConstantProperties::Zero)
2686  TakeOp = 3;
2687  else if (Ps & ConstantProperties::NonZero)
2688  TakeOp = 2;
2689  else
2690  return false;
2691 
2692  const MachineOperand &ValOp = MI.getOperand(TakeOp);
2693  RegisterSubReg DefR(MI.getOperand(0));
2694  LatticeCell RC = Outputs.get(DefR.Reg);
2695 
2696  if (ValOp.isImm()) {
2697  int64_t V = ValOp.getImm();
2698  unsigned W = getRegBitWidth(DefR.Reg);
2699  APInt A(W, V, true);
2700  const Constant *C = intToConst(A);
2701  RC.add(C);
2702  Outputs.update(DefR.Reg, RC);
2703  return true;
2704  }
2705  if (ValOp.isReg()) {
2706  RegisterSubReg R(ValOp);
2707  const LatticeCell &LR = Inputs.get(R.Reg);
2708  LatticeCell LSR;
2709  if (!evaluate(R, LR, LSR))
2710  return false;
2711  RC.meet(LSR);
2712  Outputs.update(DefR.Reg, RC);
2713  return true;
2714  }
2715  return false;
2716 }
2717 
2718 bool HexagonConstEvaluator::evaluateHexExt(const MachineInstr &MI,
2719  const CellMap &Inputs, CellMap &Outputs) {
2720  // Dst0 = ext R1
2721  RegisterSubReg R1(MI.getOperand(1));
2722  assert(Inputs.has(R1.Reg));
2723 
2724  unsigned Opc = MI.getOpcode();
2725  unsigned Bits;
2726  switch (Opc) {
2727  case Hexagon::A2_sxtb:
2728  case Hexagon::A2_zxtb:
2729  Bits = 8;
2730  break;
2731  case Hexagon::A2_sxth:
2732  case Hexagon::A2_zxth:
2733  Bits = 16;
2734  break;
2735  case Hexagon::A2_sxtw:
2736  Bits = 32;
2737  break;
2738  default:
2739  llvm_unreachable("Unhandled extension opcode");
2740  }
2741 
2742  bool Signed = false;
2743  switch (Opc) {
2744  case Hexagon::A2_sxtb:
2745  case Hexagon::A2_sxth:
2746  case Hexagon::A2_sxtw:
2747  Signed = true;
2748  break;
2749  }
2750 
2751  RegisterSubReg DefR(MI.getOperand(0));
2752  unsigned BW = getRegBitWidth(DefR.Reg);
2753  LatticeCell RC = Outputs.get(DefR.Reg);
2754  bool Eval = Signed ? evaluateSEXTr(R1, BW, Bits, Inputs, RC)
2755  : evaluateZEXTr(R1, BW, Bits, Inputs, RC);
2756  if (!Eval)
2757  return false;
2758  Outputs.update(DefR.Reg, RC);
2759  return true;
2760 }
2761 
2762 bool HexagonConstEvaluator::evaluateHexVector1(const MachineInstr &MI,
2763  const CellMap &Inputs, CellMap &Outputs) {
2764  // DefR = op R1
2765  RegisterSubReg DefR(MI.getOperand(0));
2766  RegisterSubReg R1(MI.getOperand(1));
2767  assert(Inputs.has(R1.Reg));
2768  LatticeCell RC = Outputs.get(DefR.Reg);
2769  bool Eval;
2770 
2771  unsigned Opc = MI.getOpcode();
2772  switch (Opc) {
2773  case Hexagon::S2_vsplatrb:
2774  // Rd = 4 times Rs:0..7
2775  Eval = evaluateSplatr(R1, 8, 4, Inputs, RC);
2776  break;
2777  case Hexagon::S2_vsplatrh:
2778  // Rdd = 4 times Rs:0..15
2779  Eval = evaluateSplatr(R1, 16, 4, Inputs, RC);
2780  break;
2781  default:
2782  return false;
2783  }
2784 
2785  if (!Eval)
2786  return false;
2787  Outputs.update(DefR.Reg, RC);
2788  return true;
2789 }
2790 
2791 bool HexagonConstEvaluator::rewriteHexConstDefs(MachineInstr &MI,
2792  const CellMap &Inputs, bool &AllDefs) {
2793  AllDefs = false;
2794 
2795  // Some diagnostics.
2796  // LLVM_DEBUG({...}) gets confused with all this code as an argument.
2797 #ifndef NDEBUG
2798  bool Debugging = DebugFlag && isCurrentDebugType(DEBUG_TYPE);
2799  if (Debugging) {
2800  bool Const = true, HasUse = false;
2801  for (const MachineOperand &MO : MI.operands()) {
2802  if (!MO.isReg() || !MO.isUse() || MO.isImplicit())
2803  continue;
2804  RegisterSubReg R(MO);
2805  if (!R.Reg.isVirtual())
2806  continue;
2807  HasUse = true;
2808  // PHIs can legitimately have "top" cells after propagation.
2809  if (!MI.isPHI() && !Inputs.has(R.Reg)) {
2810  dbgs() << "Top " << printReg(R.Reg, &HRI, R.SubReg)
2811  << " in MI: " << MI;
2812  continue;
2813  }
2814  const LatticeCell &L = Inputs.get(R.Reg);
2815  Const &= L.isSingle();
2816  if (!Const)
2817  break;
2818  }
2819  if (HasUse && Const) {
2820  if (!MI.isCopy()) {
2821  dbgs() << "CONST: " << MI;
2822  for (const MachineOperand &MO : MI.operands()) {
2823  if (!MO.isReg() || !MO.isUse() || MO.isImplicit())
2824  continue;
2825  Register R = MO.getReg();
2826  dbgs() << printReg(R, &TRI) << ": " << Inputs.get(R) << "\n";
2827  }
2828  }
2829  }
2830  }
2831 #endif
2832 
2833  // Avoid generating TFRIs for register transfers---this will keep the
2834  // coalescing opportunities.
2835  if (MI.isCopy())
2836  return false;
2837 
2838  MachineFunction *MF = MI.getParent()->getParent();
2839  auto &HST = MF->getSubtarget<HexagonSubtarget>();
2840 
2841  // Collect all virtual register-def operands.
2842  SmallVector<unsigned,2> DefRegs;
2843  for (const MachineOperand &MO : MI.operands()) {
2844  if (!MO.isReg() || !MO.isDef())
2845  continue;
2846  Register R = MO.getReg();
2847  if (!R.isVirtual())
2848  continue;
2849  assert(!MO.getSubReg());
2850  assert(Inputs.has(R));
2851  DefRegs.push_back(R);
2852  }
2853 
2854  MachineBasicBlock &B = *MI.getParent();
2855  const DebugLoc &DL = MI.getDebugLoc();
2856  unsigned ChangedNum = 0;
2857 #ifndef NDEBUG
2859 #endif
2860 
2861  // For each defined register, if it is a constant, create an instruction
2862  // NewR = const
2863  // and replace all uses of the defined register with NewR.
2864  for (unsigned i = 0, n = DefRegs.size(); i < n; ++i) {
2865  unsigned R = DefRegs[i];
2866  const LatticeCell &L = Inputs.get(R);
2867  if (L.isBottom())
2868  continue;
2869  const TargetRegisterClass *RC = MRI->getRegClass(R);
2870  MachineBasicBlock::iterator At = MI.getIterator();
2871 
2872  if (!L.isSingle()) {
2873  // If this a zero/non-zero cell, we can fold a definition
2874  // of a predicate register.
2875  using P = ConstantProperties;
2876 
2877  uint64_t Ps = L.properties();
2878  if (!(Ps & (P::Zero|P::NonZero)))
2879  continue;
2880  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
2881  if (RC != PredRC)
2882  continue;
2883  const MCInstrDesc *NewD = (Ps & P::Zero) ?
2884  &HII.get(Hexagon::PS_false) :
2885  &HII.get(Hexagon::PS_true);
2886  Register NewR = MRI->createVirtualRegister(PredRC);
2887  const MachineInstrBuilder &MIB = BuildMI(B, At, DL, *NewD, NewR);
2888  (void)MIB;
2889 #ifndef NDEBUG
2890  NewInstrs.push_back(&*MIB);
2891 #endif
2892  replaceAllRegUsesWith(R, NewR);
2893  } else {
2894  // This cell has a single value.
2895  APInt A;
2896  if (!constToInt(L.Value, A) || !A.isSignedIntN(64))
2897  continue;
2898  const TargetRegisterClass *NewRC;
2899  const MCInstrDesc *NewD;
2900 
2901  unsigned W = getRegBitWidth(R);
2902  int64_t V = A.getSExtValue();
2903  assert(W == 32 || W == 64);
2904  if (W == 32)
2905  NewRC = &Hexagon::IntRegsRegClass;
2906  else
2907  NewRC = &Hexagon::DoubleRegsRegClass;
2908  Register NewR = MRI->createVirtualRegister(NewRC);
2909  const MachineInstr *NewMI;
2910 
2911  if (W == 32) {
2912  NewD = &HII.get(Hexagon::A2_tfrsi);
2913  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2914  .addImm(V);
2915  } else {
2916  if (A.isSignedIntN(8)) {
2917  NewD = &HII.get(Hexagon::A2_tfrpi);
2918  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2919  .addImm(V);
2920  } else {
2921  int32_t Hi = V >> 32;
2922  int32_t Lo = V & 0xFFFFFFFFLL;
2923  if (isInt<8>(Hi) && isInt<8>(Lo)) {
2924  NewD = &HII.get(Hexagon::A2_combineii);
2925  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2926  .addImm(Hi)
2927  .addImm(Lo);
2928  } else if (MF->getFunction().hasOptSize() || !HST.isTinyCore()) {
2929  // Disable CONST64 for tiny core since it takes a LD resource.
2930  NewD = &HII.get(Hexagon::CONST64);
2931  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2932  .addImm(V);
2933  } else
2934  return false;
2935  }
2936  }
2937  (void)NewMI;
2938 #ifndef NDEBUG
2939  NewInstrs.push_back(NewMI);
2940 #endif
2941  replaceAllRegUsesWith(R, NewR);
2942  }
2943  ChangedNum++;
2944  }
2945 
2946  LLVM_DEBUG({
2947  if (!NewInstrs.empty()) {
2948  MachineFunction &MF = *MI.getParent()->getParent();
2949  dbgs() << "In function: " << MF.getName() << "\n";
2950  dbgs() << "Rewrite: for " << MI << " created " << *NewInstrs[0];
2951  for (unsigned i = 1; i < NewInstrs.size(); ++i)
2952  dbgs() << " " << *NewInstrs[i];
2953  }
2954  });
2955 
2956  AllDefs = (ChangedNum == DefRegs.size());
2957  return ChangedNum > 0;
2958 }
2959 
2960 bool HexagonConstEvaluator::rewriteHexConstUses(MachineInstr &MI,
2961  const CellMap &Inputs) {
2962  bool Changed = false;
2963  unsigned Opc = MI.getOpcode();
2964  MachineBasicBlock &B = *MI.getParent();
2965  const DebugLoc &DL = MI.getDebugLoc();
2966  MachineBasicBlock::iterator At = MI.getIterator();
2967  MachineInstr *NewMI = nullptr;
2968 
2969  switch (Opc) {
2970  case Hexagon::M2_maci:
2971  // Convert DefR += mpyi(R2, R3)
2972  // to DefR += mpyi(R, #imm),
2973  // or DefR -= mpyi(R, #imm).
2974  {
2975  RegisterSubReg DefR(MI.getOperand(0));
2976  assert(!DefR.SubReg);
2977  RegisterSubReg R2(MI.getOperand(2));
2978  RegisterSubReg R3(MI.getOperand(3));
2979  assert(Inputs.has(R2.Reg) && Inputs.has(R3.Reg));
2980  LatticeCell LS2, LS3;
2981  // It is enough to get one of the input cells, since we will only try
2982  // to replace one argument---whichever happens to be a single constant.
2983  bool HasC2 = getCell(R2, Inputs, LS2), HasC3 = getCell(R3, Inputs, LS3);
2984  if (!HasC2 && !HasC3)
2985  return false;
2986  bool Zero = ((HasC2 && (LS2.properties() & ConstantProperties::Zero)) ||
2987  (HasC3 && (LS3.properties() & ConstantProperties::Zero)));
2988  // If one of the operands is zero, eliminate the multiplication.
2989  if (Zero) {
2990  // DefR == R1 (tied operands).
2991  MachineOperand &Acc = MI.getOperand(1);
2992  RegisterSubReg R1(Acc);
2993  unsigned NewR = R1.Reg;
2994  if (R1.SubReg) {
2995  // Generate COPY. FIXME: Replace with the register:subregister.
2996  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
2997  NewR = MRI->createVirtualRegister(RC);
2998  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
2999  .addReg(R1.Reg, getRegState(Acc), R1.SubReg);
3000  }
3001  replaceAllRegUsesWith(DefR.Reg, NewR);
3002  MRI->clearKillFlags(NewR);
3003  Changed = true;
3004  break;
3005  }
3006 
3007  bool Swap = false;
3008  if (!LS3.isSingle()) {
3009  if (!LS2.isSingle())
3010  return false;
3011  Swap = true;
3012  }
3013  const LatticeCell &LI = Swap ? LS2 : LS3;
3014  const MachineOperand &OpR2 = Swap ? MI.getOperand(3)
3015  : MI.getOperand(2);
3016  // LI is single here.
3017  APInt A;
3018  if (!constToInt(LI.Value, A) || !A.isSignedIntN(8))
3019  return false;
3020  int64_t V = A.getSExtValue();
3021  const MCInstrDesc &D = (V >= 0) ? HII.get(Hexagon::M2_macsip)
3022  : HII.get(Hexagon::M2_macsin);
3023  if (V < 0)
3024  V = -V;
3025  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3026  Register NewR = MRI->createVirtualRegister(RC);
3027  const MachineOperand &Src1 = MI.getOperand(1);
3028  NewMI = BuildMI(B, At, DL, D, NewR)
3029  .addReg(Src1.getReg(), getRegState(Src1), Src1.getSubReg())
3030  .addReg(OpR2.getReg(), getRegState(OpR2), OpR2.getSubReg())
3031  .addImm(V);
3032  replaceAllRegUsesWith(DefR.Reg, NewR);
3033  Changed = true;
3034  break;
3035  }
3036 
3037  case Hexagon::A2_and:
3038  {
3039  RegisterSubReg R1(MI.getOperand(1));
3040  RegisterSubReg R2(MI.getOperand(2));
3041  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
3042  LatticeCell LS1, LS2;
3043  unsigned CopyOf = 0;
3044  // Check if any of the operands is -1 (i.e. all bits set).
3045  if (getCell(R1, Inputs, LS1) && LS1.isSingle()) {
3046  APInt M1;
3047  if (constToInt(LS1.Value, M1) && !~M1)
3048  CopyOf = 2;
3049  }
3050  else if (getCell(R2, Inputs, LS2) && LS2.isSingle()) {
3051  APInt M1;
3052  if (constToInt(LS2.Value, M1) && !~M1)
3053  CopyOf = 1;
3054  }
3055  if (!CopyOf)
3056  return false;
3057  MachineOperand &SO = MI.getOperand(CopyOf);
3058  RegisterSubReg SR(SO);
3059  RegisterSubReg DefR(MI.getOperand(0));
3060  unsigned NewR = SR.Reg;
3061  if (SR.SubReg) {
3062  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3063  NewR = MRI->createVirtualRegister(RC);
3064  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
3065  .addReg(SR.Reg, getRegState(SO), SR.SubReg);
3066  }
3067  replaceAllRegUsesWith(DefR.Reg, NewR);
3068  MRI->clearKillFlags(NewR);
3069  Changed = true;
3070  }
3071  break;
3072 
3073  case Hexagon::A2_or:
3074  {
3075  RegisterSubReg R1(MI.getOperand(1));
3076  RegisterSubReg R2(MI.getOperand(2));
3077  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
3078  LatticeCell LS1, LS2;
3079  unsigned CopyOf = 0;
3080 
3081  using P = ConstantProperties;
3082 
3083  if (getCell(R1, Inputs, LS1) && (LS1.properties() & P::Zero))
3084  CopyOf = 2;
3085  else if (getCell(R2, Inputs, LS2) && (LS2.properties() & P::Zero))
3086  CopyOf = 1;
3087  if (!CopyOf)
3088  return false;
3089  MachineOperand &SO = MI.getOperand(CopyOf);
3090  RegisterSubReg SR(SO);
3091  RegisterSubReg DefR(MI.getOperand(0));
3092  unsigned NewR = SR.Reg;
3093  if (SR.SubReg) {
3094  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3095  NewR = MRI->createVirtualRegister(RC);
3096  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
3097  .addReg(SR.Reg, getRegState(SO), SR.SubReg);
3098  }
3099  replaceAllRegUsesWith(DefR.Reg, NewR);
3100  MRI->clearKillFlags(NewR);
3101  Changed = true;
3102  }
3103  break;
3104  }
3105 
3106  if (NewMI) {
3107  // clear all the kill flags of this new instruction.
3108  for (MachineOperand &MO : NewMI->operands())
3109  if (MO.isReg() && MO.isUse())
3110  MO.setIsKill(false);
3111  }
3112 
3113  LLVM_DEBUG({
3114  if (NewMI) {
3115  dbgs() << "Rewrite: for " << MI;
3116  if (NewMI != &MI)
3117  dbgs() << " created " << *NewMI;
3118  else
3119  dbgs() << " modified the instruction itself and created:" << *NewMI;
3120  }
3121  });
3122 
3123  return Changed;
3124 }
3125 
3126 void HexagonConstEvaluator::replaceAllRegUsesWith(Register FromReg,
3127  Register ToReg) {
3128  assert(FromReg.isVirtual());
3129  assert(ToReg.isVirtual());
3130  for (MachineOperand &O :
3132  O.setReg(ToReg);
3133 }
3134 
3135 bool HexagonConstEvaluator::rewriteHexBranch(MachineInstr &BrI,
3136  const CellMap &Inputs) {
3137  MachineBasicBlock &B = *BrI.getParent();
3138  unsigned NumOp = BrI.getNumOperands();
3139  if (!NumOp)
3140  return false;
3141 
3142  bool FallsThru;
3144  bool Eval = evaluate(BrI, Inputs, Targets, FallsThru);
3145  unsigned NumTargets = Targets.size();
3146  if (!Eval || NumTargets > 1 || (NumTargets == 1 && FallsThru))
3147  return false;
3148  if (BrI.getOpcode() == Hexagon::J2_jump)
3149  return false;
3150 
3151  LLVM_DEBUG(dbgs() << "Rewrite(" << printMBBReference(B) << "):" << BrI);
3152  bool Rewritten = false;
3153  if (NumTargets > 0) {
3154  assert(!FallsThru && "This should have been checked before");
3155  // MIB.addMBB needs non-const pointer.
3156  MachineBasicBlock *TargetB = const_cast<MachineBasicBlock*>(Targets[0]);
3157  bool Moot = B.isLayoutSuccessor(TargetB);
3158  if (!Moot) {
3159  // If we build a branch here, we must make sure that it won't be
3160  // erased as "non-executable". We can't mark any new instructions
3161  // as executable here, so we need to overwrite the BrI, which we
3162  // know is executable.
3163  const MCInstrDesc &JD = HII.get(Hexagon::J2_jump);
3164  auto NI = BuildMI(B, BrI.getIterator(), BrI.getDebugLoc(), JD)
3165  .addMBB(TargetB);
3166  BrI.setDesc(JD);
3167  while (BrI.getNumOperands() > 0)
3168  BrI.removeOperand(0);
3169  // This ensures that all implicit operands (e.g. implicit-def %r31, etc)
3170  // are present in the rewritten branch.
3171  for (auto &Op : NI->operands())
3172  BrI.addOperand(Op);
3173  NI->eraseFromParent();
3174  Rewritten = true;
3175  }
3176  }
3177 
3178  // Do not erase instructions. A newly created instruction could get
3179  // the same address as an instruction marked as executable during the
3180  // propagation.
3181  if (!Rewritten)
3182  replaceWithNop(BrI);
3183  return true;
3184 }
3185 
3187  return new HexagonConstPropagation();
3188 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
i
i
Definition: README.txt:29
llvm::APFloat::isInfinity
bool isInfinity() const
Definition: APFloat.h:1212
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4709
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
MathExtras.h
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::AArch64CC::NE
@ NE
Definition: AArch64BaseInfo.h:256
llvm::AArch64_AM::LSL
@ LSL
Definition: AArch64AddressingModes.h:35
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::MachineRegisterInfo::createVirtualRegister
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
Definition: MachineRegisterInfo.cpp:156
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
T
llvm::Function
Definition: Function.h:60
StringRef.h
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::MachineOperand::setIsKill
void setIsKill(bool Val=true)
Definition: MachineOperand.h:509
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1182
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:266
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:855
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:116
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1478
HexagonSubtarget.h
llvm::MipsISD::Lo
@ Lo
Definition: MipsISelLowering.h:79
ErrorHandling.h
ToRemove
ReachingDefAnalysis InstSet & ToRemove
Definition: ARMLowOverheadLoops.cpp:542
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::APInt::zextOrTrunc
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:994
llvm::AMDGPU::HSAMD::ValueType::U32
@ U32
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:125
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:551
APInt.h
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:320
llvm::ConstantFP::isZero
bool isZero() const
Return true if the value is positive or negative zero.
Definition: Constants.h:302
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1411
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::ConstantFP::isNaN
bool isNaN() const
Return true if the value is a NaN.
Definition: Constants.h:311
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:477
llvm::ConstantFP::getValueAPF
const APFloat & getValueAPF() const
Definition: Constants.h:298
getBitWidth
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Definition: ValueTracking.cpp:98
llvm::APInt::lshr
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:832
llvm::Lo_32
constexpr uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
Definition: MathExtras.h:336
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:239
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
MachineRegisterInfo.h
llvm::MipsISD::Hi
@ Hi
Definition: MipsISelLowering.h:75
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::MachineInstr::isUnconditionalBranch
bool isUnconditionalBranch(QueryType Type=AnyInBundle) const
Return true if this is a branch which always transfers control flow to some other block.
Definition: MachineInstr.h:926
llvm::SetVector::remove
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
R2
#define R2(n)
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:666
llvm::APInt::isNegative
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
llvm::MachineOperand::isImplicit
bool isImplicit() const
Definition: MachineOperand.h:379
llvm::MachineInstrBuilder::addMBB
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Definition: MachineInstrBuilder.h:146
L2
add sub stmia L5 ldr L2
Definition: README.txt:201
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:546
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:369
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
EQ
#define EQ(a, b)
Definition: regexec.c:112
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::AArch64_AM::LSR
@ LSR
Definition: AArch64AddressingModes.h:36
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1466
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::ConstantFP
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:257
APFloat.h
llvm::MCOI::BranchTarget
@ BranchTarget
Definition: MCInstrDesc.h:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
DEBUG_TYPE
#define DEBUG_TYPE
Definition: HexagonConstPropagation.cpp:46
HexagonInstrInfo.h
llvm::APInt::countTrailingZeros
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1543
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::APInt::ashr
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:808
PB
PassBuilder PB(Machine, PassOpts->PTO, None, &PIC)
llvm::Register::isVirtual
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::MachineRegisterInfo::clearKillFlags
void clearKillFlags(Register Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
Definition: MachineRegisterInfo.cpp:433
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:656
llvm::APFloat
Definition: APFloat.h:701
llvm::APInt::slt
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1080
llvm::getRegState
unsigned getRegState(const MachineOperand &RegOp)
Get all register state flags from machine operand RegOp.
Definition: MachineInstrBuilder.h:566
llvm::AMDGPU::getRegBitWidth
unsigned getRegBitWidth(unsigned RCID)
Get the size in bits of a register from the register class RC.
Definition: AMDGPUBaseInfo.cpp:1984
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:445
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::HexagonISD::CONST32
@ CONST32
Definition: HexagonISelLowering.h:37
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
Index
uint32_t Index
Definition: ELFObjHandler.cpp:82
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
uint64_t
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:396
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::ARM_AM::add
@ add
Definition: ARMAddressingModes.h:39
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::createHexagonConstPropagationPass
FunctionPass * createHexagonConstPropagationPass()
Definition: HexagonConstPropagation.cpp:3186
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:596
propagate
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
Definition: CFLAndersAliasAnalysis.cpp:596
MachineFunctionPass.h
HexagonRegisterInfo.h
llvm::ConstantFP::isNegative
bool isNegative() const
Return true if the sign bit is set.
Definition: Constants.h:305
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
memcpy
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1990
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::Hexagon::ps_sub_hi
@ ps_sub_hi
Definition: HexagonRegisterInfo.h:26
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::HexagonInstrInfo
Definition: HexagonInstrInfo.h:38
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1571
llvm::isCurrentDebugType
bool isCurrentDebugType(const char *Type)
isCurrentDebugType - Return true if the specified string is the debug type specified on the command l...
Definition: Debug.cpp:52
llvm::MachineBasicBlock::phis
iterator_range< iterator > phis()
Returns a range that iterates over the phis in the basic block.
Definition: MachineBasicBlock.h:333
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:561
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1115
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::initializeHexagonConstPropagationPass
void initializeHexagonConstPropagationPass(PassRegistry &Registry)
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:516
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:194
uint32_t
Compiler.h
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
llvm::APInt::ult
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1061
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:364
llvm::Function::hasOptSize
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:664
rewrite
static bool rewrite(Function &F)
Definition: PoisonChecking.cpp:255
llvm::APInt::zext
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:973
llvm::SetVector::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
j
return j(j<< 16)
llvm::MachineFunction::getBlockNumbered
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Definition: MachineFunction.h:788
llvm::APInt::countLeadingZeros
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1504
llvm::Type::getInt64Ty
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:240
llvm::APInt::trunc
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:898
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:622
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::codeview::InlineeLinesSignature::Normal
@ Normal
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::X86::FirstMacroFusionInstKind::Cmp
@ Cmp
llvm::Hexagon::ps_sub_lo
@ ps_sub_lo
Definition: HexagonRegisterInfo.h:26
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
INITIALIZE_PASS
INITIALIZE_PASS(HexagonConstPropagation, "hexagon-constp", "Hexagon Constant Propagation", false, false) HexagonConstEvaluator
Definition: HexagonConstPropagation.cpp:1915
llvm::AArch64CC::LS
@ LS
Definition: AArch64BaseInfo.h:264
llvm::ISD::INLINEASM_BR
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
Definition: ISDOpcodes.h:1028
Casting.h
llvm::post_order
iterator_range< po_iterator< T > > post_order(const T &G)
Definition: PostOrderIterator.h:189
llvm::APInt::isSameValue
static bool isSameValue(const APInt &I1, const APInt &I2)
Determine if two APInts have the same value, after zero-extending one of them (if needed!...
Definition: APInt.h:534
llvm::MachineFunction::print
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
Definition: MachineFunction.cpp:571
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::MachineOperand::isImm
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
Definition: MachineOperand.h:322
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:439
llvm::codeview::ModifierOptions::Const
@ Const
llvm::APInt::sext
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:946
llvm::MachineInstr::setDesc
void setDesc(const MCInstrDesc &TID)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one.
Definition: MachineInstr.h:1763
llvm::MachineInstr::removeOperand
void removeOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with.
Definition: MachineInstr.cpp:276
llvm::DebugFlag
bool DebugFlag
This boolean is set to true if the '-debug' command line option is specified.
Definition: Debug.cpp:45
PostOrderIterator.h
llvm::Registry
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:357
llvm::ConstantInt::isNegative
bool isNegative() const
Definition: Constants.h:189
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
MachineInstrBuilder.h
N
#define N
llvm::APInt::countTrailingOnes
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1559
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:519
llvm::MachineInstr::addOperand
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
Definition: MachineInstr.cpp:184
llvm::HexagonSubtarget
Definition: HexagonSubtarget.h:43
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:365
MachineOperand.h
llvm::APInt::getLowBitsSet
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:289
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::HexagonRegisterInfo
Definition: HexagonRegisterInfo.h:29
llvm::GraphTraits
Definition: GraphTraits.h:37
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::X86II::TB
@ TB
Definition: X86BaseInfo.h:805
llvm::APInt::shl
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:854
llvm::M1
unsigned M1(unsigned Val)
Definition: VE.h:370
raw_ostream.h
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
MachineFunction.h
llvm::printReg
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.
Definition: TargetRegisterInfo.cpp:111
llvm::MachineInstrBundleIterator< const MachineInstr >
llvm::APInt::countLeadingOnes
unsigned countLeadingOnes() const
Count the number of leading one bits.
Definition: APInt.h:1520
llvm::MachineInstr::operands
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:641
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
SubReg
unsigned SubReg
Definition: AArch64AdvSIMDScalarPass.cpp:104
getCmp
static Comparison getCmp(SelectionDAG &DAG, SDValue CmpOp0, SDValue CmpOp1, ISD::CondCode Cond, const SDLoc &DL, SDValue Chain=SDValue(), bool IsSignaling=false)
Definition: SystemZISelLowering.cpp:2758
SetVector.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38