//===-- HexagonHardwareLoops.cpp - Identify and generate hardware loops ---===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass identifies loops where we can generate the Hexagon hardware
// loop instruction.  The hardware loop can perform loop branches with a
// zero-cycle overhead.
//
// The pattern that defines the induction variable can changed depending on
// prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
// normalizes induction variables, and the Loop Strength Reduction pass
// run by 'llc' may also make changes to the induction variable.
// The pattern detected by this phase is due to running Strength Reduction.
//
// Criteria for hardware loops:
//  - Countable loops (w/ ind. var for a trip count)
//  - Assumes loops are normalized by IndVarSimplify
//  - Try inner-most loops first
//  - No nested hardware loops.
//  - No function calls in loops.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "hwloops"
#include "Hexagon.h"
#include "HexagonTargetMachine.h"
#include "llvm/Constants.h"
#include "llvm/PassSupport.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include <algorithm>

using namespace llvm;

STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");

namespace {
  class CountValue;
  struct HexagonHardwareLoops : public MachineFunctionPass {
    MachineLoopInfo       *MLI;
    MachineRegisterInfo   *MRI;
    const TargetInstrInfo *TII;

  public:
    static char ID;   // Pass identification, replacement for typeid

    HexagonHardwareLoops() : MachineFunctionPass(ID) {}

    virtual bool runOnMachineFunction(MachineFunction &MF);

    const char *getPassName() const { return "Hexagon Hardware Loops"; }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
      AU.addRequired<MachineDominatorTree>();
      AU.addPreserved<MachineDominatorTree>();
      AU.addRequired<MachineLoopInfo>();
      AU.addPreserved<MachineLoopInfo>();
      MachineFunctionPass::getAnalysisUsage(AU);
    }

  private:
    /// getCanonicalInductionVariable - Check to see if the loop has a canonical
    /// induction variable.
    /// Should be defined in MachineLoop. Based upon version in class Loop.
    const MachineInstr *getCanonicalInductionVariable(MachineLoop *L) const;

    /// getTripCount - Return a loop-invariant LLVM register indicating the
    /// number of times the loop will be executed.  If the trip-count cannot
    /// be determined, this return null.
    CountValue *getTripCount(MachineLoop *L) const;

    /// isInductionOperation - Return true if the instruction matches the
    /// pattern for an opertion that defines an induction variable.
    bool isInductionOperation(const MachineInstr *MI, unsigned IVReg) const;

    /// isInvalidOperation - Return true if the instruction is not valid within
    /// a hardware loop.
    bool isInvalidLoopOperation(const MachineInstr *MI) const;

    /// containsInavlidInstruction - Return true if the loop contains an
    /// instruction that inhibits using the hardware loop.
    bool containsInvalidInstruction(MachineLoop *L) const;

    /// converToHardwareLoop - Given a loop, check if we can convert it to a
    /// hardware loop.  If so, then perform the conversion and return true.
    bool convertToHardwareLoop(MachineLoop *L);

  };

  char HexagonHardwareLoops::ID = 0;


  // CountValue class - Abstraction for a trip count of a loop. A
  // smaller vesrsion of the MachineOperand class without the concerns
  // of changing the operand representation.
  class CountValue {
  public:
    enum CountValueType {
      CV_Register,
      CV_Immediate
    };
  private:
    CountValueType Kind;
    union Values {
      unsigned RegNum;
      int64_t ImmVal;
      Values(unsigned r) : RegNum(r) {}
      Values(int64_t i) : ImmVal(i) {}
    } Contents;
    bool isNegative;

  public:
    CountValue(unsigned r, bool neg) : Kind(CV_Register), Contents(r),
                                       isNegative(neg) {}
    explicit CountValue(int64_t i) : Kind(CV_Immediate), Contents(i),
                                     isNegative(i < 0) {}
    CountValueType getType() const { return Kind; }
    bool isReg() const { return Kind == CV_Register; }
    bool isImm() const { return Kind == CV_Immediate; }
    bool isNeg() const { return isNegative; }

    unsigned getReg() const {
      assert(isReg() && "Wrong CountValue accessor");
      return Contents.RegNum;
    }
    void setReg(unsigned Val) {
      Contents.RegNum = Val;
    }
    int64_t getImm() const {
      assert(isImm() && "Wrong CountValue accessor");
      if (isNegative) {
        return -Contents.ImmVal;
      }
      return Contents.ImmVal;
    }
    void setImm(int64_t Val) {
      Contents.ImmVal = Val;
    }

    void print(raw_ostream &OS, const TargetMachine *TM = 0) const {
      if (isReg()) { OS << PrintReg(getReg()); }
      if (isImm()) { OS << getImm(); }
    }
  };

  struct HexagonFixupHwLoops : public MachineFunctionPass {
  public:
    static char ID;     // Pass identification, replacement for typeid.

    HexagonFixupHwLoops() : MachineFunctionPass(ID) {}

    virtual bool runOnMachineFunction(MachineFunction &MF);

    const char *getPassName() const { return "Hexagon Hardware Loop Fixup"; }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
      MachineFunctionPass::getAnalysisUsage(AU);
    }

  private:
    /// Maximum distance between the loop instr and the basic block.
    /// Just an estimate.
    static const unsigned MAX_LOOP_DISTANCE = 200;

    /// fixupLoopInstrs - Check the offset between each loop instruction and
    /// the loop basic block to determine if we can use the LOOP instruction
    /// or if we need to set the LC/SA registers explicitly.
    bool fixupLoopInstrs(MachineFunction &MF);

    /// convertLoopInstr - Add the instruction to set the LC and SA registers
    /// explicitly.
    void convertLoopInstr(MachineFunction &MF,
                          MachineBasicBlock::iterator &MII,
                          RegScavenger &RS);

  };

  char HexagonFixupHwLoops::ID = 0;

} // end anonymous namespace


/// isHardwareLoop - Returns true if the instruction is a hardware loop
/// instruction.
static bool isHardwareLoop(const MachineInstr *MI) {
  return MI->getOpcode() == Hexagon::LOOP0_r ||
    MI->getOpcode() == Hexagon::LOOP0_i;
}

/// isCompareEquals - Returns true if the instruction is a compare equals
/// instruction with an immediate operand.
static bool isCompareEqualsImm(const MachineInstr *MI) {
  return MI->getOpcode() == Hexagon::CMPEQri;
}


/// createHexagonHardwareLoops - Factory for creating
/// the hardware loop phase.
FunctionPass *llvm::createHexagonHardwareLoops() {
  return new HexagonHardwareLoops();
}


bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
  DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");

  bool Changed = false;

  // get the loop information
  MLI = &getAnalysis<MachineLoopInfo>();
  // get the register information
  MRI = &MF.getRegInfo();
  // the target specific instructio info.
  TII = MF.getTarget().getInstrInfo();

  for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
       I != E; ++I) {
    MachineLoop *L = *I;
    if (!L->getParentLoop()) {
      Changed |= convertToHardwareLoop(L);
    }
  }

  return Changed;
}

/// getCanonicalInductionVariable - Check to see if the loop has a canonical
/// induction variable. We check for a simple recurrence pattern - an
/// integer recurrence that decrements by one each time through the loop and
/// ends at zero.  If so, return the phi node that corresponds to it.
///
/// Based upon the similar code in LoopInfo except this code is specific to
/// the machine.
/// This method assumes that the IndVarSimplify pass has been run by 'opt'.
///
const MachineInstr
*HexagonHardwareLoops::getCanonicalInductionVariable(MachineLoop *L) const {
  MachineBasicBlock *TopMBB = L->getTopBlock();
  MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
  assert(PI != TopMBB->pred_end() &&
         "Loop must have more than one incoming edge!");
  MachineBasicBlock *Backedge = *PI++;
  if (PI == TopMBB->pred_end()) return 0;  // dead loop
  MachineBasicBlock *Incoming = *PI++;
  if (PI != TopMBB->pred_end()) return 0;  // multiple backedges?

  // make sure there is one incoming and one backedge and determine which
  // is which.
  if (L->contains(Incoming)) {
    if (L->contains(Backedge))
      return 0;
    std::swap(Incoming, Backedge);
  } else if (!L->contains(Backedge))
    return 0;

  // Loop over all of the PHI nodes, looking for a canonical induction variable:
  //   - The PHI node is "reg1 = PHI reg2, BB1, reg3, BB2".
  //   - The recurrence comes from the backedge.
  //   - the definition is an induction operatio.n
  for (MachineBasicBlock::iterator I = TopMBB->begin(), E = TopMBB->end();
       I != E && I->isPHI(); ++I) {
    const MachineInstr *MPhi = &*I;
    unsigned DefReg = MPhi->getOperand(0).getReg();
    for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
      // Check each operand for the value from the backedge.
      MachineBasicBlock *MBB = MPhi->getOperand(i+1).getMBB();
      if (L->contains(MBB)) { // operands comes from the backedge
        // Check if the definition is an induction operation.
        const MachineInstr *DI = MRI->getVRegDef(MPhi->getOperand(i).getReg());
        if (isInductionOperation(DI, DefReg)) {
          return MPhi;
        }
      }
    }
  }
  return 0;
}

/// getTripCount - Return a loop-invariant LLVM value indicating the
/// number of times the loop will be executed.  The trip count can
/// be either a register or a constant value.  If the trip-count
/// cannot be determined, this returns null.
///
/// We find the trip count from the phi instruction that defines the
/// induction variable.  We follow the links to the CMP instruction
/// to get the trip count.
///
/// Based upon getTripCount in LoopInfo.
///
CountValue *HexagonHardwareLoops::getTripCount(MachineLoop *L) const {
  // Check that the loop has a induction variable.
  const MachineInstr *IV_Inst = getCanonicalInductionVariable(L);
  if (IV_Inst == 0) return 0;

  // Canonical loops will end with a 'cmpeq_ri IV, Imm',
  //  if Imm is 0, get the count from the PHI opnd
  //  if Imm is -M, than M is the count
  //  Otherwise, Imm is the count
  const MachineOperand *IV_Opnd;
  const MachineOperand *InitialValue;
  if (!L->contains(IV_Inst->getOperand(2).getMBB())) {
    InitialValue = &IV_Inst->getOperand(1);
    IV_Opnd = &IV_Inst->getOperand(3);
  } else {
    InitialValue = &IV_Inst->getOperand(3);
    IV_Opnd = &IV_Inst->getOperand(1);
  }

  // Look for the cmp instruction to determine if we
  // can get a useful trip count.  The trip count can
  // be either a register or an immediate.  The location
  // of the value depends upon the type (reg or imm).
  while ((IV_Opnd = IV_Opnd->getNextOperandForReg())) {
    const MachineInstr *MI = IV_Opnd->getParent();
    if (L->contains(MI) && isCompareEqualsImm(MI)) {
      const MachineOperand &MO = MI->getOperand(2);
      assert(MO.isImm() && "IV Cmp Operand should be 0");
      int64_t ImmVal = MO.getImm();

      const MachineInstr *IV_DefInstr = MRI->getVRegDef(IV_Opnd->getReg());
      assert(L->contains(IV_DefInstr->getParent()) &&
             "IV definition should occurs in loop");
      int64_t iv_value = IV_DefInstr->getOperand(2).getImm();

      if (ImmVal == 0) {
        // Make sure the induction variable changes by one on each iteration.
        if (iv_value != 1 && iv_value != -1) {
          return 0;
        }
        return new CountValue(InitialValue->getReg(), iv_value > 0);
      } else {
        assert(InitialValue->isReg() && "Expecting register for init value");
        const MachineInstr *DefInstr = MRI->getVRegDef(InitialValue->getReg());
        if (DefInstr && DefInstr->getOpcode() == Hexagon::TFRI) {
          int64_t count = ImmVal - DefInstr->getOperand(1).getImm();
          if ((count % iv_value) != 0) {
            return 0;
          }
          return new CountValue(count/iv_value);
        }
      }
    }
  }
  return 0;
}

/// isInductionOperation - return true if the operation is matches the
/// pattern that defines an induction variable:
///    add iv, c
///
bool
HexagonHardwareLoops::isInductionOperation(const MachineInstr *MI,
                                           unsigned IVReg) const {
  return (MI->getOpcode() ==
          Hexagon::ADD_ri && MI->getOperand(1).getReg() == IVReg);
}

/// isInvalidOperation - Return true if the operation is invalid within
/// hardware loop.
bool
HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI) const {

  // call is not allowed because the callee may use a hardware loop
  if (MI->getDesc().isCall()) {
    return true;
  }
  // do not allow nested hardware loops
  if (isHardwareLoop(MI)) {
    return true;
  }
  // check if the instruction defines a hardware loop register
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI->getOperand(i);
    if (MO.isReg() && MO.isDef() &&
        (MO.getReg() == Hexagon::LC0 || MO.getReg() == Hexagon::LC1 ||
         MO.getReg() == Hexagon::SA0 || MO.getReg() == Hexagon::SA0)) {
      return true;
    }
  }
  return false;
}

/// containsInvalidInstruction - Return true if the loop contains
/// an instruction that inhibits the use of the hardware loop function.
///
bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const {
  const std::vector<MachineBasicBlock*> Blocks = L->getBlocks();
  for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
    MachineBasicBlock *MBB = Blocks[i];
    for (MachineBasicBlock::iterator
           MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) {
      const MachineInstr *MI = &*MII;
      if (isInvalidLoopOperation(MI)) {
        return true;
      }
    }
  }
  return false;
}

/// converToHardwareLoop - check if the loop is a candidate for
/// converting to a hardware loop.  If so, then perform the
/// transformation.
///
/// This function works on innermost loops first.  A loop can
/// be converted if it is a counting loop; either a register
/// value or an immediate.
///
/// The code makes several assumptions about the representation
/// of the loop in llvm.
bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) {
  bool Changed = false;
  // Process nested loops first.
  for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
    Changed |= convertToHardwareLoop(*I);
  }
  // If a nested loop has been converted, then we can't convert this loop.
  if (Changed) {
    return Changed;
  }
  // Are we able to determine the trip count for the loop?
  CountValue *TripCount = getTripCount(L);
  if (TripCount == 0) {
    return false;
  }
  // Does the loop contain any invalid instructions?
  if (containsInvalidInstruction(L)) {
    return false;
  }
  MachineBasicBlock *Preheader = L->getLoopPreheader();
  // No preheader means there's not place for the loop instr.
  if (Preheader == 0) {
    return false;
  }
  MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();

  MachineBasicBlock *LastMBB = L->getExitingBlock();
  // Don't generate hw loop if the loop has more than one exit.
  if (LastMBB == 0) {
    return false;
  }
  MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();

  // Determine the loop start.
  MachineBasicBlock *LoopStart = L->getTopBlock();
  if (L->getLoopLatch() != LastMBB) {
    // When the exit and latch are not the same, use the latch block as the
    // start.
    // The loop start address is used only after the 1st iteration, and the loop
    // latch may contains instrs. that need to be executed after the 1st iter.
    LoopStart = L->getLoopLatch();
    // Make sure the latch is a successor of the exit, otherwise it won't work.
    if (!LastMBB->isSuccessor(LoopStart)) {
      return false;
    }
  }

  // Convert the loop to a hardware loop
  DEBUG(dbgs() << "Change to hardware loop at "; L->dump());

  if (TripCount->isReg()) {
    // Create a copy of the loop count register.
    MachineFunction *MF = LastMBB->getParent();
    const TargetRegisterClass *RC =
      MF->getRegInfo().getRegClass(TripCount->getReg());
    unsigned CountReg = MF->getRegInfo().createVirtualRegister(RC);
    BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
            TII->get(TargetOpcode::COPY), CountReg).addReg(TripCount->getReg());
    if (TripCount->isNeg()) {
      unsigned CountReg1 = CountReg;
      CountReg = MF->getRegInfo().createVirtualRegister(RC);
      BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
              TII->get(Hexagon::NEG), CountReg).addReg(CountReg1);
    }

    // Add the Loop instruction to the begining of the loop.
    BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
            TII->get(Hexagon::LOOP0_r)).addMBB(LoopStart).addReg(CountReg);
  } else {
    assert(TripCount->isImm() && "Expecting immedate vaule for trip count");
    // Add the Loop immediate instruction to the beginning of the loop.
    int64_t CountImm = TripCount->getImm();
    BuildMI(*Preheader, InsertPos, InsertPos->getDebugLoc(),
            TII->get(Hexagon::LOOP0_i)).addMBB(LoopStart).addImm(CountImm);
  }

  // Make sure the loop start always has a reference in the CFG.  We need to
  // create a BlockAddress operand to get this mechanism to work both the
  // MachineBasicBlock and BasicBlock objects need the flag set.
  LoopStart->setHasAddressTaken();
  // This line is needed to set the hasAddressTaken flag on the BasicBlock
  // object
  BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock()));

  // Replace the loop branch with an endloop instruction.
  DebugLoc dl = LastI->getDebugLoc();
  BuildMI(*LastMBB, LastI, dl, TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart);

  // The loop ends with either:
  //  - a conditional branch followed by an unconditional branch, or
  //  - a conditional branch to the loop start.
  if (LastI->getOpcode() == Hexagon::JMP_c ||
      LastI->getOpcode() == Hexagon::JMP_cNot) {
    // delete one and change/add an uncond. branch to out of the loop
    MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
    LastI = LastMBB->erase(LastI);
    if (!L->contains(BranchTarget)) {
      if (LastI != LastMBB->end()) {
        TII->RemoveBranch(*LastMBB);
      }
      SmallVector<MachineOperand, 0> Cond;
      TII->InsertBranch(*LastMBB, BranchTarget, 0, Cond, dl);
    }
  } else {
    // Conditional branch to loop start; just delete it.
    LastMBB->erase(LastI);
  }
  delete TripCount;

  ++NumHWLoops;
  return true;
}

/// createHexagonFixupHwLoops - Factory for creating the hardware loop
/// phase.
FunctionPass *llvm::createHexagonFixupHwLoops() {
  return new HexagonFixupHwLoops();
}

bool HexagonFixupHwLoops::runOnMachineFunction(MachineFunction &MF) {
  DEBUG(dbgs() << "****** Hexagon Hardware Loop Fixup ******\n");

  bool Changed = fixupLoopInstrs(MF);
  return Changed;
}

/// fixupLoopInsts - For Hexagon, if the loop label is to far from the
/// loop instruction then we need to set the LC0 and SA0 registers
/// explicitly instead of using LOOP(start,count).  This function
/// checks the distance, and generates register assignments if needed.
///
/// This function makes two passes over the basic blocks.  The first
/// pass computes the offset of the basic block from the start.
/// The second pass checks all the loop instructions.
bool HexagonFixupHwLoops::fixupLoopInstrs(MachineFunction &MF) {

  // Offset of the current instruction from the start.
  unsigned InstOffset = 0;
  // Map for each basic block to it's first instruction.
  DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;

  // First pass - compute the offset of each basic block.
  for (MachineFunction::iterator MBB = MF.begin(), MBBe = MF.end();
       MBB != MBBe; ++MBB) {
    BlockToInstOffset[MBB] = InstOffset;
    InstOffset += (MBB->size() * 4);
  }

  // Second pass - check each loop instruction to see if it needs to
  // be converted.
  InstOffset = 0;
  bool Changed = false;
  RegScavenger RS;

  // Loop over all the basic blocks.
  for (MachineFunction::iterator MBB = MF.begin(), MBBe = MF.end();
       MBB != MBBe; ++MBB) {
    InstOffset = BlockToInstOffset[MBB];
    RS.enterBasicBlock(MBB);

    // Loop over all the instructions.
    MachineBasicBlock::iterator MIE = MBB->end();
    MachineBasicBlock::iterator MII = MBB->begin();
    while (MII != MIE) {
      if (isHardwareLoop(MII)) {
        RS.forward(MII);
        assert(MII->getOperand(0).isMBB() &&
               "Expect a basic block as loop operand");
        int diff = InstOffset - BlockToInstOffset[MII->getOperand(0).getMBB()];
        diff = (diff > 0 ? diff : -diff);
        if ((unsigned)diff > MAX_LOOP_DISTANCE) {
          // Convert to explicity setting LC0 and SA0.
          convertLoopInstr(MF, MII, RS);
          MII = MBB->erase(MII);
          Changed = true;
        } else {
          ++MII;
        }
      } else {
        ++MII;
      }
      InstOffset += 4;
    }
  }

  return Changed;

}

/// convertLoopInstr - convert a loop instruction to a sequence of instructions
/// that set the lc and sa register explicitly.
void HexagonFixupHwLoops::convertLoopInstr(MachineFunction &MF,
                                           MachineBasicBlock::iterator &MII,
                                           RegScavenger &RS) {
  const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
  MachineBasicBlock *MBB = MII->getParent();
  DebugLoc DL = MII->getDebugLoc();
  unsigned Scratch = RS.scavengeRegister(Hexagon::IntRegsRegisterClass, MII, 0);

  // First, set the LC0 with the trip count.
  if (MII->getOperand(1).isReg()) {
    // Trip count is a register
    BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::LC0)
      .addReg(MII->getOperand(1).getReg());
  } else {
    // Trip count is an immediate.
    BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFRI), Scratch)
      .addImm(MII->getOperand(1).getImm());
    BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::LC0)
      .addReg(Scratch);
  }
  // Then, set the SA0 with the loop start address.
  BuildMI(*MBB, MII, DL, TII->get(Hexagon::CONST32_Label), Scratch)
    .addMBB(MII->getOperand(0).getMBB());
  BuildMI(*MBB, MII, DL, TII->get(Hexagon::TFCR), Hexagon::SA0).addReg(Scratch);
}