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