123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333 |
- /* reorder.c: Routines to reorder sections
- Copyright (C) 2004 Sebastian Reichelt
- (original version was written by Kevin Kofler)
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2, or (at your option)
- any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software Foundation,
- Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
- #include "reorder.h"
- #include "data.h"
- #include "manip.h"
- #include "bincode/fix_m68k.h" // We need this to estimate the possible gains.
- #include "bincode/m68k.h"
- #include <stdlib.h>
- // Maximum length of the search for related sections.
- #define MAX_RELATED_SEARCH_LENGTH 100
- // Maximum size of intentional unbalancing.
- #define MAX_UNBALANCED_SIZE 4096
- // Comparison function for qsort.
- static int SectionComparisonFunction (const void *Section1Ptr, const void *Section2Ptr)
- {
- const SECTION *Section1 = *((SECTION **) Section1Ptr), *Section2 = *((SECTION **) Section2Ptr);
- return (Section2->Relocs.OptRefCount * Section1->Size - Section1->Relocs.OptRefCount * Section2->Size);
- }
- COUNT GetRelocCountFromTo (const SECTION *Src, const SECTION *Dest)
- {
- COUNT Result = 0;
- RELOC *Reloc;
- for_each (Reloc, Src->Relocs)
- {
- SYMBOL *TargetSymbol = Reloc->Target.Symbol;
- if (TargetSymbol && TargetSymbol->Parent == Dest && M68kIsRelocOptimizable (Reloc))
- Result++;
- }
- return Result;
- }
- COUNT GetRelocCountBetween (const SECTION *Section1, const SECTION *Section2)
- {
- return (GetRelocCountFromTo (Section1, Section2) + GetRelocCountFromTo (Section2, Section1));
- }
- BOOLEAN AreSectionsRelated (const SECTION *Section1, const SECTION *Section2)
- {
- if (Section1 && Section2)
- {
- COUNT Relationship = M68kGetSectionRelationship (Section1, Section2);
- return (Relationship > Section1->Size || Relationship > Section2->Size);
- }
- return FALSE;
- }
- BOOLEAN CanMoveSection (const SECTION *Section)
- {
- return (!(AreSectionsRelated (GetPrev (Section), Section) || AreSectionsRelated (Section, GetNext (Section))));
- }
- BOOLEAN CanMoveSectionToFront (const SECTION *Section, const SECTION *Dest)
- {
- if (!(CanMoveSection (Section)))
- return FALSE;
- else
- {
- SECTION *CheckSection;
- SIZE TotalSize = Section->Size;
- for (CheckSection = (Dest ? GetNext (Dest) : GetFirst (Section->Parent->Sections)); CheckSection; CheckSection = GetNext (CheckSection))
- {
- TotalSize += CheckSection->Size;
- if (TotalSize > M68K_REL_MAX && GetRelocCountBetween (Section, CheckSection) > 0)
- return FALSE;
- }
- return TRUE;
- }
- }
- BOOLEAN CanMoveSectionToBack (const SECTION *Section, const SECTION *Dest)
- {
- if (!(CanMoveSection (Section)))
- return FALSE;
- else
- {
- SECTION *CheckSection;
- SIZE TotalSize = Section->Size;
- for (CheckSection = (Dest ? GetPrev (Dest) : GetLast (Section->Parent->Sections)); CheckSection; CheckSection = GetPrev (CheckSection))
- {
- TotalSize += CheckSection->Size;
- if (TotalSize > M68K_REL_MAX && GetRelocCountBetween (Section, CheckSection) > 0)
- return FALSE;
- }
- return TRUE;
- }
- }
- // Reorder the sections to make references as short as possible. Uses heuristics
- // to avoid combinatorial explosion.
- void ReorderSections (PROGRAM *Program)
- {
- SECTION **Sections = calloc (CountItems (Program->Sections, SECTION), sizeof (SECTION *));
- if (!Sections)
- {
- Warning (NULL, "Out of memory reordering sections.");
- return;
- }
- {
- COUNT SectionCount = 0;
- SECTION *InsertPos = NULL;
-
- // Build an array of all sections, and unlink those sections from the
- // section list.
- SECTION *Section = GetFirst (Program->Sections), *NextSection;
- if (Section && Program->Type == PT_NOSTUB)
- Section = GetNext (Section);
- for (; Section; Section = NextSection)
- {
- NextSection = GetNext (Section);
- if (!(Section->StartupNumber))
- {
- if (Section->Handled)
- {
- // The first handled section is a good place to insert the sorted sections.
- if (!InsertPos)
- InsertPos = Section;
- }
- else
- {
- Sections[SectionCount++] = Section;
- Unlink (Program->Sections, Section);
- }
- }
- }
-
- // Sort this array according to the number of references.
- qsort (Sections, SectionCount, sizeof (SECTION *), SectionComparisonFunction);
-
- // Insert the sections in a new order, putting heavily referenced sections
- // in the middle of the program.
- // The reason this works best is actually very specific to M68k and TIOS.
- {
- SECTION *FirstPos = (InsertPos ? GetPrev (InsertPos) : GetLast (Program->Sections)), *SecondPos = InsertPos;
- SIZE FirstSize = 0, SecondSize = 0;
- OFFSET CurSectionIdx;
- for (CurSectionIdx = 0; CurSectionIdx < SectionCount; CurSectionIdx++)
- {
- SECTION *Section = Sections[CurSectionIdx];
- if (Section)
- {
- BOOLEAN InsertAtSecondPos = FALSE;
- if (!(Section->Relocs.RelativeRefs))
- {
- if (!(Section->Relocs.StartupRefs))
- InsertAtSecondPos = SecondSize < FirstSize;
- if (SecondSize - FirstSize <= MAX_UNBALANCED_SIZE && FirstSize - SecondSize <= MAX_UNBALANCED_SIZE)
- {
- // Try to find out which of the two sides is actually better,
- // i.e. which causes fewer absolute relocs.
- COUNT FirstRelocCount = 0, SecondRelocCount = 0;
- BOOLEAN FirstTrouble = FALSE, SecondTrouble = FALSE;
- SIZE TotalSize = FirstSize + SecondSize + Section->Size;
- SIZE SizeLeft = TotalSize;
- SECTION *CheckSection;
- for (CheckSection = (FirstPos ? GetNext (FirstPos) : GetFirst (Program->Sections)); CheckSection && CheckSection != SecondPos && SizeLeft > M68K_REL_MAX; CheckSection = GetNext (CheckSection))
- {
- COUNT RelocCount = GetRelocCountBetween (Section, CheckSection);
- if (RelocCount > 0)
- {
- FirstTrouble = TRUE;
- if (!(SecondSize - FirstSize + 2 * CheckSection->Size <= MAX_UNBALANCED_SIZE && CanMoveSectionToBack (CheckSection, SecondPos)))
- FirstRelocCount += RelocCount;
- }
- SizeLeft -= CheckSection->Size;
- }
- SizeLeft = TotalSize;
- for (CheckSection = (SecondPos ? GetPrev (SecondPos) : GetLast (Program->Sections)); CheckSection && CheckSection != FirstPos && SizeLeft > M68K_REL_MAX; CheckSection = GetPrev (CheckSection))
- {
- COUNT RelocCount = GetRelocCountBetween (Section, CheckSection);
- if (RelocCount > 0)
- {
- SecondTrouble = TRUE;
- if (!(FirstSize - SecondSize + 2 * CheckSection->Size <= MAX_UNBALANCED_SIZE && CanMoveSectionToFront (CheckSection, FirstPos)))
- SecondRelocCount += RelocCount;
- }
- SizeLeft -= CheckSection->Size;
- }
- if (FirstRelocCount != SecondRelocCount)
- InsertAtSecondPos = SecondRelocCount > FirstRelocCount;
- else if (FirstTrouble && (!SecondTrouble))
- InsertAtSecondPos = FALSE;
- else if (SecondTrouble && (!FirstTrouble))
- InsertAtSecondPos = TRUE;
- }
- }
- {
- OFFSET RelatedSectionIdx = CurSectionIdx + 1;
- OFFSET RelatedSectionSearchEnd = CurSectionIdx + MAX_RELATED_SEARCH_LENGTH;
- if (RelatedSectionSearchEnd > SectionCount)
- RelatedSectionSearchEnd = SectionCount;
- do {
- // Insert the section.
- if (InsertAtSecondPos)
- {
- SIZE OriginalDifference = SecondSize - FirstSize;
- InsertBefore (Program->Sections, Section, SecondPos);
- SecondSize += Section->Size;
- if (OriginalDifference <= MAX_UNBALANCED_SIZE)
- {
- SIZE SizeLeft = FirstSize + SecondSize;
- SECTION *CheckSection, *NextSection;
- for (CheckSection = (FirstPos ? GetNext (FirstPos) : GetFirst (Program->Sections)); CheckSection && CheckSection != SecondPos && SizeLeft > M68K_REL_MAX; CheckSection = NextSection)
- {
- NextSection = GetNext (CheckSection);
- if (GetRelocCountBetween (Section, CheckSection) > 0 && OriginalDifference + 2 * CheckSection->Size <= MAX_UNBALANCED_SIZE && CanMoveSectionToBack (CheckSection, SecondPos))
- {
- Unlink (Program->Sections, CheckSection);
- InsertBefore (Program->Sections, CheckSection, SecondPos);
- SecondSize += CheckSection->Size;
- FirstSize -= CheckSection->Size;
- }
- SizeLeft -= CheckSection->Size;
- }
- }
- }
- else
- {
- SIZE OriginalDifference = FirstSize - SecondSize;
- InsertAfter (Program->Sections, Section, FirstPos);
- FirstSize += Section->Size;
- if (OriginalDifference <= MAX_UNBALANCED_SIZE)
- {
- SIZE SizeLeft = FirstSize + SecondSize;
- SECTION *CheckSection, *NextSection;
- for (CheckSection = (SecondPos ? GetPrev (SecondPos) : GetLast (Program->Sections)); CheckSection && CheckSection != FirstPos && SizeLeft > M68K_REL_MAX; CheckSection = NextSection)
- {
- NextSection = GetPrev (CheckSection);
- if (GetRelocCountBetween (Section, CheckSection) > 0 && OriginalDifference + 2 * CheckSection->Size <= MAX_UNBALANCED_SIZE && CanMoveSectionToFront (CheckSection, FirstPos))
- {
- Unlink (Program->Sections, CheckSection);
- InsertAfter (Program->Sections, CheckSection, FirstPos);
- FirstSize += CheckSection->Size;
- SecondSize -= CheckSection->Size;
- }
- SizeLeft -= CheckSection->Size;
- }
- }
- }
- {
- SECTION *RelatedSection = NULL;
- // Look for a closely related section, which should be put right
- // next to this one.
- for (; RelatedSectionIdx < RelatedSectionSearchEnd && (!RelatedSection); RelatedSectionIdx++)
- {
- SECTION *SearchSection = Sections[RelatedSectionIdx];
- if (SearchSection)
- {
- COUNT Relationship;
- if (InsertAtSecondPos)
- Relationship = M68kGetSectionRelationship (Section, SearchSection);
- else
- Relationship = M68kGetSectionRelationship (SearchSection, Section);
- if (Relationship > SearchSection->Size)
- {
- RelatedSection = SearchSection;
- Sections[RelatedSectionIdx] = NULL;
- }
- }
- }
- Section = RelatedSection;
- }
- } while (Section);
- }
- }
- }
-
- // Look at the effect of putting sections referenced by startup sections
- // at the beginning. If it doesn't seem to have any negative effect, then
- // do it.
- {
- if (FirstPos)
- InsertPos = GetNext (FirstPos);
- else
- InsertPos = GetFirst (Program->Sections);
- {
- SECTION *FirstProblem;
- SIZE ProblemSize = 0;
- for (FirstProblem = InsertPos; FirstProblem && ProblemSize <= M68K_REL_MAX; FirstProblem = GetNext (FirstProblem))
- ProblemSize += FirstProblem->Size;
- {
- SECTION *Section, *NextSection;
- for (Section = InsertPos; Section && Section != SecondPos; Section = NextSection)
- {
- NextSection = GetNext (Section);
- if (Section->Relocs.StartupRefs && CanMoveSection (Section))
- {
- BOOLEAN CanMove = TRUE;
- SECTION *CheckSection;
- for (CheckSection = FirstProblem; CheckSection && CheckSection != SecondPos; CheckSection = GetNext (CheckSection))
- {
- if (GetRelocCountBetween (Section, CheckSection) > 0)
- {
- CanMove = FALSE;
- break;
- }
- }
- if (CanMove)
- {
- Unlink (Program->Sections, Section);
- InsertAfter (Program->Sections, Section, FirstPos);
- }
- }
- }
- }
- }
- }
- }
- }
- free (Sections);
- }
|