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