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