llvm16 targets

1 files changed, 300 insertions, 0 deletions

diff --git a/contrib/libs/llvm16/lib/Target/ARM/ARMBlockPlacement.cpp b/contrib/libs/llvm16/lib/Target/ARM/ARMBlockPlacement.cpp
new file mode 100644
index 00000000000..b2d291bbe7f
--- /dev/null
+++ b/contrib/libs/llvm16/lib/Target/ARM/ARMBlockPlacement.cpp
@@ -0,0 +1,300 @@
+//===-- 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 "MVETailPredUtils.h"
+#include "llvm/CodeGen/LivePhysRegs.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;
+  // A list of WLS instructions that need to be reverted to DLS.
+  SmallVector<MachineInstr *> RevertedWhileLoops;
+
+public:
+  static char ID;
+  ARMBlockPlacement() : MachineFunctionPass(ID) {}
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+  void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before);
+  bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
+  bool fixBackwardsWLS(MachineLoop *ML);
+  bool processPostOrderLoops(MachineLoop *ML);
+  bool revertWhileToDoLoop(MachineInstr *WLS);
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    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)
+
+static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) {
+  for (auto &Terminator : MBB->terminators()) {
+    if (isWhileLoopStart(Terminator))
+      return &Terminator;
+  }
+  return nullptr;
+}
+
+/// Find WhileLoopStart in the loop predecessor BB or otherwise in its only
+/// predecessor. If found, returns (BB, WLS Instr) pair, otherwise a null pair.
+static MachineInstr *findWLS(MachineLoop *ML) {
+  MachineBasicBlock *Predecessor = ML->getLoopPredecessor();
+  if (!Predecessor)
+    return nullptr;
+  MachineInstr *WlsInstr = findWLSInBlock(Predecessor);
+  if (WlsInstr)
+    return WlsInstr;
+  if (Predecessor->pred_size() == 1)
+    return findWLSInBlock(*Predecessor->pred_begin());
+  return nullptr;
+}
+
+// Revert a WhileLoopStart to an equivalent DoLoopStart and branch. Note that
+// because of the branches this requires an extra block to be created.
+bool ARMBlockPlacement::revertWhileToDoLoop(MachineInstr *WLS) {
+  //   lr = t2WhileLoopStartTP r0, r1, TgtBB
+  //   t2Br Ph
+  // ->
+  //   cmp r0, 0
+  //   brcc TgtBB
+  // block2:
+  //   LR = t2DoLoopStartTP r0, r1
+  //   t2Br Ph
+  MachineBasicBlock *Preheader = WLS->getParent();
+  assert(WLS != &Preheader->back());
+  assert(WLS->getNextNode() == &Preheader->back());
+  MachineInstr *Br = &Preheader->back();
+  assert(Br->getOpcode() == ARM::t2B);
+  assert(Br->getOperand(1).getImm() == 14);
+
+  // Clear the kill flags, as the cmp/bcc will no longer kill any operands.
+  WLS->getOperand(1).setIsKill(false);
+  if (WLS->getOpcode() == ARM::t2WhileLoopStartTP)
+    WLS->getOperand(2).setIsKill(false);
+
+  // Create the new block
+  MachineBasicBlock *NewBlock = Preheader->getParent()->CreateMachineBasicBlock(
+      Preheader->getBasicBlock());
+  Preheader->getParent()->insert(++Preheader->getIterator(), NewBlock);
+  // Move the Br to it
+  Br->removeFromParent();
+  NewBlock->insert(NewBlock->end(), Br);
+  // And setup the successors correctly.
+  Preheader->replaceSuccessor(Br->getOperand(0).getMBB(), NewBlock);
+  NewBlock->addSuccessor(Br->getOperand(0).getMBB());
+
+  // Create a new DLS to replace the WLS
+  MachineInstrBuilder MIB =
+      BuildMI(*NewBlock, Br, WLS->getDebugLoc(),
+              TII->get(WLS->getOpcode() == ARM::t2WhileLoopStartTP
+                           ? ARM::t2DoLoopStartTP
+                           : ARM::t2DoLoopStart));
+  MIB.add(WLS->getOperand(0));
+  MIB.add(WLS->getOperand(1));
+  if (WLS->getOpcode() == ARM::t2WhileLoopStartTP)
+    MIB.add(WLS->getOperand(2));
+
+  LLVM_DEBUG(dbgs() << DEBUG_PREFIX
+                    << "Reverting While Loop to Do Loop: " << *WLS << "\n");
+
+  RevertWhileLoopStartLR(WLS, TII, ARM::t2Bcc, true);
+
+  LivePhysRegs LiveRegs;
+  computeAndAddLiveIns(LiveRegs, *NewBlock);
+
+  Preheader->getParent()->RenumberBlocks();
+  BBUtils->computeAllBlockSizes();
+  BBUtils->adjustBBOffsetsAfter(Preheader);
+
+  return true;
+}
+
+/// Checks if loop has a backwards branching WLS, and if possible, fixes it.
+/// This requires checking the predecessor (ie. preheader or it's predecessor)
+/// for a WLS and if its loopExit/target is before it.
+/// If moving the predecessor won't convert a WLS (to the predecessor) from
+/// a forward to a backward branching WLS, then move the predecessor block
+/// to before the loopExit/target.
+bool ARMBlockPlacement::fixBackwardsWLS(MachineLoop *ML) {
+  MachineInstr *WlsInstr = findWLS(ML);
+  if (!WlsInstr)
+    return false;
+
+  MachineBasicBlock *Predecessor = WlsInstr->getParent();
+  MachineBasicBlock *LoopExit = getWhileLoopStartTargetBB(*WlsInstr);
+
+  // We don't want to move Preheader to before the function's entry block.
+  if (!LoopExit->getPrevNode())
+    return false;
+  if (blockIsBefore(Predecessor, LoopExit))
+    return false;
+  LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
+                    << Predecessor->getFullName() << " to "
+                    << LoopExit->getFullName() << "\n");
+
+  // Make sure no forward branching WLSs to the Predecessor become backwards
+  // branching. An example loop structure where the Predecessor can't be moved,
+  // since bb2's WLS will become forwards once bb3 is moved before/above bb1.
+  //
+  // bb1:           - LoopExit
+  // bb2:
+  //      WLS  bb3
+  // bb3:          - Predecessor
+  //      WLS bb1
+  // bb4:          - Header
+  for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator();
+       ++It) {
+    MachineBasicBlock *MBB = &*It;
+    for (auto &Terminator : MBB->terminators()) {
+      if (!isWhileLoopStart(Terminator))
+        continue;
+      MachineBasicBlock *WLSTarget = getWhileLoopStartTargetBB(Terminator);
+      // TODO: Analyse the blocks to make a decision if it would be worth
+      // moving Preheader even if we'd introduce a backwards WLS
+      if (WLSTarget == Predecessor) {
+        LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Can't move Predecessor block as "
+                          << "it would convert a WLS from forward to a "
+                          << "backwards branching WLS\n");
+        RevertedWhileLoops.push_back(WlsInstr);
+        return false;
+      }
+    }
+  }
+
+  moveBasicBlock(Predecessor, LoopExit);
+  return true;
+}
+
+/// Updates ordering (of WLS BB and their loopExits) in inner loops first
+/// Returns true if any change was made in any of the loops
+bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) {
+  bool Changed = false;
+  for (auto *InnerML : *ML)
+    Changed |= processPostOrderLoops(InnerML);
+  return Changed | fixBackwardsWLS(ML);
+}
+
+bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
+  if (skipFunction(MF.getFunction()))
+    return false;
+  const ARMSubtarget &ST = MF.getSubtarget<ARMSubtarget>();
+  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;
+  RevertedWhileLoops.clear();
+
+  // Find loops with a backwards branching WLS and fix if possible.
+  for (auto *ML : *MLI)
+    Changed |= processPostOrderLoops(ML);
+
+  // Revert any While loops still out of range to DLS loops.
+  for (auto *WlsInstr : RevertedWhileLoops)
+    Changed |= revertWhileToDoLoop(WlsInstr);
+
+  return Changed;
+}
+
+bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
+                                      MachineBasicBlock *Other) {
+  return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
+}
+
+// Moves a BasicBlock before another, without changing the control flow
+void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
+                                       MachineBasicBlock *Before) {
+  LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " before "
+                    << Before->getName() << "\n");
+  MachineBasicBlock *BBPrevious = BB->getPrevNode();
+  assert(BBPrevious && "Cannot move the function entry basic block");
+  MachineBasicBlock *BBNext = BB->getNextNode();
+
+  MachineBasicBlock *BeforePrev = Before->getPrevNode();
+  assert(BeforePrev &&
+         "Cannot move the given block to before the function entry block");
+  MachineFunction *F = BB->getParent();
+  BB->moveBefore(Before);
+
+  // Since only the blocks are to be moved around (but the control flow must
+  // not change), if there were any fall-throughs (to/from adjacent blocks),
+  // replace with unconditional branch to the fall through block.
+  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 (!TII->isPredicated(Terminator) &&
+        (isUncondBranchOpcode(Terminator.getOpcode()) ||
+         isIndirectBranchOpcode(Terminator.getOpcode()) ||
+         isJumpTableBranchOpcode(Terminator.getOpcode()) ||
+         Terminator.isReturn()))
+      return;
+    // 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 before it.
+  if (BeforePrev->isSuccessor(Before))
+    FixFallthrough(BeforePrev, Before);
+  // Fix fall through from the moved BB to the one that used to follow.
+  if (BBNext && BB->isSuccessor(BBNext))
+    FixFallthrough(BB, BBNext);
+
+  F->RenumberBlocks();
+  BBUtils->computeAllBlockSizes();
+  BBUtils->adjustBBOffsetsAfter(BB);
+}