reorder.c 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631
  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. free(TaggedSections);
  433. return 1;
  434. }
  435. // Compute an estimation of the savings for placing each of the sections
  436. // next.
  437. for(; CurrentSection; CurrentSection = GetNext(CurrentSection))
  438. {
  439. COUNT Goodness;
  440. // Search in reverse order to avoid having to skip over all those old
  441. // startup sections each time.
  442. for (PCurrentSection = Sections + (RecursionDepth - 1);
  443. PCurrentSection >= Sections; PCurrentSection--)
  444. {
  445. if (*PCurrentSection == CurrentSection)
  446. goto AlreadyHandled;
  447. }
  448. Goodness = ComputeGoodness(Sections, RecursionDepth,
  449. CurrentSection);
  450. // IMPOSSIBLE means this section cannot be placed here, and
  451. // placing it later can only make things worse, so backtrack
  452. // immediately.
  453. if (Goodness == IMPOSSIBLE)
  454. {
  455. Warning(NULL, "Impossible section arrangement rejected at "
  456. "recursion depth %ld.", (long) RecursionDepth);
  457. free(TaggedSections);
  458. return 0;
  459. }
  460. if (CurrentSection->StartupNumber == StartupNumber)
  461. {
  462. CurrentTaggedSection->Section = CurrentSection;
  463. (CurrentTaggedSection++)->Goodness = Goodness;
  464. }
  465. AlreadyHandled:;
  466. }
  467. TaggedSectionCount = CurrentTaggedSection - TaggedSections;
  468. // Sort by decreasing estimated savings.
  469. qsort(TaggedSections, TaggedSectionCount, sizeof(TAGGEDSECTION),
  470. TaggedSectionComparisonFunction);
  471. // Try the best one first, then the second best and so on. Note that
  472. // backtracking is ONLY used when there are hardcoded sizes which are
  473. // not satisfied. Therefore, the easiest way to avoid using exponential
  474. // time is to not hardcode any short references. That's what linker
  475. // optimization is for!
  476. for (CurrentTaggedSection = TaggedSections;
  477. CurrentTaggedSection < TaggedSections + TaggedSectionCount;
  478. CurrentTaggedSection++)
  479. {
  480. SI1 Result;
  481. Sections[RecursionDepth] = CurrentTaggedSection->Section;
  482. Result = ReorderSectionsRecurse(Program, SectionCount, Sections,
  483. RecursionDepth + 1);
  484. if (Result) /* can be 1 or -1, in both cases we don't want to */
  485. { /* try the next section */
  486. free(TaggedSections);
  487. return Result;
  488. }
  489. }
  490. Warning(NULL, "Cannot find a valid section order at recursion depth "
  491. "%ld.", (long) RecursionDepth);
  492. }
  493. free(TaggedSections);
  494. return 0;
  495. }
  496. }
  497. // Find the first section that has not yet been handled.
  498. static SECTION *FindNextSection(PROGRAM *Program, SECTION **Sections,
  499. COUNT RecursionDepth)
  500. {
  501. SECTION *CurrentSection, **PCurrentSection;
  502. // Check for a section that hasn't been handled by reordering yet. There
  503. // should be at least one such section.
  504. for_each (CurrentSection, Program->Sections)
  505. {
  506. // Search in reverse order to avoid having to skip over all those old
  507. // startup sections each time.
  508. for (PCurrentSection = Sections + (RecursionDepth - 1);
  509. PCurrentSection >= Sections; PCurrentSection--)
  510. {
  511. if (*PCurrentSection == CurrentSection)
  512. goto AlreadyHandled;
  513. }
  514. return CurrentSection;
  515. AlreadyHandled:;
  516. }
  517. return NULL;
  518. }
  519. // Compute an estimation of the win obtained by putting this section next.
  520. // Returns IMPOSSIBLE if doing so would actually invalidate a reference. Note
  521. // that, due to the heuristic employed, placing this section even later can only
  522. // make things worse, so we can immediately return FALSE if this happens.
  523. // The estimates used are machine-specific. See M68kComputeRelocGoodness.
  524. static COUNT ComputeGoodness(SECTION **Sections, COUNT RecursionDepth,
  525. SECTION *CurrentSection)
  526. {
  527. SECTION *HandledSection, **PHandledSection;
  528. COUNT Goodness = 0;
  529. OFFSET ExtraOffset = 0;
  530. // If the current section is already handled, putting it in front will not
  531. // save us anything.
  532. if (CurrentSection->Handled)
  533. return PLACELAST;
  534. // For each handled section, in reverse order...
  535. for (PHandledSection = Sections + (RecursionDepth - 1);
  536. PHandledSection >= Sections; PHandledSection--)
  537. {
  538. RELOC *Reloc;
  539. HandledSection = *PHandledSection;
  540. // Look for references FROM the handled section TO the current section.
  541. for_each (Reloc, HandledSection->Relocs)
  542. {
  543. if (!Reloc->Relation && Reloc->Target.Symbol
  544. && Reloc->Target.Symbol->Parent == CurrentSection)
  545. {
  546. OFFSET Offset = Reloc->Target.Symbol->Location
  547. + Reloc->Target.Offset
  548. + (HandledSection->Size - Reloc->Location)
  549. + ExtraOffset + Reloc->FixedOffset;
  550. if (Reloc->Size == 2 && (Offset > 32767 || Offset < -32768))
  551. return IMPOSSIBLE;
  552. else if (Reloc->Size == 1 && (Offset > 127 || Offset < -128))
  553. return IMPOSSIBLE;
  554. Goodness += M68kComputeRelocGoodness(Offset, Reloc);
  555. }
  556. }
  557. // Look for references TO the handled section FROM the current section.
  558. for_each (Reloc, CurrentSection->Relocs)
  559. {
  560. if (!Reloc->Relation && Reloc->Target.Symbol
  561. && Reloc->Target.Symbol->Parent == HandledSection)
  562. {
  563. OFFSET Offset = - Reloc->Location
  564. - (HandledSection->Size
  565. - (Reloc->Target.Symbol->Location
  566. + Reloc->Target.Offset))
  567. - ExtraOffset + Reloc->FixedOffset;
  568. if (Reloc->Size == 2 && (Offset > 32767 || Offset < -32768))
  569. return IMPOSSIBLE;
  570. else if (Reloc->Size == 1 && (Offset > 127 || Offset < -128))
  571. return IMPOSSIBLE;
  572. Goodness += M68kComputeRelocGoodness(Offset, Reloc);
  573. }
  574. }
  575. // Add the size of the handled section to the offset to account for.
  576. ExtraOffset += HandledSection->Size;
  577. }
  578. return Goodness;
  579. }
  580. // Comparison function for qsort.
  581. static int TaggedSectionComparisonFunction(const void *TaggedSection1,
  582. const void *TaggedSection2)
  583. {
  584. if (((const TAGGEDSECTION *)TaggedSection1)->Goodness
  585. > ((const TAGGEDSECTION *)TaggedSection2)->Goodness)
  586. return -1;
  587. else if (((const TAGGEDSECTION *)TaggedSection1)->Goodness
  588. < ((const TAGGEDSECTION *)TaggedSection2)->Goodness)
  589. return 1;
  590. else
  591. return 0;
  592. }