/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

Bug Summary

File:	llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp
Warning:	line 1311, column 44 Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ARMLowOverheadLoops.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/build-llvm/lib/Target/ARM -I /build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM -I /build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/build-llvm/lib/Target/ARM -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f=. -ferror-limit 19 -fvisibility hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-09-15-222444-33637-1 -x c++ /build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

→

1//===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8/// \file
9/// Finalize v8.1-m low-overhead loops by converting the associated pseudo
10/// instructions into machine operations.
11/// The expectation is that the loop contains three pseudo instructions:
12/// - t2*LoopStart - placed in the preheader or pre-preheader. The do-loop
13///   form should be in the preheader, whereas the while form should be in the
14///   preheaders only predecessor.
15/// - t2LoopDec - placed within in the loop body.
16/// - t2LoopEnd - the loop latch terminator.
17///
18/// In addition to this, we also look for the presence of the VCTP instruction,
19/// which determines whether we can generated the tail-predicated low-overhead
20/// loop form.
21///
22/// Assumptions and Dependencies:
23/// Low-overhead loops are constructed and executed using a setup instruction:
24/// DLS, WLS, DLSTP or WLSTP and an instruction that loops back: LE or LETP.
25/// WLS(TP) and LE(TP) are branching instructions with a (large) limited range
26/// but fixed polarity: WLS can only branch forwards and LE can only branch
27/// backwards. These restrictions mean that this pass is dependent upon block
28/// layout and block sizes, which is why it's the last pass to run. The same is
29/// true for ConstantIslands, but this pass does not increase the size of the
30/// basic blocks, nor does it change the CFG. Instructions are mainly removed
31/// during the transform and pseudo instructions are replaced by real ones. In
32/// some cases, when we have to revert to a 'normal' loop, we have to introduce
33/// multiple instructions for a single pseudo (see RevertWhile and
34/// RevertLoopEnd). To handle this situation, t2WhileLoopStart and t2LoopEnd
35/// are defined to be as large as this maximum sequence of replacement
36/// instructions.
37///
38/// A note on VPR.P0 (the lane mask):
39/// VPT, VCMP, VPNOT and VCTP won't overwrite VPR.P0 when they update it in a
40/// "VPT Active" context (which includes low-overhead loops and vpt blocks).
41/// They will simply "and" the result of their calculation with the current
42/// value of VPR.P0. You can think of it like this:
43/// \verbatim
44/// if VPT active:    ; Between a DLSTP/LETP, or for predicated instrs
45///   VPR.P0 &= Value
46/// else
47///   VPR.P0 = Value
48/// \endverbatim
49/// When we're inside the low-overhead loop (between DLSTP and LETP), we always
50/// fall in the "VPT active" case, so we can consider that all VPR writes by
51/// one of those instruction is actually a "and".
52//===----------------------------------------------------------------------===//

54#include "ARM.h"
55#include "ARMBaseInstrInfo.h"
56#include "ARMBaseRegisterInfo.h"
57#include "ARMBasicBlockInfo.h"
58#include "ARMSubtarget.h"
59#include "Thumb2InstrInfo.h"
60#include "llvm/ADT/SetOperations.h"
61#include "llvm/ADT/SmallSet.h"
62#include "llvm/CodeGen/LivePhysRegs.h"
63#include "llvm/CodeGen/MachineFunctionPass.h"
64#include "llvm/CodeGen/MachineLoopInfo.h"
65#include "llvm/CodeGen/MachineLoopUtils.h"
66#include "llvm/CodeGen/MachineRegisterInfo.h"
67#include "llvm/CodeGen/Passes.h"
68#include "llvm/CodeGen/ReachingDefAnalysis.h"
69#include "llvm/MC/MCInstrDesc.h"

71using namespace llvm;

73#define DEBUG_TYPE"arm-low-overhead-loops" "arm-low-overhead-loops"
74#define ARM_LOW_OVERHEAD_LOOPS_NAME"ARM Low Overhead Loops pass" "ARM Low Overhead Loops pass"

76namespace {

using InstSet = SmallPtrSetImpl<MachineInstr *>;

class PostOrderLoopTraversal {
  MachineLoop &ML;
  MachineLoopInfo &MLI;
  SmallPtrSet<MachineBasicBlock*, 4> Visited;
  SmallVector<MachineBasicBlock*, 4> Order;

public:
  PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)
    : ML(ML), MLI(MLI) { }

  const SmallVectorImpl<MachineBasicBlock*> &getOrder() const {
    return Order;
  }

  // Visit all the blocks within the loop, as well as exit blocks and any
  // blocks properly dominating the header.
  void ProcessLoop() {
    std::function<void(MachineBasicBlock*)> Search = [this, &Search]
      (MachineBasicBlock *MBB) -> void {
      if (Visited.count(MBB))
        return;

      Visited.insert(MBB);
      for (auto *Succ : MBB->successors()) {
        if (!ML.contains(Succ))
          continue;
        Search(Succ);
      }
      Order.push_back(MBB);
    };

    // Insert exit blocks.
    SmallVector<MachineBasicBlock*, 2> ExitBlocks;
    ML.getExitBlocks(ExitBlocks);
    for (auto *MBB : ExitBlocks)
      Order.push_back(MBB);

    // Then add the loop body.
    Search(ML.getHeader());

    // Then try the preheader and its predecessors.
    std::function<void(MachineBasicBlock*)> GetPredecessor =
      [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void {
      Order.push_back(MBB);
      if (MBB->pred_size() == 1)
        GetPredecessor(*MBB->pred_begin());
    };

    if (auto *Preheader = ML.getLoopPreheader())
      GetPredecessor(Preheader);
    else if (auto *Preheader = MLI.findLoopPreheader(&ML, true))
      GetPredecessor(Preheader);
  }
};

struct PredicatedMI {
  MachineInstr *MI = nullptr;
  SetVector<MachineInstr*> Predicates;

public:
  PredicatedMI(MachineInstr *I, SetVector<MachineInstr *> &Preds) : MI(I) {
    assert(I && "Instruction must not be null!")((I && "Instruction must not be null!") ? static_cast
<void> (0) : __assert_fail ("I && \"Instruction must not be null!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 141, __PRETTY_FUNCTION__));
    Predicates.insert(Preds.begin(), Preds.end());
  }
};

// Represent a VPT block, a list of instructions that begins with a VPT/VPST
// and has a maximum of four proceeding instructions. All instructions within
// the block are predicated upon the vpr and we allow instructions to define
// the vpr within in the block too.
class VPTBlock {
  // The predicate then instruction, which is either a VPT, or a VPST
  // instruction.
  std::unique_ptr<PredicatedMI> PredicateThen;
  PredicatedMI *Divergent = nullptr;
  SmallVector<PredicatedMI, 4> Insts;

public:
  VPTBlock(MachineInstr *MI, SetVector<MachineInstr*> &Preds) {
    PredicateThen = std::make_unique<PredicatedMI>(MI, Preds);
  }

  void addInst(MachineInstr *MI, SetVector<MachineInstr*> &Preds) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Adding predicated MI: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Adding predicated MI: "
 << *MI; } } while (false);
    if (!Divergent && !set_difference(Preds, PredicateThen->Predicates).empty()) {
      Divergent = &Insts.back();
      LLVM_DEBUG(dbgs() << " - has divergent predicate: " << *Divergent->MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << " - has divergent predicate: "
 << *Divergent->MI; } } while (false);
    }
    Insts.emplace_back(MI, Preds);
    assert(Insts.size() <= 4 && "Too many instructions in VPT block!")((Insts.size() <= 4 && "Too many instructions in VPT block!"
) ? static_cast<void> (0) : __assert_fail ("Insts.size() <= 4 && \"Too many instructions in VPT block!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 169, __PRETTY_FUNCTION__));
  }

  // Have we found an instruction within the block which defines the vpr? If
  // so, not all the instructions in the block will have the same predicate.
  bool HasNonUniformPredicate() const {
    return Divergent != nullptr;
3
←
Assuming the condition is true→
4
←
Returning the value 1, which participates in a condition later→
  }

  // Is the given instruction part of the predicate set controlling the entry
  // to the block.
  bool IsPredicatedOn(MachineInstr *MI) const {
    return PredicateThen->Predicates.count(MI);
  }

  // Returns true if this is a VPT instruction.
  bool isVPT() const { return !isVPST(); }

  // Returns true if this is a VPST instruction.
  bool isVPST() const {
    return PredicateThen->MI->getOpcode() == ARM::MVE_VPST;
14
←
Assuming the condition is true→
15
←
Returning the value 1, which participates in a condition later→
  }

  // Is the given instruction the only predicate which controls the entry to
  // the block.
  bool IsOnlyPredicatedOn(MachineInstr *MI) const {
    return IsPredicatedOn(MI) && PredicateThen->Predicates.size() == 1;
18
←
Assuming the condition is true→
19
←
Assuming the condition is true→
20
←
Returning the value 1, which participates in a condition later→
  }

  unsigned size() const { return Insts.size(); }
  SmallVectorImpl<PredicatedMI> &getInsts() { return Insts; }
  MachineInstr *getPredicateThen() const { return PredicateThen->MI; }
  PredicatedMI *getDivergent() const { return Divergent; }
};

struct LowOverheadLoop {

  MachineLoop &ML;
  MachineBasicBlock *Preheader = nullptr;
  MachineLoopInfo &MLI;
  ReachingDefAnalysis &RDA;
  const TargetRegisterInfo &TRI;
  const ARMBaseInstrInfo &TII;
  MachineFunction *MF = nullptr;
  MachineInstr *InsertPt = nullptr;
  MachineInstr *Start = nullptr;
  MachineInstr *Dec = nullptr;
  MachineInstr *End = nullptr;
  MachineInstr *VCTP = nullptr;
  MachineOperand TPNumElements;
  SmallPtrSet<MachineInstr*, 4> SecondaryVCTPs;
  VPTBlock *CurrentBlock = nullptr;
  SetVector<MachineInstr*> CurrentPredicate;
  SmallVector<VPTBlock, 4> VPTBlocks;
  SmallPtrSet<MachineInstr*, 4> ToRemove;
  SmallPtrSet<MachineInstr*, 4> BlockMasksToRecompute;
  bool Revert = false;
  bool CannotTailPredicate = false;

  LowOverheadLoop(MachineLoop &ML, MachineLoopInfo &MLI,
                  ReachingDefAnalysis &RDA, const TargetRegisterInfo &TRI,
                  const ARMBaseInstrInfo &TII)
      : ML(ML), MLI(MLI), RDA(RDA), TRI(TRI), TII(TII),
        TPNumElements(MachineOperand::CreateImm(0)) {
    MF = ML.getHeader()->getParent();
    if (auto *MBB = ML.getLoopPreheader())
      Preheader = MBB;
    else if (auto *MBB = MLI.findLoopPreheader(&ML, true))
      Preheader = MBB;
  }

  // If this is an MVE instruction, check that we know how to use tail
  // predication with it. Record VPT blocks and return whether the
  // instruction is valid for tail predication.
  bool ValidateMVEInst(MachineInstr *MI);

  void AnalyseMVEInst(MachineInstr *MI) {
    CannotTailPredicate = !ValidateMVEInst(MI);
  }

  bool IsTailPredicationLegal() const {
    // For now, let's keep things really simple and only support a single
    // block for tail predication.
    return !Revert && FoundAllComponents() && VCTP &&
           !CannotTailPredicate && ML.getNumBlocks() == 1;
  }

  // Check that the predication in the loop will be equivalent once we
  // perform the conversion. Also ensure that we can provide the number
  // of elements to the loop start instruction.
  bool ValidateTailPredicate(MachineInstr *StartInsertPt);

  // Check that any values available outside of the loop will be the same
  // after tail predication conversion.
  bool ValidateLiveOuts();

  // Is it safe to define LR with DLS/WLS?
  // LR can be defined if it is the operand to start, because it's the same
  // value, or if it's going to be equivalent to the operand to Start.
  MachineInstr *isSafeToDefineLR();

  // Check the branch targets are within range and we satisfy our
  // restrictions.
  void CheckLegality(ARMBasicBlockUtils *BBUtils);

  bool FoundAllComponents() const {
    return Start && Dec && End;
  }

  SmallVectorImpl<VPTBlock> &getVPTBlocks() { return VPTBlocks; }

  // Return the operand for the loop start instruction. This will be the loop
  // iteration count, or the number of elements if we're tail predicating.
  MachineOperand &getLoopStartOperand() {
    return IsTailPredicationLegal() ? TPNumElements : Start->getOperand(0);
  }

  unsigned getStartOpcode() const {
    bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart;
    if (!IsTailPredicationLegal())
      return IsDo ? ARM::t2DLS : ARM::t2WLS;

    return VCTPOpcodeToLSTP(VCTP->getOpcode(), IsDo);
  }

  void dump() const {
    if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
    if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
    if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
    if (VCTP) dbgs() << "ARM Loops: Found VCTP: " << *VCTP;
    if (!FoundAllComponents())
      dbgs() << "ARM Loops: Not a low-overhead loop.\n";
    else if (!(Start && Dec && End))
      dbgs() << "ARM Loops: Failed to find all loop components.\n";
  }
};

class ARMLowOverheadLoops : public MachineFunctionPass {
  MachineFunction           *MF = nullptr;
  MachineLoopInfo           *MLI = nullptr;
  ReachingDefAnalysis       *RDA = nullptr;
  const ARMBaseInstrInfo    *TII = nullptr;
  MachineRegisterInfo       *MRI = nullptr;
  const TargetRegisterInfo  *TRI = nullptr;
  std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;

public:
  static char ID;

  ARMLowOverheadLoops() : MachineFunctionPass(ID) { }

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

  bool runOnMachineFunction(MachineFunction &MF) override;

  MachineFunctionProperties getRequiredProperties() const override {
    return MachineFunctionProperties().set(
        MachineFunctionProperties::Property::NoVRegs).set(
        MachineFunctionProperties::Property::TracksLiveness);
  }

  StringRef getPassName() const override {
    return ARM_LOW_OVERHEAD_LOOPS_NAME"ARM Low Overhead Loops pass";
  }

private:
  bool ProcessLoop(MachineLoop *ML);

  bool RevertNonLoops();

  void RevertWhile(MachineInstr *MI) const;

  bool RevertLoopDec(MachineInstr *MI) const;

  void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;

  void ConvertVPTBlocks(LowOverheadLoop &LoLoop);

  MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);

  void Expand(LowOverheadLoop &LoLoop);

  void IterationCountDCE(LowOverheadLoop &LoLoop);
};
358}

360char ARMLowOverheadLoops::ID = 0;

362INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,static void *initializeARMLowOverheadLoopsPassOnce(PassRegistry
 &Registry) { PassInfo *PI = new PassInfo( "ARM Low Overhead Loops pass"
, "arm-low-overhead-loops", &ARMLowOverheadLoops::ID, PassInfo
::NormalCtor_t(callDefaultCtor<ARMLowOverheadLoops>), false
, false); Registry.registerPass(*PI, true); return PI; } static
 llvm::once_flag InitializeARMLowOverheadLoopsPassFlag; void llvm
::initializeARMLowOverheadLoopsPass(PassRegistry &Registry
) { llvm::call_once(InitializeARMLowOverheadLoopsPassFlag, initializeARMLowOverheadLoopsPassOnce
, std::ref(Registry)); }
              false, false)static void *initializeARMLowOverheadLoopsPassOnce(PassRegistry
 &Registry) { PassInfo *PI = new PassInfo( "ARM Low Overhead Loops pass"
, "arm-low-overhead-loops", &ARMLowOverheadLoops::ID, PassInfo
::NormalCtor_t(callDefaultCtor<ARMLowOverheadLoops>), false
, false); Registry.registerPass(*PI, true); return PI; } static
 llvm::once_flag InitializeARMLowOverheadLoopsPassFlag; void llvm
::initializeARMLowOverheadLoopsPass(PassRegistry &Registry
) { llvm::call_once(InitializeARMLowOverheadLoopsPassFlag, initializeARMLowOverheadLoopsPassOnce
, std::ref(Registry)); }

365MachineInstr *LowOverheadLoop::isSafeToDefineLR() {
// We can define LR because LR already contains the same value.
if (Start->getOperand(0).getReg() == ARM::LR)
  return Start;

unsigned CountReg = Start->getOperand(0).getReg();
auto IsMoveLR = [&CountReg](MachineInstr *MI) {
  return MI->getOpcode() == ARM::tMOVr &&
         MI->getOperand(0).getReg() == ARM::LR &&
         MI->getOperand(1).getReg() == CountReg &&
         MI->getOperand(2).getImm() == ARMCC::AL;
 };

MachineBasicBlock *MBB = Start->getParent();

// Find an insertion point:
// - Is there a (mov lr, Count) before Start? If so, and nothing else writes
//   to Count before Start, we can insert at that mov.
if (auto *LRDef = RDA.getUniqueReachingMIDef(Start, ARM::LR))
  if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg))
    return LRDef;

// - Is there a (mov lr, Count) after Start? If so, and nothing else writes
//   to Count after Start, we can insert at that mov.
if (auto *LRDef = RDA.getLocalLiveOutMIDef(MBB, ARM::LR))
  if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg))
    return LRDef;

// We've found no suitable LR def and Start doesn't use LR directly. Can we
// just define LR anyway?
return RDA.isSafeToDefRegAt(Start, ARM::LR) ? Start : nullptr;
396}

398bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt) {
assert(VCTP && "VCTP instruction expected but is not set")((VCTP && "VCTP instruction expected but is not set")
 ? static_cast<void> (0) : __assert_fail ("VCTP && \"VCTP instruction expected but is not set\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 399, __PRETTY_FUNCTION__));
// All predication within the loop should be based on vctp. If the block
// isn't predicated on entry, check whether the vctp is within the block
// and that all other instructions are then predicated on it.
for (auto &Block : VPTBlocks) {
  if (Block.IsPredicatedOn(VCTP))
    continue;
  if (Block.HasNonUniformPredicate() && !isVCTP(Block.getDivergent()->MI)) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Found unsupported diverging predicate: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found unsupported diverging predicate: "
 << *Block.getDivergent()->MI; } } while (false)
                      << *Block.getDivergent()->MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found unsupported diverging predicate: "
 << *Block.getDivergent()->MI; } } while (false);
    return false;
  }
  SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts();
  for (auto &PredMI : Insts) {
    // Check the instructions in the block and only allow:
    //   - VCTPs
    //   - Instructions predicated on the main VCTP
    //   - Any VCMP
    //      - VCMPs just "and" their result with VPR.P0. Whether they are
    //      located before/after the VCTP is irrelevant - the end result will
    //      be the same in both cases, so there's no point in requiring them
    //      to be located after the VCTP!
    if (PredMI.Predicates.count(VCTP) || isVCTP(PredMI.MI) ||
        VCMPOpcodeToVPT(PredMI.MI->getOpcode()) != 0)
      continue;
    LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *PredMI.MIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Can't convert: "
 << *PredMI.MI << " - which is predicated on:\n";
 for (auto *MI : PredMI.Predicates) dbgs() << "   - " <<
 *MI; } } while (false)
               << " - which is predicated on:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Can't convert: "
 << *PredMI.MI << " - which is predicated on:\n";
 for (auto *MI : PredMI.Predicates) dbgs() << "   - " <<
 *MI; } } while (false)
               for (auto *MI : PredMI.Predicates)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Can't convert: "
 << *PredMI.MI << " - which is predicated on:\n";
 for (auto *MI : PredMI.Predicates) dbgs() << "   - " <<
 *MI; } } while (false)
                 dbgs() << "   - " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Can't convert: "
 << *PredMI.MI << " - which is predicated on:\n";
 for (auto *MI : PredMI.Predicates) dbgs() << "   - " <<
 *MI; } } while (false);
    return false;
  }
}

if (!ValidateLiveOuts()) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Invalid live outs.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Invalid live outs.\n"
; } } while (false);
  return false;
}

// For tail predication, we need to provide the number of elements, instead
// of the iteration count, to the loop start instruction. The number of
// elements is provided to the vctp instruction, so we need to check that
// we can use this register at InsertPt.
TPNumElements = VCTP->getOperand(1);
Register NumElements = TPNumElements.getReg();

// If the register is defined within loop, then we can't perform TP.
// TODO: Check whether this is just a mov of a register that would be
// available.
if (RDA.hasLocalDefBefore(VCTP, NumElements)) {
  LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n"
; } } while (false);
  return false;
}

// The element count register maybe defined after InsertPt, in which case we
// need to try to move either InsertPt or the def so that the [w|d]lstp can
// use the value.
MachineBasicBlock *InsertBB = StartInsertPt->getParent();

if (!RDA.isReachingDefLiveOut(StartInsertPt, NumElements)) {
  if (auto *ElemDef = RDA.getLocalLiveOutMIDef(InsertBB, NumElements)) {
    if (RDA.isSafeToMoveForwards(ElemDef, StartInsertPt)) {
      ElemDef->removeFromParent();
      InsertBB->insert(MachineBasicBlock::iterator(StartInsertPt), ElemDef);
      LLVM_DEBUG(dbgs() << "ARM Loops: Moved element count def: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Moved element count def: "
 << *ElemDef; } } while (false)
                 << *ElemDef)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Moved element count def: "
 << *ElemDef; } } while (false);
    } else if (RDA.isSafeToMoveBackwards(StartInsertPt, ElemDef)) {
      StartInsertPt->removeFromParent();
      InsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef),
                            StartInsertPt);
      LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Moved start past: "
 << *ElemDef; } } while (false);
    } else {
      // If we fail to move an instruction and the element count is provided
      // by a mov, use the mov operand if it will have the same value at the
      // insertion point
      MachineOperand Operand = ElemDef->getOperand(1);
      if (isMovRegOpcode(ElemDef->getOpcode()) &&
          RDA.getUniqueReachingMIDef(ElemDef, Operand.getReg()) ==
              RDA.getUniqueReachingMIDef(StartInsertPt, Operand.getReg())) {
        TPNumElements = Operand;
        NumElements = TPNumElements.getReg();
      } else {
        LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Unable to move element count to loop "
 << "start instruction.\n"; } } while (false)
                   << "ARM Loops: Unable to move element count to loop "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Unable to move element count to loop "
 << "start instruction.\n"; } } while (false)
                   << "start instruction.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Unable to move element count to loop "
 << "start instruction.\n"; } } while (false);
        return false;
      }
    }
  }
}

// Especially in the case of while loops, InsertBB may not be the
// preheader, so we need to check that the register isn't redefined
// before entering the loop.
auto CannotProvideElements = [this](MachineBasicBlock *MBB,
                                    Register NumElements) {
  // NumElements is redefined in this block.
  if (RDA.hasLocalDefBefore(&MBB->back(), NumElements))
    return true;

  // Don't continue searching up through multiple predecessors.
  if (MBB->pred_size() > 1)
    return true;

  return false;
};

// First, find the block that looks like the preheader.
MachineBasicBlock *MBB = Preheader;
if (!MBB) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find preheader.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Didn't find preheader.\n"
; } } while (false);
  return false;
}

// Then search backwards for a def, until we get to InsertBB.
while (MBB != InsertBB) {
  if (CannotProvideElements(MBB, NumElements)) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Unable to provide element count.\n"
; } } while (false);
    return false;
  }
  MBB = *MBB->pred_begin();
}

// Check that the value change of the element count is what we expect and
// that the predication will be equivalent. For this we need:
// NumElements = NumElements - VectorWidth. The sub will be a sub immediate
// and we can also allow register copies within the chain too.
auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) {
  return -getAddSubImmediate(*MI) == ExpectedVecWidth;
};

MBB = VCTP->getParent();
// Remove modifications to the element count since they have no purpose in a
// tail predicated loop. Explicitly refer to the vctp operand no matter which
// register NumElements has been assigned to, since that is what the
// modifications will be using
if (auto *Def = RDA.getUniqueReachingMIDef(&MBB->back(),
                                           VCTP->getOperand(1).getReg())) {
  SmallPtrSet<MachineInstr*, 2> ElementChain;
  SmallPtrSet<MachineInstr*, 2> Ignore = { VCTP };
  unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());

  Ignore.insert(SecondaryVCTPs.begin(), SecondaryVCTPs.end());

  if (RDA.isSafeToRemove(Def, ElementChain, Ignore)) {
    bool FoundSub = false;

    for (auto *MI : ElementChain) {
      if (isMovRegOpcode(MI->getOpcode()))
        continue;

      if (isSubImmOpcode(MI->getOpcode())) {
        if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth))
          return false;
        FoundSub = true;
      } else
        return false;
    }

    LLVM_DEBUG(dbgs() << "ARM Loops: Will remove element count chain:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Will remove element count chain:\n"
; for (auto *MI : ElementChain) dbgs() << " - " <<
 *MI; } } while (false)
               for (auto *MI : ElementChain)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Will remove element count chain:\n"
; for (auto *MI : ElementChain) dbgs() << " - " <<
 *MI; } } while (false)
                 dbgs() << " - " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Will remove element count chain:\n"
; for (auto *MI : ElementChain) dbgs() << " - " <<
 *MI; } } while (false);
    ToRemove.insert(ElementChain.begin(), ElementChain.end());
  }
}
return true;
564}

566static bool isVectorPredicated(MachineInstr *MI) {
int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
return PIdx != -1 && MI->getOperand(PIdx + 1).getReg() == ARM::VPR;
569}

571static bool isRegInClass(const MachineOperand &MO,
                       const TargetRegisterClass *Class) {
return MO.isReg() && MO.getReg() && Class->contains(MO.getReg());
574}

576// MVE 'narrowing' operate on half a lane, reading from half and writing
577// to half, which are referred to has the top and bottom half. The other
578// half retains its previous value.
579static bool retainsPreviousHalfElement(const MachineInstr &MI) {
const MCInstrDesc &MCID = MI.getDesc();
uint64_t Flags = MCID.TSFlags;
return (Flags & ARMII::RetainsPreviousHalfElement) != 0;
583}

585// Some MVE instructions read from the top/bottom halves of their operand(s)
586// and generate a vector result with result elements that are double the
587// width of the input.
588static bool producesDoubleWidthResult(const MachineInstr &MI) {
const MCInstrDesc &MCID = MI.getDesc();
uint64_t Flags = MCID.TSFlags;
return (Flags & ARMII::DoubleWidthResult) != 0;
592}

594static bool isHorizontalReduction(const MachineInstr &MI) {
const MCInstrDesc &MCID = MI.getDesc();
uint64_t Flags = MCID.TSFlags;
return (Flags & ARMII::HorizontalReduction) != 0;
598}

600// Can this instruction generate a non-zero result when given only zeroed
601// operands? This allows us to know that, given operands with false bytes
602// zeroed by masked loads, that the result will also contain zeros in those
603// bytes.
604static bool canGenerateNonZeros(const MachineInstr &MI) {

// Check for instructions which can write into a larger element size,
// possibly writing into a previous zero'd lane.
if (producesDoubleWidthResult(MI))
  return true;

switch (MI.getOpcode()) {
default:
  break;
// FIXME: VNEG FP and -0? I think we'll need to handle this once we allow
// fp16 -> fp32 vector conversions.
// Instructions that perform a NOT will generate 1s from 0s.
case ARM::MVE_VMVN:
case ARM::MVE_VORN:
// Count leading zeros will do just that!
case ARM::MVE_VCLZs8:
case ARM::MVE_VCLZs16:
case ARM::MVE_VCLZs32:
  return true;
}
return false;
626}

628// Look at its register uses to see if it only can only receive zeros
629// into its false lanes which would then produce zeros. Also check that
630// the output register is also defined by an FalseLanesZero instruction
631// so that if tail-predication happens, the lanes that aren't updated will
632// still be zeros.
633static bool producesFalseLanesZero(MachineInstr &MI,
                                 const TargetRegisterClass *QPRs,
                                 const ReachingDefAnalysis &RDA,
                                 InstSet &FalseLanesZero) {
if (canGenerateNonZeros(MI))
  return false;

bool isPredicated = isVectorPredicated(&MI);
// Predicated loads will write zeros to the falsely predicated bytes of the
// destination register.
if (MI.mayLoad())
  return isPredicated;

auto IsZeroInit = [](MachineInstr *Def) {
  return !isVectorPredicated(Def) &&
         Def->getOpcode() == ARM::MVE_VMOVimmi32 &&
         Def->getOperand(1).getImm() == 0;
};

bool AllowScalars = isHorizontalReduction(MI);
for (auto &MO : MI.operands()) {
  if (!MO.isReg() || !MO.getReg())
    continue;
  if (!isRegInClass(MO, QPRs) && AllowScalars)
    continue;

  // Check that this instruction will produce zeros in its false lanes:
  // - If it only consumes false lanes zero or constant 0 (vmov #0)
  // - If it's predicated, it only matters that it's def register already has
  //   false lane zeros, so we can ignore the uses.
  SmallPtrSet<MachineInstr *, 2> Defs;
  RDA.getGlobalReachingDefs(&MI, MO.getReg(), Defs);
  for (auto *Def : Defs) {
    if (Def == &MI || FalseLanesZero.count(Def) || IsZeroInit(Def))
      continue;
    if (MO.isUse() && isPredicated)
      continue;
    return false;
  }
}
LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Always False Zeros: "
 << MI; } } while (false);
return true;
675}

677bool LowOverheadLoop::ValidateLiveOuts() {
// We want to find out if the tail-predicated version of this loop will
// produce the same values as the loop in its original form. For this to
// be true, the newly inserted implicit predication must not change the
// the (observable) results.
// We're doing this because many instructions in the loop will not be
// predicated and so the conversion from VPT predication to tail-predication
// can result in different values being produced; due to the tail-predication
// preventing many instructions from updating their falsely predicated
// lanes. This analysis assumes that all the instructions perform lane-wise
// operations and don't perform any exchanges.
// A masked load, whether through VPT or tail predication, will write zeros
// to any of the falsely predicated bytes. So, from the loads, we know that
// the false lanes are zeroed and here we're trying to track that those false
// lanes remain zero, or where they change, the differences are masked away
// by their user(s).
// All MVE stores have to be predicated, so we know that any predicate load
// operands, or stored results are equivalent already. Other explicitly
// predicated instructions will perform the same operation in the original
// loop and the tail-predicated form too. Because of this, we can insert
// loads, stores and other predicated instructions into our Predicated
// set and build from there.
const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID);
SetVector<MachineInstr *> FalseLanesUnknown;
SmallPtrSet<MachineInstr *, 4> FalseLanesZero;
SmallPtrSet<MachineInstr *, 4> Predicated;
MachineBasicBlock *Header = ML.getHeader();

for (auto &MI : *Header) {
  const MCInstrDesc &MCID = MI.getDesc();
  uint64_t Flags = MCID.TSFlags;
  if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE)
    continue;

  if (isVCTP(&MI) || isVPTOpcode(MI.getOpcode()))
    continue;

  bool isPredicated = isVectorPredicated(&MI);
  bool retainsOrReduces =
    retainsPreviousHalfElement(MI) || isHorizontalReduction(MI);

  if (isPredicated)
    Predicated.insert(&MI);
  if (producesFalseLanesZero(MI, QPRs, RDA, FalseLanesZero))
    FalseLanesZero.insert(&MI);
  else if (MI.getNumDefs() == 0)
    continue;
  else if (!isPredicated && retainsOrReduces)
    return false;
  else if (!isPredicated)
    FalseLanesUnknown.insert(&MI);
}

auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,
                            SmallPtrSetImpl<MachineInstr *> &Predicated) {
  SmallPtrSet<MachineInstr *, 2> Uses;
  RDA.getGlobalUses(MI, MO.getReg(), Uses);
  for (auto *Use : Uses) {
    if (Use != MI && !Predicated.count(Use))
      return false;
  }
  return true;
};

// Visit the unknowns in reverse so that we can start at the values being
// stored and then we can work towards the leaves, hopefully adding more
// instructions to Predicated. Successfully terminating the loop means that
// all the unknown values have to found to be masked by predicated user(s).
// For any unpredicated values, we store them in NonPredicated so that we
// can later check whether these form a reduction.
SmallPtrSet<MachineInstr*, 2> NonPredicated;
for (auto *MI : reverse(FalseLanesUnknown)) {
  for (auto &MO : MI->operands()) {
    if (!isRegInClass(MO, QPRs) || !MO.isDef())
      continue;
    if (!HasPredicatedUsers(MI, MO, Predicated)) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Found an unknown def of : "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found an unknown def of : "
 << TRI.getRegAsmName(MO.getReg()) << " at " <<
 *MI; } } while (false)
                        << TRI.getRegAsmName(MO.getReg()) << " at " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found an unknown def of : "
 << TRI.getRegAsmName(MO.getReg()) << " at " <<
 *MI; } } while (false);
      NonPredicated.insert(MI);
      break;
    }
  }
  // Any unknown false lanes have been masked away by the user(s).
  if (!NonPredicated.contains(MI))
    Predicated.insert(MI);
}

SmallPtrSet<MachineInstr *, 2> LiveOutMIs;
SmallVector<MachineBasicBlock *, 2> ExitBlocks;
ML.getExitBlocks(ExitBlocks);
assert(ML.getNumBlocks() == 1 && "Expected single block loop!")((ML.getNumBlocks() == 1 && "Expected single block loop!"
) ? static_cast<void> (0) : __assert_fail ("ML.getNumBlocks() == 1 && \"Expected single block loop!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 767, __PRETTY_FUNCTION__));
assert(ExitBlocks.size() == 1 && "Expected a single exit block")((ExitBlocks.size() == 1 && "Expected a single exit block"
) ? static_cast<void> (0) : __assert_fail ("ExitBlocks.size() == 1 && \"Expected a single exit block\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 768, __PRETTY_FUNCTION__));
MachineBasicBlock *ExitBB = ExitBlocks.front();
for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) {
  // TODO: Instead of blocking predication, we could move the vctp to the exit
  // block and calculate it's operand there in or the preheader.
  if (RegMask.PhysReg == ARM::VPR)
    return false;
  // Check Q-regs that are live in the exit blocks. We don't collect scalars
  // because they won't be affected by lane predication.
  if (QPRs->contains(RegMask.PhysReg))
    if (auto *MI = RDA.getLocalLiveOutMIDef(Header, RegMask.PhysReg))
      LiveOutMIs.insert(MI);
}

// We've already validated that any VPT predication within the loop will be
// equivalent when we perform the predication transformation; so we know that
// any VPT predicated instruction is predicated upon VCTP. Any live-out
// instruction needs to be predicated, so check this here. The instructions
// in NonPredicated have been found to be a reduction that we can ensure its
// legality.
for (auto *MI : LiveOutMIs) {
  if (NonPredicated.count(MI) && FalseLanesUnknown.contains(MI)) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Unable to handle live out: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Unable to handle live out: "
 << *MI; } } while (false);
    return false;
  }
}

return true;
796}

798void LowOverheadLoop::CheckLegality(ARMBasicBlockUtils *BBUtils) {
if (Revert)
  return;

if (!End->getOperand(1).isMBB())
  report_fatal_error("Expected LoopEnd to target basic block");

// TODO Maybe there's cases where the target doesn't have to be the header,
// but for now be safe and revert.
if (End->getOperand(1).getMBB() != ML.getHeader()) {
  LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targetting header.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: LoopEnd is not targetting header.\n"
; } } while (false);
  Revert = true;
  return;
}

// The WLS and LE instructions have 12-bits for the label offset. WLS
// requires a positive offset, while LE uses negative.
if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML.getHeader()) ||
    !BBUtils->isBBInRange(End, ML.getHeader(), 4094)) {
  LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: LE offset is out-of-range\n"
; } } while (false);
  Revert = true;
  return;
}

if (Start->getOpcode() == ARM::t2WhileLoopStart &&
    (BBUtils->getOffsetOf(Start) >
     BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
     !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
  LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: WLS offset is out-of-range!\n"
; } } while (false);
  Revert = true;
  return;
}

InsertPt = Revert ? nullptr : isSafeToDefineLR();
if (!InsertPt) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Unable to find safe insertion point.\n"
; } } while (false);
  Revert = true;
  return;
} else
  LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Start insertion point: "
 << *InsertPt; } } while (false);

if (!IsTailPredicationLegal()) {
  LLVM_DEBUG(if (!VCTP)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { if (!VCTP) dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n"
; dbgs() << "ARM Loops: Tail-predication is not valid.\n"
; } } while (false)
               dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { if (!VCTP) dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n"
; dbgs() << "ARM Loops: Tail-predication is not valid.\n"
; } } while (false)
             dbgs() << "ARM Loops: Tail-predication is not valid.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { if (!VCTP) dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n"
; dbgs() << "ARM Loops: Tail-predication is not valid.\n"
; } } while (false);
  return;
}

assert(ML.getBlocks().size() == 1 &&((ML.getBlocks().size() == 1 && "Shouldn't be processing a loop with more than one block"
) ? static_cast<void> (0) : __assert_fail ("ML.getBlocks().size() == 1 && \"Shouldn't be processing a loop with more than one block\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 847, __PRETTY_FUNCTION__))
       "Shouldn't be processing a loop with more than one block")((ML.getBlocks().size() == 1 && "Shouldn't be processing a loop with more than one block"
) ? static_cast<void> (0) : __assert_fail ("ML.getBlocks().size() == 1 && \"Shouldn't be processing a loop with more than one block\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 847, __PRETTY_FUNCTION__));
CannotTailPredicate = !ValidateTailPredicate(InsertPt);
LLVM_DEBUG(if (CannotTailPredicate)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { if (CannotTailPredicate) dbgs()
 << "ARM Loops: Couldn't validate tail predicate.\n"; }
 } while (false)
           dbgs() << "ARM Loops: Couldn't validate tail predicate.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { if (CannotTailPredicate) dbgs()
 << "ARM Loops: Couldn't validate tail predicate.\n"; }
 } while (false);
851}

853bool LowOverheadLoop::ValidateMVEInst(MachineInstr* MI) {
if (CannotTailPredicate)
  return false;

if (isVCTP(MI)) {
  // If we find another VCTP, check whether it uses the same value as the main VCTP.
  // If it does, store it in the SecondaryVCTPs set, else refuse it.
  if (VCTP) {
    if (!VCTP->getOperand(1).isIdenticalTo(MI->getOperand(1)) ||
        !RDA.hasSameReachingDef(VCTP, MI, MI->getOperand(1).getReg())) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found VCTP with a different reaching "
 "definition from the main VCTP"; } } while (false)
                           "definition from the main VCTP")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found VCTP with a different reaching "
 "definition from the main VCTP"; } } while (false);
      return false;
    }
    LLVM_DEBUG(dbgs() << "ARM Loops: Found secondary VCTP: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found secondary VCTP: "
 << *MI; } } while (false);
    SecondaryVCTPs.insert(MI);
  } else {
    LLVM_DEBUG(dbgs() << "ARM Loops: Found 'main' VCTP: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found 'main' VCTP: "
 << *MI; } } while (false);
    VCTP = MI;
  }
} else if (isVPTOpcode(MI->getOpcode())) {
  if (MI->getOpcode() != ARM::MVE_VPST) {
    assert(MI->findRegisterDefOperandIdx(ARM::VPR) != -1 &&((MI->findRegisterDefOperandIdx(ARM::VPR) != -1 &&
 "VPT does not implicitly define VPR?!") ? static_cast<void
> (0) : __assert_fail ("MI->findRegisterDefOperandIdx(ARM::VPR) != -1 && \"VPT does not implicitly define VPR?!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 876, __PRETTY_FUNCTION__))
           "VPT does not implicitly define VPR?!")((MI->findRegisterDefOperandIdx(ARM::VPR) != -1 &&
 "VPT does not implicitly define VPR?!") ? static_cast<void
> (0) : __assert_fail ("MI->findRegisterDefOperandIdx(ARM::VPR) != -1 && \"VPT does not implicitly define VPR?!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 876, __PRETTY_FUNCTION__));
    CurrentPredicate.insert(MI);
  }

  VPTBlocks.emplace_back(MI, CurrentPredicate);
  CurrentBlock = &VPTBlocks.back();
  return true;
} else if (MI->getOpcode() == ARM::MVE_VPSEL ||
           MI->getOpcode() == ARM::MVE_VPNOT) {
  // TODO: Allow VPSEL and VPNOT, we currently cannot because:
  // 1) It will use the VPR as a predicate operand, but doesn't have to be
  //    instead a VPT block, which means we can assert while building up
  //    the VPT block because we don't find another VPT or VPST to being a new
  //    one.
  // 2) VPSEL still requires a VPR operand even after tail predicating,
  //    which means we can't remove it unless there is another
  //    instruction, such as vcmp, that can provide the VPR def.
  return false;
}

bool IsUse = false;
bool IsDef = false;
const MCInstrDesc &MCID = MI->getDesc();
for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
  const MachineOperand &MO = MI->getOperand(i);
  if (!MO.isReg() || MO.getReg() != ARM::VPR)
    continue;

  if (MO.isDef()) {
    CurrentPredicate.insert(MI);
    IsDef = true;
  } else if (ARM::isVpred(MCID.OpInfo[i].OperandType)) {
    CurrentBlock->addInst(MI, CurrentPredicate);
    IsUse = true;
  } else {
    LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found instruction using vpr: "
 << *MI; } } while (false);
    return false;
  }
}

// If we find a vpr def that is not already predicated on the vctp, we've
// got disjoint predicates that may not be equivalent when we do the
// conversion.
if (IsDef && !IsUse && VCTP && !isVCTP(MI)) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Found disjoint vpr def: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found disjoint vpr def: "
 << *MI; } } while (false);
  return false;
}

uint64_t Flags = MCID.TSFlags;
if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE)
  return true;

// If we find an instruction that has been marked as not valid for tail
// predication, only allow the instruction if it's contained within a valid
// VPT block.
if ((Flags & ARMII::ValidForTailPredication) == 0 && !IsUse) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Can't tail predicate: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Can't tail predicate: "
 << *MI; } } while (false);
  return false;
}

// If the instruction is already explicitly predicated, then the conversion
// will be fine, but ensure that all store operations are predicated.
return !IsUse && MI->mayStore() ? false : true;
939}

941bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
if (!ST.hasLOB())
  return false;

MF = &mf;
LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops on "
 << MF->getName() << " ------------- \n"; } } while
 (false);

MLI = &getAnalysis<MachineLoopInfo>();
RDA = &getAnalysis<ReachingDefAnalysis>();
MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
MRI = &MF->getRegInfo();
TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
TRI = ST.getRegisterInfo();
BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
BBUtils->computeAllBlockSizes();
BBUtils->adjustBBOffsetsAfter(&MF->front());

bool Changed = false;
for (auto ML : *MLI) {
  if (!ML->getParentLoop())
    Changed |= ProcessLoop(ML);
}
Changed |= RevertNonLoops();
return Changed;
966}

968bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {

bool Changed = false;

// Process inner loops first.
for (auto I = ML->begin(), E = ML->end(); I != E; ++I)
  Changed |= ProcessLoop(*I);

LLVM_DEBUG(dbgs() << "ARM Loops: Processing loop containing:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
           if (auto *Preheader = ML->getLoopPreheader())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
             dbgs() << " - " << Preheader->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
           else if (auto *Preheader = MLI->findLoopPreheader(ML))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
             dbgs() << " - " << Preheader->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
           else if (auto *Preheader = MLI->findLoopPreheader(ML, true))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
             dbgs() << " - " << Preheader->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
           for (auto *MBB : ML->getBlocks())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
             dbgs() << " - " << MBB->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false)
          )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Processing loop containing:\n"
; if (auto *Preheader = ML->getLoopPreheader()) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML)) dbgs() <<
 " - " << Preheader->getName() << "\n"; else if
 (auto *Preheader = MLI->findLoopPreheader(ML, true)) dbgs
() << " - " << Preheader->getName() << "\n"
; for (auto *MBB : ML->getBlocks()) dbgs() << " - " <<
 MBB->getName() << "\n";; } } while (false);

// Search the given block for a loop start instruction. If one isn't found,
// and there's only one predecessor block, search that one too.
std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
  [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
  for (auto &MI : *MBB) {
    if (isLoopStart(MI))
      return &MI;
  }
  if (MBB->pred_size() == 1)
    return SearchForStart(*MBB->pred_begin());
  return nullptr;
};

LowOverheadLoop LoLoop(*ML, *MLI, *RDA, *TRI, *TII);
// Search the preheader for the start intrinsic.
// FIXME: I don't see why we shouldn't be supporting multiple predecessors
// with potentially multiple set.loop.iterations, so we need to enable this.
if (LoLoop.Preheader)
  LoLoop.Start = SearchForStart(LoLoop.Preheader);
else
  return false;

// Find the low-overhead loop components and decide whether or not to fall
// back to a normal loop. Also look for a vctp instructions and decide
// whether we can convert that predicate using tail predication.
for (auto *MBB : reverse(ML->getBlocks())) {
  for (auto &MI : *MBB) {
    if (MI.isDebugValue())
      continue;
    else if (MI.getOpcode() == ARM::t2LoopDec)
      LoLoop.Dec = &MI;
    else if (MI.getOpcode() == ARM::t2LoopEnd)
      LoLoop.End = &MI;
    else if (isLoopStart(MI))
      LoLoop.Start = &MI;
    else if (MI.getDesc().isCall()) {
      // TODO: Though the call will require LE to execute again, does this
      // mean we should revert? Always executing LE hopefully should be
      // faster than performing a sub,cmp,br or even subs,br.
      LoLoop.Revert = true;
      LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Found call.\n"
; } } while (false);
    } else {
      // Record VPR defs and build up their corresponding vpt blocks.
      // Check we know how to tail predicate any mve instructions.
      LoLoop.AnalyseMVEInst(&MI);
    }
  }
}

LLVM_DEBUG(LoLoop.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { LoLoop.dump(); } } while (false
);
if (!LoLoop.FoundAllComponents()) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Didn't find loop start, update, end\n"
; } } while (false);
  return false;
}

// Check that the only instruction using LoopDec is LoopEnd.
// TODO: Check for copy chains that really have no effect.
SmallPtrSet<MachineInstr*, 2> Uses;
RDA->getReachingLocalUses(LoLoop.Dec, ARM::LR, Uses);
if (Uses.size() > 1 || !Uses.count(LoLoop.End)) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Unable to remove LoopDec.\n"
; } } while (false);
  LoLoop.Revert = true;
}
LoLoop.CheckLegality(BBUtils.get());
Expand(LoLoop);
return true;
1053}

1055// WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
1056// beq that branches to the exit branch.
1057// TODO: We could also try to generate a cbz if the value in LR is also in
1058// another low register.
1059void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Reverting to cmp: "
 << *MI; } } while (false);
MachineBasicBlock *MBB = MI->getParent();
MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
                                  TII->get(ARM::t2CMPri));
MIB.add(MI->getOperand(0));
MIB.addImm(0);
MIB.addImm(ARMCC::AL);
MIB.addReg(ARM::NoRegister);

MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
  ARM::tBcc : ARM::t2Bcc;

MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
MIB.add(MI->getOperand(1));   // branch target
MIB.addImm(ARMCC::EQ);        // condition code
MIB.addReg(ARM::CPSR);
MI->eraseFromParent();
1078}

1080bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Reverting to sub: "
 << *MI; } } while (false);
MachineBasicBlock *MBB = MI->getParent();
SmallPtrSet<MachineInstr*, 1> Ignore;
for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {
  if (I->getOpcode() == ARM::t2LoopEnd) {
    Ignore.insert(&*I);
    break;
  }
}

// If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
bool SetFlags = RDA->isSafeToDefRegAt(MI, ARM::CPSR, Ignore);

MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
                                  TII->get(ARM::t2SUBri));
MIB.addDef(ARM::LR);
MIB.add(MI->getOperand(1));
MIB.add(MI->getOperand(2));
MIB.addImm(ARMCC::AL);
MIB.addReg(0);

if (SetFlags) {
  MIB.addReg(ARM::CPSR);
  MIB->getOperand(5).setIsDef(true);
} else
  MIB.addReg(0);

MI->eraseFromParent();
return SetFlags;
1110}

1112// Generate a subs, or sub and cmp, and a branch instead of an LE.
1113void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Reverting to cmp, br: "
 << *MI; } } while (false);

MachineBasicBlock *MBB = MI->getParent();
// Create cmp
if (!SkipCmp) {
  MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
                                    TII->get(ARM::t2CMPri));
  MIB.addReg(ARM::LR);
  MIB.addImm(0);
  MIB.addImm(ARMCC::AL);
  MIB.addReg(ARM::NoRegister);
}

MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
  ARM::tBcc : ARM::t2Bcc;

// Create bne
MachineInstrBuilder MIB =
  BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
MIB.add(MI->getOperand(1));   // branch target
MIB.addImm(ARMCC::NE);        // condition code
MIB.addReg(ARM::CPSR);
MI->eraseFromParent();
1138}

1140// Perform dead code elimation on the loop iteration count setup expression.
1141// If we are tail-predicating, the number of elements to be processed is the
1142// operand of the VCTP instruction in the vector body, see getCount(), which is
1143// register $r3 in this example:
1144//
1145//   $lr = big-itercount-expression
1146//   ..
1147//   t2DoLoopStart renamable $lr
1148//   vector.body:
1149//     ..
1150//     $vpr = MVE_VCTP32 renamable $r3
1151//     renamable $lr = t2LoopDec killed renamable $lr, 1
1152//     t2LoopEnd renamable $lr, %vector.body
1153//     tB %end
1154//
1155// What we would like achieve here is to replace the do-loop start pseudo
1156// instruction t2DoLoopStart with:
1157//
1158//    $lr = MVE_DLSTP_32 killed renamable $r3
1159//
1160// Thus, $r3 which defines the number of elements, is written to $lr,
1161// and then we want to delete the whole chain that used to define $lr,
1162// see the comment below how this chain could look like.
1163//
1164void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
if (!LoLoop.IsTailPredicationLegal())
  return;

LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n"
; } } while (false);

MachineInstr *Def = RDA->getMIOperand(LoLoop.Start, 0);
if (!Def) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Couldn't find iteration count.\n"
; } } while (false);
  return;
}

// Collect and remove the users of iteration count.
SmallPtrSet<MachineInstr*, 4> Killed  = { LoLoop.Start, LoLoop.Dec,
                                          LoLoop.End, LoLoop.InsertPt };
SmallPtrSet<MachineInstr*, 2> Remove;
if (RDA->isSafeToRemove(Def, Remove, Killed))
  LoLoop.ToRemove.insert(Remove.begin(), Remove.end());
else {
  LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n"
; } } while (false);
  return;
}

// Collect the dead code and the MBBs in which they reside.
RDA->collectKilledOperands(Def, Killed);
SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks;
for (auto *MI : Killed)
  BasicBlocks.insert(MI->getParent());

// Collect IT blocks in all affected basic blocks.
std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;
for (auto *MBB : BasicBlocks) {
  for (auto &MI : *MBB) {
    if (MI.getOpcode() != ARM::t2IT)
      continue;
    RDA->getReachingLocalUses(&MI, ARM::ITSTATE, ITBlocks[&MI]);
  }
}

// If we're removing all of the instructions within an IT block, then
// also remove the IT instruction.
SmallPtrSet<MachineInstr*, 2> ModifiedITs;
for (auto *MI : Killed) {
  if (MachineOperand *MO = MI->findRegisterUseOperand(ARM::ITSTATE)) {
    MachineInstr *IT = RDA->getMIOperand(MI, *MO);
    auto &CurrentBlock = ITBlocks[IT];
    CurrentBlock.erase(MI);
    if (CurrentBlock.empty())
      ModifiedITs.erase(IT);
    else
      ModifiedITs.insert(IT);
  }
}

// Delete the killed instructions only if we don't have any IT blocks that
// need to be modified because we need to fixup the mask.
// TODO: Handle cases where IT blocks are modified.
if (ModifiedITs.empty()) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Will remove iteration count:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Will remove iteration count:\n"
; for (auto *MI : Killed) dbgs() << " - " << *MI;
 } } while (false)
             for (auto *MI : Killed)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Will remove iteration count:\n"
; for (auto *MI : Killed) dbgs() << " - " << *MI;
 } } while (false)
               dbgs() << " - " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Will remove iteration count:\n"
; for (auto *MI : Killed) dbgs() << " - " << *MI;
 } } while (false);
  LoLoop.ToRemove.insert(Killed.begin(), Killed.end());
} else
  LLVM_DEBUG(dbgs() << "ARM Loops: Would need to modify IT block(s).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Would need to modify IT block(s).\n"
; } } while (false);
1228}

1230MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Expanding LoopStart.\n"
; } } while (false);
// When using tail-predication, try to delete the dead code that was used to
// calculate the number of loop iterations.
IterationCountDCE(LoLoop);

MachineInstr *InsertPt = LoLoop.InsertPt;
MachineInstr *Start = LoLoop.Start;
MachineBasicBlock *MBB = InsertPt->getParent();
bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart;
unsigned Opc = LoLoop.getStartOpcode();
MachineOperand &Count = LoLoop.getLoopStartOperand();

MachineInstrBuilder MIB =
  BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc));

MIB.addDef(ARM::LR);
MIB.add(Count);
if (!IsDo)
  MIB.add(Start->getOperand(1));

// If we're inserting at a mov lr, then remove it as it's redundant.
if (InsertPt != Start)
  LoLoop.ToRemove.insert(InsertPt);
LoLoop.ToRemove.insert(Start);
LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Inserted start: "
 << *MIB; } } while (false);
return &*MIB;
1257}

1259void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
auto RemovePredicate = [](MachineInstr *MI) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Removing predicate from: "
 << *MI; } } while (false);
  if (int PIdx = llvm::findFirstVPTPredOperandIdx(*MI)) {
    assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&((MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
 "Expected Then predicate!") ? static_cast<void> (0) : __assert_fail
 ("MI->getOperand(PIdx).getImm() == ARMVCC::Then && \"Expected Then predicate!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 1264, __PRETTY_FUNCTION__))
           "Expected Then predicate!")((MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
 "Expected Then predicate!") ? static_cast<void> (0) : __assert_fail
 ("MI->getOperand(PIdx).getImm() == ARMVCC::Then && \"Expected Then predicate!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 1264, __PRETTY_FUNCTION__));
    MI->getOperand(PIdx).setImm(ARMVCC::None);
    MI->getOperand(PIdx+1).setReg(0);
  } else
    llvm_unreachable("trying to unpredicate a non-predicated instruction")::llvm::llvm_unreachable_internal("trying to unpredicate a non-predicated instruction"
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 1268);
};

// There are a few scenarios which we have to fix up:
// 1. VPT Blocks with non-uniform predicates:
//    - a. When the divergent instruction is a vctp
//    - b. When the block uses a vpst, and is only predicated on the vctp
//    - c. When the block uses a vpt and (optionally) contains one or more
//         vctp.
// 2. VPT Blocks with uniform predicates:
//    - a. The block uses a vpst, and is only predicated on the vctp
for (auto &Block : LoLoop.getVPTBlocks()) {
1
Assuming '__begin1' is not equal to '__end1'→
  SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts();
  if (Block.HasNonUniformPredicate()) {
2
←
Calling 'VPTBlock::HasNonUniformPredicate'→
5
←
Returning from 'VPTBlock::HasNonUniformPredicate'→
6
←
Taking true branch→
    PredicatedMI *Divergent = Block.getDivergent();
    if (isVCTP(Divergent->MI)) {
7
←
Calling 'isVCTP'→
11
←
Returning from 'isVCTP'→
12
←
Taking false branch→
      // The vctp will be removed, so the block mask of the vp(s)t will need
      // to be recomputed.
      LoLoop.BlockMasksToRecompute.insert(Block.getPredicateThen());
    } else if (Block.isVPST() && Block.IsOnlyPredicatedOn(LoLoop.VCTP)) {
13
←
Calling 'VPTBlock::isVPST'→
16
←
Returning from 'VPTBlock::isVPST'→
17
←
Calling 'VPTBlock::IsOnlyPredicatedOn'→
21
←
Returning from 'VPTBlock::IsOnlyPredicatedOn'→
22
←
Taking true branch→
      // The VPT block has a non-uniform predicate but it uses a vpst and its
      // entry is guarded only by a vctp, which means we:
      // - Need to remove the original vpst.
      // - Then need to unpredicate any following instructions, until
      //   we come across the divergent vpr def.
      // - Insert a new vpst to predicate the instruction(s) that following
      //   the divergent vpr def.
      // TODO: We could be producing more VPT blocks than necessary and could
      // fold the newly created one into a proceeding one.
      for (auto I = ++MachineBasicBlock::iterator(Block.getPredicateThen()),
23
←
Loop condition is false. Execution continues on line 1301→
           E = ++MachineBasicBlock::iterator(Divergent->MI); I != E; ++I)
        RemovePredicate(&*I);

      unsigned Size = 0;
      auto E = MachineBasicBlock::reverse_iterator(Divergent->MI);
      auto I = MachineBasicBlock::reverse_iterator(Insts.back().MI);
      MachineInstr *InsertAt = nullptr;
24
←
'InsertAt' initialized to a null pointer value→
      while (I != E) {
25
←
Loop condition is false. Execution continues on line 1311→
        InsertAt = &*I;
        ++Size;
        ++I;
      }
      // Create a VPST (with a null mask for now, we'll recompute it later).
      MachineInstrBuilder MIB = BuildMI(*InsertAt->getParent(), InsertAt,
26
←
Called C++ object pointer is null
                                        InsertAt->getDebugLoc(),
                                        TII->get(ARM::MVE_VPST));
      MIB.addImm(0);
      LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getPredicateThen())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Removing VPST: "
 << *Block.getPredicateThen(); } } while (false);
      LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Created VPST: "
 << *MIB; } } while (false);
      LoLoop.ToRemove.insert(Block.getPredicateThen());
      LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
    }
    // Else, if the block uses a vpt, iterate over the block, removing the
    // extra VCTPs it may contain.
    else if (Block.isVPT()) {
      bool RemovedVCTP = false;
      for (PredicatedMI &Elt : Block.getInsts()) {
        MachineInstr *MI = Elt.MI;
        if (isVCTP(MI)) {
          LLVM_DEBUG(dbgs() << "ARM Loops: Removing VCTP: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Removing VCTP: "
 << *MI; } } while (false);
          LoLoop.ToRemove.insert(MI);
          RemovedVCTP = true;
          continue;
        }
      }
      if (RemovedVCTP)
        LoLoop.BlockMasksToRecompute.insert(Block.getPredicateThen());
    }
  } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP) && Block.isVPST()) {
    // A vpt block starting with VPST, is only predicated upon vctp and has no
    // internal vpr defs:
    // - Remove vpst.
    // - Unpredicate the remaining instructions.
    LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getPredicateThen())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Removing VPST: "
 << *Block.getPredicateThen(); } } while (false);
    LoLoop.ToRemove.insert(Block.getPredicateThen());
    for (auto &PredMI : Insts)
      RemovePredicate(PredMI.MI);
  }
}
LLVM_DEBUG(dbgs() << "ARM Loops: Removing remaining VCTPs...\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Removing remaining VCTPs...\n"
; } } while (false);
// Remove the "main" VCTP
LoLoop.ToRemove.insert(LoLoop.VCTP);
LLVM_DEBUG(dbgs() << "    " << *LoLoop.VCTP)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "    " <<
 *LoLoop.VCTP; } } while (false);
// Remove remaining secondary VCTPs
for (MachineInstr *VCTP : LoLoop.SecondaryVCTPs) {
  // All VCTPs that aren't marked for removal yet should be unpredicated ones.
  // The predicated ones should have already been marked for removal when
  // visiting the VPT blocks.
  if (LoLoop.ToRemove.insert(VCTP).second) {
    assert(getVPTInstrPredicate(*VCTP) == ARMVCC::None &&((getVPTInstrPredicate(*VCTP) == ARMVCC::None && "Removing Predicated VCTP without updating the block mask!"
) ? static_cast<void> (0) : __assert_fail ("getVPTInstrPredicate(*VCTP) == ARMVCC::None && \"Removing Predicated VCTP without updating the block mask!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 1358, __PRETTY_FUNCTION__))
           "Removing Predicated VCTP without updating the block mask!")((getVPTInstrPredicate(*VCTP) == ARMVCC::None && "Removing Predicated VCTP without updating the block mask!"
) ? static_cast<void> (0) : __assert_fail ("getVPTInstrPredicate(*VCTP) == ARMVCC::None && \"Removing Predicated VCTP without updating the block mask!\""
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp"
, 1358, __PRETTY_FUNCTION__));
    LLVM_DEBUG(dbgs() << "    " << *VCTP)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "    " <<
 *VCTP; } } while (false);
  }
}
1362}

1364void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {

// Combine the LoopDec and LoopEnd instructions into LE(TP).
auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
  MachineInstr *End = LoLoop.End;
  MachineBasicBlock *MBB = End->getParent();
  unsigned Opc = LoLoop.IsTailPredicationLegal() ?
    ARM::MVE_LETP : ARM::t2LEUpdate;
  MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
                                    TII->get(Opc));
  MIB.addDef(ARM::LR);
  MIB.add(End->getOperand(0));
  MIB.add(End->getOperand(1));
  LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Inserted LE: "
 << *MIB; } } while (false);
  LoLoop.ToRemove.insert(LoLoop.Dec);
  LoLoop.ToRemove.insert(End);
  return &*MIB;
};

// TODO: We should be able to automatically remove these branches before we
// get here - probably by teaching analyzeBranch about the pseudo
// instructions.
// If there is an unconditional branch, after I, that just branches to the
// next block, remove it.
auto RemoveDeadBranch = [](MachineInstr *I) {
  MachineBasicBlock *BB = I->getParent();
  MachineInstr *Terminator = &BB->instr_back();
  if (Terminator->isUnconditionalBranch() && I != Terminator) {
    MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();
    if (BB->isLayoutSuccessor(Succ)) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Removing branch: "
 << *Terminator; } } while (false);
      Terminator->eraseFromParent();
    }
  }
};

if (LoLoop.Revert) {
  if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart)
    RevertWhile(LoLoop.Start);
  else
    LoLoop.Start->eraseFromParent();
  bool FlagsAlreadySet = RevertLoopDec(LoLoop.Dec);
  RevertLoopEnd(LoLoop.End, FlagsAlreadySet);
} else {
  LoLoop.Start = ExpandLoopStart(LoLoop);
  RemoveDeadBranch(LoLoop.Start);
  LoLoop.End = ExpandLoopEnd(LoLoop);
  RemoveDeadBranch(LoLoop.End);
  if (LoLoop.IsTailPredicationLegal())
    ConvertVPTBlocks(LoLoop);
  for (auto *I : LoLoop.ToRemove) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Erasing "
 << *I; } } while (false);
    I->eraseFromParent();
  }
  for (auto *I : LoLoop.BlockMasksToRecompute) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: "
 << *I; } } while (false);
    recomputeVPTBlockMask(*I);
    LLVM_DEBUG(dbgs() << "           ... done: " << *I)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "           ... done: "
 << *I; } } while (false);
  }
}

PostOrderLoopTraversal DFS(LoLoop.ML, *MLI);
DFS.ProcessLoop();
const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder();
for (auto *MBB : PostOrder) {
  recomputeLiveIns(*MBB);
  // FIXME: For some reason, the live-in print order is non-deterministic for
  // our tests and I can't out why... So just sort them.
  MBB->sortUniqueLiveIns();
}

for (auto *MBB : reverse(PostOrder))
  recomputeLivenessFlags(*MBB);

// We've moved, removed and inserted new instructions, so update RDA.
RDA->reset();
1440}

1442bool ARMLowOverheadLoops::RevertNonLoops() {
LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-low-overhead-loops")) { dbgs() << "ARM Loops: Reverting any remaining pseudos...\n"
; } } while (false);
bool Changed = false;

for (auto &MBB : *MF) {
  SmallVector<MachineInstr*, 4> Starts;
  SmallVector<MachineInstr*, 4> Decs;
  SmallVector<MachineInstr*, 4> Ends;

  for (auto &I : MBB) {
    if (isLoopStart(I))
      Starts.push_back(&I);
    else if (I.getOpcode() == ARM::t2LoopDec)
      Decs.push_back(&I);
    else if (I.getOpcode() == ARM::t2LoopEnd)
      Ends.push_back(&I);
  }

  if (Starts.empty() && Decs.empty() && Ends.empty())
    continue;

  Changed = true;

  for (auto *Start : Starts) {
    if (Start->getOpcode() == ARM::t2WhileLoopStart)
      RevertWhile(Start);
    else
      Start->eraseFromParent();
  }
  for (auto *Dec : Decs)
    RevertLoopDec(Dec);

  for (auto *End : Ends)
    RevertLoopEnd(End);
}
return Changed;
1478}

1480FunctionPass *llvm::createARMLowOverheadLoopsPass() {
return new ARMLowOverheadLoops();
1482}

←

/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMBaseInstrInfo.h

1//===-- ARMBaseInstrInfo.h - ARM Base Instruction Information ---*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains the Base ARM implementation of the TargetInstrInfo class.
10//
11//===----------------------------------------------------------------------===//

13#ifndef LLVM_LIB_TARGET_ARM_ARMBASEINSTRINFO_H
14#define LLVM_LIB_TARGET_ARM_ARMBASEINSTRINFO_H

16#include "MCTargetDesc/ARMBaseInfo.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/SmallSet.h"
19#include "llvm/CodeGen/MachineBasicBlock.h"
20#include "llvm/CodeGen/MachineInstr.h"
21#include "llvm/CodeGen/MachineInstrBuilder.h"
22#include "llvm/CodeGen/MachineOperand.h"
23#include "llvm/CodeGen/TargetInstrInfo.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/IR/IntrinsicsARM.h"
26#include <array>
27#include <cstdint>

29#define GET_INSTRINFO_HEADER
30#include "ARMGenInstrInfo.inc"

32namespace llvm {

34class ARMBaseRegisterInfo;
35class ARMSubtarget;

37class ARMBaseInstrInfo : public ARMGenInstrInfo {
const ARMSubtarget &Subtarget;

40protected:
// Can be only subclassed.
explicit ARMBaseInstrInfo(const ARMSubtarget &STI);

void expandLoadStackGuardBase(MachineBasicBlock::iterator MI,
                              unsigned LoadImmOpc, unsigned LoadOpc) const;

/// Build the equivalent inputs of a REG_SEQUENCE for the given \p MI
/// and \p DefIdx.
/// \p [out] InputRegs of the equivalent REG_SEQUENCE. Each element of
/// the list is modeled as <Reg:SubReg, SubIdx>.
/// E.g., REG_SEQUENCE %1:sub1, sub0, %2, sub1 would produce
/// two elements:
/// - %1:sub1, sub0
/// - %2<:0>, sub1
///
/// \returns true if it is possible to build such an input sequence
/// with the pair \p MI, \p DefIdx. False otherwise.
///
/// \pre MI.isRegSequenceLike().
bool getRegSequenceLikeInputs(
    const MachineInstr &MI, unsigned DefIdx,
    SmallVectorImpl<RegSubRegPairAndIdx> &InputRegs) const override;

/// Build the equivalent inputs of a EXTRACT_SUBREG for the given \p MI
/// and \p DefIdx.
/// \p [out] InputReg of the equivalent EXTRACT_SUBREG.
/// E.g., EXTRACT_SUBREG %1:sub1, sub0, sub1 would produce:
/// - %1:sub1, sub0
///
/// \returns true if it is possible to build such an input sequence
/// with the pair \p MI, \p DefIdx. False otherwise.
///
/// \pre MI.isExtractSubregLike().
bool getExtractSubregLikeInputs(const MachineInstr &MI, unsigned DefIdx,
                                RegSubRegPairAndIdx &InputReg) const override;

/// Build the equivalent inputs of a INSERT_SUBREG for the given \p MI
/// and \p DefIdx.
/// \p [out] BaseReg and \p [out] InsertedReg contain
/// the equivalent inputs of INSERT_SUBREG.
/// E.g., INSERT_SUBREG %0:sub0, %1:sub1, sub3 would produce:
/// - BaseReg: %0:sub0
/// - InsertedReg: %1:sub1, sub3
///
/// \returns true if it is possible to build such an input sequence
/// with the pair \p MI, \p DefIdx. False otherwise.
///
/// \pre MI.isInsertSubregLike().
bool
getInsertSubregLikeInputs(const MachineInstr &MI, unsigned DefIdx,
                          RegSubRegPair &BaseReg,
                          RegSubRegPairAndIdx &InsertedReg) const override;

/// Commutes the operands in the given instruction.
/// The commutable operands are specified by their indices OpIdx1 and OpIdx2.
///
/// Do not call this method for a non-commutable instruction or for
/// non-commutable pair of operand indices OpIdx1 and OpIdx2.
/// Even though the instruction is commutable, the method may still
/// fail to commute the operands, null pointer is returned in such cases.
MachineInstr *commuteInstructionImpl(MachineInstr &MI, bool NewMI,
                                     unsigned OpIdx1,
                                     unsigned OpIdx2) const override;
/// If the specific machine instruction is an instruction that moves/copies
/// value from one register to another register return destination and source
/// registers as machine operands.
Optional<DestSourcePair>
isCopyInstrImpl(const MachineInstr &MI) const override;

/// Specialization of \ref TargetInstrInfo::describeLoadedValue, used to
/// enhance debug entry value descriptions for ARM targets.
Optional<ParamLoadedValue> describeLoadedValue(const MachineInstr &MI,
                                               Register Reg) const override;

115public:
// Return whether the target has an explicit NOP encoding.
bool hasNOP() const;

// Return the non-pre/post incrementing version of 'Opc'. Return 0
// if there is not such an opcode.
virtual unsigned getUnindexedOpcode(unsigned Opc) const = 0;

MachineInstr *convertToThreeAddress(MachineFunction::iterator &MFI,
                                    MachineInstr &MI,
                                    LiveVariables *LV) const override;

virtual const ARMBaseRegisterInfo &getRegisterInfo() const = 0;
const ARMSubtarget &getSubtarget() const { return Subtarget; }

ScheduleHazardRecognizer *
CreateTargetHazardRecognizer(const TargetSubtargetInfo *STI,
                             const ScheduleDAG *DAG) const override;

ScheduleHazardRecognizer *
CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II,
                                   const ScheduleDAG *DAG) const override;

// Branch analysis.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                   MachineBasicBlock *&FBB,
                   SmallVectorImpl<MachineOperand> &Cond,
                   bool AllowModify = false) const override;
unsigned removeBranch(MachineBasicBlock &MBB,
                      int *BytesRemoved = nullptr) const override;
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
                      MachineBasicBlock *FBB, ArrayRef<MachineOperand> Cond,
                      const DebugLoc &DL,
                      int *BytesAdded = nullptr) const override;

bool
reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;

// Predication support.
bool isPredicated(const MachineInstr &MI) const override;

// MIR printer helper function to annotate Operands with a comment.
std::string
createMIROperandComment(const MachineInstr &MI, const MachineOperand &Op,
                        unsigned OpIdx,
                        const TargetRegisterInfo *TRI) const override;

ARMCC::CondCodes getPredicate(const MachineInstr &MI) const {
  int PIdx = MI.findFirstPredOperandIdx();
  return PIdx != -1 ? (ARMCC::CondCodes)MI.getOperand(PIdx).getImm()
                    : ARMCC::AL;
}

bool PredicateInstruction(MachineInstr &MI,
                          ArrayRef<MachineOperand> Pred) const override;

bool SubsumesPredicate(ArrayRef<MachineOperand> Pred1,
                       ArrayRef<MachineOperand> Pred2) const override;

bool DefinesPredicate(MachineInstr &MI,
                      std::vector<MachineOperand> &Pred) const override;

bool isPredicable(const MachineInstr &MI) const override;

// CPSR defined in instruction
static bool isCPSRDefined(const MachineInstr &MI);
bool isAddrMode3OpImm(const MachineInstr &MI, unsigned Op) const;
bool isAddrMode3OpMinusReg(const MachineInstr &MI, unsigned Op) const;

// Load, scaled register offset
bool isLdstScaledReg(const MachineInstr &MI, unsigned Op) const;
// Load, scaled register offset, not plus LSL2
bool isLdstScaledRegNotPlusLsl2(const MachineInstr &MI, unsigned Op) const;
// Minus reg for ldstso addr mode
bool isLdstSoMinusReg(const MachineInstr &MI, unsigned Op) const;
// Scaled register offset in address mode 2
bool isAm2ScaledReg(const MachineInstr &MI, unsigned Op) const;
// Load multiple, base reg in list
bool isLDMBaseRegInList(const MachineInstr &MI) const;
// get LDM variable defs size
unsigned getLDMVariableDefsSize(const MachineInstr &MI) const;

/// GetInstSize - Returns the size of the specified MachineInstr.
///
unsigned getInstSizeInBytes(const MachineInstr &MI) const override;

unsigned isLoadFromStackSlot(const MachineInstr &MI,
                             int &FrameIndex) const override;
unsigned isStoreToStackSlot(const MachineInstr &MI,
                            int &FrameIndex) const override;
unsigned isLoadFromStackSlotPostFE(const MachineInstr &MI,
                                   int &FrameIndex) const override;
unsigned isStoreToStackSlotPostFE(const MachineInstr &MI,
                                  int &FrameIndex) const override;

void copyToCPSR(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
                unsigned SrcReg, bool KillSrc,
                const ARMSubtarget &Subtarget) const;
void copyFromCPSR(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
                  unsigned DestReg, bool KillSrc,
                  const ARMSubtarget &Subtarget) const;

void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
                 const DebugLoc &DL, MCRegister DestReg, MCRegister SrcReg,
                 bool KillSrc) const override;

void storeRegToStackSlot(MachineBasicBlock &MBB,
                         MachineBasicBlock::iterator MBBI,
                         Register SrcReg, bool isKill, int FrameIndex,
                         const TargetRegisterClass *RC,
                         const TargetRegisterInfo *TRI) const override;

void loadRegFromStackSlot(MachineBasicBlock &MBB,
                          MachineBasicBlock::iterator MBBI,
                          Register DestReg, int FrameIndex,
                          const TargetRegisterClass *RC,
                          const TargetRegisterInfo *TRI) const override;

bool expandPostRAPseudo(MachineInstr &MI) const override;

bool shouldSink(const MachineInstr &MI) const override;

void reMaterialize(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
                   Register DestReg, unsigned SubIdx,
                   const MachineInstr &Orig,
                   const TargetRegisterInfo &TRI) const override;

MachineInstr &
duplicate(MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
          const MachineInstr &Orig) const override;

const MachineInstrBuilder &AddDReg(MachineInstrBuilder &MIB, unsigned Reg,
                                   unsigned SubIdx, unsigned State,
                                   const TargetRegisterInfo *TRI) const;

bool produceSameValue(const MachineInstr &MI0, const MachineInstr &MI1,
                      const MachineRegisterInfo *MRI) const override;

/// areLoadsFromSameBasePtr - This is used by the pre-regalloc scheduler to
/// determine if two loads are loading from the same base address. It should
/// only return true if the base pointers are the same and the only
/// differences between the two addresses is the offset. It also returns the
/// offsets by reference.
bool areLoadsFromSameBasePtr(SDNode *Load1, SDNode *Load2, int64_t &Offset1,
                             int64_t &Offset2) const override;

/// shouldScheduleLoadsNear - This is a used by the pre-regalloc scheduler to
/// determine (in conjunction with areLoadsFromSameBasePtr) if two loads
/// should be scheduled togther. On some targets if two loads are loading from
/// addresses in the same cache line, it's better if they are scheduled
/// together. This function takes two integers that represent the load offsets
/// from the common base address. It returns true if it decides it's desirable
/// to schedule the two loads together. "NumLoads" is the number of loads that
/// have already been scheduled after Load1.
bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2,
                             int64_t Offset1, int64_t Offset2,
                             unsigned NumLoads) const override;

bool isSchedulingBoundary(const MachineInstr &MI,
                          const MachineBasicBlock *MBB,
                          const MachineFunction &MF) const override;

bool isProfitableToIfCvt(MachineBasicBlock &MBB,
                         unsigned NumCycles, unsigned ExtraPredCycles,
                         BranchProbability Probability) const override;

bool isProfitableToIfCvt(MachineBasicBlock &TMBB, unsigned NumT,
                         unsigned ExtraT, MachineBasicBlock &FMBB,
                         unsigned NumF, unsigned ExtraF,
                         BranchProbability Probability) const override;

bool isProfitableToDupForIfCvt(MachineBasicBlock &MBB, unsigned NumCycles,
                               BranchProbability Probability) const override {
  return NumCycles == 1;
}

unsigned extraSizeToPredicateInstructions(const MachineFunction &MF,
                                          unsigned NumInsts) const override;
unsigned predictBranchSizeForIfCvt(MachineInstr &MI) const override;

bool isProfitableToUnpredicate(MachineBasicBlock &TMBB,
                               MachineBasicBlock &FMBB) const override;

/// analyzeCompare - For a comparison instruction, return the source registers
/// in SrcReg and SrcReg2 if having two register operands, and the value it
/// compares against in CmpValue. Return true if the comparison instruction
/// can be analyzed.
bool analyzeCompare(const MachineInstr &MI, Register &SrcReg,
                    Register &SrcReg2, int &CmpMask,
                    int &CmpValue) const override;

/// optimizeCompareInstr - Convert the instruction to set the zero flag so
/// that we can remove a "comparison with zero"; Remove a redundant CMP
/// instruction if the flags can be updated in the same way by an earlier
/// instruction such as SUB.
bool optimizeCompareInstr(MachineInstr &CmpInstr, Register SrcReg,
                          Register SrcReg2, int CmpMask, int CmpValue,
                          const MachineRegisterInfo *MRI) const override;

bool analyzeSelect(const MachineInstr &MI,
                   SmallVectorImpl<MachineOperand> &Cond, unsigned &TrueOp,
                   unsigned &FalseOp, bool &Optimizable) const override;

MachineInstr *optimizeSelect(MachineInstr &MI,
                             SmallPtrSetImpl<MachineInstr *> &SeenMIs,
                             bool) const override;

/// FoldImmediate - 'Reg' is known to be defined by a move immediate
/// instruction, try to fold the immediate into the use instruction.
bool FoldImmediate(MachineInstr &UseMI, MachineInstr &DefMI, Register Reg,
                   MachineRegisterInfo *MRI) const override;

unsigned getNumMicroOps(const InstrItineraryData *ItinData,
                        const MachineInstr &MI) const override;

int getOperandLatency(const InstrItineraryData *ItinData,
                      const MachineInstr &DefMI, unsigned DefIdx,
                      const MachineInstr &UseMI,
                      unsigned UseIdx) const override;
int getOperandLatency(const InstrItineraryData *ItinData,
                      SDNode *DefNode, unsigned DefIdx,
                      SDNode *UseNode, unsigned UseIdx) const override;

/// VFP/NEON execution domains.
std::pair<uint16_t, uint16_t>
getExecutionDomain(const MachineInstr &MI) const override;
void setExecutionDomain(MachineInstr &MI, unsigned Domain) const override;

unsigned
getPartialRegUpdateClearance(const MachineInstr &, unsigned,
                             const TargetRegisterInfo *) const override;
void breakPartialRegDependency(MachineInstr &, unsigned,
                               const TargetRegisterInfo *TRI) const override;

/// Get the number of addresses by LDM or VLDM or zero for unknown.
unsigned getNumLDMAddresses(const MachineInstr &MI) const;

std::pair<unsigned, unsigned>
decomposeMachineOperandsTargetFlags(unsigned TF) const override;
ArrayRef<std::pair<unsigned, const char *>>
getSerializableDirectMachineOperandTargetFlags() const override;
ArrayRef<std::pair<unsigned, const char *>>
getSerializableBitmaskMachineOperandTargetFlags() const override;

/// ARM supports the MachineOutliner.
bool isFunctionSafeToOutlineFrom(MachineFunction &MF,
                                 bool OutlineFromLinkOnceODRs) const override;
outliner::OutlinedFunction getOutliningCandidateInfo(
    std::vector<outliner::Candidate> &RepeatedSequenceLocs) const override;
outliner::InstrType getOutliningType(MachineBasicBlock::iterator &MIT,
                                     unsigned Flags) const override;
bool isMBBSafeToOutlineFrom(MachineBasicBlock &MBB,
                            unsigned &Flags) const override;
void buildOutlinedFrame(MachineBasicBlock &MBB, MachineFunction &MF,
                        const outliner::OutlinedFunction &OF) const override;
MachineBasicBlock::iterator
insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
                   MachineBasicBlock::iterator &It, MachineFunction &MF,
                   const outliner::Candidate &C) const override;

/// Enable outlining by default at -Oz.
bool shouldOutlineFromFunctionByDefault(MachineFunction &MF) const override;

378private:
/// Returns an unused general-purpose register which can be used for
/// constructing an outlined call if one exists. Returns 0 otherwise.
unsigned findRegisterToSaveLRTo(const outliner::Candidate &C) const;

// Adds an instruction which saves the link register on top of the stack into
/// the MachineBasicBlock \p MBB at position \p It.
void saveLROnStack(MachineBasicBlock &MBB,
                   MachineBasicBlock::iterator &It) const;

/// Adds an instruction which restores the link register from the top the
/// stack into the MachineBasicBlock \p MBB at position \p It.
void restoreLRFromStack(MachineBasicBlock &MBB,
                        MachineBasicBlock::iterator &It) const;

unsigned getInstBundleLength(const MachineInstr &MI) const;

int getVLDMDefCycle(const InstrItineraryData *ItinData,
                    const MCInstrDesc &DefMCID,
                    unsigned DefClass,
                    unsigned DefIdx, unsigned DefAlign) const;
int getLDMDefCycle(const InstrItineraryData *ItinData,
                   const MCInstrDesc &DefMCID,
                   unsigned DefClass,
                   unsigned DefIdx, unsigned DefAlign) const;
int getVSTMUseCycle(const InstrItineraryData *ItinData,
                    const MCInstrDesc &UseMCID,
                    unsigned UseClass,
                    unsigned UseIdx, unsigned UseAlign) const;
int getSTMUseCycle(const InstrItineraryData *ItinData,
                   const MCInstrDesc &UseMCID,
                   unsigned UseClass,
                   unsigned UseIdx, unsigned UseAlign) const;
int getOperandLatency(const InstrItineraryData *ItinData,
                      const MCInstrDesc &DefMCID,
                      unsigned DefIdx, unsigned DefAlign,
                      const MCInstrDesc &UseMCID,
                      unsigned UseIdx, unsigned UseAlign) const;

int getOperandLatencyImpl(const InstrItineraryData *ItinData,
                          const MachineInstr &DefMI, unsigned DefIdx,
                          const MCInstrDesc &DefMCID, unsigned DefAdj,
                          const MachineOperand &DefMO, unsigned Reg,
                          const MachineInstr &UseMI, unsigned UseIdx,
                          const MCInstrDesc &UseMCID, unsigned UseAdj) const;

unsigned getPredicationCost(const MachineInstr &MI) const override;

unsigned getInstrLatency(const InstrItineraryData *ItinData,
                         const MachineInstr &MI,
                         unsigned *PredCost = nullptr) const override;

int getInstrLatency(const InstrItineraryData *ItinData,
                    SDNode *Node) const override;

bool hasHighOperandLatency(const TargetSchedModel &SchedModel,
                           const MachineRegisterInfo *MRI,
                           const MachineInstr &DefMI, unsigned DefIdx,
                           const MachineInstr &UseMI,
                           unsigned UseIdx) const override;
bool hasLowDefLatency(const TargetSchedModel &SchedModel,
                      const MachineInstr &DefMI,
                      unsigned DefIdx) const override;

/// verifyInstruction - Perform target specific instruction verification.
bool verifyInstruction(const MachineInstr &MI,
                       StringRef &ErrInfo) const override;

virtual void expandLoadStackGuard(MachineBasicBlock::iterator MI) const = 0;

void expandMEMCPY(MachineBasicBlock::iterator) const;

/// Identify instructions that can be folded into a MOVCC instruction, and
/// return the defining instruction.
MachineInstr *canFoldIntoMOVCC(Register Reg, const MachineRegisterInfo &MRI,
                               const TargetInstrInfo *TII) const;

bool isReallyTriviallyReMaterializable(const MachineInstr &MI,
                                       AAResults *AA) const override;

458private:
/// Modeling special VFP / NEON fp MLA / MLS hazards.

/// MLxEntryMap - Map fp MLA / MLS to the corresponding entry in the internal
/// MLx table.
DenseMap<unsigned, unsigned> MLxEntryMap;

/// MLxHazardOpcodes - Set of add / sub and multiply opcodes that would cause
/// stalls when scheduled together with fp MLA / MLS opcodes.
SmallSet<unsigned, 16> MLxHazardOpcodes;

469public:
/// isFpMLxInstruction - Return true if the specified opcode is a fp MLA / MLS
/// instruction.
bool isFpMLxInstruction(unsigned Opcode) const {
  return MLxEntryMap.count(Opcode);
}

/// isFpMLxInstruction - This version also returns the multiply opcode and the
/// addition / subtraction opcode to expand to. Return true for 'HasLane' for
/// the MLX instructions with an extra lane operand.
bool isFpMLxInstruction(unsigned Opcode, unsigned &MulOpc,
                        unsigned &AddSubOpc, bool &NegAcc,
                        bool &HasLane) const;

/// canCauseFpMLxStall - Return true if an instruction of the specified opcode
/// will cause stalls when scheduled after (within 4-cycle window) a fp
/// MLA / MLS instruction.
bool canCauseFpMLxStall(unsigned Opcode) const {
  return MLxHazardOpcodes.count(Opcode);
}

/// Returns true if the instruction has a shift by immediate that can be
/// executed in one cycle less.
bool isSwiftFastImmShift(const MachineInstr *MI) const;

/// Returns predicate register associated with the given frame instruction.
unsigned getFramePred(const MachineInstr &MI) const {
  assert(isFrameInstr(MI))((isFrameInstr(MI)) ? static_cast<void> (0) : __assert_fail
 ("isFrameInstr(MI)", "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMBaseInstrInfo.h"
, 496, __PRETTY_FUNCTION__));
  // Operands of ADJCALLSTACKDOWN/ADJCALLSTACKUP:
  // - argument declared in the pattern:
  // 0 - frame size
  // 1 - arg of CALLSEQ_START/CALLSEQ_END
  // 2 - predicate code (like ARMCC::AL)
  // - added by predOps:
  // 3 - predicate reg
  return MI.getOperand(3).getReg();
}

Optional<RegImmPair> isAddImmediate(const MachineInstr &MI,
                                    Register Reg) const override;
509};

511/// Get the operands corresponding to the given \p Pred value. By default, the
512/// predicate register is assumed to be 0 (no register), but you can pass in a
513/// \p PredReg if that is not the case.
514static inline std::array<MachineOperand, 2> predOps(ARMCC::CondCodes Pred,
                                                  unsigned PredReg = 0) {
return {{MachineOperand::CreateImm(static_cast<int64_t>(Pred)),
         MachineOperand::CreateReg(PredReg, false)}};
518}

520/// Get the operand corresponding to the conditional code result. By default,
521/// this is 0 (no register).
522static inline MachineOperand condCodeOp(unsigned CCReg = 0) {
return MachineOperand::CreateReg(CCReg, false);
524}

526/// Get the operand corresponding to the conditional code result for Thumb1.
527/// This operand will always refer to CPSR and it will have the Define flag set.
528/// You can optionally set the Dead flag by means of \p isDead.
529static inline MachineOperand t1CondCodeOp(bool isDead = false) {
return MachineOperand::CreateReg(ARM::CPSR,
                                 /*Define*/ true, /*Implicit*/ false,
                                 /*Kill*/ false, isDead);
533}

535static inline
536bool isUncondBranchOpcode(int Opc) {
return Opc == ARM::B || Opc == ARM::tB || Opc == ARM::t2B;
538}

540// This table shows the VPT instruction variants, i.e. the different
541// mask field encodings, see also B5.6. Predication/conditional execution in
542// the ArmARM.
543static inline bool isVPTOpcode(int Opc) {
return Opc == ARM::MVE_VPTv16i8 || Opc == ARM::MVE_VPTv16u8 ||
       Opc == ARM::MVE_VPTv16s8 || Opc == ARM::MVE_VPTv8i16 ||
       Opc == ARM::MVE_VPTv8u16 || Opc == ARM::MVE_VPTv8s16 ||
       Opc == ARM::MVE_VPTv4i32 || Opc == ARM::MVE_VPTv4u32 ||
       Opc == ARM::MVE_VPTv4s32 || Opc == ARM::MVE_VPTv4f32 ||
       Opc == ARM::MVE_VPTv8f16 || Opc == ARM::MVE_VPTv16i8r ||
       Opc == ARM::MVE_VPTv16u8r || Opc == ARM::MVE_VPTv16s8r ||
       Opc == ARM::MVE_VPTv8i16r || Opc == ARM::MVE_VPTv8u16r ||
       Opc == ARM::MVE_VPTv8s16r || Opc == ARM::MVE_VPTv4i32r ||
       Opc == ARM::MVE_VPTv4u32r || Opc == ARM::MVE_VPTv4s32r ||
       Opc == ARM::MVE_VPTv4f32r || Opc == ARM::MVE_VPTv8f16r ||
       Opc == ARM::MVE_VPST;
556}

558static inline
559unsigned VCMPOpcodeToVPT(unsigned Opcode) {
switch (Opcode) {
default:
  return 0;
case ARM::MVE_VCMPf32:
  return ARM::MVE_VPTv4f32;
case ARM::MVE_VCMPf16:
  return ARM::MVE_VPTv8f16;
case ARM::MVE_VCMPi8:
  return ARM::MVE_VPTv16i8;
case ARM::MVE_VCMPi16:
  return ARM::MVE_VPTv8i16;
case ARM::MVE_VCMPi32:
  return ARM::MVE_VPTv4i32;
case ARM::MVE_VCMPu8:
  return ARM::MVE_VPTv16u8;
case ARM::MVE_VCMPu16:
  return ARM::MVE_VPTv8u16;
case ARM::MVE_VCMPu32:
  return ARM::MVE_VPTv4u32;
case ARM::MVE_VCMPs8:
  return ARM::MVE_VPTv16s8;
case ARM::MVE_VCMPs16:
  return ARM::MVE_VPTv8s16;
case ARM::MVE_VCMPs32:
  return ARM::MVE_VPTv4s32;

case ARM::MVE_VCMPf32r:
  return ARM::MVE_VPTv4f32r;
case ARM::MVE_VCMPf16r:
  return ARM::MVE_VPTv8f16r;
case ARM::MVE_VCMPi8r:
  return ARM::MVE_VPTv16i8r;
case ARM::MVE_VCMPi16r:
  return ARM::MVE_VPTv8i16r;
case ARM::MVE_VCMPi32r:
  return ARM::MVE_VPTv4i32r;
case ARM::MVE_VCMPu8r:
  return ARM::MVE_VPTv16u8r;
case ARM::MVE_VCMPu16r:
  return ARM::MVE_VPTv8u16r;
case ARM::MVE_VCMPu32r:
  return ARM::MVE_VPTv4u32r;
case ARM::MVE_VCMPs8r:
  return ARM::MVE_VPTv16s8r;
case ARM::MVE_VCMPs16r:
  return ARM::MVE_VPTv8s16r;
case ARM::MVE_VCMPs32r:
  return ARM::MVE_VPTv4s32r;
}
609}

611static inline
612unsigned VCTPOpcodeToLSTP(unsigned Opcode, bool IsDoLoop) {
switch (Opcode) {
default:
  llvm_unreachable("unhandled vctp opcode")::llvm::llvm_unreachable_internal("unhandled vctp opcode", "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMBaseInstrInfo.h"
, 615);
  break;
case ARM::MVE_VCTP8:
  return IsDoLoop ? ARM::MVE_DLSTP_8 : ARM::MVE_WLSTP_8;
case ARM::MVE_VCTP16:
  return IsDoLoop ? ARM::MVE_DLSTP_16 : ARM::MVE_WLSTP_16;
case ARM::MVE_VCTP32:
  return IsDoLoop ? ARM::MVE_DLSTP_32 : ARM::MVE_WLSTP_32;
case ARM::MVE_VCTP64:
  return IsDoLoop ? ARM::MVE_DLSTP_64 : ARM::MVE_WLSTP_64;
}
return 0;
627}

629static inline unsigned getTailPredVectorWidth(unsigned Opcode) {
switch (Opcode) {
default:
  llvm_unreachable("unhandled vctp opcode")::llvm::llvm_unreachable_internal("unhandled vctp opcode", "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMBaseInstrInfo.h"
, 632);
case ARM::MVE_VCTP8:  return 16;
case ARM::MVE_VCTP16: return 8;
case ARM::MVE_VCTP32: return 4;
case ARM::MVE_VCTP64: return 2;
}
return 0;
639}

641static inline bool isVCTP(const MachineInstr *MI) {
switch (MI->getOpcode()) {
8
←
Control jumps to the 'default' case at line 643→
default:
  break;
9
←
 Execution continues on line 651→
case ARM::MVE_VCTP8:
case ARM::MVE_VCTP16:
case ARM::MVE_VCTP32:
case ARM::MVE_VCTP64:
  return true;
}
return false;
10
←
Returning zero, which participates in a condition later→
652}

654static inline
655bool isLoopStart(MachineInstr &MI) {
return MI.getOpcode() == ARM::t2DoLoopStart ||
       MI.getOpcode() == ARM::t2WhileLoopStart;
658}

660static inline
661bool isCondBranchOpcode(int Opc) {
return Opc == ARM::Bcc || Opc == ARM::tBcc || Opc == ARM::t2Bcc;
663}

665static inline bool isJumpTableBranchOpcode(int Opc) {
return Opc == ARM::BR_JTr || Opc == ARM::BR_JTm_i12 ||
       Opc == ARM::BR_JTm_rs || Opc == ARM::BR_JTadd || Opc == ARM::tBR_JTr ||
       Opc == ARM::t2BR_JT;
669}

671static inline
672bool isIndirectBranchOpcode(int Opc) {
return Opc == ARM::BX || Opc == ARM::MOVPCRX || Opc == ARM::tBRIND;
674}

676static inline bool isPopOpcode(int Opc) {
return Opc == ARM::tPOP_RET || Opc == ARM::LDMIA_RET ||
       Opc == ARM::t2LDMIA_RET || Opc == ARM::tPOP || Opc == ARM::LDMIA_UPD ||
       Opc == ARM::t2LDMIA_UPD || Opc == ARM::VLDMDIA_UPD;
680}

682static inline bool isPushOpcode(int Opc) {
return Opc == ARM::tPUSH || Opc == ARM::t2STMDB_UPD ||
       Opc == ARM::STMDB_UPD || Opc == ARM::VSTMDDB_UPD;
685}

687static inline bool isSubImmOpcode(int Opc) {
return Opc == ARM::SUBri ||
       Opc == ARM::tSUBi3 || Opc == ARM::tSUBi8 ||
       Opc == ARM::tSUBSi3 || Opc == ARM::tSUBSi8 ||
       Opc == ARM::t2SUBri || Opc == ARM::t2SUBri12 || Opc == ARM::t2SUBSri;
692}

694static inline bool isMovRegOpcode(int Opc) {
return Opc == ARM::MOVr || Opc == ARM::tMOVr || Opc == ARM::t2MOVr;
696}
697/// isValidCoprocessorNumber - decide whether an explicit coprocessor
698/// number is legal in generic instructions like CDP. The answer can
699/// vary with the subtarget.
700static inline bool isValidCoprocessorNumber(unsigned Num,
                                          const FeatureBitset& featureBits) {
// In Armv7 and Armv8-M CP10 and CP11 clash with VFP/NEON, however, the
// coprocessor is still valid for CDP/MCR/MRC and friends. Allowing it is
// useful for code which is shared with older architectures which do not know
// the new VFP/NEON mnemonics.

// Armv8-A disallows everything *other* than 111x (CP14 and CP15).
if (featureBits[ARM::HasV8Ops] && (Num & 0xE) != 0xE)
  return false;

// Armv8.1-M disallows 100x (CP8,CP9) and 111x (CP14,CP15)
// which clash with MVE.
if (featureBits[ARM::HasV8_1MMainlineOps] &&
    ((Num & 0xE) == 0x8 || (Num & 0xE) == 0xE))
  return false;

return true;
718}

720/// getInstrPredicate - If instruction is predicated, returns its predicate
721/// condition, otherwise returns AL. It also returns the condition code
722/// register by reference.
723ARMCC::CondCodes getInstrPredicate(const MachineInstr &MI, Register &PredReg);

725unsigned getMatchingCondBranchOpcode(unsigned Opc);

727/// Map pseudo instructions that imply an 'S' bit onto real opcodes. Whether
728/// the instruction is encoded with an 'S' bit is determined by the optional
729/// CPSR def operand.
730unsigned convertAddSubFlagsOpcode(unsigned OldOpc);

732/// emitARMRegPlusImmediate / emitT2RegPlusImmediate - Emits a series of
733/// instructions to materializea destreg = basereg + immediate in ARM / Thumb2
734/// code.
735void emitARMRegPlusImmediate(MachineBasicBlock &MBB,
                           MachineBasicBlock::iterator &MBBI,
                           const DebugLoc &dl, Register DestReg,
                           Register BaseReg, int NumBytes,
                           ARMCC::CondCodes Pred, Register PredReg,
                           const ARMBaseInstrInfo &TII, unsigned MIFlags = 0);

742void emitT2RegPlusImmediate(MachineBasicBlock &MBB,
                          MachineBasicBlock::iterator &MBBI,
                          const DebugLoc &dl, Register DestReg,
                          Register BaseReg, int NumBytes,
                          ARMCC::CondCodes Pred, Register PredReg,
                          const ARMBaseInstrInfo &TII, unsigned MIFlags = 0);
748void emitThumbRegPlusImmediate(MachineBasicBlock &MBB,
                             MachineBasicBlock::iterator &MBBI,
                             const DebugLoc &dl, Register DestReg,
                             Register BaseReg, int NumBytes,
                             const TargetInstrInfo &TII,
                             const ARMBaseRegisterInfo &MRI,
                             unsigned MIFlags = 0);

756/// Tries to add registers to the reglist of a given base-updating
757/// push/pop instruction to adjust the stack by an additional
758/// NumBytes. This can save a few bytes per function in code-size, but
759/// obviously generates more memory traffic. As such, it only takes
760/// effect in functions being optimised for size.
761bool tryFoldSPUpdateIntoPushPop(const ARMSubtarget &Subtarget,
                              MachineFunction &MF, MachineInstr *MI,
                              unsigned NumBytes);

765/// rewriteARMFrameIndex / rewriteT2FrameIndex -
766/// Rewrite MI to access 'Offset' bytes from the FP. Return false if the
767/// offset could not be handled directly in MI, and return the left-over
768/// portion by reference.
769bool rewriteARMFrameIndex(MachineInstr &MI, unsigned FrameRegIdx,
                        Register FrameReg, int &Offset,
                        const ARMBaseInstrInfo &TII);

773bool rewriteT2FrameIndex(MachineInstr &MI, unsigned FrameRegIdx,
                       Register FrameReg, int &Offset,
                       const ARMBaseInstrInfo &TII,
                       const TargetRegisterInfo *TRI);

778/// Return true if Reg is defd between From and To
779bool registerDefinedBetween(unsigned Reg, MachineBasicBlock::iterator From,
                          MachineBasicBlock::iterator To,
                          const TargetRegisterInfo *TRI);

783/// Search backwards from a tBcc to find a tCMPi8 against 0, meaning
784/// we can convert them to a tCBZ or tCBNZ. Return nullptr if not found.
785MachineInstr *findCMPToFoldIntoCBZ(MachineInstr *Br,
                                 const TargetRegisterInfo *TRI);

788void addUnpredicatedMveVpredNOp(MachineInstrBuilder &MIB);
789void addUnpredicatedMveVpredROp(MachineInstrBuilder &MIB, Register DestReg);

791void addPredicatedMveVpredNOp(MachineInstrBuilder &MIB, unsigned Cond);
792void addPredicatedMveVpredROp(MachineInstrBuilder &MIB, unsigned Cond,
                            unsigned Inactive);

795/// Returns the number of instructions required to materialize the given
796/// constant in a register, or 3 if a literal pool load is needed.
797/// If ForCodesize is specified, an approximate cost in bytes is returned.
798unsigned ConstantMaterializationCost(unsigned Val,
                                   const ARMSubtarget *Subtarget,
                                   bool ForCodesize = false);

802/// Returns true if Val1 has a lower Constant Materialization Cost than Val2.
803/// Uses the cost from ConstantMaterializationCost, first with ForCodesize as
804/// specified. If the scores are equal, return the comparison for !ForCodesize.
805bool HasLowerConstantMaterializationCost(unsigned Val1, unsigned Val2,
                                       const ARMSubtarget *Subtarget,
                                       bool ForCodesize = false);

809// Return the immediate if this is ADDri or SUBri, scaled as appropriate.
810// Returns 0 for unknown instructions.
811inline int getAddSubImmediate(MachineInstr &MI) {
int Scale = 1;
unsigned ImmOp;
switch (MI.getOpcode()) {
case ARM::t2ADDri:
  ImmOp = 2;
  break;
case ARM::t2SUBri:
case ARM::t2SUBri12:
  ImmOp = 2;
  Scale = -1;
  break;
case ARM::tSUBi3:
case ARM::tSUBi8:
  ImmOp = 3;
  Scale = -1;
  break;
default:
  return 0;
}
return Scale * MI.getOperand(ImmOp).getImm();
832}

834// Given a memory access Opcode, check that the give Imm would be a valid Offset
835// for this instruction using its addressing mode.
836inline bool isLegalAddressImm(unsigned Opcode, int Imm,
                            const TargetInstrInfo *TII) {
const MCInstrDesc &Desc = TII->get(Opcode);
unsigned AddrMode = (Desc.TSFlags & ARMII::AddrModeMask);
switch (AddrMode) {
case ARMII::AddrModeT2_i7:
  return std::abs(Imm) < (((1 << 7) * 1) - 1);
case ARMII::AddrModeT2_i7s2:
  return std::abs(Imm) < (((1 << 7) * 2) - 1) && Imm % 2 == 0;
case ARMII::AddrModeT2_i7s4:
  return std::abs(Imm) < (((1 << 7) * 4) - 1) && Imm % 4 == 0;
case ARMII::AddrModeT2_i8:
  return std::abs(Imm) < (((1 << 8) * 1) - 1);
case ARMII::AddrModeT2_i12:
  return Imm >= 0 && Imm < (((1 << 12) * 1) - 1);
default:
  llvm_unreachable("Unhandled Addressing mode")::llvm::llvm_unreachable_internal("Unhandled Addressing mode"
, "/build/llvm-toolchain-snapshot-12~++20200915100651+00ba1a3de7f/llvm/lib/Target/ARM/ARMBaseInstrInfo.h"
, 852);
}
854}

856// Return true if the given intrinsic is a gather
857inline bool isGather(IntrinsicInst *IntInst) {
if (IntInst == nullptr)
  return false;
unsigned IntrinsicID = IntInst->getIntrinsicID();
return (IntrinsicID == Intrinsic::masked_gather ||
        IntrinsicID == Intrinsic::arm_mve_vldr_gather_base ||
        IntrinsicID == Intrinsic::arm_mve_vldr_gather_base_predicated ||
        IntrinsicID == Intrinsic::arm_mve_vldr_gather_base_wb ||
        IntrinsicID == Intrinsic::arm_mve_vldr_gather_base_wb_predicated ||
        IntrinsicID == Intrinsic::arm_mve_vldr_gather_offset ||
        IntrinsicID == Intrinsic::arm_mve_vldr_gather_offset_predicated);
868}

870// Return true if the given intrinsic is a scatter
871inline bool isScatter(IntrinsicInst *IntInst) {
if (IntInst == nullptr)
  return false;
unsigned IntrinsicID = IntInst->getIntrinsicID();
return (IntrinsicID == Intrinsic::masked_scatter ||
        IntrinsicID == Intrinsic::arm_mve_vstr_scatter_base ||
        IntrinsicID == Intrinsic::arm_mve_vstr_scatter_base_predicated ||
        IntrinsicID == Intrinsic::arm_mve_vstr_scatter_base_wb ||
        IntrinsicID == Intrinsic::arm_mve_vstr_scatter_base_wb_predicated ||
        IntrinsicID == Intrinsic::arm_mve_vstr_scatter_offset ||
        IntrinsicID == Intrinsic::arm_mve_vstr_scatter_offset_predicated);
882}

884// Return true if the given intrinsic is a gather or scatter
885inline bool isGatherScatter(IntrinsicInst *IntInst) {
if (IntInst == nullptr)
  return false;
return isGather(IntInst) || isScatter(IntInst);
889}

891} // end namespace llvm

893#endif // LLVM_LIB_TARGET_ARM_ARMBASEINSTRINFO_H