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