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