1873 lines · 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-exception6//7//===----------------------------------------------------------------------===//8/// \file9/// Finalize v8.1-m low-overhead loops by converting the associated pseudo10/// 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-loop13/// form should be in the preheader, whereas the while form should be in the14/// 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-overhead20/// 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 range26/// but fixed polarity: WLS can only branch forwards and LE can only branch27/// backwards. These restrictions mean that this pass is dependent upon block28/// layout and block sizes, which is why it's the last pass to run. The same is29/// true for ConstantIslands, but this pass does not increase the size of the30/// basic blocks, nor does it change the CFG. Instructions are mainly removed31/// during the transform and pseudo instructions are replaced by real ones. In32/// some cases, when we have to revert to a 'normal' loop, we have to introduce33/// multiple instructions for a single pseudo (see RevertWhile and34/// RevertLoopEnd). To handle this situation, t2WhileLoopStartLR and t2LoopEnd35/// are defined to be as large as this maximum sequence of replacement36/// 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 a40/// "VPT Active" context (which includes low-overhead loops and vpt blocks).41/// They will simply "and" the result of their calculation with the current42/// value of VPR.P0. You can think of it like this:43/// \verbatim44/// if VPT active: ; Between a DLSTP/LETP, or for predicated instrs45/// VPR.P0 &= Value46/// else47/// VPR.P0 = Value48/// \endverbatim49/// When we're inside the low-overhead loop (between DLSTP and LETP), we always50/// fall in the "VPT active" case, so we can consider that all VPR writes by51/// one of those instruction is actually a "and".52//===----------------------------------------------------------------------===//53 54#include "ARM.h"55#include "ARMBaseInstrInfo.h"56#include "ARMBasicBlockInfo.h"57#include "ARMSubtarget.h"58#include "MVETailPredUtils.h"59#include "Thumb2InstrInfo.h"60#include "llvm/ADT/SetVector.h"61#include "llvm/CodeGen/LivePhysRegs.h"62#include "llvm/CodeGen/MachineFrameInfo.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"70 71using namespace llvm;72 73#define DEBUG_TYPE "arm-low-overhead-loops"74#define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"75 76static cl::opt<bool>77DisableTailPredication("arm-loloops-disable-tailpred", cl::Hidden,78 cl::desc("Disable tail-predication in the ARM LowOverheadLoop pass"),79 cl::init(false));80 81static cl::opt<bool>82 DisableOmitDLS("arm-disable-omit-dls", cl::Hidden,83 cl::desc("Disable omitting 'dls lr, lr' instructions"),84 cl::init(false));85 86static bool isVectorPredicated(MachineInstr *MI) {87 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);88 return PIdx != -1 && MI->getOperand(PIdx + 1).getReg() == ARM::VPR;89}90 91static bool isVectorPredicate(MachineInstr *MI) {92 return MI->findRegisterDefOperandIdx(ARM::VPR, /*TRI=*/nullptr) != -1;93}94 95static bool hasVPRUse(MachineInstr &MI) {96 return MI.findRegisterUseOperandIdx(ARM::VPR, /*TRI=*/nullptr) != -1;97}98 99static bool isDomainMVE(MachineInstr *MI) {100 uint64_t Domain = MI->getDesc().TSFlags & ARMII::DomainMask;101 return Domain == ARMII::DomainMVE;102}103 104static int getVecSize(const MachineInstr &MI) {105 const MCInstrDesc &MCID = MI.getDesc();106 uint64_t Flags = MCID.TSFlags;107 return (Flags & ARMII::VecSize) >> ARMII::VecSizeShift;108}109 110static bool shouldInspect(MachineInstr &MI) {111 if (MI.isDebugInstr())112 return false;113 return isDomainMVE(&MI) || isVectorPredicate(&MI) || hasVPRUse(MI);114}115 116static bool isHorizontalReduction(const MachineInstr &MI) {117 const MCInstrDesc &MCID = MI.getDesc();118 uint64_t Flags = MCID.TSFlags;119 return (Flags & ARMII::HorizontalReduction) != 0;120}121 122namespace {123 124 using InstSet = SmallPtrSetImpl<MachineInstr *>;125 126 class PostOrderLoopTraversal {127 MachineLoop &ML;128 MachineLoopInfo &MLI;129 SmallPtrSet<MachineBasicBlock*, 4> Visited;130 SmallVector<MachineBasicBlock*, 4> Order;131 132 public:133 PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)134 : ML(ML), MLI(MLI) { }135 136 const SmallVectorImpl<MachineBasicBlock*> &getOrder() const {137 return Order;138 }139 140 // Visit all the blocks within the loop, as well as exit blocks and any141 // blocks properly dominating the header.142 void ProcessLoop() {143 std::function<void(MachineBasicBlock *)> Search =144 [this, &Search](MachineBasicBlock *MBB) -> void {145 if (!Visited.insert(MBB).second)146 return;147 148 for (auto *Succ : MBB->successors()) {149 if (!ML.contains(Succ))150 continue;151 Search(Succ);152 }153 Order.push_back(MBB);154 };155 156 // Insert exit blocks.157 SmallVector<MachineBasicBlock*, 2> ExitBlocks;158 ML.getExitBlocks(ExitBlocks);159 append_range(Order, ExitBlocks);160 161 // Then add the loop body.162 Search(ML.getHeader());163 164 // Then try the preheader and its predecessors.165 std::function<void(MachineBasicBlock*)> GetPredecessor =166 [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void {167 Order.push_back(MBB);168 if (MBB->pred_size() == 1)169 GetPredecessor(*MBB->pred_begin());170 };171 172 if (auto *Preheader = ML.getLoopPreheader())173 GetPredecessor(Preheader);174 else if (auto *Preheader = MLI.findLoopPreheader(&ML, true, true))175 GetPredecessor(Preheader);176 }177 };178 179 class VPTBlock {180 SmallVector<MachineInstr *, 4> Insts;181 182 public:183 VPTBlock(MachineInstr *MI) { Insts.push_back(MI); }184 185 // Have we found an instruction within the block which defines the vpr? If186 // so, not all the instructions in the block will have the same predicate.187 bool hasUniformPredicate() { return getDivergent() == nullptr; }188 189 // If it exists, return the first internal instruction which modifies the190 // VPR.191 MachineInstr *getDivergent() {192 SmallVectorImpl<MachineInstr *> &Insts = getInsts();193 for (unsigned i = 1; i < Insts.size(); ++i) {194 MachineInstr *Next = Insts[i];195 if (isVectorPredicate(Next))196 return Next; // Found an instruction altering the vpr.197 }198 return nullptr;199 }200 201 void insert(MachineInstr *MI) {202 Insts.push_back(MI);203 // VPT/VPST + 4 predicated instructions.204 assert(Insts.size() <= 5 && "Too many instructions in VPT block!");205 }206 207 bool containsVCTP() const { return llvm::any_of(Insts, isVCTP); }208 209 unsigned size() const { return Insts.size(); }210 SmallVectorImpl<MachineInstr *> &getInsts() { return Insts; }211 };212 213 // Represent the current state of the VPR and hold all instances which214 // represent a VPT block, which is a list of instructions that begins with a215 // VPT/VPST and has a maximum of four proceeding instructions. All216 // instructions within the block are predicated upon the vpr and we allow217 // instructions to define the vpr within in the block too.218 class VPTState {219 friend struct LowOverheadLoop;220 221 SmallVector<VPTBlock, 4> Blocks;222 SetVector<MachineInstr *> CurrentPredicates;223 std::map<MachineInstr *, SetVector<MachineInstr *>> PredicatedInsts;224 225 void CreateVPTBlock(MachineInstr *MI) {226 assert((CurrentPredicates.size() || MI->getParent()->isLiveIn(ARM::VPR))227 && "Can't begin VPT without predicate");228 Blocks.emplace_back(MI);229 // The execution of MI is predicated upon the current set of instructions230 // that are AND'ed together to form the VPR predicate value. In the case231 // that MI is a VPT, CurrentPredicates will also just be MI.232 PredicatedInsts[MI] = CurrentPredicates;233 }234 235 void addInst(MachineInstr *MI) {236 Blocks.back().insert(MI);237 PredicatedInsts[MI] = CurrentPredicates;238 }239 240 void addPredicate(MachineInstr *MI) {241 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VPT Predicate: " << *MI);242 CurrentPredicates.insert(MI);243 }244 245 void resetPredicate(MachineInstr *MI) {246 LLVM_DEBUG(dbgs() << "ARM Loops: Resetting VPT Predicate: " << *MI);247 CurrentPredicates.clear();248 CurrentPredicates.insert(MI);249 }250 251 public:252 // Return whether the given instruction is predicated upon a VCTP.253 bool isPredicatedOnVCTP(MachineInstr *MI, bool Exclusive = false) {254 SetVector<MachineInstr *> &Predicates = PredicatedInsts[MI];255 if (Exclusive && Predicates.size() != 1)256 return false;257 // We do not know how to convert an else predicate of a VCTP.258 if (getVPTInstrPredicate(*MI) == ARMVCC::Else)259 return false;260 return llvm::any_of(Predicates, isVCTP);261 }262 263 // Is the VPST, controlling the block entry, predicated upon a VCTP.264 bool isEntryPredicatedOnVCTP(VPTBlock &Block, bool Exclusive = false) {265 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();266 return isPredicatedOnVCTP(Insts.front(), Exclusive);267 }268 269 // If this block begins with a VPT, we can check whether it's using270 // at least one predicated input(s), as well as possible loop invariant271 // which would result in it being implicitly predicated.272 bool hasImplicitlyValidVPT(VPTBlock &Block, ReachingDefInfo &RDI) {273 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();274 MachineInstr *VPT = Insts.front();275 assert(isVPTOpcode(VPT->getOpcode()) &&276 "Expected VPT block to begin with VPT/VPST");277 278 if (VPT->getOpcode() == ARM::MVE_VPST)279 return false;280 281 // If the VPT block does not define something that is an "output", then282 // the tail-predicated version will just perform a subset of the original283 // vpt block, where the last lanes should not be used.284 if (isVPTOpcode(VPT->getOpcode()) &&285 all_of(Block.getInsts(), [](const MachineInstr *MI) {286 return !MI->mayStore() && !MI->mayLoad() &&287 !isHorizontalReduction(*MI) && !isVCTP(MI);288 }))289 return true;290 291 auto IsOperandPredicated = [&](MachineInstr *MI, unsigned Idx) {292 MachineInstr *Op = RDI.getMIOperand(MI, MI->getOperand(Idx));293 return Op && PredicatedInsts.count(Op) && isPredicatedOnVCTP(Op);294 };295 296 auto IsOperandInvariant = [&](MachineInstr *MI, unsigned Idx) {297 MachineOperand &MO = MI->getOperand(Idx);298 if (!MO.isReg() || !MO.getReg())299 return true;300 301 SmallPtrSet<MachineInstr *, 2> Defs;302 RDI.getGlobalReachingDefs(MI, MO.getReg(), Defs);303 if (Defs.empty())304 return true;305 306 for (auto *Def : Defs)307 if (Def->getParent() == VPT->getParent())308 return false;309 return true;310 };311 312 // Check that at least one of the operands is directly predicated on a313 // vctp and allow an invariant value too.314 return (IsOperandPredicated(VPT, 1) || IsOperandPredicated(VPT, 2)) &&315 (IsOperandPredicated(VPT, 1) || IsOperandInvariant(VPT, 1)) &&316 (IsOperandPredicated(VPT, 2) || IsOperandInvariant(VPT, 2));317 }318 319 bool isValid(ReachingDefInfo &RDI) {320 // All predication within the loop should be based on vctp. If the block321 // isn't predicated on entry, check whether the vctp is within the block322 // and that all other instructions are then predicated on it.323 for (auto &Block : Blocks) {324 if (isEntryPredicatedOnVCTP(Block, false) &&325 !any_of(drop_begin(Block.getInsts()), [](const MachineInstr *MI) {326 return getVPTInstrPredicate(*MI) == ARMVCC::Else;327 }))328 continue;329 if (hasImplicitlyValidVPT(Block, RDI))330 continue;331 332 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();333 // We don't know how to convert a block with just a VPT;VCTP into334 // anything valid once we remove the VCTP. For now just bail out.335 assert(isVPTOpcode(Insts.front()->getOpcode()) &&336 "Expected VPT block to start with a VPST or VPT!");337 if (Insts.size() == 2 && Insts.front()->getOpcode() != ARM::MVE_VPST &&338 isVCTP(Insts.back()))339 return false;340 341 for (auto *MI : Insts) {342 // Check that any internal VCTPs are 'Then' predicated.343 if (isVCTP(MI) && getVPTInstrPredicate(*MI) != ARMVCC::Then)344 return false;345 // Skip other instructions that build up the predicate.346 if (MI->getOpcode() == ARM::MVE_VPST || isVectorPredicate(MI))347 continue;348 // Check that any other instructions are predicated upon a vctp.349 // TODO: We could infer when VPTs are implicitly predicated on the350 // vctp (when the operands are predicated).351 if (!isPredicatedOnVCTP(MI)) {352 LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *MI);353 return false;354 }355 }356 }357 return true;358 }359 };360 361 struct LowOverheadLoop {362 363 MachineLoop &ML;364 MachineBasicBlock *Preheader = nullptr;365 MachineLoopInfo &MLI;366 ReachingDefInfo &RDI;367 const TargetRegisterInfo &TRI;368 const ARMBaseInstrInfo &TII;369 MachineFunction *MF = nullptr;370 MachineBasicBlock::iterator StartInsertPt;371 MachineBasicBlock *StartInsertBB = nullptr;372 MachineInstr *Start = nullptr;373 MachineInstr *Dec = nullptr;374 MachineInstr *End = nullptr;375 MachineOperand TPNumElements;376 SmallVector<MachineInstr *, 4> VCTPs;377 SmallPtrSet<MachineInstr *, 4> ToRemove;378 SmallPtrSet<MachineInstr *, 4> BlockMasksToRecompute;379 SmallPtrSet<MachineInstr *, 4> DoubleWidthResultInstrs;380 SmallPtrSet<MachineInstr *, 4> VMOVCopies;381 bool Revert = false;382 bool CannotTailPredicate = false;383 VPTState VPTstate;384 385 LowOverheadLoop(MachineLoop &ML, MachineLoopInfo &MLI, ReachingDefInfo &RDI,386 const TargetRegisterInfo &TRI, const ARMBaseInstrInfo &TII)387 : ML(ML), MLI(MLI), RDI(RDI), TRI(TRI), TII(TII),388 TPNumElements(MachineOperand::CreateImm(0)) {389 MF = ML.getHeader()->getParent();390 if (auto *MBB = ML.getLoopPreheader())391 Preheader = MBB;392 else if (auto *MBB = MLI.findLoopPreheader(&ML, true, true))393 Preheader = MBB;394 }395 396 // If this is an MVE instruction, check that we know how to use tail397 // predication with it. Record VPT blocks and return whether the398 // instruction is valid for tail predication.399 bool ValidateMVEInst(MachineInstr *MI);400 401 void AnalyseMVEInst(MachineInstr *MI) {402 CannotTailPredicate = !ValidateMVEInst(MI);403 }404 405 bool IsTailPredicationLegal() const {406 // For now, let's keep things really simple and only support a single407 // block for tail predication.408 return !Revert && FoundAllComponents() && !VCTPs.empty() &&409 !CannotTailPredicate && ML.getNumBlocks() == 1;410 }411 412 // Given that MI is a VCTP, check that is equivalent to any other VCTPs413 // found.414 bool AddVCTP(MachineInstr *MI);415 416 // Check that the predication in the loop will be equivalent once we417 // perform the conversion. Also ensure that we can provide the number418 // of elements to the loop start instruction.419 bool ValidateTailPredicate();420 421 // Check that any values available outside of the loop will be the same422 // after tail predication conversion.423 bool ValidateLiveOuts();424 425 // Check the branch targets are within range and we satisfy our426 // restrictions.427 void Validate(ARMBasicBlockUtils *BBUtils);428 429 bool FoundAllComponents() const {430 return Start && Dec && End;431 }432 433 SmallVectorImpl<VPTBlock> &getVPTBlocks() { return VPTstate.Blocks; }434 435 // Return the operand for the loop start instruction. This will be the loop436 // iteration count, or the number of elements if we're tail predicating.437 MachineOperand &getLoopStartOperand() {438 if (IsTailPredicationLegal())439 return TPNumElements;440 return Start->getOperand(1);441 }442 443 unsigned getStartOpcode() const {444 bool IsDo = isDoLoopStart(*Start);445 if (!IsTailPredicationLegal())446 return IsDo ? ARM::t2DLS : ARM::t2WLS;447 448 return VCTPOpcodeToLSTP(VCTPs.back()->getOpcode(), IsDo);449 }450 451 void dump() const {452 if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;453 if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;454 if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;455 if (!VCTPs.empty()) {456 dbgs() << "ARM Loops: Found VCTP(s):\n";457 for (auto *MI : VCTPs)458 dbgs() << " - " << *MI;459 }460 if (!FoundAllComponents())461 dbgs() << "ARM Loops: Not a low-overhead loop.\n";462 else if (!(Start && Dec && End))463 dbgs() << "ARM Loops: Failed to find all loop components.\n";464 }465 };466 467 class ARMLowOverheadLoops : public MachineFunctionPass {468 MachineFunction *MF = nullptr;469 MachineLoopInfo *MLI = nullptr;470 ReachingDefInfo *RDI = nullptr;471 const ARMBaseInstrInfo *TII = nullptr;472 MachineRegisterInfo *MRI = nullptr;473 const TargetRegisterInfo *TRI = nullptr;474 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;475 476 public:477 static char ID;478 479 ARMLowOverheadLoops() : MachineFunctionPass(ID) { }480 481 void getAnalysisUsage(AnalysisUsage &AU) const override {482 AU.setPreservesCFG();483 AU.addRequired<MachineLoopInfoWrapperPass>();484 AU.addRequired<ReachingDefInfoWrapperPass>();485 MachineFunctionPass::getAnalysisUsage(AU);486 }487 488 bool runOnMachineFunction(MachineFunction &MF) override;489 490 MachineFunctionProperties getRequiredProperties() const override {491 return MachineFunctionProperties().setNoVRegs().setTracksLiveness();492 }493 494 StringRef getPassName() const override {495 return ARM_LOW_OVERHEAD_LOOPS_NAME;496 }497 498 private:499 bool ProcessLoop(MachineLoop *ML);500 501 bool RevertNonLoops();502 503 void RevertWhile(MachineInstr *MI) const;504 void RevertDo(MachineInstr *MI) const;505 506 bool RevertLoopDec(MachineInstr *MI) const;507 508 void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;509 510 void RevertLoopEndDec(MachineInstr *MI) const;511 512 void ConvertVPTBlocks(LowOverheadLoop &LoLoop);513 514 MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);515 516 void Expand(LowOverheadLoop &LoLoop);517 518 void IterationCountDCE(LowOverheadLoop &LoLoop);519 };520}521 522char ARMLowOverheadLoops::ID = 0;523 524INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,525 false, false)526 527static bool TryRemove(MachineInstr *MI, ReachingDefInfo &RDI, InstSet &ToRemove,528 InstSet &Ignore) {529 530 // Check that we can remove all of Killed without having to modify any IT531 // blocks.532 auto WontCorruptITs = [](InstSet &Killed, ReachingDefInfo &RDI) {533 // Collect the dead code and the MBBs in which they reside.534 SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks;535 for (auto *Dead : Killed)536 BasicBlocks.insert(Dead->getParent());537 538 // Collect IT blocks in all affected basic blocks.539 std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;540 for (auto *MBB : BasicBlocks) {541 for (auto &IT : *MBB) {542 if (IT.getOpcode() != ARM::t2IT)543 continue;544 RDI.getReachingLocalUses(&IT, MCRegister::from(ARM::ITSTATE),545 ITBlocks[&IT]);546 }547 }548 549 // If we're removing all of the instructions within an IT block, then550 // also remove the IT instruction.551 SmallPtrSet<MachineInstr *, 2> ModifiedITs;552 SmallPtrSet<MachineInstr *, 2> RemoveITs;553 for (auto *Dead : Killed) {554 if (MachineOperand *MO =555 Dead->findRegisterUseOperand(ARM::ITSTATE, /*TRI=*/nullptr)) {556 MachineInstr *IT = RDI.getMIOperand(Dead, *MO);557 RemoveITs.insert(IT);558 auto &CurrentBlock = ITBlocks[IT];559 CurrentBlock.erase(Dead);560 if (CurrentBlock.empty())561 ModifiedITs.erase(IT);562 else563 ModifiedITs.insert(IT);564 }565 }566 if (!ModifiedITs.empty())567 return false;568 Killed.insert_range(RemoveITs);569 return true;570 };571 572 SmallPtrSet<MachineInstr *, 2> Uses;573 if (!RDI.isSafeToRemove(MI, Uses, Ignore))574 return false;575 576 if (WontCorruptITs(Uses, RDI)) {577 ToRemove.insert_range(Uses);578 LLVM_DEBUG(dbgs() << "ARM Loops: Able to remove: " << *MI579 << " - can also remove:\n";580 for (auto *Use : Uses)581 dbgs() << " - " << *Use);582 583 SmallPtrSet<MachineInstr*, 4> Killed;584 RDI.collectKilledOperands(MI, Killed);585 if (WontCorruptITs(Killed, RDI)) {586 ToRemove.insert_range(Killed);587 LLVM_DEBUG(for (auto *Dead : Killed)588 dbgs() << " - " << *Dead);589 }590 return true;591 }592 return false;593}594 595bool LowOverheadLoop::ValidateTailPredicate() {596 if (!IsTailPredicationLegal()) {597 LLVM_DEBUG(if (VCTPs.empty())598 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";599 dbgs() << "ARM Loops: Tail-predication is not valid.\n");600 return false;601 }602 603 assert(!VCTPs.empty() && "VCTP instruction expected but is not set");604 assert(ML.getBlocks().size() == 1 &&605 "Shouldn't be processing a loop with more than one block");606 607 if (DisableTailPredication) {608 LLVM_DEBUG(dbgs() << "ARM Loops: tail-predication is disabled\n");609 return false;610 }611 612 if (!VPTstate.isValid(RDI)) {613 LLVM_DEBUG(dbgs() << "ARM Loops: Invalid VPT state.\n");614 return false;615 }616 617 if (!ValidateLiveOuts()) {618 LLVM_DEBUG(dbgs() << "ARM Loops: Invalid live outs.\n");619 return false;620 }621 622 // For tail predication, we need to provide the number of elements, instead623 // of the iteration count, to the loop start instruction. The number of624 // elements is provided to the vctp instruction, so we need to check that625 // we can use this register at InsertPt.626 MachineInstr *VCTP = VCTPs.back();627 if (Start->getOpcode() == ARM::t2DoLoopStartTP ||628 Start->getOpcode() == ARM::t2WhileLoopStartTP) {629 TPNumElements = Start->getOperand(2);630 StartInsertPt = Start;631 StartInsertBB = Start->getParent();632 } else {633 TPNumElements = VCTP->getOperand(1);634 MCRegister NumElements = TPNumElements.getReg().asMCReg();635 636 // If the register is defined within loop, then we can't perform TP.637 // TODO: Check whether this is just a mov of a register that would be638 // available.639 if (RDI.hasLocalDefBefore(VCTP, NumElements)) {640 LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");641 return false;642 }643 644 // The element count register maybe defined after InsertPt, in which case we645 // need to try to move either InsertPt or the def so that the [w|d]lstp can646 // use the value.647 648 if (StartInsertPt != StartInsertBB->end() &&649 !RDI.isReachingDefLiveOut(&*StartInsertPt, NumElements)) {650 if (auto *ElemDef =651 RDI.getLocalLiveOutMIDef(StartInsertBB, NumElements)) {652 if (RDI.isSafeToMoveForwards(ElemDef, &*StartInsertPt)) {653 ElemDef->removeFromParent();654 StartInsertBB->insert(StartInsertPt, ElemDef);655 LLVM_DEBUG(dbgs()656 << "ARM Loops: Moved element count def: " << *ElemDef);657 } else if (RDI.isSafeToMoveBackwards(&*StartInsertPt, ElemDef)) {658 StartInsertPt->removeFromParent();659 StartInsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef),660 &*StartInsertPt);661 LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);662 } else {663 // If we fail to move an instruction and the element count is provided664 // by a mov, use the mov operand if it will have the same value at the665 // insertion point666 MachineOperand Operand = ElemDef->getOperand(1);667 if (isMovRegOpcode(ElemDef->getOpcode()) &&668 RDI.getUniqueReachingMIDef(ElemDef, Operand.getReg().asMCReg()) ==669 RDI.getUniqueReachingMIDef(&*StartInsertPt,670 Operand.getReg().asMCReg())) {671 TPNumElements = Operand;672 NumElements = TPNumElements.getReg();673 } else {674 LLVM_DEBUG(dbgs()675 << "ARM Loops: Unable to move element count to loop "676 << "start instruction.\n");677 return false;678 }679 }680 }681 }682 683 // Especially in the case of while loops, InsertBB may not be the684 // preheader, so we need to check that the register isn't redefined685 // before entering the loop.686 auto CannotProvideElements = [this](MachineBasicBlock *MBB,687 MCRegister NumElements) {688 if (MBB->empty())689 return false;690 // NumElements is redefined in this block.691 if (RDI.hasLocalDefBefore(&MBB->back(), NumElements))692 return true;693 694 // Don't continue searching up through multiple predecessors.695 if (MBB->pred_size() > 1)696 return true;697 698 return false;699 };700 701 // Search backwards for a def, until we get to InsertBB.702 MachineBasicBlock *MBB = Preheader;703 while (MBB && MBB != StartInsertBB) {704 if (CannotProvideElements(MBB, NumElements)) {705 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");706 return false;707 }708 MBB = *MBB->pred_begin();709 }710 }711 712 // Could inserting the [W|D]LSTP cause some unintended affects? In a perfect713 // world the [w|d]lstp instruction would be last instruction in the preheader714 // and so it would only affect instructions within the loop body. But due to715 // scheduling, and/or the logic in this pass (above), the insertion point can716 // be moved earlier. So if the Loop Start isn't the last instruction in the717 // preheader, and if the initial element count is smaller than the vector718 // width, the Loop Start instruction will immediately generate one or more719 // false lane mask which can, incorrectly, affect the proceeding MVE720 // instructions in the preheader.721 if (std::any_of(StartInsertPt, StartInsertBB->end(), shouldInspect)) {722 LLVM_DEBUG(dbgs() << "ARM Loops: Instruction blocks [W|D]LSTP\n");723 return false;724 }725 726 // For any DoubleWidthResultInstrs we found whilst scanning instructions, they727 // need to compute an output size that is smaller than the VCTP mask operates728 // on. The VecSize of the DoubleWidthResult is the larger vector size - the729 // size it extends into, so any VCTP VecSize <= is valid.730 unsigned VCTPVecSize = getVecSize(*VCTP);731 for (MachineInstr *MI : DoubleWidthResultInstrs) {732 unsigned InstrVecSize = getVecSize(*MI);733 if (InstrVecSize > VCTPVecSize) {734 LLVM_DEBUG(dbgs() << "ARM Loops: Double width result larger than VCTP "735 << "VecSize:\n" << *MI);736 return false;737 }738 }739 740 // Check that the value change of the element count is what we expect and741 // that the predication will be equivalent. For this we need:742 // NumElements = NumElements - VectorWidth. The sub will be a sub immediate743 // and we can also allow register copies within the chain too.744 auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) {745 return -getAddSubImmediate(*MI) == ExpectedVecWidth;746 };747 748 MachineBasicBlock *MBB = VCTP->getParent();749 // Remove modifications to the element count since they have no purpose in a750 // tail predicated loop. Explicitly refer to the vctp operand no matter which751 // register NumElements has been assigned to, since that is what the752 // modifications will be using753 if (auto *Def = RDI.getUniqueReachingMIDef(754 &MBB->back(), VCTP->getOperand(1).getReg().asMCReg())) {755 SmallPtrSet<MachineInstr*, 2> ElementChain;756 SmallPtrSet<MachineInstr*, 2> Ignore;757 unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());758 759 Ignore.insert_range(VCTPs);760 761 if (TryRemove(Def, RDI, ElementChain, Ignore)) {762 bool FoundSub = false;763 764 for (auto *MI : ElementChain) {765 if (isMovRegOpcode(MI->getOpcode()))766 continue;767 768 if (isSubImmOpcode(MI->getOpcode())) {769 if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth)) {770 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"771 " count: " << *MI);772 return false;773 }774 FoundSub = true;775 } else {776 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"777 " count: " << *MI);778 return false;779 }780 }781 ToRemove.insert_range(ElementChain);782 }783 }784 785 // If we converted the LoopStart to a t2DoLoopStartTP/t2WhileLoopStartTP, we786 // can also remove any extra instructions in the preheader, which often787 // includes a now unused MOV.788 if ((Start->getOpcode() == ARM::t2DoLoopStartTP ||789 Start->getOpcode() == ARM::t2WhileLoopStartTP) &&790 Preheader && !Preheader->empty() &&791 !RDI.hasLocalDefBefore(VCTP, VCTP->getOperand(1).getReg())) {792 if (auto *Def = RDI.getUniqueReachingMIDef(793 &Preheader->back(), VCTP->getOperand(1).getReg().asMCReg())) {794 SmallPtrSet<MachineInstr *, 2> Ignore(llvm::from_range, VCTPs);795 TryRemove(Def, RDI, ToRemove, Ignore);796 }797 }798 799 return true;800}801 802static bool isRegInClass(const MachineOperand &MO,803 const TargetRegisterClass *Class) {804 return MO.isReg() && MO.getReg() && Class->contains(MO.getReg());805}806 807// MVE 'narrowing' operate on half a lane, reading from half and writing808// to half, which are referred to has the top and bottom half. The other809// half retains its previous value.810static bool retainsPreviousHalfElement(const MachineInstr &MI) {811 const MCInstrDesc &MCID = MI.getDesc();812 uint64_t Flags = MCID.TSFlags;813 return (Flags & ARMII::RetainsPreviousHalfElement) != 0;814}815 816// Some MVE instructions read from the top/bottom halves of their operand(s)817// and generate a vector result with result elements that are double the818// width of the input.819static bool producesDoubleWidthResult(const MachineInstr &MI) {820 const MCInstrDesc &MCID = MI.getDesc();821 uint64_t Flags = MCID.TSFlags;822 return (Flags & ARMII::DoubleWidthResult) != 0;823}824 825// Can this instruction generate a non-zero result when given only zeroed826// operands? This allows us to know that, given operands with false bytes827// zeroed by masked loads, that the result will also contain zeros in those828// bytes.829static bool canGenerateNonZeros(const MachineInstr &MI) {830 831 // Check for instructions which can write into a larger element size,832 // possibly writing into a previous zero'd lane.833 if (producesDoubleWidthResult(MI))834 return true;835 836 switch (MI.getOpcode()) {837 default:838 break;839 // FIXME: VNEG FP and -0? I think we'll need to handle this once we allow840 // fp16 -> fp32 vector conversions.841 // Instructions that perform a NOT will generate 1s from 0s.842 case ARM::MVE_VMVN:843 case ARM::MVE_VORN:844 // Count leading zeros will do just that!845 case ARM::MVE_VCLZs8:846 case ARM::MVE_VCLZs16:847 case ARM::MVE_VCLZs32:848 return true;849 }850 return false;851}852 853// Look at its register uses to see if it only can only receive zeros854// into its false lanes which would then produce zeros. Also check that855// the output register is also defined by an FalseLanesZero instruction856// so that if tail-predication happens, the lanes that aren't updated will857// still be zeros.858static bool producesFalseLanesZero(MachineInstr &MI,859 const TargetRegisterClass *QPRs,860 const ReachingDefInfo &RDI,861 InstSet &FalseLanesZero) {862 if (canGenerateNonZeros(MI))863 return false;864 865 bool isPredicated = isVectorPredicated(&MI);866 // Predicated loads will write zeros to the falsely predicated bytes of the867 // destination register.868 if (MI.mayLoad())869 return isPredicated;870 871 auto IsZeroInit = [](MachineInstr *Def) {872 return !isVectorPredicated(Def) &&873 Def->getOpcode() == ARM::MVE_VMOVimmi32 &&874 Def->getOperand(1).getImm() == 0;875 };876 877 bool AllowScalars = isHorizontalReduction(MI);878 for (auto &MO : MI.operands()) {879 if (!MO.isReg() || !MO.getReg())880 continue;881 if (!isRegInClass(MO, QPRs) && AllowScalars)882 continue;883 // Skip the lr predicate reg884 int PIdx = llvm::findFirstVPTPredOperandIdx(MI);885 if (PIdx != -1 && MO.getOperandNo() == PIdx + ARM::SUBOP_vpred_n_tp_reg)886 continue;887 888 // Check that this instruction will produce zeros in its false lanes:889 // - If it only consumes false lanes zero or constant 0 (vmov #0)890 // - If it's predicated, it only matters that it's def register already has891 // false lane zeros, so we can ignore the uses.892 SmallPtrSet<MachineInstr *, 2> Defs;893 RDI.getGlobalReachingDefs(&MI, MO.getReg(), Defs);894 if (Defs.empty())895 return false;896 for (auto *Def : Defs) {897 if (Def == &MI || FalseLanesZero.count(Def) || IsZeroInit(Def))898 continue;899 if (MO.isUse() && isPredicated)900 continue;901 return false;902 }903 }904 LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI);905 return true;906}907 908bool LowOverheadLoop::ValidateLiveOuts() {909 // We want to find out if the tail-predicated version of this loop will910 // produce the same values as the loop in its original form. For this to911 // be true, the newly inserted implicit predication must not change the912 // the (observable) results.913 // We're doing this because many instructions in the loop will not be914 // predicated and so the conversion from VPT predication to tail-predication915 // can result in different values being produced; due to the tail-predication916 // preventing many instructions from updating their falsely predicated917 // lanes. This analysis assumes that all the instructions perform lane-wise918 // operations and don't perform any exchanges.919 // A masked load, whether through VPT or tail predication, will write zeros920 // to any of the falsely predicated bytes. So, from the loads, we know that921 // the false lanes are zeroed and here we're trying to track that those false922 // lanes remain zero, or where they change, the differences are masked away923 // by their user(s).924 // All MVE stores have to be predicated, so we know that any predicate load925 // operands, or stored results are equivalent already. Other explicitly926 // predicated instructions will perform the same operation in the original927 // loop and the tail-predicated form too. Because of this, we can insert928 // loads, stores and other predicated instructions into our Predicated929 // set and build from there.930 const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID);931 SetVector<MachineInstr *> FalseLanesUnknown;932 SmallPtrSet<MachineInstr *, 4> FalseLanesZero;933 SmallPtrSet<MachineInstr *, 4> Predicated;934 MachineBasicBlock *Header = ML.getHeader();935 936 LLVM_DEBUG(dbgs() << "ARM Loops: Validating Live outs\n");937 938 for (auto &MI : *Header) {939 if (!shouldInspect(MI))940 continue;941 942 if (isVCTP(&MI) || isVPTOpcode(MI.getOpcode()))943 continue;944 945 bool isPredicated = isVectorPredicated(&MI);946 bool retainsOrReduces =947 retainsPreviousHalfElement(MI) || isHorizontalReduction(MI);948 949 if (isPredicated)950 Predicated.insert(&MI);951 if (producesFalseLanesZero(MI, QPRs, RDI, FalseLanesZero))952 FalseLanesZero.insert(&MI);953 else if (MI.getNumDefs() == 0)954 continue;955 else if (!isPredicated && retainsOrReduces) {956 LLVM_DEBUG(dbgs() << " Unpredicated instruction that retainsOrReduces: " << MI);957 return false;958 } else if (!isPredicated && MI.getOpcode() != ARM::MQPRCopy)959 FalseLanesUnknown.insert(&MI);960 }961 962 LLVM_DEBUG({963 dbgs() << " Predicated:\n";964 for (auto *I : Predicated)965 dbgs() << " " << *I;966 dbgs() << " FalseLanesZero:\n";967 for (auto *I : FalseLanesZero)968 dbgs() << " " << *I;969 dbgs() << " FalseLanesUnknown:\n";970 for (auto *I : FalseLanesUnknown)971 dbgs() << " " << *I;972 });973 974 auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,975 SmallPtrSetImpl<MachineInstr *> &Predicated) {976 SmallPtrSet<MachineInstr *, 2> Uses;977 RDI.getGlobalUses(MI, MO.getReg().asMCReg(), Uses);978 for (auto *Use : Uses) {979 if (Use != MI && !Predicated.count(Use))980 return false;981 }982 return true;983 };984 985 // Visit the unknowns in reverse so that we can start at the values being986 // stored and then we can work towards the leaves, hopefully adding more987 // instructions to Predicated. Successfully terminating the loop means that988 // all the unknown values have to found to be masked by predicated user(s).989 // For any unpredicated values, we store them in NonPredicated so that we990 // can later check whether these form a reduction.991 SmallPtrSet<MachineInstr*, 2> NonPredicated;992 for (auto *MI : reverse(FalseLanesUnknown)) {993 for (auto &MO : MI->operands()) {994 if (!isRegInClass(MO, QPRs) || !MO.isDef())995 continue;996 if (!HasPredicatedUsers(MI, MO, Predicated)) {997 LLVM_DEBUG(dbgs() << " Found an unknown def of : "998 << TRI.getRegAsmName(MO.getReg()) << " at " << *MI);999 NonPredicated.insert(MI);1000 break;1001 }1002 }1003 // Any unknown false lanes have been masked away by the user(s).1004 if (!NonPredicated.contains(MI))1005 Predicated.insert(MI);1006 }1007 1008 SmallPtrSet<MachineInstr *, 2> LiveOutMIs;1009 SmallVector<MachineBasicBlock *, 2> ExitBlocks;1010 ML.getExitBlocks(ExitBlocks);1011 assert(ML.getNumBlocks() == 1 && "Expected single block loop!");1012 assert(ExitBlocks.size() == 1 && "Expected a single exit block");1013 MachineBasicBlock *ExitBB = ExitBlocks.front();1014 for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) {1015 // TODO: Instead of blocking predication, we could move the vctp to the exit1016 // block and calculate it's operand there in or the preheader.1017 if (RegMask.PhysReg == ARM::VPR) {1018 LLVM_DEBUG(dbgs() << " VPR is live in to the exit block.");1019 return false;1020 }1021 // Check Q-regs that are live in the exit blocks. We don't collect scalars1022 // because they won't be affected by lane predication.1023 if (QPRs->contains(RegMask.PhysReg))1024 if (auto *MI = RDI.getLocalLiveOutMIDef(Header, RegMask.PhysReg))1025 LiveOutMIs.insert(MI);1026 }1027 1028 // We've already validated that any VPT predication within the loop will be1029 // equivalent when we perform the predication transformation; so we know that1030 // any VPT predicated instruction is predicated upon VCTP. Any live-out1031 // instruction needs to be predicated, so check this here. The instructions1032 // in NonPredicated have been found to be a reduction that we can ensure its1033 // legality. Any MQPRCopy found will need to validate its input as if it was1034 // live out.1035 SmallVector<MachineInstr *> Worklist(LiveOutMIs.begin(), LiveOutMIs.end());1036 while (!Worklist.empty()) {1037 MachineInstr *MI = Worklist.pop_back_val();1038 if (MI->getOpcode() == ARM::MQPRCopy) {1039 LLVM_DEBUG(dbgs() << " Must generate copy as VMOV: " << *MI);1040 VMOVCopies.insert(MI);1041 MachineInstr *CopySrc =1042 RDI.getUniqueReachingMIDef(MI, MI->getOperand(1).getReg());1043 if (CopySrc)1044 Worklist.push_back(CopySrc);1045 } else if (NonPredicated.count(MI) && FalseLanesUnknown.contains(MI)) {1046 LLVM_DEBUG(dbgs() << " Unable to handle live out: " << *MI);1047 VMOVCopies.clear();1048 return false;1049 } else if (isVectorPredicated(MI)) {1050 // If this is a predicated instruction with merging semantics,1051 // check where it gets its false lanes from, if any.1052 int InactiveIdx = findVPTInactiveOperandIdx(*MI);1053 if (InactiveIdx != -1) {1054 MachineInstr *FalseSrc = RDI.getUniqueReachingMIDef(1055 MI, MI->getOperand(InactiveIdx).getReg());1056 if (FalseSrc) {1057 LLVM_DEBUG(dbgs()1058 << " Must check source of false lanes for: " << *MI);1059 Worklist.push_back(FalseSrc);1060 }1061 }1062 }1063 }1064 1065 return true;1066}1067 1068void LowOverheadLoop::Validate(ARMBasicBlockUtils *BBUtils) {1069 if (Revert)1070 return;1071 1072 // Check branch target ranges: WLS[TP] can only branch forwards and LE[TP]1073 // can only jump back.1074 auto ValidateRanges = [](MachineInstr *Start, MachineInstr *End,1075 ARMBasicBlockUtils *BBUtils, MachineLoop &ML) {1076 MachineBasicBlock *TgtBB = End->getOpcode() == ARM::t2LoopEnd1077 ? End->getOperand(1).getMBB()1078 : End->getOperand(2).getMBB();1079 // TODO Maybe there's cases where the target doesn't have to be the header,1080 // but for now be safe and revert.1081 if (TgtBB != ML.getHeader()) {1082 LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targeting header.\n");1083 return false;1084 }1085 1086 // The WLS and LE instructions have 12-bits for the label offset. WLS1087 // requires a positive offset, while LE uses negative.1088 if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML.getHeader()) ||1089 !BBUtils->isBBInRange(End, ML.getHeader(), 4094)) {1090 LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");1091 return false;1092 }1093 1094 if (isWhileLoopStart(*Start)) {1095 MachineBasicBlock *TargetBB = getWhileLoopStartTargetBB(*Start);1096 if (BBUtils->getOffsetOf(Start) > BBUtils->getOffsetOf(TargetBB) ||1097 !BBUtils->isBBInRange(Start, TargetBB, 4094)) {1098 LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");1099 return false;1100 }1101 }1102 return true;1103 };1104 1105 StartInsertPt = MachineBasicBlock::iterator(Start);1106 StartInsertBB = Start->getParent();1107 LLVM_DEBUG(dbgs() << "ARM Loops: Will insert LoopStart at "1108 << *StartInsertPt);1109 1110 Revert = !ValidateRanges(Start, End, BBUtils, ML);1111 CannotTailPredicate = !ValidateTailPredicate();1112}1113 1114bool LowOverheadLoop::AddVCTP(MachineInstr *MI) {1115 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VCTP: " << *MI);1116 if (VCTPs.empty()) {1117 VCTPs.push_back(MI);1118 return true;1119 }1120 1121 // If we find another VCTP, check whether it uses the same value as the main VCTP.1122 // If it does, store it in the VCTPs set, else refuse it.1123 MachineInstr *Prev = VCTPs.back();1124 if (!Prev->getOperand(1).isIdenticalTo(MI->getOperand(1)) ||1125 !RDI.hasSameReachingDef(Prev, MI, MI->getOperand(1).getReg().asMCReg())) {1126 LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching "1127 "definition from the main VCTP");1128 return false;1129 }1130 VCTPs.push_back(MI);1131 return true;1132}1133 1134static bool ValidateMVEStore(MachineInstr *MI, MachineLoop *ML) {1135 1136 auto GetFrameIndex = [](MachineMemOperand *Operand) {1137 const PseudoSourceValue *PseudoValue = Operand->getPseudoValue();1138 if (PseudoValue && PseudoValue->kind() == PseudoSourceValue::FixedStack) {1139 if (const auto *FS = dyn_cast<FixedStackPseudoSourceValue>(PseudoValue)) {1140 return FS->getFrameIndex();1141 }1142 }1143 return -1;1144 };1145 1146 auto IsStackOp = [GetFrameIndex](MachineInstr *I) {1147 switch (I->getOpcode()) {1148 case ARM::MVE_VSTRWU32:1149 case ARM::MVE_VLDRWU32: {1150 return I->getOperand(1).getReg() == ARM::SP &&1151 I->memoperands().size() == 1 &&1152 GetFrameIndex(I->memoperands().front()) >= 0;1153 }1154 default:1155 return false;1156 }1157 };1158 1159 // An unpredicated vector register spill is allowed if all of the uses of the1160 // stack slot are within the loop1161 if (MI->getOpcode() != ARM::MVE_VSTRWU32 || !IsStackOp(MI))1162 return false;1163 1164 // Search all blocks after the loop for accesses to the same stack slot.1165 // ReachingDefAnalysis doesn't work for sp as it relies on registers being1166 // live-out (which sp never is) to know what blocks to look in1167 if (MI->memoperands().size() == 0)1168 return false;1169 int FI = GetFrameIndex(MI->memoperands().front());1170 1171 auto &FrameInfo = MI->getParent()->getParent()->getFrameInfo();1172 if (FI == -1 || !FrameInfo.isSpillSlotObjectIndex(FI))1173 return false;1174 1175 SmallVector<MachineBasicBlock *> Frontier;1176 ML->getExitBlocks(Frontier);1177 SmallPtrSet<MachineBasicBlock *, 4> Visited{MI->getParent()};1178 unsigned Idx = 0;1179 while (Idx < Frontier.size()) {1180 MachineBasicBlock *BB = Frontier[Idx];1181 bool LookAtSuccessors = true;1182 for (auto &I : *BB) {1183 if (!IsStackOp(&I) || I.memoperands().size() == 0)1184 continue;1185 if (GetFrameIndex(I.memoperands().front()) != FI)1186 continue;1187 // If this block has a store to the stack slot before any loads then we1188 // can ignore the block1189 if (I.getOpcode() == ARM::MVE_VSTRWU32) {1190 LookAtSuccessors = false;1191 break;1192 }1193 // If the store and the load are using the same stack slot then the1194 // store isn't valid for tail predication1195 if (I.getOpcode() == ARM::MVE_VLDRWU32)1196 return false;1197 }1198 1199 if (LookAtSuccessors) {1200 for (auto *Succ : BB->successors()) {1201 if (!Visited.contains(Succ) && !is_contained(Frontier, Succ))1202 Frontier.push_back(Succ);1203 }1204 }1205 Visited.insert(BB);1206 Idx++;1207 }1208 1209 return true;1210}1211 1212bool LowOverheadLoop::ValidateMVEInst(MachineInstr *MI) {1213 if (CannotTailPredicate)1214 return false;1215 1216 if (!shouldInspect(*MI))1217 return true;1218 1219 if (MI->getOpcode() == ARM::MVE_VPSEL ||1220 MI->getOpcode() == ARM::MVE_VPNOT) {1221 // TODO: Allow VPSEL and VPNOT, we currently cannot because:1222 // 1) It will use the VPR as a predicate operand, but doesn't have to be1223 // instead a VPT block, which means we can assert while building up1224 // the VPT block because we don't find another VPT or VPST to being a new1225 // one.1226 // 2) VPSEL still requires a VPR operand even after tail predicating,1227 // which means we can't remove it unless there is another1228 // instruction, such as vcmp, that can provide the VPR def.1229 return false;1230 }1231 1232 // Record all VCTPs and check that they're equivalent to one another.1233 if (isVCTP(MI) && !AddVCTP(MI))1234 return false;1235 1236 // Inspect uses first so that any instructions that alter the VPR don't1237 // alter the predicate upon themselves.1238 const MCInstrDesc &MCID = MI->getDesc();1239 bool IsUse = false;1240 unsigned LastOpIdx = MI->getNumOperands() - 1;1241 for (const auto &Op : enumerate(reverse(MCID.operands()))) {1242 const MachineOperand &MO = MI->getOperand(LastOpIdx - Op.index());1243 if (!MO.isReg() || !MO.isUse() || MO.getReg() != ARM::VPR)1244 continue;1245 1246 if (ARM::isVpred(Op.value().OperandType)) {1247 VPTstate.addInst(MI);1248 IsUse = true;1249 } else if (MI->getOpcode() != ARM::MVE_VPST) {1250 LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);1251 return false;1252 }1253 }1254 1255 // If we find an instruction that has been marked as not valid for tail1256 // predication, only allow the instruction if it's contained within a valid1257 // VPT block.1258 bool RequiresExplicitPredication =1259 (MCID.TSFlags & ARMII::ValidForTailPredication) == 0;1260 if (isDomainMVE(MI) && RequiresExplicitPredication) {1261 if (MI->getOpcode() == ARM::MQPRCopy)1262 return true;1263 if (!IsUse && producesDoubleWidthResult(*MI)) {1264 DoubleWidthResultInstrs.insert(MI);1265 return true;1266 }1267 1268 LLVM_DEBUG(if (!IsUse) dbgs()1269 << "ARM Loops: Can't tail predicate: " << *MI);1270 return IsUse;1271 }1272 1273 // If the instruction is already explicitly predicated, then the conversion1274 // will be fine, but ensure that all store operations are predicated.1275 if (MI->mayStore() && !ValidateMVEStore(MI, &ML))1276 return IsUse;1277 1278 // If this instruction defines the VPR, update the predicate for the1279 // proceeding instructions.1280 if (isVectorPredicate(MI)) {1281 // Clear the existing predicate when we're not in VPT Active state,1282 // otherwise we add to it.1283 if (!isVectorPredicated(MI))1284 VPTstate.resetPredicate(MI);1285 else1286 VPTstate.addPredicate(MI);1287 }1288 1289 // Finally once the predicate has been modified, we can start a new VPT1290 // block if necessary.1291 if (isVPTOpcode(MI->getOpcode()))1292 VPTstate.CreateVPTBlock(MI);1293 1294 return true;1295}1296 1297bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {1298 const ARMSubtarget &ST = mf.getSubtarget<ARMSubtarget>();1299 if (!ST.hasLOB())1300 return false;1301 1302 MF = &mf;1303 LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");1304 1305 MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();1306 RDI = &getAnalysis<ReachingDefInfoWrapperPass>().getRDI();1307 MF->getProperties().setTracksLiveness();1308 MRI = &MF->getRegInfo();1309 TII = ST.getInstrInfo();1310 TRI = ST.getRegisterInfo();1311 BBUtils = std::make_unique<ARMBasicBlockUtils>(*MF);1312 BBUtils->computeAllBlockSizes();1313 BBUtils->adjustBBOffsetsAfter(&MF->front());1314 1315 bool Changed = false;1316 for (auto *ML : *MLI) {1317 if (ML->isOutermost())1318 Changed |= ProcessLoop(ML);1319 }1320 Changed |= RevertNonLoops();1321 return Changed;1322}1323 1324bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {1325 bool Changed = false;1326 1327 // Process inner loops first.1328 for (MachineLoop *L : *ML)1329 Changed |= ProcessLoop(L);1330 1331 LLVM_DEBUG({1332 dbgs() << "ARM Loops: Processing loop containing:\n";1333 if (auto *Preheader = ML->getLoopPreheader())1334 dbgs() << " - Preheader: " << printMBBReference(*Preheader) << "\n";1335 else if (auto *Preheader = MLI->findLoopPreheader(ML, true, true))1336 dbgs() << " - Preheader: " << printMBBReference(*Preheader) << "\n";1337 for (auto *MBB : ML->getBlocks())1338 dbgs() << " - Block: " << printMBBReference(*MBB) << "\n";1339 });1340 1341 // Search the given block for a loop start instruction. If one isn't found,1342 // and there's only one predecessor block, search that one too.1343 std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =1344 [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {1345 for (auto &MI : *MBB) {1346 if (isLoopStart(MI))1347 return &MI;1348 }1349 if (MBB->pred_size() == 1)1350 return SearchForStart(*MBB->pred_begin());1351 return nullptr;1352 };1353 1354 LowOverheadLoop LoLoop(*ML, *MLI, *RDI, *TRI, *TII);1355 // Search the preheader for the start intrinsic.1356 // FIXME: I don't see why we shouldn't be supporting multiple predecessors1357 // with potentially multiple set.loop.iterations, so we need to enable this.1358 if (LoLoop.Preheader)1359 LoLoop.Start = SearchForStart(LoLoop.Preheader);1360 else1361 return Changed;1362 1363 // Find the low-overhead loop components and decide whether or not to fall1364 // back to a normal loop. Also look for a vctp instructions and decide1365 // whether we can convert that predicate using tail predication.1366 for (auto *MBB : reverse(ML->getBlocks())) {1367 for (auto &MI : *MBB) {1368 if (MI.isDebugValue())1369 continue;1370 else if (MI.getOpcode() == ARM::t2LoopDec)1371 LoLoop.Dec = &MI;1372 else if (MI.getOpcode() == ARM::t2LoopEnd)1373 LoLoop.End = &MI;1374 else if (MI.getOpcode() == ARM::t2LoopEndDec)1375 LoLoop.End = LoLoop.Dec = &MI;1376 else if (isLoopStart(MI))1377 LoLoop.Start = &MI;1378 else if (MI.getDesc().isCall()) {1379 // TODO: Though the call will require LE to execute again, does this1380 // mean we should revert? Always executing LE hopefully should be1381 // faster than performing a sub,cmp,br or even subs,br.1382 LoLoop.Revert = true;1383 LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");1384 } else {1385 // Record VPR defs and build up their corresponding vpt blocks.1386 // Check we know how to tail predicate any mve instructions.1387 LoLoop.AnalyseMVEInst(&MI);1388 }1389 }1390 }1391 1392 LLVM_DEBUG(LoLoop.dump());1393 if (!LoLoop.FoundAllComponents()) {1394 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");1395 return Changed;1396 }1397 1398 assert(LoLoop.Start->getOpcode() != ARM::t2WhileLoopStart &&1399 "Expected t2WhileLoopStart to be removed before regalloc!");1400 1401 // Check that the only instruction using LoopDec is LoopEnd. This can only1402 // happen when the Dec and End are separate, not a single t2LoopEndDec.1403 // TODO: Check for copy chains that really have no effect.1404 if (LoLoop.Dec != LoLoop.End) {1405 SmallPtrSet<MachineInstr *, 2> Uses;1406 RDI->getReachingLocalUses(LoLoop.Dec, MCRegister::from(ARM::LR), Uses);1407 if (Uses.size() > 1 || !Uses.count(LoLoop.End)) {1408 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n");1409 LoLoop.Revert = true;1410 }1411 }1412 LoLoop.Validate(BBUtils.get());1413 Expand(LoLoop);1414 return true;1415}1416 1417// WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a1418// beq that branches to the exit branch.1419// TODO: We could also try to generate a cbz if the value in LR is also in1420// another low register.1421void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {1422 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);1423 MachineBasicBlock *DestBB = getWhileLoopStartTargetBB(*MI);1424 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?1425 ARM::tBcc : ARM::t2Bcc;1426 1427 RevertWhileLoopStartLR(MI, TII, BrOpc);1428}1429 1430void ARMLowOverheadLoops::RevertDo(MachineInstr *MI) const {1431 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to mov: " << *MI);1432 RevertDoLoopStart(MI, TII);1433}1434 1435bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {1436 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);1437 MachineBasicBlock *MBB = MI->getParent();1438 SmallPtrSet<MachineInstr*, 1> Ignore;1439 for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {1440 if (I->getOpcode() == ARM::t2LoopEnd) {1441 Ignore.insert(&*I);1442 break;1443 }1444 }1445 1446 // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.1447 bool SetFlags =1448 RDI->isSafeToDefRegAt(MI, MCRegister::from(ARM::CPSR), Ignore);1449 1450 llvm::RevertLoopDec(MI, TII, SetFlags);1451 return SetFlags;1452}1453 1454// Generate a subs, or sub and cmp, and a branch instead of an LE.1455void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {1456 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);1457 1458 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();1459 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?1460 ARM::tBcc : ARM::t2Bcc;1461 1462 llvm::RevertLoopEnd(MI, TII, BrOpc, SkipCmp);1463}1464 1465// Generate a subs, or sub and cmp, and a branch instead of an LE.1466void ARMLowOverheadLoops::RevertLoopEndDec(MachineInstr *MI) const {1467 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to subs, br: " << *MI);1468 assert(MI->getOpcode() == ARM::t2LoopEndDec && "Expected a t2LoopEndDec!");1469 MachineBasicBlock *MBB = MI->getParent();1470 1471 MachineInstrBuilder MIB =1472 BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::t2SUBri));1473 MIB.addDef(ARM::LR);1474 MIB.add(MI->getOperand(1));1475 MIB.addImm(1);1476 MIB.addImm(ARMCC::AL);1477 MIB.addReg(ARM::NoRegister);1478 MIB.addReg(ARM::CPSR);1479 MIB->getOperand(5).setIsDef(true);1480 1481 MachineBasicBlock *DestBB = MI->getOperand(2).getMBB();1482 unsigned BrOpc =1483 BBUtils->isBBInRange(MI, DestBB, 254) ? ARM::tBcc : ARM::t2Bcc;1484 1485 // Create bne1486 MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));1487 MIB.add(MI->getOperand(2)); // branch target1488 MIB.addImm(ARMCC::NE); // condition code1489 MIB.addReg(ARM::CPSR);1490 1491 MI->eraseFromParent();1492}1493 1494// Perform dead code elimation on the loop iteration count setup expression.1495// If we are tail-predicating, the number of elements to be processed is the1496// operand of the VCTP instruction in the vector body, see getCount(), which is1497// register $r3 in this example:1498//1499// $lr = big-itercount-expression1500// ..1501// $lr = t2DoLoopStart renamable $lr1502// vector.body:1503// ..1504// $vpr = MVE_VCTP32 renamable $r31505// renamable $lr = t2LoopDec killed renamable $lr, 11506// t2LoopEnd renamable $lr, %vector.body1507// tB %end1508//1509// What we would like achieve here is to replace the do-loop start pseudo1510// instruction t2DoLoopStart with:1511//1512// $lr = MVE_DLSTP_32 killed renamable $r31513//1514// Thus, $r3 which defines the number of elements, is written to $lr,1515// and then we want to delete the whole chain that used to define $lr,1516// see the comment below how this chain could look like.1517//1518void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {1519 if (!LoLoop.IsTailPredicationLegal())1520 return;1521 1522 LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n");1523 1524 MachineInstr *Def = RDI->getMIOperand(LoLoop.Start, 1);1525 if (!Def) {1526 LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");1527 return;1528 }1529 1530 // Collect and remove the users of iteration count.1531 SmallPtrSet<MachineInstr*, 4> Killed = { LoLoop.Start, LoLoop.Dec,1532 LoLoop.End };1533 if (!TryRemove(Def, *RDI, LoLoop.ToRemove, Killed))1534 LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n");1535}1536 1537MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {1538 LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");1539 // When using tail-predication, try to delete the dead code that was used to1540 // calculate the number of loop iterations.1541 IterationCountDCE(LoLoop);1542 1543 MachineBasicBlock::iterator InsertPt = LoLoop.StartInsertPt;1544 MachineInstr *Start = LoLoop.Start;1545 MachineBasicBlock *MBB = LoLoop.StartInsertBB;1546 unsigned Opc = LoLoop.getStartOpcode();1547 MachineOperand &Count = LoLoop.getLoopStartOperand();1548 1549 // A DLS lr, lr we needn't emit1550 MachineInstr* NewStart;1551 if (!DisableOmitDLS && Opc == ARM::t2DLS && Count.isReg() &&1552 Count.getReg() == ARM::LR) {1553 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't insert start: DLS lr, lr");1554 NewStart = nullptr;1555 } else {1556 MachineInstrBuilder MIB =1557 BuildMI(*MBB, InsertPt, Start->getDebugLoc(), TII->get(Opc));1558 1559 MIB.addDef(ARM::LR);1560 MIB.add(Count);1561 if (isWhileLoopStart(*Start))1562 MIB.addMBB(getWhileLoopStartTargetBB(*Start));1563 1564 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);1565 NewStart = &*MIB;1566 }1567 1568 LoLoop.ToRemove.insert(Start);1569 return NewStart;1570}1571 1572void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {1573 auto RemovePredicate = [](MachineInstr *MI) {1574 if (MI->isDebugInstr())1575 return;1576 LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);1577 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);1578 assert(PIdx >= 1 && "Trying to unpredicate a non-predicated instruction");1579 assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&1580 "Expected Then predicate!");1581 MI->getOperand(PIdx).setImm(ARMVCC::None);1582 MI->getOperand(PIdx + 1).setReg(0);1583 };1584 1585 for (auto &Block : LoLoop.getVPTBlocks()) {1586 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();1587 1588 auto ReplaceVCMPWithVPT = [&](MachineInstr *&TheVCMP, MachineInstr *At) {1589 assert(TheVCMP && "Replacing a removed or non-existent VCMP");1590 // Replace the VCMP with a VPT1591 MachineInstrBuilder MIB =1592 BuildMI(*At->getParent(), At, At->getDebugLoc(),1593 TII->get(VCMPOpcodeToVPT(TheVCMP->getOpcode())));1594 MIB.addImm(ARMVCC::Then);1595 // Register one1596 MIB.add(TheVCMP->getOperand(1));1597 // Register two1598 MIB.add(TheVCMP->getOperand(2));1599 // The comparison code, e.g. ge, eq, lt1600 MIB.add(TheVCMP->getOperand(3));1601 LLVM_DEBUG(dbgs() << "ARM Loops: Combining with VCMP to VPT: " << *MIB);1602 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());1603 LoLoop.ToRemove.insert(TheVCMP);1604 TheVCMP = nullptr;1605 };1606 1607 if (LoLoop.VPTstate.isEntryPredicatedOnVCTP(Block, /*exclusive*/ true)) {1608 MachineInstr *VPST = Insts.front();1609 if (Block.hasUniformPredicate()) {1610 // A vpt block starting with VPST, is only predicated upon vctp and has no1611 // internal vpr defs:1612 // - Remove vpst.1613 // - Unpredicate the remaining instructions.1614 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);1615 for (unsigned i = 1; i < Insts.size(); ++i)1616 RemovePredicate(Insts[i]);1617 } else {1618 // The VPT block has a non-uniform predicate but it uses a vpst and its1619 // entry is guarded only by a vctp, which means we:1620 // - Need to remove the original vpst.1621 // - Then need to unpredicate any following instructions, until1622 // we come across the divergent vpr def.1623 // - Insert a new vpst to predicate the instruction(s) that following1624 // the divergent vpr def.1625 MachineInstr *Divergent = Block.getDivergent();1626 MachineBasicBlock *MBB = Divergent->getParent();1627 auto DivergentNext = ++MachineBasicBlock::iterator(Divergent);1628 while (DivergentNext != MBB->end() && DivergentNext->isDebugInstr())1629 ++DivergentNext;1630 1631 bool DivergentNextIsPredicated =1632 DivergentNext != MBB->end() &&1633 getVPTInstrPredicate(*DivergentNext) != ARMVCC::None;1634 1635 for (auto I = ++MachineBasicBlock::iterator(VPST), E = DivergentNext;1636 I != E; ++I)1637 RemovePredicate(&*I);1638 1639 // Check if the instruction defining vpr is a vcmp so it can be combined1640 // with the VPST This should be the divergent instruction1641 MachineInstr *VCMP =1642 VCMPOpcodeToVPT(Divergent->getOpcode()) != 0 ? Divergent : nullptr;1643 1644 if (DivergentNextIsPredicated) {1645 // Insert a VPST at the divergent only if the next instruction1646 // would actually use it. A VCMP following a VPST can be1647 // merged into a VPT so do that instead if the VCMP exists.1648 if (!VCMP) {1649 // Create a VPST (with a null mask for now, we'll recompute it1650 // later)1651 MachineInstrBuilder MIB =1652 BuildMI(*Divergent->getParent(), Divergent,1653 Divergent->getDebugLoc(), TII->get(ARM::MVE_VPST));1654 MIB.addImm(0);1655 LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);1656 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());1657 } else {1658 // No RDI checks are necessary here since the VPST would have been1659 // directly after the VCMP1660 ReplaceVCMPWithVPT(VCMP, VCMP);1661 }1662 }1663 }1664 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);1665 LoLoop.ToRemove.insert(VPST);1666 } else if (Block.containsVCTP()) {1667 // The vctp will be removed, so either the entire block will be dead or1668 // the block mask of the vp(s)t will need to be recomputed.1669 MachineInstr *VPST = Insts.front();1670 if (Block.size() == 2) {1671 assert(VPST->getOpcode() == ARM::MVE_VPST &&1672 "Found a VPST in an otherwise empty vpt block");1673 LoLoop.ToRemove.insert(VPST);1674 } else1675 LoLoop.BlockMasksToRecompute.insert(VPST);1676 } else if (Insts.front()->getOpcode() == ARM::MVE_VPST) {1677 // If this block starts with a VPST then attempt to merge it with the1678 // preceeding un-merged VCMP into a VPT. This VCMP comes from a VPT1679 // block that no longer exists1680 MachineInstr *VPST = Insts.front();1681 auto Next = ++MachineBasicBlock::iterator(VPST);1682 assert(getVPTInstrPredicate(*Next) != ARMVCC::None &&1683 "The instruction after a VPST must be predicated");1684 (void)Next;1685 MachineInstr *VprDef = RDI->getUniqueReachingMIDef(VPST, ARM::VPR);1686 if (VprDef && VCMPOpcodeToVPT(VprDef->getOpcode()) &&1687 !LoLoop.ToRemove.contains(VprDef)) {1688 MachineInstr *VCMP = VprDef;1689 // The VCMP and VPST can only be merged if the VCMP's operands will have1690 // the same values at the VPST.1691 // If any of the instructions between the VCMP and VPST are predicated1692 // then a different code path is expected to have merged the VCMP and1693 // VPST already.1694 if (std::none_of(++MachineBasicBlock::iterator(VCMP),1695 MachineBasicBlock::iterator(VPST), hasVPRUse) &&1696 RDI->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(1).getReg()) &&1697 RDI->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(2).getReg())) {1698 ReplaceVCMPWithVPT(VCMP, VPST);1699 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);1700 LoLoop.ToRemove.insert(VPST);1701 }1702 }1703 }1704 }1705 1706 LoLoop.ToRemove.insert_range(LoLoop.VCTPs);1707}1708 1709void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {1710 1711 // Combine the LoopDec and LoopEnd instructions into LE(TP).1712 auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {1713 MachineInstr *End = LoLoop.End;1714 MachineBasicBlock *MBB = End->getParent();1715 unsigned Opc = LoLoop.IsTailPredicationLegal() ?1716 ARM::MVE_LETP : ARM::t2LEUpdate;1717 MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),1718 TII->get(Opc));1719 MIB.addDef(ARM::LR);1720 unsigned Off = LoLoop.Dec == LoLoop.End ? 1 : 0;1721 MIB.add(End->getOperand(Off + 0));1722 MIB.add(End->getOperand(Off + 1));1723 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);1724 LoLoop.ToRemove.insert(LoLoop.Dec);1725 LoLoop.ToRemove.insert(End);1726 return &*MIB;1727 };1728 1729 // TODO: We should be able to automatically remove these branches before we1730 // get here - probably by teaching analyzeBranch about the pseudo1731 // instructions.1732 // If there is an unconditional branch, after I, that just branches to the1733 // next block, remove it.1734 auto RemoveDeadBranch = [](MachineInstr *I) {1735 MachineBasicBlock *BB = I->getParent();1736 MachineInstr *Terminator = &BB->instr_back();1737 if (Terminator->isUnconditionalBranch() && I != Terminator) {1738 MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();1739 if (BB->isLayoutSuccessor(Succ)) {1740 LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);1741 Terminator->eraseFromParent();1742 }1743 }1744 };1745 1746 // And VMOVCopies need to become 2xVMOVD for tail predication to be valid.1747 // Anything other MQPRCopy can be converted to MVE_VORR later on.1748 auto ExpandVMOVCopies = [this](SmallPtrSet<MachineInstr *, 4> &VMOVCopies) {1749 for (auto *MI : VMOVCopies) {1750 LLVM_DEBUG(dbgs() << "Converting copy to VMOVD: " << *MI);1751 assert(MI->getOpcode() == ARM::MQPRCopy && "Only expected MQPRCOPY!");1752 MachineBasicBlock *MBB = MI->getParent();1753 Register Dst = MI->getOperand(0).getReg();1754 Register Src = MI->getOperand(1).getReg();1755 auto MIB1 = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::VMOVD),1756 ARM::D0 + (Dst - ARM::Q0) * 2)1757 .addReg(ARM::D0 + (Src - ARM::Q0) * 2)1758 .add(predOps(ARMCC::AL));1759 (void)MIB1;1760 LLVM_DEBUG(dbgs() << " into " << *MIB1);1761 auto MIB2 = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::VMOVD),1762 ARM::D0 + (Dst - ARM::Q0) * 2 + 1)1763 .addReg(ARM::D0 + (Src - ARM::Q0) * 2 + 1)1764 .add(predOps(ARMCC::AL));1765 LLVM_DEBUG(dbgs() << " and " << *MIB2);1766 (void)MIB2;1767 MI->eraseFromParent();1768 }1769 };1770 1771 if (LoLoop.Revert) {1772 if (isWhileLoopStart(*LoLoop.Start))1773 RevertWhile(LoLoop.Start);1774 else1775 RevertDo(LoLoop.Start);1776 if (LoLoop.Dec == LoLoop.End)1777 RevertLoopEndDec(LoLoop.End);1778 else1779 RevertLoopEnd(LoLoop.End, RevertLoopDec(LoLoop.Dec));1780 } else {1781 ExpandVMOVCopies(LoLoop.VMOVCopies);1782 LoLoop.Start = ExpandLoopStart(LoLoop);1783 if (LoLoop.Start)1784 RemoveDeadBranch(LoLoop.Start);1785 LoLoop.End = ExpandLoopEnd(LoLoop);1786 RemoveDeadBranch(LoLoop.End);1787 if (LoLoop.IsTailPredicationLegal())1788 ConvertVPTBlocks(LoLoop);1789 for (auto *I : LoLoop.ToRemove) {1790 LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I);1791 I->eraseFromParent();1792 }1793 for (auto *I : LoLoop.BlockMasksToRecompute) {1794 LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I);1795 recomputeVPTBlockMask(*I);1796 LLVM_DEBUG(dbgs() << " ... done: " << *I);1797 }1798 }1799 1800 PostOrderLoopTraversal DFS(LoLoop.ML, *MLI);1801 DFS.ProcessLoop();1802 const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder();1803 fullyRecomputeLiveIns(PostOrder);1804 1805 for (auto *MBB : reverse(PostOrder))1806 recomputeLivenessFlags(*MBB);1807 1808 // We've moved, removed and inserted new instructions, so update RDI.1809 RDI->reset();1810}1811 1812bool ARMLowOverheadLoops::RevertNonLoops() {1813 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");1814 bool Changed = false;1815 1816 for (auto &MBB : *MF) {1817 SmallVector<MachineInstr*, 4> Starts;1818 SmallVector<MachineInstr*, 4> Decs;1819 SmallVector<MachineInstr*, 4> Ends;1820 SmallVector<MachineInstr *, 4> EndDecs;1821 SmallVector<MachineInstr *, 4> MQPRCopies;1822 1823 for (auto &I : MBB) {1824 if (isLoopStart(I))1825 Starts.push_back(&I);1826 else if (I.getOpcode() == ARM::t2LoopDec)1827 Decs.push_back(&I);1828 else if (I.getOpcode() == ARM::t2LoopEnd)1829 Ends.push_back(&I);1830 else if (I.getOpcode() == ARM::t2LoopEndDec)1831 EndDecs.push_back(&I);1832 else if (I.getOpcode() == ARM::MQPRCopy)1833 MQPRCopies.push_back(&I);1834 }1835 1836 if (Starts.empty() && Decs.empty() && Ends.empty() && EndDecs.empty() &&1837 MQPRCopies.empty())1838 continue;1839 1840 Changed = true;1841 1842 for (auto *Start : Starts) {1843 if (isWhileLoopStart(*Start))1844 RevertWhile(Start);1845 else1846 RevertDo(Start);1847 }1848 for (auto *Dec : Decs)1849 RevertLoopDec(Dec);1850 1851 for (auto *End : Ends)1852 RevertLoopEnd(End);1853 for (auto *End : EndDecs)1854 RevertLoopEndDec(End);1855 for (auto *MI : MQPRCopies) {1856 LLVM_DEBUG(dbgs() << "Converting copy to VORR: " << *MI);1857 assert(MI->getOpcode() == ARM::MQPRCopy && "Only expected MQPRCOPY!");1858 MachineBasicBlock *MBB = MI->getParent();1859 auto MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::MVE_VORR),1860 MI->getOperand(0).getReg())1861 .add(MI->getOperand(1))1862 .add(MI->getOperand(1));1863 addUnpredicatedMveVpredROp(MIB, MI->getOperand(0).getReg());1864 MI->eraseFromParent();1865 }1866 }1867 return Changed;1868}1869 1870FunctionPass *llvm::createARMLowOverheadLoopsPass() {1871 return new ARMLowOverheadLoops();1872}1873