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/MBFIWrapper.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 ProfileSummaryInfo; 35 class TargetRegisterInfo; 36 37 /// Utility class to perform tail duplication. 38 class TailDuplicator { 39 const TargetInstrInfo *TII; 40 const TargetRegisterInfo *TRI; 41 const MachineBranchProbabilityInfo *MBPI; 42 const MachineModuleInfo *MMI; 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 SmallVectorImpl<MachineInstr *> &Copies); 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