1 /*
2 * Copyright (c) 2007-2018, 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 /** \file
19 \brief Use the pointer analysis Determine when pointers point to aligned
20 memory, or contiguous memory, or leftmost-stride-1 memory. Save
21 flow-insensitive pointer target information for use by the back end
22 */
23
24 #include "gbldefs.h"
25 #include "global.h"
26 #include "optimize.h"
27 #include "symtab.h"
28 #include "nme.h"
29 #include "ast.h"
30 #include "gramtk.h"
31 #include "pd.h"
32 #include "extern.h"
33
34 static FILE *dfile = NULL;
35
36 /*
37 * should _findrefs look at pointer A_ID as a pointer dereference?
38 */
39 static int deref = 1;
40
41 /*
42 * keep a linked list of symbols we've visited,
43 * whether we've seen a non-quad-aligned dereference of this symbol,
44 * whether we've seen a non-stride-1 dereference of this symbol
45 */
46 typedef struct INFO {
47 int next;
48 int flags;
49 int fistptr;
50 } INFO;
51 static INFO *info = NULL;
52 static int first = 0, count = 0;
53
54 #define INFO_QALN 0x1
55 #define INFO_NON_QALN 0x2
56 #define INFO_STRIDE1 0x4
57 #define INFO_NON_STRIDE1 0x8
58 #define INFO_TARGET 0x10
59 #define INFO_UNK_TARGET 0x20
60
61 #define SEEN_QALN(sptr) (info[sptr].flags & INFO_QALN)
62 #define SEEN_NON_QALN(sptr) (info[sptr].flags & INFO_NON_QALN)
63 #define SEEN_STRIDE1(sptr) (info[sptr].flags & INFO_STRIDE1)
64 #define SEEN_NON_STRIDE1(sptr) (info[sptr].flags & INFO_NON_STRIDE1)
65 #define SEEN_TARGET(sptr) (info[sptr].flags & INFO_TARGET)
66 #define SEEN_UNK_TARGET(sptr) (info[sptr].flags & INFO_UNK_TARGET)
67
68 #define SET_QALN(sptr) info[sptr].flags |= INFO_QALN
69 #define SET_NON_QALN(sptr) info[sptr].flags |= INFO_NON_QALN
70 #define SET_STRIDE1(sptr) info[sptr].flags |= INFO_STRIDE1
71 #define SET_NON_STRIDE1(sptr) info[sptr].flags |= INFO_NON_STRIDE1
72 #define SET_TARGET(sptr) info[sptr].flags |= INFO_TARGET
73 #define SET_UNK_TARGET(sptr) info[sptr].flags |= INFO_UNK_TARGET
74
75 /*
76 * save Flow-InSensitive pointer-Target information (FIST)
77 */
78 typedef struct FIST {
79 int next;
80 int ttype, tid; /* target type, target identifier */
81 } FIST;
82
83 static struct {
84 FIST *stg_base;
85 int stg_avail, stg_size;
86 } fist = {NULL, 0, 0};
87
88 #define FIST_UNK 1
89 #define FIST_LDYN 2
90 #define FIST_GDYN 3
91 #define FIST_NLOC 4
92 #define FIST_PSYM 5
93 #define FIST_ISYM 6
94
95 #define FIST_TYPE(i) fist.stg_base[i].ttype
96 #define FIST_ID(i) fist.stg_base[i].tid
97 #define FIST_NEXT(i) fist.stg_base[i].next
98
99 /*
100 * save list of FIST for some symbols;
101 */
102 typedef struct FISTLIST {
103 int sptr, fistptr;
104 } FISTLIST;
105
106 #define FLIST_SPTR(i) fistlist.stg_base[i].sptr
107 #define FLIST_PTR(i) fistlist.stg_base[i].fistptr
108
109 static struct {
110 FISTLIST *stg_base;
111 int stg_avail, stg_size;
112 } fistlist = {NULL, 0, 0};
113
114 /*
115 * determine whether we have pointer target info for this
116 * symbol at this statement; if so, merge that into what we have
117 */
118 static void
do_targets(int stdx,int sptr)119 do_targets(int stdx, int sptr)
120 {
121 if (!SEEN_UNK_TARGET(sptr)) {
122 int c, t, tag, tid;
123 c = 0;
124 while (pta_target(stdx, sptr, &tag, &tid)) {
125 int t;
126 ++c;
127 if (tag == FIST_UNK) {
128 #if DEBUG
129 if (DBGBIT(10, 0x200000)) {
130 fprintf(gbl.dbgfil, " set UNKTARGET for %d:%s at std %d\n", sptr,
131 SYMNAME(sptr), stdx);
132 }
133 #endif
134 SET_UNK_TARGET(sptr);
135 return;
136 }
137 for (t = info[sptr].fistptr; t; t = FIST_NEXT(t)) {
138 if (FIST_TYPE(t) == tag && FIST_ID(t) == tid)
139 break;
140 }
141 if (!t) {
142 t = fist.stg_avail++;
143 OPT_NEED(fist, FIST, 100);
144 FIST_TYPE(t) = tag;
145 FIST_ID(t) = tid;
146 FIST_NEXT(t) = info[sptr].fistptr;
147 info[sptr].fistptr = t;
148 }
149 }
150 if (c) {
151 SET_TARGET(sptr);
152 } else {
153 SET_UNK_TARGET(sptr);
154 #if DEBUG
155 if (DBGBIT(10, 0x200000)) {
156 fprintf(gbl.dbgfil, " set UNKTARGET (no targets) for %d:%s at std %d\n",
157 sptr, SYMNAME(sptr), stdx);
158 }
159 #endif
160 }
161 }
162 } /* do_targets */
163
164 /*
165 * analyze one symbol referenced in this statement
166 */
167 static void
analyze(int sptr,int stdx)168 analyze(int sptr, int stdx)
169 {
170 if (sptr && deref) {
171 switch (STYPEG(sptr)) {
172 case ST_VAR:
173 case ST_ARRAY:
174 if (ALLOCATTRG(sptr)) {
175 /* allocatables are always aligned */
176 if (!VISITG(sptr)) {
177 info[sptr].flags = 0;
178 info[sptr].fistptr = 0;
179 info[sptr].next = first;
180 first = sptr;
181 VISITP(sptr, 1);
182 }
183 SET_QALN(sptr);
184 SET_STRIDE1(sptr);
185 if (XBIT(53, 2))
186 do_targets(stdx, sptr);
187 } else if (deref && POINTERG(sptr) && XBIT(53, 2)) {
188 #if DEBUG
189 if (DBGBIT(10, 0x200000)) {
190 fprintf(dfile, "--deref=%d sptr=%d:%s std=%d ", deref, sptr,
191 SYMNAME(sptr), stdx);
192 printast(STD_AST(stdx));
193 fprintf(dfile, "\n");
194 putstdpta(stdx);
195 }
196 #endif
197 if (!VISITG(sptr)) {
198 info[sptr].flags = 0;
199 info[sptr].fistptr = 0;
200 info[sptr].next = first;
201 first = sptr;
202 VISITP(sptr, 1);
203 }
204 if (!SEEN_NON_QALN(sptr)) {
205 if (pta_aligned(stdx, sptr)) {
206 SET_QALN(sptr);
207 } else {
208 SET_NON_QALN(sptr);
209 }
210 }
211 if (!SEEN_NON_STRIDE1(sptr)) {
212 if (pta_stride1(stdx, sptr)) {
213 SET_STRIDE1(sptr);
214 } else {
215 SET_NON_STRIDE1(sptr);
216 }
217 }
218 if (XBIT(53, 2))
219 do_targets(stdx, sptr);
220 }
221 break;
222 case ST_MEMBER:
223 if (ALLOCATTRG(sptr)) {
224 /* allocatables are always aligned */
225 if (!VISITG(sptr)) {
226 info[sptr].flags = 0;
227 info[sptr].fistptr = 0;
228 info[sptr].next = first;
229 first = sptr;
230 VISITP(sptr, 1);
231 }
232 SET_QALN(sptr);
233 SET_STRIDE1(sptr);
234 }
235 else if (deref && POINTERG(sptr) && XBIT(53, 2)) {
236 if (!VISITG(sptr)) {
237 info[sptr].flags = 0;
238 info[sptr].fistptr = 0;
239 info[sptr].next = first;
240 first = sptr;
241 VISITP(sptr, 1);
242 }
243 if (!SEEN_NON_QALN(sptr)) {
244 if (pta_aligned(stdx, sptr)) {
245 SET_QALN(sptr);
246 } else {
247 SET_NON_QALN(sptr);
248 }
249 }
250 if (!SEEN_NON_STRIDE1(sptr)) {
251 if (pta_stride1(stdx, sptr)) {
252 SET_STRIDE1(sptr);
253 } else {
254 SET_NON_STRIDE1(sptr);
255 }
256 }
257 if (XBIT(53, 2))
258 do_targets(stdx, sptr);
259 }
260 break;
261 default:;
262 }
263 }
264 } /* analyze */
265
266 /*
267 * recursive, depth-first (parent, then all children) traversal of expression
268 * tree.
269 * special handling for some types of expressions, like procedure calls.
270 */
271 static int
_findrefs(int astx,int * pstdx)272 _findrefs(int astx, int *pstdx)
273 {
274 int savederef;
275 int sptr;
276 int asd, ndim, i;
277 int args, argcnt, a;
278
279 savederef = deref;
280
281 switch (A_TYPEG(astx)) {
282 case A_ID:
283 analyze(A_SPTRG(astx), *pstdx);
284 break;
285 case A_ALLOC:
286 /* the object being allocated/deallocated is not interesting */
287 deref = 0;
288 ast_traverse(A_SRCG(astx), _findrefs, NULL, pstdx);
289 /* the status, if given, is interesting */
290 deref = 1;
291 if (A_LOPG(astx))
292 ast_traverse(A_LOPG(astx), _findrefs, NULL, pstdx);
293 deref = savederef;
294 return 1;
295 case A_SUBSCR:
296 ast_traverse(A_LOPG(astx), _findrefs, NULL, pstdx);
297 /* all subscripts are interesting */
298 asd = A_ASDG(astx);
299 ndim = ASD_NDIM(asd);
300 deref = 1;
301 for (i = 0; i < ndim; ++i)
302 ast_traverse(ASD_SUBS(asd, i), _findrefs, NULL, pstdx);
303 deref = savederef;
304 return 1;
305 case A_SUBSTR:
306 ast_traverse(A_LOPG(astx), _findrefs, NULL, pstdx);
307 /* all substring arguments are interesting */
308 deref = 1;
309 if (A_LEFTG(astx))
310 ast_traverse(A_LEFTG(astx), _findrefs, NULL, pstdx);
311 if (A_RIGHTG(astx))
312 ast_traverse(A_RIGHTG(astx), _findrefs, NULL, pstdx);
313 deref = savederef;
314 return 1;
315 case A_ICALL:
316 /* intrinsic call, see if it is ptr assignment */
317 if (A_OPTYPEG(astx) == I_PTR2_ASSIGN) {
318 /* pointer assignment, 1st argument is not interesting */
319 args = A_ARGSG(astx);
320 deref = 0;
321 ast_traverse(ARGT_ARG(args, 0), _findrefs, NULL, pstdx);
322 deref = 1;
323 ast_traverse(ARGT_ARG(args, 1), _findrefs, NULL, pstdx);
324 deref = savederef;
325 return 1;
326 } else if (A_OPTYPEG(astx) == I_NULLIFY) {
327 /* pointer nullify */
328 args = A_ARGSG(astx);
329 deref = 0;
330 ast_traverse(ARGT_ARG(args, 0), _findrefs, NULL, pstdx);
331 deref = savederef;
332 return 1;
333 }
334 break;
335 case A_CALL:
336 case A_FUNC:
337 /* look at any expression arguments */
338 args = A_ARGSG(astx);
339 argcnt = A_ARGCNTG(astx);
340 for (a = 0; a < argcnt; ++a) {
341 deref = 0;
342 ast_traverse(ARGT_ARG(args, a), _findrefs, NULL, pstdx);
343 }
344 deref = savederef;
345 return 1;
346 }
347
348 deref = 1;
349 return 0;
350 } /* _findrefs */
351
352 /*
353 * go through all statements, visit all expressions
354 * for any expression, find references to any pointers.
355 * determine whether any of those references might NOT be to
356 * aligned memory, or contiguous memory, or leftmost-stride-1 memory.
357 */
358 void
pstride_analysis(void)359 pstride_analysis(void)
360 {
361 int stdx, astx, sptr;
362 #if DEBUG
363 dfile = gbl.dbgfil ? gbl.dbgfil : stderr;
364 #endif
365 NEW(info, INFO, stb.stg_avail);
366 if (XBIT(53, 2)) {
367 points_to(); /* pointsto.c */
368 OPT_ALLOC(fist, FIST, 100);
369 fist.stg_avail = 1;
370 }
371 first = 0;
372 for (sptr = stb.firstosym; sptr < stb.stg_avail; ++sptr)
373 VISITP(sptr, 0);
374 #if DEBUG
375 if (DBGBIT(10, 0x400000)) {
376 dstdpa();
377 }
378 #endif
379 /* go through all statements, go through all expressions */
380 for (stdx = STD_NEXT(0); stdx != 0; stdx = STD_NEXT(stdx)) {
381 astx = STD_AST(stdx);
382 ast_visit(1, 1);
383 ast_traverse(astx, _findrefs, NULL, &stdx);
384 ast_unvisit();
385 }
386 if (XBIT(53, 2)) {
387 f90_fini_pointsto(); /* pointsto.c */
388 }
389 count = 0;
390 for (sptr = first; sptr > 0; sptr = info[sptr].next) {
391 int ptr, sdsc;
392 VISITG(sptr) = 0;
393 if (SEEN_QALN(sptr) && !SEEN_NON_QALN(sptr)) {
394 ptr = MIDNUMG(sptr);
395 if (ptr)
396 TQALNP(ptr, 1);
397 }
398 if (SEEN_STRIDE1(sptr) && !SEEN_NON_STRIDE1(sptr)) {
399 SDSCS1P(sptr, 1);
400 sdsc = SDSCG(sptr);
401 if (sdsc)
402 SDSCS1P(sdsc, 1);
403 }
404 if (SEEN_TARGET(sptr) && !SEEN_UNK_TARGET(sptr)) {
405 ++count;
406 }
407 #if DEBUG
408 if (DBGBIT(10, 0x200000)) {
409 dsym(sptr);
410 }
411 #endif
412 }
413 if (XBIT(53, 2) && count) {
414 OPT_ALLOC(fistlist, FISTLIST, count + 1);
415 fistlist.stg_avail = 1;
416 for (sptr = first; sptr > 0; sptr = info[sptr].next) {
417 int ptr, sdsc;
418 if (SEEN_TARGET(sptr) && !SEEN_UNK_TARGET(sptr)) {
419 FLIST_SPTR(fistlist.stg_avail) = sptr;
420 FLIST_PTR(fistlist.stg_avail) = info[sptr].fistptr;
421 #if DEBUG
422 if (DBGBIT(10, 0x200000)) {
423 int t;
424 fprintf(gbl.dbgfil, "FIS targets for %s :", SYMNAME(sptr));
425 for (t = FLIST_PTR(fistlist.stg_avail); t; t = FIST_NEXT(t)) {
426 switch (FIST_TYPE(t)) {
427 case FIST_UNK:
428 fprintf(gbl.dbgfil, " unk");
429 break;
430 case FIST_LDYN:
431 fprintf(gbl.dbgfil, " ldyn(%d)", FIST_ID(t));
432 break;
433 case FIST_GDYN:
434 fprintf(gbl.dbgfil, " gdyn(%d)", FIST_ID(t));
435 break;
436 case FIST_NLOC:
437 fprintf(gbl.dbgfil, " nloc(%d)", FIST_ID(t));
438 break;
439 case FIST_PSYM:
440 fprintf(gbl.dbgfil, " %d:%s", FIST_ID(t), SYMNAME(FIST_ID(t)));
441 break;
442 case FIST_ISYM:
443 fprintf(gbl.dbgfil, " %d:%s?", FIST_ID(t), SYMNAME(FIST_ID(t)));
444 break;
445 default:
446 fprintf(gbl.dbgfil, " ??%d", FIST_ID(t));
447 break;
448 }
449 }
450 fprintf(gbl.dbgfil, "\n");
451 }
452 #endif
453 ++fistlist.stg_avail;
454 }
455 }
456 }
457 FREE(info);
458 first = 0;
459 count = 0;
460 } /* pstride_analysis */
461
462 /*
463 * put any discovered flow-insensitive pointer target information
464 * out to the information file
465 */
466 void
lower_pstride_info(FILE * lowerfile)467 lower_pstride_info(FILE *lowerfile)
468 {
469 int f, t, sptr;
470 if (fistlist.stg_base == NULL || fist.stg_base == NULL) {
471 return;
472 }
473 for (f = 1; f < fistlist.stg_avail; ++f) {
474 for (t = FLIST_PTR(f); t; t = FIST_NEXT(t)) {
475 sptr = FLIST_SPTR(f);
476 if (sptr && MIDNUMG(sptr)) {
477 switch (FIST_TYPE(t)) {
478 case FIST_UNK:
479 default:
480 fprintf(lowerfile, "info:%d T type:1 id:0\n", MIDNUMG(sptr));
481 break;
482 case FIST_LDYN:
483 fprintf(lowerfile, "info:%d T type:2 id:%d\n", MIDNUMG(sptr),
484 FIST_ID(t));
485 break;
486 case FIST_GDYN:
487 fprintf(lowerfile, "info:%d T type:3 id:%d\n", MIDNUMG(sptr),
488 FIST_ID(t));
489 break;
490 case FIST_NLOC:
491 fprintf(lowerfile, "info:%d T type:4 id:%d\n", MIDNUMG(sptr),
492 FIST_ID(t));
493 break;
494 case FIST_PSYM:
495 fprintf(lowerfile, "info:%d T type:5 id:%d\n", MIDNUMG(sptr),
496 FIST_ID(t));
497 break;
498 case FIST_ISYM:
499 fprintf(lowerfile, "info:%d T type:6 id:%d\n", MIDNUMG(sptr),
500 FIST_ID(t));
501 break;
502 }
503 }
504 }
505 }
506 } /* lower_pstride_info */
507
508 void
fini_pstride_analysis(void)509 fini_pstride_analysis(void)
510 {
511 if (fist.stg_base) {
512 OPT_FREE(fist);
513 fist.stg_size = 0;
514 fist.stg_avail = 0;
515 }
516 if (fistlist.stg_base) {
517 OPT_FREE(fistlist);
518 fistlist.stg_size = 0;
519 fistlist.stg_avail = 0;
520 }
521 } /* fini_pstride_analysis */
522