Home | History | Annotate | Download | only in CodeGen 
      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/ADT/STLExtras.h"
     23 #include "llvm/CodeGen/RegisterScavenging.h"
     24 #include "llvm/Support/CommandLine.h"
     25 #include "llvm/Target/TargetInstrInfo.h"
     26 #include "llvm/Target/TargetSubtargetInfo.h"
     27 #include <utility>
     28 #include <vector>
     29 
     30 namespace llvm {
     31 
     32 class MachineBasicBlock;
     33 class MachineBranchProbabilityInfo;
     34 class MachineFunction;
     35 class MachineInstr;
     36 class MachineModuleInfo;
     37 class MachineRegisterInfo;
     38 class TargetRegisterInfo;
     39 
     40 /// Utility class to perform tail duplication.
     41 class TailDuplicator {
     42   const TargetInstrInfo *TII;
     43   const TargetRegisterInfo *TRI;
     44   const MachineBranchProbabilityInfo *MBPI;
     45   const MachineModuleInfo *MMI;
     46   MachineRegisterInfo *MRI;
     47   MachineFunction *MF;
     48   bool PreRegAlloc;
     49   bool LayoutMode;
     50   unsigned TailDupSize;
     51 
     52   // A list of virtual registers for which to update SSA form.
     53   SmallVector<unsigned, 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 *, unsigned>>;
     58 
     59   DenseMap<unsigned, 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               bool LayoutMode, unsigned TailDupSize = 0);
     74 
     75   bool tailDuplicateBlocks();
     76   static bool isSimpleBB(MachineBasicBlock *TailBB);
     77   bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
     78 
     79   /// Returns true if TailBB can successfully be duplicated into PredBB
     80   bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB);
     81 
     82   /// Tail duplicate a single basic block into its predecessors, and then clean
     83   /// up.
     84   /// If \p DuplicatePreds is not null, it will be updated to contain the list
     85   /// of predecessors that received a copy of \p MBB.
     86   /// If \p RemovalCallback is non-null. It will be called before MBB is
     87   /// deleted.
     88   bool tailDuplicateAndUpdate(
     89       bool IsSimple, MachineBasicBlock *MBB,
     90       MachineBasicBlock *ForcedLayoutPred,
     91       SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
     92       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
     93 
     94 private:
     95   using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
     96 
     97   void addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
     98                          MachineBasicBlock *BB);
     99   void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
    100                   MachineBasicBlock *PredBB,
    101                   DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
    102                   SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies,
    103                   const DenseSet<unsigned> &UsedByPhi, bool Remove);
    104   void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
    105                             MachineBasicBlock *PredBB,
    106                             DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
    107                             const DenseSet<unsigned> &UsedByPhi);
    108   void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
    109                             SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    110                             SmallSetVector<MachineBasicBlock *, 8> &Succs);
    111   bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
    112   bool duplicateSimpleBB(MachineBasicBlock *TailBB,
    113                          SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    114                          const DenseSet<unsigned> &RegsUsedByPhi,
    115                          SmallVectorImpl<MachineInstr *> &Copies);
    116   bool tailDuplicate(bool IsSimple,
    117                      MachineBasicBlock *TailBB,
    118                      MachineBasicBlock *ForcedLayoutPred,
    119                      SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    120                      SmallVectorImpl<MachineInstr *> &Copies);
    121   void appendCopies(MachineBasicBlock *MBB,
    122                  SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
    123                  SmallVectorImpl<MachineInstr *> &Copies);
    124 
    125   void removeDeadBlock(
    126       MachineBasicBlock *MBB,
    127       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
    128 };
    129 
    130 } // end namespace llvm
    131 
    132 #endif // LLVM_CODEGEN_TAILDUPLICATOR_H
    133