//===- HexagonConstPropagation.cpp ----------------------------------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

#include "HexagonInstrInfo.h"

#include "HexagonRegisterInfo.h"

#include "HexagonSubtarget.h"

#include "llvm/ADT/APFloat.h"

#include "llvm/ADT/APInt.h"

#include "llvm/ADT/PostOrderIterator.h"

#include "llvm/ADT/SetVector.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/CodeGen/MachineBasicBlock.h"

#include "llvm/CodeGen/MachineFunction.h"

#include "llvm/CodeGen/MachineFunctionPass.h"

#include "llvm/CodeGen/MachineInstr.h"

#include "llvm/CodeGen/MachineInstrBuilder.h"

#include "llvm/CodeGen/MachineOperand.h"

#include "llvm/CodeGen/MachineRegisterInfo.h"

#include "llvm/CodeGen/TargetRegisterInfo.h"

#include "llvm/CodeGen/TargetSubtargetInfo.h"

#include "llvm/IR/Constants.h"

#include "llvm/IR/Type.h"

#include "llvm/Pass.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/Compiler.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/ErrorHandling.h"

#include "llvm/Support/MathExtras.h"

#include "llvm/Support/raw_ostream.h"

#include <cassert>

#include <cstdint>

#include <cstring>

#include <iterator>

#include <map>

#include <queue>

#include <set>

#include <utility>

#include <vector>

#define DEBUG_TYPE "hcp"

using namespace llvm;

namespace {

  // Properties of a value that are tracked by the propagation.

  // A property that is marked as present (i.e. bit is set) dentes that the

  // value is known (proven) to have this property. Not all combinations

  // of bits make sense, for example Zero and NonZero are mutually exclusive,

  // but on the other hand, Zero implies Finite. In this case, whenever

  // the Zero property is present, Finite should also be present.

  class ConstantProperties {

  public:

    enum {

      Unknown   = 0x0000,

      Zero      = 0x0001,

      NonZero   = 0x0002,

      Finite    = 0x0004,

      Infinity  = 0x0008,

      NaN       = 0x0010,

      SignedZero = 0x0020,

      NumericProperties = (Zero|NonZero|Finite|Infinity|NaN|SignedZero),

      PosOrZero       = 0x0100,

      NegOrZero       = 0x0200,

      SignProperties  = (PosOrZero|NegOrZero),

      Everything      = (NumericProperties|SignProperties)

    };

    // For a given constant, deduce the set of trackable properties that this

    // constant has.

    static uint32_t deduce(const Constant *C);

  };

  // A representation of a register as it can appear in a MachineOperand,

  // i.e. a pair register:subregister.

  // FIXME: Use TargetInstrInfo::RegSubRegPair. Also duplicated in

  // HexagonGenPredicate

  struct RegisterSubReg {

    Register Reg;

    unsigned SubReg;

    explicit RegisterSubReg(unsigned R, unsigned SR = 0) : Reg(R), SubReg(SR) {}

    explicit RegisterSubReg(const MachineOperand &MO)

      : Reg(MO.getReg()), SubReg(MO.getSubReg()) {}

    void print(const TargetRegisterInfo *TRI = nullptr) const {

      dbgs() << printReg(Reg, TRI, SubReg);

    }

    bool operator== (const RegisterSubReg &R) const {

      return (Reg == R.Reg) && (SubReg == R.SubReg);

    }

  };

  // Lattice cell, based on that was described in the W-Z paper on constant

  // propagation.

  // Latice cell will be allowed to hold multiple constant values. While

  // multiple values would normally indicate "bottom", we can still derive

  // some useful information from them. For example, comparison X > 0

  // could be folded if all the values in the cell associated with X are

  // positive.

  class LatticeCell {

  private:

    enum { Normal, Top, Bottom };

    static const unsigned MaxCellSize = 4;

    unsigned Kind:2;

    unsigned Size:3;

    unsigned IsSpecial:1;

    unsigned :0;

  public:

    union {

      uint32_t Properties;

      const Constant *Value;

      const Constant *Values[MaxCellSize];

    };

    LatticeCell() : Kind(Top), Size(0), IsSpecial(false) {

      for (const Constant *&Value : Values)

        Value = nullptr;

    }

    bool meet(const LatticeCell &L);

    bool add(const Constant *C);

    bool add(uint32_t Property);

    uint32_t properties() const;

    unsigned size() const { return Size; }

    LatticeCell(const LatticeCell &L) {

      // This memcpy also copies Properties (when L.Size == 0).

      uint32_t N =

          L.IsSpecial ? sizeof L.Properties : L.Size * sizeof(const Constant *);

      memcpy(Values, L.Values, N);

      Kind = L.Kind;

      Size = L.Size;

      IsSpecial = L.IsSpecial;

    }

    LatticeCell &operator=(const LatticeCell &L) {

      if (this != &L) {

        // This memcpy also copies Properties (when L.Size == 0).

        uint32_t N = L.IsSpecial ? sizeof L.Properties

                                 : L.Size * sizeof(const Constant *);

        memcpy(Values, L.Values, N);

        Kind = L.Kind;

        Size = L.Size;

        IsSpecial = L.IsSpecial;

      }

      return *this;

    }

    bool isSingle() const { return size() == 1; }

    bool isProperty() const { return IsSpecial; }

    bool isTop() const { return Kind == Top; }

    bool isBottom() const { return Kind == Bottom; }

    bool setBottom() {

      bool Changed = (Kind != Bottom);

      Kind = Bottom;

      Size = 0;

      IsSpecial = false;

      return Changed;

    }

    void print(raw_ostream &os) const;

  private:

    void setProperty() {

      IsSpecial = true;

      Size = 0;

      Kind = Normal;

    }

    bool convertToProperty();

  };

#ifndef NDEBUG

  raw_ostream &operator<< (raw_ostream &os, const LatticeCell &L) {

    L.print(os);

    return os;

  }

#endif

  class MachineConstEvaluator;

  class MachineConstPropagator {

  public:

    MachineConstPropagator(MachineConstEvaluator &E) : MCE(E) {

      Bottom.setBottom();

    }

    // Mapping: vreg -> cell

    // The keys are registers _without_ subregisters. This won't allow

    // definitions in the form of "vreg:subreg = ...". Such definitions

    // would be questionable from the point of view of SSA, since the "vreg"

    // could not be initialized in its entirety (specifically, an instruction

    // defining the "other part" of "vreg" would also count as a definition

    // of "vreg", which would violate the SSA).

    // If a value of a pair vreg:subreg needs to be obtained, the cell for

    // "vreg" needs to be looked up, and then the value of subregister "subreg"

    // needs to be evaluated.

    class CellMap {

    public:

      CellMap() {

        assert(Top.isTop());

        Bottom.setBottom();

      }

      void clear() { Map.clear(); }

      bool has(Register R) const {

        // All non-virtual registers are considered "bottom".

        if (!R.isVirtual())

          return true;

        MapType::const_iterator F = Map.find(R);

        return F != Map.end();

      }

      const LatticeCell &get(Register R) const {

        if (!R.isVirtual())

          return Bottom;

        MapType::const_iterator F = Map.find(R);

        if (F != Map.end())

          return F->second;

        return Top;

      }

      // Invalidates any const references.

      void update(Register R, const LatticeCell &L) { Map[R] = L; }

      void print(raw_ostream &os, const TargetRegisterInfo &TRI) const;

    private:

      using MapType = std::map<Register, LatticeCell>;

      MapType Map;

      // To avoid creating "top" entries, return a const reference to

      // this cell in "get". Also, have a "Bottom" cell to return from

      // get when a value of a physical register is requested.

      LatticeCell Top, Bottom;

    public:

      using const_iterator = MapType::const_iterator;

      const_iterator begin() const { return Map.begin(); }

      const_iterator end() const { return Map.end(); }

    };

    bool run(MachineFunction &MF);

  private:

    void visitPHI(const MachineInstr &PN);

    void visitNonBranch(const MachineInstr &MI);

    void visitBranchesFrom(const MachineInstr &BrI);

    void visitUsesOf(unsigned R);

    bool computeBlockSuccessors(const MachineBasicBlock *MB,

          SetVector<const MachineBasicBlock*> &Targets);

    void removeCFGEdge(MachineBasicBlock *From, MachineBasicBlock *To);

    void propagate(MachineFunction &MF);

    bool rewrite(MachineFunction &MF);

    MachineRegisterInfo      *MRI = nullptr;

    MachineConstEvaluator    &MCE;

    using CFGEdge = std::pair<unsigned, unsigned>;

    using SetOfCFGEdge = std::set<CFGEdge>;

    using SetOfInstr = std::set<const MachineInstr *>;

    using QueueOfCFGEdge = std::queue<CFGEdge>;

    LatticeCell     Bottom;

    CellMap         Cells;

    SetOfCFGEdge    EdgeExec;

    SetOfInstr      InstrExec;

    QueueOfCFGEdge  FlowQ;

  };

  // The "evaluator/rewriter" of machine instructions. This is an abstract

  // base class that provides the interface that the propagator will use,

  // as well as some helper functions that are target-independent.

  class MachineConstEvaluator {

  public:

    MachineConstEvaluator(MachineFunction &Fn)

      : TRI(*Fn.getSubtarget().getRegisterInfo()),

        MF(Fn), CX(Fn.getFunction().getContext()) {}

    virtual ~MachineConstEvaluator() = default;

    // The required interface:

    // - A set of three "evaluate" functions. Each returns "true" if the

    //       computation succeeded, "false" otherwise.

    //   (1) Given an instruction MI, and the map with input values "Inputs",

    //       compute the set of output values "Outputs". An example of when

    //       the computation can "fail" is if MI is not an instruction that

    //       is recognized by the evaluator.

    //   (2) Given a register R (as reg:subreg), compute the cell that

    //       corresponds to the "subreg" part of the given register.

    //   (3) Given a branch instruction BrI, compute the set of target blocks.

    //       If the branch can fall-through, add null (0) to the list of

    //       possible targets.

    // - A function "rewrite", that given the cell map after propagation,

    //   could rewrite instruction MI in a more beneficial form. Return

    //   "true" if a change has been made, "false" otherwise.

    using CellMap = MachineConstPropagator::CellMap;

    virtual bool evaluate(const MachineInstr &MI, const CellMap &Inputs,

                          CellMap &Outputs) = 0;

    virtual bool evaluate(const RegisterSubReg &R, const LatticeCell &SrcC,

                          LatticeCell &Result) = 0;

    virtual bool evaluate(const MachineInstr &BrI, const CellMap &Inputs,

                          SetVector<const MachineBasicBlock*> &Targets,

                          bool &CanFallThru) = 0;

    virtual bool rewrite(MachineInstr &MI, const CellMap &Inputs) = 0;

    const TargetRegisterInfo &TRI;

  protected:

    MachineFunction &MF;

    LLVMContext     &CX;

    struct Comparison {

      enum {

        Unk = 0x00,

        EQ  = 0x01,

        NE  = 0x02,

        L   = 0x04, // Less-than property.

        G   = 0x08, // Greater-than property.

        U   = 0x40, // Unsigned property.

        LTs = L,

        LEs = L | EQ,

        GTs = G,

        GEs = G | EQ,

        LTu = L      | U,

        LEu = L | EQ | U,

        GTu = G      | U,

        GEu = G | EQ | U

      };

      static uint32_t negate(uint32_t Cmp) {

        if (Cmp == EQ)

          return NE;

        if (Cmp == NE)

          return EQ;

        assert((Cmp & (L|G)) != (L|G));

        return Cmp ^ (L|G);

      }

    };

    // Helper functions.

    bool getCell(const RegisterSubReg &R, const CellMap &Inputs, LatticeCell &RC);

    bool constToInt(const Constant *C, APInt &Val) const;

    const ConstantInt *intToConst(const APInt &Val) const;

    // Compares.

    bool evaluateCMPrr(uint32_t Cmp, const RegisterSubReg &R1, const RegisterSubReg &R2,

          const CellMap &Inputs, bool &Result);

    bool evaluateCMPri(uint32_t Cmp, const RegisterSubReg &R1, const APInt &A2,

          const CellMap &Inputs, bool &Result);

    bool evaluateCMPrp(uint32_t Cmp, const RegisterSubReg &R1, uint64_t Props2,

          const CellMap &Inputs, bool &Result);

    bool evaluateCMPii(uint32_t Cmp, const APInt &A1, const APInt &A2,

          bool &Result);

    bool evaluateCMPpi(uint32_t Cmp, uint32_t Props, const APInt &A2,

          bool &Result);

    bool evaluateCMPpp(uint32_t Cmp, uint32_t Props1, uint32_t Props2,

          bool &Result);

    bool evaluateCOPY(const RegisterSubReg &R1, const CellMap &Inputs,

          LatticeCell &Result);

    // Logical operations.

    bool evaluateANDrr(const RegisterSubReg &R1, const RegisterSubReg &R2,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateANDri(const RegisterSubReg &R1, const APInt &A2,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateANDii(const APInt &A1, const APInt &A2, APInt &Result);

    bool evaluateORrr(const RegisterSubReg &R1, const RegisterSubReg &R2,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateORri(const RegisterSubReg &R1, const APInt &A2,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateORii(const APInt &A1, const APInt &A2, APInt &Result);

    bool evaluateXORrr(const RegisterSubReg &R1, const RegisterSubReg &R2,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateXORri(const RegisterSubReg &R1, const APInt &A2,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateXORii(const APInt &A1, const APInt &A2, APInt &Result);

    // Extensions.

    bool evaluateZEXTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateZEXTi(const APInt &A1, unsigned Width, unsigned Bits,

          APInt &Result);

    bool evaluateSEXTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateSEXTi(const APInt &A1, unsigned Width, unsigned Bits,

          APInt &Result);

    // Leading/trailing bits.

    bool evaluateCLBr(const RegisterSubReg &R1, bool Zeros, bool Ones,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateCLBi(const APInt &A1, bool Zeros, bool Ones, APInt &Result);

    bool evaluateCTBr(const RegisterSubReg &R1, bool Zeros, bool Ones,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateCTBi(const APInt &A1, bool Zeros, bool Ones, APInt &Result);

    // Bitfield extract.

    bool evaluateEXTRACTr(const RegisterSubReg &R1, unsigned Width, unsigned Bits,

          unsigned Offset, bool Signed, const CellMap &Inputs,

          LatticeCell &Result);

    bool evaluateEXTRACTi(const APInt &A1, unsigned Bits, unsigned Offset,

          bool Signed, APInt &Result);

    // Vector operations.

    bool evaluateSplatr(const RegisterSubReg &R1, unsigned Bits, unsigned Count,

          const CellMap &Inputs, LatticeCell &Result);

    bool evaluateSplati(const APInt &A1, unsigned Bits, unsigned Count,

          APInt &Result);

  };

} // end anonymous namespace

uint32_t ConstantProperties::deduce(const Constant *C) {

  if (isa<ConstantInt>(C)) {

    const ConstantInt *CI = cast<ConstantInt>(C);

    if (CI->isZero())

      return Zero | PosOrZero | NegOrZero | Finite;

    uint32_t Props = (NonZero | Finite);

    if (CI->isNegative())

      return Props | NegOrZero;

    return Props | PosOrZero;

  }

  if (isa<ConstantFP>(C)) {

    const ConstantFP *CF = cast<ConstantFP>(C);

    uint32_t Props = CF->isNegative() ? (NegOrZero|NonZero)

                                      : PosOrZero;

    if (CF->isZero())

      return (Props & ~NumericProperties) | (Zero|Finite);

    Props = (Props & ~NumericProperties) | NonZero;

    if (CF->isNaN())

      return (Props & ~NumericProperties) | NaN;

    const APFloat &Val = CF->getValueAPF();

    if (Val.isInfinity())

      return (Props & ~NumericProperties) | Infinity;

    Props |= Finite;

    return Props;

  }

  return Unknown;

}

// Convert a cell from a set of specific values to a cell that tracks

// properties.

bool LatticeCell::convertToProperty() {

  if (isProperty())

    return false;

  // Corner case: converting a fresh (top) cell to "special".

  // This can happen, when adding a property to a top cell.

  uint32_t Everything = ConstantProperties::Everything;

  uint32_t Ps = !isTop() ? properties()

                         : Everything;

  if (Ps != ConstantProperties::Unknown) {

    Properties = Ps;

    setProperty();

  } else {

    setBottom();

  }

  return true;

}

#ifndef NDEBUG

void LatticeCell::print(raw_ostream &os) const {

  if (isProperty()) {

    os << "{ ";

    uint32_t Ps = properties();

    if (Ps & ConstantProperties::Zero)

      os << "zero ";

    if (Ps & ConstantProperties::NonZero)

      os << "nonzero ";

    if (Ps & ConstantProperties::Finite)

      os << "finite ";

    if (Ps & ConstantProperties::Infinity)

      os << "infinity ";

    if (Ps & ConstantProperties::NaN)

      os << "nan ";

    if (Ps & ConstantProperties::PosOrZero)

      os << "poz ";

    if (Ps & ConstantProperties::NegOrZero)

      os << "nez ";

    os << '}';

    return;

  }

  os << "{ ";

  if (isBottom()) {

    os << "bottom";

  } else if (isTop()) {

    os << "top";

  } else {

    for (unsigned i = 0; i < size(); ++i) {

      const Constant *C = Values[i];

      if (i != 0)

        os << ", ";

      C->print(os);

    }

  }

  os << " }";

}

#endif

// "Meet" operation on two cells. This is the key of the propagation

// algorithm.

bool LatticeCell::meet(const LatticeCell &L) {

  bool Changed = false;

  if (L.isBottom())

    Changed = setBottom();

  if (isBottom() || L.isTop())

    return Changed;

  if (isTop()) {

    *this = L;

    // L can be neither Top nor Bottom, so *this must have changed.

    return true;

  }

  // Top/bottom cases covered. Need to integrate L's set into ours.

  if (L.isProperty())

    return add(L.properties());

  for (unsigned i = 0; i < L.size(); ++i) {

    const Constant *LC = L.Values[i];

    Changed |= add(LC);

  }

  return Changed;

}

// Add a new constant to the cell. This is actually where the cell update

// happens. If a cell has room for more constants, the new constant is added.

// Otherwise, the cell is converted to a "property" cell (i.e. a cell that

// will track properties of the associated values, and not the values

// themselves. Care is taken to handle special cases, like "bottom", etc.

bool LatticeCell::add(const Constant *LC) {

  assert(LC);

  if (isBottom())

    return false;

  if (!isProperty()) {

    // Cell is not special. Try to add the constant here first,

    // if there is room.

    unsigned Index = 0;

    while (Index < Size) {

      const Constant *C = Values[Index];

      // If the constant is already here, no change is needed.

      if (C == LC)

        return false;

      Index++;

    }

    if (Index < MaxCellSize) {

      Values[Index] = LC;

      Kind = Normal;

      Size++;

      return true;

    }

  }

  bool Changed = false;

  // This cell is special, or is not special, but is full. After this

  // it will be special.

  Changed = convertToProperty();

  uint32_t Ps = properties();

  uint32_t NewPs = Ps & ConstantProperties::deduce(LC);

  if (NewPs == ConstantProperties::Unknown) {

    setBottom();

    return true;

  }

  if (Ps != NewPs) {

    Properties = NewPs;

    Changed = true;

  }

  return Changed;

}

// Add a property to the cell. This will force the cell to become a property-

// tracking cell.

bool LatticeCell::add(uint32_t Property) {

  bool Changed = convertToProperty();

  uint32_t Ps = properties();

  if (Ps == (Ps & Property))

    return Changed;

  Properties = Property & Ps;

  return true;

}

// Return the properties of the values in the cell. This is valid for any

// cell, and does not alter the cell itself.

uint32_t LatticeCell::properties() const {

  if (isProperty())

    return Properties;

  assert(!isTop() && "Should not call this for a top cell");

  if (isBottom())

    return ConstantProperties::Unknown;

  assert(size() > 0 && "Empty cell");

  uint32_t Ps = ConstantProperties::deduce(Values[0]);

  for (unsigned i = 1; i < size(); ++i) {

    if (Ps == ConstantProperties::Unknown)

      break;

    Ps &= ConstantProperties::deduce(Values[i]);

  }

  return Ps;

}

#ifndef NDEBUG

void MachineConstPropagator::CellMap::print(raw_ostream &os,

      const TargetRegisterInfo &TRI) const {

  for (auto &I : Map)

    dbgs() << "  " << printReg(I.first, &TRI) << " -> " << I.second << '\n';

}

#endif

void MachineConstPropagator::visitPHI(const MachineInstr &PN) {

  const MachineBasicBlock *MB = PN.getParent();

  unsigned MBN = MB->getNumber();

  LLVM_DEBUG(dbgs() << "Visiting FI(" << printMBBReference(*MB) << "): " << PN);

  const MachineOperand &MD = PN.getOperand(0);

  RegisterSubReg DefR(MD);

  assert(DefR.Reg.isVirtual());

  bool Changed = false;

  // If the def has a sub-register, set the corresponding cell to "bottom".

  if (DefR.SubReg) {

Bottomize:

    const LatticeCell &T = Cells.get(DefR.Reg);

    Changed = !T.isBottom();

    Cells.update(DefR.Reg, Bottom);

    if (Changed)

      visitUsesOf(DefR.Reg);

    return;

  }

  LatticeCell DefC = Cells.get(DefR.Reg);

  for (unsigned i = 1, n = PN.getNumOperands(); i < n; i += 2) {

    const MachineBasicBlock *PB = PN.getOperand(i+1).getMBB();

    unsigned PBN = PB->getNumber();

    if (!EdgeExec.count(CFGEdge(PBN, MBN))) {

      LLVM_DEBUG(dbgs() << "  edge " << printMBBReference(*PB) << "->"

                        << printMBBReference(*MB) << " not executable\n");

      continue;

    }

    const MachineOperand &SO = PN.getOperand(i);

    RegisterSubReg UseR(SO);

    // If the input is not a virtual register, we don't really know what

    // value it holds.

    if (!UseR.Reg.isVirtual())

      goto Bottomize;

    // If there is no cell for an input register, it means top.

    if (!Cells.has(UseR.Reg))

      continue;

    LatticeCell SrcC;

    bool Eval = MCE.evaluate(UseR, Cells.get(UseR.Reg), SrcC);

    LLVM_DEBUG(dbgs() << "  edge from " << printMBBReference(*PB) << ": "

                      << printReg(UseR.Reg, &MCE.TRI, UseR.SubReg) << SrcC

                      << '\n');

    Changed |= Eval ? DefC.meet(SrcC)

                    : DefC.setBottom();

    Cells.update(DefR.Reg, DefC);

    if (DefC.isBottom())

      break;

  }

  if (Changed)

    visitUsesOf(DefR.Reg);

}

void MachineConstPropagator::visitNonBranch(const MachineInstr &MI) {

  LLVM_DEBUG(dbgs() << "Visiting MI(" << printMBBReference(*MI.getParent())

                    << "): " << MI);

  CellMap Outputs;

  bool Eval = MCE.evaluate(MI, Cells, Outputs);

  LLVM_DEBUG({

    if (Eval) {

      dbgs() << "  outputs:";

      for (auto &I : Outputs)

        dbgs() << ' ' << I.second;

      dbgs() << '\n';

    }

  });

  // Update outputs. If the value was not computed, set all the

  // def cells to bottom.

  for (const MachineOperand &MO : MI.operands()) {

    if (!MO.isReg() || !MO.isDef())

      continue;

    RegisterSubReg DefR(MO);

    // Only track virtual registers.

    if (!DefR.Reg.isVirtual())

      continue;

    bool Changed = false;

    // If the evaluation failed, set cells for all output registers to bottom.

    if (!Eval) {

      const LatticeCell &T = Cells.get(DefR.Reg);

      Changed = !T.isBottom();

      Cells.update(DefR.Reg, Bottom);

    } else {

      // Find the corresponding cell in the computed outputs.

      // If it's not there, go on to the next def.

      if (!Outputs.has(DefR.Reg))

        continue;

      LatticeCell RC = Cells.get(DefR.Reg);

      Changed = RC.meet(Outputs.get(DefR.Reg));

      Cells.update(DefR.Reg, RC);

    }

    if (Changed)

      visitUsesOf(DefR.Reg);

  }

}

// Starting at a given branch, visit remaining branches in the block.

// Traverse over the subsequent branches for as long as the preceding one

// can fall through. Add all the possible targets to the flow work queue,

// including the potential fall-through to the layout-successor block.

void MachineConstPropagator::visitBranchesFrom(const MachineInstr &BrI) {

  const MachineBasicBlock &B = *BrI.getParent();

  unsigned MBN = B.getNumber();

  MachineBasicBlock::const_iterator It = BrI.getIterator();

  MachineBasicBlock::const_iterator End = B.end();

  SetVector<const MachineBasicBlock*> Targets;

  bool EvalOk = true, FallsThru = true;

  while (It != End) {

    const MachineInstr &MI = *It;

    InstrExec.insert(&MI);

    LLVM_DEBUG(dbgs() << "Visiting " << (EvalOk ? "BR" : "br") << "("

                      << printMBBReference(B) << "): " << MI);

    // Do not evaluate subsequent branches if the evaluation of any of the

    // previous branches failed. Keep iterating over the branches only

    // to mark them as executable.

    EvalOk = EvalOk && MCE.evaluate(MI, Cells, Targets, FallsThru);

    if (!EvalOk)

      FallsThru = true;

    if (!FallsThru)

      break;

    ++It;

  }

  if (B.mayHaveInlineAsmBr())

    EvalOk = false;

  if (EvalOk) {

    // Need to add all CFG successors that lead to EH landing pads.

    // There won't be explicit branches to these blocks, but they must

    // be processed.

    for (const MachineBasicBlock *SB : B.successors()) {

      if (SB->isEHPad())

        Targets.insert(SB);

    }

    if (FallsThru) {

      const MachineFunction &MF = *B.getParent();

      MachineFunction::const_iterator BI = B.getIterator();

      MachineFunction::const_iterator Next = std::next(BI);

      if (Next != MF.end())

        Targets.insert(&*Next);

    }

  } else {

    // If the evaluation of the branches failed, make "Targets" to be the

    // set of all successors of the block from the CFG.

    // If the evaluation succeeded for all visited branches, then if the

    // last one set "FallsThru", then add an edge to the layout successor

    // to the targets.

    Targets.clear();

    LLVM_DEBUG(dbgs() << "  failed to evaluate a branch...adding all CFG "

                         "successors\n");

    for (const MachineBasicBlock *SB : B.successors())

      Targets.insert(SB);

  }

  for (const MachineBasicBlock *TB : Targets) {

    unsigned TBN = TB->getNumber();

    LLVM_DEBUG(dbgs() << "  pushing edge " << printMBBReference(B) << " -> "

                      << printMBBReference(*TB) << "\n");

    FlowQ.push(CFGEdge(MBN, TBN));

  }

}

void MachineConstPropagator::visitUsesOf(unsigned Reg) {

  LLVM_DEBUG(dbgs() << "Visiting uses of " << printReg(Reg, &MCE.TRI)

                    << Cells.get(Reg) << '\n');

  for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {

    // Do not process non-executable instructions. They can become exceutable

    // later (via a flow-edge in the work queue). In such case, the instruc-

    // tion will be visited at that time.

    if (!InstrExec.count(&MI))

      continue;

    if (MI.isPHI())

      visitPHI(MI);

    else if (!MI.isBranch())

      visitNonBranch(MI);

    else

      visitBranchesFrom(MI);

  }

}

bool MachineConstPropagator::computeBlockSuccessors(const MachineBasicBlock *MB,

      SetVector<const MachineBasicBlock*> &Targets) {

  Targets.clear();

  MachineBasicBlock::const_iterator FirstBr = MB->end();

  for (const MachineInstr &MI : *MB) {

    if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)

      return false;

    if (MI.isDebugInstr())

      continue;

    if (MI.isBranch()) {

      FirstBr = MI.getIterator();

      break;

    }

  }

  MachineBasicBlock::const_iterator End = MB->end();

  bool DoNext = true;

  for (MachineBasicBlock::const_iterator I = FirstBr; I != End; ++I) {

    const MachineInstr &MI = *I;

    // Can there be debug instructions between branches?

    if (MI.isDebugInstr())

      continue;

    if (!InstrExec.count(&MI))

      continue;

    bool Eval = MCE.evaluate(MI, Cells, Targets, DoNext);

    if (!Eval)

      return false;

    if (!DoNext)

      break;

  }

  // If the last branch could fall-through, add block's layout successor.

  if (DoNext) {

    MachineFunction::const_iterator BI = MB->getIterator();

    MachineFunction::const_iterator NextI = std::next(BI);

    if (NextI != MB->getParent()->end())

      Targets.insert(&*NextI);

  }

  // Add all the EH landing pads.

  for (const MachineBasicBlock *SB : MB->successors())

    if (SB->isEHPad())

      Targets.insert(SB);

  return true;

}

void MachineConstPropagator::removeCFGEdge(MachineBasicBlock *From,

      MachineBasicBlock *To) {

  // First, remove the CFG successor/predecessor information.

  From->removeSuccessor(To);

  // Remove all corresponding PHI operands in the To block.

  for (MachineInstr &PN : To->phis()) {

    // reg0 = PHI reg1, bb2, reg3, bb4, ...

    int N = PN.getNumOperands() - 2;

    while (N > 0) {

      if (PN.getOperand(N + 1).getMBB() == From) {

        PN.removeOperand(N + 1);

        PN.removeOperand(N);

      }

      N -= 2;

    }

  }

}

void MachineConstPropagator::propagate(MachineFunction &MF) {

  MachineBasicBlock *Entry = GraphTraits<MachineFunction*>::getEntryNode(&MF);

  unsigned EntryNum = Entry->getNumber();

  // Start with a fake edge, just to process the entry node.

  FlowQ.push(CFGEdge(EntryNum, EntryNum));

  while (!FlowQ.empty()) {

    CFGEdge Edge = FlowQ.front();

    FlowQ.pop();

    LLVM_DEBUG(

        dbgs() << "Picked edge "

               << printMBBReference(*MF.getBlockNumbered(Edge.first)) << "->"

               << printMBBReference(*MF.getBlockNumbered(Edge.second)) << '\n');

    if (Edge.first != EntryNum)

      if (EdgeExec.count(Edge))

        continue;

    EdgeExec.insert(Edge);

    MachineBasicBlock *SB = MF.getBlockNumbered(Edge.second);

    // Process the block in three stages:

    // - visit all PHI nodes,

    // - visit all non-branch instructions,

    // - visit block branches.

    MachineBasicBlock::const_iterator It = SB->begin(), End = SB->end();

    // Visit PHI nodes in the successor block.

    while (It != End && It->isPHI()) {

      InstrExec.insert(&*It);

      visitPHI(*It);

      ++It;

    }

    // If the successor block just became executable, visit all instructions.

    // To see if this is the first time we're visiting it, check the first

    // non-debug instruction to see if it is executable.

    while (It != End && It->isDebugInstr())

      ++It;

    assert(It == End || !It->isPHI());

    // If this block has been visited, go on to the next one.

    if (It != End && InstrExec.count(&*It))

      continue;

    // For now, scan all non-branch instructions. Branches require different

    // processing.

    while (It != End && !It->isBranch()) {

      if (!It->isDebugInstr()) {

        InstrExec.insert(&*It);

        visitNonBranch(*It);

      }

      ++It;

    }

    // Time to process the end of the block. This is different from

    // processing regular (non-branch) instructions, because there can

    // be multiple branches in a block, and they can cause the block to

    // terminate early.

    if (It != End) {

      visitBranchesFrom(*It);

    } else {

      // If the block didn't have a branch, add all successor edges to the

      // work queue. (There should really be only one successor in such case.)

      unsigned SBN = SB->getNumber();

      for (const MachineBasicBlock *SSB : SB->successors())

        FlowQ.push(CFGEdge(SBN, SSB->getNumber()));

    }

  } // while (FlowQ)

  LLVM_DEBUG({

    dbgs() << "Cells after propagation:\n";

    Cells.print(dbgs(), MCE.TRI);

    dbgs() << "Dead CFG edges:\n";

    for (const MachineBasicBlock &B : MF) {

      unsigned BN = B.getNumber();

      for (const MachineBasicBlock *SB : B.successors()) {

        unsigned SN = SB->getNumber();

        if (!EdgeExec.count(CFGEdge(BN, SN)))

          dbgs() << "  " << printMBBReference(B) << " -> "

                 << printMBBReference(*SB) << '\n';

      }

    }

  });

}

bool MachineConstPropagator::rewrite(MachineFunction &MF) {

  bool Changed = false;

  // Rewrite all instructions based on the collected cell information.

  //

  // Traverse the instructions in a post-order, so that rewriting an

  // instruction can make changes "downstream" in terms of control-flow

  // without affecting the rewriting process. (We should not change

  // instructions that have not yet been visited by the rewriter.)

  // The reason for this is that the rewriter can introduce new vregs,

  // and replace uses of old vregs (which had corresponding cells

  // computed during propagation) with these new vregs (which at this

  // point would not have any cells, and would appear to be "top").

  // If an attempt was made to evaluate an instruction with a fresh

  // "top" vreg, it would cause an error (abend) in the evaluator.

  // Collect the post-order-traversal block ordering. The subsequent

  // traversal/rewrite will update block successors, so it's safer

  // if the visiting order it computed ahead of time.

  std::vector<MachineBasicBlock*> POT;

  for (MachineBasicBlock *B : post_order(&MF))

    if (!B->empty())

      POT.push_back(B);

  for (MachineBasicBlock *B : POT) {

    // Walk the block backwards (which usually begin with the branches).

    // If any branch is rewritten, we may need to update the successor

    // information for this block. Unless the block's successors can be

    // precisely determined (which may not be the case for indirect

    // branches), we cannot modify any branch.

    // Compute the successor information.

    SetVector<const MachineBasicBlock*> Targets;

    bool HaveTargets = computeBlockSuccessors(B, Targets);

    // Rewrite the executable instructions. Skip branches if we don't

    // have block successor information.

    for (MachineInstr &MI : llvm::reverse(*B)) {

      if (InstrExec.count(&MI)) {

        if (MI.isBranch() && !HaveTargets)

          continue;

        Changed |= MCE.rewrite(MI, Cells);

      }

    }

    // The rewriting could rewrite PHI nodes to non-PHI nodes, causing

    // regular instructions to appear in between PHI nodes. Bring all

    // the PHI nodes to the beginning of the block.

    for (auto I = B->begin(), E = B->end(); I != E; ++I) {

      if (I->isPHI())

        continue;