reorder.c 22 KB

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