contrib/llvm/lib/Target/Hexagon/HexagonConstPropagation.cpp

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