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"
21 #include "llvm/CodeGen/MBFIWrapper.h"
22 #include "llvm/CodeGen/TargetInstrInfo.h"
23 #include <utility>
24 #include <vector>
25 
26 namespace llvm {
27 
28 class MachineBasicBlock;
29 class MachineBranchProbabilityInfo;
30 class MachineFunction;
31 class MachineInstr;
32 class MachineModuleInfo;
33 class MachineRegisterInfo;
34 class ProfileSummaryInfo;
35 class TargetRegisterInfo;
36 
37 /// Utility class to perform tail duplication.
38 class TailDuplicator {
39   const TargetInstrInfo *TII;
40   const TargetRegisterInfo *TRI;
41   const MachineBranchProbabilityInfo *MBPI;
42   const MachineModuleInfo *MMI;
43   MachineRegisterInfo *MRI;
44   MachineFunction *MF;
45   MBFIWrapper *MBFI;
46   ProfileSummaryInfo *PSI;
47   bool PreRegAlloc;
48   bool LayoutMode;
49   unsigned TailDupSize;
50 
51   // A list of virtual registers for which to update SSA form.
52   SmallVector<Register, 16> SSAUpdateVRs;
53 
54   // For each virtual register in SSAUpdateVals keep a list of source virtual
55   // registers.
56   using AvailableValsTy = std::vector<std::pair<MachineBasicBlock *, Register>>;
57 
58   DenseMap<Register, AvailableValsTy> SSAUpdateVals;
59 
60 public:
61   /// Prepare to run on a specific machine function.
62   /// @param MF - Function that will be processed
63   /// @param PreRegAlloc - true if used before register allocation
64   /// @param MBPI - Branch Probability Info. Used to propagate correct
65   ///     probabilities when modifying the CFG.
66   /// @param LayoutMode - When true, don't use the existing layout to make
67   ///     decisions.
68   /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
69   ///     default implies using the command line value TailDupSize.
70   void initMF(MachineFunction &MF, bool PreRegAlloc,
71               const MachineBranchProbabilityInfo *MBPI,
72               MBFIWrapper *MBFI,
73               ProfileSummaryInfo *PSI,
74               bool LayoutMode, unsigned TailDupSize = 0);
75 
76   bool tailDuplicateBlocks();
77   static bool isSimpleBB(MachineBasicBlock *TailBB);
78   bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
79 
80   /// Returns true if TailBB can successfully be duplicated into PredBB
81   bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB);
82 
83   /// Tail duplicate a single basic block into its predecessors, and then clean
84   /// up.
85   /// If \p DuplicatePreds is not null, it will be updated to contain the list
86   /// of predecessors that received a copy of \p MBB.
87   /// If \p RemovalCallback is non-null. It will be called before MBB is
88   /// deleted.
89   /// If \p CandidatePtr is not null, duplicate into these blocks only.
90   bool tailDuplicateAndUpdate(
91       bool IsSimple, MachineBasicBlock *MBB,
92       MachineBasicBlock *ForcedLayoutPred,
93       SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
94       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr,
95       SmallVectorImpl<MachineBasicBlock *> *CandidatePtr = nullptr);
96 
97 private:
98   using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
99 
100   void addSSAUpdateEntry(Register OrigReg, Register NewReg,
101                          MachineBasicBlock *BB);
102   void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
103                   MachineBasicBlock *PredBB,
104                   DenseMap<Register, RegSubRegPair> &LocalVRMap,
105                   SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
106                   const DenseSet<Register> &UsedByPhi, bool Remove);
107   void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
108                             MachineBasicBlock *PredBB,
109                             DenseMap<Register, RegSubRegPair> &LocalVRMap,
110                             const DenseSet<Register> &UsedByPhi);
111   void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
112                             SmallVectorImpl<MachineBasicBlock *> &TDBBs,
113                             SmallSetVector<MachineBasicBlock *, 8> &Succs);
114   bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
115   bool duplicateSimpleBB(MachineBasicBlock *TailBB,
116                          SmallVectorImpl<MachineBasicBlock *> &TDBBs,
117                          const DenseSet<Register> &RegsUsedByPhi,
118                          SmallVectorImpl<MachineInstr *> &Copies);
119   bool tailDuplicate(bool IsSimple,
120                      MachineBasicBlock *TailBB,
121                      MachineBasicBlock *ForcedLayoutPred,
122                      SmallVectorImpl<MachineBasicBlock *> &TDBBs,
123                      SmallVectorImpl<MachineInstr *> &Copies,
124                      SmallVectorImpl<MachineBasicBlock *> *CandidatePtr);
125   void appendCopies(MachineBasicBlock *MBB,
126                  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
127                  SmallVectorImpl<MachineInstr *> &Copies);
128 
129   void removeDeadBlock(
130       MachineBasicBlock *MBB,
131       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
132 };
133 
134 } // end namespace llvm
135 
136 #endif // LLVM_CODEGEN_TAILDUPLICATOR_H
137