Line data    Source code

       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       60101 : 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