xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonConstPropagation.cpp (revision 9f23cbd6cae82fd77edfad7173432fa8dccd0a95)
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 
48 using namespace llvm;
49 
50 namespace {
51 
52   // Properties of a value that are tracked by the propagation.
53   // A property that is marked as present (i.e. bit is set) dentes that the
54   // value is known (proven) to have this property. Not all combinations
55   // of bits make sense, for example Zero and NonZero are mutually exclusive,
56   // but on the other hand, Zero implies Finite. In this case, whenever
57   // the Zero property is present, Finite should also be present.
58   class ConstantProperties {
59   public:
60     enum {
61       Unknown   = 0x0000,
62       Zero      = 0x0001,
63       NonZero   = 0x0002,
64       Finite    = 0x0004,
65       Infinity  = 0x0008,
66       NaN       = 0x0010,
67       SignedZero = 0x0020,
68       NumericProperties = (Zero|NonZero|Finite|Infinity|NaN|SignedZero),
69       PosOrZero       = 0x0100,
70       NegOrZero       = 0x0200,
71       SignProperties  = (PosOrZero|NegOrZero),
72       Everything      = (NumericProperties|SignProperties)
73     };
74 
75     // For a given constant, deduce the set of trackable properties that this
76     // constant has.
77     static uint32_t deduce(const Constant *C);
78   };
79 
80   // A representation of a register as it can appear in a MachineOperand,
81   // i.e. a pair register:subregister.
82 
83   // FIXME: Use TargetInstrInfo::RegSubRegPair. Also duplicated in
84   // HexagonGenPredicate
85   struct RegisterSubReg {
86     Register Reg;
87     unsigned SubReg;
88 
89     explicit RegisterSubReg(unsigned R, unsigned SR = 0) : Reg(R), SubReg(SR) {}
90     explicit RegisterSubReg(const MachineOperand &MO)
91       : Reg(MO.getReg()), SubReg(MO.getSubReg()) {}
92 
93     void print(const TargetRegisterInfo *TRI = nullptr) const {
94       dbgs() << printReg(Reg, TRI, SubReg);
95     }
96 
97     bool operator== (const RegisterSubReg &R) const {
98       return (Reg == R.Reg) && (SubReg == R.SubReg);
99     }
100   };
101 
102   // Lattice cell, based on that was described in the W-Z paper on constant
103   // propagation.
104   // Latice cell will be allowed to hold multiple constant values. While
105   // multiple values would normally indicate "bottom", we can still derive
106   // some useful information from them. For example, comparison X > 0
107   // could be folded if all the values in the cell associated with X are
108   // positive.
109   class LatticeCell {
110   private:
111     enum { Normal, Top, Bottom };
112 
113     static const unsigned MaxCellSize = 4;
114 
115     unsigned Kind:2;
116     unsigned Size:3;
117     unsigned IsSpecial:1;
118     unsigned :0;
119 
120   public:
121     union {
122       uint32_t Properties;
123       const Constant *Value;
124       const Constant *Values[MaxCellSize];
125     };
126 
127     LatticeCell() : Kind(Top), Size(0), IsSpecial(false) {
128       for (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 
430 uint32_t ConstantProperties::deduce(const Constant *C) {
431   if (isa<ConstantInt>(C)) {
432     const ConstantInt *CI = cast<ConstantInt>(C);
433     if (CI->isZero())
434       return Zero | PosOrZero | NegOrZero | Finite;
435     uint32_t Props = (NonZero | Finite);
436     if (CI->isNegative())
437       return Props | NegOrZero;
438     return Props | PosOrZero;
439   }
440 
441   if (isa<ConstantFP>(C)) {
442     const ConstantFP *CF = cast<ConstantFP>(C);
443     uint32_t Props = CF->isNegative() ? (NegOrZero|NonZero)
444                                       : PosOrZero;
445     if (CF->isZero())
446       return (Props & ~NumericProperties) | (Zero|Finite);
447     Props = (Props & ~NumericProperties) | NonZero;
448     if (CF->isNaN())
449       return (Props & ~NumericProperties) | NaN;
450     const APFloat &Val = CF->getValueAPF();
451     if (Val.isInfinity())
452       return (Props & ~NumericProperties) | Infinity;
453     Props |= Finite;
454     return Props;
455   }
456 
457   return Unknown;
458 }
459 
460 // Convert a cell from a set of specific values to a cell that tracks
461 // properties.
462 bool LatticeCell::convertToProperty() {
463   if (isProperty())
464     return false;
465   // Corner case: converting a fresh (top) cell to "special".
466   // This can happen, when adding a property to a top cell.
467   uint32_t Everything = ConstantProperties::Everything;
468   uint32_t Ps = !isTop() ? properties()
469                          : Everything;
470   if (Ps != ConstantProperties::Unknown) {
471     Properties = Ps;
472     setProperty();
473   } else {
474     setBottom();
475   }
476   return true;
477 }
478 
479 #ifndef NDEBUG
480 void LatticeCell::print(raw_ostream &os) const {
481   if (isProperty()) {
482     os << "{ ";
483     uint32_t Ps = properties();
484     if (Ps & ConstantProperties::Zero)
485       os << "zero ";
486     if (Ps & ConstantProperties::NonZero)
487       os << "nonzero ";
488     if (Ps & ConstantProperties::Finite)
489       os << "finite ";
490     if (Ps & ConstantProperties::Infinity)
491       os << "infinity ";
492     if (Ps & ConstantProperties::NaN)
493       os << "nan ";
494     if (Ps & ConstantProperties::PosOrZero)
495       os << "poz ";
496     if (Ps & ConstantProperties::NegOrZero)
497       os << "nez ";
498     os << '}';
499     return;
500   }
501 
502   os << "{ ";
503   if (isBottom()) {
504     os << "bottom";
505   } else if (isTop()) {
506     os << "top";
507   } else {
508     for (unsigned i = 0; i < size(); ++i) {
509       const Constant *C = Values[i];
510       if (i != 0)
511         os << ", ";
512       C->print(os);
513     }
514   }
515   os << " }";
516 }
517 #endif
518 
519 // "Meet" operation on two cells. This is the key of the propagation
520 // algorithm.
521 bool LatticeCell::meet(const LatticeCell &L) {
522   bool Changed = false;
523   if (L.isBottom())
524     Changed = setBottom();
525   if (isBottom() || L.isTop())
526     return Changed;
527   if (isTop()) {
528     *this = L;
529     // L can be neither Top nor Bottom, so *this must have changed.
530     return true;
531   }
532 
533   // Top/bottom cases covered. Need to integrate L's set into ours.
534   if (L.isProperty())
535     return add(L.properties());
536   for (unsigned i = 0; i < L.size(); ++i) {
537     const Constant *LC = L.Values[i];
538     Changed |= add(LC);
539   }
540   return Changed;
541 }
542 
543 // Add a new constant to the cell. This is actually where the cell update
544 // happens. If a cell has room for more constants, the new constant is added.
545 // Otherwise, the cell is converted to a "property" cell (i.e. a cell that
546 // will track properties of the associated values, and not the values
547 // themselves. Care is taken to handle special cases, like "bottom", etc.
548 bool LatticeCell::add(const Constant *LC) {
549   assert(LC);
550   if (isBottom())
551     return false;
552 
553   if (!isProperty()) {
554     // Cell is not special. Try to add the constant here first,
555     // if there is room.
556     unsigned Index = 0;
557     while (Index < Size) {
558       const Constant *C = Values[Index];
559       // If the constant is already here, no change is needed.
560       if (C == LC)
561         return false;
562       Index++;
563     }
564     if (Index < MaxCellSize) {
565       Values[Index] = LC;
566       Kind = Normal;
567       Size++;
568       return true;
569     }
570   }
571 
572   bool Changed = false;
573 
574   // This cell is special, or is not special, but is full. After this
575   // it will be special.
576   Changed = convertToProperty();
577   uint32_t Ps = properties();
578   uint32_t NewPs = Ps & ConstantProperties::deduce(LC);
579   if (NewPs == ConstantProperties::Unknown) {
580     setBottom();
581     return true;
582   }
583   if (Ps != NewPs) {
584     Properties = NewPs;
585     Changed = true;
586   }
587   return Changed;
588 }
589 
590 // Add a property to the cell. This will force the cell to become a property-
591 // tracking cell.
592 bool LatticeCell::add(uint32_t Property) {
593   bool Changed = convertToProperty();
594   uint32_t Ps = properties();
595   if (Ps == (Ps & Property))
596     return Changed;
597   Properties = Property & Ps;
598   return true;
599 }
600 
601 // Return the properties of the values in the cell. This is valid for any
602 // cell, and does not alter the cell itself.
603 uint32_t LatticeCell::properties() const {
604   if (isProperty())
605     return Properties;
606   assert(!isTop() && "Should not call this for a top cell");
607   if (isBottom())
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
621 void 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 
628 void MachineConstPropagator::visitPHI(const MachineInstr &PN) {
629   const MachineBasicBlock *MB = PN.getParent();
630   unsigned MBN = MB->getNumber();
631   LLVM_DEBUG(dbgs() << "Visiting FI(" << printMBBReference(*MB) << "): " << PN);
632 
633   const MachineOperand &MD = PN.getOperand(0);
634   RegisterSubReg DefR(MD);
635   assert(DefR.Reg.isVirtual());
636 
637   bool Changed = false;
638 
639   // If the def has a sub-register, set the corresponding cell to "bottom".
640   if (DefR.SubReg) {
641 Bottomize:
642     const LatticeCell &T = Cells.get(DefR.Reg);
643     Changed = !T.isBottom();
644     Cells.update(DefR.Reg, Bottom);
645     if (Changed)
646       visitUsesOf(DefR.Reg);
647     return;
648   }
649 
650   LatticeCell DefC = Cells.get(DefR.Reg);
651 
652   for (unsigned i = 1, n = PN.getNumOperands(); i < n; i += 2) {
653     const MachineBasicBlock *PB = PN.getOperand(i+1).getMBB();
654     unsigned PBN = PB->getNumber();
655     if (!EdgeExec.count(CFGEdge(PBN, MBN))) {
656       LLVM_DEBUG(dbgs() << "  edge " << printMBBReference(*PB) << "->"
657                         << printMBBReference(*MB) << " not executable\n");
658       continue;
659     }
660     const MachineOperand &SO = PN.getOperand(i);
661     RegisterSubReg UseR(SO);
662     // If the input is not a virtual register, we don't really know what
663     // value it holds.
664     if (!UseR.Reg.isVirtual())
665       goto Bottomize;
666     // If there is no cell for an input register, it means top.
667     if (!Cells.has(UseR.Reg))
668       continue;
669 
670     LatticeCell SrcC;
671     bool Eval = MCE.evaluate(UseR, Cells.get(UseR.Reg), SrcC);
672     LLVM_DEBUG(dbgs() << "  edge from " << printMBBReference(*PB) << ": "
673                       << printReg(UseR.Reg, &MCE.TRI, UseR.SubReg) << SrcC
674                       << '\n');
675     Changed |= Eval ? DefC.meet(SrcC)
676                     : DefC.setBottom();
677     Cells.update(DefR.Reg, DefC);
678     if (DefC.isBottom())
679       break;
680   }
681   if (Changed)
682     visitUsesOf(DefR.Reg);
683 }
684 
685 void MachineConstPropagator::visitNonBranch(const MachineInstr &MI) {
686   LLVM_DEBUG(dbgs() << "Visiting MI(" << printMBBReference(*MI.getParent())
687                     << "): " << MI);
688   CellMap Outputs;
689   bool Eval = MCE.evaluate(MI, Cells, Outputs);
690   LLVM_DEBUG({
691     if (Eval) {
692       dbgs() << "  outputs:";
693       for (auto &I : Outputs)
694         dbgs() << ' ' << I.second;
695       dbgs() << '\n';
696     }
697   });
698 
699   // Update outputs. If the value was not computed, set all the
700   // def cells to bottom.
701   for (const MachineOperand &MO : MI.operands()) {
702     if (!MO.isReg() || !MO.isDef())
703       continue;
704     RegisterSubReg DefR(MO);
705     // Only track virtual registers.
706     if (!DefR.Reg.isVirtual())
707       continue;
708     bool Changed = false;
709     // If the evaluation failed, set cells for all output registers to bottom.
710     if (!Eval) {
711       const LatticeCell &T = Cells.get(DefR.Reg);
712       Changed = !T.isBottom();
713       Cells.update(DefR.Reg, Bottom);
714     } else {
715       // Find the corresponding cell in the computed outputs.
716       // If it's not there, go on to the next def.
717       if (!Outputs.has(DefR.Reg))
718         continue;
719       LatticeCell RC = Cells.get(DefR.Reg);
720       Changed = RC.meet(Outputs.get(DefR.Reg));
721       Cells.update(DefR.Reg, RC);
722     }
723     if (Changed)
724       visitUsesOf(DefR.Reg);
725   }
726 }
727 
728 // Starting at a given branch, visit remaining branches in the block.
729 // Traverse over the subsequent branches for as long as the preceding one
730 // can fall through. Add all the possible targets to the flow work queue,
731 // including the potential fall-through to the layout-successor block.
732 void MachineConstPropagator::visitBranchesFrom(const MachineInstr &BrI) {
733   const MachineBasicBlock &B = *BrI.getParent();
734   unsigned MBN = B.getNumber();
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 
795 void MachineConstPropagator::visitUsesOf(unsigned Reg) {
796   LLVM_DEBUG(dbgs() << "Visiting uses of " << printReg(Reg, &MCE.TRI)
797                     << Cells.get(Reg) << '\n');
798   for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
799     // Do not process non-executable instructions. They can become exceutable
800     // later (via a flow-edge in the work queue). In such case, the instruc-
801     // tion will be visited at that time.
802     if (!InstrExec.count(&MI))
803       continue;
804     if (MI.isPHI())
805       visitPHI(MI);
806     else if (!MI.isBranch())
807       visitNonBranch(MI);
808     else
809       visitBranchesFrom(MI);
810   }
811 }
812 
813 bool MachineConstPropagator::computeBlockSuccessors(const MachineBasicBlock *MB,
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 
861 void MachineConstPropagator::removeCFGEdge(MachineBasicBlock *From,
862       MachineBasicBlock *To) {
863   // First, remove the CFG successor/predecessor information.
864   From->removeSuccessor(To);
865   // Remove all corresponding PHI operands in the To block.
866   for (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 
879 void 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 
963 bool 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.
1056 bool 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 
1080 bool 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 
1093 bool 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 
1102 const ConstantInt *MachineConstEvaluator::intToConst(const APInt &Val) const {
1103   return ConstantInt::get(CX, Val);
1104 }
1105 
1106 bool 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 
1145 bool 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 
1172 bool 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 
1198 bool 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 
1239 bool 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 
1305 bool 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 
1365 bool MachineConstEvaluator::evaluateCOPY(const RegisterSubReg &R1,
1366       const CellMap &Inputs, LatticeCell &Result) {
1367   return getCell(R1, Inputs, Result);
1368 }
1369 
1370 bool 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 
1401 bool 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 
1431 bool MachineConstEvaluator::evaluateANDii(const APInt &A1,
1432       const APInt &A2, APInt &Result) {
1433   Result = A1 & A2;
1434   return true;
1435 }
1436 
1437 bool 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 
1468 bool 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 
1498 bool MachineConstEvaluator::evaluateORii(const APInt &A1,
1499       const APInt &A2, APInt &Result) {
1500   Result = A1 | A2;
1501   return true;
1502 }
1503 
1504 bool 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 
1533 bool 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 
1560 bool MachineConstEvaluator::evaluateXORii(const APInt &A1,
1561       const APInt &A2, APInt &Result) {
1562   Result = A1 ^ A2;
1563   return true;
1564 }
1565 
1566 bool 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 
1587 bool 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 
1597 bool 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 
1618 bool 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 
1662 bool 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 
1683 bool 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 
1697 bool 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 
1718 bool 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 
1732 bool 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 
1764 bool 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 
1790 bool 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 
1812 bool 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 
1832 namespace llvm {
1833 
1834   FunctionPass *createHexagonConstPropagationPass();
1835   void initializeHexagonConstPropagationPass(PassRegistry &Registry);
1836 
1837 } // end namespace llvm
1838 
1839 namespace {
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 
1913 char HexagonConstPropagation::ID = 0;
1914 
1915 INITIALIZE_PASS(HexagonConstPropagation, "hexagon-constp",
1916   "Hexagon Constant Propagation", false, false)
1917 
1918 HexagonConstEvaluator::HexagonConstEvaluator(MachineFunction &Fn)
1919   : MachineConstEvaluator(Fn),
1920     HII(*Fn.getSubtarget<HexagonSubtarget>().getInstrInfo()),
1921     HRI(*Fn.getSubtarget<HexagonSubtarget>().getRegisterInfo()) {
1922   MRI = &Fn.getRegInfo();
1923 }
1924 
1925 bool 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 
2203 bool 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 
2259 bool 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:
2285 Undetermined:
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 
2328 bool 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 
2360 unsigned 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 
2372 uint32_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 
2467 APInt 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 
2510 void HexagonConstEvaluator::replaceWithNop(MachineInstr &MI) {
2511   MI.setDesc(HII.get(Hexagon::A2_nop));
2512   while (MI.getNumOperands() > 0)
2513     MI.removeOperand(0);
2514 }
2515 
2516 bool 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 
2553 bool 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 
2598 bool 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 
2628 bool 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 
2675 bool 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 
2718 bool 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 
2762 bool 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 
2791 bool 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 
2960 bool 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 
3126 void 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 
3135 bool 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 
3186 FunctionPass *llvm::createHexagonConstPropagationPass() {
3187   return new HexagonConstPropagation();
3188 }
3189