Home | History | Annotate | Line # | Download | only in CodeGen 
      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 MachineBlockFrequencyInfo;
     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   const MachineModuleInfo *MMI;
     44   MachineRegisterInfo *MRI;
     45   MachineFunction *MF;
     46   MBFIWrapper *MBFI;
     47   ProfileSummaryInfo *PSI;
     48   bool PreRegAlloc;
     49   bool LayoutMode;
     50   unsigned TailDupSize;
     51 
     52   // A list of virtual registers for which to update SSA form.
     53   SmallVector<Register, 16> SSAUpdateVRs;
     54 
     55   // For each virtual register in SSAUpdateVals keep a list of source virtual
     56   // registers.
     57   using AvailableValsTy = std::vector<std::pair<MachineBasicBlock *, Register>>;
     58 
     59   DenseMap<Register, AvailableValsTy> SSAUpdateVals;
     60 
     61 public:
     62   /// Prepare to run on a specific machine function.
     63   /// @param MF - Function that will be processed
     64   /// @param PreRegAlloc - true if used before register allocation
     65   /// @param MBPI - Branch Probability Info. Used to propagate correct
     66   ///     probabilities when modifying the CFG.
     67   /// @param LayoutMode - When true, don't use the existing layout to make
     68   ///     decisions.
     69   /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
     70   ///     default implies using the command line value TailDupSize.
     71   void initMF(MachineFunction &MF, bool PreRegAlloc,
     72               const MachineBranchProbabilityInfo *MBPI,
     73               MBFIWrapper *MBFI,
     74               ProfileSummaryInfo *PSI,
     75               bool LayoutMode, unsigned TailDupSize = 0);
     76 
     77   bool tailDuplicateBlocks();
     78   static bool isSimpleBB(MachineBasicBlock *TailBB);
     79   bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
     80 
     81   /// Returns true if TailBB can successfully be duplicated into PredBB
     82   bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB);
     83 
     84   /// Tail duplicate a single basic block into its predecessors, and then clean
     85   /// up.
     86   /// If \p DuplicatePreds is not null, it will be updated to contain the list
     87   /// of predecessors that received a copy of \p MBB.
     88   /// If \p RemovalCallback is non-null. It will be called before MBB is
     89   /// deleted.
     90   /// If \p CandidatePtr is not null, duplicate into these blocks only.
     91   bool tailDuplicateAndUpdate(
     92       bool IsSimple, MachineBasicBlock *MBB,
     93       MachineBasicBlock *ForcedLayoutPred,
     94       SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
     95       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr,
     96       SmallVectorImpl<MachineBasicBlock *> *CandidatePtr = nullptr);
     97 
     98 private:
     99   using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
    100 
    101   void addSSAUpdateEntry(Register OrigReg, Register NewReg,
    102                          MachineBasicBlock *BB);
    103   void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
    104                   MachineBasicBlock *PredBB,
    105                   DenseMap<Register, RegSubRegPair> &LocalVRMap,
    106                   SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
    107                   const DenseSet<Register> &UsedByPhi, bool Remove);
    108   void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
    109                             MachineBasicBlock *PredBB,
    110                             DenseMap<Register, RegSubRegPair> &LocalVRMap,
    111                             const DenseSet<Register> &UsedByPhi);
    112   void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
    113                             SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    114                             SmallSetVector<MachineBasicBlock *, 8> &Succs);
    115   bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
    116   bool duplicateSimpleBB(MachineBasicBlock *TailBB,
    117                          SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    118                          const DenseSet<Register> &RegsUsedByPhi,
    119                          SmallVectorImpl<MachineInstr *> &Copies);
    120   bool tailDuplicate(bool IsSimple,
    121                      MachineBasicBlock *TailBB,
    122                      MachineBasicBlock *ForcedLayoutPred,
    123                      SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    124                      SmallVectorImpl<MachineInstr *> &Copies,
    125                      SmallVectorImpl<MachineBasicBlock *> *CandidatePtr);
    126   void appendCopies(MachineBasicBlock *MBB,
    127                  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
    128                  SmallVectorImpl<MachineInstr *> &Copies);
    129 
    130   void removeDeadBlock(
    131       MachineBasicBlock *MBB,
    132       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
    133 };
    134 
    135 } // end namespace llvm
    136 
    137 #endif // LLVM_CODEGEN_TAILDUPLICATOR_H
    138