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