Coverage Report

Created: 2019-07-24 05:18

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