Import binutils-2.20
[dragonfly.git] / contrib / binutils-2.20 / gold / gc.h
1 // gc.h -- garbage collection of unused sections
2
3 // Copyright 2009 Free Software Foundation, Inc.
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 #ifndef GOLD_GC_H
24 #define GOLD_GC_H
25
26 #include <queue>
27 #include <vector>
28
29 #include "elfcpp.h"
30 #include "symtab.h"
31 #include "icf.h"
32
33 namespace gold
34 {
35
36 class Object;
37
38 template<int size, bool big_endian>
39 class Sized_relobj;
40
41 template<int sh_type, int size, bool big_endian>
42 class Reloc_types;
43
44 class Output_section;
45 class General_options;
46 class Layout;
47
48 typedef std::pair<Object *, unsigned int> Section_id;
49
50 class Garbage_collection
51 {
52   struct Section_id_hash
53   {
54     size_t operator()(const Section_id& loc) const
55     { return reinterpret_cast<uintptr_t>(loc.first) ^ loc.second; }
56   };
57
58  public:
59
60   typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable;
61   typedef std::map<Section_id, Sections_reachable> Section_ref;
62   typedef std::queue<Section_id> Worklist_type;
63
64   Garbage_collection()
65   : is_worklist_ready_(false)
66   { }
67
68   // Accessor methods for the private members.
69
70   Sections_reachable&
71   referenced_list()
72   { return referenced_list_; }
73
74   Section_ref&
75   section_reloc_map()
76   { return this->section_reloc_map_; }
77
78   Worklist_type&
79   worklist()
80   { return this->work_list_; }
81
82   bool
83   is_worklist_ready()
84   { return this->is_worklist_ready_; }
85
86   void
87   worklist_ready()
88   { this->is_worklist_ready_ = true; }
89
90   void
91   do_transitive_closure();
92
93   bool
94   is_section_garbage(Object* obj, unsigned int shndx)
95   { return (this->referenced_list().find(Section_id(obj, shndx))
96             == this->referenced_list().end()); }
97  private:
98
99   Worklist_type work_list_;
100   bool is_worklist_ready_;
101   Section_ref section_reloc_map_;
102   Sections_reachable referenced_list_;
103 };
104
105 // Data to pass between successive invocations of do_layout
106 // in object.cc while garbage collecting.  This data structure
107 // is filled by using the data from Read_symbols_data.
108
109 struct Symbols_data
110 {
111   // Section headers.
112   unsigned char* section_headers_data;
113   // Section names.
114   unsigned char* section_names_data;
115   // Size of section name data in bytes.
116   section_size_type section_names_size;
117   // Symbol data.
118   unsigned char* symbols_data;
119   // Size of symbol data in bytes.
120   section_size_type symbols_size;
121   // Offset of external symbols within symbol data.  This structure
122   // sometimes contains only external symbols, in which case this will
123   // be zero.  Sometimes it contains all symbols.
124   section_offset_type external_symbols_offset;
125   // Symbol names.
126   unsigned char* symbol_names_data;
127   // Size of symbol name data in bytes.
128   section_size_type symbol_names_size;
129 };
130
131 // This function implements the generic part of reloc
132 // processing to map a section to all the sections it
133 // references through relocs.  It is called only during
134 // garbage collection (--gc-sections) and identical code
135 // folding (--icf).
136
137 template<int size, bool big_endian, typename Target_type, int sh_type,
138          typename Scan>
139 inline void
140 gc_process_relocs(
141     const General_options& ,
142     Symbol_table* symtab,
143     Layout*,
144     Target_type* ,
145     Sized_relobj<size, big_endian>* src_obj,
146     unsigned int src_indx,
147     const unsigned char* prelocs,
148     size_t reloc_count,
149     Output_section*,
150     bool ,
151     size_t local_count,
152     const unsigned char* plocal_syms)
153 {
154   Object *dst_obj;
155   unsigned int dst_indx;
156
157   typedef typename Reloc_types<sh_type, size, big_endian>::Reloc Reltype;
158   const int reloc_size = Reloc_types<sh_type, size, big_endian>::reloc_size;
159   const int sym_size = elfcpp::Elf_sizes<size>::sym_size;
160
161   std::vector<Section_id>* secvec = NULL;
162   std::vector<Symbol*>* symvec = NULL;
163   std::vector<std::pair<long long, long long> >* addendvec = NULL;
164   bool is_icf_tracked = false;
165
166   if (parameters->options().icf_enabled()
167       && is_prefix_of(".text.", (src_obj)->section_name(src_indx).c_str()))
168     {
169       is_icf_tracked = true;
170       Section_id src_id(src_obj, src_indx);
171       secvec = &symtab->icf()->section_reloc_list()[src_id];
172       symvec = &symtab->icf()->symbol_reloc_list()[src_id];
173       addendvec = &symtab->icf()->addend_reloc_list()[src_id];
174     }
175
176   for (size_t i = 0; i < reloc_count; ++i, prelocs += reloc_size)
177     {
178       Reltype reloc(prelocs);
179       typename elfcpp::Elf_types<size>::Elf_WXword r_info = reloc.get_r_info();
180       unsigned int r_sym = elfcpp::elf_r_sym<size>(r_info);
181       typename elfcpp::Elf_types<size>::Elf_Swxword addend =
182       Reloc_types<sh_type, size, big_endian>::get_reloc_addend_noerror(&reloc);
183
184       if (r_sym < local_count)
185         {
186           gold_assert(plocal_syms != NULL);
187           typename elfcpp::Sym<size, big_endian> lsym(plocal_syms
188                                                       + r_sym * sym_size);
189           unsigned int shndx = lsym.get_st_shndx();
190           bool is_ordinary;
191           shndx = src_obj->adjust_sym_shndx(r_sym, shndx, &is_ordinary);
192           if (!is_ordinary)
193             continue;
194           dst_obj = src_obj;
195           dst_indx = shndx;
196           Section_id dst_id(dst_obj, dst_indx);
197           if (is_icf_tracked)
198             {
199               (*secvec).push_back(dst_id);
200               (*symvec).push_back(NULL);
201               long long symvalue = static_cast<long long>(lsym.get_st_value());
202               (*addendvec).push_back(std::make_pair(symvalue,
203                                               static_cast<long long>(addend)));
204             }
205           if (shndx == src_indx)
206             continue;
207         }
208       else
209         {
210           Symbol* gsym = src_obj->global_symbol(r_sym);
211           gold_assert(gsym != NULL);
212           if (gsym->is_forwarder())
213             gsym = symtab->resolve_forwards(gsym);
214           if (gsym->source() != Symbol::FROM_OBJECT)
215             continue;
216           bool is_ordinary;
217           dst_obj = gsym->object();
218           dst_indx = gsym->shndx(&is_ordinary);
219           if (!is_ordinary)
220             continue;
221           Section_id dst_id(dst_obj, dst_indx);
222           if (is_icf_tracked)
223             {
224               (*secvec).push_back(dst_id);
225               (*symvec).push_back(gsym);
226               Sized_symbol<size>* sized_gsym =
227                         static_cast<Sized_symbol<size>* >(gsym);
228               long long symvalue =
229                         static_cast<long long>(sized_gsym->value());
230               (*addendvec).push_back(std::make_pair(symvalue,
231                                         static_cast<long long>(addend)));
232             }
233         }
234       if (parameters->options().gc_sections())
235         {
236           Section_id src_id(src_obj, src_indx);
237           Section_id dst_id(dst_obj, dst_indx);
238           Garbage_collection::Section_ref::iterator map_it;
239           map_it = symtab->gc()->section_reloc_map().find(src_id);
240           if (map_it == symtab->gc()->section_reloc_map().end())
241             {
242               symtab->gc()->section_reloc_map()[src_id].insert(dst_id);
243             }
244           else
245             {
246               Garbage_collection::Sections_reachable& v(map_it->second);
247               v.insert(dst_id);
248             }
249         }
250     }
251   return;
252 }
253
254 } // End of namespace gold.
255
256 #endif