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/SmallVector.h"
20 #include "llvm/CodeGen/TargetInstrInfo.h"
21 #include <utility>
22 #include <vector>
23 
24 namespace llvm {
25 
26 template <typename T, unsigned int N> class SmallSetVector;
27 template <typename Fn> class function_ref;
28 class MBFIWrapper;
29 class MachineBasicBlock;
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.
39 class TailDuplicator {
40   const TargetInstrInfo *TII;
41   const TargetRegisterInfo *TRI;
42   const MachineBranchProbabilityInfo *MBPI;
43   const MachineModuleInfo *MMI;
44   MachineRegisterInfo *MRI;
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 
59   DenseMap<Register, AvailableValsTy> SSAUpdateVals;
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
82   bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *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.
91   bool tailDuplicateAndUpdate(
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:
99   using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
100 
101   void addSSAUpdateEntry(Register OrigReg, Register NewReg,
102                          MachineBasicBlock *BB);
103   void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
104                   MachineBasicBlock *PredBB,
105                   DenseMap<Register, RegSubRegPair> &LocalVRMap,
106                   SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
107                   const DenseSet<Register> &UsedByPhi, bool Remove);
108   void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
109                             MachineBasicBlock *PredBB,
110                             DenseMap<Register, RegSubRegPair> &LocalVRMap,
111                             const DenseSet<Register> &UsedByPhi);
112   void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
113                             SmallVectorImpl<MachineBasicBlock *> &TDBBs,
114                             SmallSetVector<MachineBasicBlock *, 8> &Succs);
115   bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
116   bool duplicateSimpleBB(MachineBasicBlock *TailBB,
117                          SmallVectorImpl<MachineBasicBlock *> &TDBBs,
118                          const DenseSet<Register> &RegsUsedByPhi);
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