constmrg.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279
  1. /* constmrg.c: Routines to merge constants
  2. Copyright (C) 2004 Kevin Kofler
  3. This program is free software; you can redistribute it and/or modify
  4. it under the terms of the GNU General Public License as published by
  5. the Free Software Foundation; either version 2, or (at your option)
  6. any later version.
  7. This program is distributed in the hope that it will be useful,
  8. but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  10. GNU General Public License for more details.
  11. You should have received a copy of the GNU General Public License
  12. along with this program; if not, write to the Free Software Foundation,
  13. Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  14. #include "generic.h"
  15. #include "data.h"
  16. #include "constmrg.h"
  17. #include "manip.h"
  18. #include "bincode/cutrange.h"
  19. #include <stdlib.h>
  20. #include <string.h>
  21. #ifndef min
  22. #define min(a,b) ({typeof(a) __a = (a); typeof(b) __b = (b); (__a < __b) ? __a : __b;})
  23. #endif
  24. #ifndef max
  25. #define max(a,b) ({typeof(a) __a = (a); typeof(b) __b = (b); (__a > __b) ? __a : __b;})
  26. #endif
  27. // Merge constants (including strings) in sections marked Mergeable to avoid
  28. // duplication. A constant is considered to be an interval enclosed within 2
  29. // label groups, where a label group is the equivalence class formed by the
  30. // symbols at a given offset. A constant is said unaligned if the section
  31. // containing it also has the Unaligned flag set, and aligned otherwise. The
  32. // value of a constant is said to be the contents of the interval defining it.
  33. // The algorithm used is a prefix merge algorithm:
  34. // * If the value of a constant A is a prefix of the value of a constant B, and
  35. // A is unaligned and/or B is aligned, then A is identified with B.
  36. // * If the value of a constant A is a strict prefix of the value of a constant
  37. // B, A is aligned and B is unaligned, then B is split into a new aligned
  38. // section, and A is identified with the so-created B.
  39. // Identification works the following way: The label group defining A is moved
  40. // into the label group defining B. Then, if A was constituting an entire
  41. // section, the section is deleted. Otherwise, A is removed using the
  42. // range-cutting API.
  43. // The linker doesn't look for identical constants in the same section. It is
  44. // the compiler's job to merge constants in this case.
  45. void MergeConstants (PROGRAM *Program)
  46. {
  47. // Loop through all constants.
  48. SECTION *Section1, *NextSection1;
  49. for (Section1 = GetFirst (Program->Sections); Section1; Section1 = NextSection1)
  50. {
  51. SYMBOL *Symbol1, *NextSymbol1;
  52. NextSection1 = GetNext (Section1);
  53. if (!Section1->Mergeable) continue; // Ignore non-mergeable sections.
  54. for (Symbol1 = GetFirst(Section1->Symbols); Symbol1; Symbol1 = NextSymbol1)
  55. {
  56. // Compute the length of the constant.
  57. OFFSET Constant1Start = Symbol1->Location, Constant1End, Constant1Length;
  58. SECTION *Section2, *NextSection2;
  59. NextSymbol1 = FindSymbolAtPos (Section1, Symbol1->Location + 1, TRUE);
  60. Constant1End = NextSymbol1 ? NextSymbol1->Location : Section1->Size;
  61. Constant1Length = Constant1End - Constant1Start;
  62. // Loop through all constants in the following sections.
  63. for (Section2 = NextSection1; Section2; Section2 = NextSection2)
  64. {
  65. SYMBOL *Symbol2, *NextSymbol2;
  66. NextSection2 = GetNext (Section2);
  67. if (!Section2->Mergeable) continue; // Ignore non-mergeable sections.
  68. for (Symbol2 = GetFirst(Section2->Symbols); Symbol2; Symbol2 = NextSymbol2)
  69. {
  70. // Compute the length of the constant.
  71. OFFSET Constant2Start = Symbol2->Location, Constant2End, Constant2Length;
  72. NextSymbol2 = FindSymbolAtPos (Section2, Symbol2->Location + 1, TRUE);
  73. Constant2End = NextSymbol2 ? NextSymbol2->Location : Section2->Size;
  74. Constant2Length = Constant2End - Constant2Start;
  75. // Check if one constant is a prefix of the other.
  76. if (memcmp(Section1->Data + Constant1Start, Section2->Data + Constant2Start,
  77. min (Constant1Length, Constant2Length)))
  78. continue;
  79. // Now we know it is. We must now decide which constant to merge into which.
  80. // Try direct merge of Constant2 into Constant1 first.
  81. if ((Constant2Length <= Constant1Length) && (!Section1->Unaligned || Section2->Unaligned))
  82. {
  83. // Move the label group of Constant2 into Constant1.
  84. SYMBOL *CurSymbol, *NextSymbol;
  85. for (CurSymbol = Symbol2; CurSymbol && CurSymbol->Location == Constant2Start; CurSymbol = NextSymbol)
  86. {
  87. NextSymbol = GetNext (CurSymbol);
  88. // Don't move the section symbol.
  89. if (CurSymbol == Section2->SectionSymbol) continue;
  90. Unlink (Section2->Symbols, CurSymbol);
  91. CurSymbol->Parent = Section1;
  92. CurSymbol->Location = Constant1Start;
  93. InsertBefore (Section1->Symbols, CurSymbol, NextSymbol1);
  94. }
  95. // Delete Constant2.
  96. if (Constant2Length == Section2->Size)
  97. {
  98. // Move the section symbol. We are deleting the section, so we need to
  99. // put the symbol somewhere else. It should never be referenced anyway,
  100. // but if it is, we don't want the linker to segfault. Do this here,
  101. // because even when not explicitly skipping it in the loop above, it
  102. // won't always be caught by the loop.
  103. Unlink (Section2->Symbols, Section2->SectionSymbol);
  104. Section2->SectionSymbol->Parent = Section1;
  105. Section2->SectionSymbol->Location = Constant1Start;
  106. InsertBefore (Section1->Symbols, Section2->SectionSymbol, NextSymbol1);
  107. // If the Section2 was the next Section1, we must update NextSection1.
  108. if (Section2 == NextSection1)
  109. NextSection1 = GetNext (NextSection1);
  110. // Free the section.
  111. FreeSection (Section2);
  112. }
  113. else
  114. {
  115. // We don't check CanCutRange here. Mergeable ranges are supposed to be always cuttable.
  116. CutRange (Section2, Constant2Start, Constant2End);
  117. // Realloc the data now, we don't know if we will cut other ranges.
  118. FinalizeRangeCutting (Section2);
  119. }
  120. // Proceed normally. If we deleted Section2, then NextSymbol2 is NULL and we'll exit the inner loop
  121. // immediately. Otherwise, we can continue with NextSymbol2.
  122. }
  123. // Try direct merge of Constant1 into Constant2.
  124. else if ((Constant1Length <= Constant2Length) && (!Section2->Unaligned || Section1->Unaligned))
  125. {
  126. // Move the label group of Constant1 into Constant2.
  127. SYMBOL *CurSymbol, *NextSymbol;
  128. for (CurSymbol = Symbol1; CurSymbol && CurSymbol->Location == Constant1Start; CurSymbol = NextSymbol)
  129. {
  130. NextSymbol = GetNext (CurSymbol);
  131. // Don't move the section symbol.
  132. if (CurSymbol == Section1->SectionSymbol) continue;
  133. Unlink (Section1->Symbols, CurSymbol);
  134. CurSymbol->Parent = Section2;
  135. CurSymbol->Location = Constant2Start;
  136. InsertBefore (Section2->Symbols, CurSymbol, NextSymbol2);
  137. }
  138. // Delete Constant1.
  139. if (Constant1Length == Section1->Size)
  140. {
  141. // Move the section symbol. We are deleting the section, so we need to
  142. // put the symbol somewhere else. It should never be referenced anyway,
  143. // but if it is, we don't want the linker to segfault. Do this here,
  144. // because even when not explicitly skipping it in the loop above, it
  145. // won't always be caught by the loop.
  146. Unlink (Section1->Symbols, Section1->SectionSymbol);
  147. Section1->SectionSymbol->Parent = Section2;
  148. Section1->SectionSymbol->Location = Constant2Start;
  149. InsertBefore (Section2->Symbols, Section1->SectionSymbol, NextSymbol2);
  150. // Free the section.
  151. FreeSection (Section1);
  152. }
  153. else
  154. {
  155. // We don't check CanCutRange here. Mergeable ranges are supposed to be always cuttable.
  156. CutRange (Section1, Constant1Start, Constant1End);
  157. // Realloc the data now, we don't know if we will cut other ranges.
  158. FinalizeRangeCutting (Section1);
  159. }
  160. // Exit the inner loops. We need a new Symbol1. (We will get back to Symbol2 later.)
  161. goto NewSymbol1;
  162. }
  163. // Otherwise we have to throw away both Constant1 and Constant2 and create a completely new section.
  164. else
  165. {
  166. // Create a new section, initialize it, and append it to the list of sections.
  167. SECTION *Section = calloc (1, sizeof (SECTION));
  168. if (!Section)
  169. {
  170. OutOfMem:
  171. Warning (NULL, "Out of memory during constant merging.");
  172. return;
  173. }
  174. Section->Parent = Program;
  175. Section->Initialized = TRUE;
  176. Section->Mergeable = TRUE;
  177. Section->Referenced = TRUE;
  178. Section->Size = max (Constant1Length, Constant2Length);
  179. Section->Data = malloc (Section->Size);
  180. if (!Section->Data)
  181. {
  182. FreeAndOutOfMem:
  183. free (Section);
  184. goto OutOfMem;
  185. }
  186. memcpy (Section->Data, Constant1Length >= Constant2Length ? Section1->Data + Constant1Start : Section2->Data + Constant2Start, Section->Size);
  187. Section->FileName = Constant1Length >= Constant2Length ? Section1->FileName : Section2->FileName;
  188. // Create a new section symbol. We can't use the Constant1 symbol because we can't move section symbols into other sections,
  189. // but we may have to move the Constant1 symbol into another section.
  190. if (!CreateSectionSymbol (Section, ".constmerge.auto")) goto FreeAndOutOfMem;
  191. Append (Program->Sections, Section);
  192. {
  193. SYMBOL *CurSymbol, *NextSymbol;
  194. // Move the label group of Constant1 into the new section.
  195. for (CurSymbol = Symbol1; CurSymbol && CurSymbol->Location == Constant1Start; CurSymbol = NextSymbol)
  196. {
  197. NextSymbol = GetNext (CurSymbol);
  198. // Don't move the section symbol.
  199. if (CurSymbol == Section1->SectionSymbol) continue;
  200. Unlink (Section1->Symbols, CurSymbol);
  201. CurSymbol->Parent = Section;
  202. CurSymbol->Location = 0;
  203. Append (Section->Symbols, CurSymbol);
  204. }
  205. // Move the label group of Constant2 into the new section.
  206. for (CurSymbol = Symbol2; CurSymbol && CurSymbol->Location == Constant2Start; CurSymbol = NextSymbol)
  207. {
  208. NextSymbol = GetNext (CurSymbol);
  209. // Don't move the section symbol.
  210. if (CurSymbol == Section2->SectionSymbol) continue;
  211. Unlink (Section2->Symbols, CurSymbol);
  212. CurSymbol->Parent = Section;
  213. CurSymbol->Location = 0;
  214. Append (Section->Symbols, CurSymbol);
  215. }
  216. }
  217. // Delete Constant1.
  218. if (Constant1Length == Section1->Size)
  219. {
  220. // Move the section symbol. We are deleting the section, so we need to
  221. // put the symbol somewhere else. It should never be referenced anyway,
  222. // but if it is, we don't want the linker to segfault. Do this here,
  223. // because even when not explicitly skipping it in the loop above, it
  224. // won't always be caught by the loop.
  225. Unlink (Section1->Symbols, Section1->SectionSymbol);
  226. Section1->SectionSymbol->Parent = Section;
  227. Append (Section->Symbols, Section1->SectionSymbol);
  228. // Free the section.
  229. FreeSection (Section1);
  230. }
  231. else
  232. {
  233. // We don't check CanCutRange here. Mergeable ranges are supposed to be always cuttable.
  234. CutRange (Section1, Constant1Start, Constant1End);
  235. // Realloc the data now, we don't know if we will cut other ranges.
  236. FinalizeRangeCutting (Section1);
  237. }
  238. // Delete Constant2.
  239. if (Constant2Length == Section2->Size)
  240. {
  241. // Move the section symbol. We are deleting the section, so we need to
  242. // put the symbol somewhere else. It should never be referenced anyway,
  243. // but if it is, we don't want the linker to segfault. Do this here,
  244. // because even when not explicitly skipping it in the loop above, it
  245. // won't always be caught by the loop.
  246. Unlink (Section2->Symbols, Section2->SectionSymbol);
  247. Section2->SectionSymbol->Parent = Section;
  248. Append (Section->Symbols, Section2->SectionSymbol);
  249. // If the Section2 was the next Section1, we must update NextSection1.
  250. if (Section2 == NextSection1)
  251. NextSection1 = GetNext (NextSection1);
  252. // Free the section.
  253. FreeSection (Section2);
  254. }
  255. else
  256. {
  257. // We don't check CanCutRange here. Mergeable ranges are supposed to be always cuttable.
  258. CutRange (Section2, Constant2Start, Constant2End);
  259. // Realloc the data now, we don't know if we will cut other ranges.
  260. FinalizeRangeCutting (Section2);
  261. }
  262. // Exit the inner loops. We need a new Symbol1. (If another symbol matches, we will get back to it later.)
  263. goto NewSymbol1;
  264. }
  265. }
  266. }
  267. NewSymbol1:;
  268. }
  269. }
  270. }