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