1 | /*****************************************************************************/ |
2 | /* */ |
3 | /* litpool.c */ |
4 | /* */ |
5 | /* Literal string handling for the cc65 C compiler */ |
6 | /* */ |
7 | /* */ |
8 | /* */ |
9 | /* (C) 1998-2013, Ullrich von Bassewitz */ |
10 | /* Roemerstrasse 52 */ |
11 | /* D-70794 Filderstadt */ |
12 | /* EMail: uz@cc65.org */ |
13 | /* */ |
14 | /* */ |
15 | /* This software is provided 'as-is', without any expressed or implied */ |
16 | /* warranty. In no event will the authors be held liable for any damages */ |
17 | /* arising from the use of this software. */ |
18 | /* */ |
19 | /* Permission is granted to anyone to use this software for any purpose, */ |
20 | /* including commercial applications, and to alter it and redistribute it */ |
21 | /* freely, subject to the following restrictions: */ |
22 | /* */ |
23 | /* 1. The origin of this software must not be misrepresented; you must not */ |
24 | /* claim that you wrote the original software. If you use this software */ |
25 | /* in a product, an acknowledgment in the product documentation would be */ |
26 | /* appreciated but is not required. */ |
27 | /* 2. Altered source versions must be plainly marked as such, and must not */ |
28 | /* be misrepresented as being the original software. */ |
29 | /* 3. This notice may not be removed or altered from any source */ |
30 | /* distribution. */ |
31 | /* */ |
32 | /*****************************************************************************/ |
33 | |
34 | |
35 | |
36 | #include <stdio.h> |
37 | #include <string.h> |
38 | |
39 | /* common */ |
40 | #include "attrib.h" |
41 | #include "check.h" |
42 | #include "coll.h" |
43 | #include "tgttrans.h" |
44 | #include "xmalloc.h" |
45 | |
46 | /* cc65 */ |
47 | #include "asmlabel.h" |
48 | #include "codegen.h" |
49 | #include "error.h" |
50 | #include "global.h" |
51 | #include "litpool.h" |
52 | |
53 | |
54 | |
55 | /*****************************************************************************/ |
56 | /* Data */ |
57 | /*****************************************************************************/ |
58 | |
59 | |
60 | |
61 | /* Definition of a literal */ |
62 | struct Literal { |
63 | unsigned Label; /* Asm label for this literal */ |
64 | int RefCount; /* Reference count */ |
65 | int Output; /* True if output has been generated */ |
66 | StrBuf Data; /* Literal data */ |
67 | }; |
68 | |
69 | /* Definition of the literal pool */ |
70 | struct LiteralPool { |
71 | struct SymEntry* Func; /* Function that owns the pool */ |
72 | Collection WritableLiterals; /* Writable literals in the pool */ |
73 | Collection ReadOnlyLiterals; /* Readonly literals in the pool */ |
74 | }; |
75 | |
76 | /* The global and current literal pool */ |
77 | static LiteralPool* GlobalPool = 0; |
78 | static LiteralPool* LP = 0; |
79 | |
80 | /* Stack that contains the nested literal pools. Since TOS is in LiteralPool |
81 | ** and functions aren't nested in C, the maximum depth is 1. I'm using a |
82 | ** collection anyway, so the code is prepared for nested functions or |
83 | ** whatever. |
84 | */ |
85 | static Collection LPStack = STATIC_COLLECTION_INITIALIZER; |
86 | |
87 | |
88 | |
89 | /*****************************************************************************/ |
90 | /* struct Literal */ |
91 | /*****************************************************************************/ |
92 | |
93 | |
94 | |
95 | static Literal* NewLiteral (const void* Buf, unsigned Len) |
96 | /* Create a new literal and return it */ |
97 | { |
98 | /* Allocate memory */ |
99 | Literal* L = xmalloc (sizeof (*L)); |
100 | |
101 | /* Initialize the fields */ |
102 | L->Label = GetLocalLabel (); |
103 | L->RefCount = 0; |
104 | L->Output = 0; |
105 | SB_Init (&L->Data); |
106 | SB_AppendBuf (&L->Data, Buf, Len); |
107 | |
108 | /* Return the new literal */ |
109 | return L; |
110 | } |
111 | |
112 | |
113 | |
114 | static void FreeLiteral (Literal* L) |
115 | /* Free a literal */ |
116 | { |
117 | /* Free the literal data */ |
118 | SB_Done (&L->Data); |
119 | |
120 | /* Free the structure itself */ |
121 | xfree (L); |
122 | } |
123 | |
124 | |
125 | |
126 | static void OutputLiteral (Literal* L) |
127 | /* Output one literal to the currently active data segment */ |
128 | { |
129 | /* Translate the literal into the target charset */ |
130 | TranslateLiteral (L); |
131 | |
132 | /* Define the label for the literal */ |
133 | g_defdatalabel (L->Label); |
134 | |
135 | /* Output the literal data */ |
136 | g_defbytes (SB_GetConstBuf (&L->Data), SB_GetLen (&L->Data)); |
137 | |
138 | /* Mark the literal as output */ |
139 | L->Output = 1; |
140 | } |
141 | |
142 | |
143 | |
144 | Literal* UseLiteral (Literal* L) |
145 | /* Increase the reference counter for the literal and return it */ |
146 | { |
147 | /* Increase the reference count */ |
148 | ++L->RefCount; |
149 | |
150 | /* If --local-strings was given, immediately output the literal */ |
151 | if (IS_Get (&LocalStrings)) { |
152 | /* Switch to the proper data segment */ |
153 | if (IS_Get (&WritableStrings)) { |
154 | g_usedata (); |
155 | } else { |
156 | g_userodata (); |
157 | } |
158 | /* Output the literal */ |
159 | OutputLiteral (L); |
160 | } |
161 | |
162 | /* Return the literal */ |
163 | return L; |
164 | } |
165 | |
166 | |
167 | |
168 | void ReleaseLiteral (Literal* L) |
169 | /* Decrement the reference counter for the literal */ |
170 | { |
171 | --L->RefCount; |
172 | CHECK (L->RefCount >= 0); |
173 | } |
174 | |
175 | |
176 | |
177 | void TranslateLiteral (Literal* L) |
178 | /* Translate a literal into the target charset. */ |
179 | { |
180 | TgtTranslateBuf (SB_GetBuf (&L->Data), SB_GetLen (&L->Data)); |
181 | } |
182 | |
183 | |
184 | |
185 | unsigned GetLiteralLabel (const Literal* L) |
186 | /* Return the asm label for a literal */ |
187 | { |
188 | return L->Label; |
189 | } |
190 | |
191 | |
192 | |
193 | const char* GetLiteralStr (const Literal* L) |
194 | /* Return the data for a literal as pointer to char */ |
195 | { |
196 | return SB_GetConstBuf (&L->Data); |
197 | } |
198 | |
199 | |
200 | |
201 | const StrBuf* GetLiteralStrBuf (const Literal* L) |
202 | /* Return the data for a literal as pointer to the string buffer */ |
203 | { |
204 | return &L->Data; |
205 | } |
206 | |
207 | |
208 | |
209 | unsigned GetLiteralSize (const Literal* L) |
210 | /* Get the size of a literal string */ |
211 | { |
212 | return SB_GetLen (&L->Data); |
213 | } |
214 | |
215 | |
216 | |
217 | /*****************************************************************************/ |
218 | /* Code */ |
219 | /*****************************************************************************/ |
220 | |
221 | |
222 | |
223 | static LiteralPool* NewLiteralPool (struct SymEntry* Func) |
224 | /* Create a new literal pool and return it */ |
225 | { |
226 | /* Allocate memory */ |
227 | LiteralPool* LP = xmalloc (sizeof (*LP)); |
228 | |
229 | /* Initialize the fields */ |
230 | LP->Func = Func; |
231 | InitCollection (&LP->WritableLiterals); |
232 | InitCollection (&LP->ReadOnlyLiterals); |
233 | |
234 | /* Return the new pool */ |
235 | return LP; |
236 | } |
237 | |
238 | |
239 | |
240 | static void FreeLiteralPool (LiteralPool* LP) |
241 | /* Free a LiteralPool structure */ |
242 | { |
243 | /* Free the collections contained within the struct */ |
244 | DoneCollection (&LP->WritableLiterals); |
245 | DoneCollection (&LP->ReadOnlyLiterals); |
246 | |
247 | /* Free the struct itself */ |
248 | xfree (LP); |
249 | } |
250 | |
251 | |
252 | |
253 | static int Compare (void* Data attribute ((unused)), |
254 | const void* Left, const void* Right) |
255 | /* Compare function used when sorting the literal pool */ |
256 | { |
257 | /* Larger strings are considered "smaller" */ |
258 | return (int) GetLiteralSize (Right) - (int) GetLiteralSize (Left); |
259 | } |
260 | |
261 | |
262 | |
263 | void InitLiteralPool (void) |
264 | /* Initialize the literal pool */ |
265 | { |
266 | /* Create the global literal pool */ |
267 | GlobalPool = LP = NewLiteralPool (0); |
268 | } |
269 | |
270 | |
271 | |
272 | void PushLiteralPool (struct SymEntry* Func) |
273 | /* Push the current literal pool onto the stack and create a new one */ |
274 | { |
275 | /* We must have a literal pool to push! */ |
276 | PRECONDITION (LP != 0); |
277 | |
278 | /* Push the old pool */ |
279 | CollAppend (&LPStack, LP); |
280 | |
281 | /* Create a new one */ |
282 | LP = NewLiteralPool (Func); |
283 | } |
284 | |
285 | |
286 | |
287 | LiteralPool* PopLiteralPool (void) |
288 | /* Pop the last literal pool from TOS and activate it. Return the old |
289 | ** literal pool. |
290 | */ |
291 | { |
292 | /* Remember the current literal pool */ |
293 | LiteralPool* Old = LP; |
294 | |
295 | /* Pop one from stack */ |
296 | LP = CollPop (&LPStack); |
297 | |
298 | /* Return the old one */ |
299 | return Old; |
300 | } |
301 | |
302 | |
303 | |
304 | static void MoveLiterals (Collection* Source, Collection* Target) |
305 | /* Move referenced literals from Source to Target, delete unreferenced ones */ |
306 | { |
307 | unsigned I; |
308 | |
309 | /* Move referenced literals, remove unreferenced ones */ |
310 | for (I = 0; I < CollCount (Source); ++I) { |
311 | |
312 | /* Get the literal */ |
313 | Literal* L = CollAt (Source, I); |
314 | |
315 | /* If it is referenced and not output, add it to the Target pool, |
316 | ** otherwise free it |
317 | */ |
318 | if (L->RefCount && !L->Output) { |
319 | CollAppend (Target, L); |
320 | } else { |
321 | FreeLiteral (L); |
322 | } |
323 | } |
324 | } |
325 | |
326 | |
327 | |
328 | void MoveLiteralPool (LiteralPool* LocalPool) |
329 | /* Move all referenced literals in LocalPool to the global literal pool. This |
330 | ** function will free LocalPool after moving the used string literals. |
331 | */ |
332 | { |
333 | /* Move the literals */ |
334 | MoveLiterals (&LocalPool->WritableLiterals, &GlobalPool->WritableLiterals); |
335 | MoveLiterals (&LocalPool->ReadOnlyLiterals, &GlobalPool->ReadOnlyLiterals); |
336 | |
337 | /* Free the local literal pool */ |
338 | FreeLiteralPool (LocalPool); |
339 | } |
340 | |
341 | |
342 | |
343 | static void OutputWritableLiterals (Collection* Literals) |
344 | /* Output the given writable literals */ |
345 | { |
346 | unsigned I; |
347 | |
348 | /* If nothing there, exit... */ |
349 | if (CollCount (Literals) == 0) { |
350 | return; |
351 | } |
352 | |
353 | /* Switch to the correct segment */ |
354 | g_usedata (); |
355 | |
356 | /* Emit all literals that have a reference */ |
357 | for (I = 0; I < CollCount (Literals); ++I) { |
358 | |
359 | /* Get a pointer to the literal */ |
360 | Literal* L = CollAtUnchecked (Literals, I); |
361 | |
362 | /* Output this one, if it has references and wasn't already output */ |
363 | if (L->RefCount > 0 && !L->Output) { |
364 | OutputLiteral (L); |
365 | } |
366 | |
367 | } |
368 | } |
369 | |
370 | |
371 | |
372 | static void OutputReadOnlyLiterals (Collection* Literals) |
373 | /* Output the given readonly literals merging (even partial) duplicates */ |
374 | { |
375 | unsigned I; |
376 | |
377 | /* If nothing there, exit... */ |
378 | if (CollCount (Literals) == 0) { |
379 | return; |
380 | } |
381 | |
382 | /* Switch to the correct segment */ |
383 | g_userodata (); |
384 | |
385 | /* Sort the literal pool by literal size. Larger strings go first */ |
386 | CollSort (Literals, Compare, 0); |
387 | |
388 | /* Emit all literals that have a reference */ |
389 | for (I = 0; I < CollCount (Literals); ++I) { |
390 | |
391 | unsigned J; |
392 | Literal* C; |
393 | |
394 | /* Get the next literal */ |
395 | Literal* L = CollAt (Literals, I); |
396 | |
397 | /* Ignore it, if it doesn't have references or was already output */ |
398 | if (L->RefCount == 0 || L->Output) { |
399 | continue; |
400 | } |
401 | |
402 | /* Translate the literal into the target charset */ |
403 | TranslateLiteral (L); |
404 | |
405 | /* Check if this literal is part of another one. Since the literals |
406 | ** are sorted by size (larger ones first), it can only be part of a |
407 | ** literal with a smaller index. |
408 | ** Beware: Only check literals that have actually been referenced. |
409 | */ |
410 | C = 0; |
411 | for (J = 0; J < I; ++J) { |
412 | |
413 | const void* D; |
414 | |
415 | /* Get a pointer to the compare literal */ |
416 | Literal* L2 = CollAt (Literals, J); |
417 | |
418 | /* Ignore literals that have no reference */ |
419 | if (L2->RefCount == 0) { |
420 | continue; |
421 | } |
422 | |
423 | /* Get a pointer to the data */ |
424 | D = SB_GetConstBuf (&L2->Data) + SB_GetLen (&L2->Data) - SB_GetLen (&L->Data); |
425 | |
426 | /* Compare the data */ |
427 | if (memcmp (D, SB_GetConstBuf (&L->Data), SB_GetLen (&L->Data)) == 0) { |
428 | /* Remember the literal and terminate the loop */ |
429 | C = L2; |
430 | break; |
431 | } |
432 | } |
433 | |
434 | /* Check if we found a match */ |
435 | if (C != 0) { |
436 | |
437 | /* This literal is part of a longer literal, merge them */ |
438 | g_aliasdatalabel (L->Label, C->Label, GetLiteralSize (C) - GetLiteralSize (L)); |
439 | |
440 | } else { |
441 | |
442 | /* Define the label for the literal */ |
443 | g_defdatalabel (L->Label); |
444 | |
445 | /* Output the literal data */ |
446 | g_defbytes (SB_GetConstBuf (&L->Data), SB_GetLen (&L->Data)); |
447 | |
448 | } |
449 | |
450 | /* Mark the literal */ |
451 | L->Output = 1; |
452 | } |
453 | } |
454 | |
455 | |
456 | |
457 | void OutputLiteralPool (void) |
458 | /* Output the global literal pool */ |
459 | { |
460 | /* Output both sorts of literals */ |
461 | OutputWritableLiterals (&GlobalPool->WritableLiterals); |
462 | OutputReadOnlyLiterals (&GlobalPool->ReadOnlyLiterals); |
463 | } |
464 | |
465 | |
466 | |
467 | Literal* AddLiteral (const char* S) |
468 | /* Add a literal string to the literal pool. Return the literal. */ |
469 | { |
470 | return AddLiteralBuf (S, strlen (S) + 1); |
471 | } |
472 | |
473 | |
474 | |
475 | Literal* AddLiteralBuf (const void* Buf, unsigned Len) |
476 | /* Add a buffer containing a literal string to the literal pool. Return the |
477 | ** literal. |
478 | */ |
479 | { |
480 | /* Create a new literal */ |
481 | Literal* L = NewLiteral (Buf, Len); |
482 | |
483 | /* Add the literal to the correct pool */ |
484 | if (IS_Get (&WritableStrings)) { |
485 | CollAppend (&LP->WritableLiterals, L); |
486 | } else { |
487 | CollAppend (&LP->ReadOnlyLiterals, L); |
488 | } |
489 | |
490 | /* Return the new literal */ |
491 | return L; |
492 | } |
493 | |
494 | |
495 | |
496 | Literal* AddLiteralStr (const StrBuf* S) |
497 | /* Add a literal string to the literal pool. Return the literal. */ |
498 | { |
499 | return AddLiteralBuf (SB_GetConstBuf (S), SB_GetLen (S)); |
500 | } |
501 | |