//===-- ARMBlockPlacement.cpp - ARM block placement pass ------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This pass re-arranges machine basic blocks to suit target requirements.
// Currently it only moves blocks to fix backwards WLS branches.
//
//===----------------------------------------------------------------------===//

#include "ARM.h"
#include "ARMBaseInstrInfo.h"
#include "ARMBasicBlockInfo.h"
#include "ARMSubtarget.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"

using namespace llvm;

#define DEBUG_TYPE "arm-block-placement"
#define DEBUG_PREFIX "ARM Block Placement: "

namespace llvm {
class ARMBlockPlacement : public MachineFunctionPass {
private:
  const ARMBaseInstrInfo *TII;
  std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
  MachineLoopInfo *MLI = nullptr;

public:
  static char ID;
  ARMBlockPlacement() : MachineFunctionPass(ID) {}

  bool runOnMachineFunction(MachineFunction &MF) override;
  void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *After);
  bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);

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

} // namespace llvm

FunctionPass *llvm::createARMBlockPlacementPass() {
  return new ARMBlockPlacement();
}

char ARMBlockPlacement::ID = 0;

INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,
                false)

bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
  if (skipFunction(MF.getFunction()))
      return false;
  const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget());
  if (!ST.hasLOB())
    return false;
  LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n");
  MLI = &getAnalysis<MachineLoopInfo>();
  TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
  BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
  MF.RenumberBlocks();
  BBUtils->computeAllBlockSizes();
  BBUtils->adjustBBOffsetsAfter(&MF.front());
  bool Changed = false;

  // Find loops with a backwards branching WLS.
  // This requires looping over the loops in the function, checking each
  // preheader for a WLS and if its target is before the preheader. If moving
  // the target block wouldn't produce another backwards WLS or a new forwards
  // LE branch then move the target block after the preheader.
  for (auto *ML : *MLI) {
    MachineBasicBlock *Preheader = ML->getLoopPredecessor();
    if (!Preheader)
      continue;

    for (auto &Terminator : Preheader->terminators()) {
      if (Terminator.getOpcode() != ARM::t2WhileLoopStart)
        continue;
      MachineBasicBlock *LoopExit = Terminator.getOperand(1).getMBB();
      // We don't want to move the function's entry block.
      if (!LoopExit->getPrevNode())
        continue;
      if (blockIsBefore(Preheader, LoopExit))
        continue;
      LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
                        << Preheader->getFullName() << " to "
                        << LoopExit->getFullName() << "\n");

      // Make sure that moving the target block doesn't cause any of its WLSs
      // that were previously not backwards to become backwards
      bool CanMove = true;
      for (auto &LoopExitTerminator : LoopExit->terminators()) {
        if (LoopExitTerminator.getOpcode() != ARM::t2WhileLoopStart)
          continue;
        // An example loop structure where the LoopExit can't be moved, since
        // bb1's WLS will become backwards once it's moved after bb3 bb1: -
        // LoopExit
        //      WLS bb2  - LoopExit2
        // bb2:
        //      ...
        // bb3:          - Preheader
        //      WLS bb1
        // bb4:          - Header
        MachineBasicBlock *LoopExit2 =
            LoopExitTerminator.getOperand(1).getMBB();
        // If the WLS from LoopExit to LoopExit2 is already backwards then
        // moving LoopExit won't affect it, so it can be moved. If LoopExit2 is
        // after the Preheader then moving will keep it as a forward branch, so
        // it can be moved. If LoopExit2 is between the Preheader and LoopExit
        // then moving LoopExit will make it a backwards branch, so it can't be
        // moved since we'd fix one and introduce one backwards branch.
        // TODO: Analyse the blocks to make a decision if it would be worth
        // moving LoopExit even if LoopExit2 is between the Preheader and
        // LoopExit.
        if (!blockIsBefore(LoopExit2, LoopExit) &&
            (LoopExit2 == Preheader || blockIsBefore(LoopExit2, Preheader))) {
          LLVM_DEBUG(dbgs() << DEBUG_PREFIX
                            << "Can't move the target block as it would "
                               "introduce a new backwards WLS branch\n");
          CanMove = false;
          break;
        }
      }

      if (CanMove) {
        // Make sure no LEs become forwards.
        // An example loop structure where the LoopExit can't be moved, since
        // bb2's LE will become forwards once bb1 is moved after bb3.
        // bb1:           - LoopExit
        // bb2:
        //      LE  bb1  - Terminator
        // bb3:          - Preheader
        //      WLS bb1
        // bb4:          - Header
        for (auto It = LoopExit->getIterator(); It != Preheader->getIterator();
             It++) {
          MachineBasicBlock *MBB = &*It;
          for (auto &Terminator : MBB->terminators()) {
            if (Terminator.getOpcode() != ARM::t2LoopEndDec)
              continue;
            MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB();
            // The LE will become forwards branching if it branches to LoopExit
            // which isn't allowed by the architecture, so we should avoid
            // introducing these.
            // TODO: Analyse the blocks to make a decision if it would be worth
            // moving LoopExit even if we'd introduce a forwards LE
            if (LETarget == LoopExit) {
              LLVM_DEBUG(dbgs() << DEBUG_PREFIX
                                << "Can't move the target block as it would "
                                   "introduce a new forwards LE branch\n");
              CanMove = false;
              break;
            }
          }
        }

        if (!CanMove)
          break;
      }

      if (CanMove) {
        moveBasicBlock(LoopExit, Preheader);
        Changed = true;
        break;
      }
    }
  }

  return Changed;
}

bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
                                      MachineBasicBlock *Other) {
  return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
}

void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
                                       MachineBasicBlock *After) {
  LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after "
                    << After->getName() << "\n");
  MachineBasicBlock *BBPrevious = BB->getPrevNode();
  assert(BBPrevious && "Cannot move the function entry basic block");
  MachineBasicBlock *AfterNext = After->getNextNode();
  MachineBasicBlock *BBNext = BB->getNextNode();

  BB->moveAfter(After);

  auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) {
    LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from "
                      << From->getName() << " to " << To->getName() << "\n");
    assert(From->isSuccessor(To) &&
           "'To' is expected to be a successor of 'From'");
    MachineInstr &Terminator = *(--From->terminators().end());
    if (!Terminator.isUnconditionalBranch()) {
      // The BB doesn't have an unconditional branch so it relied on
      // fall-through. Fix by adding an unconditional branch to the moved BB.
      MachineInstrBuilder MIB =
          BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
      MIB.addMBB(To);
      MIB.addImm(ARMCC::CondCodes::AL);
      MIB.addReg(ARM::NoRegister);
      LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from "
                        << From->getName() << " to " << To->getName() << ": "
                        << *MIB.getInstr());
    }
  };

  // Fix fall-through to the moved BB from the one that used to be before it.
  if (BBPrevious->isSuccessor(BB))
    FixFallthrough(BBPrevious, BB);
  // Fix fall through from the destination BB to the one that used to follow.
  if (AfterNext && After->isSuccessor(AfterNext))
    FixFallthrough(After, AfterNext);
  // Fix fall through from the moved BB to the one that used to follow.
  if (BBNext && BB->isSuccessor(BBNext))
    FixFallthrough(BB, BBNext);

  BBUtils->adjustBBOffsetsAfter(After);
}