Commit | Line | Data |
---|---|---|
ef15dade ST |
1 | // icf.cc -- Identical Code Folding. |
2 | // | |
82704155 | 3 | // Copyright (C) 2009-2019 Free Software Foundation, Inc. |
ef15dade ST |
4 | // Written by Sriraman Tallam <tmsriram@google.com>. |
5 | ||
6 | // This file is part of gold. | |
7 | ||
8 | // This program is free software; you can redistribute it and/or modify | |
9 | // it under the terms of the GNU General Public License as published by | |
10 | // the Free Software Foundation; either version 3 of the License, or | |
11 | // (at your option) any later version. | |
12 | ||
13 | // This program is distributed in the hope that it will be useful, | |
14 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | // GNU General Public License for more details. | |
17 | ||
18 | // You should have received a copy of the GNU General Public License | |
19 | // along with this program; if not, write to the Free Software | |
20 | // Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, | |
21 | // MA 02110-1301, USA. | |
22 | ||
23 | // Identical Code Folding Algorithm | |
24 | // ---------------------------------- | |
25 | // Detecting identical functions is done here and the basic algorithm | |
55a2bb35 | 26 | // is as follows. A checksum is computed on each foldable section using |
ef15dade ST |
27 | // its contents and relocations. If the symbol name corresponding to |
28 | // a relocation is known it is used to compute the checksum. If the | |
29 | // symbol name is not known the stringified name of the object and the | |
30 | // section number pointed to by the relocation is used. The checksums | |
31 | // are stored as keys in a hash map and a section is identical to some | |
32 | // other section if its checksum is already present in the hash map. | |
33 | // Checksum collisions are handled by using a multimap and explicitly | |
34 | // checking the contents when two sections have the same checksum. | |
35 | // | |
36 | // However, two functions A and B with identical text but with | |
55a2bb35 ST |
37 | // relocations pointing to different foldable sections can be identical if |
38 | // the corresponding foldable sections to which their relocations point to | |
ef15dade ST |
39 | // turn out to be identical. Hence, this checksumming process must be |
40 | // done repeatedly until convergence is obtained. Here is an example for | |
41 | // the following case : | |
42 | // | |
43 | // int funcA () int funcB () | |
44 | // { { | |
45 | // return foo(); return goo(); | |
46 | // } } | |
47 | // | |
48 | // The functions funcA and funcB are identical if functions foo() and | |
49 | // goo() are identical. | |
50 | // | |
51 | // Hence, as described above, we repeatedly do the checksumming, | |
52 | // assigning identical functions to the same group, until convergence is | |
53 | // obtained. Now, we have two different ways to do this depending on how | |
54 | // we initialize. | |
55 | // | |
56 | // Algorithm I : | |
57 | // ----------- | |
58 | // We can start with marking all functions as different and repeatedly do | |
59 | // the checksumming. This has the advantage that we do not need to wait | |
60 | // for convergence. We can stop at any point and correctness will be | |
61 | // guaranteed although not all cases would have been found. However, this | |
62 | // has a problem that some cases can never be found even if it is run until | |
63 | // convergence. Here is an example with mutually recursive functions : | |
64 | // | |
65 | // int funcA (int a) int funcB (int a) | |
66 | // { { | |
67 | // if (a == 1) if (a == 1) | |
68 | // return 1; return 1; | |
69 | // return 1 + funcB(a - 1); return 1 + funcA(a - 1); | |
70 | // } } | |
71 | // | |
72 | // In this example funcA and funcB are identical and one of them could be | |
73 | // folded into the other. However, if we start with assuming that funcA | |
74 | // and funcB are not identical, the algorithm, even after it is run to | |
75 | // convergence, cannot detect that they are identical. It should be noted | |
76 | // that even if the functions were self-recursive, Algorithm I cannot catch | |
77 | // that they are identical, at least as is. | |
78 | // | |
79 | // Algorithm II : | |
80 | // ------------ | |
81 | // Here we start with marking all functions as identical and then repeat | |
82 | // the checksumming until convergence. This can detect the above case | |
83 | // mentioned above. It can detect all cases that Algorithm I can and more. | |
84 | // However, the caveat is that it has to be run to convergence. It cannot | |
85 | // be stopped arbitrarily like Algorithm I as correctness cannot be | |
86 | // guaranteed. Algorithm II is not implemented. | |
87 | // | |
88 | // Algorithm I is used because experiments show that about three | |
89 | // iterations are more than enough to achieve convergence. Algorithm I can | |
90 | // handle recursive calls if it is changed to use a special common symbol | |
91 | // for recursive relocs. This seems to be the most common case that | |
92 | // Algorithm I could not catch as is. Mutually recursive calls are not | |
93 | // frequent and Algorithm I wins because of its ability to be stopped | |
94 | // arbitrarily. | |
95 | // | |
96 | // Caveat with using function pointers : | |
97 | // ------------------------------------ | |
98 | // | |
99 | // Programs using function pointer comparisons/checks should use function | |
100 | // folding with caution as the result of such comparisons could be different | |
101 | // when folding takes place. This could lead to unexpected run-time | |
102 | // behaviour. | |
103 | // | |
21bb3914 ST |
104 | // Safe Folding : |
105 | // ------------ | |
106 | // | |
107 | // ICF in safe mode folds only ctors and dtors if their function pointers can | |
108 | // never be taken. Also, for X86-64, safe folding uses the relocation | |
109 | // type to determine if a function's pointer is taken or not and only folds | |
110 | // functions whose pointers are definitely not taken. | |
111 | // | |
112 | // Caveat with safe folding : | |
113 | // ------------------------ | |
114 | // | |
115 | // This applies only to x86_64. | |
116 | // | |
117 | // Position independent executables are created from PIC objects (compiled | |
118 | // with -fPIC) and/or PIE objects (compiled with -fPIE). For PIE objects, the | |
119 | // relocation types for function pointer taken and a call are the same. | |
120 | // Now, it is not always possible to tell if an object used in the link of | |
121 | // a pie executable is a PIC object or a PIE object. Hence, for pie | |
122 | // executables, using relocation types to disambiguate function pointers is | |
123 | // currently disabled. | |
124 | // | |
125 | // Further, it is not correct to use safe folding to build non-pie | |
126 | // executables using PIC/PIE objects. PIC/PIE objects have different | |
127 | // relocation types for function pointers than non-PIC objects, and the | |
128 | // current implementation of safe folding does not handle those relocation | |
129 | // types. Hence, if used, functions whose pointers are taken could still be | |
130 | // folded causing unpredictable run-time behaviour if the pointers were used | |
131 | // in comparisons. | |
132 | // | |
133 | // | |
ef15dade | 134 | // |
55a2bb35 | 135 | // How to run : --icf=[safe|all|none] |
ef15dade ST |
136 | // Optional parameters : --icf-iterations <num> --print-icf-sections |
137 | // | |
138 | // Performance : Less than 20 % link-time overhead on industry strength | |
139 | // applications. Up to 6 % text size reductions. | |
140 | ||
141 | #include "gold.h" | |
142 | #include "object.h" | |
143 | #include "gc.h" | |
144 | #include "icf.h" | |
145 | #include "symtab.h" | |
146 | #include "libiberty.h" | |
032ce4e9 | 147 | #include "demangle.h" |
41cbeecc ST |
148 | #include "elfcpp.h" |
149 | #include "int_encoding.h" | |
ef15dade ST |
150 | |
151 | namespace gold | |
152 | { | |
153 | ||
154 | // This function determines if a section or a group of identical | |
155 | // sections has unique contents. Such unique sections or groups can be | |
156 | // declared final and need not be processed any further. | |
157 | // Parameters : | |
158 | // ID_SECTION : Vector mapping a section index to a Section_id pair. | |
159 | // IS_SECN_OR_GROUP_UNIQUE : To check if a section or a group of identical | |
160 | // sections is already known to be unique. | |
161 | // SECTION_CONTENTS : Contains the section's text and relocs to sections | |
162 | // that cannot be folded. SECTION_CONTENTS are NULL | |
163 | // implies that this function is being called for the | |
164 | // first time before the first iteration of icf. | |
165 | ||
166 | static void | |
167 | preprocess_for_unique_sections(const std::vector<Section_id>& id_section, | |
168 | std::vector<bool>* is_secn_or_group_unique, | |
169 | std::vector<std::string>* section_contents) | |
170 | { | |
171 | Unordered_map<uint32_t, unsigned int> uniq_map; | |
172 | std::pair<Unordered_map<uint32_t, unsigned int>::iterator, bool> | |
173 | uniq_map_insert; | |
174 | ||
175 | for (unsigned int i = 0; i < id_section.size(); i++) | |
176 | { | |
177 | if ((*is_secn_or_group_unique)[i]) | |
178 | continue; | |
179 | ||
180 | uint32_t cksum; | |
181 | Section_id secn = id_section[i]; | |
182 | section_size_type plen; | |
183 | if (section_contents == NULL) | |
184 | { | |
5f9bcf58 CC |
185 | // Lock the object so we can read from it. This is only called |
186 | // single-threaded from queue_middle_tasks, so it is OK to lock. | |
187 | // Unfortunately we have no way to pass in a Task token. | |
188 | const Task* dummy_task = reinterpret_cast<const Task*>(-1); | |
189 | Task_lock_obj<Object> tl(dummy_task, secn.first); | |
ef15dade ST |
190 | const unsigned char* contents; |
191 | contents = secn.first->section_contents(secn.second, | |
192 | &plen, | |
193 | false); | |
194 | cksum = xcrc32(contents, plen, 0xffffffff); | |
195 | } | |
196 | else | |
197 | { | |
198 | const unsigned char* contents_array = reinterpret_cast | |
199 | <const unsigned char*>((*section_contents)[i].c_str()); | |
200 | cksum = xcrc32(contents_array, (*section_contents)[i].length(), | |
201 | 0xffffffff); | |
202 | } | |
203 | uniq_map_insert = uniq_map.insert(std::make_pair(cksum, i)); | |
204 | if (uniq_map_insert.second) | |
205 | { | |
206 | (*is_secn_or_group_unique)[i] = true; | |
207 | } | |
208 | else | |
209 | { | |
210 | (*is_secn_or_group_unique)[i] = false; | |
211 | (*is_secn_or_group_unique)[uniq_map_insert.first->second] = false; | |
212 | } | |
213 | } | |
214 | } | |
215 | ||
84d543b7 ST |
216 | // For SHF_MERGE sections that use REL relocations, the addend is stored in |
217 | // the text section at the relocation offset. Read the addend value given | |
218 | // the pointer to the addend in the text section and the addend size. | |
219 | // Update the addend value if a valid addend is found. | |
220 | // Parameters: | |
221 | // RELOC_ADDEND_PTR : Pointer to the addend in the text section. | |
222 | // ADDEND_SIZE : The size of the addend. | |
223 | // RELOC_ADDEND_VALUE : Pointer to the addend that is updated. | |
224 | ||
225 | inline void | |
226 | get_rel_addend(const unsigned char* reloc_addend_ptr, | |
227 | const unsigned int addend_size, | |
228 | uint64_t* reloc_addend_value) | |
229 | { | |
230 | switch (addend_size) | |
231 | { | |
232 | case 0: | |
233 | break; | |
234 | case 1: | |
235 | *reloc_addend_value = | |
236 | read_from_pointer<8>(reloc_addend_ptr); | |
237 | break; | |
238 | case 2: | |
239 | *reloc_addend_value = | |
240 | read_from_pointer<16>(reloc_addend_ptr); | |
241 | break; | |
242 | case 4: | |
243 | *reloc_addend_value = | |
244 | read_from_pointer<32>(reloc_addend_ptr); | |
245 | break; | |
246 | case 8: | |
247 | *reloc_addend_value = | |
248 | read_from_pointer<64>(reloc_addend_ptr); | |
249 | break; | |
250 | default: | |
251 | gold_unreachable(); | |
252 | } | |
253 | } | |
254 | ||
ef15dade ST |
255 | // This returns the buffer containing the section's contents, both |
256 | // text and relocs. Relocs are differentiated as those pointing to | |
257 | // sections that could be folded and those that cannot. Only relocs | |
258 | // pointing to sections that could be folded are recomputed on | |
259 | // subsequent invocations of this function. | |
260 | // Parameters : | |
261 | // FIRST_ITERATION : true if it is the first invocation. | |
262 | // SECN : Section for which contents are desired. | |
263 | // SECTION_NUM : Unique section number of this section. | |
264 | // NUM_TRACKED_RELOCS : Vector reference to store the number of relocs | |
265 | // to ICF sections. | |
266 | // KEPT_SECTION_ID : Vector which maps folded sections to kept sections. | |
267 | // SECTION_CONTENTS : Store the section's text and relocs to non-ICF | |
268 | // sections. | |
269 | ||
270 | static std::string | |
271 | get_section_contents(bool first_iteration, | |
272 | const Section_id& secn, | |
273 | unsigned int section_num, | |
274 | unsigned int* num_tracked_relocs, | |
275 | Symbol_table* symtab, | |
276 | const std::vector<unsigned int>& kept_section_id, | |
277 | std::vector<std::string>* section_contents) | |
278 | { | |
880473a6 DK |
279 | // Lock the object so we can read from it. This is only called |
280 | // single-threaded from queue_middle_tasks, so it is OK to lock. | |
281 | // Unfortunately we have no way to pass in a Task token. | |
282 | const Task* dummy_task = reinterpret_cast<const Task*>(-1); | |
283 | Task_lock_obj<Object> tl(dummy_task, secn.first); | |
284 | ||
ef15dade ST |
285 | section_size_type plen; |
286 | const unsigned char* contents = NULL; | |
ef15dade | 287 | if (first_iteration) |
880473a6 | 288 | contents = secn.first->section_contents(secn.second, &plen, false); |
ef15dade ST |
289 | |
290 | // The buffer to hold all the contents including relocs. A checksum | |
291 | // is then computed on this buffer. | |
292 | std::string buffer; | |
293 | std::string icf_reloc_buffer; | |
294 | ||
295 | if (num_tracked_relocs) | |
296 | *num_tracked_relocs = 0; | |
297 | ||
b487ad64 ST |
298 | Icf::Reloc_info_list& reloc_info_list = |
299 | symtab->icf()->reloc_info_list(); | |
ef15dade | 300 | |
b487ad64 ST |
301 | Icf::Reloc_info_list::iterator it_reloc_info_list = |
302 | reloc_info_list.find(secn); | |
ef15dade ST |
303 | |
304 | buffer.clear(); | |
305 | icf_reloc_buffer.clear(); | |
306 | ||
307 | // Process relocs and put them into the buffer. | |
308 | ||
b487ad64 | 309 | if (it_reloc_info_list != reloc_info_list.end()) |
ef15dade | 310 | { |
c4eb27e1 | 311 | Icf::Sections_reachable_info &v = |
b487ad64 | 312 | (it_reloc_info_list->second).section_info; |
ef38fd8a | 313 | // Stores the information of the symbol pointed to by the reloc. |
c4eb27e1 | 314 | const Icf::Symbol_info &s = (it_reloc_info_list->second).symbol_info; |
ef38fd8a | 315 | // Stores the addend and the symbol value. |
c4eb27e1 | 316 | Icf::Addend_info &a = (it_reloc_info_list->second).addend_info; |
ef38fd8a | 317 | // Stores the offset of the reloc. |
c4eb27e1 ST |
318 | const Icf::Offset_info &o = (it_reloc_info_list->second).offset_info; |
319 | const Icf::Reloc_addend_size_info &reloc_addend_size_info = | |
41cbeecc | 320 | (it_reloc_info_list->second).reloc_addend_size_info; |
b487ad64 | 321 | Icf::Sections_reachable_info::iterator it_v = v.begin(); |
c4eb27e1 | 322 | Icf::Symbol_info::const_iterator it_s = s.begin(); |
ef15dade | 323 | Icf::Addend_info::iterator it_a = a.begin(); |
c4eb27e1 ST |
324 | Icf::Offset_info::const_iterator it_o = o.begin(); |
325 | Icf::Reloc_addend_size_info::const_iterator it_addend_size = | |
41cbeecc | 326 | reloc_addend_size_info.begin(); |
ef15dade | 327 | |
41cbeecc | 328 | for (; it_v != v.end(); ++it_v, ++it_s, ++it_a, ++it_o, ++it_addend_size) |
ef15dade | 329 | { |
651d1620 CC |
330 | Symbol* gsym = *it_s; |
331 | bool is_section_symbol = false; | |
332 | ||
333 | // A -1 value in the symbol vector indicates a local section symbol. | |
334 | if (gsym == reinterpret_cast<Symbol*>(-1)) | |
335 | { | |
336 | is_section_symbol = true; | |
337 | gsym = NULL; | |
338 | } | |
339 | ||
ad3d8a2f AM |
340 | if (first_iteration |
341 | && it_v->first != NULL) | |
342 | { | |
343 | Symbol_location loc; | |
344 | loc.object = it_v->first; | |
345 | loc.shndx = it_v->second; | |
346 | loc.offset = convert_types<off_t, long long>(it_a->first | |
347 | + it_a->second); | |
348 | // Look through function descriptors | |
349 | parameters->target().function_location(&loc); | |
350 | if (loc.shndx != it_v->second) | |
351 | { | |
352 | it_v->second = loc.shndx; | |
353 | // Modify symvalue/addend to the code entry. | |
354 | it_a->first = loc.offset; | |
355 | it_a->second = 0; | |
356 | } | |
357 | } | |
358 | ||
b487ad64 | 359 | // ADDEND_STR stores the symbol value and addend and offset, |
9b547ce6 | 360 | // each at most 16 hex digits long. it_a points to a pair |
ef15dade ST |
361 | // where first is the symbol value and second is the |
362 | // addend. | |
b487ad64 | 363 | char addend_str[50]; |
bb0bfe4f DK |
364 | |
365 | // It would be nice if we could use format macros in inttypes.h | |
366 | // here but there are not in ISO/IEC C++ 1998. | |
651d1620 | 367 | snprintf(addend_str, sizeof(addend_str), "%llx %llx %llx", |
bb0bfe4f DK |
368 | static_cast<long long>((*it_a).first), |
369 | static_cast<long long>((*it_a).second), | |
370 | static_cast<unsigned long long>(*it_o)); | |
ef38fd8a ST |
371 | |
372 | // If the symbol pointed to by the reloc is not in an ordinary | |
373 | // section or if the symbol type is not FROM_OBJECT, then the | |
374 | // object is NULL. | |
375 | if (it_v->first == NULL) | |
376 | { | |
377 | if (first_iteration) | |
378 | { | |
379 | // If the symbol name is available, use it. | |
651d1620 CC |
380 | if (gsym != NULL) |
381 | buffer.append(gsym->name()); | |
ef38fd8a ST |
382 | // Append the addend. |
383 | buffer.append(addend_str); | |
384 | buffer.append("@"); | |
385 | } | |
386 | continue; | |
387 | } | |
388 | ||
ef15dade ST |
389 | Section_id reloc_secn(it_v->first, it_v->second); |
390 | ||
391 | // If this reloc turns back and points to the same section, | |
392 | // like a recursive call, use a special symbol to mark this. | |
393 | if (reloc_secn.first == secn.first | |
394 | && reloc_secn.second == secn.second) | |
395 | { | |
396 | if (first_iteration) | |
397 | { | |
398 | buffer.append("R"); | |
399 | buffer.append(addend_str); | |
400 | buffer.append("@"); | |
401 | } | |
402 | continue; | |
403 | } | |
404 | Icf::Uniq_secn_id_map& section_id_map = | |
405 | symtab->icf()->section_to_int_map(); | |
406 | Icf::Uniq_secn_id_map::iterator section_id_map_it = | |
407 | section_id_map.find(reloc_secn); | |
651d1620 CC |
408 | bool is_sym_preemptible = (gsym != NULL |
409 | && !gsym->is_from_dynobj() | |
410 | && !gsym->is_undefined() | |
411 | && gsym->is_preemptible()); | |
ce97fa81 ST |
412 | if (!is_sym_preemptible |
413 | && section_id_map_it != section_id_map.end()) | |
ef15dade ST |
414 | { |
415 | // This is a reloc to a section that might be folded. | |
416 | if (num_tracked_relocs) | |
417 | (*num_tracked_relocs)++; | |
418 | ||
419 | char kept_section_str[10]; | |
420 | unsigned int secn_id = section_id_map_it->second; | |
421 | snprintf(kept_section_str, sizeof(kept_section_str), "%u", | |
422 | kept_section_id[secn_id]); | |
423 | if (first_iteration) | |
424 | { | |
425 | buffer.append("ICF_R"); | |
426 | buffer.append(addend_str); | |
427 | } | |
428 | icf_reloc_buffer.append(kept_section_str); | |
429 | // Append the addend. | |
430 | icf_reloc_buffer.append(addend_str); | |
431 | icf_reloc_buffer.append("@"); | |
432 | } | |
433 | else | |
434 | { | |
435 | // This is a reloc to a section that cannot be folded. | |
436 | // Process it only in the first iteration. | |
437 | if (!first_iteration) | |
438 | continue; | |
439 | ||
440 | uint64_t secn_flags = (it_v->first)->section_flags(it_v->second); | |
441 | // This reloc points to a merge section. Hash the | |
442 | // contents of this section. | |
c95e9f27 | 443 | if ((secn_flags & elfcpp::SHF_MERGE) != 0 |
b3ce541e | 444 | && parameters->target().can_icf_inline_merge_sections()) |
ef15dade ST |
445 | { |
446 | uint64_t entsize = | |
447 | (it_v->first)->section_entsize(it_v->second); | |
ce97fa81 | 448 | long long offset = it_a->first; |
651d1620 CC |
449 | |
450 | // Handle SHT_RELA and SHT_REL addends. Only one of these | |
451 | // addends exists. When pointing to a merge section, the | |
452 | // addend only matters if it's relative to a section | |
453 | // symbol. In order to unambiguously identify the target | |
454 | // of the relocation, the compiler (and assembler) must use | |
455 | // a local non-section symbol unless Symbol+Addend does in | |
456 | // fact point directly to the target. (In other words, | |
457 | // a bias for a pc-relative reference or a non-zero based | |
458 | // access forces the use of a local symbol, and the addend | |
459 | // is used only to provide that bias.) | |
460 | uint64_t reloc_addend_value = 0; | |
461 | if (is_section_symbol) | |
462 | { | |
463 | // Get the SHT_RELA addend. For RELA relocations, | |
464 | // we have the addend from the relocation. | |
465 | reloc_addend_value = it_a->second; | |
466 | ||
467 | // Handle SHT_REL addends. | |
468 | // For REL relocations, we need to fetch the addend | |
469 | // from the section contents. | |
470 | const unsigned char* reloc_addend_ptr = | |
471 | contents + static_cast<unsigned long long>(*it_o); | |
472 | ||
473 | // Update the addend value with the SHT_REL addend if | |
474 | // available. | |
475 | get_rel_addend(reloc_addend_ptr, *it_addend_size, | |
476 | &reloc_addend_value); | |
477 | ||
478 | // Ignore the addend when it is a negative value. | |
479 | // See the comments in Merged_symbol_value::value | |
480 | // in object.h. | |
481 | if (reloc_addend_value < 0xffffff00) | |
482 | offset = offset + reloc_addend_value; | |
483 | } | |
41cbeecc | 484 | |
ef15dade | 485 | section_size_type secn_len; |
84d543b7 | 486 | |
ef15dade ST |
487 | const unsigned char* str_contents = |
488 | (it_v->first)->section_contents(it_v->second, | |
489 | &secn_len, | |
490 | false) + offset; | |
84d543b7 ST |
491 | gold_assert (offset < (long long) secn_len); |
492 | ||
ef15dade ST |
493 | if ((secn_flags & elfcpp::SHF_STRINGS) != 0) |
494 | { | |
495 | // String merge section. | |
496 | const char* str_char = | |
497 | reinterpret_cast<const char*>(str_contents); | |
498 | switch(entsize) | |
499 | { | |
500 | case 1: | |
501 | { | |
502 | buffer.append(str_char); | |
503 | break; | |
504 | } | |
505 | case 2: | |
506 | { | |
507 | const uint16_t* ptr_16 = | |
508 | reinterpret_cast<const uint16_t*>(str_char); | |
509 | unsigned int strlen_16 = 0; | |
510 | // Find the NULL character. | |
511 | while(*(ptr_16 + strlen_16) != 0) | |
512 | strlen_16++; | |
513 | buffer.append(str_char, strlen_16 * 2); | |
514 | } | |
515 | break; | |
516 | case 4: | |
517 | { | |
518 | const uint32_t* ptr_32 = | |
519 | reinterpret_cast<const uint32_t*>(str_char); | |
520 | unsigned int strlen_32 = 0; | |
521 | // Find the NULL character. | |
522 | while(*(ptr_32 + strlen_32) != 0) | |
523 | strlen_32++; | |
524 | buffer.append(str_char, strlen_32 * 4); | |
525 | } | |
526 | break; | |
527 | default: | |
528 | gold_unreachable(); | |
529 | } | |
530 | } | |
531 | else | |
532 | { | |
84d543b7 ST |
533 | // Use the entsize to determine the length to copy. |
534 | uint64_t bufsize = entsize; | |
535 | // If entsize is too big, copy all the remaining bytes. | |
536 | if ((offset + entsize) > secn_len) | |
537 | bufsize = secn_len - offset; | |
538 | buffer.append(reinterpret_cast<const | |
ef15dade | 539 | char*>(str_contents), |
84d543b7 | 540 | bufsize); |
ef15dade | 541 | } |
d62d0f5f | 542 | buffer.append("@"); |
ef15dade | 543 | } |
651d1620 | 544 | else if (gsym != NULL) |
ef15dade ST |
545 | { |
546 | // If symbol name is available use that. | |
651d1620 | 547 | buffer.append(gsym->name()); |
ef15dade ST |
548 | // Append the addend. |
549 | buffer.append(addend_str); | |
550 | buffer.append("@"); | |
551 | } | |
552 | else | |
553 | { | |
554 | // Symbol name is not available, like for a local symbol, | |
555 | // use object and section id. | |
556 | buffer.append(it_v->first->name()); | |
557 | char secn_id[10]; | |
558 | snprintf(secn_id, sizeof(secn_id), "%u",it_v->second); | |
559 | buffer.append(secn_id); | |
560 | // Append the addend. | |
561 | buffer.append(addend_str); | |
562 | buffer.append("@"); | |
563 | } | |
564 | } | |
565 | } | |
566 | } | |
567 | ||
568 | if (first_iteration) | |
569 | { | |
570 | buffer.append("Contents = "); | |
571 | buffer.append(reinterpret_cast<const char*>(contents), plen); | |
5c3024d2 | 572 | // Store the section contents that don't change to avoid recomputing |
ef15dade ST |
573 | // during the next call to this function. |
574 | (*section_contents)[section_num] = buffer; | |
575 | } | |
576 | else | |
577 | { | |
578 | gold_assert(buffer.empty()); | |
579 | // Reuse the contents computed in the previous iteration. | |
580 | buffer.append((*section_contents)[section_num]); | |
581 | } | |
582 | ||
583 | buffer.append(icf_reloc_buffer); | |
584 | return buffer; | |
585 | } | |
586 | ||
587 | // This function computes a checksum on each section to detect and form | |
588 | // groups of identical sections. The first iteration does this for all | |
589 | // sections. | |
590 | // Further iterations do this only for the kept sections from each group to | |
591 | // determine if larger groups of identical sections could be formed. The | |
592 | // first section in each group is the kept section for that group. | |
593 | // | |
594 | // CRC32 is the checksumming algorithm and can have collisions. That is, | |
595 | // two sections with different contents can have the same checksum. Hence, | |
596 | // a multimap is used to maintain more than one group of checksum | |
597 | // identical sections. A section is added to a group only after its | |
598 | // contents are explicitly compared with the kept section of the group. | |
599 | // | |
600 | // Parameters : | |
601 | // ITERATION_NUM : Invocation instance of this function. | |
602 | // NUM_TRACKED_RELOCS : Vector reference to store the number of relocs | |
603 | // to ICF sections. | |
604 | // KEPT_SECTION_ID : Vector which maps folded sections to kept sections. | |
605 | // ID_SECTION : Vector mapping a section to an unique integer. | |
606 | // IS_SECN_OR_GROUP_UNIQUE : To check if a section or a group of identical | |
9b547ce6 | 607 | // sections is already known to be unique. |
ef15dade ST |
608 | // SECTION_CONTENTS : Store the section's text and relocs to non-ICF |
609 | // sections. | |
610 | ||
611 | static bool | |
612 | match_sections(unsigned int iteration_num, | |
613 | Symbol_table* symtab, | |
614 | std::vector<unsigned int>* num_tracked_relocs, | |
615 | std::vector<unsigned int>* kept_section_id, | |
616 | const std::vector<Section_id>& id_section, | |
ac423761 | 617 | const std::vector<uint64_t>& section_addraligns, |
ef15dade ST |
618 | std::vector<bool>* is_secn_or_group_unique, |
619 | std::vector<std::string>* section_contents) | |
620 | { | |
621 | Unordered_multimap<uint32_t, unsigned int> section_cksum; | |
622 | std::pair<Unordered_multimap<uint32_t, unsigned int>::iterator, | |
623 | Unordered_multimap<uint32_t, unsigned int>::iterator> key_range; | |
624 | bool converged = true; | |
625 | ||
626 | if (iteration_num == 1) | |
627 | preprocess_for_unique_sections(id_section, | |
628 | is_secn_or_group_unique, | |
629 | NULL); | |
630 | else | |
631 | preprocess_for_unique_sections(id_section, | |
632 | is_secn_or_group_unique, | |
633 | section_contents); | |
634 | ||
635 | std::vector<std::string> full_section_contents; | |
636 | ||
637 | for (unsigned int i = 0; i < id_section.size(); i++) | |
638 | { | |
639 | full_section_contents.push_back(""); | |
640 | if ((*is_secn_or_group_unique)[i]) | |
641 | continue; | |
642 | ||
643 | Section_id secn = id_section[i]; | |
644 | std::string this_secn_contents; | |
645 | uint32_t cksum; | |
646 | if (iteration_num == 1) | |
647 | { | |
648 | unsigned int num_relocs = 0; | |
649 | this_secn_contents = get_section_contents(true, secn, i, &num_relocs, | |
650 | symtab, (*kept_section_id), | |
651 | section_contents); | |
652 | (*num_tracked_relocs)[i] = num_relocs; | |
653 | } | |
654 | else | |
655 | { | |
656 | if ((*kept_section_id)[i] != i) | |
657 | { | |
ac423761 | 658 | // This section is already folded into something. |
ef15dade ST |
659 | continue; |
660 | } | |
661 | this_secn_contents = get_section_contents(false, secn, i, NULL, | |
662 | symtab, (*kept_section_id), | |
663 | section_contents); | |
664 | } | |
665 | ||
666 | const unsigned char* this_secn_contents_array = | |
667 | reinterpret_cast<const unsigned char*>(this_secn_contents.c_str()); | |
668 | cksum = xcrc32(this_secn_contents_array, this_secn_contents.length(), | |
669 | 0xffffffff); | |
670 | size_t count = section_cksum.count(cksum); | |
671 | ||
672 | if (count == 0) | |
673 | { | |
674 | // Start a group with this cksum. | |
675 | section_cksum.insert(std::make_pair(cksum, i)); | |
676 | full_section_contents[i] = this_secn_contents; | |
677 | } | |
678 | else | |
679 | { | |
680 | key_range = section_cksum.equal_range(cksum); | |
681 | Unordered_multimap<uint32_t, unsigned int>::iterator it; | |
682 | // Search all the groups with this cksum for a match. | |
683 | for (it = key_range.first; it != key_range.second; ++it) | |
684 | { | |
685 | unsigned int kept_section = it->second; | |
686 | if (full_section_contents[kept_section].length() | |
687 | != this_secn_contents.length()) | |
688 | continue; | |
689 | if (memcmp(full_section_contents[kept_section].c_str(), | |
690 | this_secn_contents.c_str(), | |
691 | this_secn_contents.length()) != 0) | |
692 | continue; | |
ac423761 GN |
693 | |
694 | // Check section alignment here. | |
695 | // The section with the larger alignment requirement | |
696 | // should be kept. We assume alignment can only be | |
5c3024d2 | 697 | // zero or positive integral powers of two. |
ac423761 GN |
698 | uint64_t align_i = section_addraligns[i]; |
699 | uint64_t align_kept = section_addraligns[kept_section]; | |
700 | if (align_i <= align_kept) | |
701 | { | |
702 | (*kept_section_id)[i] = kept_section; | |
703 | } | |
704 | else | |
705 | { | |
706 | (*kept_section_id)[kept_section] = i; | |
707 | it->second = i; | |
708 | full_section_contents[kept_section].swap( | |
709 | full_section_contents[i]); | |
710 | } | |
711 | ||
ef15dade ST |
712 | converged = false; |
713 | break; | |
714 | } | |
715 | if (it == key_range.second) | |
716 | { | |
717 | // Create a new group for this cksum. | |
718 | section_cksum.insert(std::make_pair(cksum, i)); | |
719 | full_section_contents[i] = this_secn_contents; | |
720 | } | |
721 | } | |
722 | // If there are no relocs to foldable sections do not process | |
723 | // this section any further. | |
724 | if (iteration_num == 1 && (*num_tracked_relocs)[i] == 0) | |
725 | (*is_secn_or_group_unique)[i] = true; | |
726 | } | |
727 | ||
ac423761 GN |
728 | // If a section was folded into another section that was later folded |
729 | // again then the former has to be updated. | |
730 | for (unsigned int i = 0; i < id_section.size(); i++) | |
731 | { | |
732 | // Find the end of the folding chain | |
733 | unsigned int kept = i; | |
734 | while ((*kept_section_id)[kept] != kept) | |
735 | { | |
736 | kept = (*kept_section_id)[kept]; | |
737 | } | |
738 | // Update every element of the chain | |
739 | unsigned int current = i; | |
740 | while ((*kept_section_id)[current] != kept) | |
741 | { | |
742 | unsigned int next = (*kept_section_id)[current]; | |
743 | (*kept_section_id)[current] = kept; | |
744 | current = next; | |
745 | } | |
746 | } | |
747 | ||
ef15dade ST |
748 | return converged; |
749 | } | |
750 | ||
032ce4e9 | 751 | // During safe icf (--icf=safe), only fold functions that are ctors or dtors. |
4e271fff | 752 | // This function returns true if the section name is that of a ctor or a dtor. |
032ce4e9 ST |
753 | |
754 | static bool | |
4e271fff | 755 | is_function_ctor_or_dtor(const std::string& section_name) |
032ce4e9 | 756 | { |
4e271fff ST |
757 | const char* mangled_func_name = strrchr(section_name.c_str(), '.'); |
758 | gold_assert(mangled_func_name != NULL); | |
759 | if ((is_prefix_of("._ZN", mangled_func_name) | |
760 | || is_prefix_of("._ZZ", mangled_func_name)) | |
761 | && (is_gnu_v3_mangled_ctor(mangled_func_name + 1) | |
762 | || is_gnu_v3_mangled_dtor(mangled_func_name + 1))) | |
032ce4e9 ST |
763 | { |
764 | return true; | |
765 | } | |
766 | return false; | |
767 | } | |
ef15dade ST |
768 | |
769 | // This is the main ICF function called in gold.cc. This does the | |
770 | // initialization and calls match_sections repeatedly (twice by default) | |
771 | // which computes the crc checksums and detects identical functions. | |
772 | ||
773 | void | |
774 | Icf::find_identical_sections(const Input_objects* input_objects, | |
775 | Symbol_table* symtab) | |
776 | { | |
777 | unsigned int section_num = 0; | |
2ea97941 | 778 | std::vector<unsigned int> num_tracked_relocs; |
ac423761 | 779 | std::vector<uint64_t> section_addraligns; |
ef15dade ST |
780 | std::vector<bool> is_secn_or_group_unique; |
781 | std::vector<std::string> section_contents; | |
21bb3914 | 782 | const Target& target = parameters->target(); |
ef15dade ST |
783 | |
784 | // Decide which sections are possible candidates first. | |
785 | ||
786 | for (Input_objects::Relobj_iterator p = input_objects->relobj_begin(); | |
787 | p != input_objects->relobj_end(); | |
788 | ++p) | |
789 | { | |
5f9bcf58 CC |
790 | // Lock the object so we can read from it. This is only called |
791 | // single-threaded from queue_middle_tasks, so it is OK to lock. | |
792 | // Unfortunately we have no way to pass in a Task token. | |
793 | const Task* dummy_task = reinterpret_cast<const Task*>(-1); | |
794 | Task_lock_obj<Object> tl(dummy_task, *p); | |
795 | ||
ef15dade ST |
796 | for (unsigned int i = 0;i < (*p)->shnum(); ++i) |
797 | { | |
4e271fff | 798 | const std::string section_name = (*p)->section_name(i); |
55a2bb35 | 799 | if (!is_section_foldable_candidate(section_name)) |
ef15dade ST |
800 | continue; |
801 | if (!(*p)->is_section_included(i)) | |
802 | continue; | |
803 | if (parameters->options().gc_sections() | |
804 | && symtab->gc()->is_section_garbage(*p, i)) | |
805 | continue; | |
55a2bb35 ST |
806 | // With --icf=safe, check if the mangled function name is a ctor |
807 | // or a dtor. The mangled function name can be obtained from the | |
808 | // section name by stripping the section prefix. | |
032ce4e9 | 809 | if (parameters->options().icf_safe_folding() |
4e271fff | 810 | && !is_function_ctor_or_dtor(section_name) |
21bb3914 ST |
811 | && (!target.can_check_for_function_pointers() |
812 | || section_has_function_pointers(*p, i))) | |
813 | { | |
814 | continue; | |
815 | } | |
ef15dade ST |
816 | this->id_section_.push_back(Section_id(*p, i)); |
817 | this->section_id_[Section_id(*p, i)] = section_num; | |
818 | this->kept_section_id_.push_back(section_num); | |
2ea97941 | 819 | num_tracked_relocs.push_back(0); |
ac423761 | 820 | section_addraligns.push_back((*p)->section_addralign(i)); |
ef15dade ST |
821 | is_secn_or_group_unique.push_back(false); |
822 | section_contents.push_back(""); | |
823 | section_num++; | |
824 | } | |
825 | } | |
826 | ||
827 | unsigned int num_iterations = 0; | |
828 | ||
829 | // Default number of iterations to run ICF is 2. | |
830 | unsigned int max_iterations = (parameters->options().icf_iterations() > 0) | |
831 | ? parameters->options().icf_iterations() | |
832 | : 2; | |
833 | ||
834 | bool converged = false; | |
835 | ||
836 | while (!converged && (num_iterations < max_iterations)) | |
837 | { | |
838 | num_iterations++; | |
839 | converged = match_sections(num_iterations, symtab, | |
2ea97941 | 840 | &num_tracked_relocs, &this->kept_section_id_, |
ac423761 GN |
841 | this->id_section_, section_addraligns, |
842 | &is_secn_or_group_unique, §ion_contents); | |
ef15dade ST |
843 | } |
844 | ||
845 | if (parameters->options().print_icf_sections()) | |
846 | { | |
847 | if (converged) | |
848 | gold_info(_("%s: ICF Converged after %u iteration(s)"), | |
849 | program_name, num_iterations); | |
850 | else | |
851 | gold_info(_("%s: ICF stopped after %u iteration(s)"), | |
852 | program_name, num_iterations); | |
853 | } | |
854 | ||
48c187ce ST |
855 | // Unfold --keep-unique symbols. |
856 | for (options::String_set::const_iterator p = | |
857 | parameters->options().keep_unique_begin(); | |
858 | p != parameters->options().keep_unique_end(); | |
859 | ++p) | |
860 | { | |
861 | const char* name = p->c_str(); | |
862 | Symbol* sym = symtab->lookup(name); | |
ef5e0cb1 ST |
863 | if (sym == NULL) |
864 | { | |
865 | gold_warning(_("Could not find symbol %s to unfold\n"), name); | |
866 | } | |
867 | else if (sym->source() == Symbol::FROM_OBJECT | |
868 | && !sym->object()->is_dynamic()) | |
48c187ce | 869 | { |
efc6fa12 | 870 | Relobj* obj = static_cast<Relobj*>(sym->object()); |
48c187ce ST |
871 | bool is_ordinary; |
872 | unsigned int shndx = sym->shndx(&is_ordinary); | |
873 | if (is_ordinary) | |
874 | { | |
875 | this->unfold_section(obj, shndx); | |
876 | } | |
877 | } | |
878 | ||
879 | } | |
880 | ||
ef15dade ST |
881 | this->icf_ready(); |
882 | } | |
883 | ||
48c187ce ST |
884 | // Unfolds the section denoted by OBJ and SHNDX if folded. |
885 | ||
886 | void | |
efc6fa12 | 887 | Icf::unfold_section(Relobj* obj, unsigned int shndx) |
48c187ce ST |
888 | { |
889 | Section_id secn(obj, shndx); | |
890 | Uniq_secn_id_map::iterator it = this->section_id_.find(secn); | |
891 | if (it == this->section_id_.end()) | |
892 | return; | |
893 | unsigned int section_num = it->second; | |
894 | unsigned int kept_section_id = this->kept_section_id_[section_num]; | |
895 | if (kept_section_id != section_num) | |
896 | this->kept_section_id_[section_num] = section_num; | |
897 | } | |
898 | ||
ef15dade ST |
899 | // This function determines if the section corresponding to the |
900 | // given object and index is folded based on if the kept section | |
901 | // is different from this section. | |
902 | ||
903 | bool | |
efc6fa12 | 904 | Icf::is_section_folded(Relobj* obj, unsigned int shndx) |
ef15dade ST |
905 | { |
906 | Section_id secn(obj, shndx); | |
907 | Uniq_secn_id_map::iterator it = this->section_id_.find(secn); | |
908 | if (it == this->section_id_.end()) | |
909 | return false; | |
910 | unsigned int section_num = it->second; | |
911 | unsigned int kept_section_id = this->kept_section_id_[section_num]; | |
912 | return kept_section_id != section_num; | |
913 | } | |
914 | ||
915 | // This function returns the folded section for the given section. | |
916 | ||
917 | Section_id | |
efc6fa12 | 918 | Icf::get_folded_section(Relobj* dup_obj, unsigned int dup_shndx) |
ef15dade ST |
919 | { |
920 | Section_id dup_secn(dup_obj, dup_shndx); | |
921 | Uniq_secn_id_map::iterator it = this->section_id_.find(dup_secn); | |
922 | gold_assert(it != this->section_id_.end()); | |
923 | unsigned int section_num = it->second; | |
924 | unsigned int kept_section_id = this->kept_section_id_[section_num]; | |
925 | Section_id folded_section = this->id_section_[kept_section_id]; | |
926 | return folded_section; | |
927 | } | |
928 | ||
929 | } // End of namespace gold. |