1 /*
2 * Copyright (c) 2017, 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 /**
19 \file
20 \brief Invariant communication optimization.
21 */
22
23 #include "gbldefs.h"
24 #include "global.h"
25 #include "error.h"
26 #include "symtab.h"
27 #include "ast.h"
28 #include "nme.h"
29 #include "machar.h"
30 #include "gramtk.h"
31 #include "optimize.h"
32 #include "induc.h"
33 #include "extern.h"
34 #include "commopt.h"
35 #include "ccffinfo.h"
36 #include "direct.h"
37
38 /* Compiler switches:
39 -x 49 0x20000: Inhibit invariant communication hoisting
40 -q 43 2: Trace invariant communication hoisting
41 -q 43 64: Dump statements before and after hoisting
42 */
43
44 /* local macros */
45 #define A_CONDG(a) A_OPT2G(a)
46 #define A_CONDP(a, v) A_OPT2P(a, v)
47
48 #if DEBUG
49 #define TRACE0(s) \
50 if (DBGBIT(43, 2)) \
51 fprintf(gbl.dbgfil, s)
52 #define TRACE1(s, a1) \
53 if (DBGBIT(43, 2)) \
54 fprintf(gbl.dbgfil, s, a1)
55 #define TRACE2(s, a1, a2) \
56 if (DBGBIT(43, 2)) \
57 fprintf(gbl.dbgfil, s, a1, a2)
58 #define TRACE3(s, a1, a2, a3) \
59 if (DBGBIT(43, 2)) \
60 fprintf(gbl.dbgfil, s, a1, a2, a3)
61 #define TRACE4(s, a1, a2, a3, a4) \
62 if (DBGBIT(43, 2)) \
63 fprintf(gbl.dbgfil, s, a1, a2, a3, a4)
64 #define TRACE5(s, a1, a2, a3, a4, a5) \
65 if (DBGBIT(43, 2)) \
66 fprintf(gbl.dbgfil, s, a1, a2, a3, a4, a5)
67 #else
68 #define TRACE0(s)
69 #define TRACE1(s, a1)
70 #define TRACE2(s, a1, a2)
71 #define TRACE3(s, a1, a2, a3)
72 #define TRACE4(s, a1, a2, a3, a4)
73 #define TRACE5(s, a1, a2, a3, a4, a5)
74 #endif
75
76 /* local functions */
77 static LOGICAL hoist_loop(int lp);
78 static void clean_flags(void);
79 static void get_loopcounts(void);
80 static LOGICAL contains_alloc(int lp);
81 static LOGICAL unique_allo(int allo_std, int allo_ft, int lp);
82 static void hoist_comms(int lp);
83 static void hoist_std(int, int, int);
84 static LOGICAL check_outer_defs(int std, int lp, int nme);
85 static LOGICAL check_inner_uses(int std, int lp, int nme);
86 static LOGICAL is_invariant_base(int nme);
87 static LOGICAL is_parent_loop(int lpParent, int lpChild);
88 static LOGICAL has_invar_subs(int ast);
89 static LOGICAL is_invariant_list(int n, int vast[]);
90 static LOGICAL check_moved_list(int n, int vstd[]);
91 static LOGICAL check_moved(int std);
92 static void move_invar_std(int std, int fg);
93 static void mk_loop_hdtl(int lp);
94 static int mk_count_test(int astCond, int astCount);
95 static int mk_dealloc_stub(int astCond);
96 static void mk_ztrips(int lp);
97 static int remove_cond(int astTarg, int astSrc);
98
99 /* global data */
100 static int fgPre; /* pre-header of current loop */
101 static int fgPost; /* trailer of current loop */
102 static LOGICAL bMovedComm; /* TRUE when invariant comm statement moved */
103 static LOGICAL bMovedAssn; /* TRUE when invariant assignment moved */
104 static int *pastCounts = NULL; /* loop counts */
105
106 /** \brief Hoist invariant communication expressions out of loops. */
107 void
comm_invar(void)108 comm_invar(void)
109 {
110 int lp;
111
112 hlopt_init(HLOPT_INDUC);
113
114 #if DEBUG
115 if (DBGBIT(43, 64)) {
116 fprintf(gbl.dbgfil, "----------- STDs before invariant hoisting\n");
117 dump_std();
118 }
119 #endif
120
121 get_loopcounts();
122
123 clean_flags();
124
125 for (lp = LP_CHILD(0); lp; lp = LP_SIBLING(lp))
126 hoist_loop(lp);
127
128 mk_ztrips(0);
129 #if DEBUG
130 if (DBGBIT(43, 64)) {
131 fprintf(gbl.dbgfil, "----------- STDs after invariant hoisting\n");
132 dump_std();
133 }
134 #endif
135
136 if (pastCounts) {
137 FREE(pastCounts);
138 pastCounts = NULL;
139 }
140 hlopt_end(HLOPT_INDUC, 0);
141 }
142
143 /* Clear flags & fields in STDs & ASTs that will be used for hoisting. */
144 static void
clean_flags(void)145 clean_flags(void)
146 {
147 int std;
148
149 for (std = STD_FIRST; std; std = STD_NEXT(std)) {
150 STD_MOVED(std) = FALSE;
151 A_CONDP(STD_AST(std), 0);
152 }
153 }
154
155 /* For each loop lp, set pastCounts[lp] to its count. */
156 static void
get_loopcounts(void)157 get_loopcounts(void)
158 {
159 int lp;
160
161 NEW(pastCounts, int, opt.nloops + 1);
162
163 for (lp = 1; lp <= opt.nloops; lp++) {
164 /* Mark invariant ASTs within lp. */
165 invariant_nomotion(lp);
166 pastCounts[lp] = get_loop_count(lp);
167 end_loop_count();
168 invariant_unmarkv();
169 }
170 }
171
172 /* Hoist invariant communication expressions out of loop #lp. Return TRUE
173 * if lp is a candidate for hoisting. */
174 static LOGICAL
hoist_loop(int lp)175 hoist_loop(int lp)
176 {
177 int lpi;
178 LOGICAL bHoistInner = TRUE;
179 LOGICAL bx49;
180
181 for (lpi = LP_CHILD(lp); lpi; lpi = LP_SIBLING(lpi))
182 bHoistInner &= hoist_loop(lpi);
183
184 if (!bHoistInner)
185 /* Don't analyze if an inner loop can't be analyzed. */
186 return FALSE;
187 if (LP_MEXITS(lp))
188 /* Don't analyze if lp contains multiple exits. */
189 return TRUE;
190 if (!pastCounts[lp])
191 /* Loop not countable. */
192 return TRUE;
193 if (contains_alloc(lp))
194 /* Don't analyze if user-defined arrays are allocated. */
195 return FALSE;
196
197 /* Check for a disabling directive. */
198 open_pragma(FG_LINENO(LP_HEAD(lp)));
199 bx49 = (XBIT(49, 0x20000) != 0);
200 close_pragma();
201 if (bx49)
202 return TRUE;
203
204 /* Mark invariant ASTs within lp. */
205 invariant_nomotion(lp);
206
207 fgPre = fgPost = 0;
208
209 /* Hoist communication ASTs. */
210 hoist_comms(lp);
211
212 invariant_unmarkv();
213 return TRUE;
214 }
215
216 /* Return TRUE if loop #lp contains an ALLOCATE/DEALLOCATE statement of
217 * a user-defined array. */
218 static LOGICAL
contains_alloc(int lp)219 contains_alloc(int lp)
220 {
221 int fg;
222 int std, stdend;
223 int ast, sptr;
224
225 for (fg = LP_FG(lp); fg; fg = FG_NEXT(fg)) {
226 std = FG_STDFIRST(fg);
227 if (!std)
228 continue;
229 stdend = STD_NEXT(FG_STDLAST(fg));
230 for (; std != stdend; std = STD_NEXT(std)) {
231 ast = STD_AST(std);
232 if (A_TYPEG(ast) != A_ALLOC)
233 continue;
234 ast = A_SRCG(ast);
235 if (A_TYPEG(ast) == A_SUBSCR)
236 ast = A_LOPG(ast);
237 switch (A_TYPEG(ast)) {
238 case A_ID:
239 sptr = A_SPTRG(ast);
240 break;
241 case A_MEM:
242 sptr = A_SPTRG(A_MEMG(ast));
243 break;
244 default:
245 interr("contains_alloc: ID operand not found", lp, 4);
246 }
247 if (!CCSYMG(sptr))
248 return TRUE;
249 }
250 }
251 return FALSE;
252 }
253
254 /* Hoist invariant communication ASTs within loop #lp into a
255 * pre-header (and trailer) located at fgPre (and fgPost). */
256 static void
hoist_comms(int lp)257 hoist_comms(int lp)
258 {
259 int fg, fgtail, fgend;
260 int std, stdend, stdnext;
261 int ast;
262 int par;
263
264 bMovedComm = FALSE;
265 bMovedAssn = FALSE;
266 fgtail = LP_TAIL(lp);
267 fgend = FG_LNEXT(fgtail);
268 fg = LP_HEAD(lp);
269 par = STD_PAR(FG_STDFIRST(fg));
270 for (; fg != fgend; fg = FG_LNEXT(fg)) {
271 if (FG_LOOP(fg) != lp)
272 continue;
273 if (!is_dominator(fg, fgtail))
274 continue;
275 std = FG_STDFIRST(fg);
276 if (!std)
277 continue;
278 stdend = STD_NEXT(FG_STDLAST(fg));
279 stdnext = STD_NEXT(std);
280 for (; std != stdend; std = stdnext, stdnext = STD_NEXT(stdnext)) {
281 if (par != STD_PAR(std))
282 continue;
283 if (!STD_DELETE(std))
284 hoist_std(fg, std, lp);
285 }
286 }
287
288 if (!bMovedComm && !bMovedAssn)
289 return;
290
291 /* Clear the flags. */
292 std = FG_STDFIRST(fgPre);
293 if (std) {
294 stdend = STD_NEXT(FG_STDLAST(fgPre));
295 for (; std != stdend; std = STD_NEXT(std))
296 STD_MOVED(std) = FALSE;
297 }
298
299 if (bMovedComm && flg.hpf)
300 ccff_info(MSGFTN, "FTN012", 1, FG_LINENO(LP_HEAD(lp)),
301 "Invariant communication calls hoisted out of loop", NULL);
302 if (bMovedAssn)
303 ccff_info(MSGFTN, "FTN013", 1, FG_LINENO(LP_HEAD(lp)),
304 "Invariant assignments hoisted out of loop", NULL);
305 }
306
307 /* Return TRUE if the A_HALLOBNDS at allo_std is unique in lp. That is,
308 no other A_HALLOBNDS in the loop allocates/deallocates the same symbol. */
309 static LOGICAL
unique_allo(int allo_std,int allo_ft,int lp)310 unique_allo(int allo_std, int allo_ft, int lp)
311 {
312 int fg;
313 int std, stdend;
314 int ast, ft;
315
316 for (fg = LP_FG(lp); fg; fg = FG_NEXT(fg)) {
317 std = FG_STDFIRST(fg);
318 if (!std)
319 continue;
320 stdend = STD_NEXT(FG_STDLAST(fg));
321 for (; std != stdend; std = STD_NEXT(std)) {
322 if (std == allo_std)
323 continue;
324 ast = STD_AST(std);
325 if (A_TYPEG(ast) != A_HALLOBNDS)
326 continue;
327 ft = A_OPT1G(ast);
328 if (!ft)
329 continue;
330 if (FT_ALLOC_SPTR(ft) == FT_ALLOC_SPTR(allo_ft))
331 return FALSE;
332 }
333 }
334 return TRUE;
335 }
336
337 /* Hoist an invariant communication AST at STD std to fgPre. STD std occurs
338 * within node #fg. Set bMovedComm or bMovedAssn to TRUE when hoisting
339 * occurs. */
340 static void
hoist_std(int fg,int std,int lp)341 hoist_std(int fg, int std, int lp)
342 {
343 int ast, ast1, astcomm, astcont;
344 int ft;
345 int stdfree;
346 int nme;
347 int ndim, dim;
348 int asd;
349
350 if (!std)
351 return;
352
353 ast = STD_AST(std);
354
355 if (A_CONDG(ast) && !is_invariant(A_CONDG(ast)))
356 return;
357
358 if (A_TYPEG(ast) == A_ASN && A_TYPEG(A_DESTG(ast)) == A_ID
359 && STYPEG(A_SPTRG(A_DESTG(ast))) == ST_VAR) {
360 /* Hoist unique scalar assignments with invariant right-hand sides,
361 * which may be allocatable array bounds. */
362 nme = A_NMEG(A_DESTG(ast));
363 if (is_sym_invariant_safe(nme, lp) &&
364 check_outer_defs(std, FG_LOOP(fg), nme) &&
365 check_inner_uses(std, FG_LOOP(fg), nme) && is_invariant(A_SRCG(ast)) &&
366 is_invariant_base(nme)) {
367 invariant_mark(A_DESTG(ast), INV);
368 NME_STL(nme) = 0;
369 move_invar_std(std, fg);
370 bMovedAssn = TRUE;
371 return;
372 }
373 }
374
375 if (A_TYPEG(ast) == A_ASN)
376 astcomm = A_SRCG(ast);
377 else
378 astcomm = ast;
379 ft = A_OPT1G(astcomm);
380
381 switch (A_TYPEG(astcomm)) {
382 case A_HALLOBNDS:
383 if (!ft || !unique_allo(std, ft, lp) || !has_invar_subs(A_LOPG(astcomm)))
384 return;
385 move_invar_std(std, fg);
386 stdfree = mk_dealloc_stub(A_CONDG(ast));
387 FT_ALLOC_FREE(ft) = stdfree;
388 bMovedComm = TRUE;
389 return;
390 case A_HSECT:
391 if (!ft || !has_invar_subs(A_LOPG(astcomm)) ||
392 !check_moved(FT_SECT_ALLOC(ft)))
393 return;
394 move_invar_std(std, fg);
395 stdfree = mk_dealloc_stub(A_CONDG(ast));
396 FT_SECT_FREE(ft) = stdfree;
397 bMovedComm = TRUE;
398 return;
399 case A_HLOCALIZEBNDS:
400 case A_HCYCLICLP:
401 if (!ft || !is_invariant(A_ITRIPLEG(astcomm)))
402 return;
403 move_invar_std(std, fg);
404 bMovedComm = TRUE;
405 return;
406 case A_HCOPYSECT:
407 if (!ft || !has_invar_subs(A_SRCG(astcomm)) ||
408 !check_moved(FT_CCOPY_ALLOC(ft)) || !check_moved(FT_CCOPY_SECTL(ft)) ||
409 !check_moved(FT_CCOPY_SECTR(ft)))
410 return;
411 move_invar_std(std, fg);
412 stdfree = mk_dealloc_stub(A_CONDG(ast));
413 FT_CCOPY_FREE(ft) = stdfree;
414 bMovedComm = TRUE;
415 return;
416 case A_HCSTART:
417 assert(A_TYPEG(A_SRCG(astcomm)) == A_SUBSCR,
418 "hoist_std: source operand not subscript", ast, 4);
419 assert(A_TYPEG(A_DESTG(astcomm)) == A_SUBSCR,
420 "hoist_std: dest operand not subscript", ast, 4);
421 if (!ft || !is_invariant(A_SRCG(astcomm)) ||
422 !is_invariant(A_DESTG(astcomm)) || !check_moved(FT_CSTART_COMM(ft)) ||
423 !check_moved(FT_CSTART_SECTL(ft)) || !check_moved(FT_CSTART_SECTR(ft)))
424 return;
425 move_invar_std(std, fg);
426 stdfree = mk_dealloc_stub(A_CONDG(ast));
427 FT_CSTART_FREE(ft) = stdfree;
428 bMovedComm = TRUE;
429 FT_CSTART_INVMVD(ft) = 1;
430 return;
431 case A_HOVLPSHIFT:
432 if (!ft || !has_invar_subs(A_SRCG(astcomm)) ||
433 (FT_SHIFT_BOUNDARY(ft) && !is_invariant(FT_SHIFT_BOUNDARY(ft))))
434 return;
435 move_invar_std(std, fg);
436 stdfree = mk_dealloc_stub(A_CONDG(ast));
437 FT_SHIFT_FREE(ft) = stdfree;
438 bMovedComm = TRUE;
439 return;
440 case A_HSCATTER:
441 case A_HGATHER:
442 if (!ft)
443 return;
444 ndim = ASD_NDIM(A_ASDG(FT_CGATHER_VSUB(ft)));
445 if (!has_invar_subs(FT_CGATHER_VSUB(ft)) ||
446 !has_invar_subs(FT_CGATHER_NVSUB(ft)) ||
447 (FT_CGATHER_MASK(ft) && !is_invariant(FT_CGATHER_MASK(ft))) ||
448 !is_invariant_list(ndim, &FT_CGATHER_V(ft, 0)) ||
449 !check_moved(FT_CGATHER_SECTVSUB(ft)) ||
450 !check_moved(FT_CGATHER_SECTNVSUB(ft)) ||
451 !check_moved(FT_CGATHER_SECTM(ft)) ||
452 !check_moved_list(ndim, &FT_CGATHER_SECTV(ft, 0)))
453 return;
454 move_invar_std(std, fg);
455 stdfree = mk_dealloc_stub(A_CONDG(ast));
456 FT_CGATHER_FREE(ft) = stdfree;
457 bMovedComm = TRUE;
458 return;
459 case A_HGETSCLR:
460 if (!is_invariant(A_SRCG(astcomm)))
461 return;
462 move_invar_std(std, fg);
463 bMovedComm = TRUE;
464 return;
465 case A_HOWNERPROC:
466 ast1 = A_LOPG(astcomm);
467 assert(A_TYPEG(ast1) == A_SUBSCR, "hoist_std: missing array ref", astcomm,
468 4);
469 asd = A_ASDG(ast1);
470 dim = CONVAL2G(A_SPTRG(A_DIMG(astcomm)));
471 if (!is_invariant(ASD_SUBS(asd, dim)))
472 return;
473 move_invar_std(std, fg);
474 bMovedComm = TRUE;
475 return;
476 default:
477 return;
478 }
479 }
480
481 /* Return TRUE if every definition of nme that is not at std occurs in
482 * a parent of loop lp. */
483 static LOGICAL
check_outer_defs(int std,int lp,int nme)484 check_outer_defs(int std, int lp, int nme)
485 {
486 int def;
487 int lpo;
488
489 for (def = NME_DEF(nme); def; def = DEF_NEXT(def)) {
490 if (DEF_STD(def) == std)
491 continue;
492 if (is_parent_loop(lp, FG_LOOP(DEF_FG(def))))
493 return FALSE;
494 }
495 return TRUE;
496 }
497
498 /* Return TRUE if every use of nme within loop lp is not reached by
499 * a def of nme other than the def at STD std. */
500 static LOGICAL
check_inner_uses(int std,int lp,int nme)501 check_inner_uses(int std, int lp, int nme)
502 {
503 int def;
504 DU *du;
505 int use;
506
507 for (def = NME_DEF(nme); def; def = DEF_NEXT(def)) {
508 if (DEF_STD(def) == std)
509 continue;
510 for (du = DEF_DU(def); du; du = du->next) {
511 use = du->use;
512 if (is_parent_loop(lp, FG_LOOP(USE_FG(use))))
513 return FALSE;
514 }
515 }
516 return TRUE;
517 }
518
519 /*
520 * return FALSE if this NME is for a BASED symbol, and the
521 * base pointer (from MIDNUM) is not already marked invariant
522 */
523 static LOGICAL
is_invariant_base(int nme)524 is_invariant_base(int nme)
525 {
526 int sym;
527 sym = NME_SYM(nme);
528 if (SCG(sym) == SC_BASED && MIDNUMG(sym) > NOSYM &&
529 !is_invariant(mk_id(MIDNUMG(sym))))
530 return FALSE;
531 return TRUE;
532 } /* is_invariant_base */
533
534 /* Return TRUE if lpParent is a parent loop of lpChild, or if they are
535 * identical. */
536 static LOGICAL
is_parent_loop(int lpParent,int lpChild)537 is_parent_loop(int lpParent, int lpChild)
538 {
539 int lpo;
540
541 for (lpo = lpChild; lpo; lpo = LP_PARENT(lpo))
542 if (lpo == lpParent)
543 return TRUE;
544 return FALSE;
545 }
546
547 /* Return TRUE if the subscript expressions of AST ast are all invariant. */
548 static LOGICAL
has_invar_subs(int ast)549 has_invar_subs(int ast)
550 {
551 int asd;
552 int ndims, sub;
553
554 if (!ast)
555 return TRUE;
556
557 if (A_TYPEG(ast) == A_ID) {
558 assert(A_SHAPEG(ast), "has_invar_subs: ast has no shape", ast, 4);
559 return TRUE;
560 }
561 while (A_TYPEG(ast) != A_ID) {
562 switch (A_TYPEG(ast)) {
563 case A_SUBSCR:
564 asd = A_ASDG(ast);
565 ndims = ASD_NDIM(asd);
566 for (sub = 0; sub < ndims; sub++) {
567 if (!is_invariant(ASD_SUBS(asd, sub)))
568 return FALSE;
569 }
570 ast = A_LOPG(ast);
571 break;
572 case A_MEM:
573 ast = A_PARENTG(ast);
574 break;
575 default:
576 interr("reference not ID,SUBSCR,MEM", ast, 4);
577 }
578 }
579 return TRUE;
580 }
581
582 /* Return TRUE if every AST in vast[0], ..., vast[n-1] is invariant. */
583 static LOGICAL
is_invariant_list(int n,int vast[])584 is_invariant_list(int n, int vast[])
585 {
586 int i;
587
588 for (i = 0; i < n; i++)
589 if (vast[i] && !is_invariant(vast[i]))
590 return FALSE;
591 return TRUE;
592 }
593
594 /* Return TRUE if every STD in vstd[0], ..., vstd[n-1] has been moved. */
595 static LOGICAL
check_moved_list(int n,int vstd[])596 check_moved_list(int n, int vstd[])
597 {
598 int i;
599
600 for (i = 0; i < n; i++)
601 if (!check_moved(vstd[i]))
602 return FALSE;
603 return TRUE;
604 }
605
606 /* Return TRUE if std has been moved. */
607 static LOGICAL
check_moved(int std)608 check_moved(int std)
609 {
610 if (!std)
611 return TRUE;
612 if (STD_DELETE(std))
613 return FALSE;
614 return STD_MOVED(std) != 0;
615 }
616
617 /* Move the invariant AST at STD #std within node #fg to the last statement
618 * in the preheader of fg's loop. Set the std's MOVED flag. */
619 static void
move_invar_std(int std,int fg)620 move_invar_std(int std, int fg)
621 {
622 int stdprev;
623 int astCont, astStmt, astCond;
624
625 mk_loop_hdtl(FG_LOOP(fg));
626
627 rdilts(fg);
628 stdprev = STD_PREV(std);
629 if (STD_LABEL(std)) {
630 astCont = mk_stmt(A_CONTINUE, 0);
631 stdprev = add_stmt_after(astCont, stdprev);
632 STD_LABEL(stdprev) = STD_LABEL(std);
633 STD_LABEL(std) = 0;
634 STD_LINENO(stdprev) = STD_LINENO(std);
635 }
636 STD_NEXT(stdprev) = STD_NEXT(std);
637 STD_PREV(STD_NEXT(std)) = stdprev;
638 wrilts(fg);
639
640 rdilts(fgPre);
641 stdprev = STD_LAST;
642 STD_NEXT(stdprev) = std;
643 STD_PREV(std) = stdprev;
644 STD_NEXT(std) = 0;
645 STD_LAST = std;
646 wrilts(fgPre);
647
648 STD_MOVED(std) = TRUE;
649 astStmt = STD_AST(std);
650 astCond = mk_count_test(A_CONDG(astStmt), pastCounts[FG_LOOP(fg)]);
651 A_CONDP(astStmt, astCond);
652 /*
653 * This is where fgPost needs be associated with astCond & saved
654 * in a data strucutre for mk_ztrips(int lp). Problably need to
655 * repurpose A_COND.
656 fprintf(STDERR,
657 "XXX lp:%d, fgPre:%d, fgPost:%d, fgPost_stdfirst:%d\n",
658 FG_LOOP(fg), fgPre, fgPost, FG_STDFIRST(fgPost));
659 */
660 }
661
662 /* If necessary create new preheader and trailer nodes for loop #lp,
663 * and set fgPre & fgPost to these nodes. */
664 static void
mk_loop_hdtl(int lp)665 mk_loop_hdtl(int lp)
666 {
667 int ast;
668 int std;
669
670 if (fgPre)
671 return;
672
673 fgPre = add_fg(FG_LPREV(LP_HEAD(lp)));
674 opt.pre_fg = fgPre;
675 FG_FT(fgPre) = TRUE;
676 std = FG_STDFIRST(fgPre);
677 if (!std) {
678 /* Node empty; add a CONTINUE statement. */
679 rdilts(fgPre);
680 ast = mk_stmt(A_CONTINUE, 0);
681 std = add_stmt_after(ast, 0);
682 wrilts(fgPre);
683 }
684 FG_LINENO(fgPre) = STD_LINENO(std) = FG_LINENO(LP_HEAD(lp));
685 add_loop_preheader(lp);
686
687 add_single_loop_exit(lp);
688 fgPost = FG_LNEXT(LP_TAIL(lp));
689 }
690
691 /** \brief If necessary create new preheader and trailer nodes for loop \#lp,
692 and set fgPre & fgPost to these nodes. */
693 void
add_loop_hd(int lp)694 add_loop_hd(int lp)
695 {
696 int ast;
697 int std;
698
699 fgPre = add_fg(FG_LPREV(LP_HEAD(lp)));
700 opt.pre_fg = fgPre;
701 FG_FT(fgPre) = TRUE;
702 std = FG_STDFIRST(fgPre);
703 if (!std) {
704 /* Node empty; add a CONTINUE statement. */
705 rdilts(fgPre);
706 ast = mk_stmt(A_CONTINUE, 0);
707 std = add_stmt_after(ast, 0);
708 wrilts(fgPre);
709 }
710
711 add_loop_preheader(lp);
712 }
713
714 /* Augment the current conjunction of count tests, astCond, with a new test
715 * that the loop count, astCount, is greater than 0. */
716 static int
mk_count_test(int astCond,int astCount)717 mk_count_test(int astCond, int astCount)
718 {
719 int ast, astNewCond;
720
721 assert(astCount, "mk_count_test: loop not countable", 0, 4);
722 if (A_TYPEG(astCount) == A_CNST)
723 return astCond;
724 ast = mk_binop(OP_GT, astCount, astb.i0, DT_LOG);
725 if (astCond)
726 astNewCond = mk_binop(OP_LAND, astCond, ast, DT_LOG);
727 else
728 astNewCond = ast;
729 return astNewCond;
730 }
731
732 /* Create a CONTINUE statement, with COND field astCond,
733 * in node fgPost, and return the STD. */
734 static int
mk_dealloc_stub(int astCond)735 mk_dealloc_stub(int astCond)
736 {
737 int ast = mk_stmt(A_CONTINUE, 0);
738 int std;
739
740 A_CONDP(ast, astCond);
741 rdilts(fgPost);
742 std = add_stmt_after(ast, 0);
743 wrilts(fgPost);
744 STD_LINENO(std) = FG_LINENO(fgPost);
745 return std;
746 }
747
748 /*
749 * Create zero-trip tests around hoisted communication statements within
750 * loop lp.
751 */
752 static void
mk_ztrips(int lp)753 mk_ztrips(int lp)
754 {
755 int lpi;
756 int fg;
757 int std, stdend;
758 int ast, astCond, astNewCond;
759 int *pastConds = NULL;
760 int maxconds = opt.nloops + 1;
761 int nconds;
762
763 for (lpi = LP_CHILD(lp); lpi; lpi = LP_SIBLING(lpi))
764 mk_ztrips(lpi);
765
766 NEW(pastConds, int, maxconds);
767 for (fg = LP_FG(lp); fg; fg = FG_NEXT(fg)) {
768 nconds = 0;
769 std = FG_STDFIRST(fg);
770 if (!std)
771 continue;
772 stdend = STD_NEXT(FG_STDLAST(fg));
773 for (; std != stdend; std = STD_NEXT(std)) {
774 astCond = A_CONDG(STD_AST(std));
775 astNewCond = astCond;
776 for (; nconds; nconds--) {
777 if (astCond)
778 astNewCond = remove_cond(astCond, pastConds[nconds - 1]);
779 else
780 astNewCond = astCond;
781 if (astNewCond != astCond)
782 /* ...new condition contained in old. */
783 break;
784 /* ...new condition not in old, so terminate old condition. */
785 ast = mk_stmt(A_ENDIF, 0);
786 add_stmt_before(ast, std);
787 }
788 if (!astCond || !astNewCond)
789 continue;
790 ast = mk_stmt(A_IFTHEN, 0);
791 A_IFEXPRP(ast, astNewCond);
792 add_stmt_before(ast, std);
793 pastConds[nconds++] = astCond;
794 assert(nconds <= opt.nloops, "mk_ztrips: too many conditions", lp, 4);
795 }
796 /*
797 * f20730 - hoisting of invariant assignments is suboptimal for
798 * reaching defs. Hoisting an invariant assignment from a loop
799 * occurs as follows:
800 *
801 * the loop
802 * ---------
803 * do __the_loop__
804 * XX = __invariant_expression__
805 * __work__ << uses XX>
806 * enddo
807 *
808 * the hoist
809 * ---------
810 * if (zero-trip-test) then
811 * XX = __invariant_expression__
812 * endif
813 * do __the_loop__
814 * __work__ <<< uses XX>>>
815 * enddo
816 *
817 * this needs to be
818 * ----------------
819 * if (zero-trip-test) then
820 * XX = __invariant_expression__
821 * do __the_loop__ !!! and somehow elide the backend's ZT
822 * __work__ << uses XX>
823 * enddo
824 * endif
825 *
826 * THE PROBLEM
827 * -----------
828 * IF there exists a def of XX prior to the original loop, that def
829 * now reaches the XX within the transformed loop (the hoisted
830 * assignment is now guarded). Without the hoisting, XX was killed
831 * by the def of XX in the loop. This can lead to false uses of
832 * XX -- for WRF, this was especially bad given that the XX was
833 * considered a live-out of a loop, which inhibited vectorizing
834 * that loop.
835 *
836 * To correctly place the ENDIF, move_invar_std() needs to associate
837 * A_COND with fgPost (FG_STDFIRST(fgPost) would be the correct
838 * insert point for the ENDIF.
839 *
840 * AT THIS TIME, it is not be worth the effort -- the backend will
841 * still hoist the RHS within the correct zero-trip context.
842 */
843 for (; nconds; nconds--) {
844 ast = mk_stmt(A_ENDIF, 0);
845 add_stmt_before(ast, std);
846 }
847 }
848 FREE(pastConds);
849 }
850
851 /* Remove conjunction astSrc from conjunction astTarg. If astSrc not in
852 * astTarg, return astTarg. If astSrc = astTarg, return 0. */
853 static int
remove_cond(int astTarg,int astSrc)854 remove_cond(int astTarg, int astSrc)
855 {
856 int astNewl, astNewr, astNew;
857
858 if (astSrc == astTarg)
859 return 0;
860 if (A_TYPEG(astTarg) != A_BINOP || A_OPTYPEG(astTarg) != OP_LAND)
861 return astTarg;
862 astNewl = remove_cond(A_LOPG(astTarg), astSrc);
863 if (!astNewl) {
864 astNewr = remove_cond(A_ROPG(astTarg), astSrc);
865 return astNewr;
866 }
867 astNewr = remove_cond(A_ROPG(astTarg), astSrc);
868 if (!astNewr) {
869 astNewl = remove_cond(A_LOPG(astTarg), astSrc);
870 return astNewl;
871 }
872 if (astNewl == A_LOPG(astTarg) && astNewr == A_ROPG(astTarg))
873 astNew = astTarg;
874 else
875 astNew = mk_binop(OP_LAND, astNewl, astNewr, DT_LOG);
876 return astNew;
877 }
878