| 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 |
}; |