LCOV - code coverage report
Current view: top level - lib/CodeGen - BranchFolding.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 8 8 100.0 %
Date: 2018-05-20 00:06:23 Functions: 1 1 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- BranchFolding.h - Fold machine code branch instructions --*- 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             : #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H
      11             : #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
      12             : 
      13             : #include "llvm/ADT/DenseMap.h"
      14             : #include "llvm/ADT/SmallPtrSet.h"
      15             : #include "llvm/CodeGen/LivePhysRegs.h"
      16             : #include "llvm/CodeGen/MachineBasicBlock.h"
      17             : #include "llvm/Support/BlockFrequency.h"
      18             : #include "llvm/Support/Compiler.h"
      19             : #include <cstdint>
      20             : #include <vector>
      21             : 
      22             : namespace llvm {
      23             : 
      24             : class BasicBlock;
      25             : class MachineBlockFrequencyInfo;
      26             : class MachineBranchProbabilityInfo;
      27             : class MachineFunction;
      28             : class MachineLoopInfo;
      29             : class MachineModuleInfo;
      30             : class MachineRegisterInfo;
      31             : class raw_ostream;
      32             : class TargetInstrInfo;
      33             : class TargetRegisterInfo;
      34             : 
      35      420109 :   class LLVM_LIBRARY_VISIBILITY BranchFolder {
      36             :   public:
      37             :     class MBFIWrapper;
      38             : 
      39             :     explicit BranchFolder(bool defaultEnableTailMerge,
      40             :                           bool CommonHoist,
      41             :                           MBFIWrapper &MBFI,
      42             :                           const MachineBranchProbabilityInfo &MBPI,
      43             :                           // Min tail length to merge. Defaults to commandline
      44             :                           // flag. Ignored for optsize.
      45             :                           unsigned MinCommonTailLength = 0);
      46             : 
      47             :     /// Perhaps branch folding, tail merging and other CFG optimizations on the
      48             :     /// given function.  Block placement changes the layout and may create new
      49             :     /// tail merging opportunities.
      50             :     bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,
      51             :                           const TargetRegisterInfo *tri, MachineModuleInfo *mmi,
      52             :                           MachineLoopInfo *mli = nullptr,
      53             :                           bool AfterPlacement = false);
      54             : 
      55             :   private:
      56             :     class MergePotentialsElt {
      57             :       unsigned Hash;
      58             :       MachineBasicBlock *Block;
      59             : 
      60             :     public:
      61             :       MergePotentialsElt(unsigned h, MachineBasicBlock *b)
      62      610929 :         : Hash(h), Block(b) {}
      63             : 
      64             :       unsigned getHash() const { return Hash; }
      65             :       MachineBasicBlock *getBlock() const { return Block; }
      66             : 
      67             :       void setBlock(MachineBasicBlock *MBB) {
      68        3573 :         Block = MBB;
      69             :       }
      70             : 
      71             :       bool operator<(const MergePotentialsElt &) const;
      72             :     };
      73             : 
      74             :     using MPIterator = std::vector<MergePotentialsElt>::iterator;
      75             : 
      76             :     std::vector<MergePotentialsElt> MergePotentials;
      77             :     SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
      78             :     DenseMap<const MachineBasicBlock *, int> FuncletMembership;
      79             : 
      80             :     class SameTailElt {
      81             :       MPIterator MPIter;
      82             :       MachineBasicBlock::iterator TailStartPos;
      83             : 
      84             :     public:
      85             :       SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
      86       21002 :         : MPIter(mp), TailStartPos(tsp) {}
      87             : 
      88             :       MPIterator getMPIter() const {
      89             :         return MPIter;
      90             :       }
      91             : 
      92             :       MergePotentialsElt &getMergePotentialsElt() const {
      93             :         return *getMPIter();
      94             :       }
      95             : 
      96             :       MachineBasicBlock::iterator getTailStartPos() const {
      97             :         return TailStartPos;
      98             :       }
      99             : 
     100             :       unsigned getHash() const {
     101             :         return getMergePotentialsElt().getHash();
     102             :       }
     103             : 
     104             :       MachineBasicBlock *getBlock() const {
     105       75449 :         return getMergePotentialsElt().getBlock();
     106             :       }
     107             : 
     108             :       bool tailIsWholeBlock() const {
     109             :         return TailStartPos == getBlock()->begin();
     110             :       }
     111             : 
     112             :       void setBlock(MachineBasicBlock *MBB) {
     113             :         getMergePotentialsElt().setBlock(MBB);
     114             :       }
     115             : 
     116             :       void setTailStartPos(MachineBasicBlock::iterator Pos) {
     117        3573 :         TailStartPos = Pos;
     118             :       }
     119             :     };
     120             :     std::vector<SameTailElt> SameTails;
     121             : 
     122             :     bool AfterBlockPlacement;
     123             :     bool EnableTailMerge;
     124             :     bool EnableHoistCommonCode;
     125             :     bool UpdateLiveIns;
     126             :     unsigned MinCommonTailLength;
     127             :     const TargetInstrInfo *TII;
     128             :     const MachineRegisterInfo *MRI;
     129             :     const TargetRegisterInfo *TRI;
     130             :     MachineModuleInfo *MMI;
     131             :     MachineLoopInfo *MLI;
     132             :     LivePhysRegs LiveRegs;
     133             : 
     134             :   public:
     135             :     /// This class keeps track of branch frequencies of newly created
     136             :     /// blocks and tail-merged blocks.
     137       14710 :     class MBFIWrapper {
     138             :     public:
     139      216591 :       MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
     140             : 
     141             :       BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
     142             :       void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
     143             :       raw_ostream &printBlockFreq(raw_ostream &OS,
     144             :                                   const MachineBasicBlock *MBB) const;
     145             :       raw_ostream &printBlockFreq(raw_ostream &OS,
     146             :                                   const BlockFrequency Freq) const;
     147             :       void view(const Twine &Name, bool isSimple = true);
     148             :       uint64_t getEntryFreq() const;
     149             : 
     150             :     private:
     151             :       const MachineBlockFrequencyInfo &MBFI;
     152             :       DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
     153             :     };
     154             : 
     155             :   private:
     156             :     MBFIWrapper &MBBFreqInfo;
     157             :     const MachineBranchProbabilityInfo &MBPI;
     158             : 
     159             :     bool TailMergeBlocks(MachineFunction &MF);
     160             :     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
     161             :                        MachineBasicBlock* PredBB,
     162             :                        unsigned MinCommonTailLength);
     163             :     void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
     164             : 
     165             :     /// Delete the instruction OldInst and everything after it, replacing it
     166             :     /// with an unconditional branch to NewDest.
     167             :     void replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
     168             :                                  MachineBasicBlock &NewDest);
     169             : 
     170             :     /// Given a machine basic block and an iterator into it, split the MBB so
     171             :     /// that the part before the iterator falls into the part starting at the
     172             :     /// iterator.  This returns the new MBB.
     173             :     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
     174             :                                   MachineBasicBlock::iterator BBI1,
     175             :                                   const BasicBlock *BB);
     176             : 
     177             :     /// Look through all the blocks in MergePotentials that have hash CurHash
     178             :     /// (guaranteed to match the last element).  Build the vector SameTails of
     179             :     /// all those that have the (same) largest number of instructions in common
     180             :     /// of any pair of these blocks.  SameTails entries contain an iterator into
     181             :     /// MergePotentials (from which the MachineBasicBlock can be found) and a
     182             :     /// MachineBasicBlock::iterator into that MBB indicating the instruction
     183             :     /// where the matching code sequence begins.  Order of elements in SameTails
     184             :     /// is the reverse of the order in which those blocks appear in
     185             :     /// MergePotentials (where they are not necessarily consecutive).
     186             :     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
     187             :                               MachineBasicBlock *SuccBB,
     188             :                               MachineBasicBlock *PredBB);
     189             : 
     190             :     /// Remove all blocks with hash CurHash from MergePotentials, restoring
     191             :     /// branches at ends of blocks as appropriate.
     192             :     void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
     193             :                                                 MachineBasicBlock* PredBB);
     194             : 
     195             :     /// None of the blocks to be tail-merged consist only of the common tail.
     196             :     /// Create a block that does by splitting one.
     197             :     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
     198             :                                    MachineBasicBlock *SuccBB,
     199             :                                    unsigned maxCommonTailLength,
     200             :                                    unsigned &commonTailIndex);
     201             : 
     202             :     /// Create merged DebugLocs of identical instructions across SameTails and
     203             :     /// assign it to the instruction in common tail; merge MMOs and undef flags.
     204             :     void mergeCommonTails(unsigned commonTailIndex);
     205             : 
     206             :     bool OptimizeBranches(MachineFunction &MF);
     207             : 
     208             :     /// Analyze and optimize control flow related to the specified block. This
     209             :     /// is never called on the entry block.
     210             :     bool OptimizeBlock(MachineBasicBlock *MBB);
     211             : 
     212             :     /// Remove the specified dead machine basic block from the function,
     213             :     /// updating the CFG.
     214             :     void RemoveDeadBlock(MachineBasicBlock *MBB);
     215             : 
     216             :     /// Hoist common instruction sequences at the start of basic blocks to their
     217             :     /// common predecessor.
     218             :     bool HoistCommonCode(MachineFunction &MF);
     219             : 
     220             :     /// If the successors of MBB has common instruction sequence at the start of
     221             :     /// the function, move the instructions before MBB terminator if it's legal.
     222             :     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
     223             :   };
     224             : 
     225             : } // end namespace llvm
     226             : 
     227             : #endif // LLVM_LIB_CODEGEN_BRANCHFOLDING_H

Generated by: LCOV version 1.13