• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- SymbolCategory.cpp -------------------------------------------------===//
2 //
3 //                     The MCLinker Project
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 #include "mcld/MC/SymbolCategory.h"
10 
11 #include "mcld/LD/LDSymbol.h"
12 #include "mcld/LD/ResolveInfo.h"
13 
14 #include <algorithm>
15 #include <cassert>
16 
17 namespace mcld {
18 
19 //===----------------------------------------------------------------------===//
20 // Category
categorize(const ResolveInfo & pInfo)21 SymbolCategory::Category::Type SymbolCategory::Category::categorize(
22     const ResolveInfo& pInfo) {
23   if (ResolveInfo::File == pInfo.type())
24     return Category::File;
25   if (ResolveInfo::Local == pInfo.binding())
26     return Category::Local;
27   if (ResolveInfo::Common == pInfo.desc())
28     return Category::Common;
29   if (ResolveInfo::Default == pInfo.visibility() ||
30       ResolveInfo::Protected == pInfo.visibility())
31     return Category::Dynamic;
32   return Category::Regular;
33 }
34 
35 //===----------------------------------------------------------------------===//
36 // SymbolCategory
SymbolCategory()37 SymbolCategory::SymbolCategory() {
38   m_pFile = new Category(Category::File);
39   m_pLocal = new Category(Category::Local);
40   m_pLocalDyn = new Category(Category::LocalDyn);
41   m_pCommon = new Category(Category::Common);
42   m_pDynamic = new Category(Category::Dynamic);
43   m_pRegular = new Category(Category::Regular);
44 
45   m_pFile->next = m_pLocal;
46   m_pLocal->next = m_pLocalDyn;
47   m_pLocalDyn->next = m_pCommon;
48   m_pCommon->next = m_pDynamic;
49   m_pDynamic->next = m_pRegular;
50 
51   m_pRegular->prev = m_pDynamic;
52   m_pDynamic->prev = m_pCommon;
53   m_pCommon->prev = m_pLocalDyn;
54   m_pLocalDyn->prev = m_pLocal;
55   m_pLocal->prev = m_pFile;
56 }
57 
~SymbolCategory()58 SymbolCategory::~SymbolCategory() {
59   Category* current = m_pFile;
60   while (current != NULL) {
61     Category* tmp = current;
62     current = current->next;
63     delete tmp;
64   }
65 }
66 
add(LDSymbol & pSymbol,Category::Type pTarget)67 SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol, Category::Type pTarget) {
68   Category* current = m_pRegular;
69   m_OutputSymbols.push_back(&pSymbol);
70 
71   // use non-stable bubble sort to arrange the order of symbols.
72   while (current != NULL) {
73     if (current->type == pTarget) {
74       current->end++;
75       break;
76     } else {
77       if (!current->empty()) {
78         std::swap(m_OutputSymbols[current->begin],
79                   m_OutputSymbols[current->end]);
80       }
81       current->end++;
82       current->begin++;
83       current = current->prev;
84     }
85   }
86   return *this;
87 }
88 
add(LDSymbol & pSymbol)89 SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol) {
90   assert(pSymbol.resolveInfo() != NULL);
91   return add(pSymbol, Category::categorize(*pSymbol.resolveInfo()));
92 }
93 
forceLocal(LDSymbol & pSymbol)94 SymbolCategory& SymbolCategory::forceLocal(LDSymbol& pSymbol) {
95   return add(pSymbol, Category::Local);
96 }
97 
arrange(LDSymbol & pSymbol,Category::Type pSource,Category::Type pTarget)98 SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol,
99                                         Category::Type pSource,
100                                         Category::Type pTarget) {
101   int distance = pTarget - pSource;
102   if (distance == 0) {
103     // in the same category, do not need to re-arrange
104     return *this;
105   }
106 
107   // source and target are not in the same category
108   // find the category of source
109   Category* current = m_pFile;
110   while (current != NULL) {
111     if (pSource == current->type)
112       break;
113     current = current->next;
114   }
115 
116   assert(current != NULL);
117   size_t pos = 0;
118   if (!current->empty()) {
119     // find the position of source
120     pos = current->begin;
121     while (pos != current->end) {
122       if (m_OutputSymbols[pos] == &pSymbol)
123         break;
124       ++pos;
125     }
126   }
127   // FIXME: Try to search the symbol explicitly, if symbol is not in the given
128   // source category. Or we need to add some logics like shouldForceLocal() in
129   // SymbolCategory::Category::categorize().
130   if (current->end == pos || current->empty()) {
131     current = m_pFile;
132     do {
133       pos = current->begin;
134       while (pos != current->end) {
135         if (m_OutputSymbols[pos] == &pSymbol) {
136           distance = pTarget - current->type;
137           break;
138         }
139         ++pos;
140       }
141       if (pos != current->end)
142         break;
143       current = current->next;
144     } while (current != NULL);
145     assert(current != NULL);
146   }
147 
148   // The distance is positive. It means we should bubble sort downward.
149   if (distance > 0) {
150     // downward
151     size_t rear;
152     do {
153       if (current->type == pTarget) {
154         break;
155       } else {
156         assert(!current->isLast() && "target category is wrong.");
157         rear = current->end - 1;
158         std::swap(m_OutputSymbols[pos], m_OutputSymbols[rear]);
159         pos = rear;
160         current->next->begin--;
161         current->end--;
162       }
163       current = current->next;
164     } while (current != NULL);
165 
166     return *this;
167   }  // downward
168 
169   // The distance is negative. It means we should bubble sort upward.
170   if (distance < 0) {
171     // upward
172     do {
173       if (current->type == pTarget) {
174         break;
175       } else {
176         assert(!current->isFirst() && "target category is wrong.");
177         std::swap(m_OutputSymbols[current->begin], m_OutputSymbols[pos]);
178         pos = current->begin;
179         current->begin++;
180         current->prev->end++;
181       }
182       current = current->prev;
183     } while (current != NULL);
184 
185     return *this;
186   }  // upward
187   return *this;
188 }
189 
arrange(LDSymbol & pSymbol,const ResolveInfo & pSourceInfo)190 SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol,
191                                         const ResolveInfo& pSourceInfo) {
192   assert(pSymbol.resolveInfo() != NULL);
193   return arrange(pSymbol,
194                  Category::categorize(pSourceInfo),
195                  Category::categorize(*pSymbol.resolveInfo()));
196 }
197 
changeCommonsToGlobal()198 SymbolCategory& SymbolCategory::changeCommonsToGlobal() {
199   // Change Common to Dynamic/Regular
200   while (!emptyCommons()) {
201     size_t pos = m_pCommon->end - 1;
202     switch (Category::categorize(*(m_OutputSymbols[pos]->resolveInfo()))) {
203       case Category::Dynamic:
204         m_pCommon->end--;
205         m_pDynamic->begin--;
206         break;
207       case Category::Regular:
208         std::swap(m_OutputSymbols[pos], m_OutputSymbols[m_pDynamic->end - 1]);
209         m_pCommon->end--;
210         m_pDynamic->begin--;
211         m_pDynamic->end--;
212         m_pRegular->begin--;
213         break;
214       default:
215         assert(0);
216         break;
217     }
218   }
219   return *this;
220 }
221 
changeToDynamic(LDSymbol & pSymbol)222 SymbolCategory& SymbolCategory::changeToDynamic(LDSymbol& pSymbol) {
223   assert(pSymbol.resolveInfo() != NULL);
224   return arrange(pSymbol,
225                  Category::categorize(*pSymbol.resolveInfo()),
226                  Category::LocalDyn);
227 }
228 
numOfSymbols() const229 size_t SymbolCategory::numOfSymbols() const {
230   return m_OutputSymbols.size();
231 }
232 
numOfFiles() const233 size_t SymbolCategory::numOfFiles() const {
234   return m_pFile->size();
235 }
236 
numOfLocals() const237 size_t SymbolCategory::numOfLocals() const {
238   return m_pLocal->size();
239 }
240 
numOfLocalDyns() const241 size_t SymbolCategory::numOfLocalDyns() const {
242   return m_pLocalDyn->size();
243 }
244 
numOfCommons() const245 size_t SymbolCategory::numOfCommons() const {
246   return m_pCommon->size();
247 }
248 
numOfDynamics() const249 size_t SymbolCategory::numOfDynamics() const {
250   return m_pDynamic->size();
251 }
252 
numOfRegulars() const253 size_t SymbolCategory::numOfRegulars() const {
254   return m_pRegular->size();
255 }
256 
empty() const257 bool SymbolCategory::empty() const {
258   return m_OutputSymbols.empty();
259 }
260 
emptyFiles() const261 bool SymbolCategory::emptyFiles() const {
262   return m_pFile->empty();
263 }
264 
emptyLocals() const265 bool SymbolCategory::emptyLocals() const {
266   return m_pLocal->empty();
267 }
268 
emptyLocalDyns() const269 bool SymbolCategory::emptyLocalDyns() const {
270   return m_pLocalDyn->empty();
271 }
272 
emptyCommons() const273 bool SymbolCategory::emptyCommons() const {
274   return m_pCommon->empty();
275 }
276 
emptyDynamics() const277 bool SymbolCategory::emptyDynamics() const {
278   return m_pDynamic->empty();
279 }
280 
emptyRegulars() const281 bool SymbolCategory::emptyRegulars() const {
282   return m_pRegular->empty();
283 }
284 
begin()285 SymbolCategory::iterator SymbolCategory::begin() {
286   return m_OutputSymbols.begin();
287 }
288 
end()289 SymbolCategory::iterator SymbolCategory::end() {
290   return m_OutputSymbols.end();
291 }
292 
begin() const293 SymbolCategory::const_iterator SymbolCategory::begin() const {
294   return m_OutputSymbols.begin();
295 }
296 
end() const297 SymbolCategory::const_iterator SymbolCategory::end() const {
298   return m_OutputSymbols.end();
299 }
300 
fileBegin()301 SymbolCategory::iterator SymbolCategory::fileBegin() {
302   return m_OutputSymbols.begin();
303 }
304 
fileEnd()305 SymbolCategory::iterator SymbolCategory::fileEnd() {
306   iterator iter = fileBegin();
307   iter += m_pFile->size();
308   return iter;
309 }
310 
fileBegin() const311 SymbolCategory::const_iterator SymbolCategory::fileBegin() const {
312   return m_OutputSymbols.begin();
313 }
314 
fileEnd() const315 SymbolCategory::const_iterator SymbolCategory::fileEnd() const {
316   const_iterator iter = fileBegin();
317   iter += m_pFile->size();
318   return iter;
319 }
320 
localBegin()321 SymbolCategory::iterator SymbolCategory::localBegin() {
322   return fileEnd();
323 }
324 
localEnd()325 SymbolCategory::iterator SymbolCategory::localEnd() {
326   iterator iter = localBegin();
327   iter += m_pLocal->size();
328   return iter;
329 }
330 
localBegin() const331 SymbolCategory::const_iterator SymbolCategory::localBegin() const {
332   return fileEnd();
333 }
334 
localEnd() const335 SymbolCategory::const_iterator SymbolCategory::localEnd() const {
336   const_iterator iter = localBegin();
337   iter += m_pLocal->size();
338   return iter;
339 }
340 
localDynBegin()341 SymbolCategory::iterator SymbolCategory::localDynBegin() {
342   return localEnd();
343 }
344 
localDynEnd()345 SymbolCategory::iterator SymbolCategory::localDynEnd() {
346   iterator iter = localDynBegin();
347   iter += m_pLocalDyn->size();
348   return iter;
349 }
350 
localDynBegin() const351 SymbolCategory::const_iterator SymbolCategory::localDynBegin() const {
352   return localEnd();
353 }
354 
localDynEnd() const355 SymbolCategory::const_iterator SymbolCategory::localDynEnd() const {
356   const_iterator iter = localDynBegin();
357   iter += m_pLocalDyn->size();
358   return iter;
359 }
360 
commonBegin()361 SymbolCategory::iterator SymbolCategory::commonBegin() {
362   return localDynEnd();
363 }
364 
commonEnd()365 SymbolCategory::iterator SymbolCategory::commonEnd() {
366   iterator iter = commonBegin();
367   iter += m_pCommon->size();
368   return iter;
369 }
370 
commonBegin() const371 SymbolCategory::const_iterator SymbolCategory::commonBegin() const {
372   return localDynEnd();
373 }
374 
commonEnd() const375 SymbolCategory::const_iterator SymbolCategory::commonEnd() const {
376   const_iterator iter = commonBegin();
377   iter += m_pCommon->size();
378   return iter;
379 }
380 
dynamicBegin()381 SymbolCategory::iterator SymbolCategory::dynamicBegin() {
382   return commonEnd();
383 }
384 
dynamicEnd()385 SymbolCategory::iterator SymbolCategory::dynamicEnd() {
386   iterator iter = dynamicBegin();
387   iter += m_pDynamic->size();
388   return iter;
389 }
390 
dynamicBegin() const391 SymbolCategory::const_iterator SymbolCategory::dynamicBegin() const {
392   return commonEnd();
393 }
394 
dynamicEnd() const395 SymbolCategory::const_iterator SymbolCategory::dynamicEnd() const {
396   const_iterator iter = dynamicBegin();
397   iter += m_pDynamic->size();
398   return iter;
399 }
400 
regularBegin()401 SymbolCategory::iterator SymbolCategory::regularBegin() {
402   return dynamicEnd();
403 }
404 
regularEnd()405 SymbolCategory::iterator SymbolCategory::regularEnd() {
406   return m_OutputSymbols.end();
407 }
408 
regularBegin() const409 SymbolCategory::const_iterator SymbolCategory::regularBegin() const {
410   return dynamicEnd();
411 }
412 
regularEnd() const413 SymbolCategory::const_iterator SymbolCategory::regularEnd() const {
414   return m_OutputSymbols.end();
415 }
416 
417 }  // namespace mcld
418