llvm/CodeGen/TailDuplicator.h

0001 //===- llvm/CodeGen/TailDuplicator.h ----------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines the TailDuplicator class. Used by the
0010 // TailDuplication pass, and MachineBlockPlacement.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CODEGEN_TAILDUPLICATOR_H
0015 #define LLVM_CODEGEN_TAILDUPLICATOR_H
0016
0017 #include "llvm/ADT/DenseMap.h"
0018 #include "llvm/ADT/DenseSet.h"
0019 #include "llvm/ADT/SmallVector.h"
0020 #include "llvm/CodeGen/TargetInstrInfo.h"
0021 #include <utility>
0022 #include <vector>
0023
0024 namespace llvm {
0025
0026 template <typename T, unsigned int N> class SmallSetVector;
0027 template <typename Fn> class function_ref;
0028 class MBFIWrapper;
0029 class MachineBasicBlock;
0030 class MachineBranchProbabilityInfo;
0031 class MachineFunction;
0032 class MachineInstr;
0033 class MachineModuleInfo;
0034 class MachineRegisterInfo;
0035 class ProfileSummaryInfo;
0036 class TargetRegisterInfo;
0037
0038 /// Utility class to perform tail duplication.
0039 class TailDuplicator {
0040   const TargetInstrInfo *TII;
0041   const TargetRegisterInfo *TRI;
0042   const MachineBranchProbabilityInfo *MBPI;
0043   MachineRegisterInfo *MRI;
0044   MachineFunction *MF;
0045   MBFIWrapper *MBFI;
0046   ProfileSummaryInfo *PSI;
0047   bool PreRegAlloc;
0048   bool LayoutMode;
0049   unsigned TailDupSize;
0050
0051   // A list of virtual registers for which to update SSA form.
0052   SmallVector<Register, 16> SSAUpdateVRs;
0053
0054   // For each virtual register in SSAUpdateVals keep a list of source virtual
0055   // registers.
0056   using AvailableValsTy = std::vector<std::pair<MachineBasicBlock *, Register>>;
0057
0058   DenseMap<Register, AvailableValsTy> SSAUpdateVals;
0059
0060 public:
0061   /// Prepare to run on a specific machine function.
0062   /// @param MF - Function that will be processed
0063   /// @param PreRegAlloc - true if used before register allocation
0064   /// @param MBPI - Branch Probability Info. Used to propagate correct
0065   ///     probabilities when modifying the CFG.
0066   /// @param LayoutMode - When true, don't use the existing layout to make
0067   ///     decisions.
0068   /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
0069   ///     default implies using the command line value TailDupSize.
0070   void initMF(MachineFunction &MF, bool PreRegAlloc,
0071               const MachineBranchProbabilityInfo *MBPI,
0072               MBFIWrapper *MBFI,
0073               ProfileSummaryInfo *PSI,
0074               bool LayoutMode, unsigned TailDupSize = 0);
0075
0076   bool tailDuplicateBlocks();
0077   static bool isSimpleBB(MachineBasicBlock *TailBB);
0078   bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
0079
0080   /// Returns true if TailBB can successfully be duplicated into PredBB
0081   bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB);
0082
0083   /// Tail duplicate a single basic block into its predecessors, and then clean
0084   /// up.
0085   /// If \p DuplicatePreds is not null, it will be updated to contain the list
0086   /// of predecessors that received a copy of \p MBB.
0087   /// If \p RemovalCallback is non-null. It will be called before MBB is
0088   /// deleted.
0089   /// If \p CandidatePtr is not null, duplicate into these blocks only.
0090   bool tailDuplicateAndUpdate(
0091       bool IsSimple, MachineBasicBlock *MBB,
0092       MachineBasicBlock *ForcedLayoutPred,
0093       SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
0094       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr,
0095       SmallVectorImpl<MachineBasicBlock *> *CandidatePtr = nullptr);
0096
0097 private:
0098   using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
0099
0100   void addSSAUpdateEntry(Register OrigReg, Register NewReg,
0101                          MachineBasicBlock *BB);
0102   void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
0103                   MachineBasicBlock *PredBB,
0104                   DenseMap<Register, RegSubRegPair> &LocalVRMap,
0105                   SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
0106                   const DenseSet<Register> &UsedByPhi, bool Remove);
0107   void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
0108                             MachineBasicBlock *PredBB,
0109                             DenseMap<Register, RegSubRegPair> &LocalVRMap,
0110                             const DenseSet<Register> &UsedByPhi);
0111   void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
0112                             SmallVectorImpl<MachineBasicBlock *> &TDBBs,
0113                             SmallSetVector<MachineBasicBlock *, 8> &Succs);
0114   bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
0115   bool duplicateSimpleBB(MachineBasicBlock *TailBB,
0116                          SmallVectorImpl<MachineBasicBlock *> &TDBBs,
0117                          const DenseSet<Register> &RegsUsedByPhi);
0118   bool tailDuplicate(bool IsSimple,
0119                      MachineBasicBlock *TailBB,
0120                      MachineBasicBlock *ForcedLayoutPred,
0121                      SmallVectorImpl<MachineBasicBlock *> &TDBBs,
0122                      SmallVectorImpl<MachineInstr *> &Copies,
0123                      SmallVectorImpl<MachineBasicBlock *> *CandidatePtr);
0124   void appendCopies(MachineBasicBlock *MBB,
0125                  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
0126                  SmallVectorImpl<MachineInstr *> &Copies);
0127
0128   void removeDeadBlock(
0129       MachineBasicBlock *MBB,
0130       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
0131 };
0132
0133 } // end namespace llvm
0134
0135 #endif // LLVM_CODEGEN_TAILDUPLICATOR_H