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