Line data Source code
1 : /* do not edit automatically generated by mc from M2Optimize. */
2 : /* M2Optimize.mod removes redundant quadruples.
3 :
4 : Copyright (C) 2001-2026 Free Software Foundation, Inc.
5 : Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>.
6 :
7 : This file is part of GNU Modula-2.
8 :
9 : GNU Modula-2 is free software; you can redistribute it and/or modify
10 : it under the terms of the GNU General Public License as published by
11 : the Free Software Foundation; either version 3, or (at your option)
12 : any later version.
13 :
14 : GNU Modula-2 is distributed in the hope that it will be useful, but
15 : WITHOUT ANY WARRANTY; without even the implied warranty of
16 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 : General Public License for more details.
18 :
19 : You should have received a copy of the GNU General Public License
20 : along with GNU Modula-2; see the file COPYING3. If not see
21 : <http://www.gnu.org/licenses/>. */
22 :
23 : #include "config.h"
24 : #include "system.h"
25 : #include "gcc-consolidation.h"
26 :
27 : #include <stdbool.h>
28 : # if !defined (PROC_D)
29 : # define PROC_D
30 : typedef void (*PROC_t) (void);
31 : typedef struct { PROC_t proc; } PROC;
32 : # endif
33 :
34 : # if !defined (TRUE)
35 : # define TRUE (1==1)
36 : # endif
37 :
38 : # if !defined (FALSE)
39 : # define FALSE (1==0)
40 : # endif
41 :
42 : #define _M2Optimize_C
43 :
44 : #include "GM2Optimize.h"
45 : # include "GM2Debug.h"
46 : # include "GNameKey.h"
47 : # include "GStrIO.h"
48 : # include "GNumberIO.h"
49 : # include "GM2Error.h"
50 : # include "GM2Batch.h"
51 : # include "GM2Quiet.h"
52 : # include "GM2Scope.h"
53 : # include "GSymbolTable.h"
54 : # include "GM2Quads.h"
55 :
56 :
57 : /*
58 : FoldBranches - folds unneccessary branches in the list of quadruples.
59 : It searches for the following patterns:
60 :
61 : [x] GotoOp _ _ y GotoOp _ _ z
62 : ... ...
63 : [y] GotoOp _ _ z "deleted"
64 :
65 : WHERE ... may contain 0..n Pseudo Quads
66 :
67 :
68 : OR
69 :
70 :
71 : [x] IfREL _ _ z If NOT REL _ _ a
72 : ... ...
73 : [y] Goto _ _ a "deleted"
74 : ... ...
75 : [z]
76 :
77 :
78 : WHERE ... may contain 0..n Pseudo Quads
79 : but in this case they must not be a
80 : target of any other quad.
81 : */
82 :
83 : extern "C" void M2Optimize_FoldBranches (unsigned int start, unsigned int end);
84 :
85 : /*
86 : RemoveProcedures - removes any procedures that are never referenced
87 : by the quadruples.
88 : */
89 :
90 : extern "C" void M2Optimize_RemoveProcedures (unsigned int scope);
91 :
92 : /*
93 : DisplayReachable - Displays the data structures surrounding Reachablity.
94 : */
95 :
96 : extern "C" void M2Optimize_DisplayReachable (void);
97 :
98 : /*
99 : ReduceBranch - searches for the following pattern:
100 :
101 : [x] IfREL _ _ z If NOT REL _ _ a
102 : ... ...
103 : [y] Goto _ _ a "deleted"
104 : ... ...
105 : [z]
106 :
107 :
108 : WHERE ... may contain 0..n Pseudo Quads
109 : but in this case they must not be a
110 : target of any other quad.
111 :
112 : */
113 :
114 : static bool ReduceBranch (M2Quads_QuadOperator Operator, unsigned int CurrentQuad, unsigned int CurrentOperand1, unsigned int CurrentOperand2, unsigned int CurrentOperand3, unsigned int *NextQuad, bool Folded);
115 :
116 : /*
117 : IsBasicBlock - returns TRUE if no other quadruple jumps inbetween
118 : the range From..To.
119 : It assumes that there are no jumps in the quadruples
120 : From..To.
121 : */
122 :
123 : static bool IsBasicBlock (unsigned int From, unsigned int To);
124 :
125 : /*
126 : ReduceGoto - searches for the following patterns:
127 :
128 : [x] GotoOp _ _ y GotoOp _ _ z
129 : ... ...
130 : [y] GotoOp _ _ z "deleted"
131 :
132 :
133 : */
134 :
135 : static bool ReduceGoto (unsigned int CurrentQuad, unsigned int CurrentOperand3, unsigned int NextQuad, bool Folded);
136 :
137 : /*
138 : FoldMultipleGoto - takes a QuadNo and if it jumps to another GotoOp
139 : then it takes the later target as a replacement
140 : for its own.
141 :
142 : NOTE it does not remove any quadruples.
143 : */
144 :
145 : static bool FoldMultipleGoto (unsigned int QuadNo);
146 :
147 : /*
148 : CheckNeedSavePriority -
149 : */
150 :
151 : static void CheckNeedSavePriority (unsigned int sym);
152 :
153 : /*
154 : CheckExportedReachable - checks to see whether procedure, sym, was
155 : exported and if so it calls RemoveProcedures.
156 : */
157 :
158 : static void CheckExportedReachable (unsigned int sym);
159 : static void KnownReachable (unsigned int Start, unsigned int End);
160 : static void KnownReach (unsigned int sym);
161 :
162 :
163 : /*
164 : ReduceBranch - searches for the following pattern:
165 :
166 : [x] IfREL _ _ z If NOT REL _ _ a
167 : ... ...
168 : [y] Goto _ _ a "deleted"
169 : ... ...
170 : [z]
171 :
172 :
173 : WHERE ... may contain 0..n Pseudo Quads
174 : but in this case they must not be a
175 : target of any other quad.
176 :
177 : */
178 :
179 319798 : static bool ReduceBranch (M2Quads_QuadOperator Operator, unsigned int CurrentQuad, unsigned int CurrentOperand1, unsigned int CurrentOperand2, unsigned int CurrentOperand3, unsigned int *NextQuad, bool Folded)
180 : {
181 319798 : bool constExpr;
182 319798 : bool overflowChecking;
183 319798 : M2Quads_QuadOperator OpNext;
184 319798 : unsigned int tok;
185 319798 : unsigned int NextPlusOne;
186 319798 : unsigned int Op1Next;
187 319798 : unsigned int Op2Next;
188 319798 : unsigned int Op3Next;
189 319798 : unsigned int op1tok;
190 319798 : unsigned int op2tok;
191 319798 : unsigned int op3tok;
192 319798 : unsigned int From;
193 319798 : unsigned int To;
194 :
195 : /* Goto x */
196 319798 : if ((*NextQuad) != 0)
197 : {
198 319798 : if (((M2Quads_GetNextQuad (CurrentQuad)) == CurrentOperand3) || ((M2Quads_GetRealQuad (M2Quads_GetNextQuad (CurrentQuad))) == CurrentOperand3))
199 : {
200 406 : M2Quads_SubQuad (CurrentQuad);
201 406 : Folded = true;
202 : }
203 : else
204 : {
205 319392 : From = M2Quads_GetNextQuad (CurrentQuad); /* start after CurrentQuad */
206 319392 : To = (*NextQuad); /* start after CurrentQuad */
207 319392 : CurrentOperand3 = M2Quads_GetRealQuad (CurrentOperand3);
208 319392 : NextPlusOne = M2Quads_GetRealQuad (M2Quads_GetNextQuad ((*NextQuad)));
209 319392 : M2Quads_GetQuad ((*NextQuad), &OpNext, &Op1Next, &Op2Next, &Op3Next);
210 319392 : if (((OpNext == M2Quads_GotoOp) && (NextPlusOne == CurrentOperand3)) && (IsBasicBlock (From, To)))
211 : {
212 79263 : M2Quads_GetQuadOtok (CurrentQuad, &tok, &Operator, &CurrentOperand1, &CurrentOperand2, &CurrentOperand3, &overflowChecking, &constExpr, &op1tok, &op2tok, &op3tok);
213 79263 : M2Quads_SubQuad ((*NextQuad));
214 79263 : M2Quads_PutQuadOtok (CurrentQuad, tok, M2Quads_Opposite (Operator), CurrentOperand1, CurrentOperand2, Op3Next, overflowChecking, constExpr, op1tok, op2tok, op3tok);
215 79263 : (*NextQuad) = NextPlusOne;
216 79263 : Folded = true;
217 : }
218 : }
219 319798 : if (FoldMultipleGoto (CurrentQuad))
220 : {
221 3385 : Folded = true;
222 : }
223 : }
224 319798 : return Folded;
225 : /* static analysis guarentees a RETURN statement will be used before here. */
226 : __builtin_unreachable ();
227 : }
228 :
229 :
230 : /*
231 : IsBasicBlock - returns TRUE if no other quadruple jumps inbetween
232 : the range From..To.
233 : It assumes that there are no jumps in the quadruples
234 : From..To.
235 : */
236 :
237 79263 : static bool IsBasicBlock (unsigned int From, unsigned int To)
238 : {
239 80669 : while (From != To)
240 : {
241 1406 : if (M2Quads_IsReferenced (From))
242 : {
243 : return false;
244 : }
245 : else
246 : {
247 1406 : if (From > To)
248 : {
249 0 : M2Error_InternalError ((const char *) "assert failed From should never be larger than To", 49);
250 : }
251 1406 : From = M2Quads_GetNextQuad (From);
252 : }
253 : }
254 : return true;
255 : /* static analysis guarentees a RETURN statement will be used before here. */
256 : __builtin_unreachable ();
257 : }
258 :
259 :
260 : /*
261 : ReduceGoto - searches for the following patterns:
262 :
263 : [x] GotoOp _ _ y GotoOp _ _ z
264 : ... ...
265 : [y] GotoOp _ _ z "deleted"
266 :
267 :
268 : */
269 :
270 224402 : static bool ReduceGoto (unsigned int CurrentQuad, unsigned int CurrentOperand3, unsigned int NextQuad, bool Folded)
271 : {
272 224402 : CurrentOperand3 = M2Quads_GetRealQuad (CurrentOperand3);
273 : /* IF next quad is a GotoOp */
274 224402 : if (CurrentOperand3 == NextQuad)
275 : {
276 35558 : M2Quads_SubQuad (CurrentQuad);
277 35558 : Folded = true;
278 : }
279 : else
280 : {
281 : /* Does Goto point to another Goto ? */
282 188844 : if (FoldMultipleGoto (CurrentQuad))
283 : {
284 39360 : Folded = true;
285 : }
286 : }
287 224402 : return Folded;
288 : /* static analysis guarentees a RETURN statement will be used before here. */
289 : __builtin_unreachable ();
290 : }
291 :
292 :
293 : /*
294 : FoldMultipleGoto - takes a QuadNo and if it jumps to another GotoOp
295 : then it takes the later target as a replacement
296 : for its own.
297 :
298 : NOTE it does not remove any quadruples.
299 : */
300 :
301 508642 : static bool FoldMultipleGoto (unsigned int QuadNo)
302 : {
303 508642 : M2Quads_QuadOperator Operator;
304 508642 : M2Quads_QuadOperator Op;
305 508642 : unsigned int Op1;
306 508642 : unsigned int Op2;
307 508642 : unsigned int Op3;
308 508642 : unsigned int Operand1;
309 508642 : unsigned int Operand2;
310 508642 : unsigned int Operand3;
311 :
312 508642 : M2Quads_GetQuad (QuadNo, &Operator, &Operand1, &Operand2, &Operand3);
313 508642 : Operand3 = M2Quads_GetRealQuad (Operand3); /* skip pseudo quadruples */
314 508642 : M2Quads_GetQuad (Operand3, &Op, &Op1, &Op2, &Op3); /* skip pseudo quadruples */
315 508642 : if (Op == M2Quads_GotoOp)
316 : {
317 7187 : M2Quads_PutQuad (QuadNo, Operator, Operand1, Operand2, Op3);
318 : /* forever. */
319 7187 : return Op3 != Operand3;
320 : }
321 : else
322 : {
323 : return false;
324 : }
325 : /* static analysis guarentees a RETURN statement will be used before here. */
326 : __builtin_unreachable ();
327 : }
328 :
329 :
330 : /*
331 : CheckNeedSavePriority -
332 : */
333 :
334 976873 : static void CheckNeedSavePriority (unsigned int sym)
335 : {
336 976873 : if ((SymbolTable_IsProcedure (sym)) && ((SymbolTable_GetPriority (SymbolTable_GetModuleScope (sym))) != SymbolTable_NulSym))
337 : {
338 162 : SymbolTable_PutNeedSavePriority (sym);
339 : }
340 976873 : }
341 :
342 :
343 : /*
344 : CheckExportedReachable - checks to see whether procedure, sym, was
345 : exported and if so it calls RemoveProcedures.
346 : */
347 :
348 217893 : static void CheckExportedReachable (unsigned int sym)
349 : {
350 217893 : if (SymbolTable_IsExported (SymbolTable_GetModuleScope (sym), sym))
351 : {
352 19252 : M2Optimize_RemoveProcedures (sym);
353 19252 : CheckNeedSavePriority (sym);
354 : }
355 217893 : }
356 :
357 418822 : static void KnownReachable (unsigned int Start, unsigned int End)
358 : {
359 418822 : M2Quads_QuadOperator Op;
360 418822 : unsigned int Op1;
361 418822 : unsigned int Op2;
362 418822 : unsigned int Op3;
363 :
364 : /* DeleteUnReachableProcedures */
365 418822 : if (Start != 0)
366 : {
367 5427987 : do {
368 5427987 : M2Quads_GetQuad (Start, &Op, &Op1, &Op2, &Op3);
369 5427987 : switch (Op)
370 : {
371 161410 : case M2Quads_CallOp:
372 161410 : KnownReach (Op3);
373 161410 : break;
374 :
375 957621 : case M2Quads_AddrOp:
376 957621 : case M2Quads_ParamOp:
377 957621 : case M2Quads_XIndrOp:
378 957621 : case M2Quads_BecomesOp:
379 957621 : KnownReach (Op3);
380 957621 : CheckNeedSavePriority (Op3);
381 957621 : break;
382 :
383 :
384 : default:
385 : break;
386 : }
387 5427987 : Start = M2Quads_GetNextQuad (Start);
388 5427987 : } while (! ((Start > End) || (Start == 0)));
389 : }
390 418822 : }
391 :
392 1119031 : static void KnownReach (unsigned int sym)
393 : {
394 1119031 : if ((SymbolTable_IsProcedure (sym)) && (! (SymbolTable_IsProcedureReachable (sym))))
395 : {
396 49949 : M2Optimize_RemoveProcedures (sym);
397 : }
398 1119031 : }
399 :
400 :
401 : /*
402 : FoldBranches - folds unneccessary branches in the list of quadruples.
403 : It searches for the following patterns:
404 :
405 : [x] GotoOp _ _ y GotoOp _ _ z
406 : ... ...
407 : [y] GotoOp _ _ z "deleted"
408 :
409 : WHERE ... may contain 0..n Pseudo Quads
410 :
411 :
412 : OR
413 :
414 :
415 : [x] IfREL _ _ z If NOT REL _ _ a
416 : ... ...
417 : [y] Goto _ _ a "deleted"
418 : ... ...
419 : [z]
420 :
421 :
422 : WHERE ... may contain 0..n Pseudo Quads
423 : but in this case they must not be a
424 : target of any other quad.
425 : */
426 :
427 1171026 : extern "C" void M2Optimize_FoldBranches (unsigned int start, unsigned int end)
428 : {
429 1172676 : bool Folded;
430 1172676 : unsigned int i;
431 1172676 : unsigned int j;
432 1172676 : unsigned int Right;
433 1172676 : M2Quads_QuadOperator Operator;
434 1172676 : unsigned int Operand1;
435 1172676 : unsigned int Operand2;
436 1172676 : unsigned int Operand3;
437 :
438 1172676 : do {
439 1172676 : i = start;
440 1172676 : Folded = false;
441 14242109 : while ((i <= end) && (i != 0))
442 : {
443 13861877 : j = M2Quads_GetNextQuad (i);
444 13861877 : if ((j > end) || (j == 0))
445 : {
446 792444 : return;
447 : }
448 13151312 : Right = M2Quads_GetRealQuad (j);
449 13151312 : if (Right == 0)
450 : {
451 : return;
452 : }
453 13069433 : M2Quads_GetQuad (i, &Operator, &Operand1, &Operand2, &Operand3);
454 13069433 : switch (Operator)
455 : {
456 224402 : case M2Quads_GotoOp:
457 224402 : Folded = ReduceGoto (i, Operand3, Right, Folded);
458 224402 : break;
459 :
460 319798 : case M2Quads_IfInOp:
461 319798 : case M2Quads_IfNotInOp:
462 319798 : case M2Quads_IfNotEquOp:
463 319798 : case M2Quads_IfEquOp:
464 319798 : case M2Quads_IfLessEquOp:
465 319798 : case M2Quads_IfGreEquOp:
466 319798 : case M2Quads_IfGreOp:
467 319798 : case M2Quads_IfLessOp:
468 319798 : Folded = ReduceBranch (Operator, i, Operand1, Operand2, Operand3, &Right, Folded);
469 319798 : break;
470 :
471 :
472 : default:
473 : break;
474 : }
475 13069433 : i = Right;
476 : }
477 380232 : } while (! (! Folded));
478 : }
479 :
480 :
481 : /*
482 : RemoveProcedures - removes any procedures that are never referenced
483 : by the quadruples.
484 : */
485 :
486 83957 : extern "C" void M2Optimize_RemoveProcedures (unsigned int scope)
487 : {
488 83957 : M2Scope_ScopeBlock sb;
489 :
490 83957 : sb = M2Scope_InitScopeBlock (scope);
491 83957 : if (SymbolTable_IsProcedure (scope))
492 : {
493 69201 : SymbolTable_PutProcedureReachable (scope);
494 69201 : M2Scope_ForeachScopeBlockDo2 (sb, (M2Scope_ScopeProcedure2) {(M2Scope_ScopeProcedure2_t) KnownReachable});
495 : }
496 14756 : else if (SymbolTable_IsModuleWithinProcedure (scope))
497 : {
498 : /* avoid dangling else. */
499 36 : M2Scope_ForeachScopeBlockDo2 (sb, (M2Scope_ScopeProcedure2) {(M2Scope_ScopeProcedure2_t) KnownReachable});
500 36 : SymbolTable_ForeachProcedureDo (scope, (SymbolKey_PerformOperation) {(SymbolKey_PerformOperation_t) CheckExportedReachable});
501 : }
502 : else
503 : {
504 : /* avoid dangling else. */
505 14720 : M2Scope_ForeachScopeBlockDo2 (sb, (M2Scope_ScopeProcedure2) {(M2Scope_ScopeProcedure2_t) KnownReachable});
506 14720 : SymbolTable_ForeachProcedureDo (scope, (SymbolKey_PerformOperation) {(SymbolKey_PerformOperation_t) CheckExportedReachable});
507 : }
508 83957 : SymbolTable_ForeachInnerModuleDo (scope, (SymbolKey_PerformOperation) {(SymbolKey_PerformOperation_t) M2Optimize_RemoveProcedures});
509 83957 : M2Scope_KillScopeBlock (&sb);
510 83957 : }
511 :
512 :
513 : /*
514 : DisplayReachable - Displays the data structures surrounding Reachablity.
515 : */
516 :
517 0 : extern "C" void M2Optimize_DisplayReachable (void)
518 : {
519 0 : unsigned int n;
520 0 : unsigned int m;
521 0 : unsigned int Scope;
522 0 : unsigned int StartInit;
523 0 : unsigned int EndInit;
524 0 : unsigned int StartFinish;
525 0 : unsigned int EndFinish;
526 0 : unsigned int Module;
527 0 : unsigned int Proc;
528 :
529 0 : m = 1;
530 0 : do {
531 0 : Module = M2Batch_GetModuleNo (m);
532 0 : if (Module != SymbolTable_NulSym)
533 : {
534 0 : StrIO_WriteString ((const char *) "Module", 6);
535 0 : NumberIO_WriteCard (m, 3);
536 0 : NameKey_WriteKey (SymbolTable_GetSymName (Module));
537 0 : SymbolTable_GetModuleQuads (Module, &StartInit, &EndInit, &StartFinish, &EndFinish);
538 0 : StrIO_WriteString ((const char *) " Reachable initialization", 25);
539 0 : NumberIO_WriteCard (StartInit, 6);
540 0 : NumberIO_WriteCard (EndInit, 6);
541 0 : StrIO_WriteLn ();
542 0 : StrIO_WriteString ((const char *) "Module", 6);
543 0 : NumberIO_WriteCard (m, 3);
544 0 : NameKey_WriteKey (SymbolTable_GetSymName (Module));
545 0 : SymbolTable_GetModuleQuads (Module, &StartInit, &EndInit, &StartFinish, &EndFinish);
546 0 : StrIO_WriteString ((const char *) " Reachable finalization", 23);
547 0 : NumberIO_WriteCard (StartFinish, 6);
548 0 : NumberIO_WriteCard (EndFinish, 6);
549 0 : StrIO_WriteLn ();
550 0 : n = 1;
551 0 : Proc = SymbolTable_GetNthProcedure (Module, n);
552 0 : while (Proc != SymbolTable_NulSym)
553 : {
554 0 : StrIO_WriteString ((const char *) "Procedure ", 10);
555 0 : NameKey_WriteKey (SymbolTable_GetSymName (Proc));
556 0 : SymbolTable_GetProcedureQuads (Proc, &Scope, &StartInit, &EndInit);
557 0 : StrIO_WriteString ((const char *) " Quads: ", 8);
558 0 : NumberIO_WriteCard (StartInit, 6);
559 0 : NumberIO_WriteCard (EndInit, 6);
560 0 : if (! (SymbolTable_IsProcedureReachable (Proc)))
561 : {
562 0 : StrIO_WriteString ((const char *) " UN reachable", 13);
563 : }
564 : else
565 : {
566 0 : StrIO_WriteString ((const char *) " IS reachable", 13);
567 : }
568 0 : StrIO_WriteLn ();
569 0 : n += 1;
570 0 : Proc = SymbolTable_GetNthProcedure (Module, n);
571 : }
572 0 : m += 1;
573 : }
574 0 : } while (! (Module == SymbolTable_NulSym));
575 0 : }
576 :
577 0 : extern "C" void _M2_M2Optimize_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
578 : {
579 0 : }
580 :
581 0 : extern "C" void _M2_M2Optimize_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
582 : {
583 0 : }
|
