LLVM 24.0.0git
PeepholeOptimizer.cpp
Go to the documentation of this file.
1//===- PeepholeOptimizer.cpp - Peephole Optimizations ---------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Perform peephole optimizations on the machine code:
10//
11// - Optimize Extensions
12//
13// Optimization of sign / zero extension instructions. It may be extended to
14// handle other instructions with similar properties.
15//
16// On some targets, some instructions, e.g. X86 sign / zero extension, may
17// leave the source value in the lower part of the result. This optimization
18// will replace some uses of the pre-extension value with uses of the
19// sub-register of the results.
20//
21// - Optimize Comparisons
22//
23// Optimization of comparison instructions. For instance, in this code:
24//
25// sub r1, 1
26// cmp r1, 0
27// bz L1
28//
29// If the "sub" instruction all ready sets (or could be modified to set) the
30// same flag that the "cmp" instruction sets and that "bz" uses, then we can
31// eliminate the "cmp" instruction.
32//
33// Another instance, in this code:
34//
35// sub r1, r3 | sub r1, imm
36// cmp r3, r1 or cmp r1, r3 | cmp r1, imm
37// bge L1
38//
39// If the branch instruction can use flag from "sub", then we can replace
40// "sub" with "subs" and eliminate the "cmp" instruction.
41//
42// - Optimize Loads:
43//
44// Loads that can be folded into a later instruction. A load is foldable
45// if it loads to virtual registers and the virtual register defined has
46// a single use.
47//
48// - Optimize Copies and Bitcast (more generally, target specific copies):
49//
50// Rewrite copies and bitcasts to avoid cross register bank copies
51// when possible.
52// E.g., Consider the following example, where capital and lower
53// letters denote different register file:
54// b = copy A <-- cross-bank copy
55// C = copy b <-- cross-bank copy
56// =>
57// b = copy A <-- cross-bank copy
58// C = copy A <-- same-bank copy
59//
60// E.g., for bitcast:
61// b = bitcast A <-- cross-bank copy
62// C = bitcast b <-- cross-bank copy
63// =>
64// b = bitcast A <-- cross-bank copy
65// C = copy A <-- same-bank copy
66//===----------------------------------------------------------------------===//
67
69#include "CodeGenOptions.h"
70#include "llvm/ADT/DenseMap.h"
72#include "llvm/ADT/SmallSet.h"
74#include "llvm/ADT/Statistic.h"
90#include "llvm/MC/LaneBitmask.h"
91#include "llvm/MC/MCInstrDesc.h"
92#include "llvm/Pass.h"
94#include "llvm/Support/Debug.h"
96#include <cassert>
97#include <cstdint>
98#include <utility>
99
100using namespace llvm;
103
104#define DEBUG_TYPE "peephole-opt"
105
106// Optimize Extensions
107static cl::opt<bool> Aggressive("aggressive-ext-opt", cl::Hidden,
108 cl::desc("Aggressive extension optimization"));
109
110STATISTIC(NumReuse, "Number of extension results reused");
111STATISTIC(NumCmps, "Number of compares eliminated");
112STATISTIC(NumImmFold, "Number of move immediate folded");
113STATISTIC(NumLoadFold, "Number of loads folded");
114STATISTIC(NumSelects, "Number of selects optimized");
115STATISTIC(NumUncoalescableCopies, "Number of uncoalescable copies optimized");
116STATISTIC(NumRewrittenCopies, "Number of copies rewritten");
117STATISTIC(NumNAPhysCopies, "Number of non-allocatable physical copies removed");
118
119namespace {
120
121class ValueTrackerResult;
122class RecurrenceInstr;
123
124/// Interface to query instructions amenable to copy rewriting.
125class Rewriter {
126protected:
127 MachineInstr &CopyLike;
128 int CurrentSrcIdx = 0; ///< The index of the source being rewritten.
129public:
130 Rewriter(MachineInstr &CopyLike) : CopyLike(CopyLike) {}
131 virtual ~Rewriter() = default;
132
133 /// Get the next rewritable source (SrcReg, SrcSubReg) and
134 /// the related value that it affects (DstReg, DstSubReg).
135 /// A source is considered rewritable if its register class and the
136 /// register class of the related DstReg may not be register
137 /// coalescer friendly. In other words, given a copy-like instruction
138 /// not all the arguments may be returned at rewritable source, since
139 /// some arguments are none to be register coalescer friendly.
140 ///
141 /// Each call of this method moves the current source to the next
142 /// rewritable source.
143 /// For instance, let CopyLike be the instruction to rewrite.
144 /// CopyLike has one definition and one source:
145 /// dst.dstSubIdx = CopyLike src.srcSubIdx.
146 ///
147 /// The first call will give the first rewritable source, i.e.,
148 /// the only source this instruction has:
149 /// (SrcReg, SrcSubReg) = (src, srcSubIdx).
150 /// This source defines the whole definition, i.e.,
151 /// (DstReg, DstSubReg) = (dst, dstSubIdx).
152 ///
153 /// The second and subsequent calls will return false, as there is only one
154 /// rewritable source.
155 ///
156 /// \return True if a rewritable source has been found, false otherwise.
157 /// The output arguments are valid if and only if true is returned.
158 virtual bool getNextRewritableSource(RegSubRegPair &Src,
159 RegSubRegPair &Dst) = 0;
160
161 /// Rewrite the current source with \p NewReg and \p NewSubReg if possible.
162 /// \return True if the rewriting was possible, false otherwise.
163 virtual bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) = 0;
164};
165
166/// Rewriter for COPY instructions.
167class CopyRewriter : public Rewriter {
168public:
169 CopyRewriter(MachineInstr &MI) : Rewriter(MI) {
170 assert(MI.isCopy() && "Expected copy instruction");
171 }
172 ~CopyRewriter() override = default;
173
174 bool getNextRewritableSource(RegSubRegPair &Src,
175 RegSubRegPair &Dst) override {
176 if (++CurrentSrcIdx > 1)
177 return false;
178
179 // The rewritable source is the argument.
180 const MachineOperand &MOSrc = CopyLike.getOperand(CurrentSrcIdx);
181 Src = RegSubRegPair(MOSrc.getReg(), MOSrc.getSubReg());
182 // What we track are the alternative sources of the definition.
183 const MachineOperand &MODef = CopyLike.getOperand(0);
184 Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg());
185 return true;
186 }
187
188 bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override {
189 MachineOperand &MOSrc = CopyLike.getOperand(CurrentSrcIdx);
190 MOSrc.setReg(NewReg);
191 MOSrc.setSubReg(NewSubReg);
192 return true;
193 }
194};
195
196/// Helper class to rewrite uncoalescable copy like instructions
197/// into new COPY (coalescable friendly) instructions.
198class UncoalescableRewriter : public Rewriter {
199 int NumDefs; ///< Number of defs in the bitcast.
200
201public:
202 UncoalescableRewriter(MachineInstr &MI) : Rewriter(MI) {
203 NumDefs = MI.getDesc().getNumDefs();
204 }
205
206 /// \see See Rewriter::getNextRewritableSource()
207 /// All such sources need to be considered rewritable in order to
208 /// rewrite a uncoalescable copy-like instruction. This method return
209 /// each definition that must be checked if rewritable.
210 bool getNextRewritableSource(RegSubRegPair &Src,
211 RegSubRegPair &Dst) override {
212 // Find the next non-dead definition and continue from there.
213 if (CurrentSrcIdx == NumDefs)
214 return false;
215
216 while (CopyLike.getOperand(CurrentSrcIdx).isDead()) {
217 ++CurrentSrcIdx;
218 if (CurrentSrcIdx == NumDefs)
219 return false;
220 }
221
222 // What we track are the alternative sources of the definition.
223 Src = RegSubRegPair(0, 0);
224 const MachineOperand &MODef = CopyLike.getOperand(CurrentSrcIdx);
225 Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg());
226
227 CurrentSrcIdx++;
228 return true;
229 }
230
231 bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override {
232 return false;
233 }
234};
235
236/// Specialized rewriter for INSERT_SUBREG instruction.
237class InsertSubregRewriter : public Rewriter {
238public:
239 InsertSubregRewriter(MachineInstr &MI) : Rewriter(MI) {
240 assert(MI.isInsertSubreg() && "Invalid instruction");
241 }
242
243 /// \see See Rewriter::getNextRewritableSource()
244 /// Here CopyLike has the following form:
245 /// dst = INSERT_SUBREG Src1, Src2.src2SubIdx, subIdx.
246 /// Src1 has the same register class has dst, hence, there is
247 /// nothing to rewrite.
248 /// Src2.src2SubIdx, may not be register coalescer friendly.
249 /// Therefore, the first call to this method returns:
250 /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx).
251 /// (DstReg, DstSubReg) = (dst, subIdx).
252 ///
253 /// Subsequence calls will return false.
254 bool getNextRewritableSource(RegSubRegPair &Src,
255 RegSubRegPair &Dst) override {
256 // If we already get the only source we can rewrite, return false.
257 if (CurrentSrcIdx == 2)
258 return false;
259 // We are looking at v2 = INSERT_SUBREG v0, v1, sub0.
260 CurrentSrcIdx = 2;
261 const MachineOperand &MOInsertedReg = CopyLike.getOperand(2);
262 Src = RegSubRegPair(MOInsertedReg.getReg(), MOInsertedReg.getSubReg());
263 const MachineOperand &MODef = CopyLike.getOperand(0);
264
265 // We want to track something that is compatible with the
266 // partial definition.
267 if (MODef.getSubReg())
268 // Bail if we have to compose sub-register indices.
269 return false;
270 Dst = RegSubRegPair(MODef.getReg(),
271 (unsigned)CopyLike.getOperand(3).getImm());
272 return true;
273 }
274
275 bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override {
276 if (CurrentSrcIdx != 2)
277 return false;
278 // We are rewriting the inserted reg.
279 MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx);
280 MO.setReg(NewReg);
281 MO.setSubReg(NewSubReg);
282 return true;
283 }
284};
285
286/// Specialized rewriter for EXTRACT_SUBREG instruction.
287class ExtractSubregRewriter : public Rewriter {
288 const TargetInstrInfo &TII;
289
290public:
291 ExtractSubregRewriter(MachineInstr &MI, const TargetInstrInfo &TII)
292 : Rewriter(MI), TII(TII) {
293 assert(MI.isExtractSubreg() && "Invalid instruction");
294 }
295
296 /// \see Rewriter::getNextRewritableSource()
297 /// Here CopyLike has the following form:
298 /// dst.dstSubIdx = EXTRACT_SUBREG Src, subIdx.
299 /// There is only one rewritable source: Src.subIdx,
300 /// which defines dst.dstSubIdx.
301 bool getNextRewritableSource(RegSubRegPair &Src,
302 RegSubRegPair &Dst) override {
303 // If we already get the only source we can rewrite, return false.
304 if (CurrentSrcIdx == 1)
305 return false;
306 // We are looking at v1 = EXTRACT_SUBREG v0, sub0.
307 CurrentSrcIdx = 1;
308 const MachineOperand &MOExtractedReg = CopyLike.getOperand(1);
309 // If we have to compose sub-register indices, bail out.
310 if (MOExtractedReg.getSubReg())
311 return false;
312
313 Src =
314 RegSubRegPair(MOExtractedReg.getReg(), CopyLike.getOperand(2).getImm());
315
316 // We want to track something that is compatible with the definition.
317 const MachineOperand &MODef = CopyLike.getOperand(0);
318 Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg());
319 return true;
320 }
321
322 bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override {
323 // The only source we can rewrite is the input register.
324 if (CurrentSrcIdx != 1)
325 return false;
326
327 CopyLike.getOperand(CurrentSrcIdx).setReg(NewReg);
328
329 // If we find a source that does not require to extract something,
330 // rewrite the operation with a copy.
331 if (!NewSubReg) {
332 // Move the current index to an invalid position.
333 // We do not want another call to this method to be able
334 // to do any change.
335 CurrentSrcIdx = -1;
336 // Rewrite the operation as a COPY.
337 // Get rid of the sub-register index.
338 CopyLike.removeOperand(2);
339 // Morph the operation into a COPY.
340 CopyLike.setDesc(TII.get(TargetOpcode::COPY));
341 return true;
342 }
343 CopyLike.getOperand(CurrentSrcIdx + 1).setImm(NewSubReg);
344 return true;
345 }
346};
347
348/// Specialized rewriter for REG_SEQUENCE instruction.
349class RegSequenceRewriter : public Rewriter {
350public:
351 RegSequenceRewriter(MachineInstr &MI) : Rewriter(MI) {
352 assert(MI.isRegSequence() && "Invalid instruction");
353 CurrentSrcIdx = -1;
354 }
355
356 /// \see Rewriter::getNextRewritableSource()
357 /// Here CopyLike has the following form:
358 /// dst = REG_SEQUENCE Src1.src1SubIdx, subIdx1, Src2.src2SubIdx, subIdx2.
359 /// Each call will return a different source, walking all the available
360 /// source.
361 ///
362 /// The first call returns:
363 /// (SrcReg, SrcSubReg) = (Src1, src1SubIdx).
364 /// (DstReg, DstSubReg) = (dst, subIdx1).
365 ///
366 /// The second call returns:
367 /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx).
368 /// (DstReg, DstSubReg) = (dst, subIdx2).
369 ///
370 /// And so on, until all the sources have been traversed, then
371 /// it returns false.
372 bool getNextRewritableSource(RegSubRegPair &Src,
373 RegSubRegPair &Dst) override {
374 // We are looking at v0 = REG_SEQUENCE v1, sub1, v2, sub2, etc.
375 CurrentSrcIdx += 2;
376 if (static_cast<unsigned>(CurrentSrcIdx) >= CopyLike.getNumOperands())
377 return false;
378
379 const MachineOperand &MOInsertedReg = CopyLike.getOperand(CurrentSrcIdx);
380 Src.Reg = MOInsertedReg.getReg();
381 Src.SubReg = MOInsertedReg.getSubReg();
382
383 // We want to track something that is compatible with the related
384 // partial definition.
385 Dst.SubReg = CopyLike.getOperand(CurrentSrcIdx + 1).getImm();
386
387 const MachineOperand &MODef = CopyLike.getOperand(0);
388 Dst.Reg = MODef.getReg();
389 assert(MODef.getSubReg() == 0 && "cannot have subregister def in SSA");
390 return true;
391 }
392
393 bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override {
394 MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx);
395 MO.setReg(NewReg);
396 MO.setSubReg(NewSubReg);
397 return true;
398 }
399};
400
401class PeepholeOptimizer : private MachineFunction::Delegate {
402 const CodeGenOptions &Opts;
403 const TargetInstrInfo *TII = nullptr;
404 const TargetRegisterInfo *TRI = nullptr;
405 MachineRegisterInfo *MRI = nullptr;
406 MachineDominatorTree *DT = nullptr; // Machine dominator tree
407 MachineLoopInfo *MLI = nullptr;
408
409public:
410 PeepholeOptimizer(const CodeGenOptions &Opts, MachineDominatorTree *DT,
411 MachineLoopInfo *MLI)
412 : Opts(Opts), DT(DT), MLI(MLI) {}
413
414 bool run(MachineFunction &MF);
415 /// Track Def -> Use info used for rewriting copies.
416 using RewriteMapTy = SmallDenseMap<RegSubRegPair, ValueTrackerResult>;
417
418 /// Sequence of instructions that formulate recurrence cycle.
419 using RecurrenceCycle = SmallVector<RecurrenceInstr, 4>;
420
421private:
422 bool optimizeCmpInstr(MachineInstr &MI, MachineFunction &MF,
423 SmallPtrSet<MachineInstr *, 16> &LocalMIs);
424 bool optimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB,
425 SmallPtrSetImpl<MachineInstr *> &LocalMIs);
426 bool optimizeSelect(MachineInstr &MI,
427 SmallPtrSetImpl<MachineInstr *> &LocalMIs);
428 bool optimizeCondBranch(MachineInstr &MI);
429
430 bool optimizeCoalescableCopyImpl(Rewriter &&CpyRewriter);
431 bool optimizeCoalescableCopy(MachineInstr &MI);
432 bool optimizeUncoalescableCopy(MachineInstr &MI,
433 SmallPtrSetImpl<MachineInstr *> &LocalMIs);
434 bool optimizeRecurrence(MachineInstr &PHI);
435 bool findNextSource(const TargetRegisterClass *DefRC, unsigned DefSubReg,
436 RegSubRegPair RegSubReg, RewriteMapTy &RewriteMap);
437 bool isMoveImmediate(MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs,
438 DenseMap<Register, MachineInstr *> &ImmDefMIs);
439 bool foldImmediate(MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs,
440 DenseMap<Register, MachineInstr *> &ImmDefMIs,
441 bool &Deleted);
442
443 /// Finds recurrence cycles, but only ones that formulated around
444 /// a def operand and a use operand that are tied. If there is a use
445 /// operand commutable with the tied use operand, find recurrence cycle
446 /// along that operand as well.
447 bool findTargetRecurrence(Register Reg,
448 const SmallSet<Register, 2> &TargetReg,
449 RecurrenceCycle &RC);
450
451 /// If copy instruction \p MI is a virtual register copy or a copy of a
452 /// constant physical register to a virtual register, track it in the
453 /// set CopySrcMIs. If this virtual register was previously seen as a
454 /// copy, replace the uses of this copy with the previously seen copy's
455 /// destination register.
456 bool foldRedundantCopy(MachineInstr &MI);
457
458 /// Is the register \p Reg a non-allocatable physical register?
459 bool isNAPhysCopy(Register Reg);
460
461 /// If copy instruction \p MI is a non-allocatable virtual<->physical
462 /// register copy, track it in the \p NAPhysToVirtMIs map. If this
463 /// non-allocatable physical register was previously copied to a virtual
464 /// registered and hasn't been clobbered, the virt->phys copy can be
465 /// deleted.
466 bool
467 foldRedundantNAPhysCopy(MachineInstr &MI,
468 DenseMap<Register, MachineInstr *> &NAPhysToVirtMIs);
469
470 bool isLoadFoldable(MachineInstr &MI,
471 SmallSet<Register, 16> &FoldAsLoadDefCandidates);
472
473 /// Try to fold the load defined by \p FoldReg into \p MI using
474 /// TII->optimizeLoadInstr. On success, updates \p LocalMIs, erases the old
475 /// instructions, and returns the replacement; returns nullptr otherwise.
476 MachineInstr *foldLoadInto(MachineFunction &MF, MachineInstr &MI,
477 Register FoldReg,
478 SmallPtrSet<MachineInstr *, 16> &LocalMIs);
479
480 /// Check whether \p MI is understood by the register coalescer
481 /// but may require some rewriting.
482 bool isCoalescableCopy(const MachineInstr &MI) const {
483 // SubregToRegs are not interesting, because they are already register
484 // coalescer friendly.
485 return MI.isCopy() ||
486 (Opts.adv_copy_opt && (MI.isRegSequence() || MI.isInsertSubreg() ||
487 MI.isExtractSubreg()));
488 }
489
490 /// Check whether \p MI is a copy like instruction that is
491 /// not recognized by the register coalescer.
492 bool isUncoalescableCopy(const MachineInstr &MI) const {
493 return MI.isBitcast() || (Opts.adv_copy_opt && (MI.isRegSequenceLike() ||
494 MI.isInsertSubregLike() ||
495 MI.isExtractSubregLike()));
496 }
497
498 MachineInstr &rewriteSource(MachineInstr &CopyLike, RegSubRegPair Def,
499 RewriteMapTy &RewriteMap);
500
501 // Set of copies to virtual registers keyed by source register. Never
502 // holds any physreg which requires def tracking.
503 DenseMap<RegSubRegPair, MachineInstr *> CopySrcMIs;
504
505 // MachineFunction::Delegate implementation. Used to maintain CopySrcMIs.
506 void MF_HandleInsertion(MachineInstr &MI) override {}
507
508 bool getCopySrc(MachineInstr &MI, RegSubRegPair &SrcPair) {
509 if (!MI.isCopy())
510 return false;
511
512 Register SrcReg = MI.getOperand(1).getReg();
513 unsigned SrcSubReg = MI.getOperand(1).getSubReg();
514 if (!SrcReg.isVirtual() && !MRI->isConstantPhysReg(SrcReg))
515 return false;
516
517 SrcPair = RegSubRegPair(SrcReg, SrcSubReg);
518 return true;
519 }
520
521 // If a COPY instruction is to be deleted or changed, we should also remove
522 // it from CopySrcMIs.
523 void deleteChangedCopy(MachineInstr &MI) {
524 RegSubRegPair SrcPair;
525 if (!getCopySrc(MI, SrcPair))
526 return;
527
528 auto It = CopySrcMIs.find(SrcPair);
529 if (It != CopySrcMIs.end() && It->second == &MI)
530 CopySrcMIs.erase(It);
531 }
532
533 void MF_HandleRemoval(MachineInstr &MI) override { deleteChangedCopy(MI); }
534
535 void MF_HandleChangeDesc(MachineInstr &MI, const MCInstrDesc &TID) override {
536 deleteChangedCopy(MI);
537 }
538};
539
540class PeepholeOptimizerLegacy : public MachineFunctionPass {
541public:
542 static char ID; // Pass identification
543
544 PeepholeOptimizerLegacy() : MachineFunctionPass(ID) {}
545
546 bool runOnMachineFunction(MachineFunction &MF) override;
547
548 void getAnalysisUsage(AnalysisUsage &AU) const override {
549 AU.setPreservesCFG();
551 AU.addRequired<MachineLoopInfoWrapperPass>();
552 if (Aggressive) {
553 AU.addRequired<MachineDominatorTreeWrapperPass>();
554 }
555 }
556
557 MachineFunctionProperties getRequiredProperties() const override {
558 return MachineFunctionProperties().setIsSSA();
559 }
560};
561
562/// Helper class to hold instructions that are inside recurrence cycles.
563/// The recurrence cycle is formulated around 1) a def operand and its
564/// tied use operand, or 2) a def operand and a use operand that is commutable
565/// with another use operand which is tied to the def operand. In the latter
566/// case, index of the tied use operand and the commutable use operand are
567/// maintained with CommutePair.
568class RecurrenceInstr {
569public:
570 using IndexPair = std::pair<unsigned, unsigned>;
571
572 RecurrenceInstr(MachineInstr *MI) : MI(MI) {}
573 RecurrenceInstr(MachineInstr *MI, unsigned Idx1, unsigned Idx2)
574 : MI(MI), CommutePair(std::make_pair(Idx1, Idx2)) {}
575
576 MachineInstr *getMI() const { return MI; }
577 std::optional<IndexPair> getCommutePair() const { return CommutePair; }
578
579private:
580 MachineInstr *MI;
581 std::optional<IndexPair> CommutePair;
582};
583
584/// Helper class to hold a reply for ValueTracker queries.
585/// Contains the returned sources for a given search and the instructions
586/// where the sources were tracked from.
587class ValueTrackerResult {
588private:
589 /// Track all sources found by one ValueTracker query.
591
592 /// Instruction using the sources in 'RegSrcs'.
593 const MachineInstr *Inst = nullptr;
594
595public:
596 ValueTrackerResult() = default;
597
598 ValueTrackerResult(Register Reg, unsigned SubReg) { addSource(Reg, SubReg); }
599
600 bool isValid() const { return getNumSources() > 0; }
601
602 void setInst(const MachineInstr *I) { Inst = I; }
603 const MachineInstr *getInst() const { return Inst; }
604
605 void clear() {
606 RegSrcs.clear();
607 Inst = nullptr;
608 }
609
610 void addSource(Register SrcReg, unsigned SrcSubReg) {
611 RegSrcs.push_back(RegSubRegPair(SrcReg, SrcSubReg));
612 }
613
614 void setSource(int Idx, Register SrcReg, unsigned SrcSubReg) {
615 assert(Idx < getNumSources() && "Reg pair source out of index");
616 RegSrcs[Idx] = RegSubRegPair(SrcReg, SrcSubReg);
617 }
618
619 int getNumSources() const { return RegSrcs.size(); }
620
621 RegSubRegPair getSrc(int Idx) const { return RegSrcs[Idx]; }
622
623 Register getSrcReg(int Idx) const {
624 assert(Idx < getNumSources() && "Reg source out of index");
625 return RegSrcs[Idx].Reg;
626 }
627
628 unsigned getSrcSubReg(int Idx) const {
629 assert(Idx < getNumSources() && "SubReg source out of index");
630 return RegSrcs[Idx].SubReg;
631 }
632
633 bool operator==(const ValueTrackerResult &Other) const {
634 if (Other.getInst() != getInst())
635 return false;
636
637 if (Other.getNumSources() != getNumSources())
638 return false;
639
640 for (int i = 0, e = Other.getNumSources(); i != e; ++i)
641 if (Other.getSrcReg(i) != getSrcReg(i) ||
642 Other.getSrcSubReg(i) != getSrcSubReg(i))
643 return false;
644 return true;
645 }
646};
647
648/// Helper class to track the possible sources of a value defined by
649/// a (chain of) copy related instructions.
650/// Given a definition (instruction and definition index), this class
651/// follows the use-def chain to find successive suitable sources.
652/// The given source can be used to rewrite the definition into
653/// def = COPY src.
654///
655/// For instance, let us consider the following snippet:
656/// v0 =
657/// v2 = INSERT_SUBREG v1, v0, sub0
658/// def = COPY v2.sub0
659///
660/// Using a ValueTracker for def = COPY v2.sub0 will give the following
661/// suitable sources:
662/// v2.sub0 and v0.
663/// Then, def can be rewritten into def = COPY v0.
664class ValueTracker {
665private:
666 const CodeGenOptions &Opts;
667
668 /// The current point into the use-def chain.
669 const MachineInstr *Def = nullptr;
670
671 /// The index of the definition in Def.
672 unsigned DefIdx = 0;
673
674 /// The sub register index of the definition.
675 unsigned DefSubReg;
676
677 /// The register where the value can be found.
678 Register Reg;
679
680 /// MachineRegisterInfo used to perform tracking.
681 const MachineRegisterInfo &MRI;
682
683 /// Optional TargetInstrInfo used to perform some complex tracking.
684 const TargetInstrInfo *TII;
685
686 /// Dispatcher to the right underlying implementation of getNextSource.
687 ValueTrackerResult getNextSourceImpl();
688
689 /// Specialized version of getNextSource for Copy instructions.
690 ValueTrackerResult getNextSourceFromCopy();
691
692 /// Specialized version of getNextSource for Bitcast instructions.
693 ValueTrackerResult getNextSourceFromBitcast();
694
695 /// Specialized version of getNextSource for RegSequence instructions.
696 ValueTrackerResult getNextSourceFromRegSequence();
697
698 /// Specialized version of getNextSource for InsertSubreg instructions.
699 ValueTrackerResult getNextSourceFromInsertSubreg();
700
701 /// Specialized version of getNextSource for ExtractSubreg instructions.
702 ValueTrackerResult getNextSourceFromExtractSubreg();
703
704 /// Specialized version of getNextSource for SubregToReg instructions.
705 ValueTrackerResult getNextSourceFromSubregToReg();
706
707 /// Specialized version of getNextSource for PHI instructions.
708 ValueTrackerResult getNextSourceFromPHI();
709
710public:
711 /// Create a ValueTracker instance for the value defined by \p Reg.
712 /// \p DefSubReg represents the sub register index the value tracker will
713 /// track. It does not need to match the sub register index used in the
714 /// definition of \p Reg.
715 /// If \p Reg is a physical register, a value tracker constructed with
716 /// this constructor will not find any alternative source.
717 /// Indeed, when \p Reg is a physical register that constructor does not
718 /// know which definition of \p Reg it should track.
719 /// Use the next constructor to track a physical register.
720 ValueTracker(const CodeGenOptions &Opts, Register Reg, unsigned DefSubReg,
721 const MachineRegisterInfo &MRI,
722 const TargetInstrInfo *TII = nullptr)
723 : Opts(Opts), DefSubReg(DefSubReg), Reg(Reg), MRI(MRI), TII(TII) {
724 if (!Reg.isPhysical()) {
725 MachineRegisterInfo::def_iterator DI = MRI.def_begin(Reg);
726 if (DI != MRI.def_end()) {
727 Def = DI->getParent();
728 DefIdx = DI.getOperandNo();
729 }
730 }
731 }
732
733 /// Following the use-def chain, get the next available source
734 /// for the tracked value.
735 /// \return A ValueTrackerResult containing a set of registers
736 /// and sub registers with tracked values. A ValueTrackerResult with
737 /// an empty set of registers means no source was found.
738 ValueTrackerResult getNextSource();
739};
740
741} // end anonymous namespace
742
743char PeepholeOptimizerLegacy::ID = 0;
744
745char &llvm::PeepholeOptimizerLegacyID = PeepholeOptimizerLegacy::ID;
746
747INITIALIZE_PASS_BEGIN(PeepholeOptimizerLegacy, DEBUG_TYPE,
748 "Peephole Optimizations", false, false)
751INITIALIZE_PASS_END(PeepholeOptimizerLegacy, DEBUG_TYPE,
752 "Peephole Optimizations", false, false)
753
754/// If instruction is a copy-like instruction, i.e. it reads a single register
755/// and writes a single register and it does not modify the source, and if the
756/// source value is preserved as a sub-register of the result, then replace all
757/// reachable uses of the source with the subreg of the result.
758///
759/// Do not generate an EXTRACT that is used only in a debug use, as this changes
760/// the code. Since this code does not currently share EXTRACTs, just ignore all
761/// debug uses.
762bool PeepholeOptimizer::optimizeExtInstr(
764 SmallPtrSetImpl<MachineInstr *> &LocalMIs) {
765 Register SrcReg, DstReg;
766 unsigned SubIdx;
767 if (!TII->isCoalescableExtInstr(MI, SrcReg, DstReg, SubIdx))
768 return false;
769
770 if (DstReg.isPhysical() || SrcReg.isPhysical())
771 return false;
772
773 if (MRI->hasOneNonDBGUse(SrcReg))
774 // No other uses.
775 return false;
776
777 // Ensure DstReg can get a register class that actually supports
778 // sub-registers. Don't change the class until we commit.
779 const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
780 DstRC = TRI->getSubClassWithSubReg(DstRC, SubIdx);
781 if (!DstRC)
782 return false;
783
784 // The ext instr may be operating on a sub-register of SrcReg as well.
785 // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit
786 // register.
787 // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of
788 // SrcReg:SubIdx should be replaced.
789 bool UseSrcSubIdx =
790 TRI->getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != nullptr;
791
792 // The source has other uses. See if we can replace the other uses with use of
793 // the result of the extension.
795 for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg))
796 ReachedBBs.insert(UI.getParent());
797
798 // Uses that are in the same BB of uses of the result of the instruction.
800
801 // Uses that the result of the instruction can reach.
803
804 bool ExtendLife = true;
805 for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) {
806 MachineInstr *UseMI = UseMO.getParent();
807 if (UseMI == &MI)
808 continue;
809
810 if (UseMI->isPHI()) {
811 ExtendLife = false;
812 continue;
813 }
814
815 // Only accept uses of SrcReg:SubIdx.
816 if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx)
817 continue;
818
819 // It's an error to translate this:
820 //
821 // %reg1025 = <sext> %reg1024
822 // ...
823 // %reg1026 = SUBREG_TO_REG %reg1024, 4
824 //
825 // into this:
826 //
827 // %reg1025 = <sext> %reg1024
828 // ...
829 // %reg1027 = COPY %reg1025:4
830 // %reg1026 = SUBREG_TO_REG %reg1027, 4
831 //
832 // The problem here is that SUBREG_TO_REG is there to assert that an
833 // implicit zext occurs. It doesn't insert a zext instruction. If we allow
834 // the COPY here, it will give us the value after the <sext>, not the
835 // original value of %reg1024 before <sext>.
836 if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
837 continue;
838
839 MachineBasicBlock *UseMBB = UseMI->getParent();
840 if (UseMBB == &MBB) {
841 // Local uses that come after the extension.
842 if (!LocalMIs.count(UseMI))
843 Uses.push_back(&UseMO);
844 } else if (ReachedBBs.count(UseMBB)) {
845 // Non-local uses where the result of the extension is used. Always
846 // replace these unless it's a PHI.
847 Uses.push_back(&UseMO);
848 } else if (Aggressive && DT->dominates(&MBB, UseMBB)) {
849 // We may want to extend the live range of the extension result in order
850 // to replace these uses.
851 ExtendedUses.push_back(&UseMO);
852 } else {
853 // Both will be live out of the def MBB anyway. Don't extend live range of
854 // the extension result.
855 ExtendLife = false;
856 break;
857 }
858 }
859
860 if (ExtendLife && !ExtendedUses.empty())
861 // Extend the liveness of the extension result.
862 Uses.append(ExtendedUses.begin(), ExtendedUses.end());
863
864 // Now replace all uses.
865 bool Changed = false;
866 if (!Uses.empty()) {
867 SmallPtrSet<MachineBasicBlock *, 4> PHIBBs;
868
869 // Look for PHI uses of the extended result, we don't want to extend the
870 // liveness of a PHI input. It breaks all kinds of assumptions down
871 // stream. A PHI use is expected to be the kill of its source values.
872 for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg))
873 if (UI.isPHI())
874 PHIBBs.insert(UI.getParent());
875
876 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
877 for (MachineOperand *UseMO : Uses) {
878 MachineInstr *UseMI = UseMO->getParent();
879 MachineBasicBlock *UseMBB = UseMI->getParent();
880 if (PHIBBs.count(UseMBB))
881 continue;
882
883 if (!Changed)
884 MRI->constrainRegClass(DstReg, DstRC);
885
886 // SubReg defs are illegal in machine SSA phase,
887 // we should not generate SubReg defs.
888 //
889 // For example, for the instructions:
890 //
891 // %1:g8rc_and_g8rc_nox0 = EXTSW %0:g8rc
892 // %3:gprc_and_gprc_nor0 = COPY %0.sub_32:g8rc
893 //
894 // We should generate:
895 //
896 // %1:g8rc_and_g8rc_nox0 = EXTSW %0:g8rc
897 // %6:gprc_and_gprc_nor0 = COPY %1.sub_32:g8rc_and_g8rc_nox0
898 // %3:gprc_and_gprc_nor0 = COPY %6:gprc_and_gprc_nor0
899 //
900 if (UseSrcSubIdx) {
901 RC = MRI->getRegClass(UseMO->getReg());
902 if (UseMO->getSubReg())
903 RC = TRI->getSubRegisterClass(RC, UseMO->getSubReg());
904 }
905
906 Register NewVR = MRI->createVirtualRegister(RC);
907 [[maybe_unused]] auto Copy = BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
908 TII->get(TargetOpcode::COPY), NewVR)
909 .addReg(DstReg, {}, SubIdx);
910 LLVM_DEBUG(dbgs() << " Build new copy: " << *Copy
911 << " Changing: " << *UseMI);
912 if (UseSrcSubIdx)
913 UseMO->setSubReg(0);
914
915 UseMO->setReg(NewVR);
916 LLVM_DEBUG(dbgs() << " to: " << *UseMI);
917 ++NumReuse;
918 Changed = true;
919 }
920 }
921
922 return Changed;
923}
924
925/// If the instruction is a compare and the previous instruction it's comparing
926/// against already sets (or could be modified to set) the same flag as the
927/// compare, then we can remove the comparison and use the flag from the
928/// previous instruction.
929bool PeepholeOptimizer::optimizeCmpInstr(
932 // If this instruction is a comparison against zero and isn't comparing a
933 // physical register, we can try to optimize it.
934 Register SrcReg, SrcReg2;
935 int64_t CmpMask, CmpValue;
936 if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) ||
937 SrcReg.isPhysical() || SrcReg2.isPhysical())
938 return false;
939
940 // Attempt to optimize the comparison instruction.
941 LLVM_DEBUG(dbgs() << "Attempting to optimize compare: " << MI);
942 if (!TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI))
943 return false;
944
945 LLVM_DEBUG(dbgs() << " -> Successfully optimized compare!\n");
946 LocalMIs.erase(&MI);
947 ++NumCmps;
948
949 // The eliminated compare may have been the extra use preventing a
950 // load from being folded into the flag-setting instruction.
951 if (MachineInstr *FlagProducer =
952 SrcReg.isVirtual() ? MRI->getOneNonDBGUser(SrcReg) : nullptr) {
953 MachineInstr *LoadMI = MRI->getVRegDef(SrcReg);
954 // No store between LoadMI and FlagProducer that could change the value.
955 if (LocalMIs.count(FlagProducer) && LoadMI && LoadMI->canFoldAsLoad() &&
956 LoadMI->mayLoad() && LocalMIs.count(LoadMI) &&
958 make_range(std::next(LoadMI->getIterator()),
959 FlagProducer->getIterator()),
960 [](const MachineInstr &I) { return I.isLoadFoldBarrier(); }))
961 foldLoadInto(MF, *FlagProducer, SrcReg, LocalMIs);
962 }
963
964 return true;
965}
966
967/// Optimize a select instruction.
968bool PeepholeOptimizer::optimizeSelect(
969 MachineInstr &MI, SmallPtrSetImpl<MachineInstr *> &LocalMIs) {
970 assert(MI.isSelect() && "Should only be called when MI->isSelect() is true");
971 if (!TII->optimizeSelect(MI, LocalMIs))
972 return false;
973 LLVM_DEBUG(dbgs() << "Deleting select: " << MI);
974 MI.eraseFromParent();
975 ++NumSelects;
976 return true;
977}
978
979/// Check if a simpler conditional branch can be generated.
980bool PeepholeOptimizer::optimizeCondBranch(MachineInstr &MI) {
981 return TII->optimizeCondBranch(MI);
982}
983
984/// Try to find a better source value that shares the same register file to
985/// replace \p RegSubReg in an instruction like
986/// `DefRC.DefSubReg = COPY RegSubReg`
987///
988/// When true is returned, the \p RewriteMap can be used by the client to
989/// retrieve all Def -> Use along the way up to the next source. Any found
990/// Use that is not itself a key for another entry, is the next source to
991/// use. During the search for the next source, multiple sources can be found
992/// given multiple incoming sources of a PHI instruction. In this case, we
993/// look in each PHI source for the next source; all found next sources must
994/// share the same register file as \p Reg and \p SubReg. The client should
995/// then be capable to rewrite all intermediate PHIs to get the next source.
996/// \return False if no alternative sources are available. True otherwise.
997bool PeepholeOptimizer::findNextSource(const TargetRegisterClass *DefRC,
998 unsigned DefSubReg,
999 RegSubRegPair RegSubReg,
1000 RewriteMapTy &RewriteMap) {
1001 // Do not try to find a new source for a physical register.
1002 // So far we do not have any motivating example for doing that.
1003 // Thus, instead of maintaining untested code, we will revisit that if
1004 // that changes at some point.
1005 Register Reg = RegSubReg.Reg;
1006 RegSubRegPair CurSrcPair = RegSubReg;
1007 SmallVector<RegSubRegPair, 4> SrcToLook = {CurSrcPair};
1008
1009 unsigned PHICount = 0;
1010
1011 // Remember the last suitable source in case the search meets an invalid
1012 // source.
1013 bool FoundSuitable = false;
1014 RegSubRegPair SuitablePair = RegSubReg;
1015 bool Aborted = false;
1016 do {
1017 CurSrcPair = SrcToLook.pop_back_val();
1018 // As explained above, do not handle physical registers
1019 if (CurSrcPair.Reg.isPhysical()) {
1020 Aborted = true;
1021 break;
1022 }
1023
1024 ValueTracker ValTracker(Opts, CurSrcPair.Reg, CurSrcPair.SubReg, *MRI, TII);
1025
1026 // Follow the chain of copies until we find a more suitable source, a phi
1027 // or have to abort.
1028 while (true) {
1029 ValueTrackerResult Res = ValTracker.getNextSource();
1030 // Abort at the end of a chain (without finding a suitable source).
1031 if (!Res.isValid()) {
1032 Aborted = true;
1033 break;
1034 }
1035
1036 // Insert the Def -> Use entry for the recently found source.
1037 auto [InsertPt, WasInserted] = RewriteMap.try_emplace(CurSrcPair, Res);
1038
1039 if (!WasInserted) {
1040 const ValueTrackerResult &CurSrcRes = InsertPt->second;
1041
1042 assert(CurSrcRes == Res && "ValueTrackerResult found must match");
1043 // An existent entry with multiple sources is a PHI cycle we must avoid.
1044 // Otherwise it's an entry with a valid next source we already found.
1045 if (CurSrcRes.getNumSources() > 1) {
1047 << "findNextSource: found PHI cycle, aborting...\n");
1048 Aborted = true;
1049 }
1050 break;
1051 }
1052
1053 // ValueTrackerResult usually have one source unless it's the result from
1054 // a PHI instruction. Add the found PHI edges to be looked up further.
1055 unsigned NumSrcs = Res.getNumSources();
1056 if (NumSrcs > 1) {
1057 PHICount++;
1058 if (PHICount >= Opts.rewrite_phi_limit) {
1059 LLVM_DEBUG(dbgs() << "findNextSource: PHI limit reached\n");
1060 Aborted = true;
1061 break;
1062 }
1063
1064 for (unsigned i = 0; i < NumSrcs; ++i)
1065 SrcToLook.push_back(Res.getSrc(i));
1066 break;
1067 }
1068
1069 CurSrcPair = Res.getSrc(0);
1070 // Do not extend the live-ranges of physical registers as they add
1071 // constraints to the register allocator. Moreover, if we want to extend
1072 // the live-range of a physical register, unlike SSA virtual register,
1073 // we will have to check that they aren't redefine before the related use.
1074 if (CurSrcPair.Reg.isPhysical()) {
1075 Aborted = true;
1076 break;
1077 }
1078
1079 // Keep following the chain if the value isn't any better yet.
1080 const TargetRegisterClass *SrcRC = MRI->getRegClass(CurSrcPair.Reg);
1081 if (!TRI->shouldRewriteCopySrc(DefRC, DefSubReg, SrcRC,
1082 CurSrcPair.SubReg))
1083 continue;
1084
1085 // We currently cannot deal with subreg operands on PHI instructions
1086 // (see insertPHI()).
1087 if (PHICount > 0 && CurSrcPair.SubReg != 0)
1088 continue;
1089
1090 // Don't stop at the first suitable source if it is still a subregister;
1091 // keep tracing to try to reach a deeper source. Remember it.
1092 if (CurSrcPair.SubReg != 0) {
1093 SuitablePair = CurSrcPair;
1094 FoundSuitable = true;
1095 continue;
1096 }
1097
1098 // We found a suitable source, and are done with this chain.
1099 break;
1100 }
1101
1102 // A dead-ended chain ends all exploration
1103 if (Aborted)
1104 break;
1105 } while (!SrcToLook.empty());
1106
1107 if (Aborted) {
1108 // If aborted with an invalid source, restore the suitable so far, if any.
1109 if (!FoundSuitable)
1110 return false;
1111
1112 CurSrcPair = SuitablePair;
1113 RewriteMap.erase(SuitablePair);
1114 }
1115
1116 // If we did not find a more suitable source, there is nothing to optimize.
1117 return CurSrcPair.Reg != Reg;
1118}
1119
1120/// Insert a PHI instruction with incoming edges \p SrcRegs that are
1121/// guaranteed to have the same register class. This is necessary whenever we
1122/// successfully traverse a PHI instruction and find suitable sources coming
1123/// from its edges. By inserting a new PHI, we provide a rewritten PHI def
1124/// suitable to be used in a new COPY instruction.
1126 const TargetInstrInfo &TII,
1127 const SmallVectorImpl<RegSubRegPair> &SrcRegs,
1128 MachineInstr &OrigPHI) {
1129 assert(!SrcRegs.empty() && "No sources to create a PHI instruction?");
1130
1131 const TargetRegisterClass *NewRC = MRI.getRegClass(SrcRegs[0].Reg);
1132 // NewRC is only correct if no subregisters are involved. findNextSource()
1133 // should have rejected those cases already.
1134 assert(SrcRegs[0].SubReg == 0 && "should not have subreg operand");
1135 Register NewVR = MRI.createVirtualRegister(NewRC);
1136 MachineBasicBlock *MBB = OrigPHI.getParent();
1137 MachineInstrBuilder MIB = BuildMI(*MBB, &OrigPHI, OrigPHI.getDebugLoc(),
1138 TII.get(TargetOpcode::PHI), NewVR);
1139
1140 unsigned MBBOpIdx = 2;
1141 for (const RegSubRegPair &RegPair : SrcRegs) {
1142 MIB.addReg(RegPair.Reg, {}, RegPair.SubReg);
1143 MIB.addMBB(OrigPHI.getOperand(MBBOpIdx).getMBB());
1144 MBBOpIdx += 2;
1145 }
1146
1147 return *MIB;
1148}
1149
1150/// Given a \p Def.Reg and Def.SubReg pair, use \p RewriteMap to find
1151/// the new source to use for rewrite. If \p HandleMultipleSources is true and
1152/// multiple sources for a given \p Def are found along the way, we found a
1153/// PHI instructions that needs to be rewritten.
1154/// TODO: HandleMultipleSources should be removed once we test PHI handling
1155/// with coalescable copies.
1156static RegSubRegPair
1158 RegSubRegPair Def,
1159 const PeepholeOptimizer::RewriteMapTy &RewriteMap,
1160 bool HandleMultipleSources = true) {
1161 RegSubRegPair LookupSrc(Def.Reg, Def.SubReg);
1162 while (true) {
1163 ValueTrackerResult Res = RewriteMap.lookup(LookupSrc);
1164 // If there are no entries on the map, LookupSrc is the new source.
1165 if (!Res.isValid())
1166 return LookupSrc;
1167
1168 // There's only one source for this definition, keep searching...
1169 unsigned NumSrcs = Res.getNumSources();
1170 if (NumSrcs == 1) {
1171 LookupSrc.Reg = Res.getSrcReg(0);
1172 LookupSrc.SubReg = Res.getSrcSubReg(0);
1173 continue;
1174 }
1175
1176 // TODO: Remove once multiple srcs w/ coalescable copies are supported.
1177 if (!HandleMultipleSources)
1178 break;
1179
1180 // Multiple sources, recurse into each source to find a new source
1181 // for it. Then, rewrite the PHI accordingly to its new edges.
1183 for (unsigned i = 0; i < NumSrcs; ++i) {
1184 RegSubRegPair PHISrc(Res.getSrcReg(i), Res.getSrcSubReg(i));
1185 NewPHISrcs.push_back(
1186 getNewSource(MRI, TII, PHISrc, RewriteMap, HandleMultipleSources));
1187 }
1188
1189 // Build the new PHI node and return its def register as the new source.
1190 MachineInstr &OrigPHI = const_cast<MachineInstr &>(*Res.getInst());
1191 MachineInstr &NewPHI = insertPHI(*MRI, *TII, NewPHISrcs, OrigPHI);
1192 LLVM_DEBUG(dbgs() << "-- getNewSource\n");
1193 LLVM_DEBUG(dbgs() << " Replacing: " << OrigPHI);
1194 LLVM_DEBUG(dbgs() << " With: " << NewPHI);
1195 const MachineOperand &MODef = NewPHI.getOperand(0);
1196 return RegSubRegPair(MODef.getReg(), MODef.getSubReg());
1197 }
1198
1199 return RegSubRegPair(0, 0);
1200}
1201
1202bool PeepholeOptimizer::optimizeCoalescableCopyImpl(Rewriter &&CpyRewriter) {
1203 bool Changed = false;
1204 // Get the right rewriter for the current copy.
1205 // Rewrite each rewritable source.
1206 RegSubRegPair Dst;
1207 RegSubRegPair TrackPair;
1208 while (CpyRewriter.getNextRewritableSource(TrackPair, Dst)) {
1209 if (Dst.Reg.isPhysical()) {
1210 // Do not try to find a new source for a physical register.
1211 // So far we do not have any motivating example for doing that.
1212 // Thus, instead of maintaining untested code, we will revisit that if
1213 // that changes at some point.
1214 continue;
1215 }
1216
1217 const TargetRegisterClass *DefRC = MRI->getRegClass(Dst.Reg);
1218
1219 // Keep track of PHI nodes and its incoming edges when looking for sources.
1220 RewriteMapTy RewriteMap;
1221 // Try to find a more suitable source. If we failed to do so, or get the
1222 // actual source, move to the next source.
1223 if (!findNextSource(DefRC, Dst.SubReg, TrackPair, RewriteMap))
1224 continue;
1225
1226 // Get the new source to rewrite. TODO: Only enable handling of multiple
1227 // sources (PHIs) once we have a motivating example and testcases for it.
1228 RegSubRegPair NewSrc = getNewSource(MRI, TII, TrackPair, RewriteMap,
1229 /*HandleMultipleSources=*/false);
1230 assert(TrackPair.Reg != NewSrc.Reg &&
1231 "should not rewrite source to original value");
1232 if (!NewSrc.Reg)
1233 continue;
1234
1235 if (NewSrc.SubReg) {
1236 // Verify the register class supports the subregister index. ARM's
1237 // copy-like queries return register:subreg pairs where the register's
1238 // current class does not directly support the subregister index.
1239 const TargetRegisterClass *RC = MRI->getRegClass(NewSrc.Reg);
1240 const TargetRegisterClass *WithSubRC =
1241 TRI->getSubClassWithSubReg(RC, NewSrc.SubReg);
1242 if (!MRI->constrainRegClass(NewSrc.Reg, WithSubRC))
1243 continue;
1244 Changed = true;
1245 }
1246
1247 // Rewrite source.
1248 if (CpyRewriter.RewriteCurrentSource(NewSrc.Reg, NewSrc.SubReg))
1249 Changed = true;
1250 }
1251
1252 // TODO: We could have a clean-up method to tidy the instruction.
1253 // E.g., v0 = INSERT_SUBREG v1, v1.sub0, sub0
1254 // => v0 = COPY v1
1255 // Currently we haven't seen motivating example for that and we
1256 // want to avoid untested code.
1257 NumRewrittenCopies += Changed;
1258 return Changed;
1259}
1260
1261/// Optimize generic copy instructions to avoid cross register bank copy.
1262/// The optimization looks through a chain of copies and tries to find a source
1263/// that has a compatible register class.
1264/// Two register classes are considered to be compatible if they share the same
1265/// register bank.
1266/// New copies issued by this optimization are register allocator
1267/// friendly. This optimization does not remove any copy as it may
1268/// overconstrain the register allocator, but replaces some operands
1269/// when possible.
1270/// \pre isCoalescableCopy(*MI) is true.
1271/// \return True, when \p MI has been rewritten. False otherwise.
1272bool PeepholeOptimizer::optimizeCoalescableCopy(MachineInstr &MI) {
1273 assert(isCoalescableCopy(MI) && "Invalid argument");
1274 assert(MI.getDesc().getNumDefs() == 1 &&
1275 "Coalescer can understand multiple defs?!");
1276 const MachineOperand &MODef = MI.getOperand(0);
1277 // Do not rewrite physical definitions.
1278 if (MODef.getReg().isPhysical())
1279 return false;
1280
1281 switch (MI.getOpcode()) {
1282 case TargetOpcode::COPY:
1283 return optimizeCoalescableCopyImpl(CopyRewriter(MI));
1284 case TargetOpcode::INSERT_SUBREG:
1285 return optimizeCoalescableCopyImpl(InsertSubregRewriter(MI));
1286 case TargetOpcode::EXTRACT_SUBREG:
1287 return optimizeCoalescableCopyImpl(ExtractSubregRewriter(MI, *TII));
1288 case TargetOpcode::REG_SEQUENCE:
1289 return optimizeCoalescableCopyImpl(RegSequenceRewriter(MI));
1290 default:
1291 // Handle uncoalescable copy-like instructions.
1292 if (MI.isBitcast() || MI.isRegSequenceLike() || MI.isInsertSubregLike() ||
1293 MI.isExtractSubregLike())
1294 return optimizeCoalescableCopyImpl(UncoalescableRewriter(MI));
1295 return false;
1296 }
1297}
1298
1299/// Rewrite the source found through \p Def, by using the \p RewriteMap
1300/// and create a new COPY instruction. More info about RewriteMap in
1301/// PeepholeOptimizer::findNextSource. Right now this is only used to handle
1302/// Uncoalescable copies, since they are copy like instructions that aren't
1303/// recognized by the register allocator.
1304MachineInstr &PeepholeOptimizer::rewriteSource(MachineInstr &CopyLike,
1305 RegSubRegPair Def,
1306 RewriteMapTy &RewriteMap) {
1307 assert(!Def.Reg.isPhysical() && "We do not rewrite physical registers");
1308
1309 // Find the new source to use in the COPY rewrite.
1310 RegSubRegPair NewSrc = getNewSource(MRI, TII, Def, RewriteMap);
1311
1312 // Insert the COPY.
1313 const TargetRegisterClass *DefRC = MRI->getRegClass(Def.Reg);
1314 Register NewVReg = MRI->createVirtualRegister(DefRC);
1315
1316 if (NewSrc.SubReg) {
1317 const TargetRegisterClass *NewSrcRC = MRI->getRegClass(NewSrc.Reg);
1318 const TargetRegisterClass *WithSubRC =
1319 TRI->getSubClassWithSubReg(NewSrcRC, NewSrc.SubReg);
1320
1321 // The new source may not directly support the subregister, but we should be
1322 // able to assume it is constrainable to support the subregister (otherwise
1323 // ValueTracker was lying and reported a useless value).
1324 if (!MRI->constrainRegClass(NewSrc.Reg, WithSubRC))
1325 llvm_unreachable("replacement register cannot support subregister");
1326 }
1327
1328 MachineInstr *NewCopy =
1329 BuildMI(*CopyLike.getParent(), &CopyLike, CopyLike.getDebugLoc(),
1330 TII->get(TargetOpcode::COPY), NewVReg)
1331 .addReg(NewSrc.Reg, {}, NewSrc.SubReg);
1332
1333 if (Def.SubReg) {
1334 NewCopy->getOperand(0).setSubReg(Def.SubReg);
1335 NewCopy->getOperand(0).setIsUndef();
1336 }
1337
1338 LLVM_DEBUG(dbgs() << "-- RewriteSource\n");
1339 LLVM_DEBUG(dbgs() << " Replacing: " << CopyLike);
1340 LLVM_DEBUG(dbgs() << " With: " << *NewCopy);
1341 MRI->replaceRegWith(Def.Reg, NewVReg);
1342
1343 return *NewCopy;
1344}
1345
1346/// Optimize copy-like instructions to create
1347/// register coalescer friendly instruction.
1348/// The optimization tries to kill-off the \p MI by looking
1349/// through a chain of copies to find a source that has a compatible
1350/// register class.
1351/// If such a source is found, it replace \p MI by a generic COPY
1352/// operation.
1353/// \pre isUncoalescableCopy(*MI) is true.
1354/// \return True, when \p MI has been optimized. In that case, \p MI has
1355/// been removed from its parent.
1356/// All COPY instructions created, are inserted in \p LocalMIs.
1357bool PeepholeOptimizer::optimizeUncoalescableCopy(
1358 MachineInstr &MI, SmallPtrSetImpl<MachineInstr *> &LocalMIs) {
1359 assert(isUncoalescableCopy(MI) && "Invalid argument");
1360 UncoalescableRewriter CpyRewriter(MI);
1361
1362 // Rewrite each rewritable source by generating new COPYs. This works
1363 // differently from optimizeCoalescableCopy since it first makes sure that all
1364 // definitions can be rewritten.
1365 RewriteMapTy RewriteMap;
1366 RegSubRegPair Src;
1368 SmallVector<RegSubRegPair, 4> RewritePairs;
1369 while (CpyRewriter.getNextRewritableSource(Src, Def)) {
1370 // If a physical register is here, this is probably for a good reason.
1371 // Do not rewrite that.
1372 if (Def.Reg.isPhysical())
1373 return false;
1374
1375 // FIXME: Uncoalescable copies are treated differently by
1376 // UncoalescableRewriter, and this probably should not share
1377 // API. getNextRewritableSource really finds rewritable defs.
1378 const TargetRegisterClass *DefRC = MRI->getRegClass(Def.Reg);
1379
1380 // If we do not know how to rewrite this definition, there is no point
1381 // in trying to kill this instruction.
1382 if (!findNextSource(DefRC, Def.SubReg, Def, RewriteMap))
1383 return false;
1384
1385 RewritePairs.push_back(Def);
1386 }
1387
1388 // The change is possible for all defs, do it.
1389 for (const RegSubRegPair &Def : RewritePairs) {
1390 // Rewrite the "copy" in a way the register coalescer understands.
1391 MachineInstr &NewCopy = rewriteSource(MI, Def, RewriteMap);
1392 LocalMIs.insert(&NewCopy);
1393 }
1394
1395 // MI is now dead.
1396 LLVM_DEBUG(dbgs() << "Deleting uncoalescable copy: " << MI);
1397 MI.eraseFromParent();
1398 ++NumUncoalescableCopies;
1399 return true;
1400}
1401
1402/// Check whether MI is a candidate for folding into a later instruction.
1403/// We only fold loads to virtual registers and the virtual register defined
1404/// has a single user.
1405bool PeepholeOptimizer::isLoadFoldable(
1406 MachineInstr &MI, SmallSet<Register, 16> &FoldAsLoadDefCandidates) {
1407 if (!MI.canFoldAsLoad() || !MI.mayLoad())
1408 return false;
1409 const MCInstrDesc &MCID = MI.getDesc();
1410 if (MCID.getNumDefs() != 1)
1411 return false;
1412
1413 Register Reg = MI.getOperand(0).getReg();
1414 // To reduce compilation time, we check MRI->hasOneNonDBGUser when inserting
1415 // loads. It should be checked when processing uses of the load, since
1416 // uses can be removed during peephole.
1417 if (Reg.isVirtual() && !MI.getOperand(0).getSubReg() &&
1419 FoldAsLoadDefCandidates.insert(Reg);
1420 return true;
1421 }
1422 return false;
1423}
1424
1425MachineInstr *
1426PeepholeOptimizer::foldLoadInto(MachineFunction &MF, MachineInstr &MI,
1427 Register FoldReg,
1428 SmallPtrSet<MachineInstr *, 16> &LocalMIs) {
1429 Register Reg = FoldReg;
1430 MachineInstr *DefMI = nullptr;
1431 MachineInstr *CopyMI = nullptr;
1432 MachineInstr *FoldMI = TII->optimizeLoadInstr(MI, MRI, Reg, DefMI, CopyMI);
1433 if (!FoldMI)
1434 return nullptr;
1435 LLVM_DEBUG(dbgs() << "Replacing: " << MI << " With: " << *FoldMI);
1436 LocalMIs.erase(&MI);
1437 LocalMIs.erase(DefMI);
1438 LocalMIs.insert(FoldMI);
1439 if (CopyMI)
1440 LocalMIs.insert(CopyMI);
1441 if (MI.shouldUpdateAdditionalCallInfo())
1442 MF.moveAdditionalCallInfo(&MI, FoldMI);
1443 MI.eraseFromParent();
1446 ++NumLoadFold;
1447 return FoldMI;
1448}
1449
1450bool PeepholeOptimizer::isMoveImmediate(
1451 MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs,
1452 DenseMap<Register, MachineInstr *> &ImmDefMIs) {
1453 const MCInstrDesc &MCID = MI.getDesc();
1454 if (MCID.getNumDefs() != 1 || !MI.getOperand(0).isReg())
1455 return false;
1456 Register Reg = MI.getOperand(0).getReg();
1457 if (!Reg.isVirtual())
1458 return false;
1459
1460 int64_t ImmVal;
1461 if (!MI.isMoveImmediate() && !TII->getConstValDefinedInReg(MI, Reg, ImmVal))
1462 return false;
1463
1464 ImmDefMIs.insert(std::make_pair(Reg, &MI));
1465 ImmDefRegs.insert(Reg);
1466 return true;
1467}
1468
1469/// Try folding register operands that are defined by move immediate
1470/// instructions, i.e. a trivial constant folding optimization, if
1471/// and only if the def and use are in the same BB.
1472bool PeepholeOptimizer::foldImmediate(
1473 MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs,
1474 DenseMap<Register, MachineInstr *> &ImmDefMIs, bool &Deleted) {
1475 Deleted = false;
1476 for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
1477 MachineOperand &MO = MI.getOperand(i);
1478 if (!MO.isReg() || MO.isDef())
1479 continue;
1480 Register Reg = MO.getReg();
1481 if (!Reg.isVirtual())
1482 continue;
1483 if (ImmDefRegs.count(Reg) == 0)
1484 continue;
1485 auto II = ImmDefMIs.find(Reg);
1486 assert(II != ImmDefMIs.end() && "couldn't find immediate definition");
1487 if (TII->foldImmediate(MI, *II->second, Reg, MRI)) {
1488 ++NumImmFold;
1489 // foldImmediate can delete ImmDefMI if MI was its only user. If ImmDefMI
1490 // is not deleted, and we happened to get a same MI, we can delete MI and
1491 // replace its users.
1492 if (MRI->getVRegDef(Reg) &&
1494 Register DstReg = MI.getOperand(0).getReg();
1495 if (DstReg.isVirtual() &&
1496 MRI->getRegClass(DstReg) == MRI->getRegClass(Reg)) {
1497 MRI->replaceRegWith(DstReg, Reg);
1498 MI.eraseFromParent();
1499 Deleted = true;
1500 }
1501 }
1502 return true;
1503 }
1504 }
1505 return false;
1506}
1507
1508// FIXME: This is very simple and misses some cases which should be handled when
1509// motivating examples are found.
1510//
1511// The copy rewriting logic should look at uses as well as defs and be able to
1512// eliminate copies across blocks.
1513//
1514// Later copies that are subregister extracts will also not be eliminated since
1515// only the first copy is considered.
1516//
1517// e.g.
1518// %1 = COPY %0
1519// %2 = COPY %0:sub1
1520//
1521// Should replace %2 uses with %1:sub1
1522bool PeepholeOptimizer::foldRedundantCopy(MachineInstr &MI) {
1523 assert(MI.isCopy() && "expected a COPY machine instruction");
1524
1525 RegSubRegPair SrcPair;
1526 if (!getCopySrc(MI, SrcPair))
1527 return false;
1528
1529 Register DstReg = MI.getOperand(0).getReg();
1530 if (!DstReg.isVirtual())
1531 return false;
1532
1533 if (CopySrcMIs.insert(std::make_pair(SrcPair, &MI)).second) {
1534 // First copy of this reg seen.
1535 return false;
1536 }
1537
1538 MachineInstr *PrevCopy = CopySrcMIs.find(SrcPair)->second;
1539
1540 assert(SrcPair.SubReg == PrevCopy->getOperand(1).getSubReg() &&
1541 "Unexpected mismatching subreg!");
1542
1543 Register PrevDstReg = PrevCopy->getOperand(0).getReg();
1544
1545 // Only replace if the copy register class is the same.
1546 //
1547 // TODO: If we have multiple copies to different register classes, we may want
1548 // to track multiple copies of the same source register.
1549 if (MRI->getRegClass(DstReg) != MRI->getRegClass(PrevDstReg))
1550 return false;
1551
1552 MRI->replaceRegWith(DstReg, PrevDstReg);
1553 return true;
1554}
1555
1556bool PeepholeOptimizer::isNAPhysCopy(Register Reg) {
1557 return Reg.isPhysical() && !MRI->isAllocatable(Reg);
1558}
1559
1560bool PeepholeOptimizer::foldRedundantNAPhysCopy(
1561 MachineInstr &MI, DenseMap<Register, MachineInstr *> &NAPhysToVirtMIs) {
1562 assert(MI.isCopy() && "expected a COPY machine instruction");
1563
1564 if (!Opts.non_allocatable_phys_copy_opt)
1565 return false;
1566
1567 Register DstReg = MI.getOperand(0).getReg();
1568 Register SrcReg = MI.getOperand(1).getReg();
1569 if (isNAPhysCopy(SrcReg) && DstReg.isVirtual()) {
1570 // %vreg = COPY $physreg
1571 // Avoid using a datastructure which can track multiple live non-allocatable
1572 // phys->virt copies since LLVM doesn't seem to do this.
1573 NAPhysToVirtMIs.insert({SrcReg, &MI});
1574 return false;
1575 }
1576
1577 if (!(SrcReg.isVirtual() && isNAPhysCopy(DstReg)))
1578 return false;
1579
1580 // $physreg = COPY %vreg
1581 auto PrevCopy = NAPhysToVirtMIs.find(DstReg);
1582 if (PrevCopy == NAPhysToVirtMIs.end()) {
1583 // We can't remove the copy: there was an intervening clobber of the
1584 // non-allocatable physical register after the copy to virtual.
1585 LLVM_DEBUG(dbgs() << "NAPhysCopy: intervening clobber forbids erasing "
1586 << MI);
1587 return false;
1588 }
1589
1590 Register PrevDstReg = PrevCopy->second->getOperand(0).getReg();
1591 if (PrevDstReg == SrcReg) {
1592 // Remove the virt->phys copy: we saw the virtual register definition, and
1593 // the non-allocatable physical register's state hasn't changed since then.
1594 LLVM_DEBUG(dbgs() << "NAPhysCopy: erasing " << MI);
1595 ++NumNAPhysCopies;
1596 return true;
1597 }
1598
1599 // Potential missed optimization opportunity: we saw a different virtual
1600 // register get a copy of the non-allocatable physical register, and we only
1601 // track one such copy. Avoid getting confused by this new non-allocatable
1602 // physical register definition, and remove it from the tracked copies.
1603 LLVM_DEBUG(dbgs() << "NAPhysCopy: missed opportunity " << MI);
1604 NAPhysToVirtMIs.erase(PrevCopy);
1605 return false;
1606}
1607
1608/// \bried Returns true if \p MO is a virtual register operand.
1610 return MO.isReg() && MO.getReg().isVirtual();
1611}
1612
1613bool PeepholeOptimizer::findTargetRecurrence(
1614 Register Reg, const SmallSet<Register, 2> &TargetRegs,
1615 RecurrenceCycle &RC) {
1616 // Recurrence found if Reg is in TargetRegs.
1617 if (TargetRegs.count(Reg))
1618 return true;
1619
1620 // TODO: Curerntly, we only allow the last instruction of the recurrence
1621 // cycle (the instruction that feeds the PHI instruction) to have more than
1622 // one uses to guarantee that commuting operands does not tie registers
1623 // with overlapping live range. Once we have actual live range info of
1624 // each register, this constraint can be relaxed.
1625 if (!MRI->hasOneNonDBGUse(Reg))
1626 return false;
1627
1628 // Give up if the reccurrence chain length is longer than the limit.
1629 if (RC.size() >= Opts.recurrence_chain_limit)
1630 return false;
1631
1632 MachineInstr &MI = *(MRI->use_instr_nodbg_begin(Reg));
1633 unsigned Idx = MI.findRegisterUseOperandIdx(Reg, /*TRI=*/nullptr);
1634
1635 // Only interested in recurrences whose instructions have only one def, which
1636 // is a virtual register.
1637 if (MI.getDesc().getNumDefs() != 1)
1638 return false;
1639
1640 MachineOperand &DefOp = MI.getOperand(0);
1641 if (!isVirtualRegisterOperand(DefOp))
1642 return false;
1643
1644 // Check if def operand of MI is tied to any use operand. We are only
1645 // interested in the case that all the instructions in the recurrence chain
1646 // have there def operand tied with one of the use operand.
1647 unsigned TiedUseIdx;
1648 if (!MI.isRegTiedToUseOperand(0, &TiedUseIdx))
1649 return false;
1650
1651 if (Idx == TiedUseIdx) {
1652 RC.push_back(RecurrenceInstr(&MI));
1653 return findTargetRecurrence(DefOp.getReg(), TargetRegs, RC);
1654 } else {
1655 // If Idx is not TiedUseIdx, check if Idx is commutable with TiedUseIdx.
1656 unsigned CommIdx = TargetInstrInfo::CommuteAnyOperandIndex;
1657 if (TII->findCommutedOpIndices(MI, Idx, CommIdx) && CommIdx == TiedUseIdx) {
1658 RC.push_back(RecurrenceInstr(&MI, Idx, CommIdx));
1659 return findTargetRecurrence(DefOp.getReg(), TargetRegs, RC);
1660 }
1661 }
1662
1663 return false;
1664}
1665
1666/// Phi instructions will eventually be lowered to copy instructions.
1667/// If phi is in a loop header, a recurrence may formulated around the source
1668/// and destination of the phi. For such case commuting operands of the
1669/// instructions in the recurrence may enable coalescing of the copy instruction
1670/// generated from the phi. For example, if there is a recurrence of
1671///
1672/// LoopHeader:
1673/// %1 = phi(%0, %100)
1674/// LoopLatch:
1675/// %0<def, tied1> = ADD %2<def, tied0>, %1
1676///
1677/// , the fact that %0 and %2 are in the same tied operands set makes
1678/// the coalescing of copy instruction generated from the phi in
1679/// LoopHeader(i.e. %1 = COPY %0) impossible, because %1 and
1680/// %2 have overlapping live range. This introduces additional move
1681/// instruction to the final assembly. However, if we commute %2 and
1682/// %1 of ADD instruction, the redundant move instruction can be
1683/// avoided.
1684bool PeepholeOptimizer::optimizeRecurrence(MachineInstr &PHI) {
1685 SmallSet<Register, 2> TargetRegs;
1686 for (unsigned Idx = 1; Idx < PHI.getNumOperands(); Idx += 2) {
1687 MachineOperand &MO = PHI.getOperand(Idx);
1688 assert(isVirtualRegisterOperand(MO) && "Invalid PHI instruction");
1689 TargetRegs.insert(MO.getReg());
1690 }
1691
1692 bool Changed = false;
1693 RecurrenceCycle RC;
1694 if (findTargetRecurrence(PHI.getOperand(0).getReg(), TargetRegs, RC)) {
1695 // Commutes operands of instructions in RC if necessary so that the copy to
1696 // be generated from PHI can be coalesced.
1697 LLVM_DEBUG(dbgs() << "Optimize recurrence chain from " << PHI);
1698 for (auto &RI : RC) {
1699 LLVM_DEBUG(dbgs() << "\tInst: " << *(RI.getMI()));
1700 auto CP = RI.getCommutePair();
1701 if (CP) {
1702 Changed = true;
1703 TII->commuteInstruction(*(RI.getMI()), false, (*CP).first,
1704 (*CP).second);
1705 LLVM_DEBUG(dbgs() << "\t\tCommuted: " << *(RI.getMI()));
1706 }
1707 }
1708 }
1709
1710 return Changed;
1711}
1712
1713PreservedAnalyses
1716 MFPropsModifier _(*this, MF);
1717 auto *DT =
1718 Aggressive ? &MFAM.getResult<MachineDominatorTreeAnalysis>(MF) : nullptr;
1719 auto *MLI = &MFAM.getResult<MachineLoopAnalysis>(MF);
1720 PeepholeOptimizer Impl(getCodeGenOptions(MF), DT, MLI);
1721 bool Changed = Impl.run(MF);
1722 if (!Changed)
1723 return PreservedAnalyses::all();
1724
1726 PA.preserveSet<CFGAnalyses>();
1727 return PA;
1728}
1729
1730bool PeepholeOptimizerLegacy::runOnMachineFunction(MachineFunction &MF) {
1731 if (skipFunction(MF.getFunction()))
1732 return false;
1733 auto *DT = Aggressive
1734 ? &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree()
1735 : nullptr;
1736 auto *MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1737 PeepholeOptimizer Impl(getCodeGenOptions(MF), DT, MLI);
1738 return Impl.run(MF);
1739}
1740
1741bool PeepholeOptimizer::run(MachineFunction &MF) {
1742
1743 LLVM_DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n");
1744 LLVM_DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n');
1745
1746 if (!Opts.peephole)
1747 return false;
1748
1749 TII = MF.getSubtarget().getInstrInfo();
1751 MRI = &MF.getRegInfo();
1752 MF.setDelegate(this);
1753
1754 bool Changed = false;
1755
1756 for (MachineBasicBlock &MBB : MF) {
1757 bool SeenMoveImm = false;
1758
1759 // During this forward scan, at some point it needs to answer the question
1760 // "given a pointer to an MI in the current BB, is it located before or
1761 // after the current instruction".
1762 // To perform this, the following set keeps track of the MIs already seen
1763 // during the scan, if a MI is not in the set, it is assumed to be located
1764 // after. Newly created MIs have to be inserted in the set as well.
1766 SmallSet<Register, 4> ImmDefRegs;
1768 SmallSet<Register, 16> FoldAsLoadDefCandidates;
1769
1770 // Track when a non-allocatable physical register is copied to a virtual
1771 // register so that useless moves can be removed.
1772 //
1773 // $physreg is the map index; MI is the last valid `%vreg = COPY $physreg`
1774 // without any intervening re-definition of $physreg.
1775 DenseMap<Register, MachineInstr *> NAPhysToVirtMIs;
1776
1777 CopySrcMIs.clear();
1778
1779 bool IsLoopHeader = MLI->isLoopHeader(&MBB);
1780
1781 for (MachineBasicBlock::iterator MII = MBB.begin(), MIE = MBB.end();
1782 MII != MIE;) {
1783 MachineInstr *MI = &*MII;
1784 // We may be erasing MI below, increment MII now.
1785 ++MII;
1786 LocalMIs.insert(MI);
1787
1788 // Skip debug instructions. They should not affect this peephole
1789 // optimization.
1790 if (MI->isDebugInstr())
1791 continue;
1792
1793 if (MI->isPosition())
1794 continue;
1795
1796 if (IsLoopHeader && MI->isPHI()) {
1797 if (optimizeRecurrence(*MI)) {
1798 Changed = true;
1799 continue;
1800 }
1801 }
1802
1803 if (!MI->isCopy()) {
1804 for (const MachineOperand &MO : MI->operands()) {
1805 // Visit all operands: definitions can be implicit or explicit.
1806 if (MO.isReg()) {
1807 Register Reg = MO.getReg();
1808 if (MO.isDef() && isNAPhysCopy(Reg)) {
1809 const auto &Def = NAPhysToVirtMIs.find(Reg);
1810 if (Def != NAPhysToVirtMIs.end()) {
1811 // A new definition of the non-allocatable physical register
1812 // invalidates previous copies.
1814 << "NAPhysCopy: invalidating because of " << *MI);
1815 NAPhysToVirtMIs.erase(Def);
1816 }
1817 }
1818 } else if (MO.isRegMask()) {
1819 const uint32_t *RegMask = MO.getRegMask();
1820 NAPhysToVirtMIs.remove_if([&](const auto &RegMI) {
1821 if (!MachineOperand::clobbersPhysReg(RegMask, RegMI.first))
1822 return false;
1824 << "NAPhysCopy: invalidating because of " << *MI);
1825 return true;
1826 });
1827 }
1828 }
1829 }
1830
1831 if (MI->isImplicitDef() || MI->isKill())
1832 continue;
1833
1834 if (MI->isInlineAsm() || MI->hasUnmodeledSideEffects()) {
1835 // Blow away all non-allocatable physical registers knowledge since we
1836 // don't know what's correct anymore.
1837 //
1838 // FIXME: handle explicit asm clobbers.
1839 LLVM_DEBUG(dbgs() << "NAPhysCopy: blowing away all info due to "
1840 << *MI);
1841 NAPhysToVirtMIs.clear();
1842 }
1843
1844 if (MI->isCompare() && optimizeCmpInstr(*MI, MF, LocalMIs)) {
1845 Changed = true;
1846 continue;
1847 }
1848
1849 if ((isUncoalescableCopy(*MI) &&
1850 optimizeUncoalescableCopy(*MI, LocalMIs)) ||
1851 (MI->isSelect() && optimizeSelect(*MI, LocalMIs))) {
1852 // MI is deleted.
1853 LocalMIs.erase(MI);
1854 Changed = true;
1855 continue;
1856 }
1857
1858 if (MI->isConditionalBranch() && optimizeCondBranch(*MI)) {
1859 Changed = true;
1860 continue;
1861 }
1862
1863 if (isCoalescableCopy(*MI) && optimizeCoalescableCopy(*MI)) {
1864 // MI is just rewritten.
1865 Changed = true;
1866 continue;
1867 }
1868
1869 if (MI->isCopy() && (foldRedundantCopy(*MI) ||
1870 foldRedundantNAPhysCopy(*MI, NAPhysToVirtMIs))) {
1871 LocalMIs.erase(MI);
1872 LLVM_DEBUG(dbgs() << "Deleting redundant copy: " << *MI << "\n");
1873 MI->eraseFromParent();
1874 Changed = true;
1875 continue;
1876 }
1877
1878 if (isMoveImmediate(*MI, ImmDefRegs, ImmDefMIs)) {
1879 SeenMoveImm = true;
1880 } else {
1881 Changed |= optimizeExtInstr(*MI, MBB, LocalMIs);
1882 // optimizeExtInstr might have created new instructions after MI
1883 // and before the already incremented MII. Adjust MII so that the
1884 // next iteration sees the new instructions.
1885 MII = MI;
1886 ++MII;
1887 if (SeenMoveImm) {
1888 bool Deleted;
1889 Changed |= foldImmediate(*MI, ImmDefRegs, ImmDefMIs, Deleted);
1890 if (Deleted) {
1891 LocalMIs.erase(MI);
1892 continue;
1893 }
1894 }
1895 }
1896
1897 // Check whether MI is a load candidate for folding into a later
1898 // instruction. If MI is not a candidate, check whether we can fold an
1899 // earlier load into MI.
1900 if (!isLoadFoldable(*MI, FoldAsLoadDefCandidates) &&
1901 !FoldAsLoadDefCandidates.empty()) {
1902
1903 // We visit each operand even after successfully folding a previous
1904 // one. This allows us to fold multiple loads into a single
1905 // instruction. We do assume that optimizeLoadInstr doesn't insert
1906 // foldable uses earlier in the argument list. Since we don't restart
1907 // iteration, we'd miss such cases.
1908 const MCInstrDesc &MIDesc = MI->getDesc();
1909 for (unsigned i = MIDesc.getNumDefs(); i != MI->getNumOperands(); ++i) {
1910 const MachineOperand &MOp = MI->getOperand(i);
1911 if (!MOp.isReg())
1912 continue;
1913 Register FoldAsLoadDefReg = MOp.getReg();
1914 if (FoldAsLoadDefCandidates.count(FoldAsLoadDefReg)) {
1915 // We need to fold load after optimizeCmpInstr, since
1916 // optimizeCmpInstr can enable folding by converting SUB to CMP.
1917 Register FoldedReg = FoldAsLoadDefReg;
1918 if (MachineInstr *FoldMI =
1919 foldLoadInto(MF, *MI, FoldAsLoadDefReg, LocalMIs)) {
1920 FoldAsLoadDefCandidates.erase(FoldedReg);
1921 // MI is replaced with FoldMI so we can continue trying to fold
1922 Changed = true;
1923 MI = FoldMI;
1924 }
1925 }
1926 }
1927 }
1928
1929 // If we run into an instruction we can't fold across, discard
1930 // the load candidates. Note: We might be able to fold *into* this
1931 // instruction, so this needs to be after the folding logic.
1932 if (MI->isLoadFoldBarrier()) {
1933 LLVM_DEBUG(dbgs() << "Encountered load fold barrier on " << *MI);
1934 FoldAsLoadDefCandidates.clear();
1935 }
1936 }
1937 }
1938
1939 MF.resetDelegate(this);
1940 return Changed;
1941}
1942
1943ValueTrackerResult ValueTracker::getNextSourceFromCopy() {
1944 assert(Def->isCopy() && "Invalid definition");
1945 // Copy instruction are supposed to be: Def = Src.
1946 // If someone breaks this assumption, bad things will happen everywhere.
1947 // There may be implicit uses preventing the copy to be moved across
1948 // some target specific register definitions
1949 assert(Def->getNumOperands() - Def->getNumImplicitOperands() == 2 &&
1950 "Invalid number of operands");
1951 assert(!Def->hasImplicitDef() && "Only implicit uses are allowed");
1952 assert(!Def->getOperand(DefIdx).getSubReg() && "no subregister defs in SSA");
1953
1954 // Otherwise, we want the whole source.
1955 const MachineOperand &Src = Def->getOperand(1);
1956 if (Src.isUndef())
1957 return ValueTrackerResult();
1958
1959 Register SrcReg = Src.getReg();
1960 unsigned SubReg = Src.getSubReg();
1961 if (DefSubReg) {
1962 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
1963 SubReg = TRI->composeSubRegIndices(SubReg, DefSubReg);
1964
1965 if (SrcReg.isVirtual()) {
1966 // TODO: Try constraining on rewrite if we can
1967 const TargetRegisterClass *RegRC = MRI.getRegClass(SrcReg);
1968 if (!TRI->isSubRegValidForRegClass(RegRC, SubReg))
1969 return ValueTrackerResult();
1970 } else {
1971 if (!TRI->getSubReg(SrcReg, SubReg))
1972 return ValueTrackerResult();
1973 }
1974 }
1975
1976 return ValueTrackerResult(SrcReg, SubReg);
1977}
1978
1979ValueTrackerResult ValueTracker::getNextSourceFromBitcast() {
1980 assert(Def->isBitcast() && "Invalid definition");
1981
1982 // Bail if there are effects that a plain copy will not expose.
1983 if (Def->mayRaiseFPException() || Def->hasUnmodeledSideEffects())
1984 return ValueTrackerResult();
1985
1986 // Bitcasts with more than one def are not supported.
1987 if (Def->getDesc().getNumDefs() != 1)
1988 return ValueTrackerResult();
1989
1990 assert(!Def->getOperand(DefIdx).getSubReg() && "no subregister defs in SSA");
1991
1992 unsigned SrcIdx = Def->getNumOperands();
1993 for (unsigned OpIdx = DefIdx + 1, EndOpIdx = SrcIdx; OpIdx != EndOpIdx;
1994 ++OpIdx) {
1995 const MachineOperand &MO = Def->getOperand(OpIdx);
1996 if (!MO.isReg() || !MO.getReg())
1997 continue;
1998 // Ignore dead implicit defs.
1999 if (MO.isImplicit() && MO.isDead())
2000 continue;
2001 assert(!MO.isDef() && "We should have skipped all the definitions by now");
2002 if (SrcIdx != EndOpIdx)
2003 // Multiple sources?
2004 return ValueTrackerResult();
2005 SrcIdx = OpIdx;
2006 }
2007
2008 // In some rare case, Def has no input, SrcIdx is out of bound,
2009 // getOperand(SrcIdx) will fail below.
2010 if (SrcIdx >= Def->getNumOperands())
2011 return ValueTrackerResult();
2012
2013 const MachineOperand &DefOp = Def->getOperand(DefIdx);
2014
2015 // Stop when any user of the bitcast is a SUBREG_TO_REG, replacing with a COPY
2016 // will break the assumed guarantees for the upper bits.
2017 for (const MachineInstr &UseMI : MRI.use_nodbg_instructions(DefOp.getReg())) {
2018 if (UseMI.isSubregToReg())
2019 return ValueTrackerResult();
2020 }
2021
2022 const MachineOperand &Src = Def->getOperand(SrcIdx);
2023 if (Src.isUndef())
2024 return ValueTrackerResult();
2025 return ValueTrackerResult(Src.getReg(), Src.getSubReg());
2026}
2027
2028ValueTrackerResult ValueTracker::getNextSourceFromRegSequence() {
2029 assert((Def->isRegSequence() || Def->isRegSequenceLike()) &&
2030 "Invalid definition");
2031
2032 assert(!Def->getOperand(DefIdx).getSubReg() && "illegal subregister def");
2033
2035 if (!TII->getRegSequenceInputs(*Def, DefIdx, RegSeqInputRegs))
2036 return ValueTrackerResult();
2037
2038 // We are looking at:
2039 // Def = REG_SEQUENCE v0, sub0, v1, sub1, ...
2040 //
2041 // Check if one of the operands exactly defines the subreg we are interested
2042 // in.
2043 for (const RegSubRegPairAndIdx &RegSeqInput : RegSeqInputRegs) {
2044 if (RegSeqInput.SubIdx == DefSubReg)
2045 return ValueTrackerResult(RegSeqInput.Reg, RegSeqInput.SubReg);
2046 }
2047
2048 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
2049
2050 // If we did not find an exact match, see if we can do a composition to
2051 // extract a sub-subregister.
2052 for (const RegSubRegPairAndIdx &RegSeqInput : RegSeqInputRegs) {
2053 LaneBitmask DefMask = TRI->getSubRegIndexLaneMask(DefSubReg);
2054 LaneBitmask ThisOpRegMask = TRI->getSubRegIndexLaneMask(RegSeqInput.SubIdx);
2055
2056 // Check that this extract reads a subset of this single reg_sequence input.
2057 //
2058 // FIXME: We should be able to filter this in terms of the indexes directly
2059 // without checking the lanemasks.
2060 if ((DefMask & ThisOpRegMask) != DefMask)
2061 continue;
2062
2063 unsigned ReverseDefCompose =
2064 TRI->reverseComposeSubRegIndices(RegSeqInput.SubIdx, DefSubReg);
2065 if (!ReverseDefCompose)
2066 continue;
2067
2068 unsigned ComposedDefInSrcReg1 =
2069 TRI->composeSubRegIndices(RegSeqInput.SubReg, ReverseDefCompose);
2070
2071 // TODO: We should be able to defer checking if the result register class
2072 // supports the index to continue looking for a rewritable source.
2073 //
2074 // TODO: Should we modify the register class to support the index?
2075 const TargetRegisterClass *SrcRC = MRI.getRegClass(RegSeqInput.Reg);
2076 if (!TRI->isSubRegValidForRegClass(SrcRC, ComposedDefInSrcReg1))
2077 return ValueTrackerResult();
2078
2079 return ValueTrackerResult(RegSeqInput.Reg, ComposedDefInSrcReg1);
2080 }
2081
2082 // If the subreg we are tracking is super-defined by another subreg,
2083 // we could follow this value. However, this would require to compose
2084 // the subreg and we do not do that for now.
2085 return ValueTrackerResult();
2086}
2087
2088ValueTrackerResult ValueTracker::getNextSourceFromInsertSubreg() {
2089 assert((Def->isInsertSubreg() || Def->isInsertSubregLike()) &&
2090 "Invalid definition");
2091 assert(!Def->getOperand(DefIdx).getSubReg() && "no subreg defs in SSA");
2092
2094 RegSubRegPairAndIdx InsertedReg;
2095 if (!TII->getInsertSubregInputs(*Def, DefIdx, BaseReg, InsertedReg))
2096 return ValueTrackerResult();
2097
2098 // We are looking at:
2099 // Def = INSERT_SUBREG v0, v1, sub1
2100 // There are two cases:
2101 // 1. DefSubReg == sub1, get v1.
2102 // 2. DefSubReg != sub1, the value may be available through v0.
2103
2104 // #1 Check if the inserted register matches the required sub index.
2105 if (InsertedReg.SubIdx == DefSubReg) {
2106 return ValueTrackerResult(InsertedReg.Reg, InsertedReg.SubReg);
2107 }
2108 // #2 Otherwise, if the sub register we are looking for is not partial
2109 // defined by the inserted element, we can look through the main
2110 // register (v0).
2111 const MachineOperand &MODef = Def->getOperand(DefIdx);
2112 // If the result register (Def) and the base register (v0) do not
2113 // have the same register class or if we have to compose
2114 // subregisters, bail out.
2115 if (MRI.getRegClass(MODef.getReg()) != MRI.getRegClass(BaseReg.Reg) ||
2116 BaseReg.SubReg)
2117 return ValueTrackerResult();
2118
2119 // Get the TRI and check if the inserted sub-register overlaps with the
2120 // sub-register we are tracking.
2121 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
2122 if ((TRI->getSubRegIndexLaneMask(DefSubReg) &
2123 TRI->getSubRegIndexLaneMask(InsertedReg.SubIdx))
2124 .any())
2125 return ValueTrackerResult();
2126 // At this point, the value is available in v0 via the same subreg
2127 // we used for Def.
2128 return ValueTrackerResult(BaseReg.Reg, DefSubReg);
2129}
2130
2131ValueTrackerResult ValueTracker::getNextSourceFromExtractSubreg() {
2132 assert((Def->isExtractSubreg() || Def->isExtractSubregLike()) &&
2133 "Invalid definition");
2134 // We are looking at:
2135 // Def = EXTRACT_SUBREG v0, sub0
2136
2137 // Bail if we have to compose sub registers.
2138 // Indeed, if DefSubReg != 0, we would have to compose it with sub0.
2139 if (DefSubReg)
2140 return ValueTrackerResult();
2141
2142 RegSubRegPairAndIdx ExtractSubregInputReg;
2143 if (!TII->getExtractSubregInputs(*Def, DefIdx, ExtractSubregInputReg))
2144 return ValueTrackerResult();
2145
2146 // Bail if we have to compose sub registers.
2147 // Likewise, if v0.subreg != 0, we would have to compose v0.subreg with sub0.
2148 if (ExtractSubregInputReg.SubReg)
2149 return ValueTrackerResult();
2150 // Otherwise, the value is available in the v0.sub0.
2151 return ValueTrackerResult(ExtractSubregInputReg.Reg,
2152 ExtractSubregInputReg.SubIdx);
2153}
2154
2155ValueTrackerResult ValueTracker::getNextSourceFromSubregToReg() {
2156 assert(Def->isSubregToReg() && "Invalid definition");
2157 // We are looking at:
2158 // Def = SUBREG_TO_REG v0, sub0
2159
2160 // Bail if we have to compose sub registers.
2161 // If DefSubReg != sub0, we would have to check that all the bits
2162 // we track are included in sub0 and if yes, we would have to
2163 // determine the right subreg in v0.
2164 if (DefSubReg != Def->getOperand(2).getImm())
2165 return ValueTrackerResult();
2166 // Bail if we have to compose sub registers.
2167 // Likewise, if v0.subreg != 0, we would have to compose it with sub0.
2168 if (Def->getOperand(1).getSubReg())
2169 return ValueTrackerResult();
2170
2171 return ValueTrackerResult(Def->getOperand(1).getReg(),
2172 Def->getOperand(2).getImm());
2173}
2174
2175/// Explore each PHI incoming operand and return its sources.
2176ValueTrackerResult ValueTracker::getNextSourceFromPHI() {
2177 assert(Def->isPHI() && "Invalid definition");
2178 ValueTrackerResult Res;
2179
2180 // Return all register sources for PHI instructions.
2181 for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) {
2182 const MachineOperand &MO = Def->getOperand(i);
2183 assert(MO.isReg() && "Invalid PHI instruction");
2184 // We have no code to deal with undef operands. They shouldn't happen in
2185 // normal programs anyway.
2186 if (MO.isUndef())
2187 return ValueTrackerResult();
2188 Res.addSource(MO.getReg(), MO.getSubReg());
2189 }
2190
2191 return Res;
2192}
2193
2194ValueTrackerResult ValueTracker::getNextSourceImpl() {
2195 assert(Def && "This method needs a valid definition");
2196
2197 assert(((Def->getOperand(DefIdx).isDef() &&
2198 (DefIdx < Def->getDesc().getNumDefs() ||
2199 Def->getDesc().isVariadic())) ||
2200 Def->getOperand(DefIdx).isImplicit()) &&
2201 "Invalid DefIdx");
2202 if (Def->isCopy())
2203 return getNextSourceFromCopy();
2204 if (Def->isBitcast())
2205 return getNextSourceFromBitcast();
2206 // All the remaining cases involve "complex" instructions.
2207 // Bail if we did not ask for the advanced tracking.
2208 if (!Opts.adv_copy_opt)
2209 return ValueTrackerResult();
2210 if (Def->isRegSequence() || Def->isRegSequenceLike())
2211 return getNextSourceFromRegSequence();
2212 if (Def->isInsertSubreg() || Def->isInsertSubregLike())
2213 return getNextSourceFromInsertSubreg();
2214 if (Def->isExtractSubreg() || Def->isExtractSubregLike())
2215 return getNextSourceFromExtractSubreg();
2216 if (Def->isSubregToReg())
2217 return getNextSourceFromSubregToReg();
2218 if (Def->isPHI())
2219 return getNextSourceFromPHI();
2220 return ValueTrackerResult();
2221}
2222
2223ValueTrackerResult ValueTracker::getNextSource() {
2224 // If we reach a point where we cannot move up in the use-def chain,
2225 // there is nothing we can get.
2226 if (!Def)
2227 return ValueTrackerResult();
2228
2229 ValueTrackerResult Res = getNextSourceImpl();
2230 if (Res.isValid()) {
2231 // Update definition, definition index, and subregister for the
2232 // next call of getNextSource.
2233 // Update the current register.
2234 bool OneRegSrc = Res.getNumSources() == 1;
2235 if (OneRegSrc)
2236 Reg = Res.getSrcReg(0);
2237 // Update the result before moving up in the use-def chain
2238 // with the instruction containing the last found sources.
2239 Res.setInst(Def);
2240
2241 // If we can still move up in the use-def chain, move to the next
2242 // definition.
2243 if (!Reg.isPhysical() && OneRegSrc) {
2245 if (DI != MRI.def_end()) {
2246 Def = DI->getParent();
2247 DefIdx = DI.getOperandNo();
2248 DefSubReg = Res.getSrcSubReg(0);
2249 } else {
2250 Def = nullptr;
2251 }
2252 return Res;
2253 }
2254 }
2255 // If we end up here, this means we will not be able to find another source
2256 // for the next iteration. Make sure any new call to getNextSource bails out
2257 // early by cutting the use-def chain.
2258 Def = nullptr;
2259 return Res;
2260}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Rewrite undef for PHI
MachineBasicBlock & MBB
This file defines the DenseMap class.
#define DEBUG_TYPE
const HexagonInstrInfo * TII
#define _
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define I(x, y, z)
Definition MD5.cpp:57
TargetInstrInfo::RegSubRegPair RegSubRegPair
Register Reg
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
uint64_t IntrinsicInst * II
if(PassOpts->AAPipeline)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
static bool isVirtualRegisterOperand(MachineOperand &MO)
\bried Returns true if MO is a virtual register operand.
static MachineInstr & insertPHI(MachineRegisterInfo &MRI, const TargetInstrInfo &TII, const SmallVectorImpl< RegSubRegPair > &SrcRegs, MachineInstr &OrigPHI)
Insert a PHI instruction with incoming edges SrcRegs that are guaranteed to have the same register cl...
static cl::opt< bool > Aggressive("aggressive-ext-opt", cl::Hidden, cl::desc("Aggressive extension optimization"))
TargetInstrInfo::RegSubRegPairAndIdx RegSubRegPairAndIdx
static RegSubRegPair getNewSource(MachineRegisterInfo *MRI, const TargetInstrInfo *TII, RegSubRegPair Def, const PeepholeOptimizer::RewriteMapTy &RewriteMap, bool HandleMultipleSources=true)
Given a Def.Reg and Def.SubReg pair, use RewriteMap to find the new source to use for rewrite.
MachineRegisterInfo & MRI
Remove Loads Into Fake Uses
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
virt reg Virtual Register Rewriter
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition Pass.cpp:280
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:766
iterator end()
Definition DenseMap.h:686
bool erase(const KeyT &Val)
Definition DenseMap.h:930
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Definition DenseMap.h:793
bool remove_if(Predicate Pred)
Remove entries that match the given predicate.
Definition DenseMap.h:946
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:827
bool analyzeCompare(const MachineInstr &MI, Register &SrcReg, Register &SrcReg2, int64_t &Mask, int64_t &Value) const override
For a comparison instruction, return the source registers in SrcReg and SrcReg2 if having two registe...
bool isLoopHeader(const BlockT *BB) const
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
An RAII based helper class to modify MachineFunctionProperties when running pass.
MachineInstrBundleIterator< MachineInstr > iterator
Analysis pass which computes a MachineDominatorTree.
Analysis pass which computes a MachineDominatorTree.
bool dominates(const MachineInstr *A, const MachineInstr *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void moveAdditionalCallInfo(const MachineInstr *Old, const MachineInstr *New)
Move the call site info from Old to \New call site info.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
void setDelegate(Delegate *delegate)
Set the delegate.
const MachineInstrBuilder & addReg(Register RegNo, RegState Flags={}, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
LLVM_ABI bool isIdenticalTo(const MachineInstr &Other, MICheckType Check=CheckDefs) const
Return true if this instruction is identical to Other.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
LLVM_ABI MachineInstrBundleIterator< MachineInstr > eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
bool canFoldAsLoad(QueryType Type=IgnoreBundle) const
Return true for instructions that can be folded as memory operands in other instructions.
Analysis pass that exposes the MachineLoopInfo for a machine function.
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
MachineBasicBlock * getMBB() const
LLVM_ABI void setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
void setIsUndef(bool Val=true)
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
unsigned getOperandNo() const
getOperandNo - Return the operand # of this MachineOperand in its MachineInstr.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
LLVM_ABI bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
LLVM_ABI void markUsesInDebugValueAsUndef(Register Reg) const
markUsesInDebugValueAsUndef - Mark every DBG_VALUE referencing the specified register as undefined wh...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
LLVM_ABI LLVM_READONLY MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
def_iterator def_begin(Register RegNo) const
LLVM_ABI Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
use_instr_nodbg_iterator use_instr_nodbg_begin(Register RegNo) const
LLVM_ABI bool hasOneNonDBGUser(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug instruction using the specified regis...
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
defusechain_iterator< false, true, false, true, false > def_iterator
def_iterator/def_begin/def_end - Walk all defs of the specified register.
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
static def_iterator def_end()
const TargetRegisterInfo * getTargetRegisterInfo() const
LLVM_ABI const TargetRegisterClass * constrainRegClass(Register Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
LLVM_ABI void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
LLVM_ABI MachineInstr * getOneNonDBGUser(Register RegNo) const
If the register has a single non-Debug instruction using the specified register, returns it; otherwis...
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
Wrapper class representing virtual and physical registers.
Definition Register.h:20
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:79
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition Register.h:83
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition SmallSet.h:134
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition SmallSet.h:176
bool empty() const
Definition SmallSet.h:169
bool erase(const T &V)
Definition SmallSet.h:200
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition SmallSet.h:184
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
static const unsigned CommuteAnyOperandIndex
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
self_iterator getIterator()
Definition ilist_node.h:123
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
MCInstrDesc const & getDesc(MCInstrInfo const &MCII, MCInst const &MCI)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< DefNode * > Def
Definition RDFGraph.h:384
BaseReg
Stack frame base register. Bit 0 of FREInfo.Info.
Definition SFrame.h:77
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
LLVM_ABI char & PeepholeOptimizerLegacyID
PeepholeOptimizer - This pass performs peephole optimizations - like extension and comparison elimina...
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1769
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
@ Other
Any other memory.
Definition ModRef.h:68
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
MCRegisterClass TargetRegisterClass
Definition FastISel.h:58
A pair composed of a pair of a register and a sub-register index, and another sub-register index.
A pair composed of a register and a sub-register index.