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