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 MBPI - Branch Probability Info. Used to propagate correct
     65   ///     probabilities when modifying the CFG.
     66   /// @param LayoutMode - When true, don't use the existing layout to make
     67   ///     decisions.
     68   /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
     69   ///     default implies using the command line value TailDupSize.
     70   void initMF(MachineFunction &MF,
     71               const MachineBranchProbabilityInfo *MBPI,
     72               bool LayoutMode, unsigned TailDupSize = 0);
     73 
     74   bool tailDuplicateBlocks();
     75   static bool isSimpleBB(MachineBasicBlock *TailBB);
     76   bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
     77 
     78   /// Returns true if TailBB can successfully be duplicated into PredBB
     79   bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB);
     80 
     81   /// Tail duplicate a single basic block into its predecessors, and then clean
     82   /// up.
     83   /// If \p DuplicatePreds is not null, it will be updated to contain the list
     84   /// of predecessors that received a copy of \p MBB.
     85   /// If \p RemovalCallback is non-null. It will be called before MBB is
     86   /// deleted.
     87   bool tailDuplicateAndUpdate(
     88       bool IsSimple, MachineBasicBlock *MBB,
     89       MachineBasicBlock *ForcedLayoutPred,
     90       SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
     91       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
     92 
     93 private:
     94   using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
     95 
     96   void addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
     97                          MachineBasicBlock *BB);
     98   void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
     99                   MachineBasicBlock *PredBB,
    100                   DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
    101                   SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies,
    102                   const DenseSet<unsigned> &UsedByPhi, bool Remove);
    103   void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
    104                             MachineBasicBlock *PredBB,
    105                             DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
    106                             const DenseSet<unsigned> &UsedByPhi);
    107   void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
    108                             SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    109                             SmallSetVector<MachineBasicBlock *, 8> &Succs);
    110   bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
    111   bool duplicateSimpleBB(MachineBasicBlock *TailBB,
    112                          SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    113                          const DenseSet<unsigned> &RegsUsedByPhi,
    114                          SmallVectorImpl<MachineInstr *> &Copies);
    115   bool tailDuplicate(bool IsSimple,
    116                      MachineBasicBlock *TailBB,
    117                      MachineBasicBlock *ForcedLayoutPred,
    118                      SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    119                      SmallVectorImpl<MachineInstr *> &Copies);
    120   void appendCopies(MachineBasicBlock *MBB,
    121                  SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
    122                  SmallVectorImpl<MachineInstr *> &Copies);
    123 
    124   void removeDeadBlock(
    125       MachineBasicBlock *MBB,
    126       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
    127 };
    128 
    129 } // end namespace llvm
    130 
    131 #endif // LLVM_CODEGEN_TAILDUPLICATOR_H
    132