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