reorder.c 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629
  1. /* reorder.c: Routines to reorder sections
  2. Copyright (C) 2004-2005 Kevin Kofler
  3. Copyright (C) 2004 Sebastian Reichelt
  4. This program is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU General Public License as published by
  6. the Free Software Foundation; either version 2, or (at your option)
  7. any later version.
  8. This program is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11. GNU General Public License for more details.
  12. You should have received a copy of the GNU General Public License
  13. along with this program; if not, write to the Free Software Foundation,
  14. Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  15. #include "reorder.h"
  16. #include "data.h"
  17. #include "manip.h"
  18. #include "bincode/fix_m68k.h" // We need this to estimate the possible gains.
  19. #include "bincode/m68k.h"
  20. #include <stdlib.h>
  21. // MAIN ENTRY POINT:
  22. static void ReorderNonStartupSections (PROGRAM *Program);
  23. static void ReorderStartupSections (PROGRAM *Program);
  24. // Reorder the sections to make references as short as possible. Uses heuristics
  25. // to avoid combinatorial explosion.
  26. void ReorderSections (PROGRAM *Program)
  27. {
  28. ReorderStartupSections(Program);
  29. ReorderNonStartupSections(Program);
  30. }
  31. // REORDERING ROUTINES USING GLOBAL HEURISTICS (Sebastian Reichelt):
  32. // The following functions handle section reordering using global heuristics.
  33. // They are used to reorder non-startup sections.
  34. // Maximum length of the search for related sections.
  35. #define MAX_RELATED_SEARCH_LENGTH 100
  36. // Maximum size of intentional unbalancing.
  37. #define MAX_UNBALANCED_SIZE 4096
  38. // Comparison function for qsort.
  39. static int SectionComparisonFunction (const void *Section1Ptr, const void *Section2Ptr)
  40. {
  41. const SECTION *Section1 = *((SECTION **) Section1Ptr), *Section2 = *((SECTION **) Section2Ptr);
  42. return (Section2->Relocs.OptRefCount * Section1->Size - Section1->Relocs.OptRefCount * Section2->Size);
  43. }
  44. static COUNT GetRelocCountFromTo (const SECTION *Src, const SECTION *Dest)
  45. {
  46. COUNT Result = 0;
  47. RELOC *Reloc;
  48. for_each (Reloc, Src->Relocs)
  49. {
  50. SYMBOL *TargetSymbol = Reloc->Target.Symbol;
  51. if (TargetSymbol && TargetSymbol->Parent == Dest && M68kIsRelocOptimizable (Reloc))
  52. Result++;
  53. }
  54. return Result;
  55. }
  56. static COUNT GetRelocCountBetween (const SECTION *Section1, const SECTION *Section2)
  57. {
  58. return (GetRelocCountFromTo (Section1, Section2) + GetRelocCountFromTo (Section2, Section1));
  59. }
  60. static BOOLEAN AreSectionsRelated (const SECTION *Section1, const SECTION *Section2)
  61. {
  62. if (Section1 && Section2)
  63. {
  64. COUNT Relationship = M68kGetSectionRelationship (Section1, Section2);
  65. return (Relationship > Section1->Size || Relationship > Section2->Size);
  66. }
  67. return FALSE;
  68. }
  69. static BOOLEAN CanMoveSection (const SECTION *Section)
  70. {
  71. return (!(AreSectionsRelated (GetPrev (Section), Section) || AreSectionsRelated (Section, GetNext (Section))));
  72. }
  73. static BOOLEAN CanMoveSectionToFront (const SECTION *Section, const SECTION *Dest)
  74. {
  75. if (!(CanMoveSection (Section)))
  76. return FALSE;
  77. else
  78. {
  79. SECTION *CheckSection;
  80. SIZE TotalSize = Section->Size;
  81. for (CheckSection = (Dest ? GetNext (Dest) : GetFirst (Section->Parent->Sections)); CheckSection; CheckSection = GetNext (CheckSection))
  82. {
  83. TotalSize += CheckSection->Size;
  84. if (TotalSize > M68K_REL_MAX && GetRelocCountBetween (Section, CheckSection) > 0)
  85. return FALSE;
  86. }
  87. return TRUE;
  88. }
  89. }
  90. static BOOLEAN CanMoveSectionToBack (const SECTION *Section, const SECTION *Dest)
  91. {
  92. if (!(CanMoveSection (Section)))
  93. return FALSE;
  94. else
  95. {
  96. SECTION *CheckSection;
  97. SIZE TotalSize = Section->Size;
  98. for (CheckSection = (Dest ? GetPrev (Dest) : GetLast (Section->Parent->Sections)); CheckSection; CheckSection = GetPrev (CheckSection))
  99. {
  100. TotalSize += CheckSection->Size;
  101. if (TotalSize > M68K_REL_MAX && GetRelocCountBetween (Section, CheckSection) > 0)
  102. return FALSE;
  103. }
  104. return TRUE;
  105. }
  106. }
  107. // Reorder non-startup sections to make references as short as possible. Uses
  108. // global heuristics to avoid combinatorial explosion.
  109. static void ReorderNonStartupSections (PROGRAM *Program)
  110. {
  111. SECTION **Sections = calloc (CountItems (Program->Sections, SECTION), sizeof (SECTION *));
  112. if (!Sections)
  113. {
  114. Warning (NULL, "Out of memory reordering sections.");
  115. return;
  116. }
  117. {
  118. COUNT SectionCount = 0;
  119. SECTION *InsertPos = NULL;
  120. // Build an array of all sections, and unlink those sections from the
  121. // section list.
  122. SECTION *Section = GetFirst (Program->Sections), *NextSection;
  123. if (Section && Program->Type == PT_NOSTUB)
  124. Section = GetNext (Section);
  125. for (; Section; Section = NextSection)
  126. {
  127. NextSection = GetNext (Section);
  128. if (!(Section->StartupNumber))
  129. {
  130. if (Section->Handled)
  131. {
  132. // The first handled section is a good place to insert the sorted sections.
  133. if (!InsertPos)
  134. InsertPos = Section;
  135. }
  136. else
  137. {
  138. Sections[SectionCount++] = Section;
  139. Unlink (Program->Sections, Section);
  140. }
  141. }
  142. }
  143. // Sort this array according to the number of references.
  144. qsort (Sections, SectionCount, sizeof (SECTION *), SectionComparisonFunction);
  145. // Insert the sections in a new order, putting heavily referenced sections
  146. // in the middle of the program.
  147. // The reason this works best is actually very specific to M68k and TIOS.
  148. {
  149. SECTION *FirstPos = (InsertPos ? GetPrev (InsertPos) : GetLast (Program->Sections)), *SecondPos = InsertPos;
  150. SIZE FirstSize = 0, SecondSize = 0;
  151. OFFSET CurSectionIdx;
  152. for (CurSectionIdx = 0; CurSectionIdx < SectionCount; CurSectionIdx++)
  153. {
  154. SECTION *Section = Sections[CurSectionIdx];
  155. if (Section)
  156. {
  157. BOOLEAN InsertAtSecondPos = FALSE;
  158. if (!(Section->Relocs.RelativeRefs))
  159. {
  160. if (!(Section->Relocs.StartupRefs))
  161. InsertAtSecondPos = SecondSize < FirstSize;
  162. if (SecondSize - FirstSize <= MAX_UNBALANCED_SIZE && FirstSize - SecondSize <= MAX_UNBALANCED_SIZE)
  163. {
  164. // Try to find out which of the two sides is actually better,
  165. // i.e. which causes fewer absolute relocs.
  166. COUNT FirstRelocCount = 0, SecondRelocCount = 0;
  167. BOOLEAN FirstTrouble = FALSE, SecondTrouble = FALSE;
  168. SIZE TotalSize = FirstSize + SecondSize + Section->Size;
  169. SIZE SizeLeft = TotalSize;
  170. SECTION *CheckSection;
  171. for (CheckSection = (FirstPos ? GetNext (FirstPos) : GetFirst (Program->Sections)); CheckSection && CheckSection != SecondPos && SizeLeft > M68K_REL_MAX; CheckSection = GetNext (CheckSection))
  172. {
  173. COUNT RelocCount = GetRelocCountBetween (Section, CheckSection);
  174. if (RelocCount > 0)
  175. {
  176. FirstTrouble = TRUE;
  177. if (!(SecondSize - FirstSize + 2 * CheckSection->Size <= MAX_UNBALANCED_SIZE && CanMoveSectionToBack (CheckSection, SecondPos)))
  178. FirstRelocCount += RelocCount;
  179. }
  180. SizeLeft -= CheckSection->Size;
  181. }
  182. SizeLeft = TotalSize;
  183. for (CheckSection = (SecondPos ? GetPrev (SecondPos) : GetLast (Program->Sections)); CheckSection && CheckSection != FirstPos && SizeLeft > M68K_REL_MAX; CheckSection = GetPrev (CheckSection))
  184. {
  185. COUNT RelocCount = GetRelocCountBetween (Section, CheckSection);
  186. if (RelocCount > 0)
  187. {
  188. SecondTrouble = TRUE;
  189. if (!(FirstSize - SecondSize + 2 * CheckSection->Size <= MAX_UNBALANCED_SIZE && CanMoveSectionToFront (CheckSection, FirstPos)))
  190. SecondRelocCount += RelocCount;
  191. }
  192. SizeLeft -= CheckSection->Size;
  193. }
  194. if (FirstRelocCount != SecondRelocCount)
  195. InsertAtSecondPos = SecondRelocCount > FirstRelocCount;
  196. else if (FirstTrouble && (!SecondTrouble))
  197. InsertAtSecondPos = FALSE;
  198. else if (SecondTrouble && (!FirstTrouble))
  199. InsertAtSecondPos = TRUE;
  200. }
  201. }
  202. {
  203. OFFSET RelatedSectionIdx = CurSectionIdx + 1;
  204. OFFSET RelatedSectionSearchEnd = CurSectionIdx + MAX_RELATED_SEARCH_LENGTH;
  205. if (RelatedSectionSearchEnd > SectionCount)
  206. RelatedSectionSearchEnd = SectionCount;
  207. do {
  208. // Insert the section.
  209. if (InsertAtSecondPos)
  210. {
  211. SIZE OriginalDifference = SecondSize - FirstSize;
  212. InsertBefore (Program->Sections, Section, SecondPos);
  213. SecondSize += Section->Size;
  214. if (OriginalDifference <= MAX_UNBALANCED_SIZE)
  215. {
  216. SIZE SizeLeft = FirstSize + SecondSize;
  217. SECTION *CheckSection, *NextSection;
  218. for (CheckSection = (FirstPos ? GetNext (FirstPos) : GetFirst (Program->Sections)); CheckSection && CheckSection != SecondPos && SizeLeft > M68K_REL_MAX; CheckSection = NextSection)
  219. {
  220. NextSection = GetNext (CheckSection);
  221. if (GetRelocCountBetween (Section, CheckSection) > 0 && OriginalDifference + 2 * CheckSection->Size <= MAX_UNBALANCED_SIZE && CanMoveSectionToBack (CheckSection, SecondPos))
  222. {
  223. Unlink (Program->Sections, CheckSection);
  224. InsertBefore (Program->Sections, CheckSection, SecondPos);
  225. SecondSize += CheckSection->Size;
  226. FirstSize -= CheckSection->Size;
  227. }
  228. SizeLeft -= CheckSection->Size;
  229. }
  230. }
  231. }
  232. else
  233. {
  234. SIZE OriginalDifference = FirstSize - SecondSize;
  235. InsertAfter (Program->Sections, Section, FirstPos);
  236. FirstSize += Section->Size;
  237. if (OriginalDifference <= MAX_UNBALANCED_SIZE)
  238. {
  239. SIZE SizeLeft = FirstSize + SecondSize;
  240. SECTION *CheckSection, *NextSection;
  241. for (CheckSection = (SecondPos ? GetPrev (SecondPos) : GetLast (Program->Sections)); CheckSection && CheckSection != FirstPos && SizeLeft > M68K_REL_MAX; CheckSection = NextSection)
  242. {
  243. NextSection = GetPrev (CheckSection);
  244. if (GetRelocCountBetween (Section, CheckSection) > 0 && OriginalDifference + 2 * CheckSection->Size <= MAX_UNBALANCED_SIZE && CanMoveSectionToFront (CheckSection, FirstPos))
  245. {
  246. Unlink (Program->Sections, CheckSection);
  247. InsertAfter (Program->Sections, CheckSection, FirstPos);
  248. FirstSize += CheckSection->Size;
  249. SecondSize -= CheckSection->Size;
  250. }
  251. SizeLeft -= CheckSection->Size;
  252. }
  253. }
  254. }
  255. {
  256. SECTION *RelatedSection = NULL;
  257. // Look for a closely related section, which should be put right
  258. // next to this one.
  259. for (; RelatedSectionIdx < RelatedSectionSearchEnd && (!RelatedSection); RelatedSectionIdx++)
  260. {
  261. SECTION *SearchSection = Sections[RelatedSectionIdx];
  262. if (SearchSection)
  263. {
  264. COUNT Relationship;
  265. if (InsertAtSecondPos)
  266. Relationship = M68kGetSectionRelationship (Section, SearchSection);
  267. else
  268. Relationship = M68kGetSectionRelationship (SearchSection, Section);
  269. if (Relationship > SearchSection->Size)
  270. {
  271. RelatedSection = SearchSection;
  272. Sections[RelatedSectionIdx] = NULL;
  273. }
  274. }
  275. }
  276. Section = RelatedSection;
  277. }
  278. } while (Section);
  279. }
  280. }
  281. }
  282. // Look at the effect of putting sections referenced by startup sections
  283. // at the beginning. If it doesn't seem to have any negative effect, then
  284. // do it.
  285. {
  286. if (FirstPos)
  287. InsertPos = GetNext (FirstPos);
  288. else
  289. InsertPos = GetFirst (Program->Sections);
  290. {
  291. SECTION *FirstProblem;
  292. SIZE ProblemSize = 0;
  293. for (FirstProblem = InsertPos; FirstProblem && ProblemSize <= M68K_REL_MAX; FirstProblem = GetNext (FirstProblem))
  294. ProblemSize += FirstProblem->Size;
  295. {
  296. SECTION *Section, *NextSection;
  297. for (Section = InsertPos; Section && Section != SecondPos; Section = NextSection)
  298. {
  299. NextSection = GetNext (Section);
  300. if (Section->Relocs.StartupRefs && CanMoveSection (Section))
  301. {
  302. BOOLEAN CanMove = TRUE;
  303. SECTION *CheckSection;
  304. for (CheckSection = FirstProblem; CheckSection && CheckSection != SecondPos; CheckSection = GetNext (CheckSection))
  305. {
  306. if (GetRelocCountBetween (Section, CheckSection) > 0)
  307. {
  308. CanMove = FALSE;
  309. break;
  310. }
  311. }
  312. if (CanMove)
  313. {
  314. Unlink (Program->Sections, Section);
  315. InsertAfter (Program->Sections, Section, FirstPos);
  316. }
  317. }
  318. }
  319. }
  320. }
  321. }
  322. }
  323. }
  324. free (Sections);
  325. }
  326. // REORDERING ROUTINES USING LOCAL HEURISTICS (Kevin Kofler):
  327. // The following functions handle reordering of startup sections which share one
  328. // and the same startup number and can thus be arbitrarily reordered. The
  329. // current implementation is based on my (Kevin Kofler's) original section
  330. // reordering algorithm.
  331. // Reorder the sections to make references as short as possible. Backtrack when
  332. // a solution is impossible (due to hard-coded short references). Returns 1 on
  333. // success, 0 on failure, -1 on memory overflow.
  334. static SI1 ReorderSectionsRecurse(PROGRAM *Program, COUNT SectionCount,
  335. SECTION **Sections, COUNT RecursionDepth);
  336. // Find the first section that has not yet been handled.
  337. static SECTION *FindNextSection(PROGRAM *Program, SECTION **Sections,
  338. COUNT RecursionDepth);
  339. // Compute an estimation of the win obtained by putting this section next.
  340. // Returns IMPOSSIBLE if doing so would actually invalidate a reference. Note
  341. // that, due to the heuristic employed, placing this section even later can only
  342. // make things worse, so we can immediately return FALSE if this happens.
  343. static COUNT ComputeGoodness(SECTION **Sections, COUNT RecursionDepth,
  344. SECTION *CurrentSection);
  345. #define PLACELAST ((COUNT)-1)
  346. #define IMPOSSIBLE ((COUNT)-2)
  347. // Comparison function for qsort.
  348. static int TaggedSectionComparisonFunction(const void *TaggedSection1,
  349. const void *TaggedSection2);
  350. // Reorder startup sections to make references as short as possible. Uses
  351. // local heuristics to avoid combinatorial explosion.
  352. static void ReorderStartupSections(PROGRAM *Program)
  353. {
  354. SI1 Result;
  355. COUNT RecursionDepth = 0;
  356. COUNT SectionCount = CountItems(Program->Sections,SECTION);
  357. SECTION **Sections = malloc(SectionCount * sizeof(SECTION *));
  358. if (!Sections)
  359. {
  360. Warning(NULL, "Out of memory reordering sections.");
  361. return;
  362. }
  363. if (Program->Type == PT_NOSTUB)
  364. {
  365. *Sections = GetFirst(Program->Sections);
  366. RecursionDepth++;
  367. }
  368. Result = ReorderSectionsRecurse(Program, SectionCount, Sections, RecursionDepth);
  369. if (Result > 0)
  370. {
  371. // Reorder our linked list of sections:
  372. SECTION *Section, *NextSection;
  373. COUNT i;
  374. // First unlink them all.
  375. for (Section = GetFirst(Program->Sections); Section; Section = NextSection)
  376. {
  377. NextSection = GetNext (Section);
  378. Unlink(Program->Sections, Section);
  379. }
  380. // Then append them in the order given by the array.
  381. for (i = 0; i < SectionCount; i++)
  382. Append(Program->Sections, Sections[i]);
  383. }
  384. else if (!Result)
  385. {
  386. Warning(NULL, "Section reordering failed.");
  387. }
  388. free(Sections);
  389. }
  390. typedef struct {
  391. SECTION *Section;
  392. COUNT Goodness;
  393. } TAGGEDSECTION;
  394. // Reorder the sections to make references as short as possible. Backtrack when
  395. // a solution is impossible (due to hard-coded short references). Returns 1 on
  396. // success, 0 on failure, -1 on memory overflow.
  397. static SI1 ReorderSectionsRecurse(PROGRAM *Program, COUNT SectionCount,
  398. SECTION **Sections, COUNT RecursionDepth)
  399. {
  400. // If there are no more sections to reorder, return immediately.
  401. if (RecursionDepth == SectionCount)
  402. return 1;
  403. else
  404. {
  405. TAGGEDSECTION *TaggedSections = malloc(SectionCount
  406. * sizeof(TAGGEDSECTION)),
  407. *CurrentTaggedSection = TaggedSections;
  408. SECTION *CurrentSection;
  409. if (!TaggedSections)
  410. {
  411. Warning(NULL, "Out of memory reordering sections.");
  412. return -1;
  413. }
  414. CurrentSection = FindNextSection(Program, Sections, RecursionDepth);
  415. if (CurrentSection)
  416. {
  417. SECTION **PCurrentSection;
  418. OFFSET StartupNumber = CurrentSection->StartupNumber;
  419. COUNT TaggedSectionCount;
  420. // If the current section is not a startup section, it means we are
  421. // done with the startup sections. So just add all the remaining
  422. // sections in their current order, to be rearranged by global
  423. // reordering.
  424. if (!StartupNumber)
  425. {
  426. SECTION *RemainingSection;
  427. for (RemainingSection = CurrentSection; RemainingSection;
  428. RemainingSection = GetNext (RemainingSection))
  429. {
  430. Sections[RecursionDepth++] = RemainingSection;
  431. }
  432. return 1;
  433. }
  434. // Compute an estimation of the savings for placing each of the sections
  435. // next.
  436. for(; CurrentSection; CurrentSection = GetNext(CurrentSection))
  437. {
  438. COUNT Goodness;
  439. // Search in reverse order to avoid having to skip over all those old
  440. // startup sections each time.
  441. for (PCurrentSection = Sections + (RecursionDepth - 1);
  442. PCurrentSection >= Sections; PCurrentSection--)
  443. {
  444. if (*PCurrentSection == CurrentSection)
  445. goto AlreadyHandled;
  446. }
  447. Goodness = ComputeGoodness(Sections, RecursionDepth,
  448. CurrentSection);
  449. // IMPOSSIBLE means this section cannot be placed here, and
  450. // placing it later can only make things worse, so backtrack
  451. // immediately.
  452. if (Goodness == IMPOSSIBLE)
  453. {
  454. Warning(NULL, "Impossible section arrangement rejected at "
  455. "recursion depth %ld.", (long) RecursionDepth);
  456. return 0;
  457. }
  458. if (CurrentSection->StartupNumber == StartupNumber)
  459. {
  460. CurrentTaggedSection->Section = CurrentSection;
  461. (CurrentTaggedSection++)->Goodness = Goodness;
  462. }
  463. AlreadyHandled:;
  464. }
  465. TaggedSectionCount = CurrentTaggedSection - TaggedSections;
  466. // Sort by decreasing estimated savings.
  467. qsort(TaggedSections, TaggedSectionCount, sizeof(TAGGEDSECTION),
  468. TaggedSectionComparisonFunction);
  469. // Try the best one first, then the second best and so on. Note that
  470. // backtracking is ONLY used when there are hardcoded sizes which are
  471. // not satisfied. Therefore, the easiest way to avoid using exponential
  472. // time is to not hardcode any short references. That's what linker
  473. // optimization is for!
  474. for (CurrentTaggedSection = TaggedSections;
  475. CurrentTaggedSection < TaggedSections + TaggedSectionCount;
  476. CurrentTaggedSection++)
  477. {
  478. SI1 Result;
  479. Sections[RecursionDepth] = CurrentTaggedSection->Section;
  480. Result = ReorderSectionsRecurse(Program, SectionCount, Sections,
  481. RecursionDepth + 1);
  482. if (Result) /* can be 1 or -1, in both cases we don't want to */
  483. { /* try the next section */
  484. free(TaggedSections);
  485. return Result;
  486. }
  487. }
  488. Warning(NULL, "Cannot find a valid section order at recursion depth "
  489. "%ld.", (long) RecursionDepth);
  490. }
  491. free(TaggedSections);
  492. return 0;
  493. }
  494. }
  495. // Find the first section that has not yet been handled.
  496. static SECTION *FindNextSection(PROGRAM *Program, SECTION **Sections,
  497. COUNT RecursionDepth)
  498. {
  499. SECTION *CurrentSection, **PCurrentSection;
  500. // Check for a section that hasn't been handled by reordering yet. There
  501. // should be at least one such section.
  502. for_each (CurrentSection, Program->Sections)
  503. {
  504. // Search in reverse order to avoid having to skip over all those old
  505. // startup sections each time.
  506. for (PCurrentSection = Sections + (RecursionDepth - 1);
  507. PCurrentSection >= Sections; PCurrentSection--)
  508. {
  509. if (*PCurrentSection == CurrentSection)
  510. goto AlreadyHandled;
  511. }
  512. return CurrentSection;
  513. AlreadyHandled:;
  514. }
  515. return NULL;
  516. }
  517. // Compute an estimation of the win obtained by putting this section next.
  518. // Returns IMPOSSIBLE if doing so would actually invalidate a reference. Note
  519. // that, due to the heuristic employed, placing this section even later can only
  520. // make things worse, so we can immediately return FALSE if this happens.
  521. // The estimates used are machine-specific. See M68kComputeRelocGoodness.
  522. static COUNT ComputeGoodness(SECTION **Sections, COUNT RecursionDepth,
  523. SECTION *CurrentSection)
  524. {
  525. SECTION *HandledSection, **PHandledSection;
  526. COUNT Goodness = 0;
  527. OFFSET ExtraOffset = 0;
  528. // If the current section is already handled, putting it in front will not
  529. // save us anything.
  530. if (CurrentSection->Handled)
  531. return PLACELAST;
  532. // For each handled section, in reverse order...
  533. for (PHandledSection = Sections + (RecursionDepth - 1);
  534. PHandledSection >= Sections; PHandledSection--)
  535. {
  536. RELOC *Reloc;
  537. HandledSection = *PHandledSection;
  538. // Look for references FROM the handled section TO the current section.
  539. for_each (Reloc, HandledSection->Relocs)
  540. {
  541. if (!Reloc->Relation && Reloc->Target.Symbol
  542. && Reloc->Target.Symbol->Parent == CurrentSection)
  543. {
  544. OFFSET Offset = Reloc->Target.Symbol->Location
  545. + Reloc->Target.Offset
  546. + (HandledSection->Size - Reloc->Location)
  547. + ExtraOffset + Reloc->FixedOffset;
  548. if (Reloc->Size == 2 && (Offset > 32767 || Offset < -32768))
  549. return IMPOSSIBLE;
  550. else if (Reloc->Size == 1 && (Offset > 127 || Offset < -128))
  551. return IMPOSSIBLE;
  552. Goodness += M68kComputeRelocGoodness(Offset, Reloc);
  553. }
  554. }
  555. // Look for references TO the handled section FROM the current section.
  556. for_each (Reloc, CurrentSection->Relocs)
  557. {
  558. if (!Reloc->Relation && Reloc->Target.Symbol
  559. && Reloc->Target.Symbol->Parent == HandledSection)
  560. {
  561. OFFSET Offset = - Reloc->Location
  562. - (HandledSection->Size
  563. - (Reloc->Target.Symbol->Location
  564. + Reloc->Target.Offset))
  565. - ExtraOffset + Reloc->FixedOffset;
  566. if (Reloc->Size == 2 && (Offset > 32767 || Offset < -32768))
  567. return IMPOSSIBLE;
  568. else if (Reloc->Size == 1 && (Offset > 127 || Offset < -128))
  569. return IMPOSSIBLE;
  570. Goodness += M68kComputeRelocGoodness(Offset, Reloc);
  571. }
  572. }
  573. // Add the size of the handled section to the offset to account for.
  574. ExtraOffset += HandledSection->Size;
  575. }
  576. return Goodness;
  577. }
  578. // Comparison function for qsort.
  579. static int TaggedSectionComparisonFunction(const void *TaggedSection1,
  580. const void *TaggedSection2)
  581. {
  582. if (((const TAGGEDSECTION *)TaggedSection1)->Goodness
  583. > ((const TAGGEDSECTION *)TaggedSection2)->Goodness)
  584. return -1;
  585. else if (((const TAGGEDSECTION *)TaggedSection1)->Goodness
  586. < ((const TAGGEDSECTION *)TaggedSection2)->Goodness)
  587. return 1;
  588. else
  589. return 0;
  590. }