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
24namespace llvm {
25
26template <typename T, unsigned int N> class SmallSetVector;
27template <typename Fn> class function_ref;
28class MBFIWrapper;
29class MachineBasicBlock;
30class MachineBranchProbabilityInfo;
31class MachineFunction;
32class MachineInstr;
33class MachineModuleInfo;
34class MachineRegisterInfo;
35class ProfileSummaryInfo;
36class TargetRegisterInfo;
37
38/// Utility class to perform tail duplication.
39class TailDuplicator {
40 const TargetInstrInfo *TII;
41 const TargetRegisterInfo *TRI;
42 const MachineBranchProbabilityInfo *MBPI;
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
60public:
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
97private:
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 bool tailDuplicate(bool IsSimple,
119 MachineBasicBlock *TailBB,
120 MachineBasicBlock *ForcedLayoutPred,
121 SmallVectorImpl<MachineBasicBlock *> &TDBBs,
122 SmallVectorImpl<MachineInstr *> &Copies,
123 SmallVectorImpl<MachineBasicBlock *> *CandidatePtr);
124 void appendCopies(MachineBasicBlock *MBB,
125 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
126 SmallVectorImpl<MachineInstr *> &Copies);
127
128 void removeDeadBlock(
129 MachineBasicBlock *MBB,
130 function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
131};
132
133} // end namespace llvm
134
135#endif // LLVM_CODEGEN_TAILDUPLICATOR_H
136