//===------------- PPCExpandISEL.cpp - Expand ISEL instruction ------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// A pass that expands the ISEL instruction into an if-then-else sequence.
// This pass must be run post-RA since all operands must be physical registers.
//
//===----------------------------------------------------------------------===//

#include "PPC.h"
#include "PPCInstrInfo.h"
#include "PPCSubtarget.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

#define DEBUG_TYPE "ppc-expand-isel"

STATISTIC(NumExpanded, "Number of ISEL instructions expanded");
STATISTIC(NumRemoved, "Number of ISEL instructions removed");
STATISTIC(NumFolded, "Number of ISEL instructions folded");

// If -ppc-gen-isel=false is set, we will disable generating the ISEL
// instruction on all PPC targets. Otherwise, if the user set option
// -misel or the platform supports ISEL by default, still generate the
// ISEL instruction, else expand it.
static cl::opt<bool>
    GenerateISEL("ppc-gen-isel",
                 cl::desc("Enable generating the ISEL instruction."),
                 cl::init(true), cl::Hidden);

namespace {
class PPCExpandISEL : public MachineFunctionPass {
  DebugLoc dl;
  MachineFunction *MF;
  const TargetInstrInfo *TII;
  bool IsTrueBlockRequired;
  bool IsFalseBlockRequired;
  MachineBasicBlock *TrueBlock;
  MachineBasicBlock *FalseBlock;
  MachineBasicBlock *NewSuccessor;
  MachineBasicBlock::iterator TrueBlockI;
  MachineBasicBlock::iterator FalseBlockI;

  typedef SmallVector<MachineInstr *, 4> BlockISELList;
  typedef SmallDenseMap<int, BlockISELList> ISELInstructionList;

  // A map of MBB numbers to their lists of contained ISEL instructions.
  // Please note when we traverse this list and expand ISEL, we only remove
  // the ISEL from the MBB not from this list.
  ISELInstructionList ISELInstructions;

  /// Initialize the object.
  void initialize(MachineFunction &MFParam);

  void handleSpecialCases(BlockISELList &BIL, MachineBasicBlock *MBB);
  void reorganizeBlockLayout(BlockISELList &BIL, MachineBasicBlock *MBB);
  void populateBlocks(BlockISELList &BIL);
  void expandMergeableISELs(BlockISELList &BIL);
  void expandAndMergeISELs();

  bool canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI);

  ///  Is this instruction an ISEL or ISEL8?
  static bool isISEL(const MachineInstr &MI) {
    return (MI.getOpcode() == PPC::ISEL || MI.getOpcode() == PPC::ISEL8);
  }

  ///  Is this instruction an ISEL8?
  static bool isISEL8(const MachineInstr &MI) {
    return (MI.getOpcode() == PPC::ISEL8);
  }

  /// Are the two operands using the same register?
  bool useSameRegister(const MachineOperand &Op1, const MachineOperand &Op2) {
    return (Op1.getReg() == Op2.getReg());
  }

  ///
  ///  Collect all ISEL instructions from the current function.
  ///
  /// Walk the current function and collect all the ISEL instructions that are
  /// found. The instructions are placed in the ISELInstructions vector.
  ///
  /// \return true if any ISEL instructions were found, false otherwise
  ///
  bool collectISELInstructions();

public:
  static char ID;
  PPCExpandISEL() : MachineFunctionPass(ID) {
    initializePPCExpandISELPass(*PassRegistry::getPassRegistry());
  }

  ///
  ///  Determine whether to generate the ISEL instruction or expand it.
  ///
  /// Expand ISEL instruction into if-then-else sequence when one of
  /// the following two conditions hold:
  /// (1) -ppc-gen-isel=false
  /// (2) hasISEL() return false
  /// Otherwise, still generate ISEL instruction.
  /// The -ppc-gen-isel option is set to true by default. Which means the ISEL
  /// instruction is still generated by default on targets that support them.
  ///
  /// \return true if ISEL should be expanded into if-then-else code sequence;
  ///         false if ISEL instruction should be generated, i.e. not expaned.
  ///
  static bool isExpandISELEnabled(const MachineFunction &MF);

#ifndef NDEBUG
  void DumpISELInstructions() const;
#endif

  bool runOnMachineFunction(MachineFunction &MF) override {
    DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
    initialize(MF);

    if (!collectISELInstructions()) {
      DEBUG(dbgs() << "No ISEL instructions in this function\n");
      return false;
    }

#ifndef NDEBUG
    DumpISELInstructions();
#endif

    expandAndMergeISELs();

    return true;
  }
};
} // end anonymous namespace

void PPCExpandISEL::initialize(MachineFunction &MFParam) {
  MF = &MFParam;
  TII = MF->getSubtarget().getInstrInfo();
  ISELInstructions.clear();
}

bool PPCExpandISEL::isExpandISELEnabled(const MachineFunction &MF) {
  return !GenerateISEL || !MF.getSubtarget<PPCSubtarget>().hasISEL();
}

bool PPCExpandISEL::collectISELInstructions() {
  for (MachineBasicBlock &MBB : *MF) {
    BlockISELList thisBlockISELs;
    for (MachineInstr &MI : MBB)
      if (isISEL(MI))
        thisBlockISELs.push_back(&MI);
    if (!thisBlockISELs.empty())
      ISELInstructions.insert(std::make_pair(MBB.getNumber(), thisBlockISELs));
  }
  return !ISELInstructions.empty();
}

#ifndef NDEBUG
void PPCExpandISEL::DumpISELInstructions() const {
  for (const auto &I : ISELInstructions) {
    DEBUG(dbgs() << printMBBReference(*MF->getBlockNumbered(I.first)) << ":\n");
    for (const auto &VI : I.second)
      DEBUG(dbgs() << "    "; VI->print(dbgs()));
  }
}
#endif

/// Contiguous ISELs that have the same condition can be merged.
bool PPCExpandISEL::canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI) {
  // Same Condition Register?
  if (!useSameRegister(PrevPushedMI->getOperand(3), MI->getOperand(3)))
    return false;

  MachineBasicBlock::iterator PrevPushedMBBI = *PrevPushedMI;
  MachineBasicBlock::iterator MBBI = *MI;
  return (std::prev(MBBI) == PrevPushedMBBI); // Contiguous ISELs?
}

void PPCExpandISEL::expandAndMergeISELs() {
  bool ExpandISELEnabled = isExpandISELEnabled(*MF);

  for (auto &BlockList : ISELInstructions) {
    DEBUG(dbgs() << "Expanding ISEL instructions in "
                 << printMBBReference(*MF->getBlockNumbered(BlockList.first))
                 << "\n");
    BlockISELList &CurrentISELList = BlockList.second;
    auto I = CurrentISELList.begin();
    auto E = CurrentISELList.end();

    while (I != E) {
      assert(isISEL(**I) && "Expecting an ISEL instruction");
      MachineOperand &Dest = (*I)->getOperand(0);
      MachineOperand &TrueValue = (*I)->getOperand(1);
      MachineOperand &FalseValue = (*I)->getOperand(2);

      // Special case 1, all registers used by ISEL are the same one.
      // The non-redundant isel 0, 0, 0, N would not satisfy these conditions
      // as it would be ISEL %R0, %ZERO, %R0, %CRN.
      if (useSameRegister(Dest, TrueValue) &&
          useSameRegister(Dest, FalseValue)) {
        DEBUG(dbgs() << "Remove redudant ISEL instruction: " << **I << "\n");
        // FIXME: if the CR field used has no other uses, we could eliminate the
        // instruction that defines it. This would have to be done manually
        // since this pass runs too late to run DCE after it.
        NumRemoved++;
        (*I)->eraseFromParent();
        I++;
      } else if (useSameRegister(TrueValue, FalseValue)) {
        // Special case 2, the two input registers used by ISEL are the same.
        // Note: the non-foldable isel RX, 0, 0, N would not satisfy this
        // condition as it would be ISEL %RX, %ZERO, %R0, %CRN, which makes it
        // safe to fold ISEL to MR(OR) instead of ADDI.
        MachineBasicBlock *MBB = (*I)->getParent();
        DEBUG(dbgs() << "Fold the ISEL instruction to an unconditonal copy:\n");
        DEBUG(dbgs() << "ISEL: " << **I << "\n");
        NumFolded++;
        // Note: we're using both the TrueValue and FalseValue operands so as
        // not to lose the kill flag if it is set on either of them.
        BuildMI(*MBB, (*I), dl, TII->get(isISEL8(**I) ? PPC::OR8 : PPC::OR))
            .add(Dest)
            .add(TrueValue)
            .add(FalseValue);
        (*I)->eraseFromParent();
        I++;
      } else if (ExpandISELEnabled) { // Normal cases expansion enabled
        DEBUG(dbgs() << "Expand ISEL instructions:\n");
        DEBUG(dbgs() << "ISEL: " << **I << "\n");
        BlockISELList SubISELList;
        SubISELList.push_back(*I++);
        // Collect the ISELs that can be merged together.
        // This will eat up ISEL instructions without considering whether they
        // may be redundant or foldable to a register copy. So we still keep
        // the handleSpecialCases() downstream to handle them.
        while (I != E && canMerge(SubISELList.back(), *I)) {
          DEBUG(dbgs() << "ISEL: " << **I << "\n");
          SubISELList.push_back(*I++);
        }

        expandMergeableISELs(SubISELList);
      } else { // Normal cases expansion disabled
        I++; // leave the ISEL as it is
      }
    } // end while
  } // end for
}

void PPCExpandISEL::handleSpecialCases(BlockISELList &BIL,
                                       MachineBasicBlock *MBB) {
  IsTrueBlockRequired = false;
  IsFalseBlockRequired = false;

  auto MI = BIL.begin();
  while (MI != BIL.end()) {
    assert(isISEL(**MI) && "Expecting an ISEL instruction");
    DEBUG(dbgs() << "ISEL: " << **MI << "\n");

    MachineOperand &Dest = (*MI)->getOperand(0);
    MachineOperand &TrueValue = (*MI)->getOperand(1);
    MachineOperand &FalseValue = (*MI)->getOperand(2);

    // If at least one of the ISEL instructions satisfy the following
    // condition, we need the True Block:
    // The Dest Register and True Value Register are not the same
    // Similarly, if at least one of the ISEL instructions satisfy the
    // following condition, we need the False Block:
    // The Dest Register and False Value Register are not the same.
    bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
    bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);

    // Special case 1, all registers used by ISEL are the same one.
    if (!IsADDIInstRequired && !IsORIInstRequired) {
      DEBUG(dbgs() << "Remove redudant ISEL instruction.");
      // FIXME: if the CR field used has no other uses, we could eliminate the
      // instruction that defines it. This would have to be done manually
      // since this pass runs too late to run DCE after it.
      NumRemoved++;
      (*MI)->eraseFromParent();
      // Setting MI to the erase result keeps the iterator valid and increased.
      MI = BIL.erase(MI);
      continue;
    }

    // Special case 2, the two input registers used by ISEL are the same.
    // Note 1: We favor merging ISEL expansions over folding a single one. If
    // the passed list has multiple merge-able ISEL's, we won't fold any.
    // Note 2: There is no need to test for PPC::R0/PPC::X0 because PPC::ZERO/
    // PPC::ZERO8 will be used for the first operand if the value is meant to
    // be zero. In this case, the useSameRegister method will return false,
    // thereby preventing this ISEL from being folded.
    if (useSameRegister(TrueValue, FalseValue) && (BIL.size() == 1)) {
      DEBUG(dbgs() << "Fold the ISEL instruction to an unconditonal copy.");
      NumFolded++;
      // Note: we're using both the TrueValue and FalseValue operands so as
      // not to lose the kill flag if it is set on either of them.
      BuildMI(*MBB, (*MI), dl, TII->get(isISEL8(**MI) ? PPC::OR8 : PPC::OR))
          .add(Dest)
          .add(TrueValue)
          .add(FalseValue);
      (*MI)->eraseFromParent();
      // Setting MI to the erase result keeps the iterator valid and increased.
      MI = BIL.erase(MI);
      continue;
    }

    IsTrueBlockRequired |= IsADDIInstRequired;
    IsFalseBlockRequired |= IsORIInstRequired;
    MI++;
  }
}

void PPCExpandISEL::reorganizeBlockLayout(BlockISELList &BIL,
                                          MachineBasicBlock *MBB) {
  if (BIL.empty())
    return;

  assert((IsTrueBlockRequired || IsFalseBlockRequired) &&
         "Should have been handled by special cases earlier!");

  MachineBasicBlock *Successor = nullptr;
  const BasicBlock *LLVM_BB = MBB->getBasicBlock();
  MachineBasicBlock::iterator MBBI = (*BIL.back());
  NewSuccessor = (MBBI != MBB->getLastNonDebugInstr() || !MBB->canFallThrough())
                     // Another BB is needed to move the instructions that
                     // follow this ISEL.  If the ISEL is the last instruction
                     // in a block that can't fall through, we also need a block
                     // to branch to.
                     ? MF->CreateMachineBasicBlock(LLVM_BB)
                     : nullptr;

  MachineFunction::iterator It = MBB->getIterator();
  ++It; // Point to the successor block of MBB.

  // If NewSuccessor is NULL then the last ISEL in this group is the last
  // non-debug instruction in this block. Find the fall-through successor
  // of this block to use when updating the CFG below.
  if (!NewSuccessor) {
    for (auto &Succ : MBB->successors()) {
      if (MBB->isLayoutSuccessor(Succ)) {
        Successor = Succ;
        break;
      }
    }
  } else
    Successor = NewSuccessor;

  // The FalseBlock and TrueBlock are inserted after the MBB block but before
  // its successor.
  // Note this need to be done *after* the above setting the Successor code.
  if (IsFalseBlockRequired) {
    FalseBlock = MF->CreateMachineBasicBlock(LLVM_BB);
    MF->insert(It, FalseBlock);
  }

  if (IsTrueBlockRequired) {
    TrueBlock = MF->CreateMachineBasicBlock(LLVM_BB);
    MF->insert(It, TrueBlock);
  }

  if (NewSuccessor) {
    MF->insert(It, NewSuccessor);

    // Transfer the rest of this block into the new successor block.
    NewSuccessor->splice(NewSuccessor->end(), MBB,
                         std::next(MachineBasicBlock::iterator(BIL.back())),
                         MBB->end());
    NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB);

    // Copy the original liveIns of MBB to NewSuccessor.
    for (auto &LI : MBB->liveins())
      NewSuccessor->addLiveIn(LI);

    // After splitting the NewSuccessor block, Regs defined but not killed
    // in MBB should be treated as liveins of NewSuccessor.
    // Note: Cannot use stepBackward instead since we are using the Reg
    // liveness state at the end of MBB (liveOut of MBB) as the liveIn for
    // NewSuccessor. Otherwise, will cause cyclic dependence.
    LivePhysRegs LPR(*MF->getSubtarget<PPCSubtarget>().getRegisterInfo());
    SmallVector<std::pair<unsigned, const MachineOperand *>, 2> Clobbers;
    for (MachineInstr &MI : *MBB)
      LPR.stepForward(MI, Clobbers);
    for (auto &LI : LPR)
      NewSuccessor->addLiveIn(LI);
  } else {
    // Remove successor from MBB.
    MBB->removeSuccessor(Successor);
  }

  // Note that this needs to be done *after* transfering the successors from MBB
  // to the NewSuccessor block, otherwise these blocks will also be transferred
  // as successors!
  MBB->addSuccessor(IsTrueBlockRequired ? TrueBlock : Successor);
  MBB->addSuccessor(IsFalseBlockRequired ? FalseBlock : Successor);

  if (IsTrueBlockRequired) {
    TrueBlockI = TrueBlock->begin();
    TrueBlock->addSuccessor(Successor);
  }

  if (IsFalseBlockRequired) {
    FalseBlockI = FalseBlock->begin();
    FalseBlock->addSuccessor(Successor);
  }

  // Conditional branch to the TrueBlock or Successor
  BuildMI(*MBB, BIL.back(), dl, TII->get(PPC::BC))
      .add(BIL.back()->getOperand(3))
      .addMBB(IsTrueBlockRequired ? TrueBlock : Successor);

  // Jump over the true block to the new successor if the condition is false.
  BuildMI(*(IsFalseBlockRequired ? FalseBlock : MBB),
          (IsFalseBlockRequired ? FalseBlockI : BIL.back()), dl,
          TII->get(PPC::B))
      .addMBB(Successor);

  if (IsFalseBlockRequired)
    FalseBlockI = FalseBlock->begin(); // get the position of PPC::B
}

void PPCExpandISEL::populateBlocks(BlockISELList &BIL) {
  for (auto &MI : BIL) {
    assert(isISEL(*MI) && "Expecting an ISEL instruction");

    MachineOperand &Dest = MI->getOperand(0);       // location to store to
    MachineOperand &TrueValue = MI->getOperand(1);  // Value to store if
                                                       // condition is true
    MachineOperand &FalseValue = MI->getOperand(2); // Value to store if
                                                       // condition is false
    MachineOperand &ConditionRegister = MI->getOperand(3); // Condition

    DEBUG(dbgs() << "Dest: " << Dest << "\n");
    DEBUG(dbgs() << "TrueValue: " << TrueValue << "\n");
    DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n");
    DEBUG(dbgs() << "ConditionRegister: " << ConditionRegister << "\n");


    // If the Dest Register and True Value Register are not the same one, we
    // need the True Block.
    bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
    bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);

    if (IsADDIInstRequired) {
      // Copy the result into the destination if the condition is true.
      BuildMI(*TrueBlock, TrueBlockI, dl,
              TII->get(isISEL8(*MI) ? PPC::ADDI8 : PPC::ADDI))
          .add(Dest)
          .add(TrueValue)
          .add(MachineOperand::CreateImm(0));

      // Add the LiveIn registers required by true block.
      TrueBlock->addLiveIn(TrueValue.getReg());
    }

    if (IsORIInstRequired) {
      // Add the LiveIn registers required by false block.
      FalseBlock->addLiveIn(FalseValue.getReg());
    }

    if (NewSuccessor) {
      // Add the LiveIn registers required by NewSuccessor block.
      NewSuccessor->addLiveIn(Dest.getReg());
      NewSuccessor->addLiveIn(TrueValue.getReg());
      NewSuccessor->addLiveIn(FalseValue.getReg());
      NewSuccessor->addLiveIn(ConditionRegister.getReg());
    }

    // Copy the value into the destination if the condition is false.
    if (IsORIInstRequired)
      BuildMI(*FalseBlock, FalseBlockI, dl,
              TII->get(isISEL8(*MI) ? PPC::ORI8 : PPC::ORI))
          .add(Dest)
          .add(FalseValue)
          .add(MachineOperand::CreateImm(0));

    MI->eraseFromParent(); // Remove the ISEL instruction.

    NumExpanded++;
  }
}

void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) {
  // At this stage all the ISELs of BIL are in the same MBB.
  MachineBasicBlock *MBB = BIL.back()->getParent();

  handleSpecialCases(BIL, MBB);
  reorganizeBlockLayout(BIL, MBB);
  populateBlocks(BIL);
}

INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation",
                false, false)
char PPCExpandISEL::ID = 0;

FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); }