1 //===-- BasicBlockSectionsProfileReader.h - BB sections profile reader pass ==//
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 // This pass creates the basic block cluster info by reading the basic block
10 // sections profile. The cluster info will be used by the basic-block-sections
11 // pass to arrange basic blocks in their sections.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CODEGEN_BASICBLOCKSECTIONSPROFILEREADER_H
16 #define LLVM_CODEGEN_BASICBLOCKSECTIONSPROFILEREADER_H
17 
18 #include "llvm/ADT/SmallString.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringMap.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/InitializePasses.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Support/Error.h"
28 #include "llvm/Support/LineIterator.h"
29 #include "llvm/Support/MemoryBuffer.h"
30 #include "llvm/Target/TargetMachine.h"
31 
32 using namespace llvm;
33 
34 namespace llvm {
35 
36 // This struct represents the cluster information for a machine basic block,
37 // which is specifed by a unique ID (`MachineBasicBlock::BBID`).
38 struct BBClusterInfo {
39   // Basic block ID.
40   UniqueBBID BBID;
41   // Cluster ID this basic block belongs to.
42   unsigned ClusterID;
43   // Position of basic block within the cluster.
44   unsigned PositionInCluster;
45 };
46 
47 // This represents the raw input profile for one function.
48 struct FunctionPathAndClusterInfo {
49   // BB Cluster information specified by `UniqueBBID`s.
50   SmallVector<BBClusterInfo> ClusterInfo;
51   // Paths to clone. A path a -> b -> c -> d implies cloning b, c, and d along
52   // the edge a -> b (a is not cloned). The index of the path in this vector
53   // determines the `UniqueBBID::CloneID` of the cloned blocks in that path.
54   SmallVector<SmallVector<unsigned>> ClonePaths;
55 };
56 
57 // Provides DenseMapInfo for UniqueBBID.
58 template <> struct DenseMapInfo<UniqueBBID> {
59   static inline UniqueBBID getEmptyKey() {
60     unsigned EmptyKey = DenseMapInfo<unsigned>::getEmptyKey();
61     return UniqueBBID{EmptyKey, EmptyKey};
62   }
63   static inline UniqueBBID getTombstoneKey() {
64     unsigned TombstoneKey = DenseMapInfo<unsigned>::getTombstoneKey();
65     return UniqueBBID{TombstoneKey, TombstoneKey};
66   }
67   static unsigned getHashValue(const UniqueBBID &Val) {
68     std::pair<unsigned, unsigned> PairVal =
69         std::make_pair(Val.BaseID, Val.CloneID);
70     return DenseMapInfo<std::pair<unsigned, unsigned>>::getHashValue(PairVal);
71   }
72   static bool isEqual(const UniqueBBID &LHS, const UniqueBBID &RHS) {
73     return DenseMapInfo<unsigned>::isEqual(LHS.BaseID, RHS.BaseID) &&
74            DenseMapInfo<unsigned>::isEqual(LHS.CloneID, RHS.CloneID);
75   }
76 };
77 
78 class BasicBlockSectionsProfileReader {
79 public:
80   friend class BasicBlockSectionsProfileReaderWrapperPass;
81   BasicBlockSectionsProfileReader(const MemoryBuffer *Buf)
82       : MBuf(Buf), LineIt(*Buf, /*SkipBlanks=*/true, /*CommentMarker=*/'#'){};
83 
84   BasicBlockSectionsProfileReader(){};
85 
86   // Returns true if basic block sections profile exist for function \p
87   // FuncName.
88   bool isFunctionHot(StringRef FuncName) const;
89 
90   // Returns a pair with first element representing whether basic block sections
91   // profile exist for the function \p FuncName, and the second element
92   // representing the basic block sections profile (cluster info) for this
93   // function. If the first element is true and the second element is empty, it
94   // means unique basic block sections are desired for all basic blocks of the
95   // function.
96   std::pair<bool, SmallVector<BBClusterInfo>>
97   getClusterInfoForFunction(StringRef FuncName) const;
98 
99   // Returns the path clonings for the given function.
100   SmallVector<SmallVector<unsigned>>
101   getClonePathsForFunction(StringRef FuncName) const;
102 
103 private:
104   StringRef getAliasName(StringRef FuncName) const {
105     auto R = FuncAliasMap.find(FuncName);
106     return R == FuncAliasMap.end() ? FuncName : R->second;
107   }
108 
109   // Returns a profile parsing error for the current line.
110   Error createProfileParseError(Twine Message) const {
111     return make_error<StringError>(
112         Twine("invalid profile " + MBuf->getBufferIdentifier() + " at line " +
113               Twine(LineIt.line_number()) + ": " + Message),
114         inconvertibleErrorCode());
115   }
116 
117   // Parses a `UniqueBBID` from `S`. `S` must be in the form "<bbid>"
118   // (representing an original block) or "<bbid>.<cloneid>" (representing a
119   // cloned block) where bbid is a non-negative integer and cloneid is a
120   // positive integer.
121   Expected<UniqueBBID> parseUniqueBBID(StringRef S) const;
122 
123   // Reads the basic block sections profile for functions in this module.
124   Error ReadProfile();
125 
126   // Reads version 0 profile.
127   // TODO: Remove this function once version 0 is deprecated.
128   Error ReadV0Profile();
129 
130   // Reads version 1 profile.
131   Error ReadV1Profile();
132 
133   // This contains the basic-block-sections profile.
134   const MemoryBuffer *MBuf = nullptr;
135 
136   // Iterator to the line being parsed.
137   line_iterator LineIt;
138 
139   // Map from every function name in the module to its debug info filename or
140   // empty string if no debug info is available.
141   StringMap<SmallString<128>> FunctionNameToDIFilename;
142 
143   // This contains the BB cluster information for the whole program.
144   //
145   // For every function name, it contains the cloning and cluster information
146   // for (all or some of) its basic blocks. The cluster information for every
147   // basic block includes its cluster ID along with the position of the basic
148   // block in that cluster.
149   StringMap<FunctionPathAndClusterInfo> ProgramPathAndClusterInfo;
150 
151   // Some functions have alias names. We use this map to find the main alias
152   // name which appears in ProgramPathAndClusterInfo as a key.
153   StringMap<StringRef> FuncAliasMap;
154 };
155 
156 // Creates a BasicBlockSectionsProfileReader pass to parse the basic block
157 // sections profile. \p Buf is a memory buffer that contains the list of
158 // functions and basic block ids to selectively enable basic block sections.
159 ImmutablePass *
160 createBasicBlockSectionsProfileReaderWrapperPass(const MemoryBuffer *Buf);
161 
162 /// Analysis pass providing the \c BasicBlockSectionsProfileReader.
163 ///
164 /// Note that this pass's result cannot be invalidated, it is immutable for the
165 /// life of the module.
166 class BasicBlockSectionsProfileReaderAnalysis
167     : public AnalysisInfoMixin<BasicBlockSectionsProfileReaderAnalysis> {
168 
169 public:
170   static AnalysisKey Key;
171   typedef BasicBlockSectionsProfileReader Result;
172   BasicBlockSectionsProfileReaderAnalysis(const TargetMachine *TM) : TM(TM) {}
173 
174   Result run(Function &F, FunctionAnalysisManager &AM);
175 
176 private:
177   const TargetMachine *TM;
178 };
179 
180 class BasicBlockSectionsProfileReaderWrapperPass : public ImmutablePass {
181 public:
182   static char ID;
183   BasicBlockSectionsProfileReader BBSPR;
184 
185   BasicBlockSectionsProfileReaderWrapperPass(const MemoryBuffer *Buf)
186       : ImmutablePass(ID), BBSPR(BasicBlockSectionsProfileReader(Buf)) {
187     initializeBasicBlockSectionsProfileReaderWrapperPassPass(
188         *PassRegistry::getPassRegistry());
189   };
190 
191   BasicBlockSectionsProfileReaderWrapperPass()
192       : ImmutablePass(ID), BBSPR(BasicBlockSectionsProfileReader()) {
193     initializeBasicBlockSectionsProfileReaderWrapperPassPass(
194         *PassRegistry::getPassRegistry());
195   }
196 
197   StringRef getPassName() const override {
198     return "Basic Block Sections Profile Reader";
199   }
200 
201   bool isFunctionHot(StringRef FuncName) const;
202 
203   std::pair<bool, SmallVector<BBClusterInfo>>
204   getClusterInfoForFunction(StringRef FuncName) const;
205 
206   SmallVector<SmallVector<unsigned>>
207   getClonePathsForFunction(StringRef FuncName) const;
208 
209   // Initializes the FunctionNameToDIFilename map for the current module and
210   // then reads the profile for the matching functions.
211   bool doInitialization(Module &M) override;
212 
213   BasicBlockSectionsProfileReader &getBBSPR();
214 };
215 
216 } // namespace llvm
217 #endif // LLVM_CODEGEN_BASICBLOCKSECTIONSPROFILEREADER_H
218