Debian Codegraph @

libcextract/IpaClonesParser.hh

raw
1 //===- IpaClonesParser.hh - Parse .ipa-clones file --------------*- C++ -*-===//
2 //
3 // This project is licensed 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 /// \file
10 /// Parse the .ipa-clones files to determine the optimization decision by gcc.
11 //
12 //===----------------------------------------------------------------------===//
13
14 /* Author: Giuliano Belinassi */
15
16 /** IpaClonesParser: Parse GCC IPA-clones files and build an inline graph.
17 *
18 * GCC performs many cross-function optimizations, one of them is `inlining`,
19 * which copies the body of the callee into the caller. This optimization often
20 * removes the original symbol from the ELF file and insert additional stuff
21 * into the caller, so that if we want to livepatch this function we need to be
22 * careful about them. This file implements the datastructures necessary for
23 * parsing and processing those files.
24 */
25
26 #pragma once
27
28 #include "Parser.hh"
29
30 #include <set>
31 #include <unordered_map>
32 #include <string>
33 #include <string.h>
34 #include <stdlib.h>
35 #include <memory>
36
37 /** @brief Represent an cloned node. See this as a callgraph, but we only
38 * incide edges when there is an inline.
39 */
40 struct IpaCloneNode
41 {
42 /** Name of the symbol. */
43 std::string Name;
44 /** Where is this symbol inlined into? */
45 std::set<IpaCloneNode *> InlinedInto;
46
47 /** Which symbols this symbol is inline into? */
48 std::set<IpaCloneNode *> Inlines;
49 };
50
51 /** @brief Parse .ipa-clone files and build an inline graph. */
52 class IpaClones : public Parser
53 {
54 public:
55 /** There are two decision cases:
56 * - REMOVE, which removes the function from the code.
57 * - CLONE, which does some transformation in the code.
58 *
59 * This is used to find out how many tokens there are in a single line of
60 * the .ipa-clones file.
61 */
62 enum IpaDecision
63 {
64 IPA_REMOVE,
65 IPA_CLONE,
66 };
67
68 /** Construct the IpaClones from a ipa-clones files. */
69 IpaClones(const char *path);
70
71 // IPA clones can point to a directory, so we need to handle paths at this
72 // point.
73 void Parse(const char *path);
74
75 /** Construct the IpaClones from a ipa-clones files. */
76 inline IpaClones(const std::string &path)
77 : IpaClones(path.c_str())
78 { }
79
80 /** Get a node with matching ASM name. ASM names are unique even for C++ so
81 * there should not be any clashes. */
82 inline IpaCloneNode *Get_Node(const std::string &name)
83 {
84 std::unordered_map<std::string, IpaCloneNode>::iterator it = Nodes.find(name);
85 if (it != Nodes.end()) {
86 return &Nodes[name];
87 }
88
89 return nullptr;
90 }
91
92 /** Get a node with matching ASM name. ASM names are unique even for C++ so
93 * there should not be any clashes. */
94 inline IpaCloneNode *Get_Node(const char *name)
95 {
96 return Get_Node(std::string(name));
97 }
98
99 /** Get a node with matching ASM name, or create it if does not exists. */
100 IpaCloneNode *Get_Or_Create_Node(const std::string &name);
101
102 /** Get a node with matching ASM name, or create it if does not exists. */
103 inline IpaCloneNode *Get_Or_Create_Node(const char *name)
104 {
105 return Get_Or_Create_Node(std::string(name));
106 }
107
108 /** Iterate through the set of all nodes. */
109 inline std::unordered_map<std::string, IpaCloneNode>::iterator begin()
110 {
111 return Nodes.begin();
112 }
113 inline std::unordered_map<std::string, IpaCloneNode>::iterator end()
114 {
115 return Nodes.end();
116 }
117
118 void Dump(void);
119 void Dump_Graphviz(const char *filename);
120
121 private:
122
123 void Open_Recursive(const char *path);
124
125 /** Set of nodes. */
126 std::unordered_map<std::string, IpaCloneNode> Nodes;
127
128 /** Hold the state machine of the lexer, which is where in the string it is. */
129 class LexingState
130 {
131 public:
132 inline LexingState(char *line)
133 : CurrentStateString(line),
134 OriginalPtr(line)
135 {
136 }
137
138 inline ~LexingState(void)
139 {
140 free(OriginalPtr);
141 }
142
143 /** Next token in file. */
144 const char *Lex(void);
145
146 /** Parse the decision string into a IpaDecision. */
147 static IpaDecision Get_Decision(const char *);
148
149 /** Current state for strtok. */
150 char *CurrentStateString;
151
152 /** Original string returned by getline. */
153 char *OriginalPtr;
154 };
155 };
156
157 /** Compute the closure of a symbol executing an Action on each edge.
158 *
159 * On many analysis we need to do an DFS on the IPA-clones graph and execute
160 * a set of commands on each edge of the graph. This class abstract this by
161 * giving a way to pass a function pointer and a opaque pointer to an object
162 * which can be used to populate with information.
163 */
164 struct IpaClosure
165 {
166 public:
167 /** Build the object.
168 * @param ipa The IPA clones object.
169 * @param opaque Pointer to an opaque object handled by `action_function`.
170 * @param action_function Function which will do something with the `opaque` and
171 * nodes given to it.
172 */
173 inline IpaClosure(IpaClones &ipa, void *opaque,
174 int (*action_function)(void *, IpaCloneNode *, IpaCloneNode *))
175 : Ipa(ipa),
176 Opaque(opaque),
177 Action(action_function)
178 {
179 }
180
181 /** Find which symbols are inlined in the function represented by `node`. */
182 void Find_Inlined_Symbols(IpaCloneNode *node);
183
184 /** Find the other functions where the symbol represented by `node` is
185 inlined. */
186 void Find_Where_Symbol_Is_Inlined(IpaCloneNode *node);
187
188 /** Find which symbols are inlined in the function with mangled name `name`. */
189 inline void Find_Inlined_Symbols(const std::string &name)
190 {
191 IpaCloneNode *node = Ipa.Get_Node(name);
192 Find_Inlined_Symbols(node);
193 }
194
195 /** Find the other functions where the symbol with mangled name `name` is
196 inlined. */
197 inline void Find_Where_Symbol_Is_Inlined(const std::string &name)
198 {
199 IpaCloneNode *node = Ipa.Get_Node(name);
200 Find_Where_Symbol_Is_Inlined(node);
201 }
202
203 /** Set of marked symbols. */
204 std::set<IpaCloneNode *> Set;
205
206 private:
207
208 /** Is symbol marked? (already analyzed). */
209 inline bool Is_In_Set(IpaCloneNode *x)
210 {
211 return Set.find(x) != Set.end();
212 }
213
214 /** Reference to the IpaClones object used to build this object. */
215 IpaClones &Ipa;
216
217 /** Opaque pointer that is always passed to Action. */
218 void *Opaque;
219
220 /** Action function that will always be executed on each edge. */
221 int (*Action)(void *opaque, IpaCloneNode *, IpaCloneNode *);
222 };