constmrg.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290
  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. if (Constant1Start < 0)
  61. {
  62. Warning (Section1->FileName, "Symbol at negative location -0x%lx",
  63. - (long) Symbol1->Location);
  64. continue;
  65. }
  66. Constant1End = NextSymbol1 ? NextSymbol1->Location : Section1->Size;
  67. Constant1Length = Constant1End - Constant1Start;
  68. // Loop through all constants in the following sections.
  69. for (Section2 = NextSection1; Section2; Section2 = NextSection2)
  70. {
  71. SYMBOL *Symbol2, *NextSymbol2;
  72. NextSection2 = GetNext (Section2);
  73. if (!Section2->Mergeable) continue; // Ignore non-mergeable sections.
  74. for (Symbol2 = GetFirst(Section2->Symbols); Symbol2; Symbol2 = NextSymbol2)
  75. {
  76. // Compute the length of the constant.
  77. OFFSET Constant2Start = Symbol2->Location, Constant2End, Constant2Length;
  78. NextSymbol2 = FindSymbolAtPos (Section2, Symbol2->Location + 1, TRUE);
  79. if (Constant2Start < 0)
  80. {
  81. Warning (Section2->FileName, "Symbol at negative location -0x%lx",
  82. - (long) Symbol2->Location);
  83. continue;
  84. }
  85. Constant2End = NextSymbol2 ? NextSymbol2->Location : Section2->Size;
  86. Constant2Length = Constant2End - Constant2Start;
  87. // Check if one constant is a prefix of the other.
  88. if (memcmp(Section1->Data + Constant1Start, Section2->Data + Constant2Start,
  89. min (Constant1Length, Constant2Length)))
  90. continue;
  91. // Now we know it is. We must now decide which constant to merge into which.
  92. // Try direct merge of Constant2 into Constant1 first.
  93. if ((Constant2Length <= Constant1Length) && (!Section1->Unaligned || Section2->Unaligned))
  94. {
  95. // Move the label group of Constant2 into Constant1.
  96. SYMBOL *CurSymbol, *NextSymbol;
  97. for (CurSymbol = Symbol2; CurSymbol && CurSymbol->Location == Constant2Start; CurSymbol = NextSymbol)
  98. {
  99. NextSymbol = GetNext (CurSymbol);
  100. // Don't move the section symbol.
  101. if (CurSymbol == Section2->SectionSymbol) continue;
  102. Unlink (Section2->Symbols, CurSymbol);
  103. CurSymbol->Parent = Section1;
  104. CurSymbol->Location = Constant1Start;
  105. InsertBefore (Section1->Symbols, CurSymbol, NextSymbol1);
  106. }
  107. // Delete Constant2.
  108. if (Constant2Length == Section2->Size && !NextSymbol2)
  109. {
  110. // Move the section symbol. We are deleting the section, so we need to
  111. // put the symbol somewhere else. It should never be referenced anyway,
  112. // but if it is, we don't want the linker to segfault. Do this here,
  113. // because even when not explicitly skipping it in the loop above, it
  114. // won't always be caught by the loop.
  115. Unlink (Section2->Symbols, Section2->SectionSymbol);
  116. Section2->SectionSymbol->Parent = Section1;
  117. Section2->SectionSymbol->Location = Constant1Start;
  118. InsertBefore (Section1->Symbols, Section2->SectionSymbol, NextSymbol1);
  119. // If the Section2 was the next Section1, we must update NextSection1.
  120. if (Section2 == NextSection1)
  121. NextSection1 = GetNext (NextSection1);
  122. // Free the section.
  123. FreeSection (Section2);
  124. }
  125. else
  126. {
  127. // We don't check CanCutRange here. Mergeable ranges are supposed to be always cuttable.
  128. CutRange (Section2, Constant2Start, Constant2End);
  129. // Realloc the data now, we don't know if we will cut other ranges.
  130. FinalizeRangeCutting (Section2);
  131. }
  132. // Proceed normally. If we deleted Section2, then NextSymbol2 is NULL and we'll exit the inner loop
  133. // immediately. Otherwise, we can continue with NextSymbol2.
  134. }
  135. // Try direct merge of Constant1 into Constant2.
  136. else if ((Constant1Length <= Constant2Length) && (!Section2->Unaligned || Section1->Unaligned))
  137. {
  138. // Move the label group of Constant1 into Constant2.
  139. SYMBOL *CurSymbol, *NextSymbol;
  140. for (CurSymbol = Symbol1; CurSymbol && CurSymbol->Location == Constant1Start; CurSymbol = NextSymbol)
  141. {
  142. NextSymbol = GetNext (CurSymbol);
  143. // Don't move the section symbol.
  144. if (CurSymbol == Section1->SectionSymbol) continue;
  145. Unlink (Section1->Symbols, CurSymbol);
  146. CurSymbol->Parent = Section2;
  147. CurSymbol->Location = Constant2Start;
  148. InsertBefore (Section2->Symbols, CurSymbol, NextSymbol2);
  149. }
  150. // Delete Constant1.
  151. if (Constant1Length == Section1->Size && !NextSymbol1)
  152. {
  153. // Move the section symbol. We are deleting the section, so we need to
  154. // put the symbol somewhere else. It should never be referenced anyway,
  155. // but if it is, we don't want the linker to segfault. Do this here,
  156. // because even when not explicitly skipping it in the loop above, it
  157. // won't always be caught by the loop.
  158. Unlink (Section1->Symbols, Section1->SectionSymbol);
  159. Section1->SectionSymbol->Parent = Section2;
  160. Section1->SectionSymbol->Location = Constant2Start;
  161. InsertBefore (Section2->Symbols, Section1->SectionSymbol, NextSymbol2);
  162. // Free the section.
  163. FreeSection (Section1);
  164. }
  165. else
  166. {
  167. // We don't check CanCutRange here. Mergeable ranges are supposed to be always cuttable.
  168. CutRange (Section1, Constant1Start, Constant1End);
  169. // Realloc the data now, we don't know if we will cut other ranges.
  170. FinalizeRangeCutting (Section1);
  171. }
  172. // Exit the inner loops. We need a new Symbol1. (We will get back to Symbol2 later.)
  173. goto NewSymbol1;
  174. }
  175. // Otherwise we have to throw away both Constant1 and Constant2 and create a completely new section.
  176. else
  177. {
  178. // Create a new section, initialize it, and append it to the list of sections.
  179. SECTION *Section = calloc (1, sizeof (SECTION));
  180. if (!Section)
  181. {
  182. OutOfMem:
  183. Warning (NULL, "Out of memory during constant merging.");
  184. return;
  185. }
  186. Section->Parent = Program;
  187. Section->Initialized = TRUE;
  188. Section->Mergeable = TRUE;
  189. Section->Size = max (Constant1Length, Constant2Length);
  190. Section->Data = malloc (Section->Size);
  191. if (!Section->Data)
  192. {
  193. FreeAndOutOfMem:
  194. free (Section);
  195. goto OutOfMem;
  196. }
  197. memcpy (Section->Data, Constant1Length >= Constant2Length ? Section1->Data + Constant1Start : Section2->Data + Constant2Start, Section->Size);
  198. Section->FileName = Constant1Length >= Constant2Length ? Section1->FileName : Section2->FileName;
  199. // Create a new section symbol. We can't use the Constant1 symbol because we can't move section symbols into other sections,
  200. // but we may have to move the Constant1 symbol into another section.
  201. if (!CreateSectionSymbol (Section, ".constmerge.auto")) goto FreeAndOutOfMem;
  202. Append (Program->Sections, Section);
  203. {
  204. SYMBOL *CurSymbol, *NextSymbol;
  205. // Move the label group of Constant1 into the new section.
  206. for (CurSymbol = Symbol1; CurSymbol && CurSymbol->Location == Constant1Start; CurSymbol = NextSymbol)
  207. {
  208. NextSymbol = GetNext (CurSymbol);
  209. // Don't move the section symbol.
  210. if (CurSymbol == Section1->SectionSymbol) continue;
  211. Unlink (Section1->Symbols, CurSymbol);
  212. CurSymbol->Parent = Section;
  213. CurSymbol->Location = 0;
  214. Append (Section->Symbols, CurSymbol);
  215. }
  216. // Move the label group of Constant2 into the new section.
  217. for (CurSymbol = Symbol2; CurSymbol && CurSymbol->Location == Constant2Start; CurSymbol = NextSymbol)
  218. {
  219. NextSymbol = GetNext (CurSymbol);
  220. // Don't move the section symbol.
  221. if (CurSymbol == Section2->SectionSymbol) continue;
  222. Unlink (Section2->Symbols, CurSymbol);
  223. CurSymbol->Parent = Section;
  224. CurSymbol->Location = 0;
  225. Append (Section->Symbols, CurSymbol);
  226. }
  227. }
  228. // Delete Constant1.
  229. if (Constant1Length == Section1->Size && !NextSymbol1)
  230. {
  231. // Move the section symbol. We are deleting the section, so we need to
  232. // put the symbol somewhere else. It should never be referenced anyway,
  233. // but if it is, we don't want the linker to segfault. Do this here,
  234. // because even when not explicitly skipping it in the loop above, it
  235. // won't always be caught by the loop.
  236. Unlink (Section1->Symbols, Section1->SectionSymbol);
  237. Section1->SectionSymbol->Parent = Section;
  238. Append (Section->Symbols, Section1->SectionSymbol);
  239. // Free the section.
  240. FreeSection (Section1);
  241. }
  242. else
  243. {
  244. // We don't check CanCutRange here. Mergeable ranges are supposed to be always cuttable.
  245. CutRange (Section1, Constant1Start, Constant1End);
  246. // Realloc the data now, we don't know if we will cut other ranges.
  247. FinalizeRangeCutting (Section1);
  248. }
  249. // Delete Constant2.
  250. if (Constant2Length == Section2->Size && !NextSymbol2)
  251. {
  252. // Move the section symbol. We are deleting the section, so we need to
  253. // put the symbol somewhere else. It should never be referenced anyway,
  254. // but if it is, we don't want the linker to segfault. Do this here,
  255. // because even when not explicitly skipping it in the loop above, it
  256. // won't always be caught by the loop.
  257. Unlink (Section2->Symbols, Section2->SectionSymbol);
  258. Section2->SectionSymbol->Parent = Section;
  259. Append (Section->Symbols, Section2->SectionSymbol);
  260. // If the Section2 was the next Section1, we must update NextSection1.
  261. if (Section2 == NextSection1)
  262. NextSection1 = GetNext (NextSection1);
  263. // Free the section.
  264. FreeSection (Section2);
  265. }
  266. else
  267. {
  268. // We don't check CanCutRange here. Mergeable ranges are supposed to be always cuttable.
  269. CutRange (Section2, Constant2Start, Constant2End);
  270. // Realloc the data now, we don't know if we will cut other ranges.
  271. FinalizeRangeCutting (Section2);
  272. }
  273. // Exit the inner loops. We need a new Symbol1. (If another symbol matches, we will get back to it later.)
  274. goto NewSymbol1;
  275. }
  276. }
  277. }
  278. NewSymbol1:;
  279. }
  280. }
  281. }