LLVM  8.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  LLVM_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  LLVM_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  LLVM_DEBUG(dbgs() << " edge from " << printMBBReference(*PB) << ": "
662  << printReg(UseR.Reg, &MCE.TRI, UseR.SubReg) << SrcC
663  << '\n');
664  Changed |= Eval ? DefC.meet(SrcC)
665  : DefC.setBottom();
666  Cells.update(DefR.Reg, DefC);
667  if (DefC.isBottom())
668  break;
669  }
670  if (Changed)
671  visitUsesOf(DefR.Reg);
672 }
673 
674 void MachineConstPropagator::visitNonBranch(const MachineInstr &MI) {
675  LLVM_DEBUG(dbgs() << "Visiting MI(" << printMBBReference(*MI.getParent())
676  << "): " << MI);
677  CellMap Outputs;
678  bool Eval = MCE.evaluate(MI, Cells, Outputs);
679  LLVM_DEBUG({
680  if (Eval) {
681  dbgs() << " outputs:";
682  for (auto &I : Outputs)
683  dbgs() << ' ' << I.second;
684  dbgs() << '\n';
685  }
686  });
687 
688  // Update outputs. If the value was not computed, set all the
689  // def cells to bottom.
690  for (const MachineOperand &MO : MI.operands()) {
691  if (!MO.isReg() || !MO.isDef())
692  continue;
693  Register DefR(MO);
694  // Only track virtual registers.
696  continue;
697  bool Changed = false;
698  // If the evaluation failed, set cells for all output registers to bottom.
699  if (!Eval) {
700  const LatticeCell &T = Cells.get(DefR.Reg);
701  Changed = !T.isBottom();
702  Cells.update(DefR.Reg, Bottom);
703  } else {
704  // Find the corresponding cell in the computed outputs.
705  // If it's not there, go on to the next def.
706  if (!Outputs.has(DefR.Reg))
707  continue;
708  LatticeCell RC = Cells.get(DefR.Reg);
709  Changed = RC.meet(Outputs.get(DefR.Reg));
710  Cells.update(DefR.Reg, RC);
711  }
712  if (Changed)
713  visitUsesOf(DefR.Reg);
714  }
715 }
716 
717 // Starting at a given branch, visit remaining branches in the block.
718 // Traverse over the subsequent branches for as long as the preceding one
719 // can fall through. Add all the possible targets to the flow work queue,
720 // including the potential fall-through to the layout-successor block.
721 void MachineConstPropagator::visitBranchesFrom(const MachineInstr &BrI) {
722  const MachineBasicBlock &B = *BrI.getParent();
723  unsigned MBN = B.getNumber();
726 
728  bool EvalOk = true, FallsThru = true;
729  while (It != End) {
730  const MachineInstr &MI = *It;
731  InstrExec.insert(&MI);
732  LLVM_DEBUG(dbgs() << "Visiting " << (EvalOk ? "BR" : "br") << "("
733  << printMBBReference(B) << "): " << MI);
734  // Do not evaluate subsequent branches if the evaluation of any of the
735  // previous branches failed. Keep iterating over the branches only
736  // to mark them as executable.
737  EvalOk = EvalOk && MCE.evaluate(MI, Cells, Targets, FallsThru);
738  if (!EvalOk)
739  FallsThru = true;
740  if (!FallsThru)
741  break;
742  ++It;
743  }
744 
745  if (EvalOk) {
746  // Need to add all CFG successors that lead to EH landing pads.
747  // There won't be explicit branches to these blocks, but they must
748  // be processed.
749  for (const MachineBasicBlock *SB : B.successors()) {
750  if (SB->isEHPad())
751  Targets.insert(SB);
752  }
753  if (FallsThru) {
754  const MachineFunction &MF = *B.getParent();
756  MachineFunction::const_iterator Next = std::next(BI);
757  if (Next != MF.end())
758  Targets.insert(&*Next);
759  }
760  } else {
761  // If the evaluation of the branches failed, make "Targets" to be the
762  // set of all successors of the block from the CFG.
763  // If the evaluation succeeded for all visited branches, then if the
764  // last one set "FallsThru", then add an edge to the layout successor
765  // to the targets.
766  Targets.clear();
767  LLVM_DEBUG(dbgs() << " failed to evaluate a branch...adding all CFG "
768  "successors\n");
769  for (const MachineBasicBlock *SB : B.successors())
770  Targets.insert(SB);
771  }
772 
773  for (const MachineBasicBlock *TB : Targets) {
774  unsigned TBN = TB->getNumber();
775  LLVM_DEBUG(dbgs() << " pushing edge " << printMBBReference(B) << " -> "
776  << printMBBReference(*TB) << "\n");
777  FlowQ.push(CFGEdge(MBN, TBN));
778  }
779 }
780 
781 void MachineConstPropagator::visitUsesOf(unsigned Reg) {
782  LLVM_DEBUG(dbgs() << "Visiting uses of " << printReg(Reg, &MCE.TRI)
783  << Cells.get(Reg) << '\n');
784  for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
785  // Do not process non-executable instructions. They can become exceutable
786  // later (via a flow-edge in the work queue). In such case, the instruc-
787  // tion will be visited at that time.
788  if (!InstrExec.count(&MI))
789  continue;
790  if (MI.isPHI())
791  visitPHI(MI);
792  else if (!MI.isBranch())
793  visitNonBranch(MI);
794  else
795  visitBranchesFrom(MI);
796  }
797 }
798 
799 bool MachineConstPropagator::computeBlockSuccessors(const MachineBasicBlock *MB,
801  MachineBasicBlock::const_iterator FirstBr = MB->end();
802  for (const MachineInstr &MI : *MB) {
803  if (MI.isDebugInstr())
804  continue;
805  if (MI.isBranch()) {
806  FirstBr = MI.getIterator();
807  break;
808  }
809  }
810 
811  Targets.clear();
812  MachineBasicBlock::const_iterator End = MB->end();
813 
814  bool DoNext = true;
815  for (MachineBasicBlock::const_iterator I = FirstBr; I != End; ++I) {
816  const MachineInstr &MI = *I;
817  // Can there be debug instructions between branches?
818  if (MI.isDebugInstr())
819  continue;
820  if (!InstrExec.count(&MI))
821  continue;
822  bool Eval = MCE.evaluate(MI, Cells, Targets, DoNext);
823  if (!Eval)
824  return false;
825  if (!DoNext)
826  break;
827  }
828  // If the last branch could fall-through, add block's layout successor.
829  if (DoNext) {
830  MachineFunction::const_iterator BI = MB->getIterator();
831  MachineFunction::const_iterator NextI = std::next(BI);
832  if (NextI != MB->getParent()->end())
833  Targets.insert(&*NextI);
834  }
835 
836  // Add all the EH landing pads.
837  for (const MachineBasicBlock *SB : MB->successors())
838  if (SB->isEHPad())
839  Targets.insert(SB);
840 
841  return true;
842 }
843 
844 void MachineConstPropagator::removeCFGEdge(MachineBasicBlock *From,
845  MachineBasicBlock *To) {
846  // First, remove the CFG successor/predecessor information.
847  From->removeSuccessor(To);
848  // Remove all corresponding PHI operands in the To block.
849  for (auto I = To->begin(), E = To->getFirstNonPHI(); I != E; ++I) {
850  MachineInstr *PN = &*I;
851  // reg0 = PHI reg1, bb2, reg3, bb4, ...
852  int N = PN->getNumOperands()-2;
853  while (N > 0) {
854  if (PN->getOperand(N+1).getMBB() == From) {
855  PN->RemoveOperand(N+1);
856  PN->RemoveOperand(N);
857  }
858  N -= 2;
859  }
860  }
861 }
862 
865  unsigned EntryNum = Entry->getNumber();
866 
867  // Start with a fake edge, just to process the entry node.
868  FlowQ.push(CFGEdge(EntryNum, EntryNum));
869 
870  while (!FlowQ.empty()) {
871  CFGEdge Edge = FlowQ.front();
872  FlowQ.pop();
873 
874  LLVM_DEBUG(
875  dbgs() << "Picked edge "
876  << printMBBReference(*MF.getBlockNumbered(Edge.first)) << "->"
877  << printMBBReference(*MF.getBlockNumbered(Edge.second)) << '\n');
878  if (Edge.first != EntryNum)
879  if (EdgeExec.count(Edge))
880  continue;
881  EdgeExec.insert(Edge);
882  MachineBasicBlock *SB = MF.getBlockNumbered(Edge.second);
883 
884  // Process the block in three stages:
885  // - visit all PHI nodes,
886  // - visit all non-branch instructions,
887  // - visit block branches.
888  MachineBasicBlock::const_iterator It = SB->begin(), End = SB->end();
889 
890  // Visit PHI nodes in the successor block.
891  while (It != End && It->isPHI()) {
892  InstrExec.insert(&*It);
893  visitPHI(*It);
894  ++It;
895  }
896 
897  // If the successor block just became executable, visit all instructions.
898  // To see if this is the first time we're visiting it, check the first
899  // non-debug instruction to see if it is executable.
900  while (It != End && It->isDebugInstr())
901  ++It;
902  assert(It == End || !It->isPHI());
903  // If this block has been visited, go on to the next one.
904  if (It != End && InstrExec.count(&*It))
905  continue;
906  // For now, scan all non-branch instructions. Branches require different
907  // processing.
908  while (It != End && !It->isBranch()) {
909  if (!It->isDebugInstr()) {
910  InstrExec.insert(&*It);
911  visitNonBranch(*It);
912  }
913  ++It;
914  }
915 
916  // Time to process the end of the block. This is different from
917  // processing regular (non-branch) instructions, because there can
918  // be multiple branches in a block, and they can cause the block to
919  // terminate early.
920  if (It != End) {
921  visitBranchesFrom(*It);
922  } else {
923  // If the block didn't have a branch, add all successor edges to the
924  // work queue. (There should really be only one successor in such case.)
925  unsigned SBN = SB->getNumber();
926  for (const MachineBasicBlock *SSB : SB->successors())
927  FlowQ.push(CFGEdge(SBN, SSB->getNumber()));
928  }
929  } // while (FlowQ)
930 
931  LLVM_DEBUG({
932  dbgs() << "Cells after propagation:\n";
933  Cells.print(dbgs(), MCE.TRI);
934  dbgs() << "Dead CFG edges:\n";
935  for (const MachineBasicBlock &B : MF) {
936  unsigned BN = B.getNumber();
937  for (const MachineBasicBlock *SB : B.successors()) {
938  unsigned SN = SB->getNumber();
939  if (!EdgeExec.count(CFGEdge(BN, SN)))
940  dbgs() << " " << printMBBReference(B) << " -> "
941  << printMBBReference(*SB) << '\n';
942  }
943  }
944  });
945 }
946 
947 bool MachineConstPropagator::rewrite(MachineFunction &MF) {
948  bool Changed = false;
949  // Rewrite all instructions based on the collected cell information.
950  //
951  // Traverse the instructions in a post-order, so that rewriting an
952  // instruction can make changes "downstream" in terms of control-flow
953  // without affecting the rewriting process. (We should not change
954  // instructions that have not yet been visited by the rewriter.)
955  // The reason for this is that the rewriter can introduce new vregs,
956  // and replace uses of old vregs (which had corresponding cells
957  // computed during propagation) with these new vregs (which at this
958  // point would not have any cells, and would appear to be "top").
959  // If an attempt was made to evaluate an instruction with a fresh
960  // "top" vreg, it would cause an error (abend) in the evaluator.
961 
962  // Collect the post-order-traversal block ordering. The subsequent
963  // traversal/rewrite will update block successors, so it's safer
964  // if the visiting order it computed ahead of time.
965  std::vector<MachineBasicBlock*> POT;
966  for (MachineBasicBlock *B : post_order(&MF))
967  if (!B->empty())
968  POT.push_back(B);
969 
970  for (MachineBasicBlock *B : POT) {
971  // Walk the block backwards (which usually begin with the branches).
972  // If any branch is rewritten, we may need to update the successor
973  // information for this block. Unless the block's successors can be
974  // precisely determined (which may not be the case for indirect
975  // branches), we cannot modify any branch.
976 
977  // Compute the successor information.
979  bool HaveTargets = computeBlockSuccessors(B, Targets);
980  // Rewrite the executable instructions. Skip branches if we don't
981  // have block successor information.
982  for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) {
983  MachineInstr &MI = *I;
984  if (InstrExec.count(&MI)) {
985  if (MI.isBranch() && !HaveTargets)
986  continue;
987  Changed |= MCE.rewrite(MI, Cells);
988  }
989  }
990  // The rewriting could rewrite PHI nodes to non-PHI nodes, causing
991  // regular instructions to appear in between PHI nodes. Bring all
992  // the PHI nodes to the beginning of the block.
993  for (auto I = B->begin(), E = B->end(); I != E; ++I) {
994  if (I->isPHI())
995  continue;
996  // I is not PHI. Find the next PHI node P.
997  auto P = I;
998  while (++P != E)
999  if (P->isPHI())
1000  break;
1001  // Not found.
1002  if (P == E)
1003  break;
1004  // Splice P right before I.
1005  B->splice(I, B, P);
1006  // Reset I to point at the just spliced PHI node.
1007  --I;
1008  }
1009  // Update the block successor information: remove unnecessary successors.
1010  if (HaveTargets) {
1012  for (MachineBasicBlock *SB : B->successors()) {
1013  if (!Targets.count(SB))
1014  ToRemove.push_back(const_cast<MachineBasicBlock*>(SB));
1015  Targets.remove(SB);
1016  }
1017  for (unsigned i = 0, n = ToRemove.size(); i < n; ++i)
1018  removeCFGEdge(B, ToRemove[i]);
1019  // If there are any blocks left in the computed targets, it means that
1020  // we think that the block could go somewhere, but the CFG does not.
1021  // This could legitimately happen in blocks that have non-returning
1022  // calls---we would think that the execution can continue, but the
1023  // CFG will not have a successor edge.
1024  }
1025  }
1026  // Need to do some final post-processing.
1027  // If a branch was not executable, it will not get rewritten, but should
1028  // be removed (or replaced with something equivalent to a A2_nop). We can't
1029  // erase instructions during rewriting, so this needs to be delayed until
1030  // now.
1031  for (MachineBasicBlock &B : MF) {
1032  MachineBasicBlock::iterator I = B.begin(), E = B.end();
1033  while (I != E) {
1034  auto Next = std::next(I);
1035  if (I->isBranch() && !InstrExec.count(&*I))
1036  B.erase(I);
1037  I = Next;
1038  }
1039  }
1040  return Changed;
1041 }
1042 
1043 // This is the constant propagation algorithm as described by Wegman-Zadeck.
1044 // Most of the terminology comes from there.
1045 bool MachineConstPropagator::run(MachineFunction &MF) {
1046  LLVM_DEBUG(MF.print(dbgs() << "Starting MachineConstPropagator\n", nullptr));
1047 
1048  MRI = &MF.getRegInfo();
1049 
1050  Cells.clear();
1051  EdgeExec.clear();
1052  InstrExec.clear();
1053  assert(FlowQ.empty());
1054 
1055  propagate(MF);
1056  bool Changed = rewrite(MF);
1057 
1058  LLVM_DEBUG({
1059  dbgs() << "End of MachineConstPropagator (Changed=" << Changed << ")\n";
1060  if (Changed)
1061  MF.print(dbgs(), nullptr);
1062  });
1063  return Changed;
1064 }
1065 
1066 // --------------------------------------------------------------------
1067 // Machine const evaluator.
1068 
1069 bool MachineConstEvaluator::getCell(const Register &R, const CellMap &Inputs,
1070  LatticeCell &RC) {
1072  return false;
1073  const LatticeCell &L = Inputs.get(R.Reg);
1074  if (!R.SubReg) {
1075  RC = L;
1076  return !RC.isBottom();
1077  }
1078  bool Eval = evaluate(R, L, RC);
1079  return Eval && !RC.isBottom();
1080 }
1081 
1082 bool MachineConstEvaluator::constToInt(const Constant *C,
1083  APInt &Val) const {
1084  const ConstantInt *CI = dyn_cast<ConstantInt>(C);
1085  if (!CI)
1086  return false;
1087  Val = CI->getValue();
1088  return true;
1089 }
1090 
1091 const ConstantInt *MachineConstEvaluator::intToConst(const APInt &Val) const {
1092  return ConstantInt::get(CX, Val);
1093 }
1094 
1095 bool MachineConstEvaluator::evaluateCMPrr(uint32_t Cmp, const Register &R1,
1096  const Register &R2, const CellMap &Inputs, bool &Result) {
1097  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1098  LatticeCell LS1, LS2;
1099  if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2))
1100  return false;
1101 
1102  bool IsProp1 = LS1.isProperty();
1103  bool IsProp2 = LS2.isProperty();
1104  if (IsProp1) {
1105  uint32_t Prop1 = LS1.properties();
1106  if (IsProp2)
1107  return evaluateCMPpp(Cmp, Prop1, LS2.properties(), Result);
1108  uint32_t NegCmp = Comparison::negate(Cmp);
1109  return evaluateCMPrp(NegCmp, R2, Prop1, Inputs, Result);
1110  }
1111  if (IsProp2) {
1112  uint32_t Prop2 = LS2.properties();
1113  return evaluateCMPrp(Cmp, R1, Prop2, Inputs, Result);
1114  }
1115 
1116  APInt A;
1117  bool IsTrue = true, IsFalse = true;
1118  for (unsigned i = 0; i < LS2.size(); ++i) {
1119  bool Res;
1120  bool Computed = constToInt(LS2.Values[i], A) &&
1121  evaluateCMPri(Cmp, R1, A, Inputs, Res);
1122  if (!Computed)
1123  return false;
1124  IsTrue &= Res;
1125  IsFalse &= !Res;
1126  }
1127  assert(!IsTrue || !IsFalse);
1128  // The actual logical value of the comparison is same as IsTrue.
1129  Result = IsTrue;
1130  // Return true if the result was proven to be true or proven to be false.
1131  return IsTrue || IsFalse;
1132 }
1133 
1134 bool MachineConstEvaluator::evaluateCMPri(uint32_t Cmp, const Register &R1,
1135  const APInt &A2, const CellMap &Inputs, bool &Result) {
1136  assert(Inputs.has(R1.Reg));
1137  LatticeCell LS;
1138  if (!getCell(R1, Inputs, LS))
1139  return false;
1140  if (LS.isProperty())
1141  return evaluateCMPpi(Cmp, LS.properties(), A2, Result);
1142 
1143  APInt A;
1144  bool IsTrue = true, IsFalse = true;
1145  for (unsigned i = 0; i < LS.size(); ++i) {
1146  bool Res;
1147  bool Computed = constToInt(LS.Values[i], A) &&
1148  evaluateCMPii(Cmp, A, A2, Res);
1149  if (!Computed)
1150  return false;
1151  IsTrue &= Res;
1152  IsFalse &= !Res;
1153  }
1154  assert(!IsTrue || !IsFalse);
1155  // The actual logical value of the comparison is same as IsTrue.
1156  Result = IsTrue;
1157  // Return true if the result was proven to be true or proven to be false.
1158  return IsTrue || IsFalse;
1159 }
1160 
1161 bool MachineConstEvaluator::evaluateCMPrp(uint32_t Cmp, const Register &R1,
1162  uint64_t Props2, const CellMap &Inputs, bool &Result) {
1163  assert(Inputs.has(R1.Reg));
1164  LatticeCell LS;
1165  if (!getCell(R1, Inputs, LS))
1166  return false;
1167  if (LS.isProperty())
1168  return evaluateCMPpp(Cmp, LS.properties(), Props2, Result);
1169 
1170  APInt A;
1171  uint32_t NegCmp = Comparison::negate(Cmp);
1172  bool IsTrue = true, IsFalse = true;
1173  for (unsigned i = 0; i < LS.size(); ++i) {
1174  bool Res;
1175  bool Computed = constToInt(LS.Values[i], A) &&
1176  evaluateCMPpi(NegCmp, Props2, A, Res);
1177  if (!Computed)
1178  return false;
1179  IsTrue &= Res;
1180  IsFalse &= !Res;
1181  }
1182  assert(!IsTrue || !IsFalse);
1183  Result = IsTrue;
1184  return IsTrue || IsFalse;
1185 }
1186 
1187 bool MachineConstEvaluator::evaluateCMPii(uint32_t Cmp, const APInt &A1,
1188  const APInt &A2, bool &Result) {
1189  // NE is a special kind of comparison (not composed of smaller properties).
1190  if (Cmp == Comparison::NE) {
1191  Result = !APInt::isSameValue(A1, A2);
1192  return true;
1193  }
1194  if (Cmp == Comparison::EQ) {
1195  Result = APInt::isSameValue(A1, A2);
1196  return true;
1197  }
1198  if (Cmp & Comparison::EQ) {
1199  if (APInt::isSameValue(A1, A2))
1200  return (Result = true);
1201  }
1202  assert((Cmp & (Comparison::L | Comparison::G)) && "Malformed comparison");
1203  Result = false;
1204 
1205  unsigned W1 = A1.getBitWidth();
1206  unsigned W2 = A2.getBitWidth();
1207  unsigned MaxW = (W1 >= W2) ? W1 : W2;
1208  if (Cmp & Comparison::U) {
1209  const APInt Zx1 = A1.zextOrSelf(MaxW);
1210  const APInt Zx2 = A2.zextOrSelf(MaxW);
1211  if (Cmp & Comparison::L)
1212  Result = Zx1.ult(Zx2);
1213  else if (Cmp & Comparison::G)
1214  Result = Zx2.ult(Zx1);
1215  return true;
1216  }
1217 
1218  // Signed comparison.
1219  const APInt Sx1 = A1.sextOrSelf(MaxW);
1220  const APInt Sx2 = A2.sextOrSelf(MaxW);
1221  if (Cmp & Comparison::L)
1222  Result = Sx1.slt(Sx2);
1223  else if (Cmp & Comparison::G)
1224  Result = Sx2.slt(Sx1);
1225  return true;
1226 }
1227 
1228 bool MachineConstEvaluator::evaluateCMPpi(uint32_t Cmp, uint32_t Props,
1229  const APInt &A2, bool &Result) {
1230  if (Props == ConstantProperties::Unknown)
1231  return false;
1232 
1233  // Should never see NaN here, but check for it for completeness.
1234  if (Props & ConstantProperties::NaN)
1235  return false;
1236  // Infinity could theoretically be compared to a number, but the
1237  // presence of infinity here would be very suspicious. If we don't
1238  // know for sure that the number is finite, bail out.
1239  if (!(Props & ConstantProperties::Finite))
1240  return false;
1241 
1242  // Let X be a number that has properties Props.
1243 
1244  if (Cmp & Comparison::U) {
1245  // In case of unsigned comparisons, we can only compare against 0.
1246  if (A2 == 0) {
1247  // Any x!=0 will be considered >0 in an unsigned comparison.
1248  if (Props & ConstantProperties::Zero)
1249  Result = (Cmp & Comparison::EQ);
1250  else if (Props & ConstantProperties::NonZero)
1251  Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE);
1252  else
1253  return false;
1254  return true;
1255  }
1256  // A2 is not zero. The only handled case is if X = 0.
1257  if (Props & ConstantProperties::Zero) {
1258  Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE);
1259  return true;
1260  }
1261  return false;
1262  }
1263 
1264  // Signed comparisons are different.
1265  if (Props & ConstantProperties::Zero) {
1266  if (A2 == 0)
1267  Result = (Cmp & Comparison::EQ);
1268  else
1269  Result = (Cmp == Comparison::NE) ||
1270  ((Cmp & Comparison::L) && !A2.isNegative()) ||
1271  ((Cmp & Comparison::G) && A2.isNegative());
1272  return true;
1273  }
1274  if (Props & ConstantProperties::PosOrZero) {
1275  // X >= 0 and !(A2 < 0) => cannot compare
1276  if (!A2.isNegative())
1277  return false;
1278  // X >= 0 and A2 < 0
1279  Result = (Cmp & Comparison::G) || (Cmp == Comparison::NE);
1280  return true;
1281  }
1282  if (Props & ConstantProperties::NegOrZero) {
1283  // X <= 0 and Src1 < 0 => cannot compare
1284  if (A2 == 0 || A2.isNegative())
1285  return false;
1286  // X <= 0 and A2 > 0
1287  Result = (Cmp & Comparison::L) || (Cmp == Comparison::NE);
1288  return true;
1289  }
1290 
1291  return false;
1292 }
1293 
1294 bool MachineConstEvaluator::evaluateCMPpp(uint32_t Cmp, uint32_t Props1,
1295  uint32_t Props2, bool &Result) {
1296  using P = ConstantProperties;
1297 
1298  if ((Props1 & P::NaN) && (Props2 & P::NaN))
1299  return false;
1300  if (!(Props1 & P::Finite) || !(Props2 & P::Finite))
1301  return false;
1302 
1303  bool Zero1 = (Props1 & P::Zero), Zero2 = (Props2 & P::Zero);
1304  bool NonZero1 = (Props1 & P::NonZero), NonZero2 = (Props2 & P::NonZero);
1305  if (Zero1 && Zero2) {
1306  Result = (Cmp & Comparison::EQ);
1307  return true;
1308  }
1309  if (Cmp == Comparison::NE) {
1310  if ((Zero1 && NonZero2) || (NonZero1 && Zero2))
1311  return (Result = true);
1312  return false;
1313  }
1314 
1315  if (Cmp & Comparison::U) {
1316  // In unsigned comparisons, we can only compare against a known zero,
1317  // or a known non-zero.
1318  if (Zero1 && NonZero2) {
1319  Result = (Cmp & Comparison::L);
1320  return true;
1321  }
1322  if (NonZero1 && Zero2) {
1323  Result = (Cmp & Comparison::G);
1324  return true;
1325  }
1326  return false;
1327  }
1328 
1329  // Signed comparison. The comparison is not NE.
1330  bool Poz1 = (Props1 & P::PosOrZero), Poz2 = (Props2 & P::PosOrZero);
1331  bool Nez1 = (Props1 & P::NegOrZero), Nez2 = (Props2 & P::NegOrZero);
1332  if (Nez1 && Poz2) {
1333  if (NonZero1 || NonZero2) {
1334  Result = (Cmp & Comparison::L);
1335  return true;
1336  }
1337  // Either (or both) could be zero. Can only say that X <= Y.
1338  if ((Cmp & Comparison::EQ) && (Cmp & Comparison::L))
1339  return (Result = true);
1340  }
1341  if (Poz1 && Nez2) {
1342  if (NonZero1 || NonZero2) {
1343  Result = (Cmp & Comparison::G);
1344  return true;
1345  }
1346  // Either (or both) could be zero. Can only say that X >= Y.
1347  if ((Cmp & Comparison::EQ) && (Cmp & Comparison::G))
1348  return (Result = true);
1349  }
1350 
1351  return false;
1352 }
1353 
1354 bool MachineConstEvaluator::evaluateCOPY(const Register &R1,
1355  const CellMap &Inputs, LatticeCell &Result) {
1356  return getCell(R1, Inputs, Result);
1357 }
1358 
1359 bool MachineConstEvaluator::evaluateANDrr(const Register &R1,
1360  const Register &R2, const CellMap &Inputs, LatticeCell &Result) {
1361  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1362  const LatticeCell &L1 = Inputs.get(R2.Reg);
1363  const LatticeCell &L2 = Inputs.get(R2.Reg);
1364  // If both sources are bottom, exit. Otherwise try to evaluate ANDri
1365  // with the non-bottom argument passed as the immediate. This is to
1366  // catch cases of ANDing with 0.
1367  if (L2.isBottom()) {
1368  if (L1.isBottom())
1369  return false;
1370  return evaluateANDrr(R2, R1, Inputs, Result);
1371  }
1372  LatticeCell LS2;
1373  if (!evaluate(R2, L2, LS2))
1374  return false;
1375  if (LS2.isBottom() || LS2.isProperty())
1376  return false;
1377 
1378  APInt A;
1379  for (unsigned i = 0; i < LS2.size(); ++i) {
1380  LatticeCell RC;
1381  bool Eval = constToInt(LS2.Values[i], A) &&
1382  evaluateANDri(R1, A, Inputs, RC);
1383  if (!Eval)
1384  return false;
1385  Result.meet(RC);
1386  }
1387  return !Result.isBottom();
1388 }
1389 
1390 bool MachineConstEvaluator::evaluateANDri(const Register &R1,
1391  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1392  assert(Inputs.has(R1.Reg));
1393  if (A2 == -1)
1394  return getCell(R1, Inputs, Result);
1395  if (A2 == 0) {
1396  LatticeCell RC;
1397  RC.add(intToConst(A2));
1398  // Overwrite Result.
1399  Result = RC;
1400  return true;
1401  }
1402  LatticeCell LS1;
1403  if (!getCell(R1, Inputs, LS1))
1404  return false;
1405  if (LS1.isBottom() || LS1.isProperty())
1406  return false;
1407 
1408  APInt A, ResA;
1409  for (unsigned i = 0; i < LS1.size(); ++i) {
1410  bool Eval = constToInt(LS1.Values[i], A) &&
1411  evaluateANDii(A, A2, ResA);
1412  if (!Eval)
1413  return false;
1414  const Constant *C = intToConst(ResA);
1415  Result.add(C);
1416  }
1417  return !Result.isBottom();
1418 }
1419 
1420 bool MachineConstEvaluator::evaluateANDii(const APInt &A1,
1421  const APInt &A2, APInt &Result) {
1422  Result = A1 & A2;
1423  return true;
1424 }
1425 
1426 bool MachineConstEvaluator::evaluateORrr(const Register &R1,
1427  const Register &R2, const CellMap &Inputs, LatticeCell &Result) {
1428  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1429  const LatticeCell &L1 = Inputs.get(R2.Reg);
1430  const LatticeCell &L2 = Inputs.get(R2.Reg);
1431  // If both sources are bottom, exit. Otherwise try to evaluate ORri
1432  // with the non-bottom argument passed as the immediate. This is to
1433  // catch cases of ORing with -1.
1434  if (L2.isBottom()) {
1435  if (L1.isBottom())
1436  return false;
1437  return evaluateORrr(R2, R1, Inputs, Result);
1438  }
1439  LatticeCell LS2;
1440  if (!evaluate(R2, L2, LS2))
1441  return false;
1442  if (LS2.isBottom() || LS2.isProperty())
1443  return false;
1444 
1445  APInt A;
1446  for (unsigned i = 0; i < LS2.size(); ++i) {
1447  LatticeCell RC;
1448  bool Eval = constToInt(LS2.Values[i], A) &&
1449  evaluateORri(R1, A, Inputs, RC);
1450  if (!Eval)
1451  return false;
1452  Result.meet(RC);
1453  }
1454  return !Result.isBottom();
1455 }
1456 
1457 bool MachineConstEvaluator::evaluateORri(const Register &R1,
1458  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1459  assert(Inputs.has(R1.Reg));
1460  if (A2 == 0)
1461  return getCell(R1, Inputs, Result);
1462  if (A2 == -1) {
1463  LatticeCell RC;
1464  RC.add(intToConst(A2));
1465  // Overwrite Result.
1466  Result = RC;
1467  return true;
1468  }
1469  LatticeCell LS1;
1470  if (!getCell(R1, Inputs, LS1))
1471  return false;
1472  if (LS1.isBottom() || LS1.isProperty())
1473  return false;
1474 
1475  APInt A, ResA;
1476  for (unsigned i = 0; i < LS1.size(); ++i) {
1477  bool Eval = constToInt(LS1.Values[i], A) &&
1478  evaluateORii(A, A2, ResA);
1479  if (!Eval)
1480  return false;
1481  const Constant *C = intToConst(ResA);
1482  Result.add(C);
1483  }
1484  return !Result.isBottom();
1485 }
1486 
1487 bool MachineConstEvaluator::evaluateORii(const APInt &A1,
1488  const APInt &A2, APInt &Result) {
1489  Result = A1 | A2;
1490  return true;
1491 }
1492 
1493 bool MachineConstEvaluator::evaluateXORrr(const Register &R1,
1494  const Register &R2, const CellMap &Inputs, LatticeCell &Result) {
1495  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
1496  LatticeCell LS1, LS2;
1497  if (!getCell(R1, Inputs, LS1) || !getCell(R2, Inputs, LS2))
1498  return false;
1499  if (LS1.isProperty()) {
1500  if (LS1.properties() & ConstantProperties::Zero)
1501  return !(Result = LS2).isBottom();
1502  return false;
1503  }
1504  if (LS2.isProperty()) {
1505  if (LS2.properties() & ConstantProperties::Zero)
1506  return !(Result = LS1).isBottom();
1507  return false;
1508  }
1509 
1510  APInt A;
1511  for (unsigned i = 0; i < LS2.size(); ++i) {
1512  LatticeCell RC;
1513  bool Eval = constToInt(LS2.Values[i], A) &&
1514  evaluateXORri(R1, A, Inputs, RC);
1515  if (!Eval)
1516  return false;
1517  Result.meet(RC);
1518  }
1519  return !Result.isBottom();
1520 }
1521 
1522 bool MachineConstEvaluator::evaluateXORri(const Register &R1,
1523  const APInt &A2, const CellMap &Inputs, LatticeCell &Result) {
1524  assert(Inputs.has(R1.Reg));
1525  LatticeCell LS1;
1526  if (!getCell(R1, Inputs, LS1))
1527  return false;
1528  if (LS1.isProperty()) {
1529  if (LS1.properties() & ConstantProperties::Zero) {
1530  const Constant *C = intToConst(A2);
1531  Result.add(C);
1532  return !Result.isBottom();
1533  }
1534  return false;
1535  }
1536 
1537  APInt A, XA;
1538  for (unsigned i = 0; i < LS1.size(); ++i) {
1539  bool Eval = constToInt(LS1.Values[i], A) &&
1540  evaluateXORii(A, A2, XA);
1541  if (!Eval)
1542  return false;
1543  const Constant *C = intToConst(XA);
1544  Result.add(C);
1545  }
1546  return !Result.isBottom();
1547 }
1548 
1549 bool MachineConstEvaluator::evaluateXORii(const APInt &A1,
1550  const APInt &A2, APInt &Result) {
1551  Result = A1 ^ A2;
1552  return true;
1553 }
1554 
1555 bool MachineConstEvaluator::evaluateZEXTr(const Register &R1, unsigned Width,
1556  unsigned Bits, const CellMap &Inputs, LatticeCell &Result) {
1557  assert(Inputs.has(R1.Reg));
1558  LatticeCell LS1;
1559  if (!getCell(R1, Inputs, LS1))
1560  return false;
1561  if (LS1.isProperty())
1562  return false;
1563 
1564  APInt A, XA;
1565  for (unsigned i = 0; i < LS1.size(); ++i) {
1566  bool Eval = constToInt(LS1.Values[i], A) &&
1567  evaluateZEXTi(A, Width, Bits, XA);
1568  if (!Eval)
1569  return false;
1570  const Constant *C = intToConst(XA);
1571  Result.add(C);
1572  }
1573  return true;
1574 }
1575 
1576 bool MachineConstEvaluator::evaluateZEXTi(const APInt &A1, unsigned Width,
1577  unsigned Bits, APInt &Result) {
1578  unsigned BW = A1.getBitWidth();
1579  (void)BW;
1580  assert(Width >= Bits && BW >= Bits);
1581  APInt Mask = APInt::getLowBitsSet(Width, Bits);
1582  Result = A1.zextOrTrunc(Width) & Mask;
1583  return true;
1584 }
1585 
1586 bool MachineConstEvaluator::evaluateSEXTr(const Register &R1, unsigned Width,
1587  unsigned Bits, const CellMap &Inputs, LatticeCell &Result) {
1588  assert(Inputs.has(R1.Reg));
1589  LatticeCell LS1;
1590  if (!getCell(R1, Inputs, LS1))
1591  return false;
1592  if (LS1.isBottom() || LS1.isProperty())
1593  return false;
1594 
1595  APInt A, XA;
1596  for (unsigned i = 0; i < LS1.size(); ++i) {
1597  bool Eval = constToInt(LS1.Values[i], A) &&
1598  evaluateSEXTi(A, Width, Bits, XA);
1599  if (!Eval)
1600  return false;
1601  const Constant *C = intToConst(XA);
1602  Result.add(C);
1603  }
1604  return true;
1605 }
1606 
1607 bool MachineConstEvaluator::evaluateSEXTi(const APInt &A1, unsigned Width,
1608  unsigned Bits, APInt &Result) {
1609  unsigned BW = A1.getBitWidth();
1610  assert(Width >= Bits && BW >= Bits);
1611  // Special case to make things faster for smaller source widths.
1612  // Sign extension of 0 bits generates 0 as a result. This is consistent
1613  // with what the HW does.
1614  if (Bits == 0) {
1615  Result = APInt(Width, 0);
1616  return true;
1617  }
1618  // In C, shifts by 64 invoke undefined behavior: handle that case in APInt.
1619  if (BW <= 64 && Bits != 0) {
1620  int64_t V = A1.getSExtValue();
1621  switch (Bits) {
1622  case 8:
1623  V = static_cast<int8_t>(V);
1624  break;
1625  case 16:
1626  V = static_cast<int16_t>(V);
1627  break;
1628  case 32:
1629  V = static_cast<int32_t>(V);
1630  break;
1631  default:
1632  // Shift left to lose all bits except lower "Bits" bits, then shift
1633  // the value back, replicating what was a sign bit after the first
1634  // shift.
1635  V = (V << (64-Bits)) >> (64-Bits);
1636  break;
1637  }
1638  // V is a 64-bit sign-extended value. Convert it to APInt of desired
1639  // width.
1640  Result = APInt(Width, V, true);
1641  return true;
1642  }
1643  // Slow case: the value doesn't fit in int64_t.
1644  if (Bits < BW)
1645  Result = A1.trunc(Bits).sext(Width);
1646  else // Bits == BW
1647  Result = A1.sext(Width);
1648  return true;
1649 }
1650 
1651 bool MachineConstEvaluator::evaluateCLBr(const Register &R1, bool Zeros,
1652  bool Ones, const CellMap &Inputs, LatticeCell &Result) {
1653  assert(Inputs.has(R1.Reg));
1654  LatticeCell LS1;
1655  if (!getCell(R1, Inputs, LS1))
1656  return false;
1657  if (LS1.isBottom() || LS1.isProperty())
1658  return false;
1659 
1660  APInt A, CA;
1661  for (unsigned i = 0; i < LS1.size(); ++i) {
1662  bool Eval = constToInt(LS1.Values[i], A) &&
1663  evaluateCLBi(A, Zeros, Ones, CA);
1664  if (!Eval)
1665  return false;
1666  const Constant *C = intToConst(CA);
1667  Result.add(C);
1668  }
1669  return true;
1670 }
1671 
1672 bool MachineConstEvaluator::evaluateCLBi(const APInt &A1, bool Zeros,
1673  bool Ones, APInt &Result) {
1674  unsigned BW = A1.getBitWidth();
1675  if (!Zeros && !Ones)
1676  return false;
1677  unsigned Count = 0;
1678  if (Zeros && (Count == 0))
1679  Count = A1.countLeadingZeros();
1680  if (Ones && (Count == 0))
1681  Count = A1.countLeadingOnes();
1682  Result = APInt(BW, static_cast<uint64_t>(Count), false);
1683  return true;
1684 }
1685 
1686 bool MachineConstEvaluator::evaluateCTBr(const Register &R1, bool Zeros,
1687  bool Ones, const CellMap &Inputs, LatticeCell &Result) {
1688  assert(Inputs.has(R1.Reg));
1689  LatticeCell LS1;
1690  if (!getCell(R1, Inputs, LS1))
1691  return false;
1692  if (LS1.isBottom() || LS1.isProperty())
1693  return false;
1694 
1695  APInt A, CA;
1696  for (unsigned i = 0; i < LS1.size(); ++i) {
1697  bool Eval = constToInt(LS1.Values[i], A) &&
1698  evaluateCTBi(A, Zeros, Ones, CA);
1699  if (!Eval)
1700  return false;
1701  const Constant *C = intToConst(CA);
1702  Result.add(C);
1703  }
1704  return true;
1705 }
1706 
1707 bool MachineConstEvaluator::evaluateCTBi(const APInt &A1, bool Zeros,
1708  bool Ones, APInt &Result) {
1709  unsigned BW = A1.getBitWidth();
1710  if (!Zeros && !Ones)
1711  return false;
1712  unsigned Count = 0;
1713  if (Zeros && (Count == 0))
1714  Count = A1.countTrailingZeros();
1715  if (Ones && (Count == 0))
1716  Count = A1.countTrailingOnes();
1717  Result = APInt(BW, static_cast<uint64_t>(Count), false);
1718  return true;
1719 }
1720 
1721 bool MachineConstEvaluator::evaluateEXTRACTr(const Register &R1,
1722  unsigned Width, unsigned Bits, unsigned Offset, bool Signed,
1723  const CellMap &Inputs, LatticeCell &Result) {
1724  assert(Inputs.has(R1.Reg));
1725  assert(Bits+Offset <= Width);
1726  LatticeCell LS1;
1727  if (!getCell(R1, Inputs, LS1))
1728  return false;
1729  if (LS1.isBottom())
1730  return false;
1731  if (LS1.isProperty()) {
1732  uint32_t Ps = LS1.properties();
1733  if (Ps & ConstantProperties::Zero) {
1734  const Constant *C = intToConst(APInt(Width, 0, false));
1735  Result.add(C);
1736  return true;
1737  }
1738  return false;
1739  }
1740 
1741  APInt A, CA;
1742  for (unsigned i = 0; i < LS1.size(); ++i) {
1743  bool Eval = constToInt(LS1.Values[i], A) &&
1744  evaluateEXTRACTi(A, Bits, Offset, Signed, CA);
1745  if (!Eval)
1746  return false;
1747  const Constant *C = intToConst(CA);
1748  Result.add(C);
1749  }
1750  return true;
1751 }
1752 
1753 bool MachineConstEvaluator::evaluateEXTRACTi(const APInt &A1, unsigned Bits,
1754  unsigned Offset, bool Signed, APInt &Result) {
1755  unsigned BW = A1.getBitWidth();
1756  assert(Bits+Offset <= BW);
1757  // Extracting 0 bits generates 0 as a result (as indicated by the HW people).
1758  if (Bits == 0) {
1759  Result = APInt(BW, 0);
1760  return true;
1761  }
1762  if (BW <= 64) {
1763  int64_t V = A1.getZExtValue();
1764  V <<= (64-Bits-Offset);
1765  if (Signed)
1766  V >>= (64-Bits);
1767  else
1768  V = static_cast<uint64_t>(V) >> (64-Bits);
1769  Result = APInt(BW, V, Signed);
1770  return true;
1771  }
1772  if (Signed)
1773  Result = A1.shl(BW-Bits-Offset).ashr(BW-Bits);
1774  else
1775  Result = A1.shl(BW-Bits-Offset).lshr(BW-Bits);
1776  return true;
1777 }
1778 
1779 bool MachineConstEvaluator::evaluateSplatr(const Register &R1,
1780  unsigned Bits, unsigned Count, const CellMap &Inputs,
1781  LatticeCell &Result) {
1782  assert(Inputs.has(R1.Reg));
1783  LatticeCell LS1;
1784  if (!getCell(R1, Inputs, LS1))
1785  return false;
1786  if (LS1.isBottom() || LS1.isProperty())
1787  return false;
1788 
1789  APInt A, SA;
1790  for (unsigned i = 0; i < LS1.size(); ++i) {
1791  bool Eval = constToInt(LS1.Values[i], A) &&
1792  evaluateSplati(A, Bits, Count, SA);
1793  if (!Eval)
1794  return false;
1795  const Constant *C = intToConst(SA);
1796  Result.add(C);
1797  }
1798  return true;
1799 }
1800 
1801 bool MachineConstEvaluator::evaluateSplati(const APInt &A1, unsigned Bits,
1802  unsigned Count, APInt &Result) {
1803  assert(Count > 0);
1804  unsigned BW = A1.getBitWidth(), SW = Count*Bits;
1805  APInt LoBits = (Bits < BW) ? A1.trunc(Bits) : A1.zextOrSelf(Bits);
1806  if (Count > 1)
1807  LoBits = LoBits.zext(SW);
1808 
1809  APInt Res(SW, 0, false);
1810  for (unsigned i = 0; i < Count; ++i) {
1811  Res <<= Bits;
1812  Res |= LoBits;
1813  }
1814  Result = Res;
1815  return true;
1816 }
1817 
1818 // ----------------------------------------------------------------------
1819 // Hexagon-specific code.
1820 
1821 namespace llvm {
1822 
1825 
1826 } // end namespace llvm
1827 
1828 namespace {
1829 
1830  class HexagonConstEvaluator : public MachineConstEvaluator {
1831  public:
1832  HexagonConstEvaluator(MachineFunction &Fn);
1833 
1834  bool evaluate(const MachineInstr &MI, const CellMap &Inputs,
1835  CellMap &Outputs) override;
1836  bool evaluate(const Register &R, const LatticeCell &SrcC,
1837  LatticeCell &Result) override;
1838  bool evaluate(const MachineInstr &BrI, const CellMap &Inputs,
1839  SetVector<const MachineBasicBlock*> &Targets, bool &FallsThru)
1840  override;
1841  bool rewrite(MachineInstr &MI, const CellMap &Inputs) override;
1842 
1843  private:
1844  unsigned getRegBitWidth(unsigned Reg) const;
1845 
1846  static uint32_t getCmp(unsigned Opc);
1847  static APInt getCmpImm(unsigned Opc, unsigned OpX,
1848  const MachineOperand &MO);
1849  void replaceWithNop(MachineInstr &MI);
1850 
1851  bool evaluateHexRSEQ32(Register RL, Register RH, const CellMap &Inputs,
1852  LatticeCell &Result);
1853  bool evaluateHexCompare(const MachineInstr &MI, const CellMap &Inputs,
1854  CellMap &Outputs);
1855  // This is suitable to be called for compare-and-jump instructions.
1856  bool evaluateHexCompare2(uint32_t Cmp, const MachineOperand &Src1,
1857  const MachineOperand &Src2, const CellMap &Inputs, bool &Result);
1858  bool evaluateHexLogical(const MachineInstr &MI, const CellMap &Inputs,
1859  CellMap &Outputs);
1860  bool evaluateHexCondMove(const MachineInstr &MI, const CellMap &Inputs,
1861  CellMap &Outputs);
1862  bool evaluateHexExt(const MachineInstr &MI, const CellMap &Inputs,
1863  CellMap &Outputs);
1864  bool evaluateHexVector1(const MachineInstr &MI, const CellMap &Inputs,
1865  CellMap &Outputs);
1866  bool evaluateHexVector2(const MachineInstr &MI, const CellMap &Inputs,
1867  CellMap &Outputs);
1868 
1869  void replaceAllRegUsesWith(unsigned FromReg, unsigned ToReg);
1870  bool rewriteHexBranch(MachineInstr &BrI, const CellMap &Inputs);
1871  bool rewriteHexConstDefs(MachineInstr &MI, const CellMap &Inputs,
1872  bool &AllDefs);
1873  bool rewriteHexConstUses(MachineInstr &MI, const CellMap &Inputs);
1874 
1876  const HexagonInstrInfo &HII;
1877  const HexagonRegisterInfo &HRI;
1878  };
1879 
1880  class HexagonConstPropagation : public MachineFunctionPass {
1881  public:
1882  static char ID;
1883 
1884  HexagonConstPropagation() : MachineFunctionPass(ID) {}
1885 
1886  StringRef getPassName() const override {
1887  return "Hexagon Constant Propagation";
1888  }
1889 
1890  bool runOnMachineFunction(MachineFunction &MF) override {
1891  const Function &F = MF.getFunction();
1892  if (skipFunction(F))
1893  return false;
1894 
1895  HexagonConstEvaluator HCE(MF);
1896  return MachineConstPropagator(HCE).run(MF);
1897  }
1898  };
1899 
1900 } // end anonymous namespace
1901 
1903 
1904 INITIALIZE_PASS(HexagonConstPropagation, "hexagon-constp",
1905  "Hexagon Constant Propagation", false, false)
1906 
1907 HexagonConstEvaluator::HexagonConstEvaluator(MachineFunction &Fn)
1908  : MachineConstEvaluator(Fn),
1909  HII(*Fn.getSubtarget<HexagonSubtarget>().getInstrInfo()),
1910  HRI(*Fn.getSubtarget<HexagonSubtarget>().getRegisterInfo()) {
1911  MRI = &Fn.getRegInfo();
1912 }
1913 
1914 bool HexagonConstEvaluator::evaluate(const MachineInstr &MI,
1915  const CellMap &Inputs, CellMap &Outputs) {
1916  if (MI.isCall())
1917  return false;
1918  if (MI.getNumOperands() == 0 || !MI.getOperand(0).isReg())
1919  return false;
1920  const MachineOperand &MD = MI.getOperand(0);
1921  if (!MD.isDef())
1922  return false;
1923 
1924  unsigned Opc = MI.getOpcode();
1925  Register DefR(MD);
1926  assert(!DefR.SubReg);
1928  return false;
1929 
1930  if (MI.isCopy()) {
1931  LatticeCell RC;
1932  Register SrcR(MI.getOperand(1));
1933  bool Eval = evaluateCOPY(SrcR, Inputs, RC);
1934  if (!Eval)
1935  return false;
1936  Outputs.update(DefR.Reg, RC);
1937  return true;
1938  }
1939  if (MI.isRegSequence()) {
1940  unsigned Sub1 = MI.getOperand(2).getImm();
1941  unsigned Sub2 = MI.getOperand(4).getImm();
1942  const TargetRegisterClass &DefRC = *MRI->getRegClass(DefR.Reg);
1943  unsigned SubLo = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_lo);
1944  unsigned SubHi = HRI.getHexagonSubRegIndex(DefRC, Hexagon::ps_sub_hi);
1945  if (Sub1 != SubLo && Sub1 != SubHi)
1946  return false;
1947  if (Sub2 != SubLo && Sub2 != SubHi)
1948  return false;
1949  assert(Sub1 != Sub2);
1950  bool LoIs1 = (Sub1 == SubLo);
1951  const MachineOperand &OpLo = LoIs1 ? MI.getOperand(1) : MI.getOperand(3);
1952  const MachineOperand &OpHi = LoIs1 ? MI.getOperand(3) : MI.getOperand(1);
1953  LatticeCell RC;
1954  Register SrcRL(OpLo), SrcRH(OpHi);
1955  bool Eval = evaluateHexRSEQ32(SrcRL, SrcRH, Inputs, RC);
1956  if (!Eval)
1957  return false;
1958  Outputs.update(DefR.Reg, RC);
1959  return true;
1960  }
1961  if (MI.isCompare()) {
1962  bool Eval = evaluateHexCompare(MI, Inputs, Outputs);
1963  return Eval;
1964  }
1965 
1966  switch (Opc) {
1967  default:
1968  return false;
1969  case Hexagon::A2_tfrsi:
1970  case Hexagon::A2_tfrpi:
1971  case Hexagon::CONST32:
1972  case Hexagon::CONST64:
1973  {
1974  const MachineOperand &VO = MI.getOperand(1);
1975  // The operand of CONST32 can be a blockaddress, e.g.
1976  // %0 = CONST32 <blockaddress(@eat, %l)>
1977  // Do this check for all instructions for safety.
1978  if (!VO.isImm())
1979  return false;
1980  int64_t V = MI.getOperand(1).getImm();
1981  unsigned W = getRegBitWidth(DefR.Reg);
1982  if (W != 32 && W != 64)
1983  return false;
1984  IntegerType *Ty = (W == 32) ? Type::getInt32Ty(CX)
1985  : Type::getInt64Ty(CX);
1986  const ConstantInt *CI = ConstantInt::get(Ty, V, true);
1987  LatticeCell RC = Outputs.get(DefR.Reg);
1988  RC.add(CI);
1989  Outputs.update(DefR.Reg, RC);
1990  break;
1991  }
1992 
1993  case Hexagon::PS_true:
1994  case Hexagon::PS_false:
1995  {
1996  LatticeCell RC = Outputs.get(DefR.Reg);
1997  bool NonZero = (Opc == Hexagon::PS_true);
1998  uint32_t P = NonZero ? ConstantProperties::NonZero
1999  : ConstantProperties::Zero;
2000  RC.add(P);
2001  Outputs.update(DefR.Reg, RC);
2002  break;
2003  }
2004 
2005  case Hexagon::A2_and:
2006  case Hexagon::A2_andir:
2007  case Hexagon::A2_andp:
2008  case Hexagon::A2_or:
2009  case Hexagon::A2_orir:
2010  case Hexagon::A2_orp:
2011  case Hexagon::A2_xor:
2012  case Hexagon::A2_xorp:
2013  {
2014  bool Eval = evaluateHexLogical(MI, Inputs, Outputs);
2015  if (!Eval)
2016  return false;
2017  break;
2018  }
2019 
2020  case Hexagon::A2_combineii: // combine(#s8Ext, #s8)
2021  case Hexagon::A4_combineii: // combine(#s8, #u6Ext)
2022  {
2023  if (!MI.getOperand(1).isImm() || !MI.getOperand(2).isImm())
2024  return false;
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  if (!Src2.isImm())
2635  return false;
2636  APInt A(32, Src2.getImm(), true);
2637  Eval = evaluateANDri(R1, A, Inputs, RC);
2638  break;
2639  }
2640  case Hexagon::A2_or:
2641  case Hexagon::A2_orp:
2642  Eval = evaluateORrr(R1, Register(Src2), Inputs, RC);
2643  break;
2644  case Hexagon::A2_orir: {
2645  if (!Src2.isImm())
2646  return false;
2647  APInt A(32, Src2.getImm(), true);
2648  Eval = evaluateORri(R1, A, Inputs, RC);
2649  break;
2650  }
2651  case Hexagon::A2_xor:
2652  case Hexagon::A2_xorp:
2653  Eval = evaluateXORrr(R1, Register(Src2), Inputs, RC);
2654  break;
2655  }
2656  if (Eval) {
2657  Register DefR(MI.getOperand(0));
2658  Outputs.update(DefR.Reg, RC);
2659  }
2660  return Eval;
2661 }
2662 
2663 bool HexagonConstEvaluator::evaluateHexCondMove(const MachineInstr &MI,
2664  const CellMap &Inputs, CellMap &Outputs) {
2665  // Dst0 = Cond1 ? Src2 : Src3
2666  Register CR(MI.getOperand(1));
2667  assert(Inputs.has(CR.Reg));
2668  LatticeCell LS;
2669  if (!getCell(CR, Inputs, LS))
2670  return false;
2671  uint32_t Ps = LS.properties();
2672  unsigned TakeOp;
2673  if (Ps & ConstantProperties::Zero)
2674  TakeOp = 3;
2675  else if (Ps & ConstantProperties::NonZero)
2676  TakeOp = 2;
2677  else
2678  return false;
2679 
2680  const MachineOperand &ValOp = MI.getOperand(TakeOp);
2681  Register DefR(MI.getOperand(0));
2682  LatticeCell RC = Outputs.get(DefR.Reg);
2683 
2684  if (ValOp.isImm()) {
2685  int64_t V = ValOp.getImm();
2686  unsigned W = getRegBitWidth(DefR.Reg);
2687  APInt A(W, V, true);
2688  const Constant *C = intToConst(A);
2689  RC.add(C);
2690  Outputs.update(DefR.Reg, RC);
2691  return true;
2692  }
2693  if (ValOp.isReg()) {
2694  Register R(ValOp);
2695  const LatticeCell &LR = Inputs.get(R.Reg);
2696  LatticeCell LSR;
2697  if (!evaluate(R, LR, LSR))
2698  return false;
2699  RC.meet(LSR);
2700  Outputs.update(DefR.Reg, RC);
2701  return true;
2702  }
2703  return false;
2704 }
2705 
2706 bool HexagonConstEvaluator::evaluateHexExt(const MachineInstr &MI,
2707  const CellMap &Inputs, CellMap &Outputs) {
2708  // Dst0 = ext R1
2709  Register R1(MI.getOperand(1));
2710  assert(Inputs.has(R1.Reg));
2711 
2712  unsigned Opc = MI.getOpcode();
2713  unsigned Bits;
2714  switch (Opc) {
2715  case Hexagon::A2_sxtb:
2716  case Hexagon::A2_zxtb:
2717  Bits = 8;
2718  break;
2719  case Hexagon::A2_sxth:
2720  case Hexagon::A2_zxth:
2721  Bits = 16;
2722  break;
2723  case Hexagon::A2_sxtw:
2724  Bits = 32;
2725  break;
2726  }
2727 
2728  bool Signed = false;
2729  switch (Opc) {
2730  case Hexagon::A2_sxtb:
2731  case Hexagon::A2_sxth:
2732  case Hexagon::A2_sxtw:
2733  Signed = true;
2734  break;
2735  }
2736 
2737  Register DefR(MI.getOperand(0));
2738  unsigned BW = getRegBitWidth(DefR.Reg);
2739  LatticeCell RC = Outputs.get(DefR.Reg);
2740  bool Eval = Signed ? evaluateSEXTr(R1, BW, Bits, Inputs, RC)
2741  : evaluateZEXTr(R1, BW, Bits, Inputs, RC);
2742  if (!Eval)
2743  return false;
2744  Outputs.update(DefR.Reg, RC);
2745  return true;
2746 }
2747 
2748 bool HexagonConstEvaluator::evaluateHexVector1(const MachineInstr &MI,
2749  const CellMap &Inputs, CellMap &Outputs) {
2750  // DefR = op R1
2751  Register DefR(MI.getOperand(0));
2752  Register R1(MI.getOperand(1));
2753  assert(Inputs.has(R1.Reg));
2754  LatticeCell RC = Outputs.get(DefR.Reg);
2755  bool Eval;
2756 
2757  unsigned Opc = MI.getOpcode();
2758  switch (Opc) {
2759  case Hexagon::S2_vsplatrb:
2760  // Rd = 4 times Rs:0..7
2761  Eval = evaluateSplatr(R1, 8, 4, Inputs, RC);
2762  break;
2763  case Hexagon::S2_vsplatrh:
2764  // Rdd = 4 times Rs:0..15
2765  Eval = evaluateSplatr(R1, 16, 4, Inputs, RC);
2766  break;
2767  default:
2768  return false;
2769  }
2770 
2771  if (!Eval)
2772  return false;
2773  Outputs.update(DefR.Reg, RC);
2774  return true;
2775 }
2776 
2777 bool HexagonConstEvaluator::rewriteHexConstDefs(MachineInstr &MI,
2778  const CellMap &Inputs, bool &AllDefs) {
2779  AllDefs = false;
2780 
2781  // Some diagnostics.
2782  // LLVM_DEBUG({...}) gets confused with all this code as an argument.
2783 #ifndef NDEBUG
2784  bool Debugging = DebugFlag && isCurrentDebugType(DEBUG_TYPE);
2785  if (Debugging) {
2786  bool Const = true, HasUse = false;
2787  for (const MachineOperand &MO : MI.operands()) {
2788  if (!MO.isReg() || !MO.isUse() || MO.isImplicit())
2789  continue;
2790  Register R(MO);
2792  continue;
2793  HasUse = true;
2794  // PHIs can legitimately have "top" cells after propagation.
2795  if (!MI.isPHI() && !Inputs.has(R.Reg)) {
2796  dbgs() << "Top " << printReg(R.Reg, &HRI, R.SubReg)
2797  << " in MI: " << MI;
2798  continue;
2799  }
2800  const LatticeCell &L = Inputs.get(R.Reg);
2801  Const &= L.isSingle();
2802  if (!Const)
2803  break;
2804  }
2805  if (HasUse && Const) {
2806  if (!MI.isCopy()) {
2807  dbgs() << "CONST: " << MI;
2808  for (const MachineOperand &MO : MI.operands()) {
2809  if (!MO.isReg() || !MO.isUse() || MO.isImplicit())
2810  continue;
2811  unsigned R = MO.getReg();
2812  dbgs() << printReg(R, &TRI) << ": " << Inputs.get(R) << "\n";
2813  }
2814  }
2815  }
2816  }
2817 #endif
2818 
2819  // Avoid generating TFRIs for register transfers---this will keep the
2820  // coalescing opportunities.
2821  if (MI.isCopy())
2822  return false;
2823 
2824  // Collect all virtual register-def operands.
2825  SmallVector<unsigned,2> DefRegs;
2826  for (const MachineOperand &MO : MI.operands()) {
2827  if (!MO.isReg() || !MO.isDef())
2828  continue;
2829  unsigned R = MO.getReg();
2831  continue;
2832  assert(!MO.getSubReg());
2833  assert(Inputs.has(R));
2834  DefRegs.push_back(R);
2835  }
2836 
2837  MachineBasicBlock &B = *MI.getParent();
2838  const DebugLoc &DL = MI.getDebugLoc();
2839  unsigned ChangedNum = 0;
2840 #ifndef NDEBUG
2842 #endif
2843 
2844  // For each defined register, if it is a constant, create an instruction
2845  // NewR = const
2846  // and replace all uses of the defined register with NewR.
2847  for (unsigned i = 0, n = DefRegs.size(); i < n; ++i) {
2848  unsigned R = DefRegs[i];
2849  const LatticeCell &L = Inputs.get(R);
2850  if (L.isBottom())
2851  continue;
2852  const TargetRegisterClass *RC = MRI->getRegClass(R);
2854 
2855  if (!L.isSingle()) {
2856  // If this a zero/non-zero cell, we can fold a definition
2857  // of a predicate register.
2858  using P = ConstantProperties;
2859 
2860  uint64_t Ps = L.properties();
2861  if (!(Ps & (P::Zero|P::NonZero)))
2862  continue;
2863  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
2864  if (RC != PredRC)
2865  continue;
2866  const MCInstrDesc *NewD = (Ps & P::Zero) ?
2867  &HII.get(Hexagon::PS_false) :
2868  &HII.get(Hexagon::PS_true);
2869  unsigned NewR = MRI->createVirtualRegister(PredRC);
2870  const MachineInstrBuilder &MIB = BuildMI(B, At, DL, *NewD, NewR);
2871  (void)MIB;
2872 #ifndef NDEBUG
2873  NewInstrs.push_back(&*MIB);
2874 #endif
2875  replaceAllRegUsesWith(R, NewR);
2876  } else {
2877  // This cell has a single value.
2878  APInt A;
2879  if (!constToInt(L.Value, A) || !A.isSignedIntN(64))
2880  continue;
2881  const TargetRegisterClass *NewRC;
2882  const MCInstrDesc *NewD;
2883 
2884  unsigned W = getRegBitWidth(R);
2885  int64_t V = A.getSExtValue();
2886  assert(W == 32 || W == 64);
2887  if (W == 32)
2888  NewRC = &Hexagon::IntRegsRegClass;
2889  else
2890  NewRC = &Hexagon::DoubleRegsRegClass;
2891  unsigned NewR = MRI->createVirtualRegister(NewRC);
2892  const MachineInstr *NewMI;
2893 
2894  if (W == 32) {
2895  NewD = &HII.get(Hexagon::A2_tfrsi);
2896  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2897  .addImm(V);
2898  } else {
2899  if (A.isSignedIntN(8)) {
2900  NewD = &HII.get(Hexagon::A2_tfrpi);
2901  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2902  .addImm(V);
2903  } else {
2904  int32_t Hi = V >> 32;
2905  int32_t Lo = V & 0xFFFFFFFFLL;
2906  if (isInt<8>(Hi) && isInt<8>(Lo)) {
2907  NewD = &HII.get(Hexagon::A2_combineii);
2908  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2909  .addImm(Hi)
2910  .addImm(Lo);
2911  } else {
2912  NewD = &HII.get(Hexagon::CONST64);
2913  NewMI = BuildMI(B, At, DL, *NewD, NewR)
2914  .addImm(V);
2915  }
2916  }
2917  }
2918  (void)NewMI;
2919 #ifndef NDEBUG
2920  NewInstrs.push_back(NewMI);
2921 #endif
2922  replaceAllRegUsesWith(R, NewR);
2923  }
2924  ChangedNum++;
2925  }
2926 
2927  LLVM_DEBUG({
2928  if (!NewInstrs.empty()) {
2929  MachineFunction &MF = *MI.getParent()->getParent();
2930  dbgs() << "In function: " << MF.getName() << "\n";
2931  dbgs() << "Rewrite: for " << MI << " created " << *NewInstrs[0];
2932  for (unsigned i = 1; i < NewInstrs.size(); ++i)
2933  dbgs() << " " << *NewInstrs[i];
2934  }
2935  });
2936 
2937  AllDefs = (ChangedNum == DefRegs.size());
2938  return ChangedNum > 0;
2939 }
2940 
2941 bool HexagonConstEvaluator::rewriteHexConstUses(MachineInstr &MI,
2942  const CellMap &Inputs) {
2943  bool Changed = false;
2944  unsigned Opc = MI.getOpcode();
2945  MachineBasicBlock &B = *MI.getParent();
2946  const DebugLoc &DL = MI.getDebugLoc();
2948  MachineInstr *NewMI = nullptr;
2949 
2950  switch (Opc) {
2951  case Hexagon::M2_maci:
2952  // Convert DefR += mpyi(R2, R3)
2953  // to DefR += mpyi(R, #imm),
2954  // or DefR -= mpyi(R, #imm).
2955  {
2956  Register DefR(MI.getOperand(0));
2957  assert(!DefR.SubReg);
2958  Register R2(MI.getOperand(2));
2959  Register R3(MI.getOperand(3));
2960  assert(Inputs.has(R2.Reg) && Inputs.has(R3.Reg));
2961  LatticeCell LS2, LS3;
2962  // It is enough to get one of the input cells, since we will only try
2963  // to replace one argument---whichever happens to be a single constant.
2964  bool HasC2 = getCell(R2, Inputs, LS2), HasC3 = getCell(R3, Inputs, LS3);
2965  if (!HasC2 && !HasC3)
2966  return false;
2967  bool Zero = ((HasC2 && (LS2.properties() & ConstantProperties::Zero)) ||
2968  (HasC3 && (LS3.properties() & ConstantProperties::Zero)));
2969  // If one of the operands is zero, eliminate the multiplication.
2970  if (Zero) {
2971  // DefR == R1 (tied operands).
2972  MachineOperand &Acc = MI.getOperand(1);
2973  Register R1(Acc);
2974  unsigned NewR = R1.Reg;
2975  if (R1.SubReg) {
2976  // Generate COPY. FIXME: Replace with the register:subregister.
2977  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
2978  NewR = MRI->createVirtualRegister(RC);
2979  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
2980  .addReg(R1.Reg, getRegState(Acc), R1.SubReg);
2981  }
2982  replaceAllRegUsesWith(DefR.Reg, NewR);
2983  MRI->clearKillFlags(NewR);
2984  Changed = true;
2985  break;
2986  }
2987 
2988  bool Swap = false;
2989  if (!LS3.isSingle()) {
2990  if (!LS2.isSingle())
2991  return false;
2992  Swap = true;
2993  }
2994  const LatticeCell &LI = Swap ? LS2 : LS3;
2995  const MachineOperand &OpR2 = Swap ? MI.getOperand(3)
2996  : MI.getOperand(2);
2997  // LI is single here.
2998  APInt A;
2999  if (!constToInt(LI.Value, A) || !A.isSignedIntN(8))
3000  return false;
3001  int64_t V = A.getSExtValue();
3002  const MCInstrDesc &D = (V >= 0) ? HII.get(Hexagon::M2_macsip)
3003  : HII.get(Hexagon::M2_macsin);
3004  if (V < 0)
3005  V = -V;
3006  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3007  unsigned NewR = MRI->createVirtualRegister(RC);
3008  const MachineOperand &Src1 = MI.getOperand(1);
3009  NewMI = BuildMI(B, At, DL, D, NewR)
3010  .addReg(Src1.getReg(), getRegState(Src1), Src1.getSubReg())
3011  .addReg(OpR2.getReg(), getRegState(OpR2), OpR2.getSubReg())
3012  .addImm(V);
3013  replaceAllRegUsesWith(DefR.Reg, NewR);
3014  Changed = true;
3015  break;
3016  }
3017 
3018  case Hexagon::A2_and:
3019  {
3020  Register R1(MI.getOperand(1));
3021  Register R2(MI.getOperand(2));
3022  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
3023  LatticeCell LS1, LS2;
3024  unsigned CopyOf = 0;
3025  // Check if any of the operands is -1 (i.e. all bits set).
3026  if (getCell(R1, Inputs, LS1) && LS1.isSingle()) {
3027  APInt M1;
3028  if (constToInt(LS1.Value, M1) && !~M1)
3029  CopyOf = 2;
3030  }
3031  else if (getCell(R2, Inputs, LS2) && LS2.isSingle()) {
3032  APInt M1;
3033  if (constToInt(LS2.Value, M1) && !~M1)
3034  CopyOf = 1;
3035  }
3036  if (!CopyOf)
3037  return false;
3038  MachineOperand &SO = MI.getOperand(CopyOf);
3039  Register SR(SO);
3040  Register DefR(MI.getOperand(0));
3041  unsigned NewR = SR.Reg;
3042  if (SR.SubReg) {
3043  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3044  NewR = MRI->createVirtualRegister(RC);
3045  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
3046  .addReg(SR.Reg, getRegState(SO), SR.SubReg);
3047  }
3048  replaceAllRegUsesWith(DefR.Reg, NewR);
3049  MRI->clearKillFlags(NewR);
3050  Changed = true;
3051  }
3052  break;
3053 
3054  case Hexagon::A2_or:
3055  {
3056  Register R1(MI.getOperand(1));
3057  Register R2(MI.getOperand(2));
3058  assert(Inputs.has(R1.Reg) && Inputs.has(R2.Reg));
3059  LatticeCell LS1, LS2;
3060  unsigned CopyOf = 0;
3061 
3062  using P = ConstantProperties;
3063 
3064  if (getCell(R1, Inputs, LS1) && (LS1.properties() & P::Zero))
3065  CopyOf = 2;
3066  else if (getCell(R2, Inputs, LS2) && (LS2.properties() & P::Zero))
3067  CopyOf = 1;
3068  if (!CopyOf)
3069  return false;
3070  MachineOperand &SO = MI.getOperand(CopyOf);
3071  Register SR(SO);
3072  Register DefR(MI.getOperand(0));
3073  unsigned NewR = SR.Reg;
3074  if (SR.SubReg) {
3075  const TargetRegisterClass *RC = MRI->getRegClass(DefR.Reg);
3076  NewR = MRI->createVirtualRegister(RC);
3077  NewMI = BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
3078  .addReg(SR.Reg, getRegState(SO), SR.SubReg);
3079  }
3080  replaceAllRegUsesWith(DefR.Reg, NewR);
3081  MRI->clearKillFlags(NewR);
3082  Changed = true;
3083  }
3084  break;
3085  }
3086 
3087  if (NewMI) {
3088  // clear all the kill flags of this new instruction.
3089  for (MachineOperand &MO : NewMI->operands())
3090  if (MO.isReg() && MO.isUse())
3091  MO.setIsKill(false);
3092  }
3093 
3094  LLVM_DEBUG({
3095  if (NewMI) {
3096  dbgs() << "Rewrite: for " << MI;
3097  if (NewMI != &MI)
3098  dbgs() << " created " << *NewMI;
3099  else
3100  dbgs() << " modified the instruction itself and created:" << *NewMI;
3101  }
3102  });
3103 
3104  return Changed;
3105 }
3106 
3107 void HexagonConstEvaluator::replaceAllRegUsesWith(unsigned FromReg,
3108  unsigned ToReg) {
3111  for (auto I = MRI->use_begin(FromReg), E = MRI->use_end(); I != E;) {
3112  MachineOperand &O = *I;
3113  ++I;
3114  O.setReg(ToReg);
3115  }
3116 }
3117 
3118 bool HexagonConstEvaluator::rewriteHexBranch(MachineInstr &BrI,
3119  const CellMap &Inputs) {
3120  MachineBasicBlock &B = *BrI.getParent();
3121  unsigned NumOp = BrI.getNumOperands();
3122  if (!NumOp)
3123  return false;
3124 
3125  bool FallsThru;
3127  bool Eval = evaluate(BrI, Inputs, Targets, FallsThru);
3128  unsigned NumTargets = Targets.size();
3129  if (!Eval || NumTargets > 1 || (NumTargets == 1 && FallsThru))
3130  return false;
3131  if (BrI.getOpcode() == Hexagon::J2_jump)
3132  return false;
3133 
3134  LLVM_DEBUG(dbgs() << "Rewrite(" << printMBBReference(B) << "):" << BrI);
3135  bool Rewritten = false;
3136  if (NumTargets > 0) {
3137  assert(!FallsThru && "This should have been checked before");
3138  // MIB.addMBB needs non-const pointer.
3139  MachineBasicBlock *TargetB = const_cast<MachineBasicBlock*>(Targets[0]);
3140  bool Moot = B.isLayoutSuccessor(TargetB);
3141  if (!Moot) {
3142  // If we build a branch here, we must make sure that it won't be
3143  // erased as "non-executable". We can't mark any new instructions
3144  // as executable here, so we need to overwrite the BrI, which we
3145  // know is executable.
3146  const MCInstrDesc &JD = HII.get(Hexagon::J2_jump);
3147  auto NI = BuildMI(B, BrI.getIterator(), BrI.getDebugLoc(), JD)
3148  .addMBB(TargetB);
3149  BrI.setDesc(JD);
3150  while (BrI.getNumOperands() > 0)
3151  BrI.RemoveOperand(0);
3152  // This ensures that all implicit operands (e.g. implicit-def %r31, etc)
3153  // are present in the rewritten branch.
3154  for (auto &Op : NI->operands())
3155  BrI.addOperand(Op);
3156  NI->eraseFromParent();
3157  Rewritten = true;
3158  }
3159  }
3160 
3161  // Do not erase instructions. A newly created instruction could get
3162  // the same address as an instruction marked as executable during the
3163  // propagation.
3164  if (!Rewritten)
3165  replaceWithNop(BrI);
3166  return true;
3167 }
3168 
3170  return new HexagonConstPropagation();
3171 }
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:259
DILocation * get() const
Get the underlying DILocation.
Definition: DebugLoc.cpp:22
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1557
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:834
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:633
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:250
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
#define LLVM_FALLTHROUGH
Definition: Compiler.h:86
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:289
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:383
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:858
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:1198
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:45
unsigned Reg
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:648
unsigned getSubReg() const
unsigned getRegBitWidth(unsigned RCID)
Get the size in bits of a register from the register class RC.
bool isRegSequence() const
constexpr bool isInt< 8 >(int64_t x)
Definition: MathExtras.h:303
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:811
unsigned const TargetRegisterInfo * TRI
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:876
#define R2(n)
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:459
bool isPHI() const
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:1503
iterator_range< succ_iterator > successors()
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1626
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:993
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:412
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
APInt zextOrSelf(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:892
unsigned SubReg
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
Definition: Path.cpp:250
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...
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1569
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:305
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:657
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:364
#define P(N)
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:259
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:694
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:1179
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:4120
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:450
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:659
bool isCopy() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:53
bool isDebugInstr() const
Definition: MachineInstr.h:999
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:971
void setIsKill(bool Val=true)
bool isNegative() const
Definition: Constants.h:188
const APFloat & getValueAPF() const
Definition: Constants.h:299
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:947
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
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1023
BlockVerifier::State From
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
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:621
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:133
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1640
void clear()
Completely clear the SetVector.
Definition: SetVector.h:216
Class for arbitrary precision integers.
Definition: APInt.h:70
INITIALIZE_PASS(HexagonConstPropagation, "hexagon-constp", "Hexagon Constant Propagation", false, false) HexagonConstEvaluator
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:212
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:679
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
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:56
bool isZero() const
Return true if the value is positive or negative zero.
Definition: Constants.h:302
bool isNaN() const
Return true if the value is a NaN.
Definition: Constants.h:311
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
uint32_t Size
Definition: Profile.cpp:47
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:456
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2033
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())
LLVM Value Representation.
Definition: Value.h:73
A vector that has set insertion semantics.
Definition: SetVector.h:41
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:46
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:1606
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
void RemoveOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1590
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1961
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
bool DebugFlag
This boolean is set to true if the &#39;-debug&#39; command line option is specified.
Definition: Debug.cpp:44
APInt sextOrSelf(unsigned width) const
Sign extend or truncate to width.
Definition: APInt.cpp:898
bool isCurrentDebugType(const char *Type)
isCurrentDebugType - Return true if the specified string is the debug type specified on the command l...
Definition: Debug.cpp:51
bool isImplicit() const