include/llvm/CodeGen/TailDuplicator.h

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