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 364458 : 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 364458 : bool constExpr;
182 364458 : bool overflowChecking;
183 364458 : M2Quads_QuadOperator OpNext;
184 364458 : unsigned int tok;
185 364458 : unsigned int NextPlusOne;
186 364458 : unsigned int Op1Next;
187 364458 : unsigned int Op2Next;
188 364458 : unsigned int Op3Next;
189 364458 : unsigned int op1tok;
190 364458 : unsigned int op2tok;
191 364458 : unsigned int op3tok;
192 364458 : unsigned int From;
193 364458 : unsigned int To;
194 :
195 : /* Goto x */
196 364458 : if ((*NextQuad) != 0)
197 : {
198 364458 : 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 364052 : From = M2Quads_GetNextQuad (CurrentQuad); /* start after CurrentQuad */
206 364052 : To = (*NextQuad); /* start after CurrentQuad */
207 364052 : CurrentOperand3 = M2Quads_GetRealQuad (CurrentOperand3);
208 364052 : NextPlusOne = M2Quads_GetRealQuad (M2Quads_GetNextQuad ((*NextQuad)));
209 364052 : M2Quads_GetQuad ((*NextQuad), &OpNext, &Op1Next, &Op2Next, &Op3Next);
210 364052 : if (((OpNext == M2Quads_GotoOp) && (NextPlusOne == CurrentOperand3)) && (IsBasicBlock (From, To)))
211 : {
212 89392 : M2Quads_GetQuadOtok (CurrentQuad, &tok, &Operator, &CurrentOperand1, &CurrentOperand2, &CurrentOperand3, &overflowChecking, &constExpr, &op1tok, &op2tok, &op3tok);
213 89392 : M2Quads_SubQuad ((*NextQuad));
214 89392 : M2Quads_PutQuadOtok (CurrentQuad, tok, M2Quads_Opposite (Operator), CurrentOperand1, CurrentOperand2, Op3Next, overflowChecking, constExpr, op1tok, op2tok, op3tok);
215 89392 : (*NextQuad) = NextPlusOne;
216 89392 : Folded = true;
217 : }
218 : }
219 364458 : if (FoldMultipleGoto (CurrentQuad))
220 : {
221 3735 : Folded = true;
222 : }
223 : }
224 364458 : 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 89392 : static bool IsBasicBlock (unsigned int From, unsigned int To)
238 : {
239 90861 : while (From != To)
240 : {
241 1469 : if (M2Quads_IsReferenced (From))
242 : {
243 : return false;
244 : }
245 : else
246 : {
247 1469 : if (From > To)
248 : {
249 0 : M2Error_InternalError ((const char *) "assert failed From should never be larger than To", 49);
250 : }
251 1469 : 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 248160 : static bool ReduceGoto (unsigned int CurrentQuad, unsigned int CurrentOperand3, unsigned int NextQuad, bool Folded)
271 : {
272 248160 : CurrentOperand3 = M2Quads_GetRealQuad (CurrentOperand3);
273 : /* IF next quad is a GotoOp */
274 248160 : if (CurrentOperand3 == NextQuad)
275 : {
276 38365 : M2Quads_SubQuad (CurrentQuad);
277 38365 : Folded = true;
278 : }
279 : else
280 : {
281 : /* Does Goto point to another Goto ? */
282 209795 : if (FoldMultipleGoto (CurrentQuad))
283 : {
284 42573 : Folded = true;
285 : }
286 : }
287 248160 : 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 574253 : static bool FoldMultipleGoto (unsigned int QuadNo)
302 : {
303 574253 : M2Quads_QuadOperator Operator;
304 574253 : M2Quads_QuadOperator Op;
305 574253 : unsigned int Op1;
306 574253 : unsigned int Op2;
307 574253 : unsigned int Op3;
308 574253 : unsigned int Operand1;
309 574253 : unsigned int Operand2;
310 574253 : unsigned int Operand3;
311 :
312 574253 : M2Quads_GetQuad (QuadNo, &Operator, &Operand1, &Operand2, &Operand3);
313 574253 : Operand3 = M2Quads_GetRealQuad (Operand3); /* skip pseudo quadruples */
314 574253 : M2Quads_GetQuad (Operand3, &Op, &Op1, &Op2, &Op3); /* skip pseudo quadruples */
315 574253 : if (Op == M2Quads_GotoOp)
316 : {
317 7943 : M2Quads_PutQuad (QuadNo, Operator, Operand1, Operand2, Op3);
318 : /* forever. */
319 7943 : 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 1050429 : static void CheckNeedSavePriority (unsigned int sym)
335 : {
336 1050429 : if ((SymbolTable_IsProcedure (sym)) && ((SymbolTable_GetPriority (SymbolTable_GetModuleScope (sym))) != SymbolTable_NulSym))
337 : {
338 162 : SymbolTable_PutNeedSavePriority (sym);
339 : }
340 1050429 : }
341 :
342 :
343 : /*
344 : CheckExportedReachable - checks to see whether procedure, sym, was
345 : exported and if so it calls RemoveProcedures.
346 : */
347 :
348 236121 : static void CheckExportedReachable (unsigned int sym)
349 : {
350 236121 : if (SymbolTable_IsExported (SymbolTable_GetModuleScope (sym), sym))
351 : {
352 21345 : M2Optimize_RemoveProcedures (sym);
353 21345 : CheckNeedSavePriority (sym);
354 : }
355 236121 : }
356 :
357 438681 : static void KnownReachable (unsigned int Start, unsigned int End)
358 : {
359 438681 : M2Quads_QuadOperator Op;
360 438681 : unsigned int Op1;
361 438681 : unsigned int Op2;
362 438681 : unsigned int Op3;
363 :
364 : /* DeleteUnReachableProcedures */
365 438681 : if (Start != 0)
366 : {
367 5858403 : do {
368 5858403 : M2Quads_GetQuad (Start, &Op, &Op1, &Op2, &Op3);
369 5858403 : switch (Op)
370 : {
371 179148 : case M2Quads_CallOp:
372 179148 : KnownReach (Op3);
373 179148 : break;
374 :
375 1029084 : case M2Quads_AddrOp:
376 1029084 : case M2Quads_ParamOp:
377 1029084 : case M2Quads_XIndrOp:
378 1029084 : case M2Quads_BecomesOp:
379 1029084 : KnownReach (Op3);
380 1029084 : CheckNeedSavePriority (Op3);
381 1029084 : break;
382 :
383 :
384 : default:
385 : break;
386 : }
387 5858403 : Start = M2Quads_GetNextQuad (Start);
388 5858403 : } while (! ((Start > End) || (Start == 0)));
389 : }
390 438681 : }
391 :
392 1208232 : static void KnownReach (unsigned int sym)
393 : {
394 1208232 : if ((SymbolTable_IsProcedure (sym)) && (! (SymbolTable_IsProcedureReachable (sym))))
395 : {
396 55346 : M2Optimize_RemoveProcedures (sym);
397 : }
398 1208232 : }
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 1234019 : extern "C" void M2Optimize_FoldBranches (unsigned int start, unsigned int end)
428 : {
429 1235669 : bool Folded;
430 1235669 : unsigned int i;
431 1235669 : unsigned int j;
432 1235669 : unsigned int Right;
433 1235669 : M2Quads_QuadOperator Operator;
434 1235669 : unsigned int Operand1;
435 1235669 : unsigned int Operand2;
436 1235669 : unsigned int Operand3;
437 :
438 1235669 : do {
439 1235669 : i = start;
440 1235669 : Folded = false;
441 15609671 : while ((i <= end) && (i != 0))
442 : {
443 15208397 : j = M2Quads_GetNextQuad (i);
444 15208397 : if ((j > end) || (j == 0))
445 : {
446 834395 : return;
447 : }
448 14462692 : Right = M2Quads_GetRealQuad (j);
449 14462692 : if (Right == 0)
450 : {
451 : return;
452 : }
453 14374002 : M2Quads_GetQuad (i, &Operator, &Operand1, &Operand2, &Operand3);
454 14374002 : switch (Operator)
455 : {
456 248160 : case M2Quads_GotoOp:
457 248160 : Folded = ReduceGoto (i, Operand3, Right, Folded);
458 248160 : break;
459 :
460 364458 : case M2Quads_IfInOp:
461 364458 : case M2Quads_IfNotInOp:
462 364458 : case M2Quads_IfNotEquOp:
463 364458 : case M2Quads_IfEquOp:
464 364458 : case M2Quads_IfLessEquOp:
465 364458 : case M2Quads_IfGreEquOp:
466 364458 : case M2Quads_IfGreOp:
467 364458 : case M2Quads_IfLessOp:
468 364458 : Folded = ReduceBranch (Operator, i, Operand1, Operand2, Operand3, &Right, Folded);
469 364458 : break;
470 :
471 :
472 : default:
473 : break;
474 : }
475 14374002 : i = Right;
476 : }
477 401274 : } while (! (! Folded));
478 : }
479 :
480 :
481 : /*
482 : RemoveProcedures - removes any procedures that are never referenced
483 : by the quadruples.
484 : */
485 :
486 93519 : extern "C" void M2Optimize_RemoveProcedures (unsigned int scope)
487 : {
488 93519 : M2Scope_ScopeBlock sb;
489 :
490 93519 : sb = M2Scope_InitScopeBlock (scope);
491 93519 : if (SymbolTable_IsProcedure (scope))
492 : {
493 76691 : SymbolTable_PutProcedureReachable (scope);
494 76691 : M2Scope_ForeachScopeBlockDo2 (sb, (M2Scope_ScopeProcedure2) {(M2Scope_ScopeProcedure2_t) KnownReachable});
495 : }
496 16828 : 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 16792 : M2Scope_ForeachScopeBlockDo2 (sb, (M2Scope_ScopeProcedure2) {(M2Scope_ScopeProcedure2_t) KnownReachable});
506 16792 : SymbolTable_ForeachProcedureDo (scope, (SymbolKey_PerformOperation) {(SymbolKey_PerformOperation_t) CheckExportedReachable});
507 : }
508 93519 : SymbolTable_ForeachInnerModuleDo (scope, (SymbolKey_PerformOperation) {(SymbolKey_PerformOperation_t) M2Optimize_RemoveProcedures});
509 93519 : M2Scope_KillScopeBlock (&sb);
510 93519 : }
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 : }
|
