TailDuplicator.h revision 360784 
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/TargetInstrInfo.h"
22#include <utility>
23#include <vector>
24
25namespace llvm {
26
27class MachineBasicBlock;
28class MachineBlockFrequencyInfo;
29class MachineBranchProbabilityInfo;
30class MachineFunction;
31class MachineInstr;
32class MachineModuleInfo;
33class MachineRegisterInfo;
34class ProfileSummaryInfo;
35class TargetRegisterInfo;
36
37/// Utility class to perform tail duplication.
38class TailDuplicator {
39  const TargetInstrInfo *TII;
40  const TargetRegisterInfo *TRI;
41  const MachineBranchProbabilityInfo *MBPI;
42  const MachineModuleInfo *MMI;
43  MachineRegisterInfo *MRI;
44  MachineFunction *MF;
45  const MachineBlockFrequencyInfo *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<unsigned, 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 *, unsigned>>;
57
58  DenseMap<unsigned, 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              const MachineBlockFrequencyInfo *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  bool tailDuplicateAndUpdate(
90      bool IsSimple, MachineBasicBlock *MBB,
91      MachineBasicBlock *ForcedLayoutPred,
92      SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
93      function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
94
95private:
96  using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
97
98  void addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
99                         MachineBasicBlock *BB);
100  void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
101                  MachineBasicBlock *PredBB,
102                  DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
103                  SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies,
104                  const DenseSet<unsigned> &UsedByPhi, bool Remove);
105  void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
106                            MachineBasicBlock *PredBB,
107                            DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
108                            const DenseSet<unsigned> &UsedByPhi);
109  void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
110                            SmallVectorImpl<MachineBasicBlock *> &TDBBs,
111                            SmallSetVector<MachineBasicBlock *, 8> &Succs);
112  bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
113  bool duplicateSimpleBB(MachineBasicBlock *TailBB,
114                         SmallVectorImpl<MachineBasicBlock *> &TDBBs,
115                         const DenseSet<unsigned> &RegsUsedByPhi,
116                         SmallVectorImpl<MachineInstr *> &Copies);
117  bool tailDuplicate(bool IsSimple,
118                     MachineBasicBlock *TailBB,
119                     MachineBasicBlock *ForcedLayoutPred,
120                     SmallVectorImpl<MachineBasicBlock *> &TDBBs,
121                     SmallVectorImpl<MachineInstr *> &Copies);
122  void appendCopies(MachineBasicBlock *MBB,
123                 SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
124                 SmallVectorImpl<MachineInstr *> &Copies);
125
126  void removeDeadBlock(
127      MachineBasicBlock *MBB,
128      function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
129};
130
131} // end namespace llvm
132
133#endif // LLVM_CODEGEN_TAILDUPLICATOR_H
134