lib/Target/Hexagon/HexagonConstPropagation.cpp

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