LLVM  11.0.0git
TailDuplicator.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/TailDuplicator.h ----------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the TailDuplicator class. Used by the
10 // TailDuplication pass, and MachineBlockPlacement.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CODEGEN_TAILDUPLICATOR_H
15 #define LLVM_CODEGEN_TAILDUPLICATOR_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallVector.h"
23 #include <utility>
24 #include <vector>
25 
26 namespace llvm {
27 
28 class MachineBasicBlock;
29 class MachineBlockFrequencyInfo;
30 class MachineBranchProbabilityInfo;
31 class MachineFunction;
32 class MachineInstr;
33 class MachineModuleInfo;
34 class MachineRegisterInfo;
35 class ProfileSummaryInfo;
36 class TargetRegisterInfo;
37 
38 /// Utility class to perform tail duplication.
40  const TargetInstrInfo *TII;
41  const TargetRegisterInfo *TRI;
42  const MachineBranchProbabilityInfo *MBPI;
43  const MachineModuleInfo *MMI;
45  MachineFunction *MF;
46  MBFIWrapper *MBFI;
47  ProfileSummaryInfo *PSI;
48  bool PreRegAlloc;
49  bool LayoutMode;
50  unsigned TailDupSize;
51 
52  // A list of virtual registers for which to update SSA form.
53  SmallVector<Register, 16> SSAUpdateVRs;
54 
55  // For each virtual register in SSAUpdateVals keep a list of source virtual
56  // registers.
57  using AvailableValsTy = std::vector<std::pair<MachineBasicBlock *, Register>>;
58 
60 
61 public:
62  /// Prepare to run on a specific machine function.
63  /// @param MF - Function that will be processed
64  /// @param PreRegAlloc - true if used before register allocation
65  /// @param MBPI - Branch Probability Info. Used to propagate correct
66  /// probabilities when modifying the CFG.
67  /// @param LayoutMode - When true, don't use the existing layout to make
68  /// decisions.
69  /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
70  /// default implies using the command line value TailDupSize.
71  void initMF(MachineFunction &MF, bool PreRegAlloc,
72  const MachineBranchProbabilityInfo *MBPI,
73  MBFIWrapper *MBFI,
74  ProfileSummaryInfo *PSI,
75  bool LayoutMode, unsigned TailDupSize = 0);
76 
77  bool tailDuplicateBlocks();
78  static bool isSimpleBB(MachineBasicBlock *TailBB);
79  bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
80 
81  /// Returns true if TailBB can successfully be duplicated into PredBB
83 
84  /// Tail duplicate a single basic block into its predecessors, and then clean
85  /// up.
86  /// If \p DuplicatePreds is not null, it will be updated to contain the list
87  /// of predecessors that received a copy of \p MBB.
88  /// If \p RemovalCallback is non-null. It will be called before MBB is
89  /// deleted.
90  /// If \p CandidatePtr is not null, duplicate into these blocks only.
92  bool IsSimple, MachineBasicBlock *MBB,
93  MachineBasicBlock *ForcedLayoutPred,
94  SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
95  function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr,
96  SmallVectorImpl<MachineBasicBlock *> *CandidatePtr = nullptr);
97 
98 private:
100 
101  void addSSAUpdateEntry(Register OrigReg, Register NewReg,
102  MachineBasicBlock *BB);
103  void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
104  MachineBasicBlock *PredBB,
106  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
107  const DenseSet<Register> &UsedByPhi, bool Remove);
108  void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
109  MachineBasicBlock *PredBB,
111  const DenseSet<Register> &UsedByPhi);
112  void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
115  bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
116  bool duplicateSimpleBB(MachineBasicBlock *TailBB,
118  const DenseSet<Register> &RegsUsedByPhi,
120  bool tailDuplicate(bool IsSimple,
121  MachineBasicBlock *TailBB,
122  MachineBasicBlock *ForcedLayoutPred,
126  void appendCopies(MachineBasicBlock *MBB,
127  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
129 
130  void removeDeadBlock(
131  MachineBasicBlock *MBB,
132  function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
133 };
134 
135 } // end namespace llvm
136 
137 #endif // LLVM_CODEGEN_TAILDUPLICATOR_H
bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB)
Determine if it is profitable to duplicate this block.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Implements a dense probed hash-table based set.
Definition: DenseSet.h:255
Analysis providing profile information.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
void initMF(MachineFunction &MF, bool PreRegAlloc, const MachineBranchProbabilityInfo *MBPI, MBFIWrapper *MBFI, ProfileSummaryInfo *PSI, bool LayoutMode, unsigned TailDupSize=0)
Prepare to run on a specific machine function.
MachineBasicBlock & MBB
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
bool tailDuplicateBlocks()
Look for small blocks that are unconditionally branched to and do not fall through.
TargetInstrInfo - Interface to description of machine instruction set.
static bool isSimpleBB(MachineBasicBlock *TailBB)
True if this BB has only one unconditional jump.
TargetInstrInfo::RegSubRegPair RegSubRegPair
bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB)
Returns true if TailBB can successfully be duplicated into PredBB.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
A pair composed of a register and a sub-register index.
SI Lower i1 Copies
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:62
bool tailDuplicateAndUpdate(bool IsSimple, MachineBasicBlock *MBB, MachineBasicBlock *ForcedLayoutPred, SmallVectorImpl< MachineBasicBlock *> *DuplicatedPreds=nullptr, function_ref< void(MachineBasicBlock *)> *RemovalCallback=nullptr, SmallVectorImpl< MachineBasicBlock *> *CandidatePtr=nullptr)
Tail duplicate a single basic block into its predecessors, and then clean up.
IRTranslator LLVM IR MI
Utility class to perform tail duplication.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This class contains meta information specific to a module.