| 1 |
//===- IpaClonesParser.cpp - 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 |
#include "IpaClonesParser.hh" |
| 17 |
#include "NonLLVMMisc.hh" |
| 18 |
|
| 19 |
#include <stdio.h> |
| 20 |
#include <stdlib.h> |
| 21 |
#include <assert.h> |
| 22 |
#include <stdexcept> |
| 23 |
#include <iostream> |
| 24 |
#include <stdio.h> |
| 25 |
#include <dirent.h> |
| 26 |
#include <limits.h> |
| 27 |
|
| 28 |
/* GCC can either: |
| 29 |
- Change the call ABI of a function to either reduce the stack |
| 30 |
usage, remove instructions, or anything more complicated. The |
| 31 |
pass that can do it is named "Interprocedural Scalar Replacement |
| 32 |
of Aggregates (ISRA)", and symbols with the suffix ".isra.%d" are |
| 33 |
generated from this pass. Althrough those symbols are exported and |
| 34 |
can be called, doing so seems not reliable. Instead we model |
| 35 |
such functions as being `inlined` into the caller, forcing |
| 36 |
clang-extract to issue a copy of this function into the livepatch. |
| 37 |
|
| 38 |
- Inline part of the function in the caller. Functions like this |
| 39 |
are suffixed as `.part.%d` and is again not safe to call either. |
| 40 |
So we model those functions as being inlined, forcing clang-extract |
| 41 |
to issue a copy of it into the livepatch. */ |
| 42 |
static const char *Handle_GCC_Symbol_Quirks(char *symbol) |
| 43 |
{ |
| 44 |
char *first_dot = strchr(symbol, '.'); |
| 45 |
if (first_dot == nullptr) { |
| 46 |
return symbol; |
| 47 |
} |
| 48 |
|
| 49 |
if (prefix(".part.", first_dot)) { |
| 50 |
/* Symbol generated by ipa-split.c pass. Erase the .part. */ |
| 51 |
*first_dot = '\0'; |
| 52 |
return symbol; |
| 53 |
} |
| 54 |
|
| 55 |
if (prefix(".isra.", first_dot)) { |
| 56 |
/* Symbol generated by ipa-isra.c pass. Erase the .isra. */ |
| 57 |
*first_dot = '\0'; |
| 58 |
return symbol; |
| 59 |
} |
| 60 |
|
| 61 |
return symbol; |
| 62 |
} |
| 63 |
|
| 64 |
IpaClones::IpaClones(const char *path) |
| 65 |
: Parser(path) |
| 66 |
{ |
| 67 |
const char *object_path = this->parser_path.c_str(); |
| 68 |
|
| 69 |
if (Is_Directory(object_path) == false) { |
| 70 |
/* Single file. We can pass it directly to Parse. */ |
| 71 |
Parse(path); |
| 72 |
return; |
| 73 |
} |
| 74 |
|
| 75 |
Open_Recursive(object_path); |
| 76 |
} |
| 77 |
|
| 78 |
void IpaClones::Open_Recursive(const char *path) |
| 79 |
{ |
| 80 |
/* Else we have to parse the directory tree. */ |
| 81 |
DIR *directory = opendir(path); |
| 82 |
struct dirent *entry; |
| 83 |
char buffer[PATH_MAX]; |
| 84 |
|
| 85 |
if (directory == nullptr) { |
| 86 |
/* Is a directory but isn't? */ |
| 87 |
throw std::runtime_error("Path seems invalid: " + std::string(path)); |
| 88 |
} |
| 89 |
|
| 90 |
/* Copy path to buffer. */ |
| 91 |
size_t len = strlen(path); |
| 92 |
size_t size = len + 1; |
| 93 |
memcpy(buffer, path, size); |
| 94 |
|
| 95 |
/* Add the '/' directory separation token if it doesn't exists. */ |
| 96 |
if (buffer[len-1] != '/') { |
| 97 |
buffer[len++] = '/'; |
| 98 |
buffer[len] = '\0'; |
| 99 |
size++; |
| 100 |
} |
| 101 |
|
| 102 |
char *buffer_after_slash = &buffer[len]; |
| 103 |
|
| 104 |
/* Iterate on each file of directory. */ |
| 105 |
while ((entry = readdir(directory)) != nullptr) { |
| 106 |
const char *file = entry->d_name; |
| 107 |
if (strcmp(file, ".") == 0 || strcmp(file, "..") == 0) { |
| 108 |
/* Skip the current and previous directory to avoid infinite loop. */ |
| 109 |
continue; |
| 110 |
} |
| 111 |
|
| 112 |
/* If extension matches, then analyze this file. */ |
| 113 |
const char *extension = strrchr(file, '.'); |
| 114 |
if (extension && strcmp(extension, ".ipa-clones") == 0) { |
| 115 |
strcpy(buffer_after_slash, file); |
| 116 |
Parse(buffer); |
| 117 |
continue; |
| 118 |
} |
| 119 |
|
| 120 |
/* If path is a directory, then analyze it recursively. */ |
| 121 |
strcpy(buffer_after_slash, file); |
| 122 |
if (Is_Directory(buffer)) { |
| 123 |
Open_Recursive(buffer); |
| 124 |
} |
| 125 |
} |
| 126 |
closedir(directory); |
| 127 |
} |
| 128 |
|
| 129 |
const char *IpaClones::LexingState::Lex(void) |
| 130 |
{ |
| 131 |
char *str = strtok(CurrentStateString, ";"); |
| 132 |
|
| 133 |
/* Passing the nullptr to strtok on next iteration results in it calling |
| 134 |
strtok into the correct offset of the original pointer. For more info, |
| 135 |
see `man strtok`. */ |
| 136 |
CurrentStateString = nullptr; |
| 137 |
return str; |
| 138 |
} |
| 139 |
|
| 140 |
IpaClones::IpaDecision IpaClones::LexingState::Get_Decision(const char *str) |
| 141 |
{ |
| 142 |
if (!strcmp(str, "Callgraph removal")) { |
| 143 |
return IPA_REMOVE; |
| 144 |
} |
| 145 |
|
| 146 |
if (!strcmp(str, "Callgraph clone")) { |
| 147 |
return IPA_CLONE; |
| 148 |
} |
| 149 |
|
| 150 |
/* Should never happen. */ |
| 151 |
__builtin_unreachable(); |
| 152 |
} |
| 153 |
|
| 154 |
IpaCloneNode *IpaClones::Get_Or_Create_Node(const std::string &name) |
| 155 |
{ |
| 156 |
IpaCloneNode *ret = Get_Node(name); |
| 157 |
if (ret) { |
| 158 |
return ret; |
| 159 |
} |
| 160 |
|
| 161 |
/* Not found. Create it. */ |
| 162 |
IpaCloneNode node; |
| 163 |
node.Name = name; |
| 164 |
Nodes[name] = node; |
| 165 |
|
| 166 |
return &Nodes[name]; |
| 167 |
} |
| 168 |
|
| 169 |
void IpaClones::Parse(const char *path) |
| 170 |
{ |
| 171 |
FILE *file = fopen(path, "r"); |
| 172 |
if (file == nullptr) { |
| 173 |
throw std::runtime_error("Unable to open ipa-clones file: " + std::string(path)); |
| 174 |
} |
| 175 |
|
| 176 |
char *line; |
| 177 |
|
| 178 |
/** Based on the following function, extracted from GCC source: |
| 179 |
* |
| 180 |
* void |
| 181 |
* dump_callgraph_transformation (const cgraph_node *original, |
| 182 |
* const cgraph_node *clone, |
| 183 |
* const char *suffix) |
| 184 |
* { |
| 185 |
* if (symtab->ipa_clones_dump_file) |
| 186 |
* { |
| 187 |
* fprintf (symtab->ipa_clones_dump_file, |
| 188 |
* "Callgraph clone;%s;%d;%s;%d;%d;%s;%d;%s;%d;%d;%s\n", |
| 189 |
* original->asm_name (), original->order, |
| 190 |
* DECL_SOURCE_FILE (original->decl), |
| 191 |
* DECL_SOURCE_LINE (original->decl), |
| 192 |
* DECL_SOURCE_COLUMN (original->decl), clone->asm_name (), |
| 193 |
* clone->order, DECL_SOURCE_FILE (clone->decl), |
| 194 |
* DECL_SOURCE_LINE (clone->decl), DECL_SOURCE_COLUMN (clone->decl), |
| 195 |
* suffix); |
| 196 |
* |
| 197 |
* symtab->cloned_nodes.add (original); |
| 198 |
* symtab->cloned_nodes.add (clone); |
| 199 |
* } |
| 200 |
* } |
| 201 |
*/ |
| 202 |
|
| 203 |
while ((line = getline_easy(file)) != nullptr) { |
| 204 |
LexingState lexer(line); |
| 205 |
IpaDecision decision = IpaClones::LexingState::Get_Decision(lexer.Lex()); |
| 206 |
|
| 207 |
// The IPA files contain things that we do not use but we need to parse them |
| 208 |
// anyway. So disable the warning for those unused variables. |
| 209 |
#pragma GCC diagnostic push |
| 210 |
#pragma GCC diagnostic ignored "-Wunused-variable" |
| 211 |
const char *original_asm_name = lexer.Lex(); |
| 212 |
long original_order = atol(lexer.Lex()); |
| 213 |
const char *original_filename = lexer.Lex(); |
| 214 |
unsigned original_line = atol(lexer.Lex()); |
| 215 |
unsigned original_column = atol(lexer.Lex()); |
| 216 |
|
| 217 |
if (decision == IPA_CLONE) { |
| 218 |
const char *clone_asm_name = lexer.Lex(); |
| 219 |
long clone_order = atol(lexer.Lex()); |
| 220 |
const char *clone_filename = lexer.Lex(); |
| 221 |
unsigned clone_line = atol(lexer.Lex()); |
| 222 |
unsigned clone_column = atol(lexer.Lex()); |
| 223 |
#pragma GCC diagnostic pop |
| 224 |
|
| 225 |
const char *happened = lexer.Lex(); |
| 226 |
|
| 227 |
const char *cleaned_caller_name = nullptr; |
| 228 |
const char *cleaned_callee_name = nullptr; |
| 229 |
|
| 230 |
if (!strcmp(happened, "inlining to")) { |
| 231 |
cleaned_caller_name = Handle_GCC_Symbol_Quirks((char*)clone_asm_name); |
| 232 |
cleaned_callee_name = Handle_GCC_Symbol_Quirks((char*)original_asm_name); |
| 233 |
|
| 234 |
/* Inlining a symbol to itself makes no sense. Yet this can happen if |
| 235 |
they were actually two symbols that we merged into one on |
| 236 |
Handle_GCC_Symbol_Quirks. */ |
| 237 |
if (strcmp(cleaned_callee_name, cleaned_caller_name) == 0) { |
| 238 |
continue; |
| 239 |
} |
| 240 |
} else if (!strcmp(happened, "isra")) { |
| 241 |
cleaned_caller_name = clone_asm_name; |
| 242 |
cleaned_callee_name = original_asm_name; |
| 243 |
} |
| 244 |
|
| 245 |
if (cleaned_caller_name && cleaned_callee_name) { |
| 246 |
/* This node has been inlined into. */ |
| 247 |
IpaCloneNode *callee = Get_Or_Create_Node(cleaned_callee_name); |
| 248 |
IpaCloneNode *caller = Get_Or_Create_Node(cleaned_caller_name); |
| 249 |
|
| 250 |
callee->InlinedInto.insert(caller); |
| 251 |
caller->Inlines.insert(callee); |
| 252 |
} |
| 253 |
} |
| 254 |
} |
| 255 |
fclose(file); |
| 256 |
} |
| 257 |
|
| 258 |
void IpaClones::Dump(void) |
| 259 |
{ |
| 260 |
for (auto &p : Nodes) { |
| 261 |
bool has_content = false; |
| 262 |
std::cout << " " << p.first; |
| 263 |
for (auto &q : p.second.InlinedInto) { |
| 264 |
if (has_content == false) { |
| 265 |
has_content = true; |
| 266 |
std::cout << " => "; |
| 267 |
} |
| 268 |
std::cout << q->Name << " "; |
| 269 |
} |
| 270 |
std::cout << '\n'; |
| 271 |
} |
| 272 |
} |
| 273 |
|
| 274 |
void IpaClones::Dump_Graphviz(const char *filename) |
| 275 |
{ |
| 276 |
FILE *file = fopen(filename, "w"); |
| 277 |
if (file == nullptr) { |
| 278 |
return; |
| 279 |
} |
| 280 |
|
| 281 |
fprintf(file, "strict digraph {"); |
| 282 |
for (auto &p : Nodes) { |
| 283 |
for (auto &q : p.second.InlinedInto) { |
| 284 |
fprintf(file, "\n\"%s\" -> \"%s\"", p.first.c_str(), q->Name.c_str()); |
| 285 |
} |
| 286 |
} |
| 287 |
fprintf(file, "\n}"); |
| 288 |
fclose(file); |
| 289 |
} |
| 290 |
|
| 291 |
/** Find which symbols are inlined in the function represented by `node`. */ |
| 292 |
void IpaClosure::Find_Inlined_Symbols(IpaCloneNode *node) |
| 293 |
{ |
| 294 |
if (node == nullptr || Is_In_Set(node)) { |
| 295 |
return; |
| 296 |
} |
| 297 |
|
| 298 |
/** Mark node as analyzed. */ |
| 299 |
Set.insert(node); |
| 300 |
|
| 301 |
/** Proceed to other nodes in a DFS fashion. */ |
| 302 |
for (IpaCloneNode *n : node->Inlines) { |
| 303 |
Action(Opaque, node, n); |
| 304 |
Find_Inlined_Symbols(n); |
| 305 |
} |
| 306 |
} |
| 307 |
|
| 308 |
void IpaClosure::Find_Where_Symbol_Is_Inlined(IpaCloneNode *node) |
| 309 |
{ |
| 310 |
if (node == nullptr || Is_In_Set(node)) { |
| 311 |
return; |
| 312 |
} |
| 313 |
|
| 314 |
/** Mark node as analyzed. */ |
| 315 |
Set.insert(node); |
| 316 |
|
| 317 |
/** Proceed to other nodes in a DFS fashion. */ |
| 318 |
for (IpaCloneNode *n : node->InlinedInto) { |
| 319 |
Action(Opaque, node, n); |
| 320 |
Find_Where_Symbol_Is_Inlined(n); |
| 321 |
} |
| 322 |
} |