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 25 namespace llvm { 26 27 class MachineBasicBlock; 28 class MachineBlockFrequencyInfo; 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 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 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 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 95 private: 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