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 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 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