1327952Sdim//===- PeepholeOptimizer.cpp - Peephole Optimizations ---------------------===// 2212793Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6212793Sdim// 7212793Sdim//===----------------------------------------------------------------------===// 8212793Sdim// 9212793Sdim// Perform peephole optimizations on the machine code: 10212793Sdim// 11212793Sdim// - Optimize Extensions 12212793Sdim// 13212793Sdim// Optimization of sign / zero extension instructions. It may be extended to 14212793Sdim// handle other instructions with similar properties. 15212793Sdim// 16212793Sdim// On some targets, some instructions, e.g. X86 sign / zero extension, may 17212793Sdim// leave the source value in the lower part of the result. This optimization 18212793Sdim// will replace some uses of the pre-extension value with uses of the 19212793Sdim// sub-register of the results. 20212793Sdim// 21212793Sdim// - Optimize Comparisons 22212793Sdim// 23212793Sdim// Optimization of comparison instructions. For instance, in this code: 24212793Sdim// 25212793Sdim// sub r1, 1 26212793Sdim// cmp r1, 0 27212793Sdim// bz L1 28212793Sdim// 29212793Sdim// If the "sub" instruction all ready sets (or could be modified to set) the 30212793Sdim// same flag that the "cmp" instruction sets and that "bz" uses, then we can 31212793Sdim// eliminate the "cmp" instruction. 32221345Sdim// 33239462Sdim// Another instance, in this code: 34239462Sdim// 35239462Sdim// sub r1, r3 | sub r1, imm 36239462Sdim// cmp r3, r1 or cmp r1, r3 | cmp r1, imm 37239462Sdim// bge L1 38239462Sdim// 39239462Sdim// If the branch instruction can use flag from "sub", then we can replace 40239462Sdim// "sub" with "subs" and eliminate the "cmp" instruction. 41239462Sdim// 42249423Sdim// - Optimize Loads: 43249423Sdim// 44249423Sdim// Loads that can be folded into a later instruction. A load is foldable 45296417Sdim// if it loads to virtual registers and the virtual register defined has 46249423Sdim// a single use. 47261991Sdim// 48280031Sdim// - Optimize Copies and Bitcast (more generally, target specific copies): 49261991Sdim// 50261991Sdim// Rewrite copies and bitcasts to avoid cross register bank copies 51261991Sdim// when possible. 52261991Sdim// E.g., Consider the following example, where capital and lower 53261991Sdim// letters denote different register file: 54261991Sdim// b = copy A <-- cross-bank copy 55261991Sdim// C = copy b <-- cross-bank copy 56261991Sdim// => 57261991Sdim// b = copy A <-- cross-bank copy 58261991Sdim// C = copy A <-- same-bank copy 59261991Sdim// 60261991Sdim// E.g., for bitcast: 61261991Sdim// b = bitcast A <-- cross-bank copy 62261991Sdim// C = bitcast b <-- cross-bank copy 63261991Sdim// => 64261991Sdim// b = bitcast A <-- cross-bank copy 65261991Sdim// C = copy A <-- same-bank copy 66212793Sdim//===----------------------------------------------------------------------===// 67212793Sdim 68249423Sdim#include "llvm/ADT/DenseMap.h" 69327952Sdim#include "llvm/ADT/Optional.h" 70249423Sdim#include "llvm/ADT/SmallPtrSet.h" 71249423Sdim#include "llvm/ADT/SmallSet.h" 72314564Sdim#include "llvm/ADT/SmallVector.h" 73249423Sdim#include "llvm/ADT/Statistic.h" 74314564Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 75212793Sdim#include "llvm/CodeGen/MachineDominators.h" 76314564Sdim#include "llvm/CodeGen/MachineFunction.h" 77327952Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 78314564Sdim#include "llvm/CodeGen/MachineInstr.h" 79212793Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 80321369Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 81314564Sdim#include "llvm/CodeGen/MachineOperand.h" 82212793Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 83327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 84327952Sdim#include "llvm/CodeGen/TargetOpcodes.h" 85327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 86327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 87360784Sdim#include "llvm/InitializePasses.h" 88327952Sdim#include "llvm/MC/LaneBitmask.h" 89314564Sdim#include "llvm/MC/MCInstrDesc.h" 90327952Sdim#include "llvm/Pass.h" 91249423Sdim#include "llvm/Support/CommandLine.h" 92249423Sdim#include "llvm/Support/Debug.h" 93314564Sdim#include "llvm/Support/ErrorHandling.h" 94288943Sdim#include "llvm/Support/raw_ostream.h" 95314564Sdim#include <cassert> 96314564Sdim#include <cstdint> 97314564Sdim#include <memory> 98280031Sdim#include <utility> 99314564Sdim 100212793Sdimusing namespace llvm; 101333715Sdimusing RegSubRegPair = TargetInstrInfo::RegSubRegPair; 102333715Sdimusing RegSubRegPairAndIdx = TargetInstrInfo::RegSubRegPairAndIdx; 103212793Sdim 104276479Sdim#define DEBUG_TYPE "peephole-opt" 105276479Sdim 106212793Sdim// Optimize Extensions 107212793Sdimstatic cl::opt<bool> 108212793SdimAggressive("aggressive-ext-opt", cl::Hidden, 109212793Sdim cl::desc("Aggressive extension optimization")); 110212793Sdim 111218893Sdimstatic cl::opt<bool> 112218893SdimDisablePeephole("disable-peephole", cl::Hidden, cl::init(false), 113218893Sdim cl::desc("Disable the peephole optimizer")); 114218893Sdim 115333715Sdim/// Specifiy whether or not the value tracking looks through 116333715Sdim/// complex instructions. When this is true, the value tracker 117333715Sdim/// bails on everything that is not a copy or a bitcast. 118276479Sdimstatic cl::opt<bool> 119280031SdimDisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(false), 120276479Sdim cl::desc("Disable advanced copy optimization")); 121276479Sdim 122296417Sdimstatic cl::opt<bool> DisableNAPhysCopyOpt( 123296417Sdim "disable-non-allocatable-phys-copy-opt", cl::Hidden, cl::init(false), 124296417Sdim cl::desc("Disable non-allocatable physical register copy optimization")); 125296417Sdim 126296417Sdim// Limit the number of PHI instructions to process 127296417Sdim// in PeepholeOptimizer::getNextSource. 128296417Sdimstatic cl::opt<unsigned> RewritePHILimit( 129296417Sdim "rewrite-phi-limit", cl::Hidden, cl::init(10), 130296417Sdim cl::desc("Limit the length of PHI chains to lookup")); 131296417Sdim 132321369Sdim// Limit the length of recurrence chain when evaluating the benefit of 133321369Sdim// commuting operands. 134321369Sdimstatic cl::opt<unsigned> MaxRecurrenceChain( 135321369Sdim "recurrence-chain-limit", cl::Hidden, cl::init(3), 136321369Sdim cl::desc("Maximum length of recurrence chain when evaluating the benefit " 137321369Sdim "of commuting operands")); 138321369Sdim 139321369Sdim 140333715SdimSTATISTIC(NumReuse, "Number of extension results reused"); 141333715SdimSTATISTIC(NumCmps, "Number of compares eliminated"); 142333715SdimSTATISTIC(NumImmFold, "Number of move immediate folded"); 143333715SdimSTATISTIC(NumLoadFold, "Number of loads folded"); 144333715SdimSTATISTIC(NumSelects, "Number of selects optimized"); 145280031SdimSTATISTIC(NumUncoalescableCopies, "Number of uncoalescable copies optimized"); 146280031SdimSTATISTIC(NumRewrittenCopies, "Number of copies rewritten"); 147296417SdimSTATISTIC(NumNAPhysCopies, "Number of non-allocatable physical copies removed"); 148212793Sdim 149212793Sdimnamespace { 150314564Sdim 151296417Sdim class ValueTrackerResult; 152321369Sdim class RecurrenceInstr; 153296417Sdim 154212793Sdim class PeepholeOptimizer : public MachineFunctionPass { 155212793Sdim const TargetInstrInfo *TII; 156280031Sdim const TargetRegisterInfo *TRI; 157333715Sdim MachineRegisterInfo *MRI; 158333715Sdim MachineDominatorTree *DT; // Machine dominator tree 159333715Sdim MachineLoopInfo *MLI; 160212793Sdim 161212793Sdim public: 162212793Sdim static char ID; // Pass identification 163314564Sdim 164218893Sdim PeepholeOptimizer() : MachineFunctionPass(ID) { 165218893Sdim initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry()); 166218893Sdim } 167212793Sdim 168276479Sdim bool runOnMachineFunction(MachineFunction &MF) override; 169212793Sdim 170276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 171212793Sdim AU.setPreservesCFG(); 172212793Sdim MachineFunctionPass::getAnalysisUsage(AU); 173321369Sdim AU.addRequired<MachineLoopInfo>(); 174321369Sdim AU.addPreserved<MachineLoopInfo>(); 175212793Sdim if (Aggressive) { 176212793Sdim AU.addRequired<MachineDominatorTree>(); 177212793Sdim AU.addPreserved<MachineDominatorTree>(); 178212793Sdim } 179212793Sdim } 180212793Sdim 181333715Sdim /// Track Def -> Use info used for rewriting copies. 182333715Sdim using RewriteMapTy = SmallDenseMap<RegSubRegPair, ValueTrackerResult>; 183296417Sdim 184333715Sdim /// Sequence of instructions that formulate recurrence cycle. 185327952Sdim using RecurrenceCycle = SmallVector<RecurrenceInstr, 4>; 186321369Sdim 187212793Sdim private: 188333715Sdim bool optimizeCmpInstr(MachineInstr &MI); 189333715Sdim bool optimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB, 190280031Sdim SmallPtrSetImpl<MachineInstr*> &LocalMIs); 191333715Sdim bool optimizeSelect(MachineInstr &MI, 192280031Sdim SmallPtrSetImpl<MachineInstr *> &LocalMIs); 193333715Sdim bool optimizeCondBranch(MachineInstr &MI); 194333715Sdim bool optimizeCoalescableCopy(MachineInstr &MI); 195333715Sdim bool optimizeUncoalescableCopy(MachineInstr &MI, 196280031Sdim SmallPtrSetImpl<MachineInstr *> &LocalMIs); 197321369Sdim bool optimizeRecurrence(MachineInstr &PHI); 198333715Sdim bool findNextSource(RegSubRegPair RegSubReg, RewriteMapTy &RewriteMap); 199333715Sdim bool isMoveImmediate(MachineInstr &MI, 200218893Sdim SmallSet<unsigned, 4> &ImmDefRegs, 201218893Sdim DenseMap<unsigned, MachineInstr*> &ImmDefMIs); 202333715Sdim bool foldImmediate(MachineInstr &MI, SmallSet<unsigned, 4> &ImmDefRegs, 203218893Sdim DenseMap<unsigned, MachineInstr*> &ImmDefMIs); 204327952Sdim 205341825Sdim /// Finds recurrence cycles, but only ones that formulated around 206321369Sdim /// a def operand and a use operand that are tied. If there is a use 207321369Sdim /// operand commutable with the tied use operand, find recurrence cycle 208321369Sdim /// along that operand as well. 209321369Sdim bool findTargetRecurrence(unsigned Reg, 210321369Sdim const SmallSet<unsigned, 2> &TargetReg, 211321369Sdim RecurrenceCycle &RC); 212296417Sdim 213341825Sdim /// If copy instruction \p MI is a virtual register copy, track it in 214296417Sdim /// the set \p CopySrcRegs and \p CopyMIs. If this virtual register was 215296417Sdim /// previously seen as a copy, replace the uses of this copy with the 216296417Sdim /// previously seen copy's destination register. 217333715Sdim bool foldRedundantCopy(MachineInstr &MI, 218296417Sdim SmallSet<unsigned, 4> &CopySrcRegs, 219296417Sdim DenseMap<unsigned, MachineInstr *> &CopyMIs); 220296417Sdim 221333715Sdim /// Is the register \p Reg a non-allocatable physical register? 222296417Sdim bool isNAPhysCopy(unsigned Reg); 223296417Sdim 224341825Sdim /// If copy instruction \p MI is a non-allocatable virtual<->physical 225296417Sdim /// register copy, track it in the \p NAPhysToVirtMIs map. If this 226296417Sdim /// non-allocatable physical register was previously copied to a virtual 227296417Sdim /// registered and hasn't been clobbered, the virt->phys copy can be 228296417Sdim /// deleted. 229333715Sdim bool foldRedundantNAPhysCopy(MachineInstr &MI, 230296417Sdim DenseMap<unsigned, MachineInstr *> &NAPhysToVirtMIs); 231296417Sdim 232333715Sdim bool isLoadFoldable(MachineInstr &MI, 233276479Sdim SmallSet<unsigned, 16> &FoldAsLoadDefCandidates); 234280031Sdim 235341825Sdim /// Check whether \p MI is understood by the register coalescer 236280031Sdim /// but may require some rewriting. 237280031Sdim bool isCoalescableCopy(const MachineInstr &MI) { 238280031Sdim // SubregToRegs are not interesting, because they are already register 239280031Sdim // coalescer friendly. 240280031Sdim return MI.isCopy() || (!DisableAdvCopyOpt && 241280031Sdim (MI.isRegSequence() || MI.isInsertSubreg() || 242280031Sdim MI.isExtractSubreg())); 243280031Sdim } 244280031Sdim 245341825Sdim /// Check whether \p MI is a copy like instruction that is 246280031Sdim /// not recognized by the register coalescer. 247280031Sdim bool isUncoalescableCopy(const MachineInstr &MI) { 248280031Sdim return MI.isBitcast() || 249280031Sdim (!DisableAdvCopyOpt && 250280031Sdim (MI.isRegSequenceLike() || MI.isInsertSubregLike() || 251280031Sdim MI.isExtractSubregLike())); 252280031Sdim } 253333715Sdim 254333715Sdim MachineInstr &rewriteSource(MachineInstr &CopyLike, 255333715Sdim RegSubRegPair Def, RewriteMapTy &RewriteMap); 256212793Sdim }; 257276479Sdim 258333715Sdim /// Helper class to hold instructions that are inside recurrence cycles. 259333715Sdim /// The recurrence cycle is formulated around 1) a def operand and its 260321369Sdim /// tied use operand, or 2) a def operand and a use operand that is commutable 261321369Sdim /// with another use operand which is tied to the def operand. In the latter 262321369Sdim /// case, index of the tied use operand and the commutable use operand are 263321369Sdim /// maintained with CommutePair. 264321369Sdim class RecurrenceInstr { 265321369Sdim public: 266327952Sdim using IndexPair = std::pair<unsigned, unsigned>; 267321369Sdim 268321369Sdim RecurrenceInstr(MachineInstr *MI) : MI(MI) {} 269321369Sdim RecurrenceInstr(MachineInstr *MI, unsigned Idx1, unsigned Idx2) 270321369Sdim : MI(MI), CommutePair(std::make_pair(Idx1, Idx2)) {} 271321369Sdim 272321369Sdim MachineInstr *getMI() const { return MI; } 273321369Sdim Optional<IndexPair> getCommutePair() const { return CommutePair; } 274321369Sdim 275321369Sdim private: 276321369Sdim MachineInstr *MI; 277321369Sdim Optional<IndexPair> CommutePair; 278321369Sdim }; 279321369Sdim 280333715Sdim /// Helper class to hold a reply for ValueTracker queries. 281333715Sdim /// Contains the returned sources for a given search and the instructions 282333715Sdim /// where the sources were tracked from. 283296417Sdim class ValueTrackerResult { 284296417Sdim private: 285296417Sdim /// Track all sources found by one ValueTracker query. 286333715Sdim SmallVector<RegSubRegPair, 2> RegSrcs; 287296417Sdim 288296417Sdim /// Instruction using the sources in 'RegSrcs'. 289327952Sdim const MachineInstr *Inst = nullptr; 290296417Sdim 291296417Sdim public: 292327952Sdim ValueTrackerResult() = default; 293327952Sdim 294327952Sdim ValueTrackerResult(unsigned Reg, unsigned SubReg) { 295296417Sdim addSource(Reg, SubReg); 296296417Sdim } 297296417Sdim 298296417Sdim bool isValid() const { return getNumSources() > 0; } 299296417Sdim 300296417Sdim void setInst(const MachineInstr *I) { Inst = I; } 301296417Sdim const MachineInstr *getInst() const { return Inst; } 302296417Sdim 303296417Sdim void clear() { 304296417Sdim RegSrcs.clear(); 305296417Sdim Inst = nullptr; 306296417Sdim } 307296417Sdim 308296417Sdim void addSource(unsigned SrcReg, unsigned SrcSubReg) { 309333715Sdim RegSrcs.push_back(RegSubRegPair(SrcReg, SrcSubReg)); 310296417Sdim } 311296417Sdim 312296417Sdim void setSource(int Idx, unsigned SrcReg, unsigned SrcSubReg) { 313296417Sdim assert(Idx < getNumSources() && "Reg pair source out of index"); 314333715Sdim RegSrcs[Idx] = RegSubRegPair(SrcReg, SrcSubReg); 315296417Sdim } 316296417Sdim 317296417Sdim int getNumSources() const { return RegSrcs.size(); } 318296417Sdim 319333715Sdim RegSubRegPair getSrc(int Idx) const { 320333715Sdim return RegSrcs[Idx]; 321333715Sdim } 322333715Sdim 323296417Sdim unsigned getSrcReg(int Idx) const { 324296417Sdim assert(Idx < getNumSources() && "Reg source out of index"); 325296417Sdim return RegSrcs[Idx].Reg; 326296417Sdim } 327296417Sdim 328296417Sdim unsigned getSrcSubReg(int Idx) const { 329296417Sdim assert(Idx < getNumSources() && "SubReg source out of index"); 330296417Sdim return RegSrcs[Idx].SubReg; 331296417Sdim } 332296417Sdim 333296417Sdim bool operator==(const ValueTrackerResult &Other) { 334296417Sdim if (Other.getInst() != getInst()) 335296417Sdim return false; 336296417Sdim 337296417Sdim if (Other.getNumSources() != getNumSources()) 338296417Sdim return false; 339296417Sdim 340296417Sdim for (int i = 0, e = Other.getNumSources(); i != e; ++i) 341296417Sdim if (Other.getSrcReg(i) != getSrcReg(i) || 342296417Sdim Other.getSrcSubReg(i) != getSrcSubReg(i)) 343296417Sdim return false; 344296417Sdim return true; 345296417Sdim } 346296417Sdim }; 347296417Sdim 348341825Sdim /// Helper class to track the possible sources of a value defined by 349276479Sdim /// a (chain of) copy related instructions. 350276479Sdim /// Given a definition (instruction and definition index), this class 351276479Sdim /// follows the use-def chain to find successive suitable sources. 352276479Sdim /// The given source can be used to rewrite the definition into 353276479Sdim /// def = COPY src. 354276479Sdim /// 355276479Sdim /// For instance, let us consider the following snippet: 356276479Sdim /// v0 = 357276479Sdim /// v2 = INSERT_SUBREG v1, v0, sub0 358276479Sdim /// def = COPY v2.sub0 359276479Sdim /// 360276479Sdim /// Using a ValueTracker for def = COPY v2.sub0 will give the following 361276479Sdim /// suitable sources: 362276479Sdim /// v2.sub0 and v0. 363276479Sdim /// Then, def can be rewritten into def = COPY v0. 364276479Sdim class ValueTracker { 365276479Sdim private: 366276479Sdim /// The current point into the use-def chain. 367327952Sdim const MachineInstr *Def = nullptr; 368327952Sdim 369276479Sdim /// The index of the definition in Def. 370327952Sdim unsigned DefIdx = 0; 371327952Sdim 372276479Sdim /// The sub register index of the definition. 373276479Sdim unsigned DefSubReg; 374327952Sdim 375276479Sdim /// The register where the value can be found. 376276479Sdim unsigned Reg; 377327952Sdim 378280031Sdim /// MachineRegisterInfo used to perform tracking. 379280031Sdim const MachineRegisterInfo &MRI; 380327952Sdim 381333715Sdim /// Optional TargetInstrInfo used to perform some complex tracking. 382280031Sdim const TargetInstrInfo *TII; 383276479Sdim 384333715Sdim /// Dispatcher to the right underlying implementation of getNextSource. 385296417Sdim ValueTrackerResult getNextSourceImpl(); 386327952Sdim 387333715Sdim /// Specialized version of getNextSource for Copy instructions. 388296417Sdim ValueTrackerResult getNextSourceFromCopy(); 389327952Sdim 390333715Sdim /// Specialized version of getNextSource for Bitcast instructions. 391296417Sdim ValueTrackerResult getNextSourceFromBitcast(); 392327952Sdim 393333715Sdim /// Specialized version of getNextSource for RegSequence instructions. 394296417Sdim ValueTrackerResult getNextSourceFromRegSequence(); 395327952Sdim 396333715Sdim /// Specialized version of getNextSource for InsertSubreg instructions. 397296417Sdim ValueTrackerResult getNextSourceFromInsertSubreg(); 398327952Sdim 399333715Sdim /// Specialized version of getNextSource for ExtractSubreg instructions. 400296417Sdim ValueTrackerResult getNextSourceFromExtractSubreg(); 401327952Sdim 402333715Sdim /// Specialized version of getNextSource for SubregToReg instructions. 403296417Sdim ValueTrackerResult getNextSourceFromSubregToReg(); 404327952Sdim 405333715Sdim /// Specialized version of getNextSource for PHI instructions. 406296417Sdim ValueTrackerResult getNextSourceFromPHI(); 407276479Sdim 408276479Sdim public: 409333715Sdim /// Create a ValueTracker instance for the value defined by \p Reg. 410276479Sdim /// \p DefSubReg represents the sub register index the value tracker will 411280031Sdim /// track. It does not need to match the sub register index used in the 412280031Sdim /// definition of \p Reg. 413280031Sdim /// If \p Reg is a physical register, a value tracker constructed with 414280031Sdim /// this constructor will not find any alternative source. 415280031Sdim /// Indeed, when \p Reg is a physical register that constructor does not 416280031Sdim /// know which definition of \p Reg it should track. 417280031Sdim /// Use the next constructor to track a physical register. 418280031Sdim ValueTracker(unsigned Reg, unsigned DefSubReg, 419280031Sdim const MachineRegisterInfo &MRI, 420280031Sdim const TargetInstrInfo *TII = nullptr) 421333715Sdim : DefSubReg(DefSubReg), Reg(Reg), MRI(MRI), TII(TII) { 422360784Sdim if (!Register::isPhysicalRegister(Reg)) { 423280031Sdim Def = MRI.getVRegDef(Reg); 424280031Sdim DefIdx = MRI.def_begin(Reg).getOperandNo(); 425280031Sdim } 426280031Sdim } 427280031Sdim 428341825Sdim /// Following the use-def chain, get the next available source 429276479Sdim /// for the tracked value. 430296417Sdim /// \return A ValueTrackerResult containing a set of registers 431296417Sdim /// and sub registers with tracked values. A ValueTrackerResult with 432296417Sdim /// an empty set of registers means no source was found. 433296417Sdim ValueTrackerResult getNextSource(); 434276479Sdim }; 435212793Sdim 436314564Sdim} // end anonymous namespace 437314564Sdim 438212793Sdimchar PeepholeOptimizer::ID = 0; 439327952Sdim 440234353Sdimchar &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID; 441314564Sdim 442309124SdimINITIALIZE_PASS_BEGIN(PeepholeOptimizer, DEBUG_TYPE, 443333715Sdim "Peephole Optimizations", false, false) 444218893SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 445321369SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 446309124SdimINITIALIZE_PASS_END(PeepholeOptimizer, DEBUG_TYPE, 447333715Sdim "Peephole Optimizations", false, false) 448212793Sdim 449296417Sdim/// If instruction is a copy-like instruction, i.e. it reads a single register 450296417Sdim/// and writes a single register and it does not modify the source, and if the 451296417Sdim/// source value is preserved as a sub-register of the result, then replace all 452296417Sdim/// reachable uses of the source with the subreg of the result. 453234353Sdim/// 454212793Sdim/// Do not generate an EXTRACT that is used only in a debug use, as this changes 455212793Sdim/// the code. Since this code does not currently share EXTRACTs, just ignore all 456212793Sdim/// debug uses. 457212793Sdimbool PeepholeOptimizer:: 458333715SdimoptimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB, 459280031Sdim SmallPtrSetImpl<MachineInstr*> &LocalMIs) { 460212793Sdim unsigned SrcReg, DstReg, SubIdx; 461333715Sdim if (!TII->isCoalescableExtInstr(MI, SrcReg, DstReg, SubIdx)) 462212793Sdim return false; 463234353Sdim 464360784Sdim if (Register::isPhysicalRegister(DstReg) || 465360784Sdim Register::isPhysicalRegister(SrcReg)) 466212793Sdim return false; 467212793Sdim 468239462Sdim if (MRI->hasOneNonDBGUse(SrcReg)) 469212793Sdim // No other uses. 470212793Sdim return false; 471212793Sdim 472239462Sdim // Ensure DstReg can get a register class that actually supports 473239462Sdim // sub-registers. Don't change the class until we commit. 474239462Sdim const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg); 475280031Sdim DstRC = TRI->getSubClassWithSubReg(DstRC, SubIdx); 476239462Sdim if (!DstRC) 477239462Sdim return false; 478239462Sdim 479239462Sdim // The ext instr may be operating on a sub-register of SrcReg as well. 480239462Sdim // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit 481239462Sdim // register. 482239462Sdim // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of 483239462Sdim // SrcReg:SubIdx should be replaced. 484280031Sdim bool UseSrcSubIdx = 485280031Sdim TRI->getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != nullptr; 486239462Sdim 487212793Sdim // The source has other uses. See if we can replace the other uses with use of 488212793Sdim // the result of the extension. 489212793Sdim SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs; 490276479Sdim for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg)) 491276479Sdim ReachedBBs.insert(UI.getParent()); 492212793Sdim 493212793Sdim // Uses that are in the same BB of uses of the result of the instruction. 494212793Sdim SmallVector<MachineOperand*, 8> Uses; 495212793Sdim 496212793Sdim // Uses that the result of the instruction can reach. 497212793Sdim SmallVector<MachineOperand*, 8> ExtendedUses; 498212793Sdim 499212793Sdim bool ExtendLife = true; 500276479Sdim for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) { 501276479Sdim MachineInstr *UseMI = UseMO.getParent(); 502333715Sdim if (UseMI == &MI) 503212793Sdim continue; 504212793Sdim 505212793Sdim if (UseMI->isPHI()) { 506212793Sdim ExtendLife = false; 507212793Sdim continue; 508212793Sdim } 509212793Sdim 510239462Sdim // Only accept uses of SrcReg:SubIdx. 511239462Sdim if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx) 512239462Sdim continue; 513239462Sdim 514212793Sdim // It's an error to translate this: 515212793Sdim // 516212793Sdim // %reg1025 = <sext> %reg1024 517212793Sdim // ... 518212793Sdim // %reg1026 = SUBREG_TO_REG 0, %reg1024, 4 519212793Sdim // 520212793Sdim // into this: 521212793Sdim // 522212793Sdim // %reg1025 = <sext> %reg1024 523212793Sdim // ... 524212793Sdim // %reg1027 = COPY %reg1025:4 525212793Sdim // %reg1026 = SUBREG_TO_REG 0, %reg1027, 4 526212793Sdim // 527212793Sdim // The problem here is that SUBREG_TO_REG is there to assert that an 528212793Sdim // implicit zext occurs. It doesn't insert a zext instruction. If we allow 529212793Sdim // the COPY here, it will give us the value after the <sext>, not the 530212793Sdim // original value of %reg1024 before <sext>. 531212793Sdim if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG) 532212793Sdim continue; 533212793Sdim 534212793Sdim MachineBasicBlock *UseMBB = UseMI->getParent(); 535333715Sdim if (UseMBB == &MBB) { 536212793Sdim // Local uses that come after the extension. 537212793Sdim if (!LocalMIs.count(UseMI)) 538212793Sdim Uses.push_back(&UseMO); 539212793Sdim } else if (ReachedBBs.count(UseMBB)) { 540212793Sdim // Non-local uses where the result of the extension is used. Always 541212793Sdim // replace these unless it's a PHI. 542212793Sdim Uses.push_back(&UseMO); 543333715Sdim } else if (Aggressive && DT->dominates(&MBB, UseMBB)) { 544212793Sdim // We may want to extend the live range of the extension result in order 545212793Sdim // to replace these uses. 546212793Sdim ExtendedUses.push_back(&UseMO); 547212793Sdim } else { 548212793Sdim // Both will be live out of the def MBB anyway. Don't extend live range of 549212793Sdim // the extension result. 550212793Sdim ExtendLife = false; 551212793Sdim break; 552212793Sdim } 553212793Sdim } 554212793Sdim 555212793Sdim if (ExtendLife && !ExtendedUses.empty()) 556212793Sdim // Extend the liveness of the extension result. 557288943Sdim Uses.append(ExtendedUses.begin(), ExtendedUses.end()); 558212793Sdim 559212793Sdim // Now replace all uses. 560212793Sdim bool Changed = false; 561212793Sdim if (!Uses.empty()) { 562212793Sdim SmallPtrSet<MachineBasicBlock*, 4> PHIBBs; 563212793Sdim 564212793Sdim // Look for PHI uses of the extended result, we don't want to extend the 565212793Sdim // liveness of a PHI input. It breaks all kinds of assumptions down 566212793Sdim // stream. A PHI use is expected to be the kill of its source values. 567276479Sdim for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg)) 568276479Sdim if (UI.isPHI()) 569276479Sdim PHIBBs.insert(UI.getParent()); 570212793Sdim 571212793Sdim const TargetRegisterClass *RC = MRI->getRegClass(SrcReg); 572212793Sdim for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 573212793Sdim MachineOperand *UseMO = Uses[i]; 574212793Sdim MachineInstr *UseMI = UseMO->getParent(); 575212793Sdim MachineBasicBlock *UseMBB = UseMI->getParent(); 576212793Sdim if (PHIBBs.count(UseMBB)) 577212793Sdim continue; 578212793Sdim 579234353Sdim // About to add uses of DstReg, clear DstReg's kill flags. 580239462Sdim if (!Changed) { 581234353Sdim MRI->clearKillFlags(DstReg); 582239462Sdim MRI->constrainRegClass(DstReg, DstRC); 583239462Sdim } 584234353Sdim 585360784Sdim Register NewVR = MRI->createVirtualRegister(RC); 586239462Sdim MachineInstr *Copy = BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(), 587239462Sdim TII->get(TargetOpcode::COPY), NewVR) 588212793Sdim .addReg(DstReg, 0, SubIdx); 589239462Sdim // SubIdx applies to both SrcReg and DstReg when UseSrcSubIdx is set. 590239462Sdim if (UseSrcSubIdx) { 591239462Sdim Copy->getOperand(0).setSubReg(SubIdx); 592239462Sdim Copy->getOperand(0).setIsUndef(); 593239462Sdim } 594212793Sdim UseMO->setReg(NewVR); 595212793Sdim ++NumReuse; 596212793Sdim Changed = true; 597212793Sdim } 598212793Sdim } 599212793Sdim 600212793Sdim return Changed; 601212793Sdim} 602212793Sdim 603296417Sdim/// If the instruction is a compare and the previous instruction it's comparing 604296417Sdim/// against already sets (or could be modified to set) the same flag as the 605296417Sdim/// compare, then we can remove the comparison and use the flag from the 606296417Sdim/// previous instruction. 607333715Sdimbool PeepholeOptimizer::optimizeCmpInstr(MachineInstr &MI) { 608212793Sdim // If this instruction is a comparison against zero and isn't comparing a 609212793Sdim // physical register, we can try to optimize it. 610239462Sdim unsigned SrcReg, SrcReg2; 611218893Sdim int CmpMask, CmpValue; 612333715Sdim if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) || 613360784Sdim Register::isPhysicalRegister(SrcReg) || 614360784Sdim (SrcReg2 != 0 && Register::isPhysicalRegister(SrcReg2))) 615212793Sdim return false; 616212793Sdim 617218893Sdim // Attempt to optimize the comparison instruction. 618333715Sdim if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) { 619221345Sdim ++NumCmps; 620212793Sdim return true; 621212793Sdim } 622212793Sdim 623212793Sdim return false; 624212793Sdim} 625212793Sdim 626239462Sdim/// Optimize a select instruction. 627333715Sdimbool PeepholeOptimizer::optimizeSelect(MachineInstr &MI, 628280031Sdim SmallPtrSetImpl<MachineInstr *> &LocalMIs) { 629239462Sdim unsigned TrueOp = 0; 630239462Sdim unsigned FalseOp = 0; 631239462Sdim bool Optimizable = false; 632239462Sdim SmallVector<MachineOperand, 4> Cond; 633333715Sdim if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable)) 634239462Sdim return false; 635239462Sdim if (!Optimizable) 636239462Sdim return false; 637333715Sdim if (!TII->optimizeSelect(MI, LocalMIs)) 638239462Sdim return false; 639333715Sdim MI.eraseFromParent(); 640239462Sdim ++NumSelects; 641239462Sdim return true; 642239462Sdim} 643239462Sdim 644333715Sdim/// Check if a simpler conditional branch can be generated. 645333715Sdimbool PeepholeOptimizer::optimizeCondBranch(MachineInstr &MI) { 646333715Sdim return TII->optimizeCondBranch(MI); 647280031Sdim} 648280031Sdim 649341825Sdim/// Try to find the next source that share the same register file 650280031Sdim/// for the value defined by \p Reg and \p SubReg. 651296417Sdim/// When true is returned, the \p RewriteMap can be used by the client to 652296417Sdim/// retrieve all Def -> Use along the way up to the next source. Any found 653296417Sdim/// Use that is not itself a key for another entry, is the next source to 654296417Sdim/// use. During the search for the next source, multiple sources can be found 655296417Sdim/// given multiple incoming sources of a PHI instruction. In this case, we 656296417Sdim/// look in each PHI source for the next source; all found next sources must 657296417Sdim/// share the same register file as \p Reg and \p SubReg. The client should 658296417Sdim/// then be capable to rewrite all intermediate PHIs to get the next source. 659280031Sdim/// \return False if no alternative sources are available. True otherwise. 660333715Sdimbool PeepholeOptimizer::findNextSource(RegSubRegPair RegSubReg, 661296417Sdim RewriteMapTy &RewriteMap) { 662280031Sdim // Do not try to find a new source for a physical register. 663280031Sdim // So far we do not have any motivating example for doing that. 664280031Sdim // Thus, instead of maintaining untested code, we will revisit that if 665280031Sdim // that changes at some point. 666333715Sdim unsigned Reg = RegSubReg.Reg; 667360784Sdim if (Register::isPhysicalRegister(Reg)) 668261991Sdim return false; 669280031Sdim const TargetRegisterClass *DefRC = MRI->getRegClass(Reg); 670261991Sdim 671333715Sdim SmallVector<RegSubRegPair, 4> SrcToLook; 672333715Sdim RegSubRegPair CurSrcPair = RegSubReg; 673296417Sdim SrcToLook.push_back(CurSrcPair); 674261991Sdim 675296417Sdim unsigned PHICount = 0; 676333715Sdim do { 677333715Sdim CurSrcPair = SrcToLook.pop_back_val(); 678296417Sdim // As explained above, do not handle physical registers 679360784Sdim if (Register::isPhysicalRegister(CurSrcPair.Reg)) 680296417Sdim return false; 681261991Sdim 682333715Sdim ValueTracker ValTracker(CurSrcPair.Reg, CurSrcPair.SubReg, *MRI, TII); 683261991Sdim 684328381Sdim // Follow the chain of copies until we find a more suitable source, a phi 685328381Sdim // or have to abort. 686328381Sdim while (true) { 687328381Sdim ValueTrackerResult Res = ValTracker.getNextSource(); 688328381Sdim // Abort at the end of a chain (without finding a suitable source). 689296417Sdim if (!Res.isValid()) 690328381Sdim return false; 691261991Sdim 692296417Sdim // Insert the Def -> Use entry for the recently found source. 693296417Sdim ValueTrackerResult CurSrcRes = RewriteMap.lookup(CurSrcPair); 694296417Sdim if (CurSrcRes.isValid()) { 695296417Sdim assert(CurSrcRes == Res && "ValueTrackerResult found must match"); 696296417Sdim // An existent entry with multiple sources is a PHI cycle we must avoid. 697296417Sdim // Otherwise it's an entry with a valid next source we already found. 698296417Sdim if (CurSrcRes.getNumSources() > 1) { 699341825Sdim LLVM_DEBUG(dbgs() 700341825Sdim << "findNextSource: found PHI cycle, aborting...\n"); 701296417Sdim return false; 702296417Sdim } 703296417Sdim break; 704296417Sdim } 705296417Sdim RewriteMap.insert(std::make_pair(CurSrcPair, Res)); 706261991Sdim 707296417Sdim // ValueTrackerResult usually have one source unless it's the result from 708296417Sdim // a PHI instruction. Add the found PHI edges to be looked up further. 709296417Sdim unsigned NumSrcs = Res.getNumSources(); 710296417Sdim if (NumSrcs > 1) { 711296417Sdim PHICount++; 712333715Sdim if (PHICount >= RewritePHILimit) { 713341825Sdim LLVM_DEBUG(dbgs() << "findNextSource: PHI limit reached\n"); 714333715Sdim return false; 715333715Sdim } 716333715Sdim 717296417Sdim for (unsigned i = 0; i < NumSrcs; ++i) 718333715Sdim SrcToLook.push_back(Res.getSrc(i)); 719296417Sdim break; 720296417Sdim } 721296417Sdim 722333715Sdim CurSrcPair = Res.getSrc(0); 723296417Sdim // Do not extend the live-ranges of physical registers as they add 724296417Sdim // constraints to the register allocator. Moreover, if we want to extend 725296417Sdim // the live-range of a physical register, unlike SSA virtual register, 726296417Sdim // we will have to check that they aren't redefine before the related use. 727360784Sdim if (Register::isPhysicalRegister(CurSrcPair.Reg)) 728296417Sdim return false; 729296417Sdim 730328381Sdim // Keep following the chain if the value isn't any better yet. 731296417Sdim const TargetRegisterClass *SrcRC = MRI->getRegClass(CurSrcPair.Reg); 732333715Sdim if (!TRI->shouldRewriteCopySrc(DefRC, RegSubReg.SubReg, SrcRC, 733333715Sdim CurSrcPair.SubReg)) 734328381Sdim continue; 735296417Sdim 736328381Sdim // We currently cannot deal with subreg operands on PHI instructions 737328381Sdim // (see insertPHI()). 738328381Sdim if (PHICount > 0 && CurSrcPair.SubReg != 0) 739328381Sdim continue; 740296417Sdim 741328381Sdim // We found a suitable source, and are done with this chain. 742328381Sdim break; 743328381Sdim } 744333715Sdim } while (!SrcToLook.empty()); 745296417Sdim 746296417Sdim // If we did not find a more suitable source, there is nothing to optimize. 747296417Sdim return CurSrcPair.Reg != Reg; 748280031Sdim} 749261991Sdim 750341825Sdim/// Insert a PHI instruction with incoming edges \p SrcRegs that are 751296417Sdim/// guaranteed to have the same register class. This is necessary whenever we 752296417Sdim/// successfully traverse a PHI instruction and find suitable sources coming 753296417Sdim/// from its edges. By inserting a new PHI, we provide a rewritten PHI def 754296417Sdim/// suitable to be used in a new COPY instruction. 755333715Sdimstatic MachineInstr & 756333715SdiminsertPHI(MachineRegisterInfo &MRI, const TargetInstrInfo &TII, 757333715Sdim const SmallVectorImpl<RegSubRegPair> &SrcRegs, 758333715Sdim MachineInstr &OrigPHI) { 759296417Sdim assert(!SrcRegs.empty() && "No sources to create a PHI instruction?"); 760296417Sdim 761333715Sdim const TargetRegisterClass *NewRC = MRI.getRegClass(SrcRegs[0].Reg); 762328381Sdim // NewRC is only correct if no subregisters are involved. findNextSource() 763328381Sdim // should have rejected those cases already. 764328381Sdim assert(SrcRegs[0].SubReg == 0 && "should not have subreg operand"); 765360784Sdim Register NewVR = MRI.createVirtualRegister(NewRC); 766333715Sdim MachineBasicBlock *MBB = OrigPHI.getParent(); 767333715Sdim MachineInstrBuilder MIB = BuildMI(*MBB, &OrigPHI, OrigPHI.getDebugLoc(), 768333715Sdim TII.get(TargetOpcode::PHI), NewVR); 769296417Sdim 770296417Sdim unsigned MBBOpIdx = 2; 771333715Sdim for (const RegSubRegPair &RegPair : SrcRegs) { 772296417Sdim MIB.addReg(RegPair.Reg, 0, RegPair.SubReg); 773333715Sdim MIB.addMBB(OrigPHI.getOperand(MBBOpIdx).getMBB()); 774296417Sdim // Since we're extended the lifetime of RegPair.Reg, clear the 775296417Sdim // kill flags to account for that and make RegPair.Reg reaches 776296417Sdim // the new PHI. 777333715Sdim MRI.clearKillFlags(RegPair.Reg); 778296417Sdim MBBOpIdx += 2; 779296417Sdim } 780296417Sdim 781333715Sdim return *MIB; 782296417Sdim} 783296417Sdim 784280031Sdimnamespace { 785314564Sdim 786333715Sdim/// Interface to query instructions amenable to copy rewriting. 787333715Sdimclass Rewriter { 788280031Sdimprotected: 789280031Sdim MachineInstr &CopyLike; 790333715Sdim unsigned CurrentSrcIdx = 0; ///< The index of the source being rewritten. 791280031Sdimpublic: 792333715Sdim Rewriter(MachineInstr &CopyLike) : CopyLike(CopyLike) {} 793333715Sdim virtual ~Rewriter() {} 794280031Sdim 795341825Sdim /// Get the next rewritable source (SrcReg, SrcSubReg) and 796333715Sdim /// the related value that it affects (DstReg, DstSubReg). 797280031Sdim /// A source is considered rewritable if its register class and the 798333715Sdim /// register class of the related DstReg may not be register 799280031Sdim /// coalescer friendly. In other words, given a copy-like instruction 800280031Sdim /// not all the arguments may be returned at rewritable source, since 801280031Sdim /// some arguments are none to be register coalescer friendly. 802280031Sdim /// 803280031Sdim /// Each call of this method moves the current source to the next 804280031Sdim /// rewritable source. 805280031Sdim /// For instance, let CopyLike be the instruction to rewrite. 806280031Sdim /// CopyLike has one definition and one source: 807280031Sdim /// dst.dstSubIdx = CopyLike src.srcSubIdx. 808280031Sdim /// 809280031Sdim /// The first call will give the first rewritable source, i.e., 810280031Sdim /// the only source this instruction has: 811280031Sdim /// (SrcReg, SrcSubReg) = (src, srcSubIdx). 812280031Sdim /// This source defines the whole definition, i.e., 813333715Sdim /// (DstReg, DstSubReg) = (dst, dstSubIdx). 814280031Sdim /// 815296417Sdim /// The second and subsequent calls will return false, as there is only one 816280031Sdim /// rewritable source. 817280031Sdim /// 818280031Sdim /// \return True if a rewritable source has been found, false otherwise. 819280031Sdim /// The output arguments are valid if and only if true is returned. 820333715Sdim virtual bool getNextRewritableSource(RegSubRegPair &Src, 821333715Sdim RegSubRegPair &Dst) = 0; 822333715Sdim 823333715Sdim /// Rewrite the current source with \p NewReg and \p NewSubReg if possible. 824333715Sdim /// \return True if the rewriting was possible, false otherwise. 825333715Sdim virtual bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) = 0; 826333715Sdim}; 827333715Sdim 828333715Sdim/// Rewriter for COPY instructions. 829333715Sdimclass CopyRewriter : public Rewriter { 830333715Sdimpublic: 831333715Sdim CopyRewriter(MachineInstr &MI) : Rewriter(MI) { 832333715Sdim assert(MI.isCopy() && "Expected copy instruction"); 833333715Sdim } 834333715Sdim virtual ~CopyRewriter() = default; 835333715Sdim 836333715Sdim bool getNextRewritableSource(RegSubRegPair &Src, 837333715Sdim RegSubRegPair &Dst) override { 838333715Sdim // CurrentSrcIdx > 0 means this function has already been called. 839333715Sdim if (CurrentSrcIdx > 0) 840280031Sdim return false; 841280031Sdim // This is the first call to getNextRewritableSource. 842280031Sdim // Move the CurrentSrcIdx to remember that we made that call. 843280031Sdim CurrentSrcIdx = 1; 844280031Sdim // The rewritable source is the argument. 845280031Sdim const MachineOperand &MOSrc = CopyLike.getOperand(1); 846333715Sdim Src = RegSubRegPair(MOSrc.getReg(), MOSrc.getSubReg()); 847280031Sdim // What we track are the alternative sources of the definition. 848280031Sdim const MachineOperand &MODef = CopyLike.getOperand(0); 849333715Sdim Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); 850280031Sdim return true; 851280031Sdim } 852280031Sdim 853333715Sdim bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override { 854333715Sdim if (CurrentSrcIdx != 1) 855280031Sdim return false; 856280031Sdim MachineOperand &MOSrc = CopyLike.getOperand(CurrentSrcIdx); 857280031Sdim MOSrc.setReg(NewReg); 858280031Sdim MOSrc.setSubReg(NewSubReg); 859280031Sdim return true; 860280031Sdim } 861280031Sdim}; 862280031Sdim 863341825Sdim/// Helper class to rewrite uncoalescable copy like instructions 864296417Sdim/// into new COPY (coalescable friendly) instructions. 865333715Sdimclass UncoalescableRewriter : public Rewriter { 866333715Sdim unsigned NumDefs; ///< Number of defs in the bitcast. 867327952Sdim 868296417Sdimpublic: 869333715Sdim UncoalescableRewriter(MachineInstr &MI) : Rewriter(MI) { 870296417Sdim NumDefs = MI.getDesc().getNumDefs(); 871296417Sdim } 872296417Sdim 873333715Sdim /// \see See Rewriter::getNextRewritableSource() 874296417Sdim /// All such sources need to be considered rewritable in order to 875296417Sdim /// rewrite a uncoalescable copy-like instruction. This method return 876296417Sdim /// each definition that must be checked if rewritable. 877333715Sdim bool getNextRewritableSource(RegSubRegPair &Src, 878333715Sdim RegSubRegPair &Dst) override { 879296417Sdim // Find the next non-dead definition and continue from there. 880296417Sdim if (CurrentSrcIdx == NumDefs) 881296417Sdim return false; 882296417Sdim 883296417Sdim while (CopyLike.getOperand(CurrentSrcIdx).isDead()) { 884296417Sdim ++CurrentSrcIdx; 885296417Sdim if (CurrentSrcIdx == NumDefs) 886296417Sdim return false; 887296417Sdim } 888296417Sdim 889296417Sdim // What we track are the alternative sources of the definition. 890333715Sdim Src = RegSubRegPair(0, 0); 891296417Sdim const MachineOperand &MODef = CopyLike.getOperand(CurrentSrcIdx); 892333715Sdim Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); 893296417Sdim 894296417Sdim CurrentSrcIdx++; 895296417Sdim return true; 896296417Sdim } 897296417Sdim 898333715Sdim bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override { 899333715Sdim return false; 900296417Sdim } 901296417Sdim}; 902296417Sdim 903333715Sdim/// Specialized rewriter for INSERT_SUBREG instruction. 904333715Sdimclass InsertSubregRewriter : public Rewriter { 905280031Sdimpublic: 906333715Sdim InsertSubregRewriter(MachineInstr &MI) : Rewriter(MI) { 907280031Sdim assert(MI.isInsertSubreg() && "Invalid instruction"); 908280031Sdim } 909280031Sdim 910333715Sdim /// \see See Rewriter::getNextRewritableSource() 911280031Sdim /// Here CopyLike has the following form: 912280031Sdim /// dst = INSERT_SUBREG Src1, Src2.src2SubIdx, subIdx. 913280031Sdim /// Src1 has the same register class has dst, hence, there is 914280031Sdim /// nothing to rewrite. 915280031Sdim /// Src2.src2SubIdx, may not be register coalescer friendly. 916280031Sdim /// Therefore, the first call to this method returns: 917280031Sdim /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx). 918333715Sdim /// (DstReg, DstSubReg) = (dst, subIdx). 919280031Sdim /// 920280031Sdim /// Subsequence calls will return false. 921333715Sdim bool getNextRewritableSource(RegSubRegPair &Src, 922333715Sdim RegSubRegPair &Dst) override { 923280031Sdim // If we already get the only source we can rewrite, return false. 924280031Sdim if (CurrentSrcIdx == 2) 925280031Sdim return false; 926280031Sdim // We are looking at v2 = INSERT_SUBREG v0, v1, sub0. 927280031Sdim CurrentSrcIdx = 2; 928280031Sdim const MachineOperand &MOInsertedReg = CopyLike.getOperand(2); 929333715Sdim Src = RegSubRegPair(MOInsertedReg.getReg(), MOInsertedReg.getSubReg()); 930280031Sdim const MachineOperand &MODef = CopyLike.getOperand(0); 931280031Sdim 932280031Sdim // We want to track something that is compatible with the 933280031Sdim // partial definition. 934280031Sdim if (MODef.getSubReg()) 935296417Sdim // Bail if we have to compose sub-register indices. 936280031Sdim return false; 937333715Sdim Dst = RegSubRegPair(MODef.getReg(), 938333715Sdim (unsigned)CopyLike.getOperand(3).getImm()); 939280031Sdim return true; 940280031Sdim } 941314564Sdim 942280031Sdim bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override { 943280031Sdim if (CurrentSrcIdx != 2) 944280031Sdim return false; 945280031Sdim // We are rewriting the inserted reg. 946280031Sdim MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx); 947280031Sdim MO.setReg(NewReg); 948280031Sdim MO.setSubReg(NewSubReg); 949280031Sdim return true; 950280031Sdim } 951280031Sdim}; 952280031Sdim 953333715Sdim/// Specialized rewriter for EXTRACT_SUBREG instruction. 954333715Sdimclass ExtractSubregRewriter : public Rewriter { 955280031Sdim const TargetInstrInfo &TII; 956280031Sdim 957280031Sdimpublic: 958280031Sdim ExtractSubregRewriter(MachineInstr &MI, const TargetInstrInfo &TII) 959333715Sdim : Rewriter(MI), TII(TII) { 960280031Sdim assert(MI.isExtractSubreg() && "Invalid instruction"); 961280031Sdim } 962280031Sdim 963333715Sdim /// \see Rewriter::getNextRewritableSource() 964280031Sdim /// Here CopyLike has the following form: 965280031Sdim /// dst.dstSubIdx = EXTRACT_SUBREG Src, subIdx. 966280031Sdim /// There is only one rewritable source: Src.subIdx, 967280031Sdim /// which defines dst.dstSubIdx. 968333715Sdim bool getNextRewritableSource(RegSubRegPair &Src, 969333715Sdim RegSubRegPair &Dst) override { 970280031Sdim // If we already get the only source we can rewrite, return false. 971280031Sdim if (CurrentSrcIdx == 1) 972280031Sdim return false; 973280031Sdim // We are looking at v1 = EXTRACT_SUBREG v0, sub0. 974280031Sdim CurrentSrcIdx = 1; 975280031Sdim const MachineOperand &MOExtractedReg = CopyLike.getOperand(1); 976296417Sdim // If we have to compose sub-register indices, bail out. 977280031Sdim if (MOExtractedReg.getSubReg()) 978280031Sdim return false; 979280031Sdim 980333715Sdim Src = RegSubRegPair(MOExtractedReg.getReg(), 981333715Sdim CopyLike.getOperand(2).getImm()); 982280031Sdim 983280031Sdim // We want to track something that is compatible with the definition. 984280031Sdim const MachineOperand &MODef = CopyLike.getOperand(0); 985333715Sdim Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); 986280031Sdim return true; 987280031Sdim } 988280031Sdim 989280031Sdim bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override { 990280031Sdim // The only source we can rewrite is the input register. 991280031Sdim if (CurrentSrcIdx != 1) 992280031Sdim return false; 993280031Sdim 994280031Sdim CopyLike.getOperand(CurrentSrcIdx).setReg(NewReg); 995280031Sdim 996280031Sdim // If we find a source that does not require to extract something, 997280031Sdim // rewrite the operation with a copy. 998280031Sdim if (!NewSubReg) { 999280031Sdim // Move the current index to an invalid position. 1000280031Sdim // We do not want another call to this method to be able 1001280031Sdim // to do any change. 1002280031Sdim CurrentSrcIdx = -1; 1003280031Sdim // Rewrite the operation as a COPY. 1004280031Sdim // Get rid of the sub-register index. 1005280031Sdim CopyLike.RemoveOperand(2); 1006280031Sdim // Morph the operation into a COPY. 1007280031Sdim CopyLike.setDesc(TII.get(TargetOpcode::COPY)); 1008280031Sdim return true; 1009280031Sdim } 1010280031Sdim CopyLike.getOperand(CurrentSrcIdx + 1).setImm(NewSubReg); 1011280031Sdim return true; 1012280031Sdim } 1013280031Sdim}; 1014280031Sdim 1015333715Sdim/// Specialized rewriter for REG_SEQUENCE instruction. 1016333715Sdimclass RegSequenceRewriter : public Rewriter { 1017280031Sdimpublic: 1018333715Sdim RegSequenceRewriter(MachineInstr &MI) : Rewriter(MI) { 1019280031Sdim assert(MI.isRegSequence() && "Invalid instruction"); 1020280031Sdim } 1021280031Sdim 1022333715Sdim /// \see Rewriter::getNextRewritableSource() 1023280031Sdim /// Here CopyLike has the following form: 1024280031Sdim /// dst = REG_SEQUENCE Src1.src1SubIdx, subIdx1, Src2.src2SubIdx, subIdx2. 1025280031Sdim /// Each call will return a different source, walking all the available 1026280031Sdim /// source. 1027280031Sdim /// 1028280031Sdim /// The first call returns: 1029280031Sdim /// (SrcReg, SrcSubReg) = (Src1, src1SubIdx). 1030333715Sdim /// (DstReg, DstSubReg) = (dst, subIdx1). 1031280031Sdim /// 1032280031Sdim /// The second call returns: 1033280031Sdim /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx). 1034333715Sdim /// (DstReg, DstSubReg) = (dst, subIdx2). 1035280031Sdim /// 1036280031Sdim /// And so on, until all the sources have been traversed, then 1037280031Sdim /// it returns false. 1038333715Sdim bool getNextRewritableSource(RegSubRegPair &Src, 1039333715Sdim RegSubRegPair &Dst) override { 1040280031Sdim // We are looking at v0 = REG_SEQUENCE v1, sub1, v2, sub2, etc. 1041280031Sdim 1042280031Sdim // If this is the first call, move to the first argument. 1043280031Sdim if (CurrentSrcIdx == 0) { 1044280031Sdim CurrentSrcIdx = 1; 1045280031Sdim } else { 1046280031Sdim // Otherwise, move to the next argument and check that it is valid. 1047280031Sdim CurrentSrcIdx += 2; 1048280031Sdim if (CurrentSrcIdx >= CopyLike.getNumOperands()) 1049280031Sdim return false; 1050280031Sdim } 1051280031Sdim const MachineOperand &MOInsertedReg = CopyLike.getOperand(CurrentSrcIdx); 1052333715Sdim Src.Reg = MOInsertedReg.getReg(); 1053296417Sdim // If we have to compose sub-register indices, bail out. 1054333715Sdim if ((Src.SubReg = MOInsertedReg.getSubReg())) 1055280031Sdim return false; 1056280031Sdim 1057280031Sdim // We want to track something that is compatible with the related 1058280031Sdim // partial definition. 1059333715Sdim Dst.SubReg = CopyLike.getOperand(CurrentSrcIdx + 1).getImm(); 1060280031Sdim 1061280031Sdim const MachineOperand &MODef = CopyLike.getOperand(0); 1062333715Sdim Dst.Reg = MODef.getReg(); 1063296417Sdim // If we have to compose sub-registers, bail. 1064280031Sdim return MODef.getSubReg() == 0; 1065280031Sdim } 1066280031Sdim 1067280031Sdim bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override { 1068280031Sdim // We cannot rewrite out of bound operands. 1069280031Sdim // Moreover, rewritable sources are at odd positions. 1070280031Sdim if ((CurrentSrcIdx & 1) != 1 || CurrentSrcIdx > CopyLike.getNumOperands()) 1071280031Sdim return false; 1072280031Sdim 1073280031Sdim MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx); 1074280031Sdim MO.setReg(NewReg); 1075280031Sdim MO.setSubReg(NewSubReg); 1076280031Sdim return true; 1077280031Sdim } 1078280031Sdim}; 1079280031Sdim 1080327952Sdim} // end anonymous namespace 1081314564Sdim 1082333715Sdim/// Get the appropriated Rewriter for \p MI. 1083333715Sdim/// \return A pointer to a dynamically allocated Rewriter or nullptr if no 1084333715Sdim/// rewriter works for \p MI. 1085333715Sdimstatic Rewriter *getCopyRewriter(MachineInstr &MI, const TargetInstrInfo &TII) { 1086296417Sdim // Handle uncoalescable copy-like instructions. 1087333715Sdim if (MI.isBitcast() || MI.isRegSequenceLike() || MI.isInsertSubregLike() || 1088333715Sdim MI.isExtractSubregLike()) 1089333715Sdim return new UncoalescableRewriter(MI); 1090296417Sdim 1091280031Sdim switch (MI.getOpcode()) { 1092280031Sdim default: 1093280031Sdim return nullptr; 1094280031Sdim case TargetOpcode::COPY: 1095280031Sdim return new CopyRewriter(MI); 1096280031Sdim case TargetOpcode::INSERT_SUBREG: 1097280031Sdim return new InsertSubregRewriter(MI); 1098280031Sdim case TargetOpcode::EXTRACT_SUBREG: 1099280031Sdim return new ExtractSubregRewriter(MI, TII); 1100280031Sdim case TargetOpcode::REG_SEQUENCE: 1101280031Sdim return new RegSequenceRewriter(MI); 1102280031Sdim } 1103280031Sdim} 1104280031Sdim 1105341825Sdim/// Given a \p Def.Reg and Def.SubReg pair, use \p RewriteMap to find 1106333715Sdim/// the new source to use for rewrite. If \p HandleMultipleSources is true and 1107333715Sdim/// multiple sources for a given \p Def are found along the way, we found a 1108333715Sdim/// PHI instructions that needs to be rewritten. 1109333715Sdim/// TODO: HandleMultipleSources should be removed once we test PHI handling 1110333715Sdim/// with coalescable copies. 1111333715Sdimstatic RegSubRegPair 1112333715SdimgetNewSource(MachineRegisterInfo *MRI, const TargetInstrInfo *TII, 1113333715Sdim RegSubRegPair Def, 1114333715Sdim const PeepholeOptimizer::RewriteMapTy &RewriteMap, 1115333715Sdim bool HandleMultipleSources = true) { 1116333715Sdim RegSubRegPair LookupSrc(Def.Reg, Def.SubReg); 1117333715Sdim while (true) { 1118333715Sdim ValueTrackerResult Res = RewriteMap.lookup(LookupSrc); 1119333715Sdim // If there are no entries on the map, LookupSrc is the new source. 1120333715Sdim if (!Res.isValid()) 1121333715Sdim return LookupSrc; 1122333715Sdim 1123333715Sdim // There's only one source for this definition, keep searching... 1124333715Sdim unsigned NumSrcs = Res.getNumSources(); 1125333715Sdim if (NumSrcs == 1) { 1126333715Sdim LookupSrc.Reg = Res.getSrcReg(0); 1127333715Sdim LookupSrc.SubReg = Res.getSrcSubReg(0); 1128333715Sdim continue; 1129333715Sdim } 1130333715Sdim 1131333715Sdim // TODO: Remove once multiple srcs w/ coalescable copies are supported. 1132333715Sdim if (!HandleMultipleSources) 1133333715Sdim break; 1134333715Sdim 1135333715Sdim // Multiple sources, recurse into each source to find a new source 1136333715Sdim // for it. Then, rewrite the PHI accordingly to its new edges. 1137333715Sdim SmallVector<RegSubRegPair, 4> NewPHISrcs; 1138333715Sdim for (unsigned i = 0; i < NumSrcs; ++i) { 1139333715Sdim RegSubRegPair PHISrc(Res.getSrcReg(i), Res.getSrcSubReg(i)); 1140333715Sdim NewPHISrcs.push_back( 1141333715Sdim getNewSource(MRI, TII, PHISrc, RewriteMap, HandleMultipleSources)); 1142333715Sdim } 1143333715Sdim 1144333715Sdim // Build the new PHI node and return its def register as the new source. 1145333715Sdim MachineInstr &OrigPHI = const_cast<MachineInstr &>(*Res.getInst()); 1146333715Sdim MachineInstr &NewPHI = insertPHI(*MRI, *TII, NewPHISrcs, OrigPHI); 1147341825Sdim LLVM_DEBUG(dbgs() << "-- getNewSource\n"); 1148341825Sdim LLVM_DEBUG(dbgs() << " Replacing: " << OrigPHI); 1149341825Sdim LLVM_DEBUG(dbgs() << " With: " << NewPHI); 1150333715Sdim const MachineOperand &MODef = NewPHI.getOperand(0); 1151333715Sdim return RegSubRegPair(MODef.getReg(), MODef.getSubReg()); 1152333715Sdim } 1153333715Sdim 1154333715Sdim return RegSubRegPair(0, 0); 1155333715Sdim} 1156333715Sdim 1157333715Sdim/// Optimize generic copy instructions to avoid cross register bank copy. 1158333715Sdim/// The optimization looks through a chain of copies and tries to find a source 1159333715Sdim/// that has a compatible register class. 1160333715Sdim/// Two register classes are considered to be compatible if they share the same 1161333715Sdim/// register bank. 1162280031Sdim/// New copies issued by this optimization are register allocator 1163280031Sdim/// friendly. This optimization does not remove any copy as it may 1164296417Sdim/// overconstrain the register allocator, but replaces some operands 1165280031Sdim/// when possible. 1166280031Sdim/// \pre isCoalescableCopy(*MI) is true. 1167280031Sdim/// \return True, when \p MI has been rewritten. False otherwise. 1168333715Sdimbool PeepholeOptimizer::optimizeCoalescableCopy(MachineInstr &MI) { 1169333715Sdim assert(isCoalescableCopy(MI) && "Invalid argument"); 1170333715Sdim assert(MI.getDesc().getNumDefs() == 1 && 1171280031Sdim "Coalescer can understand multiple defs?!"); 1172333715Sdim const MachineOperand &MODef = MI.getOperand(0); 1173280031Sdim // Do not rewrite physical definitions. 1174360784Sdim if (Register::isPhysicalRegister(MODef.getReg())) 1175280031Sdim return false; 1176280031Sdim 1177280031Sdim bool Changed = false; 1178280031Sdim // Get the right rewriter for the current copy. 1179333715Sdim std::unique_ptr<Rewriter> CpyRewriter(getCopyRewriter(MI, *TII)); 1180296417Sdim // If none exists, bail out. 1181280031Sdim if (!CpyRewriter) 1182280031Sdim return false; 1183280031Sdim // Rewrite each rewritable source. 1184333715Sdim RegSubRegPair Src; 1185333715Sdim RegSubRegPair TrackPair; 1186333715Sdim while (CpyRewriter->getNextRewritableSource(Src, TrackPair)) { 1187296417Sdim // Keep track of PHI nodes and its incoming edges when looking for sources. 1188296417Sdim RewriteMapTy RewriteMap; 1189296417Sdim // Try to find a more suitable source. If we failed to do so, or get the 1190296417Sdim // actual source, move to the next source. 1191333715Sdim if (!findNextSource(TrackPair, RewriteMap)) 1192280031Sdim continue; 1193296417Sdim 1194296417Sdim // Get the new source to rewrite. TODO: Only enable handling of multiple 1195296417Sdim // sources (PHIs) once we have a motivating example and testcases for it. 1196333715Sdim RegSubRegPair NewSrc = getNewSource(MRI, TII, TrackPair, RewriteMap, 1197333715Sdim /*HandleMultipleSources=*/false); 1198333715Sdim if (Src.Reg == NewSrc.Reg || NewSrc.Reg == 0) 1199296417Sdim continue; 1200296417Sdim 1201280031Sdim // Rewrite source. 1202296417Sdim if (CpyRewriter->RewriteCurrentSource(NewSrc.Reg, NewSrc.SubReg)) { 1203280031Sdim // We may have extended the live-range of NewSrc, account for that. 1204296417Sdim MRI->clearKillFlags(NewSrc.Reg); 1205280031Sdim Changed = true; 1206280031Sdim } 1207280031Sdim } 1208280031Sdim // TODO: We could have a clean-up method to tidy the instruction. 1209280031Sdim // E.g., v0 = INSERT_SUBREG v1, v1.sub0, sub0 1210280031Sdim // => v0 = COPY v1 1211280031Sdim // Currently we haven't seen motivating example for that and we 1212280031Sdim // want to avoid untested code. 1213288943Sdim NumRewrittenCopies += Changed; 1214280031Sdim return Changed; 1215280031Sdim} 1216280031Sdim 1217341825Sdim/// Rewrite the source found through \p Def, by using the \p RewriteMap 1218333715Sdim/// and create a new COPY instruction. More info about RewriteMap in 1219333715Sdim/// PeepholeOptimizer::findNextSource. Right now this is only used to handle 1220333715Sdim/// Uncoalescable copies, since they are copy like instructions that aren't 1221333715Sdim/// recognized by the register allocator. 1222333715SdimMachineInstr & 1223333715SdimPeepholeOptimizer::rewriteSource(MachineInstr &CopyLike, 1224333715Sdim RegSubRegPair Def, RewriteMapTy &RewriteMap) { 1225360784Sdim assert(!Register::isPhysicalRegister(Def.Reg) && 1226333715Sdim "We do not rewrite physical registers"); 1227333715Sdim 1228333715Sdim // Find the new source to use in the COPY rewrite. 1229333715Sdim RegSubRegPair NewSrc = getNewSource(MRI, TII, Def, RewriteMap); 1230333715Sdim 1231333715Sdim // Insert the COPY. 1232333715Sdim const TargetRegisterClass *DefRC = MRI->getRegClass(Def.Reg); 1233360784Sdim Register NewVReg = MRI->createVirtualRegister(DefRC); 1234333715Sdim 1235333715Sdim MachineInstr *NewCopy = 1236333715Sdim BuildMI(*CopyLike.getParent(), &CopyLike, CopyLike.getDebugLoc(), 1237333715Sdim TII->get(TargetOpcode::COPY), NewVReg) 1238333715Sdim .addReg(NewSrc.Reg, 0, NewSrc.SubReg); 1239333715Sdim 1240333715Sdim if (Def.SubReg) { 1241333715Sdim NewCopy->getOperand(0).setSubReg(Def.SubReg); 1242333715Sdim NewCopy->getOperand(0).setIsUndef(); 1243333715Sdim } 1244333715Sdim 1245341825Sdim LLVM_DEBUG(dbgs() << "-- RewriteSource\n"); 1246341825Sdim LLVM_DEBUG(dbgs() << " Replacing: " << CopyLike); 1247341825Sdim LLVM_DEBUG(dbgs() << " With: " << *NewCopy); 1248333715Sdim MRI->replaceRegWith(Def.Reg, NewVReg); 1249333715Sdim MRI->clearKillFlags(NewVReg); 1250333715Sdim 1251333715Sdim // We extended the lifetime of NewSrc.Reg, clear the kill flags to 1252333715Sdim // account for that. 1253333715Sdim MRI->clearKillFlags(NewSrc.Reg); 1254333715Sdim 1255333715Sdim return *NewCopy; 1256333715Sdim} 1257333715Sdim 1258341825Sdim/// Optimize copy-like instructions to create 1259280031Sdim/// register coalescer friendly instruction. 1260280031Sdim/// The optimization tries to kill-off the \p MI by looking 1261280031Sdim/// through a chain of copies to find a source that has a compatible 1262280031Sdim/// register class. 1263280031Sdim/// If such a source is found, it replace \p MI by a generic COPY 1264280031Sdim/// operation. 1265280031Sdim/// \pre isUncoalescableCopy(*MI) is true. 1266280031Sdim/// \return True, when \p MI has been optimized. In that case, \p MI has 1267280031Sdim/// been removed from its parent. 1268280031Sdim/// All COPY instructions created, are inserted in \p LocalMIs. 1269280031Sdimbool PeepholeOptimizer::optimizeUncoalescableCopy( 1270333715Sdim MachineInstr &MI, SmallPtrSetImpl<MachineInstr *> &LocalMIs) { 1271333715Sdim assert(isUncoalescableCopy(MI) && "Invalid argument"); 1272333715Sdim UncoalescableRewriter CpyRewriter(MI); 1273280031Sdim 1274296417Sdim // Rewrite each rewritable source by generating new COPYs. This works 1275296417Sdim // differently from optimizeCoalescableCopy since it first makes sure that all 1276296417Sdim // definitions can be rewritten. 1277296417Sdim RewriteMapTy RewriteMap; 1278333715Sdim RegSubRegPair Src; 1279333715Sdim RegSubRegPair Def; 1280333715Sdim SmallVector<RegSubRegPair, 4> RewritePairs; 1281333715Sdim while (CpyRewriter.getNextRewritableSource(Src, Def)) { 1282280031Sdim // If a physical register is here, this is probably for a good reason. 1283280031Sdim // Do not rewrite that. 1284360784Sdim if (Register::isPhysicalRegister(Def.Reg)) 1285280031Sdim return false; 1286280031Sdim 1287280031Sdim // If we do not know how to rewrite this definition, there is no point 1288280031Sdim // in trying to kill this instruction. 1289333715Sdim if (!findNextSource(Def, RewriteMap)) 1290280031Sdim return false; 1291296417Sdim 1292296417Sdim RewritePairs.push_back(Def); 1293280031Sdim } 1294296417Sdim 1295280031Sdim // The change is possible for all defs, do it. 1296333715Sdim for (const RegSubRegPair &Def : RewritePairs) { 1297280031Sdim // Rewrite the "copy" in a way the register coalescer understands. 1298333715Sdim MachineInstr &NewCopy = rewriteSource(MI, Def, RewriteMap); 1299333715Sdim LocalMIs.insert(&NewCopy); 1300280031Sdim } 1301296417Sdim 1302280031Sdim // MI is now dead. 1303333715Sdim MI.eraseFromParent(); 1304280031Sdim ++NumUncoalescableCopies; 1305261991Sdim return true; 1306261991Sdim} 1307261991Sdim 1308296417Sdim/// Check whether MI is a candidate for folding into a later instruction. 1309296417Sdim/// We only fold loads to virtual registers and the virtual register defined 1310353358Sdim/// has a single user. 1311276479Sdimbool PeepholeOptimizer::isLoadFoldable( 1312333715Sdim MachineInstr &MI, SmallSet<unsigned, 16> &FoldAsLoadDefCandidates) { 1313333715Sdim if (!MI.canFoldAsLoad() || !MI.mayLoad()) 1314239462Sdim return false; 1315333715Sdim const MCInstrDesc &MCID = MI.getDesc(); 1316239462Sdim if (MCID.getNumDefs() != 1) 1317239462Sdim return false; 1318239462Sdim 1319360784Sdim Register Reg = MI.getOperand(0).getReg(); 1320353358Sdim // To reduce compilation time, we check MRI->hasOneNonDBGUser when inserting 1321239462Sdim // loads. It should be checked when processing uses of the load, since 1322239462Sdim // uses can be removed during peephole. 1323360784Sdim if (!MI.getOperand(0).getSubReg() && Register::isVirtualRegister(Reg) && 1324353358Sdim MRI->hasOneNonDBGUser(Reg)) { 1325276479Sdim FoldAsLoadDefCandidates.insert(Reg); 1326239462Sdim return true; 1327239462Sdim } 1328239462Sdim return false; 1329239462Sdim} 1330239462Sdim 1331296417Sdimbool PeepholeOptimizer::isMoveImmediate( 1332333715Sdim MachineInstr &MI, SmallSet<unsigned, 4> &ImmDefRegs, 1333296417Sdim DenseMap<unsigned, MachineInstr *> &ImmDefMIs) { 1334333715Sdim const MCInstrDesc &MCID = MI.getDesc(); 1335333715Sdim if (!MI.isMoveImmediate()) 1336218893Sdim return false; 1337224145Sdim if (MCID.getNumDefs() != 1) 1338218893Sdim return false; 1339360784Sdim Register Reg = MI.getOperand(0).getReg(); 1340360784Sdim if (Register::isVirtualRegister(Reg)) { 1341333715Sdim ImmDefMIs.insert(std::make_pair(Reg, &MI)); 1342218893Sdim ImmDefRegs.insert(Reg); 1343218893Sdim return true; 1344218893Sdim } 1345234353Sdim 1346218893Sdim return false; 1347218893Sdim} 1348218893Sdim 1349296417Sdim/// Try folding register operands that are defined by move immediate 1350296417Sdim/// instructions, i.e. a trivial constant folding optimization, if 1351218893Sdim/// and only if the def and use are in the same BB. 1352333715Sdimbool PeepholeOptimizer::foldImmediate(MachineInstr &MI, 1353333715Sdim SmallSet<unsigned, 4> &ImmDefRegs, 1354296417Sdim DenseMap<unsigned, MachineInstr *> &ImmDefMIs) { 1355333715Sdim for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) { 1356333715Sdim MachineOperand &MO = MI.getOperand(i); 1357218893Sdim if (!MO.isReg() || MO.isDef()) 1358218893Sdim continue; 1359296417Sdim // Ignore dead implicit defs. 1360296417Sdim if (MO.isImplicit() && MO.isDead()) 1361296417Sdim continue; 1362360784Sdim Register Reg = MO.getReg(); 1363360784Sdim if (!Register::isVirtualRegister(Reg)) 1364218893Sdim continue; 1365218893Sdim if (ImmDefRegs.count(Reg) == 0) 1366218893Sdim continue; 1367218893Sdim DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg); 1368296417Sdim assert(II != ImmDefMIs.end() && "couldn't find immediate definition"); 1369333715Sdim if (TII->FoldImmediate(MI, *II->second, Reg, MRI)) { 1370218893Sdim ++NumImmFold; 1371218893Sdim return true; 1372218893Sdim } 1373218893Sdim } 1374218893Sdim return false; 1375218893Sdim} 1376218893Sdim 1377296417Sdim// FIXME: This is very simple and misses some cases which should be handled when 1378296417Sdim// motivating examples are found. 1379296417Sdim// 1380296417Sdim// The copy rewriting logic should look at uses as well as defs and be able to 1381296417Sdim// eliminate copies across blocks. 1382296417Sdim// 1383296417Sdim// Later copies that are subregister extracts will also not be eliminated since 1384296417Sdim// only the first copy is considered. 1385296417Sdim// 1386296417Sdim// e.g. 1387327952Sdim// %1 = COPY %0 1388327952Sdim// %2 = COPY %0:sub1 1389296417Sdim// 1390327952Sdim// Should replace %2 uses with %1:sub1 1391333715Sdimbool PeepholeOptimizer::foldRedundantCopy(MachineInstr &MI, 1392333715Sdim SmallSet<unsigned, 4> &CopySrcRegs, 1393296417Sdim DenseMap<unsigned, MachineInstr *> &CopyMIs) { 1394333715Sdim assert(MI.isCopy() && "expected a COPY machine instruction"); 1395296417Sdim 1396360784Sdim Register SrcReg = MI.getOperand(1).getReg(); 1397360784Sdim if (!Register::isVirtualRegister(SrcReg)) 1398296417Sdim return false; 1399296417Sdim 1400360784Sdim Register DstReg = MI.getOperand(0).getReg(); 1401360784Sdim if (!Register::isVirtualRegister(DstReg)) 1402296417Sdim return false; 1403296417Sdim 1404296417Sdim if (CopySrcRegs.insert(SrcReg).second) { 1405296417Sdim // First copy of this reg seen. 1406333715Sdim CopyMIs.insert(std::make_pair(SrcReg, &MI)); 1407296417Sdim return false; 1408296417Sdim } 1409296417Sdim 1410296417Sdim MachineInstr *PrevCopy = CopyMIs.find(SrcReg)->second; 1411296417Sdim 1412333715Sdim unsigned SrcSubReg = MI.getOperand(1).getSubReg(); 1413296417Sdim unsigned PrevSrcSubReg = PrevCopy->getOperand(1).getSubReg(); 1414296417Sdim 1415296417Sdim // Can't replace different subregister extracts. 1416296417Sdim if (SrcSubReg != PrevSrcSubReg) 1417296417Sdim return false; 1418296417Sdim 1419360784Sdim Register PrevDstReg = PrevCopy->getOperand(0).getReg(); 1420296417Sdim 1421296417Sdim // Only replace if the copy register class is the same. 1422296417Sdim // 1423296417Sdim // TODO: If we have multiple copies to different register classes, we may want 1424296417Sdim // to track multiple copies of the same source register. 1425296417Sdim if (MRI->getRegClass(DstReg) != MRI->getRegClass(PrevDstReg)) 1426296417Sdim return false; 1427296417Sdim 1428296417Sdim MRI->replaceRegWith(DstReg, PrevDstReg); 1429296417Sdim 1430296417Sdim // Lifetime of the previous copy has been extended. 1431296417Sdim MRI->clearKillFlags(PrevDstReg); 1432296417Sdim return true; 1433296417Sdim} 1434296417Sdim 1435296417Sdimbool PeepholeOptimizer::isNAPhysCopy(unsigned Reg) { 1436360784Sdim return Register::isPhysicalRegister(Reg) && !MRI->isAllocatable(Reg); 1437296417Sdim} 1438296417Sdim 1439296417Sdimbool PeepholeOptimizer::foldRedundantNAPhysCopy( 1440333715Sdim MachineInstr &MI, DenseMap<unsigned, MachineInstr *> &NAPhysToVirtMIs) { 1441333715Sdim assert(MI.isCopy() && "expected a COPY machine instruction"); 1442296417Sdim 1443296417Sdim if (DisableNAPhysCopyOpt) 1444296417Sdim return false; 1445296417Sdim 1446360784Sdim Register DstReg = MI.getOperand(0).getReg(); 1447360784Sdim Register SrcReg = MI.getOperand(1).getReg(); 1448360784Sdim if (isNAPhysCopy(SrcReg) && Register::isVirtualRegister(DstReg)) { 1449327952Sdim // %vreg = COPY %physreg 1450296417Sdim // Avoid using a datastructure which can track multiple live non-allocatable 1451296417Sdim // phys->virt copies since LLVM doesn't seem to do this. 1452333715Sdim NAPhysToVirtMIs.insert({SrcReg, &MI}); 1453296417Sdim return false; 1454296417Sdim } 1455296417Sdim 1456360784Sdim if (!(Register::isVirtualRegister(SrcReg) && isNAPhysCopy(DstReg))) 1457296417Sdim return false; 1458296417Sdim 1459327952Sdim // %physreg = COPY %vreg 1460296417Sdim auto PrevCopy = NAPhysToVirtMIs.find(DstReg); 1461296417Sdim if (PrevCopy == NAPhysToVirtMIs.end()) { 1462296417Sdim // We can't remove the copy: there was an intervening clobber of the 1463296417Sdim // non-allocatable physical register after the copy to virtual. 1464341825Sdim LLVM_DEBUG(dbgs() << "NAPhysCopy: intervening clobber forbids erasing " 1465341825Sdim << MI); 1466296417Sdim return false; 1467296417Sdim } 1468296417Sdim 1469360784Sdim Register PrevDstReg = PrevCopy->second->getOperand(0).getReg(); 1470296417Sdim if (PrevDstReg == SrcReg) { 1471296417Sdim // Remove the virt->phys copy: we saw the virtual register definition, and 1472296417Sdim // the non-allocatable physical register's state hasn't changed since then. 1473341825Sdim LLVM_DEBUG(dbgs() << "NAPhysCopy: erasing " << MI); 1474296417Sdim ++NumNAPhysCopies; 1475296417Sdim return true; 1476296417Sdim } 1477296417Sdim 1478296417Sdim // Potential missed optimization opportunity: we saw a different virtual 1479296417Sdim // register get a copy of the non-allocatable physical register, and we only 1480296417Sdim // track one such copy. Avoid getting confused by this new non-allocatable 1481296417Sdim // physical register definition, and remove it from the tracked copies. 1482341825Sdim LLVM_DEBUG(dbgs() << "NAPhysCopy: missed opportunity " << MI); 1483296417Sdim NAPhysToVirtMIs.erase(PrevCopy); 1484296417Sdim return false; 1485296417Sdim} 1486296417Sdim 1487321369Sdim/// \bried Returns true if \p MO is a virtual register operand. 1488321369Sdimstatic bool isVirtualRegisterOperand(MachineOperand &MO) { 1489321369Sdim if (!MO.isReg()) 1490321369Sdim return false; 1491360784Sdim return Register::isVirtualRegister(MO.getReg()); 1492321369Sdim} 1493321369Sdim 1494321369Sdimbool PeepholeOptimizer::findTargetRecurrence( 1495321369Sdim unsigned Reg, const SmallSet<unsigned, 2> &TargetRegs, 1496321369Sdim RecurrenceCycle &RC) { 1497321369Sdim // Recurrence found if Reg is in TargetRegs. 1498321369Sdim if (TargetRegs.count(Reg)) 1499321369Sdim return true; 1500321369Sdim 1501321369Sdim // TODO: Curerntly, we only allow the last instruction of the recurrence 1502321369Sdim // cycle (the instruction that feeds the PHI instruction) to have more than 1503321369Sdim // one uses to guarantee that commuting operands does not tie registers 1504321369Sdim // with overlapping live range. Once we have actual live range info of 1505321369Sdim // each register, this constraint can be relaxed. 1506321369Sdim if (!MRI->hasOneNonDBGUse(Reg)) 1507321369Sdim return false; 1508321369Sdim 1509321369Sdim // Give up if the reccurrence chain length is longer than the limit. 1510321369Sdim if (RC.size() >= MaxRecurrenceChain) 1511321369Sdim return false; 1512321369Sdim 1513321369Sdim MachineInstr &MI = *(MRI->use_instr_nodbg_begin(Reg)); 1514321369Sdim unsigned Idx = MI.findRegisterUseOperandIdx(Reg); 1515321369Sdim 1516321369Sdim // Only interested in recurrences whose instructions have only one def, which 1517321369Sdim // is a virtual register. 1518321369Sdim if (MI.getDesc().getNumDefs() != 1) 1519321369Sdim return false; 1520321369Sdim 1521321369Sdim MachineOperand &DefOp = MI.getOperand(0); 1522321369Sdim if (!isVirtualRegisterOperand(DefOp)) 1523321369Sdim return false; 1524321369Sdim 1525321369Sdim // Check if def operand of MI is tied to any use operand. We are only 1526321369Sdim // interested in the case that all the instructions in the recurrence chain 1527321369Sdim // have there def operand tied with one of the use operand. 1528321369Sdim unsigned TiedUseIdx; 1529321369Sdim if (!MI.isRegTiedToUseOperand(0, &TiedUseIdx)) 1530321369Sdim return false; 1531321369Sdim 1532321369Sdim if (Idx == TiedUseIdx) { 1533321369Sdim RC.push_back(RecurrenceInstr(&MI)); 1534321369Sdim return findTargetRecurrence(DefOp.getReg(), TargetRegs, RC); 1535321369Sdim } else { 1536321369Sdim // If Idx is not TiedUseIdx, check if Idx is commutable with TiedUseIdx. 1537321369Sdim unsigned CommIdx = TargetInstrInfo::CommuteAnyOperandIndex; 1538321369Sdim if (TII->findCommutedOpIndices(MI, Idx, CommIdx) && CommIdx == TiedUseIdx) { 1539321369Sdim RC.push_back(RecurrenceInstr(&MI, Idx, CommIdx)); 1540321369Sdim return findTargetRecurrence(DefOp.getReg(), TargetRegs, RC); 1541321369Sdim } 1542321369Sdim } 1543321369Sdim 1544321369Sdim return false; 1545321369Sdim} 1546321369Sdim 1547333715Sdim/// Phi instructions will eventually be lowered to copy instructions. 1548333715Sdim/// If phi is in a loop header, a recurrence may formulated around the source 1549333715Sdim/// and destination of the phi. For such case commuting operands of the 1550333715Sdim/// instructions in the recurrence may enable coalescing of the copy instruction 1551333715Sdim/// generated from the phi. For example, if there is a recurrence of 1552321369Sdim/// 1553321369Sdim/// LoopHeader: 1554327952Sdim/// %1 = phi(%0, %100) 1555321369Sdim/// LoopLatch: 1556327952Sdim/// %0<def, tied1> = ADD %2<def, tied0>, %1 1557321369Sdim/// 1558327952Sdim/// , the fact that %0 and %2 are in the same tied operands set makes 1559321369Sdim/// the coalescing of copy instruction generated from the phi in 1560327952Sdim/// LoopHeader(i.e. %1 = COPY %0) impossible, because %1 and 1561327952Sdim/// %2 have overlapping live range. This introduces additional move 1562327952Sdim/// instruction to the final assembly. However, if we commute %2 and 1563327952Sdim/// %1 of ADD instruction, the redundant move instruction can be 1564321369Sdim/// avoided. 1565321369Sdimbool PeepholeOptimizer::optimizeRecurrence(MachineInstr &PHI) { 1566321369Sdim SmallSet<unsigned, 2> TargetRegs; 1567321369Sdim for (unsigned Idx = 1; Idx < PHI.getNumOperands(); Idx += 2) { 1568321369Sdim MachineOperand &MO = PHI.getOperand(Idx); 1569321369Sdim assert(isVirtualRegisterOperand(MO) && "Invalid PHI instruction"); 1570321369Sdim TargetRegs.insert(MO.getReg()); 1571321369Sdim } 1572321369Sdim 1573321369Sdim bool Changed = false; 1574321369Sdim RecurrenceCycle RC; 1575321369Sdim if (findTargetRecurrence(PHI.getOperand(0).getReg(), TargetRegs, RC)) { 1576321369Sdim // Commutes operands of instructions in RC if necessary so that the copy to 1577321369Sdim // be generated from PHI can be coalesced. 1578341825Sdim LLVM_DEBUG(dbgs() << "Optimize recurrence chain from " << PHI); 1579321369Sdim for (auto &RI : RC) { 1580341825Sdim LLVM_DEBUG(dbgs() << "\tInst: " << *(RI.getMI())); 1581321369Sdim auto CP = RI.getCommutePair(); 1582321369Sdim if (CP) { 1583321369Sdim Changed = true; 1584321369Sdim TII->commuteInstruction(*(RI.getMI()), false, (*CP).first, 1585321369Sdim (*CP).second); 1586341825Sdim LLVM_DEBUG(dbgs() << "\t\tCommuted: " << *(RI.getMI())); 1587321369Sdim } 1588321369Sdim } 1589321369Sdim } 1590321369Sdim 1591321369Sdim return Changed; 1592321369Sdim} 1593321369Sdim 1594212793Sdimbool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { 1595327952Sdim if (skipFunction(MF.getFunction())) 1596276479Sdim return false; 1597276479Sdim 1598341825Sdim LLVM_DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n"); 1599341825Sdim LLVM_DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n'); 1600249423Sdim 1601218893Sdim if (DisablePeephole) 1602218893Sdim return false; 1603234353Sdim 1604280031Sdim TII = MF.getSubtarget().getInstrInfo(); 1605280031Sdim TRI = MF.getSubtarget().getRegisterInfo(); 1606212793Sdim MRI = &MF.getRegInfo(); 1607276479Sdim DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : nullptr; 1608321369Sdim MLI = &getAnalysis<MachineLoopInfo>(); 1609212793Sdim 1610212793Sdim bool Changed = false; 1611212793Sdim 1612296417Sdim for (MachineBasicBlock &MBB : MF) { 1613218893Sdim bool SeenMoveImm = false; 1614280031Sdim 1615280031Sdim // During this forward scan, at some point it needs to answer the question 1616280031Sdim // "given a pointer to an MI in the current BB, is it located before or 1617280031Sdim // after the current instruction". 1618280031Sdim // To perform this, the following set keeps track of the MIs already seen 1619280031Sdim // during the scan, if a MI is not in the set, it is assumed to be located 1620280031Sdim // after. Newly created MIs have to be inserted in the set as well. 1621280031Sdim SmallPtrSet<MachineInstr*, 16> LocalMIs; 1622276479Sdim SmallSet<unsigned, 4> ImmDefRegs; 1623276479Sdim DenseMap<unsigned, MachineInstr*> ImmDefMIs; 1624276479Sdim SmallSet<unsigned, 16> FoldAsLoadDefCandidates; 1625212793Sdim 1626296417Sdim // Track when a non-allocatable physical register is copied to a virtual 1627296417Sdim // register so that useless moves can be removed. 1628296417Sdim // 1629327952Sdim // %physreg is the map index; MI is the last valid `%vreg = COPY %physreg` 1630327952Sdim // without any intervening re-definition of %physreg. 1631296417Sdim DenseMap<unsigned, MachineInstr *> NAPhysToVirtMIs; 1632296417Sdim 1633296417Sdim // Set of virtual registers that are copied from. 1634296417Sdim SmallSet<unsigned, 4> CopySrcRegs; 1635296417Sdim DenseMap<unsigned, MachineInstr *> CopySrcMIs; 1636296417Sdim 1637321369Sdim bool IsLoopHeader = MLI->isLoopHeader(&MBB); 1638321369Sdim 1639296417Sdim for (MachineBasicBlock::iterator MII = MBB.begin(), MIE = MBB.end(); 1640296417Sdim MII != MIE; ) { 1641212793Sdim MachineInstr *MI = &*MII; 1642239462Sdim // We may be erasing MI below, increment MII now. 1643239462Sdim ++MII; 1644218893Sdim LocalMIs.insert(MI); 1645212793Sdim 1646341825Sdim // Skip debug instructions. They should not affect this peephole optimization. 1647341825Sdim if (MI->isDebugInstr()) 1648276479Sdim continue; 1649276479Sdim 1650321369Sdim if (MI->isPosition()) 1651218893Sdim continue; 1652296417Sdim 1653321369Sdim if (IsLoopHeader && MI->isPHI()) { 1654321369Sdim if (optimizeRecurrence(*MI)) { 1655321369Sdim Changed = true; 1656321369Sdim continue; 1657321369Sdim } 1658321369Sdim } 1659321369Sdim 1660296417Sdim if (!MI->isCopy()) { 1661333715Sdim for (const MachineOperand &MO : MI->operands()) { 1662296417Sdim // Visit all operands: definitions can be implicit or explicit. 1663333715Sdim if (MO.isReg()) { 1664360784Sdim Register Reg = MO.getReg(); 1665333715Sdim if (MO.isDef() && isNAPhysCopy(Reg)) { 1666296417Sdim const auto &Def = NAPhysToVirtMIs.find(Reg); 1667296417Sdim if (Def != NAPhysToVirtMIs.end()) { 1668296417Sdim // A new definition of the non-allocatable physical register 1669296417Sdim // invalidates previous copies. 1670341825Sdim LLVM_DEBUG(dbgs() 1671341825Sdim << "NAPhysCopy: invalidating because of " << *MI); 1672296417Sdim NAPhysToVirtMIs.erase(Def); 1673296417Sdim } 1674296417Sdim } 1675333715Sdim } else if (MO.isRegMask()) { 1676333715Sdim const uint32_t *RegMask = MO.getRegMask(); 1677296417Sdim for (auto &RegMI : NAPhysToVirtMIs) { 1678296417Sdim unsigned Def = RegMI.first; 1679296417Sdim if (MachineOperand::clobbersPhysReg(RegMask, Def)) { 1680341825Sdim LLVM_DEBUG(dbgs() 1681341825Sdim << "NAPhysCopy: invalidating because of " << *MI); 1682296417Sdim NAPhysToVirtMIs.erase(Def); 1683296417Sdim } 1684296417Sdim } 1685296417Sdim } 1686296417Sdim } 1687218893Sdim } 1688218893Sdim 1689296417Sdim if (MI->isImplicitDef() || MI->isKill()) 1690296417Sdim continue; 1691296417Sdim 1692296417Sdim if (MI->isInlineAsm() || MI->hasUnmodeledSideEffects()) { 1693296417Sdim // Blow away all non-allocatable physical registers knowledge since we 1694296417Sdim // don't know what's correct anymore. 1695296417Sdim // 1696296417Sdim // FIXME: handle explicit asm clobbers. 1697341825Sdim LLVM_DEBUG(dbgs() << "NAPhysCopy: blowing away all info due to " 1698341825Sdim << *MI); 1699296417Sdim NAPhysToVirtMIs.clear(); 1700296417Sdim } 1701296417Sdim 1702280031Sdim if ((isUncoalescableCopy(*MI) && 1703333715Sdim optimizeUncoalescableCopy(*MI, LocalMIs)) || 1704333715Sdim (MI->isCompare() && optimizeCmpInstr(*MI)) || 1705333715Sdim (MI->isSelect() && optimizeSelect(*MI, LocalMIs))) { 1706239462Sdim // MI is deleted. 1707239462Sdim LocalMIs.erase(MI); 1708239462Sdim Changed = true; 1709239462Sdim continue; 1710218893Sdim } 1711218893Sdim 1712333715Sdim if (MI->isConditionalBranch() && optimizeCondBranch(*MI)) { 1713280031Sdim Changed = true; 1714280031Sdim continue; 1715280031Sdim } 1716280031Sdim 1717333715Sdim if (isCoalescableCopy(*MI) && optimizeCoalescableCopy(*MI)) { 1718280031Sdim // MI is just rewritten. 1719280031Sdim Changed = true; 1720280031Sdim continue; 1721280031Sdim } 1722280031Sdim 1723296417Sdim if (MI->isCopy() && 1724333715Sdim (foldRedundantCopy(*MI, CopySrcRegs, CopySrcMIs) || 1725333715Sdim foldRedundantNAPhysCopy(*MI, NAPhysToVirtMIs))) { 1726296417Sdim LocalMIs.erase(MI); 1727296417Sdim MI->eraseFromParent(); 1728296417Sdim Changed = true; 1729296417Sdim continue; 1730296417Sdim } 1731296417Sdim 1732333715Sdim if (isMoveImmediate(*MI, ImmDefRegs, ImmDefMIs)) { 1733218893Sdim SeenMoveImm = true; 1734212793Sdim } else { 1735333715Sdim Changed |= optimizeExtInstr(*MI, MBB, LocalMIs); 1736243830Sdim // optimizeExtInstr might have created new instructions after MI 1737243830Sdim // and before the already incremented MII. Adjust MII so that the 1738243830Sdim // next iteration sees the new instructions. 1739243830Sdim MII = MI; 1740243830Sdim ++MII; 1741218893Sdim if (SeenMoveImm) 1742333715Sdim Changed |= foldImmediate(*MI, ImmDefRegs, ImmDefMIs); 1743212793Sdim } 1744218893Sdim 1745239462Sdim // Check whether MI is a load candidate for folding into a later 1746239462Sdim // instruction. If MI is not a candidate, check whether we can fold an 1747239462Sdim // earlier load into MI. 1748333715Sdim if (!isLoadFoldable(*MI, FoldAsLoadDefCandidates) && 1749276479Sdim !FoldAsLoadDefCandidates.empty()) { 1750314564Sdim 1751314564Sdim // We visit each operand even after successfully folding a previous 1752314564Sdim // one. This allows us to fold multiple loads into a single 1753314564Sdim // instruction. We do assume that optimizeLoadInstr doesn't insert 1754314564Sdim // foldable uses earlier in the argument list. Since we don't restart 1755314564Sdim // iteration, we'd miss such cases. 1756276479Sdim const MCInstrDesc &MIDesc = MI->getDesc(); 1757314564Sdim for (unsigned i = MIDesc.getNumDefs(); i != MI->getNumOperands(); 1758276479Sdim ++i) { 1759276479Sdim const MachineOperand &MOp = MI->getOperand(i); 1760276479Sdim if (!MOp.isReg()) 1761276479Sdim continue; 1762276479Sdim unsigned FoldAsLoadDefReg = MOp.getReg(); 1763276479Sdim if (FoldAsLoadDefCandidates.count(FoldAsLoadDefReg)) { 1764276479Sdim // We need to fold load after optimizeCmpInstr, since 1765276479Sdim // optimizeCmpInstr can enable folding by converting SUB to CMP. 1766276479Sdim // Save FoldAsLoadDefReg because optimizeLoadInstr() resets it and 1767276479Sdim // we need it for markUsesInDebugValueAsUndef(). 1768276479Sdim unsigned FoldedReg = FoldAsLoadDefReg; 1769276479Sdim MachineInstr *DefMI = nullptr; 1770309124Sdim if (MachineInstr *FoldMI = 1771309124Sdim TII->optimizeLoadInstr(*MI, MRI, FoldAsLoadDefReg, DefMI)) { 1772276479Sdim // Update LocalMIs since we replaced MI with FoldMI and deleted 1773276479Sdim // DefMI. 1774341825Sdim LLVM_DEBUG(dbgs() << "Replacing: " << *MI); 1775341825Sdim LLVM_DEBUG(dbgs() << " With: " << *FoldMI); 1776276479Sdim LocalMIs.erase(MI); 1777276479Sdim LocalMIs.erase(DefMI); 1778276479Sdim LocalMIs.insert(FoldMI); 1779353358Sdim if (MI->isCall()) 1780360784Sdim MI->getMF()->moveCallSiteInfo(MI, FoldMI); 1781276479Sdim MI->eraseFromParent(); 1782276479Sdim DefMI->eraseFromParent(); 1783276479Sdim MRI->markUsesInDebugValueAsUndef(FoldedReg); 1784276479Sdim FoldAsLoadDefCandidates.erase(FoldedReg); 1785276479Sdim ++NumLoadFold; 1786321369Sdim 1787314564Sdim // MI is replaced with FoldMI so we can continue trying to fold 1788276479Sdim Changed = true; 1789314564Sdim MI = FoldMI; 1790276479Sdim } 1791276479Sdim } 1792239462Sdim } 1793239462Sdim } 1794321369Sdim 1795314564Sdim // If we run into an instruction we can't fold across, discard 1796314564Sdim // the load candidates. Note: We might be able to fold *into* this 1797314564Sdim // instruction, so this needs to be after the folding logic. 1798314564Sdim if (MI->isLoadFoldBarrier()) { 1799341825Sdim LLVM_DEBUG(dbgs() << "Encountered load fold barrier on " << *MI); 1800314564Sdim FoldAsLoadDefCandidates.clear(); 1801314564Sdim } 1802212793Sdim } 1803212793Sdim } 1804212793Sdim 1805212793Sdim return Changed; 1806212793Sdim} 1807276479Sdim 1808296417SdimValueTrackerResult ValueTracker::getNextSourceFromCopy() { 1809276479Sdim assert(Def->isCopy() && "Invalid definition"); 1810276479Sdim // Copy instruction are supposed to be: Def = Src. 1811276479Sdim // If someone breaks this assumption, bad things will happen everywhere. 1812360784Sdim // There may be implicit uses preventing the copy to be moved across 1813360784Sdim // some target specific register definitions 1814360784Sdim assert(Def->getNumOperands() - Def->getNumImplicitOperands() == 2 && 1815360784Sdim "Invalid number of operands"); 1816360784Sdim assert(!Def->hasImplicitDef() && "Only implicit uses are allowed"); 1817276479Sdim 1818276479Sdim if (Def->getOperand(DefIdx).getSubReg() != DefSubReg) 1819276479Sdim // If we look for a different subreg, it means we want a subreg of src. 1820296417Sdim // Bails as we do not support composing subregs yet. 1821296417Sdim return ValueTrackerResult(); 1822276479Sdim // Otherwise, we want the whole source. 1823280031Sdim const MachineOperand &Src = Def->getOperand(1); 1824335799Sdim if (Src.isUndef()) 1825335799Sdim return ValueTrackerResult(); 1826296417Sdim return ValueTrackerResult(Src.getReg(), Src.getSubReg()); 1827276479Sdim} 1828276479Sdim 1829296417SdimValueTrackerResult ValueTracker::getNextSourceFromBitcast() { 1830276479Sdim assert(Def->isBitcast() && "Invalid definition"); 1831276479Sdim 1832276479Sdim // Bail if there are effects that a plain copy will not expose. 1833353358Sdim if (Def->mayRaiseFPException() || Def->hasUnmodeledSideEffects()) 1834296417Sdim return ValueTrackerResult(); 1835276479Sdim 1836276479Sdim // Bitcasts with more than one def are not supported. 1837276479Sdim if (Def->getDesc().getNumDefs() != 1) 1838296417Sdim return ValueTrackerResult(); 1839314564Sdim const MachineOperand DefOp = Def->getOperand(DefIdx); 1840314564Sdim if (DefOp.getSubReg() != DefSubReg) 1841276479Sdim // If we look for a different subreg, it means we want a subreg of the src. 1842296417Sdim // Bails as we do not support composing subregs yet. 1843296417Sdim return ValueTrackerResult(); 1844276479Sdim 1845280031Sdim unsigned SrcIdx = Def->getNumOperands(); 1846276479Sdim for (unsigned OpIdx = DefIdx + 1, EndOpIdx = SrcIdx; OpIdx != EndOpIdx; 1847276479Sdim ++OpIdx) { 1848276479Sdim const MachineOperand &MO = Def->getOperand(OpIdx); 1849276479Sdim if (!MO.isReg() || !MO.getReg()) 1850276479Sdim continue; 1851296417Sdim // Ignore dead implicit defs. 1852296417Sdim if (MO.isImplicit() && MO.isDead()) 1853296417Sdim continue; 1854276479Sdim assert(!MO.isDef() && "We should have skipped all the definitions by now"); 1855276479Sdim if (SrcIdx != EndOpIdx) 1856276479Sdim // Multiple sources? 1857296417Sdim return ValueTrackerResult(); 1858276479Sdim SrcIdx = OpIdx; 1859276479Sdim } 1860314564Sdim 1861360784Sdim // In some rare case, Def has no input, SrcIdx is out of bound, 1862360784Sdim // getOperand(SrcIdx) will fail below. 1863360784Sdim if (SrcIdx >= Def->getNumOperands()) 1864360784Sdim return ValueTrackerResult(); 1865360784Sdim 1866314564Sdim // Stop when any user of the bitcast is a SUBREG_TO_REG, replacing with a COPY 1867314564Sdim // will break the assumed guarantees for the upper bits. 1868314564Sdim for (const MachineInstr &UseMI : MRI.use_nodbg_instructions(DefOp.getReg())) { 1869314564Sdim if (UseMI.isSubregToReg()) 1870314564Sdim return ValueTrackerResult(); 1871314564Sdim } 1872314564Sdim 1873280031Sdim const MachineOperand &Src = Def->getOperand(SrcIdx); 1874335799Sdim if (Src.isUndef()) 1875335799Sdim return ValueTrackerResult(); 1876296417Sdim return ValueTrackerResult(Src.getReg(), Src.getSubReg()); 1877276479Sdim} 1878276479Sdim 1879296417SdimValueTrackerResult ValueTracker::getNextSourceFromRegSequence() { 1880280031Sdim assert((Def->isRegSequence() || Def->isRegSequenceLike()) && 1881280031Sdim "Invalid definition"); 1882276479Sdim 1883276479Sdim if (Def->getOperand(DefIdx).getSubReg()) 1884296417Sdim // If we are composing subregs, bail out. 1885276479Sdim // The case we are checking is Def.<subreg> = REG_SEQUENCE. 1886276479Sdim // This should almost never happen as the SSA property is tracked at 1887276479Sdim // the register level (as opposed to the subreg level). 1888276479Sdim // I.e., 1889276479Sdim // Def.sub0 = 1890276479Sdim // Def.sub1 = 1891276479Sdim // is a valid SSA representation for Def.sub0 and Def.sub1, but not for 1892276479Sdim // Def. Thus, it must not be generated. 1893276479Sdim // However, some code could theoretically generates a single 1894276479Sdim // Def.sub0 (i.e, not defining the other subregs) and we would 1895276479Sdim // have this case. 1896276479Sdim // If we can ascertain (or force) that this never happens, we could 1897276479Sdim // turn that into an assertion. 1898296417Sdim return ValueTrackerResult(); 1899276479Sdim 1900280031Sdim if (!TII) 1901280031Sdim // We could handle the REG_SEQUENCE here, but we do not want to 1902280031Sdim // duplicate the code from the generic TII. 1903296417Sdim return ValueTrackerResult(); 1904280031Sdim 1905333715Sdim SmallVector<RegSubRegPairAndIdx, 8> RegSeqInputRegs; 1906280031Sdim if (!TII->getRegSequenceInputs(*Def, DefIdx, RegSeqInputRegs)) 1907296417Sdim return ValueTrackerResult(); 1908280031Sdim 1909276479Sdim // We are looking at: 1910276479Sdim // Def = REG_SEQUENCE v0, sub0, v1, sub1, ... 1911276479Sdim // Check if one of the operand defines the subreg we are interested in. 1912333715Sdim for (const RegSubRegPairAndIdx &RegSeqInput : RegSeqInputRegs) { 1913353358Sdim if (RegSeqInput.SubIdx == DefSubReg) 1914296417Sdim return ValueTrackerResult(RegSeqInput.Reg, RegSeqInput.SubReg); 1915276479Sdim } 1916276479Sdim 1917276479Sdim // If the subreg we are tracking is super-defined by another subreg, 1918276479Sdim // we could follow this value. However, this would require to compose 1919276479Sdim // the subreg and we do not do that for now. 1920296417Sdim return ValueTrackerResult(); 1921276479Sdim} 1922276479Sdim 1923296417SdimValueTrackerResult ValueTracker::getNextSourceFromInsertSubreg() { 1924280031Sdim assert((Def->isInsertSubreg() || Def->isInsertSubregLike()) && 1925280031Sdim "Invalid definition"); 1926280031Sdim 1927276479Sdim if (Def->getOperand(DefIdx).getSubReg()) 1928296417Sdim // If we are composing subreg, bail out. 1929276479Sdim // Same remark as getNextSourceFromRegSequence. 1930276479Sdim // I.e., this may be turned into an assert. 1931296417Sdim return ValueTrackerResult(); 1932276479Sdim 1933280031Sdim if (!TII) 1934280031Sdim // We could handle the REG_SEQUENCE here, but we do not want to 1935280031Sdim // duplicate the code from the generic TII. 1936296417Sdim return ValueTrackerResult(); 1937280031Sdim 1938333715Sdim RegSubRegPair BaseReg; 1939333715Sdim RegSubRegPairAndIdx InsertedReg; 1940280031Sdim if (!TII->getInsertSubregInputs(*Def, DefIdx, BaseReg, InsertedReg)) 1941296417Sdim return ValueTrackerResult(); 1942280031Sdim 1943276479Sdim // We are looking at: 1944276479Sdim // Def = INSERT_SUBREG v0, v1, sub1 1945276479Sdim // There are two cases: 1946276479Sdim // 1. DefSubReg == sub1, get v1. 1947276479Sdim // 2. DefSubReg != sub1, the value may be available through v0. 1948276479Sdim 1949280031Sdim // #1 Check if the inserted register matches the required sub index. 1950280031Sdim if (InsertedReg.SubIdx == DefSubReg) { 1951296417Sdim return ValueTrackerResult(InsertedReg.Reg, InsertedReg.SubReg); 1952276479Sdim } 1953276479Sdim // #2 Otherwise, if the sub register we are looking for is not partial 1954276479Sdim // defined by the inserted element, we can look through the main 1955276479Sdim // register (v0). 1956276479Sdim const MachineOperand &MODef = Def->getOperand(DefIdx); 1957276479Sdim // If the result register (Def) and the base register (v0) do not 1958276479Sdim // have the same register class or if we have to compose 1959296417Sdim // subregisters, bail out. 1960280031Sdim if (MRI.getRegClass(MODef.getReg()) != MRI.getRegClass(BaseReg.Reg) || 1961280031Sdim BaseReg.SubReg) 1962296417Sdim return ValueTrackerResult(); 1963276479Sdim 1964280031Sdim // Get the TRI and check if the inserted sub-register overlaps with the 1965280031Sdim // sub-register we are tracking. 1966280031Sdim const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo(); 1967276479Sdim if (!TRI || 1968314564Sdim !(TRI->getSubRegIndexLaneMask(DefSubReg) & 1969314564Sdim TRI->getSubRegIndexLaneMask(InsertedReg.SubIdx)).none()) 1970296417Sdim return ValueTrackerResult(); 1971276479Sdim // At this point, the value is available in v0 via the same subreg 1972276479Sdim // we used for Def. 1973296417Sdim return ValueTrackerResult(BaseReg.Reg, DefSubReg); 1974276479Sdim} 1975276479Sdim 1976296417SdimValueTrackerResult ValueTracker::getNextSourceFromExtractSubreg() { 1977280031Sdim assert((Def->isExtractSubreg() || 1978280031Sdim Def->isExtractSubregLike()) && "Invalid definition"); 1979276479Sdim // We are looking at: 1980276479Sdim // Def = EXTRACT_SUBREG v0, sub0 1981276479Sdim 1982296417Sdim // Bail if we have to compose sub registers. 1983276479Sdim // Indeed, if DefSubReg != 0, we would have to compose it with sub0. 1984276479Sdim if (DefSubReg) 1985296417Sdim return ValueTrackerResult(); 1986276479Sdim 1987280031Sdim if (!TII) 1988280031Sdim // We could handle the EXTRACT_SUBREG here, but we do not want to 1989280031Sdim // duplicate the code from the generic TII. 1990296417Sdim return ValueTrackerResult(); 1991280031Sdim 1992333715Sdim RegSubRegPairAndIdx ExtractSubregInputReg; 1993280031Sdim if (!TII->getExtractSubregInputs(*Def, DefIdx, ExtractSubregInputReg)) 1994296417Sdim return ValueTrackerResult(); 1995280031Sdim 1996296417Sdim // Bail if we have to compose sub registers. 1997276479Sdim // Likewise, if v0.subreg != 0, we would have to compose v0.subreg with sub0. 1998280031Sdim if (ExtractSubregInputReg.SubReg) 1999296417Sdim return ValueTrackerResult(); 2000276479Sdim // Otherwise, the value is available in the v0.sub0. 2001296417Sdim return ValueTrackerResult(ExtractSubregInputReg.Reg, 2002296417Sdim ExtractSubregInputReg.SubIdx); 2003276479Sdim} 2004276479Sdim 2005296417SdimValueTrackerResult ValueTracker::getNextSourceFromSubregToReg() { 2006276479Sdim assert(Def->isSubregToReg() && "Invalid definition"); 2007276479Sdim // We are looking at: 2008276479Sdim // Def = SUBREG_TO_REG Imm, v0, sub0 2009276479Sdim 2010296417Sdim // Bail if we have to compose sub registers. 2011276479Sdim // If DefSubReg != sub0, we would have to check that all the bits 2012276479Sdim // we track are included in sub0 and if yes, we would have to 2013276479Sdim // determine the right subreg in v0. 2014276479Sdim if (DefSubReg != Def->getOperand(3).getImm()) 2015296417Sdim return ValueTrackerResult(); 2016296417Sdim // Bail if we have to compose sub registers. 2017276479Sdim // Likewise, if v0.subreg != 0, we would have to compose it with sub0. 2018276479Sdim if (Def->getOperand(2).getSubReg()) 2019296417Sdim return ValueTrackerResult(); 2020276479Sdim 2021296417Sdim return ValueTrackerResult(Def->getOperand(2).getReg(), 2022296417Sdim Def->getOperand(3).getImm()); 2023276479Sdim} 2024276479Sdim 2025333715Sdim/// Explore each PHI incoming operand and return its sources. 2026296417SdimValueTrackerResult ValueTracker::getNextSourceFromPHI() { 2027296417Sdim assert(Def->isPHI() && "Invalid definition"); 2028296417Sdim ValueTrackerResult Res; 2029296417Sdim 2030296417Sdim // If we look for a different subreg, bail as we do not support composing 2031296417Sdim // subregs yet. 2032296417Sdim if (Def->getOperand(0).getSubReg() != DefSubReg) 2033296417Sdim return ValueTrackerResult(); 2034296417Sdim 2035296417Sdim // Return all register sources for PHI instructions. 2036296417Sdim for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) { 2037333715Sdim const MachineOperand &MO = Def->getOperand(i); 2038296417Sdim assert(MO.isReg() && "Invalid PHI instruction"); 2039335799Sdim // We have no code to deal with undef operands. They shouldn't happen in 2040335799Sdim // normal programs anyway. 2041335799Sdim if (MO.isUndef()) 2042335799Sdim return ValueTrackerResult(); 2043296417Sdim Res.addSource(MO.getReg(), MO.getSubReg()); 2044296417Sdim } 2045296417Sdim 2046296417Sdim return Res; 2047296417Sdim} 2048296417Sdim 2049296417SdimValueTrackerResult ValueTracker::getNextSourceImpl() { 2050276479Sdim assert(Def && "This method needs a valid definition"); 2051276479Sdim 2052309124Sdim assert(((Def->getOperand(DefIdx).isDef() && 2053309124Sdim (DefIdx < Def->getDesc().getNumDefs() || 2054309124Sdim Def->getDesc().isVariadic())) || 2055309124Sdim Def->getOperand(DefIdx).isImplicit()) && 2056309124Sdim "Invalid DefIdx"); 2057276479Sdim if (Def->isCopy()) 2058296417Sdim return getNextSourceFromCopy(); 2059276479Sdim if (Def->isBitcast()) 2060296417Sdim return getNextSourceFromBitcast(); 2061276479Sdim // All the remaining cases involve "complex" instructions. 2062296417Sdim // Bail if we did not ask for the advanced tracking. 2063333715Sdim if (DisableAdvCopyOpt) 2064296417Sdim return ValueTrackerResult(); 2065280031Sdim if (Def->isRegSequence() || Def->isRegSequenceLike()) 2066296417Sdim return getNextSourceFromRegSequence(); 2067280031Sdim if (Def->isInsertSubreg() || Def->isInsertSubregLike()) 2068296417Sdim return getNextSourceFromInsertSubreg(); 2069280031Sdim if (Def->isExtractSubreg() || Def->isExtractSubregLike()) 2070296417Sdim return getNextSourceFromExtractSubreg(); 2071276479Sdim if (Def->isSubregToReg()) 2072296417Sdim return getNextSourceFromSubregToReg(); 2073296417Sdim if (Def->isPHI()) 2074296417Sdim return getNextSourceFromPHI(); 2075296417Sdim return ValueTrackerResult(); 2076276479Sdim} 2077276479Sdim 2078296417SdimValueTrackerResult ValueTracker::getNextSource() { 2079276479Sdim // If we reach a point where we cannot move up in the use-def chain, 2080276479Sdim // there is nothing we can get. 2081276479Sdim if (!Def) 2082296417Sdim return ValueTrackerResult(); 2083276479Sdim 2084296417Sdim ValueTrackerResult Res = getNextSourceImpl(); 2085296417Sdim if (Res.isValid()) { 2086276479Sdim // Update definition, definition index, and subregister for the 2087276479Sdim // next call of getNextSource. 2088276479Sdim // Update the current register. 2089296417Sdim bool OneRegSrc = Res.getNumSources() == 1; 2090296417Sdim if (OneRegSrc) 2091296417Sdim Reg = Res.getSrcReg(0); 2092296417Sdim // Update the result before moving up in the use-def chain 2093296417Sdim // with the instruction containing the last found sources. 2094296417Sdim Res.setInst(Def); 2095296417Sdim 2096276479Sdim // If we can still move up in the use-def chain, move to the next 2097296417Sdim // definition. 2098360784Sdim if (!Register::isPhysicalRegister(Reg) && OneRegSrc) { 2099335799Sdim MachineRegisterInfo::def_iterator DI = MRI.def_begin(Reg); 2100335799Sdim if (DI != MRI.def_end()) { 2101335799Sdim Def = DI->getParent(); 2102335799Sdim DefIdx = DI.getOperandNo(); 2103335799Sdim DefSubReg = Res.getSrcSubReg(0); 2104335799Sdim } else { 2105335799Sdim Def = nullptr; 2106335799Sdim } 2107296417Sdim return Res; 2108276479Sdim } 2109276479Sdim } 2110276479Sdim // If we end up here, this means we will not be able to find another source 2111296417Sdim // for the next iteration. Make sure any new call to getNextSource bails out 2112296417Sdim // early by cutting the use-def chain. 2113276479Sdim Def = nullptr; 2114296417Sdim return Res; 2115276479Sdim} 2116