LLVM  7.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 = ...". 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(" << printMBBReference(*MB) << "): " << 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 " << printMBBReference(*PB) << "->"
646  << printMBBReference(*MB) << " 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 " << printMBBReference(*PB) << ": "
662  << printReg(UseR.Reg, &MCE.TRI, UseR.SubReg) << SrcC << '\n');
663  Changed |= Eval ? DefC.meet(SrcC)
664  : DefC.setBottom();
665  Cells.update(DefR.Reg, DefC);
666  if (DefC.isBottom())
667  break;
668  }
669  if (Changed)
670  visitUsesOf(DefR.Reg);
671 }
672 
673 void MachineConstPropagator::visitNonBranch(const MachineInstr &MI) {
674  DEBUG(dbgs() << "Visiting MI(" << printMBBReference(*MI.getParent())
675  << "): " << MI);
676  CellMap Outputs;
677  bool Eval = MCE.evaluate(MI, Cells, Outputs);
678  DEBUG({
679  if (Eval) {
680  dbgs() << " outputs:";
681  for (auto &I : Outputs)
682  dbgs() << ' ' << I.second;
683  dbgs() << '\n';
684  }
685  });
686 
687  // Update outputs. If the value was not computed, set all the
688  // def cells to bottom.
689  for (const MachineOperand &MO : MI.operands()) {
690  if (!MO.isReg() || !MO.isDef())
691  continue;
692  Register DefR(MO);
693  // Only track virtual registers.
695  continue;
696  bool Changed = false;
697  // If the evaluation failed, set cells for all output registers to bottom.
698  if (!Eval) {
699  const LatticeCell &T = Cells.get(DefR.Reg);
700  Changed = !T.isBottom();
701  Cells.update(DefR.Reg, Bottom);
702  } else {
703  // Find the corresponding cell in the computed outputs.
704  // If it's not there, go on to the next def.
705  if (!Outputs.has(DefR.Reg))
706  continue;
707  LatticeCell RC = Cells.get(DefR.Reg);
708  Changed = RC.meet(Outputs.get(DefR.Reg));
709  Cells.update(DefR.Reg, RC);
710  }
711  if (Changed)
712  visitUsesOf(DefR.Reg);
713  }
714 }
715 
716 // \brief Starting at a given branch, visit remaining branches in the block.
717 // Traverse over the subsequent branches for as long as the preceding one
718 // can fall through. Add all the possible targets to the flow work queue,
719 // including the potential fall-through to the layout-successor block.
720 void MachineConstPropagator::visitBranchesFrom(const MachineInstr &BrI) {
721  const MachineBasicBlock &B = *BrI.getParent();
722  unsigned MBN = B.getNumber();
725 
727  bool EvalOk = true, FallsThru = true;
728  while (It != End) {
729  const MachineInstr &MI = *It;
730  InstrExec.insert(&MI);
731  DEBUG(dbgs() << "Visiting " << (EvalOk ? "BR" : "br") << "("
732  << printMBBReference(B) << "): " << MI);
733  // Do not evaluate subsequent branches if the evaluation of any of the
734  // previous branches failed. Keep iterating over the branches only
735  // to mark them as executable.
736  EvalOk = EvalOk && MCE.evaluate(MI, Cells, Targets, FallsThru);
737  if (!EvalOk)
738  FallsThru = true;
739  if (!FallsThru)
740  break;
741  ++It;
742  }
743 
744  if (EvalOk) {
745  // Need to add all CFG successors that lead to EH landing pads.
746  // There won't be explicit branches to these blocks, but they must
747  // be processed.
748  for (const MachineBasicBlock *SB : B.successors()) {
749  if (SB->isEHPad())
750  Targets.insert(SB);
751  }
752  if (FallsThru) {
753  const MachineFunction &MF = *B.getParent();
755  MachineFunction::const_iterator Next = std::next(BI);
756  if (Next != MF.end())
757  Targets.insert(&*Next);
758  }
759  } else {
760  // If the evaluation of the branches failed, make "Targets" to be the
761  // set of all successors of the block from the CFG.
762  // If the evaluation succeeded for all visited branches, then if the
763  // last one set "FallsThru", then add an edge to the layout successor
764  // to the targets.
765  Targets.clear();
766  DEBUG(dbgs() << " failed to evaluate a branch...adding all CFG "
767  "successors\n");
768  for (const MachineBasicBlock *SB : B.successors())
769  Targets.insert(SB);
770  }
771 
772  for (const MachineBasicBlock *TB : Targets) {
773  unsigned TBN = TB->getNumber();
774  DEBUG(dbgs() << " pushing edge " << printMBBReference(B) << " -> "
775  << printMBBReference(*TB) << "\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 "
874  << printMBBReference(*MF.getBlockNumbered(Edge.first)) << "->"
875  << printMBBReference(*MF.getBlockNumbered(Edge.second))
876  << '\n');
877  if (Edge.first != EntryNum)
878  if (EdgeExec.count(Edge))
879  continue;
880  EdgeExec.insert(Edge);
881  MachineBasicBlock *SB = MF.getBlockNumbered(Edge.second);
882 
883  // Process the block in three stages:
884  // - visit all PHI nodes,
885  // - visit all non-branch instructions,
886  // - visit block branches.
887  MachineBasicBlock::const_iterator It = SB->begin(), End = SB->end();
888 
889  // Visit PHI nodes in the successor block.
890  while (It != End && It->isPHI()) {
891  InstrExec.insert(&*It);
892  visitPHI(*It);
893  ++It;
894  }
895 
896  // If the successor block just became executable, visit all instructions.
897  // To see if this is the first time we're visiting it, check the first
898  // non-debug instruction to see if it is executable.
899  while (It != End && It->isDebugValue())
900  ++It;
901  assert(It == End || !It->isPHI());
902  // If this block has been visited, go on to the next one.
903  if (It != End && InstrExec.count(&*It))
904  continue;
905  // For now, scan all non-branch instructions. Branches require different
906  // processing.
907  while (It != End && !It->isBranch()) {
908  if (!It->isDebugValue()) {
909  InstrExec.insert(&*It);
910  visitNonBranch(*It);
911  }
912  ++It;
913  }
914 
915  // Time to process the end of the block. This is different from
916  // processing regular (non-branch) instructions, because there can
917  // be multiple branches in a block, and they can cause the block to
918  // terminate early.
919  if (It != End) {
920  visitBranchesFrom(*It);
921  } else {
922  // If the block didn't have a branch, add all successor edges to the
923  // work queue. (There should really be only one successor in such case.)
924  unsigned SBN = SB->getNumber();
925  for (const MachineBasicBlock *SSB : SB->successors())
926  FlowQ.push(CFGEdge(SBN, SSB->getNumber()));
927  }
928  } // while (FlowQ)
929 
930  DEBUG({
931  dbgs() << "Cells after propagation:\n";
932  Cells.print(dbgs(), MCE.TRI);
933  dbgs() << "Dead CFG edges:\n";
934  for (const MachineBasicBlock &B : MF) {
935  unsigned BN = B.getNumber();
936  for (const MachineBasicBlock *SB : B.successors()) {
937  unsigned SN = SB->getNumber();
938  if (!EdgeExec.count(CFGEdge(BN, SN)))
939  dbgs() << " " << printMBBReference(B) << " -> "
940  << printMBBReference(*SB) << '\n';
941  }
942  }
943  });
944 }
945 
946 bool MachineConstPropagator::rewrite(MachineFunction &MF) {
947  bool Changed = false;
948  // Rewrite all instructions based on the collected cell information.
949  //
950  // Traverse the instructions in a post-order, so that rewriting an
951  // instruction can make changes "downstream" in terms of control-flow
952  // without affecting the rewriting process. (We should not change
953  // instructions that have not yet been visited by the rewriter.)
954  // The reason for this is that the rewriter can introduce new vregs,
955  // and replace uses of old vregs (which had corresponding cells
956  // computed during propagation) with these new vregs (which at this
957  // point would not have any cells, and would appear to be "top").
958  // If an attempt was made to evaluate an instruction with a fresh
959  // "top" vreg, it would cause an error (abend) in the evaluator.
960 
961  // Collect the post-order-traversal block ordering. The subsequent
962  // traversal/rewrite will update block successors, so it's safer
963  // if the visiting order it computed ahead of time.
964  std::vector<MachineBasicBlock*> POT;
965  for (MachineBasicBlock *B : post_order(&MF))
966  if (!B->empty())
967  POT.push_back(B);
968 
969  for (MachineBasicBlock *B : POT) {
970  // Walk the block backwards (which usually begin with the branches).
971  // If any branch is rewritten, we may need to update the successor
972  // information for this block. Unless the block's successors can be
973  // precisely determined (which may not be the case for indirect
974  // branches), we cannot modify any branch.
975 
976  // Compute the successor information.
978  bool HaveTargets = computeBlockSuccessors(B, Targets);
979  // Rewrite the executable instructions. Skip branches if we don't
980  // have block successor information.
981  for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) {
982  MachineInstr &MI = *I;
983  if (InstrExec.count(&MI)) {
984  if (MI.isBranch() && !HaveTargets)
985  continue;
986  Changed |= MCE.rewrite(MI, Cells);
987  }
988  }
989  // The rewriting could rewrite PHI nodes to non-PHI nodes, causing
990  // regular instructions to appear in between PHI nodes. Bring all
991  // the PHI nodes to the beginning of the block.
992  for (auto I = B->begin(), E = B->end(); I != E; ++I) {
993  if (I->isPHI())
994  continue;
995  // I is not PHI. Find the next PHI node P.
996  auto P = I;
997  while (++P != E)
998  if (P->isPHI())
999  break;
1000  // Not found.
1001  if (P == E)
1002  break;
1003  // Splice P right before I.
1004  B->splice(I, B, P);
1005  // Reset I to point at the just spliced PHI node.
1006  --I;
1007  }
1008  // Update the block successor information: remove unnecessary successors.
1009  if (HaveTargets) {
1011  for (MachineBasicBlock *SB : B->successors()) {
1012  if (!Targets.count(SB))
1013  ToRemove.push_back(const_cast<MachineBasicBlock*>(SB));
1014  Targets.remove(SB);
1015  }
1016  for (unsigned i = 0, n = ToRemove.size(); i < n; ++i)
1017  removeCFGEdge(B, ToRemove[i]);
1018  // If there are any blocks left in the computed targets, it means that
1019  // we think that the block could go somewhere, but the CFG does not.
1020  // This could legitimately happen in blocks that have non-returning
1021  // calls---we would think that the execution can continue, but the
1022  // CFG will not have a successor edge.
1023  }
1024  }
1025  // Need to do some final post-processing.
1026  // If a branch was not executable, it will not get rewritten, but should
1027  // be removed (or replaced with something equivalent to a A2_nop). We can't
1028  // erase instructions during rewriting, so this needs to be delayed until
1029  // now.
1030  for (MachineBasicBlock &B : MF) {
1031  MachineBasicBlock::iterator I = B.begin(), E = B.end();
1032  while (I != E) {
1033  auto Next = std::next(I);
1034  if (I->isBranch() && !InstrExec.count(&*I))
1035  B.erase(I);
1036  I = Next;
1037  }
1038  }
1039  return Changed;
1040 }
1041 
1042 // This is the constant propagation algorithm as described by Wegman-Zadeck.
1043 // Most of the terminology comes from there.
1044 bool MachineConstPropagator::run(MachineFunction &MF) {
1045  DEBUG(MF.print(dbgs() << "Starting MachineConstPropagator\n", nullptr));
1046 
1047  MRI = &MF.getRegInfo();
1048 
1049  Cells.clear();
1050  EdgeExec.clear();
1051  InstrExec.clear();
1052  assert(FlowQ.empty());
1053 
1054  propagate(MF);
1055  bool Changed = rewrite(MF);
1056 
1057  DEBUG({
1058  dbgs() << "End of MachineConstPropagator (Changed=" << Changed << ")\n";
1059  if (Changed)
1060  MF.print(dbgs(), nullptr);
1061  });
1062  return Changed;
1063 }
1064 
1065 // --------------------------------------------------------------------
1066 // Machine const evaluator.
1067 
1068 bool MachineConstEvaluator::getCell(const Register &R, const CellMap &Inputs,
1069  LatticeCell &RC) {
1071  return false;
1072  const LatticeCell &L = Inputs.get(R.Reg);
1073  if (!R.SubReg) {
1074  RC = L;
1075  return !RC.isBottom();
1076  }
1077  bool Eval = evaluate(R, L, RC);
1078  return Eval && !RC.isBottom();
1079 }
1080 
1081 bool MachineConstEvaluator::constToInt(const Constant *C,
1082  APInt &Val) const {
1083  const ConstantInt *CI = dyn_cast<ConstantInt>(C);
1084  if (!CI)
1085  return false;
1086  Val = CI->getValue();
1087  return true;
1088 }
1089 
1090 const ConstantInt *MachineConstEvaluator::intToConst(const APInt &Val) const {
1091  return ConstantInt::get(CX, Val);
1092 }
1093 
1094 bool MachineConstEvaluator::evaluateCMPrr(uint32_t Cmp, const Register &R1,
1095  const Register &R2, const CellMap &Inputs, bool &Result) {
1096  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1097  LatticeCell LS1, LS2;
1098  if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2))
1099  return false;
1100 
1101  bool IsProp1 = LS1.isProperty();
1102  bool IsProp2 = LS2.isProperty();
1103  if (IsProp1) {
1104  uint32_t Prop1 = LS1.properties();
1105  if (IsProp2)
1106  return evaluateCMPpp(Cmp, Prop1, LS2.properties(), Result);
1107  uint32_t NegCmp = Comparison::negate(Cmp);
1108  return evaluateCMPrp(NegCmp, R2, Prop1, Inputs, Result);
1109  }
1110  if (IsProp2) {
1111  uint32_t Prop2 = LS2.properties();
1112  return evaluateCMPrp(Cmp, R1, Prop2, Inputs, Result);
1113  }
1114 
1115  APInt A;
1116  bool IsTrue = true, IsFalse = true;
1117  for (unsigned i = 0; i < LS2.size(); ++i) {
1118  bool Res;
1119  bool Computed = constToInt(LS2.Values[i], A) &&
1120  evaluateCMPri(Cmp, R1, A, Inputs, Res);
1121  if (!Computed)
1122  return false;
1123  IsTrue &= Res;
1124  IsFalse &= !Res;
1125  }
1126  assert(!IsTrue || !IsFalse);
1127  // The actual logical value of the comparison is same as IsTrue.
1128  Result = IsTrue;
1129  // Return true if the result was proven to be true or proven to be false.
1130  return IsTrue || IsFalse;
1131 }
1132 
1133 bool MachineConstEvaluator::evaluateCMPri(uint32_t Cmp, const Register &R1,
1134  const APInt &A2, const CellMap &Inputs, bool &Result) {
1135  assert(Inputs.has(R1.Reg));
1136  LatticeCell LS;
1137  if (!getCell(R1, Inputs, LS))
1138  return false;
1139  if (LS.isProperty())
1140  return evaluateCMPpi(Cmp, LS.properties(), A2, Result);
1141 
1142  APInt A;
1143  bool IsTrue = true, IsFalse = true;
1144  for (unsigned i = 0; i < LS.size(); ++i) {
1145  bool Res;
1146  bool Computed = constToInt(LS.Values[i], A) &&
1147  evaluateCMPii(Cmp, A, A2, Res);
1148  if (!Computed)
1149  return false;
1150  IsTrue &= Res;
1151  IsFalse &= !Res;
1152  }
1153  assert(!IsTrue || !IsFalse);
1154  // The actual logical value of the comparison is same as IsTrue.
1155  Result = IsTrue;
1156  // Return true if the result was proven to be true or proven to be false.
1157  return IsTrue || IsFalse;
1158 }
1159 
1160 bool MachineConstEvaluator::evaluateCMPrp(uint32_t Cmp, const Register &R1,
1161  uint64_t Props2, const CellMap &Inputs, bool &Result) {
1162  assert(Inputs.has(R1.Reg));
1163  LatticeCell LS;
1164  if (!getCell(R1, Inputs, LS))
1165  return false;
1166  if (LS.isProperty())
1167  return evaluateCMPpp(Cmp, LS.properties(), Props2, Result);
1168 
1169  APInt A;
1170  uint32_t NegCmp = Comparison::negate(Cmp);
1171  bool IsTrue = true, IsFalse = true;
1172  for (unsigned i = 0; i < LS.size(); ++i) {
1173  bool Res;
1174  bool Computed = constToInt(LS.Values[i], A) &&
1175  evaluateCMPpi(NegCmp, Props2, A, Res);
1176  if (!Computed)
1177  return false;
1178  IsTrue &= Res;
1179  IsFalse &= !Res;
1180  }
1181  assert(!IsTrue || !IsFalse);
1182  Result = IsTrue;
1183  return IsTrue || IsFalse;
1184 }
1185 
1186 bool MachineConstEvaluator::evaluateCMPii(uint32_t Cmp, const APInt &A1,
1187  const APInt &A2, bool &Result) {
1188  // NE is a special kind of comparison (not composed of smaller properties).
1189  if (Cmp == Comparison::NE) {
1190  Result = !APInt::isSameValue(A1, A2);
1191  return true;
1192  }
1193  if (Cmp == Comparison::EQ) {
1194  Result = APInt::isSameValue(A1, A2);
1195  return true;
1196  }
1197  if (Cmp & Comparison::EQ) {
1198  if (APInt::isSameValue(A1, A2))
1199  return (Result = true);
1200  }
1201  assert((Cmp & (Comparison::L | Comparison::G)) && "Malformed comparison");
1202  Result = false;
1203 
1204  unsigned W1 = A1.getBitWidth();
1205  unsigned W2 = A2.getBitWidth();
1206  unsigned MaxW = (W1 >= W2) ? W1 : W2;
1207  if (Cmp & Comparison::U) {
1208  const APInt Zx1 = A1.zextOrSelf(MaxW);
1209  const APInt Zx2 = A2.zextOrSelf(MaxW);
1210  if (Cmp & Comparison::L)
1211  Result = Zx1.ult(Zx2);
1212  else if (Cmp & Comparison::G)
1213  Result = Zx2.ult(Zx1);
1214  return true;
1215  }
1216 
1217  // Signed comparison.
1218  const APInt Sx1 = A1.sextOrSelf(MaxW);
1219  const APInt Sx2 = A2.sextOrSelf(MaxW);
1220  if (Cmp & Comparison::L)
1221  Result = Sx1.slt(Sx2);
1222  else if (Cmp & Comparison::G)
1223  Result = Sx2.slt(Sx1);
1224  return true;
1225 }
1226 
1227 bool MachineConstEvaluator::evaluateCMPpi(uint32_t Cmp, uint32_t Props,
1228  const APInt &A2, bool &Result) {
1229  if (Props == ConstantProperties::Unknown)
1230  return false;
1231 
1232  // Should never see NaN here, but check for it for completeness.
1233  if (Props & ConstantProperties::NaN)
1234  return false;
1235  // Infinity could theoretically be compared to a number, but the
1236  // presence of infinity here would be very suspicious. If we don't
1237  // know for sure that the number is finite, bail out.
1238  if (!(Props & ConstantProperties::Finite))
1239  return false;
1240 
1241  // Let X be a number that has properties Props.
1242 
1243  if (Cmp & Comparison::U) {
1244  // In case of unsigned comparisons, we can only compare against 0.
1245  if (A2 == 0) {
1246  // Any x!=0 will be considered >0 in an unsigned comparison.
1247  if (Props & ConstantProperties::Zero)
1248  Result = (Cmp & Comparison::EQ);
1249  else if (Props & ConstantProperties::NonZero)
1250  Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE);
1251  else
1252  return false;
1253  return true;
1254  }
1255  // A2 is not zero. The only handled case is if X = 0.
1256  if (Props & ConstantProperties::Zero) {
1257  Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE);
1258  return true;
1259  }
1260  return false;
1261  }
1262 
1263  // Signed comparisons are different.
1264  if (Props & ConstantProperties::Zero) {
1265  if (A2 == 0)
1266  Result = (Cmp & Comparison::EQ);
1267  else
1268  Result = (Cmp == Comparison::NE) ||
1269  ((Cmp & Comparison::L) && !A2.isNegative()) ||
1270  ((Cmp & Comparison::G) && A2.isNegative());
1271  return true;
1272  }
1273  if (Props & ConstantProperties::PosOrZero) {
1274  // X >= 0 and !(A2 < 0) => cannot compare
1275  if (!A2.isNegative())
1276  return false;
1277  // X >= 0 and A2 < 0
1278  Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE);
1279  return true;
1280  }
1281  if (Props & ConstantProperties::NegOrZero) {
1282  // X <= 0 and Src1 < 0 => cannot compare
1283  if (A2 == 0 || A2.isNegative())
1284  return false;
1285  // X <= 0 and A2 > 0
1286  Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE);
1287  return true;
1288  }
1289 
1290  return false;
1291 }
1292 
1293 bool MachineConstEvaluator::evaluateCMPpp(uint32_t Cmp, uint32_t Props1,
1294  uint32_t Props2, bool &Result) {
1295  using P = ConstantProperties;
1296 
1297  if ((Props1 & P::NaN) && (Props2 & P::NaN))
1298  return false;
1299  if (!(Props1 & P::Finite) || !(Props2 & P::Finite))
1300  return false;
1301 
1302  bool Zero1 = (Props1 & P::Zero), Zero2 = (Props2 & P::Zero);
1303  bool NonZero1 = (Props1 & P::NonZero), NonZero2 = (Props2 & P::NonZero);
1304  if (Zero1 && Zero2) {
1305  Result = (Cmp & Comparison::EQ);
1306  return true;
1307  }
1308  if (Cmp == Comparison::NE) {
1309  if ((Zero1 && NonZero2) || (NonZero1 && Zero2))
1310  return (Result = true);
1311  return false;
1312  }
1313 
1314  if (Cmp & Comparison::U) {
1315  // In unsigned comparisons, we can only compare against a known zero,
1316  // or a known non-zero.
1317  if (Zero1 && NonZero2) {
1318  Result = (Cmp & Comparison::L);
1319  return true;
1320  }
1321  if (NonZero1 && Zero2) {
1322  Result = (Cmp & Comparison::G);
1323  return true;
1324  }
1325  return false;
1326  }
1327 
1328  // Signed comparison. The comparison is not NE.
1329  bool Poz1 = (Props1 & P::PosOrZero), Poz2 = (Props2 & P::PosOrZero);
1330  bool Nez1 = (Props1 & P::NegOrZero), Nez2 = (Props2 & P::NegOrZero);
1331  if (Nez1 && Poz2) {
1332  if (NonZero1 || NonZero2) {
1333  Result = (Cmp & Comparison::L);
1334  return true;
1335  }
1336  // Either (or both) could be zero. Can only say that X <= Y.
1337  if ((Cmp & Comparison::EQ) && (Cmp & Comparison::L))
1338  return (Result = true);
1339  }
1340  if (Poz1 && Nez2) {
1341  if (NonZero1 || NonZero2) {
1342  Result = (Cmp & Comparison::G);
1343  return true;
1344  }
1345  // Either (or both) could be zero. Can only say that X >= Y.
1346  if ((Cmp & Comparison::EQ) && (Cmp & Comparison::G))
1347  return (Result = true);
1348  }
1349 
1350  return false;
1351 }
1352 
1353 bool MachineConstEvaluator::evaluateCOPY(const Register &R1,
1354  const CellMap &Inputs, LatticeCell &Result) {
1355  return getCell(R1, Inputs, Result);
1356 }
1357 
1358 bool MachineConstEvaluator::evaluateANDrr(const Register &R1,
1359  const Register &R2, const CellMap &Inputs, LatticeCell &Result) {
1360  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1361  const LatticeCell &L1 = Inputs.get(R2.Reg);
1362  const LatticeCell &L2 = Inputs.get(R2.Reg);
1363  // If both sources are bottom, exit. Otherwise try to evaluate ANDri
1364  // with the non-bottom argument passed as the immediate. This is to
1365  // catch cases of ANDing with 0.
1366  if (L2.isBottom()) {
1367  if (L1.isBottom())
1368  return false;
1369  return evaluateANDrr(R2, R1, Inputs, Result);
1370  }
1371  LatticeCell LS2;
1372  if (!evaluate(R2, L2, LS2))
1373  return false;
1374  if (LS2.isBottom() || LS2.isProperty())
1375  return false;
1376 
1377  APInt A;
1378  for (unsigned i = 0; i < LS2.size(); ++i) {
1379  LatticeCell RC;
1380  bool Eval = constToInt(LS2.Values[i], A) &&
1381  evaluateANDri(R1, A, Inputs, RC);
1382  if (!Eval)
1383  return false;
1384  Result.meet(RC);
1385  }
1386  return !Result.isBottom();
1387 }
1388 
1389 bool MachineConstEvaluator::evaluateANDri(const Register &R1,
1390  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1391  assert(Inputs.has(R1.Reg));
1392  if (A2 == -1)
1393  return getCell(R1, Inputs, Result);
1394  if (A2 == 0) {
1395  LatticeCell RC;
1396  RC.add(intToConst(A2));
1397  // Overwrite Result.
1398  Result = RC;
1399  return true;
1400  }
1401  LatticeCell LS1;
1402  if (!getCell(R1, Inputs, LS1))
1403  return false;
1404  if (LS1.isBottom() || LS1.isProperty())
1405  return false;
1406 
1407  APInt A, ResA;
1408  for (unsigned i = 0; i < LS1.size(); ++i) {
1409  bool Eval = constToInt(LS1.Values[i], A) &&
1410  evaluateANDii(A, A2, ResA);
1411  if (!Eval)
1412  return false;
1413  const Constant *C = intToConst(ResA);
1414  Result.add(C);
1415  }
1416  return !Result.isBottom();
1417 }
1418 
1419 bool MachineConstEvaluator::evaluateANDii(const APInt &A1,
1420  const APInt &A2, APInt &Result) {
1421  Result = A1 & A2;
1422  return true;
1423 }
1424 
1425 bool MachineConstEvaluator::evaluateORrr(const Register &R1,
1426  const Register &R2, const CellMap &Inputs, LatticeCell &Result) {
1427  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1428  const LatticeCell &L1 = Inputs.get(R2.Reg);
1429  const LatticeCell &L2 = Inputs.get(R2.Reg);
1430  // If both sources are bottom, exit. Otherwise try to evaluate ORri
1431  // with the non-bottom argument passed as the immediate. This is to
1432  // catch cases of ORing with -1.
1433  if (L2.isBottom()) {
1434  if (L1.isBottom())
1435  return false;
1436  return evaluateORrr(R2, R1, Inputs, Result);
1437  }
1438  LatticeCell LS2;
1439  if (!evaluate(R2, L2, LS2))
1440  return false;
1441  if (LS2.isBottom() || LS2.isProperty())
1442  return false;
1443 
1444  APInt A;
1445  for (unsigned i = 0; i < LS2.size(); ++i) {
1446  LatticeCell RC;
1447  bool Eval = constToInt(LS2.Values[i], A) &&
1448  evaluateORri(R1, A, Inputs, RC);
1449  if (!Eval)
1450  return false;
1451  Result.meet(RC);
1452  }
1453  return !Result.isBottom();
1454 }
1455 
1456 bool MachineConstEvaluator::evaluateORri(const Register &R1,
1457  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1458  assert(Inputs.has(R1.Reg));
1459  if (A2 == 0)
1460  return getCell(R1, Inputs, Result);
1461  if (A2 == -1) {
1462  LatticeCell RC;
1463  RC.add(intToConst(A2));
1464  // Overwrite Result.
1465  Result = RC;
1466  return true;
1467  }
1468  LatticeCell LS1;
1469  if (!getCell(R1, Inputs, LS1))
1470  return false;
1471  if (LS1.isBottom() || LS1.isProperty())
1472  return false;
1473 
1474  APInt A, ResA;
1475  for (unsigned i = 0; i < LS1.size(); ++i) {
1476  bool Eval = constToInt(LS1.Values[i], A) &&
1477  evaluateORii(A, A2, ResA);
1478  if (!Eval)
1479  return false;
1480  const Constant *C = intToConst(ResA);
1481  Result.add(C);
1482  }
1483  return !Result.isBottom();
1484 }
1485 
1486 bool MachineConstEvaluator::evaluateORii(const APInt &A1,
1487  const APInt &A2, APInt &Result) {
1488  Result = A1 | A2;
1489  return true;
1490 }
1491 
1492 bool MachineConstEvaluator::evaluateXORrr(const Register &R1,
1493  const Register &R2, const CellMap &Inputs, LatticeCell &Result) {
1494  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1495  LatticeCell LS1, LS2;
1496  if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2))
1497  return false;
1498  if (LS1.isProperty()) {
1499  if (LS1.properties() & ConstantProperties::Zero)
1500  return !(Result = LS2).isBottom();
1501  return false;
1502  }
1503  if (LS2.isProperty()) {
1504  if (LS2.properties() & ConstantProperties::Zero)
1505  return !(Result = LS1).isBottom();
1506  return false;
1507  }
1508 
1509  APInt A;
1510  for (unsigned i = 0; i < LS2.size(); ++i) {
1511  LatticeCell RC;
1512  bool Eval = constToInt(LS2.Values[i], A) &&
1513  evaluateXORri(R1, A, Inputs, RC);
1514  if (!Eval)
1515  return false;
1516  Result.meet(RC);
1517  }
1518  return !Result.isBottom();
1519 }
1520 
1521 bool MachineConstEvaluator::evaluateXORri(const Register &R1,
1522  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1523  assert(Inputs.has(R1.Reg));
1524  LatticeCell LS1;
1525  if (!getCell(R1, Inputs, LS1))
1526  return false;
1527  if (LS1.isProperty()) {
1528  if (LS1.properties() & ConstantProperties::Zero) {
1529  const Constant *C = intToConst(A2);
1530  Result.add(C);
1531  return !Result.isBottom();
1532  }
1533  return false;
1534  }
1535 
1536  APInt A, XA;
1537  for (unsigned i = 0; i < LS1.size(); ++i) {
1538  bool Eval = constToInt(LS1.Values[i], A) &&
1539  evaluateXORii(A, A2, XA);
1540  if (!Eval)
1541  return false;
1542  const Constant *C = intToConst(XA);
1543  Result.add(C);
1544  }
1545  return !Result.isBottom();
1546 }
1547 
1548 bool MachineConstEvaluator::evaluateXORii(const APInt &A1,
1549  const APInt &A2, APInt &Result) {
1550  Result = A1 ^ A2;
1551  return true;
1552 }
1553 
1554 bool MachineConstEvaluator::evaluateZEXTr(const Register &R1, unsigned Width,
1555  unsigned Bits, const CellMap &Inputs, LatticeCell &Result) {
1556  assert(Inputs.has(R1.Reg));
1557  LatticeCell LS1;
1558  if (!getCell(R1, Inputs, LS1))
1559  return false;
1560  if (LS1.isProperty())
1561  return false;
1562 
1563  APInt A, XA;
1564  for (unsigned i = 0; i < LS1.size(); ++i) {
1565  bool Eval = constToInt(LS1.Values[i], A) &&
1566  evaluateZEXTi(A, Width, Bits, XA);
1567  if (!Eval)
1568  return false;
1569  const Constant *C = intToConst(XA);
1570  Result.add(C);
1571  }
1572  return true;
1573 }
1574 
1575 bool MachineConstEvaluator::evaluateZEXTi(const APInt &A1, unsigned Width,
1576  unsigned Bits, APInt &Result) {
1577  unsigned BW = A1.getBitWidth();
1578  (void)BW;
1579  assert(Width >= Bits && BW >= Bits);
1580  APInt Mask = APInt::getLowBitsSet(Width, Bits);
1581  Result = A1.zextOrTrunc(Width) & Mask;
1582  return true;
1583 }
1584 
1585 bool MachineConstEvaluator::evaluateSEXTr(const Register &R1, unsigned Width,
1586  unsigned Bits, const CellMap &Inputs, LatticeCell &Result) {
1587  assert(Inputs.has(R1.Reg));
1588  LatticeCell LS1;
1589  if (!getCell(R1, Inputs, LS1))
1590  return false;
1591  if (LS1.isBottom() || LS1.isProperty())
1592  return false;
1593 
1594  APInt A, XA;
1595  for (unsigned i = 0; i < LS1.size(); ++i) {
1596  bool Eval = constToInt(LS1.Values[i], A) &&
1597  evaluateSEXTi(A, Width, Bits, XA);
1598  if (!Eval)
1599  return false;
1600  const Constant *C = intToConst(XA);
1601  Result.add(C);
1602  }
1603  return true;
1604 }
1605 
1606 bool MachineConstEvaluator::evaluateSEXTi(const APInt &A1, unsigned Width,
1607  unsigned Bits, APInt &Result) {
1608  unsigned BW = A1.getBitWidth();
1609  assert(Width >= Bits && BW >= Bits);
1610  // Special case to make things faster for smaller source widths.
1611  // Sign extension of 0 bits generates 0 as a result. This is consistent
1612  // with what the HW does.
1613  if (Bits == 0) {
1614  Result = APInt(Width, 0);
1615  return true;
1616  }
1617  // In C, shifts by 64 invoke undefined behavior: handle that case in APInt.
1618  if (BW <= 64 && Bits != 0) {
1619  int64_t V = A1.getSExtValue();
1620  switch (Bits) {
1621  case 8:
1622  V = static_cast<int8_t>(V);
1623  break;
1624  case 16:
1625  V = static_cast<int16_t>(V);
1626  break;
1627  case 32:
1628  V = static_cast<int32_t>(V);
1629  break;
1630  default:
1631  // Shift left to lose all bits except lower "Bits" bits, then shift
1632  // the value back, replicating what was a sign bit after the first
1633  // shift.
1634  V = (V << (64-Bits)) >> (64-Bits);
1635  break;
1636  }
1637  // V is a 64-bit sign-extended value. Convert it to APInt of desired
1638  // width.
1639  Result = APInt(Width, V, true);
1640  return true;
1641  }
1642  // Slow case: the value doesn't fit in int64_t.
1643  if (Bits < BW)
1644  Result = A1.trunc(Bits).sext(Width);
1645  else // Bits == BW
1646  Result = A1.sext(Width);
1647  return true;
1648 }
1649 
1650 bool MachineConstEvaluator::evaluateCLBr(const Register &R1, bool Zeros,
1651  bool Ones, const CellMap &Inputs, LatticeCell &Result) {
1652  assert(Inputs.has(R1.Reg));
1653  LatticeCell LS1;
1654  if (!getCell(R1, Inputs, LS1))
1655  return false;
1656  if (LS1.isBottom() || LS1.isProperty())
1657  return false;
1658 
1659  APInt A, CA;
1660  for (unsigned i = 0; i < LS1.size(); ++i) {
1661  bool Eval = constToInt(LS1.Values[i], A) &&
1662  evaluateCLBi(A, Zeros, Ones, CA);
1663  if (!Eval)
1664  return false;
1665  const Constant *C = intToConst(CA);
1666  Result.add(C);
1667  }
1668  return true;
1669 }
1670 
1671 bool MachineConstEvaluator::evaluateCLBi(const APInt &A1, bool Zeros,
1672  bool Ones, APInt &Result) {
1673  unsigned BW = A1.getBitWidth();
1674  if (!Zeros && !Ones)
1675  return false;
1676  unsigned Count = 0;
1677  if (Zeros && (Count == 0))
1678  Count = A1.countLeadingZeros();
1679  if (Ones && (Count == 0))
1680  Count = A1.countLeadingOnes();
1681  Result = APInt(BW, static_cast<uint64_t>(Count), false);
1682  return true;
1683 }
1684 
1685 bool MachineConstEvaluator::evaluateCTBr(const Register &R1, bool Zeros,
1686  bool Ones, const CellMap &Inputs, LatticeCell &Result) {
1687  assert(Inputs.has(R1.Reg));
1688  LatticeCell LS1;
1689  if (!getCell(R1, Inputs, LS1))
1690  return false;
1691  if (LS1.isBottom() || LS1.isProperty())
1692  return false;
1693 
1694  APInt A, CA;
1695  for (unsigned i = 0; i < LS1.size(); ++i) {
1696  bool Eval = constToInt(LS1.Values[i], A) &&
1697  evaluateCTBi(A, Zeros, Ones, CA);
1698  if (!Eval)
1699  return false;
1700  const Constant *C = intToConst(CA);
1701  Result.add(C);
1702  }
1703  return true;
1704 }
1705 
1706 bool MachineConstEvaluator::evaluateCTBi(const APInt &A1, bool Zeros,
1707  bool Ones, APInt &Result) {
1708  unsigned BW = A1.getBitWidth();
1709  if (!Zeros && !Ones)
1710  return false;
1711  unsigned Count = 0;
1712  if (Zeros && (Count == 0))
1713  Count = A1.countTrailingZeros();
1714  if (Ones && (Count == 0))
1715  Count = A1.countTrailingOnes();
1716  Result = APInt(BW, static_cast<uint64_t>(Count), false);
1717  return true;
1718 }
1719 
1720 bool MachineConstEvaluator::evaluateEXTRACTr(const Register &R1,
1721  unsigned Width, unsigned Bits, unsigned Offset, bool Signed,
1722  const CellMap &Inputs, LatticeCell &Result) {
1723  assert(Inputs.has(R1.Reg));
1724  assert(Bits+Offset <= Width);
1725  LatticeCell LS1;
1726  if (!getCell(R1, Inputs, LS1))
1727  return false;
1728  if (LS1.isBottom())
1729  return false;
1730  if (LS1.isProperty()) {
1731  uint32_t Ps = LS1.properties();
1732  if (Ps & ConstantProperties::Zero) {
1733  const Constant *C = intToConst(APInt(Width, 0, false));
1734  Result.add(C);
1735  return true;
1736  }
1737  return false;
1738  }
1739 
1740  APInt A, CA;
1741  for (unsigned i = 0; i < LS1.size(); ++i) {
1742  bool Eval = constToInt(LS1.Values[i], A) &&
1743  evaluateEXTRACTi(A, Bits, Offset, Signed, CA);
1744  if (!Eval)
1745  return false;
1746  const Constant *C = intToConst(CA);
1747  Result.add(C);
1748  }
1749  return true;
1750 }
1751 
1752 bool MachineConstEvaluator::evaluateEXTRACTi(const APInt &A1, unsigned Bits,
1753  unsigned Offset, bool Signed, APInt &Result) {
1754  unsigned BW = A1.getBitWidth();
1755  assert(Bits+Offset <= BW);
1756  // Extracting 0 bits generates 0 as a result (as indicated by the HW people).
1757  if (Bits == 0) {
1758  Result = APInt(BW, 0);
1759  return true;
1760  }
1761  if (BW <= 64) {
1762  int64_t V = A1.getZExtValue();
1763  V <<= (64-Bits-Offset);
1764  if (Signed)
1765  V >>= (64-Bits);
1766  else
1767  V = static_cast<uint64_t>(V) >> (64-Bits);
1768  Result = APInt(BW, V, Signed);
1769  return true;
1770  }
1771  if (Signed)
1772  Result = A1.shl(BW-Bits-Offset).ashr(BW-Bits);
1773  else
1774  Result = A1.shl(BW-Bits-Offset).lshr(BW-Bits);
1775  return true;
1776 }
1777 
1778 bool MachineConstEvaluator::evaluateSplatr(const Register &R1,
1779  unsigned Bits, unsigned Count, const CellMap &Inputs,
1780  LatticeCell &Result) {
1781  assert(Inputs.has(R1.Reg));
1782  LatticeCell LS1;
1783  if (!getCell(R1, Inputs, LS1))
1784  return false;
1785  if (LS1.isBottom() || LS1.isProperty())
1786  return false;
1787 
1788  APInt A, SA;
1789  for (unsigned i = 0; i < LS1.size(); ++i) {
1790  bool Eval = constToInt(LS1.Values[i], A) &&
1791  evaluateSplati(A, Bits, Count, SA);
1792  if (!Eval)
1793  return false;
1794  const Constant *C = intToConst(SA);
1795  Result.add(C);
1796  }
1797  return true;
1798 }
1799 
1800 bool MachineConstEvaluator::evaluateSplati(const APInt &A1, unsigned Bits,
1801  unsigned Count, APInt &Result) {
1802  assert(Count > 0);
1803  unsigned BW = A1.getBitWidth(), SW = Count*Bits;
1804  APInt LoBits = (Bits < BW) ? A1.trunc(Bits) : A1.zextOrSelf(Bits);
1805  if (Count > 1)
1806  LoBits = LoBits.zext(SW);
1807 
1808  APInt Res(SW, 0, false);
1809  for (unsigned i = 0; i < Count; ++i) {
1810  Res <<= Bits;
1811  Res |= LoBits;
1812  }
1813  Result = Res;
1814  return true;
1815 }
1816 
1817 // ----------------------------------------------------------------------
1818 // Hexagon-specific code.
1819 
1820 namespace llvm {
1821 
1824 
1825 } // end namespace llvm
1826 
1827 namespace {
1828 
1829  class HexagonConstEvaluator : public MachineConstEvaluator {
1830  public:
1831  HexagonConstEvaluator(MachineFunction &Fn);
1832 
1833  bool evaluate(const MachineInstr &MI, const CellMap &Inputs,
1834  CellMap &Outputs) override;
1835  bool evaluate(const Register &R, const LatticeCell &SrcC,
1836  LatticeCell &Result) override;
1837  bool evaluate(const MachineInstr &BrI, const CellMap &Inputs,
1838  SetVector<const MachineBasicBlock*> &Targets, bool &FallsThru)
1839  override;
1840  bool rewrite(MachineInstr &MI, const CellMap &Inputs) override;
1841 
1842  private:
1843  unsigned getRegBitWidth(unsigned Reg) const;
1844 
1845  static uint32_t getCmp(unsigned Opc);
1846  static APInt getCmpImm(unsigned Opc, unsigned OpX,
1847  const MachineOperand &MO);
1848  void replaceWithNop(MachineInstr &MI);
1849 
1850  bool evaluateHexRSEQ32(Register RL, Register RH, const CellMap &Inputs,
1851  LatticeCell &Result);
1852  bool evaluateHexCompare(const MachineInstr &MI, const CellMap &Inputs,
1853  CellMap &Outputs);
1854  // This is suitable to be called for compare-and-jump instructions.
1855  bool evaluateHexCompare2(uint32_t Cmp, const MachineOperand &Src1,
1856  const MachineOperand &Src2, const CellMap &Inputs, bool &Result);
1857  bool evaluateHexLogical(const MachineInstr &MI, const CellMap &Inputs,
1858  CellMap &Outputs);
1859  bool evaluateHexCondMove(const MachineInstr &MI, const CellMap &Inputs,
1860  CellMap &Outputs);
1861  bool evaluateHexExt(const MachineInstr &MI, const CellMap &Inputs,
1862  CellMap &Outputs);
1863  bool evaluateHexVector1(const MachineInstr &MI, const CellMap &Inputs,
1864  CellMap &Outputs);
1865  bool evaluateHexVector2(const MachineInstr &MI, const CellMap &Inputs,
1866  CellMap &Outputs);
1867 
1868  void replaceAllRegUsesWith(unsigned FromReg, unsigned ToReg);
1869  bool rewriteHexBranch(MachineInstr &BrI, const CellMap &Inputs);
1870  bool rewriteHexConstDefs(MachineInstr &MI, const CellMap &Inputs,
1871  bool &AllDefs);
1872  bool rewriteHexConstUses(MachineInstr &MI, const CellMap &Inputs);
1873 
1875  const HexagonInstrInfo &HII;
1876  const HexagonRegisterInfo &HRI;
1877  };
1878 
1879  class HexagonConstPropagation : public MachineFunctionPass {
1880  public:
1881  static char ID;
1882 
1883  HexagonConstPropagation() : MachineFunctionPass(ID) {
1886  }
1887 
1888  StringRef getPassName() const override {
1889  return "Hexagon Constant Propagation";
1890  }
1891 
1892  bool runOnMachineFunction(MachineFunction &MF) override {
1893  const Function &F = MF.getFunction();
1894  if (skipFunction(F))
1895  return false;
1896 
1897  HexagonConstEvaluator HCE(MF);
1898  return MachineConstPropagator(HCE).run(MF);
1899  }
1900  };
1901 
1902 } // end anonymous namespace
1903 
1905 
1906 INITIALIZE_PASS(HexagonConstPropagation, "hcp", "Hexagon Constant Propagation",
1907  false, false)
1908 
1909 HexagonConstEvaluator::HexagonConstEvaluator(MachineFunction &Fn)
1910  : MachineConstEvaluator(Fn),
1911  HII(*Fn.getSubtarget<HexagonSubtarget>().getInstrInfo()),
1912  HRI(*Fn.getSubtarget<HexagonSubtarget>().getRegisterInfo()) {
1913  MRI = &Fn.getRegInfo();
1914 }
1915 
1916 bool HexagonConstEvaluator::evaluate(const MachineInstr &MI,
1917  const CellMap &Inputs, CellMap &Outputs) {
1918  if (MI.isCall())
1919  return false;
1920  if (MI.getNumOperands() == 0 || !MI.getOperand(0).isReg())
1921  return false;
1922  const MachineOperand &MD = MI.getOperand(0);
1923  if (!MD.isDef())
1924  return false;
1925 
1926  unsigned Opc = MI.getOpcode();
1927  Register DefR(MD);
1928  assert(!DefR.SubReg);
1930  return false;
1931 
1932  if (MI.isCopy()) {
1933  LatticeCell RC;
1934  Register SrcR(MI.getOperand(1));
1935  bool Eval = evaluateCOPY(SrcR, Inputs, RC);
1936  if (!Eval)
1937  return false;
1938  Outputs.update(DefR.Reg, RC);
1939  return true;
1940  }
1941  if (MI.isRegSequence()) {
1942  unsigned Sub1 = MI.getOperand(2).getImm();
1943  unsigned Sub2 = MI.getOperand(4).getImm();
1944  const TargetRegisterClass &DefRC = *MRI->getRegClass(DefR.Reg);
1945  unsigned SubLo = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_lo);
1946  unsigned SubHi = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_hi);
1947  if (Sub1 != SubLo && Sub1 != SubHi)
1948  return false;
1949  if (Sub2 != SubLo && Sub2 != SubHi)
1950  return false;
1951  assert(Sub1 != Sub2);
1952  bool LoIs1 = (Sub1 == SubLo);
1953  const MachineOperand &OpLo = LoIs1 ? MI.getOperand(1) : MI.getOperand(3);
1954  const MachineOperand &OpHi = LoIs1 ? MI.getOperand(3) : MI.getOperand(1);
1955  LatticeCell RC;
1956  Register SrcRL(OpLo), SrcRH(OpHi);
1957  bool Eval = evaluateHexRSEQ32(SrcRL, SrcRH, Inputs, RC);
1958  if (!Eval)
1959  return false;
1960  Outputs.update(DefR.Reg, RC);
1961  return true;
1962  }
1963  if (MI.isCompare()) {
1964  bool Eval = evaluateHexCompare(MI, Inputs, Outputs);
1965  return Eval;
1966  }
1967 
1968  switch (Opc) {
1969  default:
1970  return false;
1971  case Hexagon::A2_tfrsi:
1972  case Hexagon::A2_tfrpi:
1973  case Hexagon::CONST32:
1974  case Hexagon::CONST64:
1975  {
1976  const MachineOperand &VO = MI.getOperand(1);
1977  // The operand of CONST32 can be a blockaddress, e.g.
1978  // %0 = CONST32 <blockaddress(@eat, %l)>
1979  // Do this check for all instructions for safety.
1980  if (!VO.isImm())
1981  return false;
1982  int64_t V = MI.getOperand(1).getImm();
1983  unsigned W = getRegBitWidth(DefR.Reg);
1984  if (W != 32 && W != 64)
1985  return false;
1986  IntegerType *Ty = (W == 32) ? Type::getInt32Ty(CX)
1987  : Type::getInt64Ty(CX);
1988  const ConstantInt *CI = ConstantInt::get(Ty, V, true);
1989  LatticeCell RC = Outputs.get(DefR.Reg);
1990  RC.add(CI);
1991  Outputs.update(DefR.Reg, RC);
1992  break;
1993  }
1994 
1995  case Hexagon::PS_true:
1996  case Hexagon::PS_false:
1997  {
1998  LatticeCell RC = Outputs.get(DefR.Reg);
1999  bool NonZero = (Opc == Hexagon::PS_true);
2000  uint32_t P = NonZero ? ConstantProperties::NonZero
2001  : ConstantProperties::Zero;
2002  RC.add(P);
2003  Outputs.update(DefR.Reg, RC);
2004  break;
2005  }
2006 
2007  case Hexagon::A2_and:
2008  case Hexagon::A2_andir:
2009  case Hexagon::A2_andp:
2010  case Hexagon::A2_or:
2011  case Hexagon::A2_orir:
2012  case Hexagon::A2_orp:
2013  case Hexagon::A2_xor:
2014  case Hexagon::A2_xorp:
2015  {
2016  bool Eval = evaluateHexLogical(MI, Inputs, Outputs);
2017  if (!Eval)
2018  return false;
2019  break;
2020  }
2021 
2022  case Hexagon::A2_combineii: // combine(#s8Ext, #s8)
2023  case Hexagon::A4_combineii: // combine(#s8, #u6Ext)
2024  {
2025  uint64_t Hi = MI.getOperand(1).getImm();
2026  uint64_t Lo = MI.getOperand(2).getImm();
2027  uint64_t Res = (Hi << 32) | (Lo & 0xFFFFFFFF);
2028  IntegerType *Ty = Type::getInt64Ty(CX);
2029  const ConstantInt *CI = ConstantInt::get(Ty, Res, false);
2030  LatticeCell RC = Outputs.get(DefR.Reg);
2031  RC.add(CI);
2032  Outputs.update(DefR.Reg, RC);
2033  break;
2034  }
2035 
2036  case Hexagon::S2_setbit_i:
2037  {
2038  int64_t B = MI.getOperand(2).getImm();
2039  assert(B >=0 && B < 32);
2040  APInt A(32, (1ull << B), false);
2041  Register R(MI.getOperand(1));
2042  LatticeCell RC = Outputs.get(DefR.Reg);
2043  bool Eval = evaluateORri(R, A, Inputs, RC);
2044  if (!Eval)
2045  return false;
2046  Outputs.update(DefR.Reg, RC);
2047  break;
2048  }
2049 
2050  case Hexagon::C2_mux:
2051  case Hexagon::C2_muxir:
2052  case Hexagon::C2_muxri:
2053  case Hexagon::C2_muxii:
2054  {
2055  bool Eval = evaluateHexCondMove(MI, Inputs, Outputs);
2056  if (!Eval)
2057  return false;
2058  break;
2059  }
2060 
2061  case Hexagon::A2_sxtb:
2062  case Hexagon::A2_sxth:
2063  case Hexagon::A2_sxtw:
2064  case Hexagon::A2_zxtb:
2065  case Hexagon::A2_zxth:
2066  {
2067  bool Eval = evaluateHexExt(MI, Inputs, Outputs);
2068  if (!Eval)
2069  return false;
2070  break;
2071  }
2072 
2073  case Hexagon::S2_ct0:
2074  case Hexagon::S2_ct0p:
2075  case Hexagon::S2_ct1:
2076  case Hexagon::S2_ct1p:
2077  {
2078  using namespace Hexagon;
2079 
2080  bool Ones = (Opc == S2_ct1) || (Opc == S2_ct1p);
2081  Register R1(MI.getOperand(1));
2082  assert(Inputs.has(R1.Reg));
2083  LatticeCell T;
2084  bool Eval = evaluateCTBr(R1, !Ones, Ones, Inputs, T);
2085  if (!Eval)
2086  return false;
2087  // All of these instructions return a 32-bit value. The evaluate
2088  // will generate the same type as the operand, so truncate the
2089  // result if necessary.
2090  APInt C;
2091  LatticeCell RC = Outputs.get(DefR.Reg);
2092  for (unsigned i = 0; i < T.size(); ++i) {
2093  const Constant *CI = T.Values[i];
2094  if (constToInt(CI, C) && C.getBitWidth() > 32)
2095  CI = intToConst(C.trunc(32));
2096  RC.add(CI);
2097  }
2098  Outputs.update(DefR.Reg, RC);
2099  break;
2100  }
2101 
2102  case Hexagon::S2_cl0:
2103  case Hexagon::S2_cl0p:
2104  case Hexagon::S2_cl1:
2105  case Hexagon::S2_cl1p:
2106  case Hexagon::S2_clb:
2107  case Hexagon::S2_clbp:
2108  {
2109  using namespace Hexagon;
2110 
2111  bool OnlyZeros = (Opc == S2_cl0) || (Opc == S2_cl0p);
2112  bool OnlyOnes = (Opc == S2_cl1) || (Opc == S2_cl1p);
2113  Register R1(MI.getOperand(1));
2114  assert(Inputs.has(R1.Reg));
2115  LatticeCell T;
2116  bool Eval = evaluateCLBr(R1, !OnlyOnes, !OnlyZeros, Inputs, T);
2117  if (!Eval)
2118  return false;
2119  // All of these instructions return a 32-bit value. The evaluate
2120  // will generate the same type as the operand, so truncate the
2121  // result if necessary.
2122  APInt C;
2123  LatticeCell RC = Outputs.get(DefR.Reg);
2124  for (unsigned i = 0; i < T.size(); ++i) {
2125  const Constant *CI = T.Values[i];
2126  if (constToInt(CI, C) && C.getBitWidth() > 32)
2127  CI = intToConst(C.trunc(32));
2128  RC.add(CI);
2129  }
2130  Outputs.update(DefR.Reg, RC);
2131  break;
2132  }
2133 
2134  case Hexagon::S4_extract:
2135  case Hexagon::S4_extractp:
2136  case Hexagon::S2_extractu:
2137  case Hexagon::S2_extractup:
2138  {
2139  bool Signed = (Opc == Hexagon::S4_extract) ||
2140  (Opc == Hexagon::S4_extractp);
2141  Register R1(MI.getOperand(1));
2142  unsigned BW = getRegBitWidth(R1.Reg);
2143  unsigned Bits = MI.getOperand(2).getImm();
2144  unsigned Offset = MI.getOperand(3).getImm();
2145  LatticeCell RC = Outputs.get(DefR.Reg);
2146  if (Offset >= BW) {
2147  APInt Zero(BW, 0, false);
2148  RC.add(intToConst(Zero));
2149  break;
2150  }
2151  if (Offset+Bits > BW) {
2152  // If the requested bitfield extends beyond the most significant bit,
2153  // the extra bits are treated as 0s. To emulate this behavior, reduce
2154  // the number of requested bits, and make the extract unsigned.
2155  Bits = BW-Offset;
2156  Signed = false;
2157  }
2158  bool Eval = evaluateEXTRACTr(R1, BW, Bits, Offset, Signed, Inputs, RC);
2159  if (!Eval)
2160  return false;
2161  Outputs.update(DefR.Reg, RC);
2162  break;
2163  }
2164 
2165  case Hexagon::S2_vsplatrb:
2166  case Hexagon::S2_vsplatrh:
2167  // vabsh, vabsh:sat
2168  // vabsw, vabsw:sat
2169  // vconj:sat
2170  // vrndwh, vrndwh:sat
2171  // vsathb, vsathub, vsatwuh
2172  // vsxtbh, vsxthw
2173  // vtrunehb, vtrunohb
2174  // vzxtbh, vzxthw
2175  {
2176  bool Eval = evaluateHexVector1(MI, Inputs, Outputs);
2177  if (!Eval)
2178  return false;
2179  break;
2180  }
2181 
2182  // TODO:
2183  // A2_vaddh
2184  // A2_vaddhs
2185  // A2_vaddw
2186  // A2_vaddws
2187  }
2188 
2189  return true;
2190 }
2191 
2192 bool HexagonConstEvaluator::evaluate(const Register &R,
2193  const LatticeCell &Input, LatticeCell &Result) {
2194  if (!R.SubReg) {
2195  Result = Input;
2196  return true;
2197  }
2198  const TargetRegisterClass *RC = MRI->getRegClass(R.Reg);
2199  if (RC != &Hexagon::DoubleRegsRegClass)
2200  return false;
2201  if (R.SubReg != Hexagon::isub_lo && R.SubReg != Hexagon::isub_hi)
2202  return false;
2203 
2204  assert(!Input.isTop());
2205  if (Input.isBottom())
2206  return false;
2207 
2208  using P = ConstantProperties;
2209 
2210  if (Input.isProperty()) {
2211  uint32_t Ps = Input.properties();
2212  if (Ps & (P::Zero|P::NaN)) {
2213  uint32_t Ns = (Ps & (P::Zero|P::NaN|P::SignProperties));
2214  Result.add(Ns);
2215  return true;
2216  }
2217  if (R.SubReg == Hexagon::isub_hi) {
2218  uint32_t Ns = (Ps & P::SignProperties);
2219  Result.add(Ns);
2220  return true;
2221  }
2222  return false;
2223  }
2224 
2225  // The Input cell contains some known values. Pick the word corresponding
2226  // to the subregister.
2227  APInt A;
2228  for (unsigned i = 0; i < Input.size(); ++i) {
2229  const Constant *C = Input.Values[i];
2230  if (!constToInt(C, A))
2231  return false;
2232  if (!A.isIntN(64))
2233  return false;
2234  uint64_t U = A.getZExtValue();
2235  if (R.SubReg == Hexagon::isub_hi)
2236  U >>= 32;
2237  U &= 0xFFFFFFFFULL;
2238  uint32_t U32 = Lo_32(U);
2239  int32_t V32;
2240  memcpy(&V32, &U32, sizeof V32);
2241  IntegerType *Ty = Type::getInt32Ty(CX);
2242  const ConstantInt *C32 = ConstantInt::get(Ty, static_cast<int64_t>(V32));
2243  Result.add(C32);
2244  }
2245  return true;
2246 }
2247 
2248 bool HexagonConstEvaluator::evaluate(const MachineInstr &BrI,
2249  const CellMap &Inputs, SetVector<const MachineBasicBlock*> &Targets,
2250  bool &FallsThru) {
2251  // We need to evaluate one branch at a time. TII::analyzeBranch checks
2252  // all the branches in a basic block at once, so we cannot use it.
2253  unsigned Opc = BrI.getOpcode();
2254  bool SimpleBranch = false;
2255  bool Negated = false;
2256  switch (Opc) {
2257  case Hexagon::J2_jumpf:
2258  case Hexagon::J2_jumpfnew:
2259  case Hexagon::J2_jumpfnewpt:
2260  Negated = true;
2262  case Hexagon::J2_jumpt:
2263  case Hexagon::J2_jumptnew:
2264  case Hexagon::J2_jumptnewpt:
2265  // Simple branch: if([!]Pn) jump ...
2266  // i.e. Op0 = predicate, Op1 = branch target.
2267  SimpleBranch = true;
2268  break;
2269  case Hexagon::J2_jump:
2270  Targets.insert(BrI.getOperand(0).getMBB());
2271  FallsThru = false;
2272  return true;
2273  default:
2274 Undetermined:
2275  // If the branch is of unknown type, assume that all successors are
2276  // executable.
2277  FallsThru = !BrI.isUnconditionalBranch();
2278  return false;
2279  }
2280 
2281  if (SimpleBranch) {
2282  const MachineOperand &MD = BrI.getOperand(0);
2283  Register PR(MD);
2284  // If the condition operand has a subregister, this is not something
2285  // we currently recognize.
2286  if (PR.SubReg)
2287  goto Undetermined;
2288  assert(Inputs.has(PR.Reg));
2289  const LatticeCell &PredC = Inputs.get(PR.Reg);
2290  if (PredC.isBottom())
2291  goto Undetermined;
2292 
2293  uint32_t Props = PredC.properties();
2294  bool CTrue = false, CFalse = false;
2295  if (Props & ConstantProperties::Zero)
2296  CFalse = true;
2297  else if (Props & ConstantProperties::NonZero)
2298  CTrue = true;
2299  // If the condition is not known to be either, bail out.
2300  if (!CTrue && !CFalse)
2301  goto Undetermined;
2302 
2303  const MachineBasicBlock *BranchTarget = BrI.getOperand(1).getMBB();
2304 
2305  FallsThru = false;
2306  if ((!Negated && CTrue) || (Negated && CFalse))
2307  Targets.insert(BranchTarget);
2308  else if ((!Negated && CFalse) || (Negated && CTrue))
2309  FallsThru = true;
2310  else
2311  goto Undetermined;
2312  }
2313 
2314  return true;
2315 }
2316 
2317 bool HexagonConstEvaluator::rewrite(MachineInstr &MI, const CellMap &Inputs) {
2318  if (MI.isBranch())
2319  return rewriteHexBranch(MI, Inputs);
2320 
2321  unsigned Opc = MI.getOpcode();
2322  switch (Opc) {
2323  default:
2324  break;
2325  case Hexagon::A2_tfrsi:
2326  case Hexagon::A2_tfrpi:
2327  case Hexagon::CONST32:
2328  case Hexagon::CONST64:
2329  case Hexagon::PS_true:
2330  case Hexagon::PS_false:
2331  return false;
2332  }
2333 
2334  unsigned NumOp = MI.getNumOperands();
2335  if (NumOp == 0)
2336  return false;
2337 
2338  bool AllDefs, Changed;
2339  Changed = rewriteHexConstDefs(MI, Inputs, AllDefs);
2340  // If not all defs have been rewritten (i.e. the instruction defines
2341  // a register that is not compile-time constant), then try to rewrite
2342  // register operands that are known to be constant with immediates.
2343  if (!AllDefs)
2344  Changed |= rewriteHexConstUses(MI, Inputs);
2345 
2346  return Changed;
2347 }
2348 
2349 unsigned HexagonConstEvaluator::getRegBitWidth(unsigned Reg) const {
2350  const TargetRegisterClass *RC = MRI->getRegClass(Reg);
2351  if (Hexagon::IntRegsRegClass.hasSubClassEq(RC))
2352  return 32;
2353  if (Hexagon::DoubleRegsRegClass.hasSubClassEq(RC))
2354  return 64;
2355  if (Hexagon::PredRegsRegClass.hasSubClassEq(RC))
2356  return 8;
2357  llvm_unreachable("Invalid register");
2358  return 0;
2359 }
2360 
2362  switch (Opc) {
2363  case Hexagon::C2_cmpeq:
2364  case Hexagon::C2_cmpeqp:
2365  case Hexagon::A4_cmpbeq:
2366  case Hexagon::A4_cmpheq:
2367  case Hexagon::A4_cmpbeqi:
2368  case Hexagon::A4_cmpheqi:
2369  case Hexagon::C2_cmpeqi:
2370  case Hexagon::J4_cmpeqn1_t_jumpnv_nt:
2371  case Hexagon::J4_cmpeqn1_t_jumpnv_t:
2372  case Hexagon::J4_cmpeqi_t_jumpnv_nt:
2373  case Hexagon::J4_cmpeqi_t_jumpnv_t:
2374  case Hexagon::J4_cmpeq_t_jumpnv_nt:
2375  case Hexagon::J4_cmpeq_t_jumpnv_t:
2376  return Comparison::EQ;
2377 
2378  case Hexagon::C4_cmpneq:
2379  case Hexagon::C4_cmpneqi:
2380  case Hexagon::J4_cmpeqn1_f_jumpnv_nt:
2381  case Hexagon::J4_cmpeqn1_f_jumpnv_t:
2382  case Hexagon::J4_cmpeqi_f_jumpnv_nt:
2383  case Hexagon::J4_cmpeqi_f_jumpnv_t:
2384  case Hexagon::J4_cmpeq_f_jumpnv_nt:
2385  case Hexagon::J4_cmpeq_f_jumpnv_t:
2386  return Comparison::NE;
2387 
2388  case Hexagon::C2_cmpgt:
2389  case Hexagon::C2_cmpgtp:
2390  case Hexagon::A4_cmpbgt:
2391  case Hexagon::A4_cmphgt:
2392  case Hexagon::A4_cmpbgti:
2393  case Hexagon::A4_cmphgti:
2394  case Hexagon::C2_cmpgti:
2395  case Hexagon::J4_cmpgtn1_t_jumpnv_nt:
2396  case Hexagon::J4_cmpgtn1_t_jumpnv_t:
2397  case Hexagon::J4_cmpgti_t_jumpnv_nt:
2398  case Hexagon::J4_cmpgti_t_jumpnv_t:
2399  case Hexagon::J4_cmpgt_t_jumpnv_nt:
2400  case Hexagon::J4_cmpgt_t_jumpnv_t:
2401  return Comparison::GTs;
2402 
2403  case Hexagon::C4_cmplte:
2404  case Hexagon::C4_cmpltei:
2405  case Hexagon::J4_cmpgtn1_f_jumpnv_nt:
2406  case Hexagon::J4_cmpgtn1_f_jumpnv_t:
2407  case Hexagon::J4_cmpgti_f_jumpnv_nt:
2408  case Hexagon::J4_cmpgti_f_jumpnv_t:
2409  case Hexagon::J4_cmpgt_f_jumpnv_nt:
2410  case Hexagon::J4_cmpgt_f_jumpnv_t:
2411  return Comparison::LEs;
2412 
2413  case Hexagon::C2_cmpgtu:
2414  case Hexagon::C2_cmpgtup:
2415  case Hexagon::A4_cmpbgtu:
2416  case Hexagon::A4_cmpbgtui:
2417  case Hexagon::A4_cmphgtu:
2418  case Hexagon::A4_cmphgtui:
2419  case Hexagon::C2_cmpgtui:
2420  case Hexagon::J4_cmpgtui_t_jumpnv_nt:
2421  case Hexagon::J4_cmpgtui_t_jumpnv_t:
2422  case Hexagon::J4_cmpgtu_t_jumpnv_nt:
2423  case Hexagon::J4_cmpgtu_t_jumpnv_t:
2424  return Comparison::GTu;
2425 
2426  case Hexagon::J4_cmpltu_f_jumpnv_nt:
2427  case Hexagon::J4_cmpltu_f_jumpnv_t:
2428  return Comparison::GEu;
2429 
2430  case Hexagon::J4_cmpltu_t_jumpnv_nt:
2431  case Hexagon::J4_cmpltu_t_jumpnv_t:
2432  return Comparison::LTu;
2433 
2434  case Hexagon::J4_cmplt_f_jumpnv_nt:
2435  case Hexagon::J4_cmplt_f_jumpnv_t:
2436  return Comparison::GEs;
2437 
2438  case Hexagon::C4_cmplteu:
2439  case Hexagon::C4_cmplteui:
2440  case Hexagon::J4_cmpgtui_f_jumpnv_nt:
2441  case Hexagon::J4_cmpgtui_f_jumpnv_t:
2442  case Hexagon::J4_cmpgtu_f_jumpnv_nt:
2443  case Hexagon::J4_cmpgtu_f_jumpnv_t:
2444  return Comparison::LEu;
2445 
2446  case Hexagon::J4_cmplt_t_jumpnv_nt:
2447  case Hexagon::J4_cmplt_t_jumpnv_t:
2448  return Comparison::LTs;
2449 
2450  default:
2451  break;
2452  }
2453  return Comparison::Unk;
2454 }
2455 
2456 APInt HexagonConstEvaluator::getCmpImm(unsigned Opc, unsigned OpX,
2457  const MachineOperand &MO) {
2458  bool Signed = false;
2459  switch (Opc) {
2460  case Hexagon::A4_cmpbgtui: // u7
2461  case Hexagon::A4_cmphgtui: // u7
2462  break;
2463  case Hexagon::A4_cmpheqi: // s8
2464  case Hexagon::C4_cmpneqi: // s8
2465  Signed = true;
2466  case Hexagon::A4_cmpbeqi: // u8
2467  break;
2468  case Hexagon::C2_cmpgtui: // u9
2469  case Hexagon::C4_cmplteui: // u9
2470  break;
2471  case Hexagon::C2_cmpeqi: // s10
2472  case Hexagon::C2_cmpgti: // s10
2473  case Hexagon::C4_cmpltei: // s10
2474  Signed = true;
2475  break;
2476  case Hexagon::J4_cmpeqi_f_jumpnv_nt: // u5
2477  case Hexagon::J4_cmpeqi_f_jumpnv_t: // u5
2478  case Hexagon::J4_cmpeqi_t_jumpnv_nt: // u5
2479  case Hexagon::J4_cmpeqi_t_jumpnv_t: // u5
2480  case Hexagon::J4_cmpgti_f_jumpnv_nt: // u5
2481  case Hexagon::J4_cmpgti_f_jumpnv_t: // u5
2482  case Hexagon::J4_cmpgti_t_jumpnv_nt: // u5
2483  case Hexagon::J4_cmpgti_t_jumpnv_t: // u5
2484  case Hexagon::J4_cmpgtui_f_jumpnv_nt: // u5
2485  case Hexagon::J4_cmpgtui_f_jumpnv_t: // u5
2486  case Hexagon::J4_cmpgtui_t_jumpnv_nt: // u5
2487  case Hexagon::J4_cmpgtui_t_jumpnv_t: // u5
2488  break;
2489  default:
2490  llvm_unreachable("Unhandled instruction");
2491  break;
2492  }
2493 
2494  uint64_t Val = MO.getImm();
2495  return APInt(32, Val, Signed);
2496 }
2497 
2498 void HexagonConstEvaluator::replaceWithNop(MachineInstr &MI) {
2499  MI.setDesc(HII.get(Hexagon::A2_nop));
2500  while (MI.getNumOperands() > 0)
2501  MI.RemoveOperand(0);
2502 }
2503 
2504 bool HexagonConstEvaluator::evaluateHexRSEQ32(Register RL, Register RH,
2505  const CellMap &Inputs, LatticeCell &Result) {
2506  assert(Inputs.has(RL.Reg) && Inputs.has(RH.Reg));
2507  LatticeCell LSL, LSH;
2508  if (!getCell(RL, Inputs, LSL) || !getCell(RH, Inputs, LSH))
2509  return false;
2510  if (LSL.isProperty() || LSH.isProperty())
2511  return false;
2512 
2513  unsigned LN = LSL.size(), HN = LSH.size();
2514  SmallVector<APInt,4> LoVs(LN), HiVs(HN);
2515  for (unsigned i = 0; i < LN; ++i) {
2516  bool Eval = constToInt(LSL.Values[i], LoVs[i]);
2517  if (!Eval)
2518  return false;
2519  assert(LoVs[i].getBitWidth() == 32);
2520  }
2521  for (unsigned i = 0; i < HN; ++i) {
2522  bool Eval = constToInt(LSH.Values[i], HiVs[i]);
2523  if (!Eval)
2524  return false;
2525  assert(HiVs[i].getBitWidth() == 32);
2526  }
2527 
2528  for (unsigned i = 0; i < HiVs.size(); ++i) {
2529  APInt HV = HiVs[i].zextOrSelf(64) << 32;
2530  for (unsigned j = 0; j < LoVs.size(); ++j) {
2531  APInt LV = LoVs[j].zextOrSelf(64);
2532  const Constant *C = intToConst(HV | LV);
2533  Result.add(C);
2534  if (Result.isBottom())
2535  return false;
2536  }
2537  }
2538  return !Result.isBottom();
2539 }
2540 
2541 bool HexagonConstEvaluator::evaluateHexCompare(const MachineInstr &MI,
2542  const CellMap &Inputs, CellMap &Outputs) {
2543  unsigned Opc = MI.getOpcode();
2544  bool Classic = false;
2545  switch (Opc) {
2546  case Hexagon::C2_cmpeq:
2547  case Hexagon::C2_cmpeqp:
2548  case Hexagon::C2_cmpgt:
2549  case Hexagon::C2_cmpgtp:
2550  case Hexagon::C2_cmpgtu:
2551  case Hexagon::C2_cmpgtup:
2552  case Hexagon::C2_cmpeqi:
2553  case Hexagon::C2_cmpgti:
2554  case Hexagon::C2_cmpgtui:
2555  // Classic compare: Dst0 = CMP Src1, Src2
2556  Classic = true;
2557  break;
2558  default:
2559  // Not handling other compare instructions now.
2560  return false;
2561  }
2562 
2563  if (Classic) {
2564  const MachineOperand &Src1 = MI.getOperand(1);
2565  const MachineOperand &Src2 = MI.getOperand(2);
2566 
2567  bool Result;
2568  unsigned Opc = MI.getOpcode();
2569  bool Computed = evaluateHexCompare2(Opc, Src1, Src2, Inputs, Result);
2570  if (Computed) {
2571  // Only create a zero/non-zero cell. At this time there isn't really
2572  // much need for specific values.
2573  Register DefR(MI.getOperand(0));
2574  LatticeCell L = Outputs.get(DefR.Reg);
2575  uint32_t P = Result ? ConstantProperties::NonZero
2576  : ConstantProperties::Zero;
2577  L.add(P);
2578  Outputs.update(DefR.Reg, L);
2579  return true;
2580  }
2581  }
2582 
2583  return false;
2584 }
2585 
2586 bool HexagonConstEvaluator::evaluateHexCompare2(unsigned Opc,
2587  const MachineOperand &Src1, const MachineOperand &Src2,
2588  const CellMap &Inputs, bool &Result) {
2589  uint32_t Cmp = getCmp(Opc);
2590  bool Reg1 = Src1.isReg(), Reg2 = Src2.isReg();
2591  bool Imm1 = Src1.isImm(), Imm2 = Src2.isImm();
2592  if (Reg1) {
2593  Register R1(Src1);
2594  if (Reg2) {
2595  Register R2(Src2);
2596  return evaluateCMPrr(Cmp, R1, R2, Inputs, Result);
2597  } else if (Imm2) {
2598  APInt A2 = getCmpImm(Opc, 2, Src2);
2599  return evaluateCMPri(Cmp, R1, A2, Inputs, Result);
2600  }
2601  } else if (Imm1) {
2602  APInt A1 = getCmpImm(Opc, 1, Src1);
2603  if (Reg2) {
2604  Register R2(Src2);
2605  uint32_t NegCmp = Comparison::negate(Cmp);
2606  return evaluateCMPri(NegCmp, R2, A1, Inputs, Result);
2607  } else if (Imm2) {
2608  APInt A2 = getCmpImm(Opc, 2, Src2);
2609  return evaluateCMPii(Cmp, A1, A2, Result);
2610  }
2611  }
2612  // Unknown kind of comparison.
2613  return false;
2614 }
2615 
2616 bool HexagonConstEvaluator::evaluateHexLogical(const MachineInstr &MI,
2617  const CellMap &Inputs, CellMap &Outputs) {
2618  unsigned Opc = MI.getOpcode();
2619  if (MI.getNumOperands() != 3)
2620  return false;
2621  const MachineOperand &Src1 = MI.getOperand(1);
2622  const MachineOperand &Src2 = MI.getOperand(2);
2623  Register R1(Src1);
2624  bool Eval = false;
2625  LatticeCell RC;
2626  switch (Opc) {
2627  default:
2628  return false;
2629  case Hexagon::A2_and:
2630  case Hexagon::A2_andp:
2631  Eval = evaluateANDrr(R1, Register(Src2), Inputs, RC);
2632  break;
2633  case Hexagon::A2_andir: {
2634  APInt A(32, Src2.getImm(), true);
2635  Eval = evaluateANDri(R1, A, Inputs, RC);
2636  break;
2637  }
2638  case Hexagon::A2_or:
2639  case Hexagon::A2_orp:
2640  Eval = evaluateORrr(R1, Register(Src2), Inputs, RC);
2641  break;
2642  case Hexagon::A2_orir: {
2643  APInt A(32, Src2.getImm(), true);
2644  Eval = evaluateORri(R1, A, Inputs, RC);
2645  break;
2646  }
2647  case Hexagon::A2_xor:
2648  case Hexagon::A2_xorp:
2649  Eval = evaluateXORrr(R1, Register(Src2), Inputs, RC);
2650  break;
2651  }
2652  if (Eval) {
2653  Register DefR(MI.getOperand(0));
2654  Outputs.update(DefR.Reg, RC);
2655  }
2656  return Eval;
2657 }
2658 
2659 bool HexagonConstEvaluator::evaluateHexCondMove(const MachineInstr &MI,
2660  const CellMap &Inputs, CellMap &Outputs) {
2661  // Dst0 = Cond1 ? Src2 : Src3
2662  Register CR(MI.getOperand(1));
2663  assert(Inputs.has(CR.Reg));
2664  LatticeCell LS;
2665  if (!getCell(CR, Inputs, LS))
2666  return false;
2667  uint32_t Ps = LS.properties();
2668  unsigned TakeOp;
2669  if (Ps & ConstantProperties::Zero)
2670  TakeOp = 3;
2671  else if (Ps & ConstantProperties::NonZero)
2672  TakeOp = 2;
2673  else
2674  return false;
2675 
2676  const MachineOperand &ValOp = MI.getOperand(TakeOp);
2677  Register DefR(MI.getOperand(0));
2678  LatticeCell RC = Outputs.get(DefR.Reg);
2679 
2680  if (ValOp.isImm()) {
2681  int64_t V = ValOp.getImm();
2682  unsigned W = getRegBitWidth(DefR.Reg);
2683  APInt A(W, V, true);
2684  const Constant *C = intToConst(A);
2685  RC.add(C);
2686  Outputs.update(DefR.Reg, RC);
2687  return true;
2688  }
2689  if (ValOp.isReg()) {
2690  Register R(ValOp);
2691  const LatticeCell &LR = Inputs.get(R.Reg);
2692  LatticeCell LSR;
2693  if (!evaluate(R, LR, LSR))
2694  return false;
2695  RC.meet(LSR);
2696  Outputs.update(DefR.Reg, RC);
2697  return true;
2698  }
2699  return false;
2700 }
2701 
2702 bool HexagonConstEvaluator::evaluateHexExt(const MachineInstr &MI,
2703  const CellMap &Inputs, CellMap &Outputs) {
2704  // Dst0 = ext R1
2705  Register R1(MI.getOperand(1));
2706  assert(Inputs.has(R1.Reg));
2707 
2708  unsigned Opc = MI.getOpcode();
2709  unsigned Bits;
2710  switch (Opc) {
2711  case Hexagon::A2_sxtb:
2712  case Hexagon::A2_zxtb:
2713  Bits = 8;
2714  break;
2715  case Hexagon::A2_sxth:
2716  case Hexagon::A2_zxth:
2717  Bits = 16;
2718  break;
2719  case Hexagon::A2_sxtw:
2720  Bits = 32;
2721  break;
2722  }
2723 
2724  bool Signed = false;
2725  switch (Opc) {
2726  case Hexagon::A2_sxtb:
2727  case Hexagon::A2_sxth:
2728  case Hexagon::A2_sxtw:
2729  Signed = true;
2730  break;
2731  }
2732 
2733  Register DefR(MI.getOperand(0));
2734  unsigned BW = getRegBitWidth(DefR.Reg);
2735  LatticeCell RC = Outputs.get(DefR.Reg);
2736  bool Eval = Signed ? evaluateSEXTr(R1, BW, Bits, Inputs, RC)
2737  : evaluateZEXTr(R1, BW, Bits, Inputs, RC);
2738  if (!Eval)
2739  return false;
2740  Outputs.update(DefR.Reg, RC);
2741  return true;
2742 }
2743 
2744 bool HexagonConstEvaluator::evaluateHexVector1(const MachineInstr &MI,
2745  const CellMap &Inputs, CellMap &Outputs) {
2746  // DefR = op R1
2747  Register DefR(MI.getOperand(0));
2748  Register R1(MI.getOperand(1));
2749  assert(Inputs.has(R1.Reg));
2750  LatticeCell RC = Outputs.get(DefR.Reg);
2751  bool Eval;
2752 
2753  unsigned Opc = MI.getOpcode();
2754  switch (Opc) {
2755  case Hexagon::S2_vsplatrb:
2756  // Rd = 4 times Rs:0..7
2757  Eval = evaluateSplatr(R1, 8, 4, Inputs, RC);
2758  break;
2759  case Hexagon::S2_vsplatrh:
2760  // Rdd = 4 times Rs:0..15
2761  Eval = evaluateSplatr(R1, 16, 4, Inputs, RC);
2762  break;
2763  default:
2764  return false;
2765  }
2766 
2767  if (!Eval)
2768  return false;
2769  Outputs.update(DefR.Reg, RC);
2770  return true;
2771 }
2772 
2773 bool HexagonConstEvaluator::rewriteHexConstDefs(MachineInstr &MI,
2774  const CellMap &Inputs, bool &AllDefs) {
2775  AllDefs = false;
2776 
2777  // Some diagnostics.
2778  // DEBUG({...}) gets confused with all this code as an argument.
2779 #ifndef NDEBUG
2780  bool Debugging = DebugFlag && isCurrentDebugType(DEBUG_TYPE);
2781  if (Debugging) {
2782  bool Const = true, HasUse = false;
2783  for (const MachineOperand &MO : MI.operands()) {
2784  if (!MO.isReg() || !MO.isUse() || MO.isImplicit())
2785  continue;
2786  Register R(MO);
2788  continue;
2789  HasUse = true;
2790  // PHIs can legitimately have "top" cells after propagation.
2791  if (!MI.isPHI() && !Inputs.has(R.Reg)) {
2792  dbgs() << "Top " << printReg(R.Reg, &HRI, R.SubReg)
2793  << " in MI: " << MI;
2794  continue;
2795  }
2796  const LatticeCell &L = Inputs.get(R.Reg);
2797  Const &= L.isSingle();
2798  if (!Const)
2799  break;
2800  }
2801  if (HasUse && Const) {
2802  if (!MI.isCopy()) {
2803  dbgs() << "CONST: " << MI;
2804  for (const MachineOperand &MO : MI.operands()) {
2805  if (!MO.isReg() || !MO.isUse() || MO.isImplicit())
2806  continue;
2807  unsigned R = MO.getReg();
2808  dbgs() << printReg(R, &TRI) << ": " << Inputs.get(R) << "\n";
2809  }
2810  }
2811  }
2812  }
2813 #endif
2814 
2815  // Avoid generating TFRIs for register transfers---this will keep the
2816  // coalescing opportunities.
2817  if (MI.isCopy())
2818  return false;
2819 
2820  // Collect all virtual register-def operands.
2821  SmallVector<unsigned,2> DefRegs;
2822  for (const MachineOperand &MO : MI.operands()) {
2823  if (!MO.isReg() || !MO.isDef())
2824  continue;
2825  unsigned R = MO.getReg();
2827  continue;
2828  assert(!MO.getSubReg());
2829  assert(Inputs.has(R));
2830  DefRegs.push_back(R);
2831  }
2832 
2833  MachineBasicBlock &B = *MI.getParent();
2834  const DebugLoc &DL = MI.getDebugLoc();
2835  unsigned ChangedNum = 0;
2836 #ifndef NDEBUG
2838 #endif
2839 
2840  // For each defined register, if it is a constant, create an instruction
2841  // NewR = const
2842  // and replace all uses of the defined register with NewR.
2843  for (unsigned i = 0, n = DefRegs.size(); i < n; ++i) {
2844  unsigned R = DefRegs[i];
2845  const LatticeCell &L = Inputs.get(R);
2846  if (L.isBottom())
2847  continue;
2848  const TargetRegisterClass *RC = MRI->getRegClass(R);
2850 
2851  if (!L.isSingle()) {
2852  // If this a zero/non-zero cell, we can fold a definition
2853  // of a predicate register.
2854  using P = ConstantProperties;
2855 
2856  uint64_t Ps = L.properties();
2857  if (!(Ps & (P::Zero|P::NonZero)))
2858  continue;
2859  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
2860  if (RC != PredRC)
2861  continue;
2862  const MCInstrDesc *NewD = (Ps & P::Zero) ?
2863  &HII.get(Hexagon::PS_false) :
2864  &HII.get(Hexagon::PS_true);
2865  unsigned NewR = MRI->createVirtualRegister(PredRC);
2866  const MachineInstrBuilder &MIB = BuildMI(B, At, DL, *NewD, NewR);
2867  (void)MIB;
2868 #ifndef NDEBUG
2869  NewInstrs.push_back(&*MIB);
2870 #endif
2871  replaceAllRegUsesWith(R, NewR);
2872  } else {
2873  // This cell has a single value.
2874  APInt A;
2875  if (!constToInt(L.Value, A) || !A.isSignedIntN(64))
2876  continue;
2877  const TargetRegisterClass *NewRC;
2878  const MCInstrDesc *NewD;
2879 
2880  unsigned W = getRegBitWidth(R);
2881  int64_t V = A.getSExtValue();
2882  assert(W == 32 || W == 64);
2883  if (W == 32)
2884  NewRC = &Hexagon::IntRegsRegClass;
2885  else
2886  NewRC = &Hexagon::DoubleRegsRegClass;
2887  unsigned NewR = MRI->createVirtualRegister(NewRC);
2888  const MachineInstr *NewMI;
2889 
2890  if (W == 32) {
2891  NewD = &HII.get(Hexagon::A2_tfrsi);
2892  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2893  .addImm(V);
2894  } else {
2895  if (A.isSignedIntN(8)) {
2896  NewD = &HII.get(Hexagon::A2_tfrpi);
2897  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2898  .addImm(V);
2899  } else {
2900  int32_t Hi = V >> 32;
2901  int32_t Lo = V & 0xFFFFFFFFLL;
2902  if (isInt<8>(Hi) && isInt<8>(Lo)) {
2903  NewD = &HII.get(Hexagon::A2_combineii);
2904  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2905  .addImm(Hi)
2906  .addImm(Lo);
2907  } else {
2908  NewD = &HII.get(Hexagon::CONST64);
2909  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2910  .addImm(V);
2911  }
2912  }
2913  }
2914  (void)NewMI;
2915 #ifndef NDEBUG
2916  NewInstrs.push_back(NewMI);
2917 #endif
2918  replaceAllRegUsesWith(R, NewR);
2919  }
2920  ChangedNum++;
2921  }
2922 
2923  DEBUG({
2924  if (!NewInstrs.empty()) {
2925  MachineFunction &MF = *MI.getParent()->getParent();
2926  dbgs() << "In function: " << MF.getName() << "\n";
2927  dbgs() << "Rewrite: for " << MI << " created " << *NewInstrs[0];
2928  for (unsigned i = 1; i < NewInstrs.size(); ++i)
2929  dbgs() << " " << *NewInstrs[i];
2930  }
2931  });
2932 
2933  AllDefs = (ChangedNum == DefRegs.size());
2934  return ChangedNum > 0;
2935 }
2936 
2937 bool HexagonConstEvaluator::rewriteHexConstUses(MachineInstr &MI,
2938  const CellMap &Inputs) {
2939  bool Changed = false;
2940  unsigned Opc = MI.getOpcode();
2941  MachineBasicBlock &B = *MI.getParent();
2942  const DebugLoc &DL = MI.getDebugLoc();
2944  MachineInstr *NewMI = nullptr;
2945 
2946  switch (Opc) {
2947  case Hexagon::M2_maci:
2948  // Convert DefR += mpyi(R2, R3)
2949  // to DefR += mpyi(R, #imm),
2950  // or DefR -= mpyi(R, #imm).
2951  {
2952  Register DefR(MI.getOperand(0));
2953  assert(!DefR.SubReg);
2954  Register R2(MI.getOperand(2));
2955  Register R3(MI.getOperand(3));
2956  assert(Inputs.has(R2.Reg) && Inputs.has(R3.Reg));
2957  LatticeCell LS2, LS3;
2958  // It is enough to get one of the input cells, since we will only try
2959  // to replace one argument---whichever happens to be a single constant.
2960  bool HasC2 = getCell(R2, Inputs, LS2), HasC3 = getCell(R3, Inputs, LS3);
2961  if (!HasC2 && !HasC3)
2962  return false;
2963  bool Zero = ((HasC2 && (LS2.properties() & ConstantProperties::Zero)) ||
2964  (HasC3 && (LS3.properties() & ConstantProperties::Zero)));
2965  // If one of the operands is zero, eliminate the multiplication.
2966  if (Zero) {
2967  // DefR == R1 (tied operands).
2968  MachineOperand &Acc = MI.getOperand(1);
2969  Register R1(Acc);
2970  unsigned NewR = R1.Reg;
2971  if (R1.SubReg) {
2972  // Generate COPY. FIXME: Replace with the register:subregister.
2973  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
2974  NewR = MRI->createVirtualRegister(RC);
2975  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
2976  .addReg(R1.Reg, getRegState(Acc), R1.SubReg);
2977  }
2978  replaceAllRegUsesWith(DefR.Reg, NewR);
2979  MRI->clearKillFlags(NewR);
2980  Changed = true;
2981  break;
2982  }
2983 
2984  bool Swap = false;
2985  if (!LS3.isSingle()) {
2986  if (!LS2.isSingle())
2987  return false;
2988  Swap = true;
2989  }
2990  const LatticeCell &LI = Swap ? LS2 : LS3;
2991  const MachineOperand &OpR2 = Swap ? MI.getOperand(3)
2992  : MI.getOperand(2);
2993  // LI is single here.
2994  APInt A;
2995  if (!constToInt(LI.Value, A) || !A.isSignedIntN(8))
2996  return false;
2997  int64_t V = A.getSExtValue();
2998  const MCInstrDesc &D = (V >= 0) ? HII.get(Hexagon::M2_macsip)
2999  : HII.get(Hexagon::M2_macsin);
3000  if (V < 0)
3001  V = -V;
3002  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3003  unsigned NewR = MRI->createVirtualRegister(RC);
3004  const MachineOperand &Src1 = MI.getOperand(1);
3005  NewMI = BuildMI(B, At, DL, D, NewR)
3006  .addReg(Src1.getReg(), getRegState(Src1), Src1.getSubReg())
3007  .addReg(OpR2.getReg(), getRegState(OpR2), OpR2.getSubReg())
3008  .addImm(V);
3009  replaceAllRegUsesWith(DefR.Reg, NewR);
3010  Changed = true;
3011  break;
3012  }
3013 
3014  case Hexagon::A2_and:
3015  {
3016  Register R1(MI.getOperand(1));
3017  Register R2(MI.getOperand(2));
3018  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
3019  LatticeCell LS1, LS2;
3020  unsigned CopyOf = 0;
3021  // Check if any of the operands is -1 (i.e. all bits set).
3022  if (getCell(R1, Inputs, LS1) && LS1.isSingle()) {
3023  APInt M1;
3024  if (constToInt(LS1.Value, M1) && !~M1)
3025  CopyOf = 2;
3026  }
3027  else if (getCell(R2, Inputs, LS2) && LS2.isSingle()) {
3028  APInt M1;
3029  if (constToInt(LS2.Value, M1) && !~M1)
3030  CopyOf = 1;
3031  }
3032  if (!CopyOf)
3033  return false;
3034  MachineOperand &SO = MI.getOperand(CopyOf);
3035  Register SR(SO);
3036  Register DefR(MI.getOperand(0));
3037  unsigned NewR = SR.Reg;
3038  if (SR.SubReg) {
3039  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3040  NewR = MRI->createVirtualRegister(RC);
3041  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
3042  .addReg(SR.Reg, getRegState(SO), SR.SubReg);
3043  }
3044  replaceAllRegUsesWith(DefR.Reg, NewR);
3045  MRI->clearKillFlags(NewR);
3046  Changed = true;
3047  }
3048  break;
3049 
3050  case Hexagon::A2_or:
3051  {
3052  Register R1(MI.getOperand(1));
3053  Register R2(MI.getOperand(2));
3054  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
3055  LatticeCell LS1, LS2;
3056  unsigned CopyOf = 0;
3057 
3058  using P = ConstantProperties;
3059 
3060  if (getCell(R1, Inputs, LS1) && (LS1.properties() & P::Zero))
3061  CopyOf = 2;
3062  else if (getCell(R2, Inputs, LS2) && (LS2.properties() & P::Zero))
3063  CopyOf = 1;
3064  if (!CopyOf)
3065  return false;
3066  MachineOperand &SO = MI.getOperand(CopyOf);
3067  Register SR(SO);
3068  Register DefR(MI.getOperand(0));
3069  unsigned NewR = SR.Reg;
3070  if (SR.SubReg) {
3071  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3072  NewR = MRI->createVirtualRegister(RC);
3073  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
3074  .addReg(SR.Reg, getRegState(SO), SR.SubReg);
3075  }
3076  replaceAllRegUsesWith(DefR.Reg, NewR);
3077  MRI->clearKillFlags(NewR);
3078  Changed = true;
3079  }
3080  break;
3081  }
3082 
3083  if (NewMI) {
3084  // clear all the kill flags of this new instruction.
3085  for (MachineOperand &MO : NewMI->operands())
3086  if (MO.isReg() && MO.isUse())
3087  MO.setIsKill(false);
3088  }
3089 
3090  DEBUG({
3091  if (NewMI) {
3092  dbgs() << "Rewrite: for " << MI;
3093  if (NewMI != &MI)
3094  dbgs() << " created " << *NewMI;
3095  else
3096  dbgs() << " modified the instruction itself and created:" << *NewMI;
3097  }
3098  });
3099 
3100  return Changed;
3101 }
3102 
3103 void HexagonConstEvaluator::replaceAllRegUsesWith(unsigned FromReg,
3104  unsigned ToReg) {
3107  for (auto I = MRI->use_begin(FromReg), E = MRI->use_end(); I != E;) {
3108  MachineOperand &O = *I;
3109  ++I;
3110  O.setReg(ToReg);
3111  }
3112 }
3113 
3114 bool HexagonConstEvaluator::rewriteHexBranch(MachineInstr &BrI,
3115  const CellMap &Inputs) {
3116  MachineBasicBlock &B = *BrI.getParent();
3117  unsigned NumOp = BrI.getNumOperands();
3118  if (!NumOp)
3119  return false;
3120 
3121  bool FallsThru;
3123  bool Eval = evaluate(BrI, Inputs, Targets, FallsThru);
3124  unsigned NumTargets = Targets.size();
3125  if (!Eval || NumTargets > 1 || (NumTargets == 1 && FallsThru))
3126  return false;
3127  if (BrI.getOpcode() == Hexagon::J2_jump)
3128  return false;
3129 
3130  DEBUG(dbgs() << "Rewrite(" << printMBBReference(B) << "):" << BrI);
3131  bool Rewritten = false;
3132  if (NumTargets > 0) {
3133  assert(!FallsThru && "This should have been checked before");
3134  // MIB.addMBB needs non-const pointer.
3135  MachineBasicBlock *TargetB = const_cast<MachineBasicBlock*>(Targets[0]);
3136  bool Moot = B.isLayoutSuccessor(TargetB);
3137  if (!Moot) {
3138  // If we build a branch here, we must make sure that it won't be
3139  // erased as "non-executable". We can't mark any new instructions
3140  // as executable here, so we need to overwrite the BrI, which we
3141  // know is executable.
3142  const MCInstrDesc &JD = HII.get(Hexagon::J2_jump);
3143  auto NI = BuildMI(B, BrI.getIterator(), BrI.getDebugLoc(), JD)
3144  .addMBB(TargetB);
3145  BrI.setDesc(JD);
3146  while (BrI.getNumOperands() > 0)
3147  BrI.RemoveOperand(0);
3148  // This ensures that all implicit operands (e.g. implicit-def %r31, etc)
3149  // are present in the rewritten branch.
3150  for (auto &Op : NI->operands())
3151  BrI.addOperand(Op);
3152  NI->eraseFromParent();
3153  Rewritten = true;
3154  }
3155  }
3156 
3157  // Do not erase instructions. A newly created instruction could get
3158  // the same address as an instruction marked as executable during the
3159  // propagation.
3160  if (!Rewritten)
3161  replaceWithNop(BrI);
3162  return true;
3163 }
3164 
3166  return new HexagonConstPropagation();
3167 }
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:245
DILocation * get() const
Get the underlying DILocation.
Definition: DebugLoc.cpp:21
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:461
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:236
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:271
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:852
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:335
bool isPHI() const
Definition: MachineInstr.h:829
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...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
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:296
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:293
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
Definition: Path.cpp:236
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...
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:485
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
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:245
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:522
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:3499
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:860
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:819
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:862
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:559
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...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
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:507
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:142
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:60
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
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 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:298
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