contrib/llvm/include/llvm/CodeGen/TailDuplicator.h

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