1 /*
2 * Copyright (c) 1993-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 C and Fortran BIH utility module
20 */
21
22 #include "bihutil.h"
23 #include "error.h"
24 #include "global.h"
25 #include "symtab.h"
26 #include "ilm.h"
27 #include "fih.h"
28 #include "ili.h"
29 #include "expand.h"
30 #include "regutil.h"
31 #include "machreg.h"
32
33 extern int getcon();
34 extern int mkfunc();
35
36 extern void rdilts();
37 extern void wrilts();
38
39 #define MAXBIH 67108864
40
41 /** \brief Initialize BIH area
42 */
43 void
bih_init(void)44 bih_init(void)
45 {
46 STG_ALLOC(bihb, 128);
47 STG_SET_FREELINK(bihb, BIH, next);
48 BIH_LPCNTFROM(0) = 0;
49 BIH_NEXT(bihb.stg_size - 1) = 0;
50 BIH_FLAGS(0) = 0;
51 BIH_NEXT(0) = 0;
52 BIH_PREV(0) = 0;
53 BIH_AVLPCNT(0) = 0;
54 BIH_GUARDEE(0) = 0;
55 BIH_GUARDER(0) = 0;
56 #ifdef BIH_FTAG
57 BIH_FTAG(0) = 0;
58 BIH_FINDEX(0) = 0;
59 BIH_LINENO(0) = 0;
60 BIH_ASM(0) = 0;
61 #endif
62 bihb.stg_max = 0;
63 #if DEBUG
64 assert(((char *)&BIH_BLKCNT(0) - (char *)&bihb.stg_base[0]) % 8 == 0,
65 "offset of BIH_BLKCNT must be a multiple of 8", 0, ERR_Fatal);
66 assert(sizeof(BIH) % 8 == 0, "size of BIH must be a multiple of 8", 0, ERR_Fatal);
67 #endif
68 }
69
70 void
bih_cleanup()71 bih_cleanup()
72 {
73 STG_DELETE(bihb);
74 } /* bih_cleanup */
75
76 /********************************************************************/
77
78 /** \brief Add a new block during the expand phase.
79 *
80 * Create a new bih entry and add it after the one specified by the formal
81 * argument set the FINDEX/FTAG from fihb structure; used during expand
82 *
83 * \param after BIH entry to add after
84 * \return new BIH entry
85 */
86 int
exp_addbih(int after)87 exp_addbih(int after)
88 {
89
90 int i;
91 BIH *p;
92
93 i = STG_NEXT_FREELIST(bihb);
94 p = bihb.stg_base + i;
95 p->prev = after;
96 p->next = BIH_NEXT(after);
97 BIH_NEXT(after) = i;
98 BIH_PREV(p->next) = i;
99 p->label = SPTR_NULL;
100 p->lineno = 0;
101 p->flags.all = 0;
102 p->flags2.all = 0;
103 p->flags.bits.rd = 1;
104 p->first = 0;
105 p->last = 0;
106 p->assn = 0;
107 p->lpcntFrom = 0;
108 p->rgset = 0;
109 #ifdef BIH_FTAG
110 p->findex = fihb.nextfindex;
111 p->ftag = fihb.nextftag;
112 #endif
113 p->blkCnt = UNKNOWN_EXEC_CNT;
114 p->aveLpCnt = 0;
115 if (i > bihb.stg_max)
116 bihb.stg_max = i;
117
118 return (i);
119 } /* exp_addbih */
120
121 /** \brief Universal function to create new BIH entry
122 *
123 * \param after BIH anery to the new one after
124 * \param flags BIH entry to take flags from
125 * \param fih BIH entry to take FIH information from
126 *
127 * \return new BIH entry
128 */
129 int
addnewbih(int after,int flags,int fih)130 addnewbih(int after, int flags, int fih)
131 {
132 int i, next;
133 BIH *p;
134
135 i = STG_NEXT_FREELIST(bihb);
136 p = bihb.stg_base + i;
137 p->prev = after;
138 next = BIH_NEXT(after);
139 BIH_NEXT(after) = i;
140 if (next >= 0) {
141 p->next = next;
142 BIH_PREV(next) = i;
143 }
144 p->label = SPTR_NULL;
145 p->lineno = 0;
146 p->flags.all = 0;
147 p->flags2.all = 0;
148 p->flags.bits.rd = 1;
149 p->first = 0;
150 p->last = 0;
151 p->assn = 0;
152 p->lpcntFrom = 0;
153 p->rgset = 0;
154 #ifdef BIH_FTAG
155 p->findex = 0;
156 p->ftag = 0;
157 #endif
158 p->blkCnt = 0;
159 #ifdef BIH_FTAG
160 p->ftag = BIH_FTAG(fih);
161 #endif
162 p->lineno = BIH_LINENO(fih);
163 p->findex = BIH_FINDEX(fih);
164 if (flags) {
165 p->flags.bits.par = BIH_PAR(flags);
166 p->flags.bits.parsect = BIH_PARSECT(flags);
167 p->flags2.bits.task = BIH_TASK(flags);
168 p->blkCnt = BIH_BLKCNT(flags);
169 p->aveLpCnt = BIH_AVLPCNT(flags);
170 }
171 if (i > bihb.stg_max)
172 bihb.stg_max = i;
173 return i;
174 } /* addnewbih */
175
176 /** \brief Create a new BIH entry and add it after the one specified by the
177 * formal argument
178 *
179 * \param after BIH entry to add after
180 * \return new BIH entry
181 */
182 int
addbih(int after)183 addbih(int after)
184 {
185 return addnewbih(after, 0, after);
186 } /* addbih */
187
188 /********************************************************************/
189
190 /** \brief Delete a bih entry from the BIH list
191 *
192 * \param bihx BIH entry to delete
193 */
194 void
delbih(int bihx)195 delbih(int bihx)
196 {
197 int prev, next;
198 BIH bb;
199 next = BIH_NEXT(bihx);
200 prev = BIH_PREV(bihx);
201 BIH_PREV(next) = prev;
202 BIH_NEXT(prev) = next;
203 /* STG_ADD_FREELIST clears the fields;
204 * instead we want to preserve the fields,
205 * except the freelist link in BIH_NEXT */
206 bb = bihb.stg_base[bihx];
207 STG_ADD_FREELIST(bihb, bihx);
208 bb.next = BIH_NEXT(bihx);
209 bihb.stg_base[bihx] = bb;
210 }
211
212 /********************************************************************/
213
214 void
merge_bih_flags(int to_bih,int fm_bih)215 merge_bih_flags(int to_bih, int fm_bih)
216 {
217 /* after merging two blocks, merge their BIH flags */
218
219 BIH_FT(to_bih) = BIH_FT(fm_bih);
220 /* BIH_EX(to_bih) |= BIH_EX(fm_bih); ***causes SUN cc to error */
221 BIH_EX(to_bih) = BIH_EX(to_bih) | BIH_EX(fm_bih);
222 BIH_ZTRP(to_bih) = BIH_ZTRP(to_bih) | BIH_ZTRP(fm_bih);
223 BIH_SMOVE(to_bih) = BIH_SMOVE(to_bih) | BIH_SMOVE(fm_bih);
224 BIH_NOBLA(to_bih) = BIH_NOBLA(to_bih) | BIH_NOBLA(fm_bih);
225 BIH_QJSR(to_bih) = BIH_QJSR(to_bih) | BIH_QJSR(fm_bih);
226 BIH_INVIF(to_bih) = BIH_INVIF(to_bih) | BIH_INVIF(fm_bih);
227 BIH_NOINVIF(to_bih) = BIH_NOINVIF(to_bih) | BIH_NOINVIF(fm_bih);
228 BIH_SIMD(to_bih) = BIH_SIMD(to_bih) | BIH_SIMD(fm_bih);
229 BIH_RESID(to_bih) = BIH_RESID(to_bih) | BIH_RESID(fm_bih);
230 BIH_VCAND(to_bih) = BIH_VCAND(to_bih) | BIH_VCAND(fm_bih);
231 BIH_MIDIOM(to_bih) = BIH_MIDIOM(to_bih) | BIH_MIDIOM(fm_bih);
232 BIH_COMBST(to_bih) = BIH_COMBST(to_bih) | BIH_COMBST(fm_bih);
233 BIH_ASM(to_bih) = BIH_ASM(to_bih) | BIH_ASM(fm_bih);
234 BIH_LDVOL(to_bih) = BIH_LDVOL(to_bih) | BIH_LDVOL(fm_bih);
235 BIH_STVOL(to_bih) = BIH_STVOL(to_bih) | BIH_STVOL(fm_bih);
236 BIH_NODEPCHK(to_bih) = BIH_NODEPCHK(to_bih) | BIH_NODEPCHK(fm_bih);
237
238 if (BIH_TAIL(fm_bih))
239 BIH_TAIL(to_bih) = 1;
240 if (BIH_LAST(fm_bih))
241 BIH_LAST(to_bih) = 1;
242 }
243
244 /** \brief Merge a block with its successor
245 *
246 * \param curbih BIH block to merge with its successor
247 * \return BIH of the merged block if merging occurred; otherwise, return 0.
248 */
249 int
merge_bih(int curbih)250 merge_bih(int curbih)
251 {
252 int nextbih, label;
253 int firstilt, lastilt, iltx;
254
255 if (XBIT(8, 0x80000000))
256 return 0;
257
258 nextbih = BIH_NEXT(curbih);
259
260 if (BIH_EN(curbih) || BIH_EN(nextbih) || BIH_XT(curbih) || BIH_XT(nextbih) ||
261 BIH_NOMERGE(curbih) || BIH_NOMERGE(nextbih) || BIH_ENLAB(curbih) ||
262 BIH_ENLAB(nextbih)
263 #ifdef BIH_GASM
264 || BIH_GASM(curbih) || BIH_GASM(nextbih)
265 #endif
266 ) {
267 return 0;
268 }
269 if (BIH_EN(nextbih))
270 return 0;
271
272 if (BIH_ASSN(curbih) != BIH_ASSN(nextbih) ||
273 BIH_PAR(curbih) != BIH_PAR(nextbih) ||
274 BIH_PARSECT(curbih) != BIH_PARSECT(nextbih) ||
275 BIH_PL(curbih) != BIH_PL(nextbih) || BIH_CS(curbih) != BIH_CS(nextbih) ||
276 BIH_TASK(curbih) != BIH_TASK(nextbih)) {
277 return 0;
278 }
279
280 if (BIH_COMBST(curbih) && !BIH_COMBST(nextbih)) {
281 return 0;
282 }
283
284 label = BIH_LABEL(nextbih);
285 if (label) {
286 if (RFCNTG(label) || VOLG(label)) {
287 return 0;
288 }
289 ILIBLKP(label, 0);
290 BIH_LABEL(nextbih) = SPTR_NULL;
291 }
292
293 firstilt = BIH_ILTFIRST(nextbih);
294 if (ILT_DBGLINE(firstilt)) /* watch out for debugger call */
295 firstilt = ILT_NEXT(firstilt);
296 if (firstilt == 0) {
297 if (BIH_LINENO(nextbih) && !BIH_LINENO(curbih))
298 BIH_LINENO(curbih) = BIH_LINENO(nextbih);
299 delbih(nextbih); /* remove empty block */
300 return curbih;
301 }
302
303 lastilt = BIH_ILTLAST(curbih);
304 if (lastilt && IL_TYPE(ILI_OPC(ILT_ILIP(lastilt))) == ILTY_BRANCH)
305 return 0;
306
307 /*
308 * Add the "first" ilt of the block to the end of the current
309 * block.
310 */
311 rdilts(curbih);
312 ILT_NEXT(lastilt) = firstilt;
313 ILT_PREV(firstilt) = lastilt;
314 ILT_PREV(0) = BIH_ILTLAST(nextbih);
315 #if DEBUG
316 if (EXPDBG(9, 32))
317 fprintf(gbl.dbgfil, " block %d merged, label %d\n",
318 nextbih, label);
319 #endif
320
321 iltx = lastilt;
322 while (iltx) {
323 if (ILT_DELEBB(iltx)) {
324 ILT_DELETE(iltx) = 1;
325 ILT_DELEBB(iltx) = 0;
326 #if DEBUG
327 if (EXPDBG(9, 32))
328 fprintf(gbl.dbgfil,
329 " ilt %d: ILT_DELEBB->ILT_DELETE\n", iltx);
330 #endif
331 }
332 iltx = ILT_PREV(iltx);
333 }
334
335 if (BIH_LINENO(nextbih) && !BIH_LINENO(curbih))
336 BIH_LINENO(curbih) = BIH_LINENO(nextbih);
337 /* update the BIH flags of the current block */
338 merge_bih_flags(curbih, nextbih);
339
340 #if DEBUG
341 assert((BIH_PARSECT(curbih) ^ BIH_PARSECT(nextbih)) == 0,
342 "merge_bih:parsect,nonparsect", curbih, ERR_Severe);
343 #endif
344
345 wrilts(curbih);
346
347 merge_rgset(curbih, nextbih, false);
348
349 /* remove the block from the BIH list */
350
351 delbih(nextbih);
352
353 return curbih;
354 }
355
356 /*
357 * \brief If a routine contains any PAR blocks, return true
358 */
359 bool
contains_par_blocks(void)360 contains_par_blocks(void)
361 {
362 int bihx;
363
364 for (bihx = gbl.entbih; bihx; bihx = BIH_NEXT(bihx))
365 if (BIH_PAR(bihx))
366 return true;
367
368 return false;
369 }
370
371 /** \brief Merge block b2 into b1
372 */
373 void
merge_blks(int b1,int b2)374 merge_blks(int b1, int b2)
375 {
376 int i;
377 int j;
378
379 rdilts(b1);
380 i = ILT_PREV(0); /* last ilt in first block */
381 j = BIH_ILTFIRST(b2); /* first ilt in second block */
382 if (i == 0) {
383 /* first block is empty: just copy contents of second block */
384 ILT_NEXT(0) = j;
385 ILT_PREV(0) = BIH_ILTLAST(b2);
386 } else if (j) {
387 /* first & second blocks are not empty */
388 ILT_NEXT(i) = j; /* link last ilt to first */
389 ILT_PREV(j) = i;
390 ILT_PREV(0) = BIH_ILTLAST(b2);
391 }
392 /* else first block nonempty & second block empty -- nothing to do */
393
394 wrilts(b1);
395
396 /* update necessary BIH flags */
397
398 BIH_FT(b1) = BIH_FT(b2);
399 BIH_EX(b1) = BIH_EX(b1) | BIH_EX(b2);
400 BIH_QJSR(b1) = BIH_QJSR(b1) | BIH_QJSR(b2);
401 }
402
403 /* BIH_RGSET(tobih) U= BIH_RGSET(frombih) */
404 void
merge_rgset(int tobih,int frombih,bool reuse_to)405 merge_rgset(int tobih, int frombih, bool reuse_to)
406 {
407 if (BIH_RGSET(tobih) != BIH_RGSET(frombih)) {
408 if (!BIH_RGSET(tobih))
409 BIH_RGSET(tobih) = mr_get_rgset();
410 if (BIH_RGSET(frombih))
411 RGSET_XR(BIH_RGSET(tobih)) |= RGSET_XR(BIH_RGSET(frombih));
412 }
413 }
414
415 #if DEBUG
416 int *badpointer1 = (int *)0;
417 long *badpointer2 = (long *)1;
418 long badnumerator = 99;
419 long baddenominator = 0;
420 #endif
421
422 /*
423 * get rid of useless splits between blocks;
424 * if we have two blocks b1 and its lexical successor b2
425 * b1 is fall-through, does not end in a jump
426 * neither has BIH_XT BIH_PL BIH_NOMERGE BIH_ENLAB
427 * BIH_GASM BIH_LAST BIH_PAR BIH_CS BIH_PARSECT
428 * merge the two blocks
429 */
430 void
unsplit(void)431 unsplit(void)
432 {
433 int bihx;
434 #if DEBUG
435 /* convenient place for a segfault */
436 if (XBIT(4, 0x2000)) {
437 if (!XBIT(4, 0x1000) || gbl.func_count > 2) {
438 /* store to null pointer */
439 *badpointer1 = 99;
440 }
441 }
442 if (XBIT(4, 0x4000)) {
443 if (!XBIT(4, 0x1000) || gbl.func_count > 2) {
444 /* divide by zero */
445 badnumerator = badnumerator / baddenominator;
446 }
447 }
448 if (XBIT(4, 0x8000)) {
449 if (!XBIT(4, 0x1000) || gbl.func_count > 2) {
450 /* infinite loop */
451 while (badnumerator) {
452 badnumerator = (badnumerator < 1) | 3;
453 }
454 }
455 }
456 #endif
457 for (bihx = gbl.entbih; bihx; bihx = BIH_NEXT(bihx)) {
458 int b;
459 if (BIH_LAST(bihx))
460 break;
461 for (b = bihx; b;) {
462 /* if 'bihx' ends in a branch or jump or call that can throw, stop here */
463 bihx = b;
464 if (!BIH_FT(bihx))
465 break;
466 if (BIH_ILTLAST(bihx) && ILT_BR_OR_CAN_THROW(BIH_ILTLAST(bihx)))
467 break;
468 b = merge_bih(bihx);
469 }
470 }
471 } /* unsplit */
472
473 /*
474 * Split blocks after an internal jump; that is, eliminate extended basic blocks
475 */
476 void
split_extended()477 split_extended()
478 {
479 int bihx, iltx, iltnext;
480 for (bihx = gbl.entbih; bihx; bihx = BIH_NEXT(bihx)) {
481 if (BIH_LAST(bihx))
482 break;
483 for (iltx = BIH_ILTFIRST(bihx); iltx; iltx = iltnext) {
484 int ilix, opc;
485 iltnext = ILT_NEXT(iltx);
486 ilix = ILT_ILIP(iltx);
487 opc = ILI_OPC(ilix);
488 if (iltnext && IL_TYPE(opc) == ILTY_BRANCH) {
489 /* split this block just after the branch.
490 * move ILTs after this one to the new block. */
491 int newbihx;
492 newbihx = addbih(bihx);
493 BIH_ILTFIRST(newbihx) = iltnext;
494 BIH_ILTLAST(newbihx) = BIH_ILTLAST(bihx);
495 BIH_ILTLAST(bihx) = iltx;
496 ILT_NEXT(iltx) = 0;
497 ILT_PREV(iltnext) = 0;
498 BIH_FT(newbihx) = BIH_FT(bihx);
499 BIH_FT(bihx) = 1;
500 BIH_EX(newbihx) = BIH_EX(bihx);
501 BIH_LDVOL(newbihx) = BIH_LDVOL(bihx);
502 BIH_STVOL(newbihx) = BIH_STVOL(bihx);
503 BIH_QJSR(newbihx) = BIH_QJSR(bihx);
504 BIH_SMOVE(newbihx) = BIH_SMOVE(bihx);
505 BIH_NOMERGE(newbihx) = BIH_NOMERGE(bihx);
506 BIH_PAR(newbihx) = BIH_PAR(bihx);
507 iltnext = 0;
508 }
509 }
510 }
511 } /* split_extended */
512
513 void
dump_blocks(FILE * ff,int bih,char * fmt,int fihflag)514 dump_blocks(FILE *ff, int bih, char *fmt, int fihflag)
515 {
516 dump_one_block(ff, bih, fmt);
517 if (ff == NULL)
518 ff = stderr;
519 for (;;) {
520 if (BIH_LAST(bih))
521 break;
522 bih = BIH_NEXT(bih);
523 dump_ilt(ff, bih);
524 }
525 if (fihflag && fihb.stg_base && fihb.stg_avail) {
526 int fihx;
527 fprintf(ff, "\n***** FIH Table *****\n");
528 fprintf(ff, " FIH FULLNAME\n");
529 for (fihx = 1; fihx < fihb.stg_avail; fihx++) {
530 fprintf(ff, " %5d. %s\n", fihx, FIH_FULLNAME(fihx));
531 }
532 }
533 }
534
535 void
dump_one_block(FILE * ff,int bih,char * fmt)536 dump_one_block(FILE *ff, int bih, char *fmt)
537 {
538 if (ff == NULL)
539 ff = stderr;
540 if (fmt) {
541 fprintf(ff, "\n");
542 if (bih)
543 fprintf(ff, fmt, getprint((int)BIH_LABEL(bih)));
544 else
545 fprintf(ff, "%s", fmt);
546 fprintf(ff, "\n");
547 }
548 dump_ilt(ff, bih);
549 }
550