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