reorder.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333
  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. }