//===--- HexagonGenPredicate.cpp ------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "gen-pred"

#include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "HexagonTargetMachine.h"

#include <functional>
#include <queue>
#include <set>
#include <vector>

using namespace llvm;

namespace llvm {
  void initializeHexagonGenPredicatePass(PassRegistry& Registry);
  FunctionPass *createHexagonGenPredicate();
}

namespace {
  struct Register {
    unsigned R, S;
    Register(unsigned r = 0, unsigned s = 0) : R(r), S(s) {}
    Register(const MachineOperand &MO) : R(MO.getReg()), S(MO.getSubReg()) {}
    bool operator== (const Register &Reg) const {
      return R == Reg.R && S == Reg.S;
    }
    bool operator< (const Register &Reg) const {
      return R < Reg.R || (R == Reg.R && S < Reg.S);
    }
  };
  struct PrintRegister {
    PrintRegister(Register R, const TargetRegisterInfo &I) : Reg(R), TRI(I) {}
    friend raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR);
  private:
    Register Reg;
    const TargetRegisterInfo &TRI;
  };
  raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR)
    LLVM_ATTRIBUTE_UNUSED;
  raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR) {
    return OS << PrintReg(PR.Reg.R, &PR.TRI, PR.Reg.S);
  }

  class HexagonGenPredicate : public MachineFunctionPass {
  public:
    static char ID;
    HexagonGenPredicate() : MachineFunctionPass(ID), TII(0), TRI(0), MRI(0) {
      initializeHexagonGenPredicatePass(*PassRegistry::getPassRegistry());
    }
    virtual const char *getPassName() const {
      return "Hexagon generate predicate operations";
    }
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<MachineDominatorTree>();
      AU.addPreserved<MachineDominatorTree>();
      MachineFunctionPass::getAnalysisUsage(AU);
    }
    virtual bool runOnMachineFunction(MachineFunction &MF);

  private:
    typedef SetVector<MachineInstr*> VectOfInst;
    typedef std::set<Register> SetOfReg;
    typedef std::map<Register,Register> RegToRegMap;

    const HexagonInstrInfo *TII;
    const HexagonRegisterInfo *TRI;
    MachineRegisterInfo *MRI;
    SetOfReg PredGPRs;
    VectOfInst PUsers;
    RegToRegMap G2P;

    bool isPredReg(unsigned R);
    void collectPredicateGPR(MachineFunction &MF);
    void processPredicateGPR(const Register &Reg);
    unsigned getPredForm(unsigned Opc);
    bool isConvertibleToPredForm(const MachineInstr *MI);
    bool isScalarCmp(unsigned Opc);
    bool isScalarPred(Register PredReg);
    Register getPredRegFor(const Register &Reg);
    bool convertToPredForm(MachineInstr *MI);
    bool eliminatePredCopies(MachineFunction &MF);
  };

  char HexagonGenPredicate::ID = 0;
}

INITIALIZE_PASS_BEGIN(HexagonGenPredicate, "hexagon-gen-pred",
  "Hexagon generate predicate operations", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_END(HexagonGenPredicate, "hexagon-gen-pred",
  "Hexagon generate predicate operations", false, false)

bool HexagonGenPredicate::isPredReg(unsigned R) {
  if (!TargetRegisterInfo::isVirtualRegister(R))
    return false;
  const TargetRegisterClass *RC = MRI->getRegClass(R);
  return RC == &Hexagon::PredRegsRegClass;
}


unsigned HexagonGenPredicate::getPredForm(unsigned Opc) {
  using namespace Hexagon;

  switch (Opc) {
    case A2_and:
    case A2_andp:
      return C2_and;
    case A4_andn:
    case A4_andnp:
      return C2_andn;
    case M4_and_and:
      return C4_and_and;
    case M4_and_andn:
      return C4_and_andn;
    case M4_and_or:
      return C4_and_or;

    case A2_or:
    case A2_orp:
      return C2_or;
    case A4_orn:
    case A4_ornp:
      return C2_orn;
    case M4_or_and:
      return C4_or_and;
    case M4_or_andn:
      return C4_or_andn;
    case M4_or_or:
      return C4_or_or;

    case A2_xor:
    case A2_xorp:
      return C2_xor;

    case C2_tfrrp:
      return COPY;
  }
  // The opcode corresponding to 0 is TargetOpcode::PHI. We can use 0 here
  // to denote "none", but we need to make sure that none of the valid opcodes
  // that we return will ever be 0.
  assert(PHI == 0 && "Use different value for <none>");
  return 0;
}


bool HexagonGenPredicate::isConvertibleToPredForm(const MachineInstr *MI) {
  unsigned Opc = MI->getOpcode();
  if (getPredForm(Opc) != 0)
    return true;

  // Comparisons against 0 are also convertible. This does not apply to
  // A4_rcmpeqi or A4_rcmpneqi, since they produce values 0 or 1, which
  // may not match the value that the predicate register would have if
  // it was converted to a predicate form.
  switch (Opc) {
    case Hexagon::C2_cmpeqi:
    case Hexagon::C4_cmpneqi:
      if (MI->getOperand(2).isImm() && MI->getOperand(2).getImm() == 0)
        return true;
      break;
  }
  return false;
}


void HexagonGenPredicate::collectPredicateGPR(MachineFunction &MF) {
  for (MachineFunction::iterator A = MF.begin(), Z = MF.end(); A != Z; ++A) {
    MachineBasicBlock &B = *A;
    for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) {
      MachineInstr *MI = &*I;
      unsigned Opc = MI->getOpcode();
      switch (Opc) {
        case Hexagon::C2_tfrpr:
        case TargetOpcode::COPY:
          if (isPredReg(MI->getOperand(1).getReg())) {
            Register RD = MI->getOperand(0);
            if (TargetRegisterInfo::isVirtualRegister(RD.R))
              PredGPRs.insert(RD);
          }
          break;
      }
    }
  }
}


void HexagonGenPredicate::processPredicateGPR(const Register &Reg) {
  DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": "
               << PrintReg(Reg.R, TRI, Reg.S) << "\n");
  typedef MachineRegisterInfo::use_iterator use_iterator;
  use_iterator I = MRI->use_begin(Reg.R), E = MRI->use_end();
  if (I == E) {
    DEBUG(dbgs() << "Dead reg: " << PrintReg(Reg.R, TRI, Reg.S) << '\n');
    MachineInstr *DefI = MRI->getVRegDef(Reg.R);
    DefI->eraseFromParent();
    return;
  }

  for (; I != E; ++I) {
    MachineInstr *UseI = I->getParent();
    if (isConvertibleToPredForm(UseI))
      PUsers.insert(UseI);
  }
}


Register HexagonGenPredicate::getPredRegFor(const Register &Reg) {
  // Create a predicate register for a given Reg. The newly created register
  // will have its value copied from Reg, so that it can be later used as
  // an operand in other instructions.
  assert(TargetRegisterInfo::isVirtualRegister(Reg.R));
  RegToRegMap::iterator F = G2P.find(Reg);
  if (F != G2P.end())
    return F->second;

  DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": " << PrintRegister(Reg, *TRI));
  MachineInstr *DefI = MRI->getVRegDef(Reg.R);
  assert(DefI);
  unsigned Opc = DefI->getOpcode();
  if (Opc == Hexagon::C2_tfrpr || Opc == TargetOpcode::COPY) {
    assert(DefI->getOperand(0).isDef() && DefI->getOperand(1).isUse());
    Register PR = DefI->getOperand(1);
    G2P.insert(std::make_pair(Reg, PR));
    DEBUG(dbgs() << " -> " << PrintRegister(PR, *TRI) << '\n');
    return PR;
  }

  MachineBasicBlock &B = *DefI->getParent();
  DebugLoc DL = DefI->getDebugLoc();
  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
  unsigned NewPR = MRI->createVirtualRegister(PredRC);

  // For convertible instructions, do not modify them, so that they can
  // be converted later.  Generate a copy from Reg to NewPR.
  if (isConvertibleToPredForm(DefI)) {
    MachineBasicBlock::iterator DefIt = DefI;
    BuildMI(B, std::next(DefIt), DL, TII->get(TargetOpcode::COPY), NewPR)
      .addReg(Reg.R, 0, Reg.S);
    G2P.insert(std::make_pair(Reg, Register(NewPR)));
    DEBUG(dbgs() << " -> !" << PrintRegister(Register(NewPR), *TRI) << '\n');
    return Register(NewPR);
  }

  llvm_unreachable("Invalid argument");
}


bool HexagonGenPredicate::isScalarCmp(unsigned Opc) {
  switch (Opc) {
    case Hexagon::C2_cmpeq:
    case Hexagon::C2_cmpgt:
    case Hexagon::C2_cmpgtu:
    case Hexagon::C2_cmpeqp:
    case Hexagon::C2_cmpgtp:
    case Hexagon::C2_cmpgtup:
    case Hexagon::C2_cmpeqi:
    case Hexagon::C2_cmpgti:
    case Hexagon::C2_cmpgtui:
    case Hexagon::C2_cmpgei:
    case Hexagon::C2_cmpgeui:
    case Hexagon::C4_cmpneqi:
    case Hexagon::C4_cmpltei:
    case Hexagon::C4_cmplteui:
    case Hexagon::C4_cmpneq:
    case Hexagon::C4_cmplte:
    case Hexagon::C4_cmplteu:
    case Hexagon::A4_cmpbeq:
    case Hexagon::A4_cmpbeqi:
    case Hexagon::A4_cmpbgtu:
    case Hexagon::A4_cmpbgtui:
    case Hexagon::A4_cmpbgt:
    case Hexagon::A4_cmpbgti:
    case Hexagon::A4_cmpheq:
    case Hexagon::A4_cmphgt:
    case Hexagon::A4_cmphgtu:
    case Hexagon::A4_cmpheqi:
    case Hexagon::A4_cmphgti:
    case Hexagon::A4_cmphgtui:
      return true;
  }
  return false;
}


bool HexagonGenPredicate::isScalarPred(Register PredReg) {
  std::queue<Register> WorkQ;
  WorkQ.push(PredReg);

  while (!WorkQ.empty()) {
    Register PR = WorkQ.front();
    WorkQ.pop();
    const MachineInstr *DefI = MRI->getVRegDef(PR.R);
    if (!DefI)
      return false;
    unsigned DefOpc = DefI->getOpcode();
    switch (DefOpc) {
      case TargetOpcode::COPY: {
        const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
        if (MRI->getRegClass(PR.R) != PredRC)
          return false;
        // If it is a copy between two predicate registers, fall through.
      }
      case Hexagon::C2_and:
      case Hexagon::C2_andn:
      case Hexagon::C4_and_and:
      case Hexagon::C4_and_andn:
      case Hexagon::C4_and_or:
      case Hexagon::C2_or:
      case Hexagon::C2_orn:
      case Hexagon::C4_or_and:
      case Hexagon::C4_or_andn:
      case Hexagon::C4_or_or:
      case Hexagon::C4_or_orn:
      case Hexagon::C2_xor:
        // Add operands to the queue.
        for (ConstMIOperands Mo(DefI); Mo.isValid(); ++Mo)
          if (Mo->isReg() && Mo->isUse())
            WorkQ.push(Register(Mo->getReg()));
        break;

      // All non-vector compares are ok, everything else is bad.
      default:
        return isScalarCmp(DefOpc);
    }
  }

  return true;
}


bool HexagonGenPredicate::convertToPredForm(MachineInstr *MI) {
  DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": " << MI << " " << *MI);

  unsigned Opc = MI->getOpcode();
  assert(isConvertibleToPredForm(MI));
  unsigned NumOps = MI->getNumOperands();
  for (unsigned i = 0; i < NumOps; ++i) {
    MachineOperand &MO = MI->getOperand(i);
    if (!MO.isReg() || !MO.isUse())
      continue;
    Register Reg(MO);
    if (Reg.S && Reg.S != Hexagon::subreg_loreg)
      return false;
    if (!PredGPRs.count(Reg))
      return false;
  }

  MachineBasicBlock &B = *MI->getParent();
  DebugLoc DL = MI->getDebugLoc();

  unsigned NewOpc = getPredForm(Opc);
  // Special case for comparisons against 0.
  if (NewOpc == 0) {
    switch (Opc) {
      case Hexagon::C2_cmpeqi:
        NewOpc = Hexagon::C2_not;
        break;
      case Hexagon::C4_cmpneqi:
        NewOpc = TargetOpcode::COPY;
        break;
      default:
        return false;
    }

    // If it's a scalar predicate register, then all bits in it are
    // the same. Otherwise, to determine whether all bits are 0 or not
    // we would need to use any8.
    Register PR = getPredRegFor(MI->getOperand(1));
    if (!isScalarPred(PR))
      return false;
    // This will skip the immediate argument when creating the predicate
    // version instruction.
    NumOps = 2;
  }

  // Some sanity: check that def is in operand #0.
  MachineOperand &Op0 = MI->getOperand(0);
  assert(Op0.isDef());
  Register OutR(Op0);

  // Don't use getPredRegFor, since it will create an association between
  // the argument and a created predicate register (i.e. it will insert a
  // copy if a new predicate register is created).
  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
  Register NewPR = MRI->createVirtualRegister(PredRC);
  MachineInstrBuilder MIB = BuildMI(B, MI, DL, TII->get(NewOpc), NewPR.R);

  // Add predicate counterparts of the GPRs.
  for (unsigned i = 1; i < NumOps; ++i) {
    Register GPR = MI->getOperand(i);
    Register Pred = getPredRegFor(GPR);
    MIB.addReg(Pred.R, 0, Pred.S);
  }
  DEBUG(dbgs() << "generated: " << *MIB);

  // Generate a copy-out: NewGPR = NewPR, and replace all uses of OutR
  // with NewGPR.
  const TargetRegisterClass *RC = MRI->getRegClass(OutR.R);
  unsigned NewOutR = MRI->createVirtualRegister(RC);
  BuildMI(B, MI, DL, TII->get(TargetOpcode::COPY), NewOutR)
    .addReg(NewPR.R, 0, NewPR.S);
  MRI->replaceRegWith(OutR.R, NewOutR);
  MI->eraseFromParent();

  // If the processed instruction was C2_tfrrp (i.e. Rn = Pm; Pk = Rn),
  // then the output will be a predicate register.  Do not visit the
  // users of it.
  if (!isPredReg(NewOutR)) {
    Register R(NewOutR);
    PredGPRs.insert(R);
    processPredicateGPR(R);
  }
  return true;
}


bool HexagonGenPredicate::eliminatePredCopies(MachineFunction &MF) {
  DEBUG(dbgs() << LLVM_FUNCTION_NAME << "\n");
  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
  bool Changed = false;
  VectOfInst Erase;

  // First, replace copies
  //   IntR = PredR1
  //   PredR2 = IntR
  // with
  //   PredR2 = PredR1
  // Such sequences can be generated when a copy-into-pred is generated from
  // a gpr register holding a result of a convertible instruction. After
  // the convertible instruction is converted, its predicate result will be
  // copied back into the original gpr.

  for (MachineFunction::iterator A = MF.begin(), Z = MF.end(); A != Z; ++A) {
    MachineBasicBlock &B = *A;
    for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) {
      if (I->getOpcode() != TargetOpcode::COPY)
        continue;
      Register DR = I->getOperand(0);
      Register SR = I->getOperand(1);
      if (!TargetRegisterInfo::isVirtualRegister(DR.R))
        continue;
      if (!TargetRegisterInfo::isVirtualRegister(SR.R))
        continue;
      if (MRI->getRegClass(DR.R) != PredRC)
        continue;
      if (MRI->getRegClass(SR.R) != PredRC)
        continue;
      assert(!DR.S && !SR.S && "Unexpected subregister");
      MRI->replaceRegWith(DR.R, SR.R);
      Erase.insert(I);
      Changed = true;
    }
  }

  for (VectOfInst::iterator I = Erase.begin(), E = Erase.end(); I != E; ++I)
    (*I)->eraseFromParent();

  return Changed;
}


bool HexagonGenPredicate::runOnMachineFunction(MachineFunction &MF) {
  TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
  TRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
  MRI = &MF.getRegInfo();
  PredGPRs.clear();
  PUsers.clear();
  G2P.clear();

  bool Changed = false;
  collectPredicateGPR(MF);
  for (SetOfReg::iterator I = PredGPRs.begin(), E = PredGPRs.end(); I != E; ++I)
    processPredicateGPR(*I);

  bool Again;
  do {
    Again = false;
    VectOfInst Processed, Copy;

    typedef VectOfInst::iterator iterator;
    Copy = PUsers;
    for (iterator I = Copy.begin(), E = Copy.end(); I != E; ++I) {
      MachineInstr *MI = *I;
      bool Done = convertToPredForm(MI);
      if (Done) {
        Processed.insert(MI);
        Again = true;
      }
    }
    Changed |= Again;

    auto Done = [Processed] (MachineInstr *MI) -> bool {
      return Processed.count(MI);
    };
    PUsers.remove_if(Done);
  } while (Again);

  Changed |= eliminatePredCopies(MF);
  return Changed;
}


FunctionPass *llvm::createHexagonGenPredicate() {
  return new HexagonGenPredicate();
}