1 /*
2 * Copyright (c) 1994-2019, NVIDIA CORPORATION. All rights reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *
16 */
17
18 /* optimize.c - main module of the optimize phase.
19 portions of this module are used by the vectorizer.
20
21 void optimize() - main controller for the optimizer
22 void optshrd_init() - init for structures and submodules shared by
23 the by optimizer and vectorizer
24 void optshrd_finit() - init for a function before its processed
25 by the optimizer or vectorizer.
26 void optshrd_fend() - cleanup after a function has been processed
27 by the optimizer or vectorizer.
28 void optshrd_end() - cleanup of shared structures and submodules
29 shared by the optimizer and vectorizer.
30
31 static void optimize_init()
32 static void optimize_end()
33 static void function_init()
34 static void function_end()
35 static void merge_blocks()
36 static void loop_init(int)
37 extern void add_loop_preheader(int)
38 static void add_loop_exit(int)
39 static void process_exit(int, int)
40 static void replace_label(int, int, int)
41
42 */
43 #include "gbldefs.h"
44 #include "global.h"
45 #include "error.h"
46 #include "symtab.h"
47 #include "ast.h"
48 #include "nme.h"
49 #include "optimize.h"
50 #include "machar.h"
51
52 #if DEBUG
53 extern void dmpnme(void);
54 #endif
55
56 extern void open_pragma(int);
57 extern void close_pragma(void);
58
59 static void br_to_br(void);
60 static void merge_blocks(void);
61 static void loop_init(int lp);
62 static void process_exit(int lp, int s);
63 static void replace_label(int bihx, int label, int newlab);
64
65 /* SHARED init and end routines for the vectorizer and optimizer */
66
67 /*
68 * Initialize and free the data structures that are shared by the
69 * vectorizer and optimizer. These data structures represent the
70 * information created by those modules that are shared by the vectorizer
71 * and optimizer. For C, this space is reused across functions in the
72 * source file during a given pass (vectorizer and optimizer); for Fortran,
73 * the space is allocated for each function. At the end of each pass, the
74 * space is freed.
75 *
76 * The shared modules are:
77 * flowgraph
78 * findloop
79 * flow
80 * invariant analysis (not code motion).
81 *
82 * Since it's possible for the vectorizer/optimizer to see more than one
83 * function, it's necessary to initialize and free certain data structures
84 * that are valid only for the lifetime of a function (for example,
85 * various getitem areas).
86 *
87 * A skeleton of the vectorizer/optimizer for using these routines is:
88 *
89 * optshrd_init();
90 * foreach function {
91 * optshrd_finit();
92 * ...
93 * optshrd_fend();
94 * }
95 * optshrd_end();
96 *
97 */
98
99 void
optshrd_init(void)100 optshrd_init(void)
101 {
102
103 STG_ALLOC(opt.fgb, 100); /* flowgraph space */
104 opt.fgb.stg_avail = 0; /* expected starting value */
105 gbl.entbih = 1; /* the first bih */
106 STG_ALLOC(opt.rteb, 32); /* retreating edges */
107
108 STG_ALLOC(opt.lpb, 50); /* loop table */
109 LP_PARENT(0) = 0; /* set the parent of region 0 to 0 -- this is
110 * for tests which look at the parent of a
111 * loop without looking at the loop index
112 */
113
114 STG_ALLOC(opt.storeb, 100); /* store area */
115 STG_ALLOC(opt.defb, 64); /* definition table */
116 STG_ALLOC(opt.useb, 64); /* use lists */
117
118 STG_ALLOC(opt.invb, 100); /* invariant expr area */
119 STG_ALLOC_SIDECAR(astb, opt.astb);
120
121 opt.sc = SC_AUTO; /* default storage class for opt-created temps */
122
123 nme_init();
124
125 }
126
127 void
optshrd_finit(void)128 optshrd_finit(void)
129 {
130
131 }
132
133 void
optshrd_fend(void)134 optshrd_fend(void)
135 {
136 flow_end();
137
138 freearea(PSI_AREA);
139 freearea(DU_AREA);
140 freearea(STL_AREA);
141
142 }
143
144 void
optshrd_end(void)145 optshrd_end(void)
146 {
147 STG_DELETE(opt.fgb);
148 STG_DELETE(opt.rteb);
149 STG_DELETE(opt.lpb);
150 STG_DELETE(opt.storeb);
151 STG_DELETE(opt.defb);
152 STG_DELETE(opt.useb);
153 STG_DELETE(opt.invb);
154 STG_DELETE_SIDECAR(astb, opt.astb);
155 nme_end();
156
157 }
158
159 /*
160 * hlopt_init() & hlopt_end():
161 * Initialization & cleanup for 'high level' optimizations (transformations)
162 * such as unrolling & invariant if removal. The optimizations require
163 * a flow graph, loop discovery, and flow analysis. Optional analysis
164 * is induction analysis (see HLOPT_... in optimize.h).
165 */
166 void
hlopt_init(int hlopt_bv)167 hlopt_init(int hlopt_bv)
168 {
169 optshrd_init();
170
171 if (hlopt_bv & HLOPT_INDUC)
172 induction_init();
173
174 optshrd_finit();
175
176 flowgraph(); /* build the flowgraph for the function */
177 #if DEBUG
178 if (DBGBIT(9, 1))
179 dump_flowgraph();
180 #endif
181
182 findloop(hlopt_bv); /* find the loops */
183 #if DEBUG
184 if (DBGBIT(9, 4)) {
185 dump_flowgraph();
186 dump_loops();
187 }
188 #endif
189
190 flow(); /* do flow analysis on the loops */
191
192 }
193
194 void
hlopt_end(int hlopt_bv,int gbc)195 hlopt_end(int hlopt_bv, int gbc)
196 {
197 optshrd_fend();
198
199 optshrd_end();
200
201 if (hlopt_bv & HLOPT_INDUC)
202 induction_end();
203
204 }
205
206 static void
optimize_init(void)207 optimize_init(void)
208 {
209
210 /* initialize for the optimize module */
211
212 optshrd_init();
213
214 induction_init(); /* induction data areas */
215
216 }
217
218 static void
optimize_end(void)219 optimize_end(void)
220 {
221
222 /* free up the space used by the optimize module */
223
224 optshrd_end();
225
226 induction_end();
227
228 }
229
230 /* initialize for a function to be optimized */
231 static void
function_init(void)232 function_init(void)
233 {
234 optshrd_finit();
235 /* clear temporary used for innermost loop count */
236
237 opt.cntlp.cnt_sym = 0;
238
239 if (DBGBIT(0, 1))
240 fprintf(gbl.dbgfil, "***** begin optimizing %s\n",
241 getprint((int)gbl.currsub));
242
243 }
244
245 /* end for an optimized function */
246 static void
function_end(void)247 function_end(void)
248 {
249 int bihx;
250
251 optshrd_fend();
252
253 }
254
255 /*
256 * given a linked list of flow edges;
257 * return the linked list with the flow edge to 'r' removed
258 */
259 static PSI_P
remove_flow_list(PSI_P link,int r)260 remove_flow_list(PSI_P link, int r)
261 {
262 PSI_P head, tail, next;
263 head = NULL;
264 tail = NULL;
265 for (; link; link = next) {
266 next = PSI_NEXT(link);
267 PSI_NEXT(link) = NULL;
268 if (PSI_NODE(link) != r) {
269 if (head == NULL) {
270 head = link;
271 } else {
272 PSI_NEXT(tail) = link;
273 }
274 tail = link;
275 }
276 }
277 return head;
278 } /* remove_flow_list */
279
280 /*
281 * remove a loop;
282 * remove lpx from the LP_CHILD list of its parent.
283 * make the fnodes be simple fall-through fnodes
284 * add the fnodes to the fnode list of the parent
285 */
286 static void
remove_loop(int lpx)287 remove_loop(int lpx)
288 {
289 int parent, prev, head, tail;
290 parent = LP_PARENT(lpx);
291 if (LP_CHILD(parent) == lpx) {
292 LP_CHILD(parent) = LP_SIBLING(lpx);
293 /* does this make 'parent' an innermost loop? */
294 if (parent && LP_CHILD(parent) == 0) {
295 LP_INNERMOST(parent) = 1;
296 }
297 } else {
298 int lc;
299 for (lc = LP_CHILD(parent); lc && LP_SIBLING(lc) != lpx;
300 lc = LP_SIBLING(lc))
301 ;
302 if (lc && LP_SIBLING(lc) == lpx) {
303 LP_SIBLING(lc) = LP_SIBLING(lpx);
304 }
305 }
306 head = LP_HEAD(lpx);
307 tail = LP_TAIL(lpx);
308 FG_PRED(head) = remove_flow_list(FG_PRED(head), tail);
309 FG_SUCC(tail) = remove_flow_list(FG_SUCC(tail), head);
310
311 for (prev = FG_LPREV(head); prev; prev = FG_LPREV(prev)) {
312 if (FG_LOOP(prev) == parent)
313 break;
314 }
315 if (prev && LP_FG(lpx)) {
316 int next, fg;
317 next = FG_NEXT(prev);
318 FG_NEXT(prev) = LP_FG(lpx);
319 for (fg = LP_FG(lpx); fg && FG_NEXT(fg); fg = FG_NEXT(fg))
320 ;
321 FG_NEXT(fg) = next;
322 }
323 LP_FG(lpx) = 0;
324 } /* remove_loop */
325
326 /*
327 * return '1' if the ast tree has no function calls
328 */
329 static int
no_functions(int ast)330 no_functions(int ast)
331 {
332 /* ### not written */
333 return 1;
334 } /* no_functions */
335
336 void
optimize(int whichpass)337 optimize(int whichpass)
338 {
339 int lpx;
340 int i;
341
342 optimize_init();
343
344 #if DEBUG
345 if (DBGBIT(38, 128)) {
346 optimize_end();
347 return;
348 }
349 #endif
350 if (opt.fgb.stg_avail == 1) {
351 optimize_end();
352 return;
353 }
354 /* optimize is called for each function */
355
356 #if DEBUG
357 if (DBGBIT(10, 2)) {
358 fprintf(gbl.dbgfil, "STDs before optimizer\n");
359 dump_std();
360 }
361 #endif
362
363 function_init();
364
365 flowgraph(); /* build the flowgraph for the function */
366 #if DEBUG
367 if (DBGBIT(9, 1))
368 dump_flowgraph();
369 #endif
370
371 findloop(HLOPT_ALL); /* find the loops */
372
373 #if DEBUG
374 if (DBGBIT(9, 4)) {
375 dump_flowgraph();
376 dump_loops();
377 }
378 #endif
379
380 if (XBIT(70, 0x2000)) /* enhanced analysis with HCCSYM variables */
381 flg.x[70] |= 0x1000;
382 flow(); /* do flow analysis on the loops */
383 flg.x[70] &= ~0x1000;
384 if (whichpass == 1) {
385 flow_end();
386 optimize_end();
387 return;
388 }
389
390 #if DEBUG
391 if (DBGBIT(29, 128))
392 dump_loops();
393 #endif
394
395 if (XBIT(0, 0x1000))
396 use_before_def(); /* after flow; check for uses before defs */
397
398 delete_stores(); /* find deleteable stores */
399
400 /*
401 * do optimizations for each loop. also, for each loop, mark
402 * the blocks which are the head and tail of the loop and mark
403 * the head block as innermost if it's the head of an innermost
404 * loop (this information is used by the scheduler).
405 */
406 for (i = 1; i <= opt.nloops; i++) {
407 int headfg;
408
409 lpx = LP_LOOP(i);
410 headfg = LP_HEAD(lpx);
411 gbl.lineno = FG_LINENO(headfg);
412
413 if (LP_PARLOOP(lpx))
414 opt.sc = SC_PRIVATE;
415
416 /* apply loop-scoped pragmas/directives available for this loop */
417 open_pragma(gbl.lineno);
418
419 if (LP_INNERMOST(lpx)) {
420 if (XBIT(70, 0x4000)) {
421 int fg, empty, dostd;
422 /* remove empty loops */
423 empty = 1;
424 dostd = 0;
425 for (fg = LP_FG(lpx); empty && fg; fg = FG_NEXT(fg)) {
426 int std;
427 for (std = FG_STDFIRST(fg); empty && std; std = STD_NEXT(std)) {
428 switch (A_TYPEG(STD_AST(std))) {
429 case A_DO:
430 if (dostd == 0) {
431 dostd = std;
432 } else {
433 empty = 0;
434 }
435 break;
436 case A_ENDDO:
437 case A_CONTINUE:
438 break;
439 default:
440 empty = 0;
441 break;
442 }
443 if (std == FG_STDLAST(fg))
444 break;
445 }
446 }
447 if (empty && dostd) {
448 /* if the DO variable is dead, remove all the statements */
449 int doast, dovar, donme;
450 doast = STD_AST(dostd);
451 dovar = A_SPTRG(A_DOVARG(doast));
452 donme = add_arrnme(NT_VAR, dovar, 0, (INT)0, 0, FALSE);
453 if (!is_live_out(donme, lpx) && no_functions(doast)) {
454 /* remove all statements, change all to continue */
455 for (fg = LP_FG(lpx); fg; fg = FG_NEXT(fg)) {
456 int std;
457 for (std = FG_STDFIRST(fg); std; std = STD_NEXT(std)) {
458 int ast;
459 ast = STD_AST(std);
460 A_TYPEP(ast, A_CONTINUE);
461 if (std == FG_STDLAST(fg))
462 break;
463 }
464 }
465 /* this loop no longer exists.
466 * remove the loop from the LP_CHILD list of its parent.
467 * if the parent has no other children, mark the parent as INNERMOST
468 */
469 remove_loop(lpx);
470 continue;
471 } else {
472 /* insert assignment from lower bound, upper bound, stride */
473 /* insert proper assignment to DO variable */
474 /* ### not done */
475 }
476 }
477 }
478 FG_INNERMOST(headfg) = 1;
479 }
480
481 if (LP_FG(lpx) == 0) {
482 continue;
483 }
484 FG_HEAD(headfg) = 1;
485 FG_MEXITS(headfg) = LP_MEXITS(lpx);
486 FG_TAIL(LP_TAIL(lpx)) = 1;
487 loop_init(lpx);
488
489 invariant(lpx);
490
491 induction(lpx);
492
493 add_loop_preheader(lpx);
494 add_loop_exit(lpx);
495
496 /* set done bit for all nodes in the loop */
497
498 close_pragma();
499
500 opt.sc = SC_AUTO;
501 }
502 if (opt.nloops == 0) {
503 ;
504 } else {
505
506 /* do region 0 */
507
508 opt.pre_fg = NEW_NODE(gbl.entbih);
509 opt.exit_fg = NEW_NODE(FG_LPREV(opt.exitfg));
510
511 if (OPTDBG(9, 1)) {
512 fprintf(gbl.dbgfil, "\n Loop init for region 0\n");
513 fprintf(gbl.dbgfil, " preheader: %d\n", opt.pre_fg);
514 fprintf(gbl.dbgfil, " exit: %d\n", opt.exit_fg);
515 }
516 }
517
518 br_to_br();
519
520 merge_blocks(); /* merge the blocks */
521
522 function_end();
523
524 #if DEBUG
525 if (DBGBIT(10, 4)) {
526 fprintf(gbl.dbgfil, "STDs after optimizer\n");
527 dump_std();
528 }
529 if (DBGBIT(10, 64))
530 dmpnme();
531 #endif
532
533 flow_end();
534 optimize_end();
535
536 }
537
538 /*******************************************************************/
539
540 /*
541 * attempt to move the label which labels a bih. The condition for
542 * moving the label is if the block contains an unconditional branch.
543 * This routine is recursive so that if we have br to br to br, ...,
544 * the label labelling last branch in the branch chain is moved first.
545 */
546 static void
move_label(int lab,int bih)547 move_label(int lab, int bih)
548 {
549
550 }
551
552 static void
br_to_br(void)553 br_to_br(void)
554 {
555 if (XBIT(6, 0x8))
556 return;
557 if (opt.num_nodes < 3)
558 return;
559
560 }
561
562 /*******************************************************************/
563
564 static void
merge_blocks(void)565 merge_blocks(void)
566 {
567 int std;
568 int next_std;
569 int ast;
570
571 if (XBIT(8, 0x4))
572 return;
573 for (std = STD_NEXT(0); std; std = next_std) {
574 next_std = STD_NEXT(std);
575 if (STD_LABEL(std) == 0) {
576 ast = STD_AST(std);
577 if (A_TYPEG(ast) == A_CONTINUE)
578 unlnkilt(std, 0, TRUE);
579 }
580 }
581 if (opt.num_nodes < 3)
582 return;
583
584 }
585
586 /*******************************************************************/
587
588 static void
loop_init(int lp)589 loop_init(int lp)
590 {
591 opt.pre_fg = NEW_NODE(FG_LPREV(LP_HEAD(lp)));
592 FG_FT(opt.pre_fg) = 1;
593
594 /* create a block for the loop exit -- code will be added to this
595 * block as optimizations are performed. Note that block is inserted
596 * the tail of the loop
597 */
598 opt.exit_fg = NEW_NODE(LP_TAIL(lp));
599 FG_FT(opt.exit_fg) = 1;
600
601 FG_PAR(opt.pre_fg) = LP_PARLOOP(lp);
602 FG_PAR(opt.exit_fg) = LP_PARLOOP(lp);
603 if (OPTDBG(9, 1)) {
604 fprintf(gbl.dbgfil, "\n Loop init for loop (%d)\n", lp);
605 fprintf(gbl.dbgfil, " preheader: %d, exit: %d\n", opt.pre_fg,
606 opt.exit_fg);
607 }
608 }
609
610 /*******************************************************************/
611
612 /*
613 * After a loop has been processed, the flow graph is updated to include
614 * the preheader. This node is physically placed immediatedly before the
615 * loop head.
616 * The predecessors of head not in the loop are replaced by the preheader
617 * flow graph node. The predecessors of this node are the predecessors
618 * of head not in the loop.
619 * Also, this node replaces head as the successor of all the nodes not
620 * in the loop.
621 * If there is a path to the head node by branching (the node does not
622 * fall thru to the head), the label of head is replaced with a new label
623 * and all the branches to the head are modified. The original label
624 * is used to label the preheader.
625 * Also, the preheader is added to the region containing the loop.
626 */
627 void
add_loop_preheader(int lp)628 add_loop_preheader(int lp)
629 {
630 int i, v;
631 PSI_P p, q, prev;
632 int newlabel;
633
634 int head;
635
636 if (FG_STDFIRST(opt.pre_fg) == 0)
637 return;
638 if (OPTDBG(9, 1))
639 fprintf(gbl.dbgfil, "\n Preheader end for loop (%d)\n", lp);
640
641 /* Every node dominated by lp's dominator will be dominated by the
642 * new preheader. */
643 head = LP_HEAD(lp); /* loop's head */
644 i = FG_DOM(head); /* dominator of loop's head */
645 for (p = FG_SUCC(i); p != PSI_P_NULL; p = PSI_NEXT(p)) {
646 v = PSI_NODE(p);
647 if (FG_DOM(v) == i)
648 FG_DOM(v) = opt.pre_fg;
649 }
650 FG_DOM(opt.pre_fg) = i;
651 FG_DOM(head) = opt.pre_fg;
652
653 i = 0; /* number of predecessors not in the loop */
654 newlabel = 0; /* non-zero if a pred does fall thru to the head */
655 prev = PSI_P_NULL; /* the last predecessor to head that's kept */
656 for (p = FG_PRED(head); p != PSI_P_NULL; p = PSI_NEXT(p)) {
657 v = PSI_NODE(p);
658 if (FG_LOOP(v) != lp) { /* v in pred(head) and not in the loop */
659 i++;
660 if (FG_LNEXT(v) != opt.pre_fg) {
661 /* if pred. doesn't fall thru */
662 newlabel = 1;
663 }
664 /* search v's successor list for the item indicating head */
665
666 for (q = FG_SUCC(v); q != PSI_P_NULL; q = PSI_NEXT(q))
667 if (head == PSI_NODE(q))
668 break;
669 assert(q != PSI_P_NULL, "add_loop_pre:suc(q)nhd", head, 3);
670
671 /* Replace head in succ(v) with the preheader node */
672
673 PSI_NODE(q) = opt.pre_fg;
674 /*
675 * Replace v in pred(head) with the preheader node only if this
676 * is the first predecessor found which is not in the loop.
677 * Otherwise, this predecessor item (p) is deleted.
678 */
679 if (i == 1) {
680 PSI_NODE(p) = opt.pre_fg;
681 prev = p;
682 } else {
683 assert(prev != PSI_P_NULL, "add_loop_pre:prev", head, 3);
684 PSI_NEXT(prev) = PSI_NEXT(p);
685 }
686 /*
687 * make v a predecessor of the preheader and make head a
688 * successor of the preheader
689 */
690 (void)add_pred(opt.pre_fg, v);
691 q = add_succ(opt.pre_fg, head);
692 PSI_FT(q) = 1;
693 #if DEBUG
694 if (OPTDBG(9, 1)) {
695 fprintf(gbl.dbgfil, " old pred of head :\n");
696 dump_node(v);
697 }
698 #endif
699 } else /* v not in pred(head), remember this predecessor item */
700 prev = p;
701 }
702
703 if (newlabel) { /* have to create a new label for the loop head */
704 int label, newlab;
705
706 label = STD_LABEL(FG_STDFIRST(head)); /* original label */
707 newlab = getlab();
708 ILIBLKP(newlab, head); /* label the head with the new label */
709 STD_LABEL(FG_STDFIRST(head)) = newlab;
710
711 ILIBLKP(label, opt.pre_fg); /* label the preheader with the */
712 STD_LABEL(FG_STDFIRST(opt.pre_fg)) = label; /* original label */
713
714 /* find all nodes in the loop which are predecessors of head.
715 * the branches in these nodes are changed to access the new
716 * label
717 */
718 for (p = FG_PRED(head); p != PSI_P_NULL; p = PSI_NEXT(p)) {
719 v = PSI_NODE(p);
720 if (FG_LOOP(v) == lp)
721 replace_label((int)FG_TO_BIH(v), label, newlab);
722 }
723 }
724 /*
725 * set the loop field of the preheader to an ancestor of lp which
726 * contains blocks -- a loop could have been deleted (indicated by a null
727 * region)
728 */
729 for (i = lp; LP_FG(i = LP_PARENT(i)) == 0;)
730 ;
731
732 FG_LOOP(opt.pre_fg) = i;
733
734 /* add the preheader to the region for parent of lp */
735
736 FG_NEXT(opt.pre_fg) = LP_FG(i);
737 LP_FG(i) = opt.pre_fg;
738
739 /* link the preheader's stds into the std list */
740
741 {
742 int new;
743 int old;
744 int p;
745
746 /* search for the last std preceding the preheader */
747 for (p = FG_LPREV(opt.pre_fg); p; p = FG_LPREV(p))
748 if (FG_STDLAST(p))
749 break;
750 new = FG_STDFIRST(opt.pre_fg);
751 old = FG_STDLAST(p);
752 STD_NEXT(old) = new;
753 STD_PREV(new) = old;
754
755 /* search for the first std following the preheader */
756 for (p = FG_LNEXT(opt.pre_fg); p; p = FG_LNEXT(p))
757 if (FG_STDFIRST(p))
758 break;
759 new = FG_STDLAST(opt.pre_fg);
760 old = FG_STDFIRST(p);
761 STD_NEXT(new) = old;
762 STD_PREV(old) = new;
763 }
764
765 #if DEBUG
766 if (OPTDBG(9, 1)) {
767 fprintf(gbl.dbgfil, " preheader:\n");
768 dump_node(opt.pre_fg);
769 fprintf(gbl.dbgfil, " head:\n");
770 dump_node(head);
771 }
772 if (OPTDBG(9, 4)) {
773 fprintf(gbl.dbgfil, "\n Region of preheader node %d\n", opt.pre_fg);
774 dump_region(i);
775 }
776 #endif
777 }
778
779 /*******************************************************************/
780
781 static int newtarget_bih;
782 static int newtarget_fg;
783
784 /*
785 * After a loop has been processed, the flow graph is updated to include
786 * the exit node. A copy of the exit block is added for each exit of the
787 * loop. This routine figures out where to add the exit blocks in the
788 * bih list. A block can be added immediately before its exit target
789 * if the loop falls through to the target. If it is not a fall through
790 * exit target, the exit block is simply added to the end of the loop
791 * and code is added to the end of the block so that it transfers control
792 * to the exit target.
793 */
794 void
add_loop_exit(int lp)795 add_loop_exit(int lp)
796 {
797 }
798
799 /* Add a loop exit following the tail of loop lp. */
800 void
add_single_loop_exit(int lp)801 add_single_loop_exit(int lp)
802 {
803 int fg, fgSucc, fgNew;
804 PSI_P psiSucc;
805 int lpSucc;
806 int sptrLbl, sptrNewLbl;
807 int std;
808 int ast;
809
810 assert(lp, "add_loop_exit: no loop", lp, 4);
811 assert(!LP_MEXITS(lp), "add_loop_exit: multiple exits", lp, 4);
812
813 fgNew = add_fg(LP_TAIL(lp));
814 add_to_parent(fgNew, LP_PARENT(lp));
815
816 for (fg = LP_FG(lp); fg; fg = FG_NEXT(fg)) {
817 /* Search for a node with a branch to the exit. */
818 for (psiSucc = FG_SUCC(fg); psiSucc; psiSucc = PSI_NEXT(psiSucc)) {
819 fgSucc = PSI_NODE(psiSucc);
820 lpSucc = FG_LOOP(fgSucc);
821 if (!lpSucc)
822 break;
823 if (lpSucc != lp && LP_PARENT(lpSucc) != lp)
824 break;
825 }
826 if (psiSucc)
827 /* ...node with exit branch found. */
828 break;
829 }
830 assert(fg, "add_loop_exit: branch not found", lp, 4);
831 FG_FT(fgNew) = PSI_FT(psiSucc);
832
833 /* Add a CONTINUE statement to the new loop trailer. */
834 ast = mk_stmt(A_CONTINUE, 0);
835 rdilts(fgNew);
836 std = add_stmt_after(ast, 0);
837 wrilts(fgNew);
838 FG_LINENO(fgNew) = STD_LINENO(std) = FG_LINENO(LP_TAIL(lp));
839
840 sptrLbl = FG_LABEL(fgSucc);
841 if (!PSI_FT(psiSucc) && sptrLbl) {
842 int astlab;
843 /* Add a GOTO statement to the new loop trailer. */
844 ast = mk_stmt(A_GOTO, 0);
845 astlab = mk_label(sptrLbl);
846 A_L1P(ast, astlab);
847 std = add_stmt_after(ast, std);
848
849 /* Create a new label for fgNew. */
850 sptrNewLbl = getlab();
851 ILIBLKP(sptrNewLbl, fgNew);
852 RFCNTI(sptrNewLbl);
853 FG_LABEL(fgNew) = sptrNewLbl;
854
855 /* Revise the branch to go to the new loop trailer. */
856 replace_label(FG_TO_BIH(fg), sptrLbl, sptrNewLbl);
857 }
858
859 /* Fix up the pred./succ. chains. */
860 add_succ(fg, fgNew); /* succ(fg) = fgNew. */
861 add_pred(fgNew, fg); /* pred(fgNew) = fg. */
862 add_succ(fgNew, fgSucc); /* succ(fgNew) = fgSucc. */
863 add_pred(fgSucc, fgNew); /* pred(fgSucc) = fgNew. */
864 rm_edge(fg, fgSucc);
865 }
866
867 /*******************************************************************/
868
869 /*
870 * node s is an exit target of the loop. newtarget_fg represents the
871 * new exit target which must be executed before executing s.
872 * newtarget_bih is the block header for the new target and has already
873 * been inserted into the bih list.
874 * s is made a successor of the new target flow graph node.
875 * The predecessors of s in the loop are replaced by the new target.
876 * These predecessors of s become the predecessors of the new
877 * target. Also, the successor lists of these nodes are updated by replacing
878 * s with the new target.
879 * If the exit in the loop does not fall thru to the new target, then
880 * a label is created for the new target and the branch in the exit is
881 * modified to access this label. NOTE that any transfer of control changes
882 * from the new target to s have been taken care of by add_loop_exit.
883 * Also, the new target is added to the region containing the loop.
884 */
885 static void
process_exit(int lp,int s)886 process_exit(int lp, int s)
887 {
888 }
889
890 /*******************************************************************/
891
892 /*
893 * Replace all occurrences of the label with a new label.
894 */
895 static void
replace_label(int bihx,int label,int newlab)896 replace_label(int bihx, int label, int newlab)
897 {
898 int std;
899 int ast;
900
901 std = BIH_ILTLAST(bihx);
902 ast = STD_AST(std);
903 ast_visit(1, 1);
904 ast_replace(mk_label(label), mk_label(newlab));
905 ast = ast_rewrite(ast);
906 ast_unvisit();
907 STD_AST(std) = ast;
908 A_STDP(ast, std);
909 }
910
911 /*******************************************************************/
912 /*
913 * remove a block of statements;
914 * optionally convert the last ELSEIF to IF
915 * optionally keep the last ENDIF
916 */
917 static void
remove_block(int std1,int std2,LOGICAL convert_elseif,LOGICAL save_endif)918 remove_block(int std1, int std2, LOGICAL convert_elseif, LOGICAL save_endif)
919 {
920 int stdx, nextstdx, astx;
921 for (stdx = std1; stdx; stdx = nextstdx) {
922 nextstdx = STD_NEXT(stdx);
923 astx = STD_AST(stdx);
924 if (stdx == std2 && A_TYPEG(astx) == A_ELSEIF && convert_elseif) {
925 A_TYPEP(astx, A_IFTHEN);
926 break;
927 }
928 if (stdx == std2 && A_TYPEG(astx) == A_ENDIF && save_endif) {
929 break;
930 }
931 if (STD_LABEL(stdx)
932 || STD_PTA(stdx) || STD_PTASGN(stdx)
933 ) {
934 /* just convert to continue */
935 A_TYPEP(astx, A_CONTINUE);
936 } else {
937 /* remove altogether */
938 delete_stmt(stdx);
939 }
940 if (stdx == std2)
941 break;
942 }
943 } /* remove_block */
944
945 /*
946 * look for conditional branches with constant conditions.
947 * remove the branch, remove unreachable code as well.
948 */
949 void
unconditional_branches(void)950 unconditional_branches(void)
951 {
952 int stdx, nextstdx;
953 int astx, nest, stdifx, stdstmtx, sptr, stdelsex, stdendx, astelsex, astendx;
954 int condx;
955 int *ifnest;
956 int ifnestsize;
957 ifnestsize = 50;
958 NEW(ifnest, int, ifnestsize);
959 /* initially, set STD_FG for A_IFTHEN, A_ELSEIF, A_ELSE to the
960 * matching following A_ELSEIF, A_ELSE, A_ENDIF, as appropriate */
961 for (stdx = STD_NEXT(0); stdx; stdx = STD_NEXT(stdx)) {
962 astx = STD_AST(stdx);
963 switch (A_TYPEG(astx)) {
964 case A_IFTHEN:
965 ++nest;
966 NEED(nest, ifnest, int, ifnestsize, ifnestsize + 50);
967 ifnest[nest] = stdx;
968 break;
969 case A_ELSEIF:
970 case A_ELSE:
971 if (nest <= 0) {
972 /* bad nesting */
973 return;
974 }
975 stdifx = ifnest[nest];
976 STD_FG(stdifx) = stdx;
977 ifnest[nest] = stdx;
978 break;
979 case A_ENDIF:
980 if (nest <= 0) {
981 /* bad nesting */
982 FREE(ifnest);
983 return;
984 }
985 stdifx = ifnest[nest];
986 STD_FG(stdifx) = stdx;
987 --nest;
988 break;
989 }
990 }
991 FREE(ifnest);
992 for (stdx = STD_NEXT(0); stdx; stdx = nextstdx) {
993 nextstdx = STD_NEXT(stdx);
994 astx = STD_AST(stdx);
995 switch (A_TYPEG(astx)) {
996 case A_IF:
997 /* if condition is .FALSE., remove if and its statement */
998 /* if condition is .TRUE., replace condition by the statement */
999 condx = A_IFEXPRG(astx);
1000 if (A_ALIASG(condx))
1001 condx = A_ALIASG(condx);
1002 if (A_TYPEG(condx) == A_CNST && (sptr = A_SPTRG(condx)) > 0 &&
1003 DT_ISLOG(DTYPEG(sptr))) {
1004 if (CONVAL2G(sptr) == 0) {
1005 /* .false. */
1006 remove_block(stdx, stdx, FALSE, FALSE);
1007 } else {
1008 /* .true. */
1009 stdstmtx = A_IFSTMTG(astx);
1010 STD_AST(stdx) = stdstmtx;
1011 }
1012 }
1013 break;
1014 case A_IFTHEN:
1015 case A_ELSEIF:
1016 /* if condition is .FALSE., remove if and all statements up
1017 * to the ENDIF, ELSEIF, ELSE (change ELSEIF to IF, ELSE/ENDIF to
1018 * CONTINUE)
1019 * if the condition is .TRUE., remove this statement, and remove
1020 * all statements from the ELSEIF/ELSE up to and including the ENDIF */
1021 condx = A_IFEXPRG(astx);
1022 if (A_ALIASG(condx))
1023 condx = A_ALIASG(condx);
1024 if (A_TYPEG(condx) == A_CNST && (sptr = A_SPTRG(condx)) > 0 &&
1025 DT_ISLOG(DTYPEG(sptr))) {
1026 stdelsex = STD_FG(stdx);
1027 if (CONVAL2G(sptr) == 0) {
1028 /* .false. */
1029 /* remove_block changes the ELSEIF to IF, if necessary */
1030 astelsex = STD_AST(stdelsex);
1031 if (A_TYPEG(astelsex) == A_ELSEIF) {
1032 remove_block(stdx, stdelsex, TRUE, FALSE);
1033 } else {
1034 stdendx = STD_FG(stdelsex);
1035 astendx = STD_AST(stdendx);
1036 if (A_TYPEG(astendx) == A_ENDIF) {
1037 remove_block(stdx, stdelsex, TRUE, FALSE);
1038 remove_block(stdendx, stdendx, FALSE, FALSE);
1039 }
1040 }
1041 } else {
1042 /* .true. */
1043 astelsex = STD_AST(stdelsex);
1044 if (A_TYPEG(astelsex) == A_ENDIF) {
1045 /* simply change if/endif to continue/continue
1046 * or else/endif */
1047 if (A_TYPEG(astx) == A_IF) {
1048 remove_block(stdx, stdx, FALSE, FALSE);
1049 remove_block(stdelsex, stdelsex, FALSE, FALSE);
1050 } else {
1051 A_TYPEG(astx) = A_ELSE;
1052 }
1053 } else if (A_TYPEG(astelsex) == A_ELSE ||
1054 A_TYPEG(astelsex) == A_ELSEIF) {
1055 /* simply change if to continue or elseif to else,
1056 * remove elseif through endif */
1057 astendx = 0;
1058 for (stdendx = STD_FG(stdelsex); STD_FG(stdendx);
1059 stdendx = STD_FG(stdendx)) {
1060 astendx = STD_AST(stdendx);
1061 if (A_TYPEG(astendx) == A_ENDIF)
1062 break;
1063 }
1064 if (stdendx)
1065 astendx = STD_AST(stdendx);
1066 if (stdendx && astendx && A_TYPEG(astendx) == A_ENDIF) {
1067 if (A_TYPEG(astx) == A_IFTHEN) {
1068 remove_block(stdx, stdx, FALSE, FALSE);
1069 remove_block(stdelsex, stdendx, FALSE, FALSE);
1070 } else {
1071 A_TYPEG(astx) = A_ELSE;
1072 remove_block(stdelsex, stdendx, FALSE, TRUE);
1073 }
1074 }
1075 }
1076 }
1077 }
1078 break;
1079 }
1080 }
1081 /* clear STD_FG field */
1082 for (stdx = STD_NEXT(0); stdx; stdx = STD_NEXT(stdx)) {
1083 STD_FG(stdx) = 0;
1084 }
1085 } /* unconditional_branches */
1086