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 /** \file optimize.h 19 \brief arious definitions for the optimizer module 20 */ 21 22 /* DEBUG-controlled -q stuff */ 23 24 #define OPTDBG(x, y) (DEBUG && DBGBIT(x, y)) 25 26 /* * * * * symbol table macros for just the optimizer * * * * */ 27 28 #define ISSCALAR(s) TY_ISSCALAR(DTY(DTYPEG(s))) 29 /* FTN's storage classes */ 30 #define IS_LCL(s) (SCG(s) == SC_LOCAL || SCG(s) == SC_PRIVATE) 31 #define IS_EXTERN(s) (SC_ISCMBLK(SCG(s)) || SCG(s) == SC_EXTERN) 32 #define IS_STATIC(s) (SCG(s) == SC_STATIC) 33 #define IS_CMNBLK(s) (SC_ISCMBLK(SCG(s))) 34 #define IS_DUM(s) (SCG(s) == SC_DUMMY) 35 #define IS_LCL_OR_DUM(s) (IS_LCL(s) || IS_DUM(s)) 36 #define IS_REGARG(s) (REGARGG(s) && REDUCG(s)) 37 38 #define IS_PRIVATE(s) (SCG(s) == SC_PRIVATE) 39 40 /* * * * * storage allocation macros * * * * */ 41 42 #define OPT_ALLOC(stgb, dt, sz) \ 43 { \ 44 NEW(stgb.stg_base, dt, sz); \ 45 stgb.stg_size = sz; \ 46 } 47 48 #define OPT_NEXT(stb) stb.stg_avail++ 49 50 #define OPT_NEED(stb, dt, sz) \ 51 { \ 52 NEED(stb.stg_avail, stb.stg_base, dt, stb.stg_size, stb.stg_size + sz); \ 53 } 54 55 #define OPT_FREE(stb) \ 56 { \ 57 FREE(stb.stg_base); \ 58 stb.stg_base = NULL; \ 59 stb.stg_size = 0; \ 60 stb.stg_avail = 0; \ 61 } 62 63 typedef unsigned short US; 64 65 /* * * * * getitem (salloc.c) Areas Used * * * * */ 66 67 #define PSI_AREA 0 /* pred/succ area */ 68 #define BUCKET_AREA 1 /* item area for dominators */ 69 #define IUSE_AREA 1 /* induction use area */ 70 #define TOPI_AREA 2 /* item area for topological sort */ 71 #define Q_AREA 2 /* queue area (used local to a routine */ 72 #define DU_AREA 3 /* definition use and use def area */ 73 #define STL_AREA 5 /* store list area */ 74 #define DLT_AREA \ 75 9 /* list of stds to be deleted in flow(); can't \ 76 * be shared with flowgraph() and findloops(). \ 77 */ 78 79 /* * * * * Queue list Item * * * * */ 80 81 typedef struct Q_TAG { 82 int info; 83 int flag; 84 struct Q_TAG *next; 85 } Q_ITEM; 86 #define Q_NULL NULL 87 #define GET_Q_ITEM(q) q = (Q_ITEM *)getitem(Q_AREA, sizeof(Q_ITEM)) 88 89 /* * * * * Predecessor/Successor Item * * * * */ 90 91 typedef struct PSI_TAG *PSI_P; 92 #define PSI_P_NULL NULL 93 94 typedef struct PSI_TAG { 95 int node; 96 union { 97 UINT all; 98 struct { 99 unsigned f1 : 1; 100 unsigned f2 : 1; 101 unsigned f3 : 1; 102 unsigned f4 : 1; 103 unsigned f5 : 1; 104 unsigned f6 : 1; 105 unsigned f7 : 1; 106 unsigned f8 : 1; 107 unsigned f9 : 1; 108 unsigned f10 : 1; 109 unsigned f11 : 1; 110 unsigned f12 : 1; 111 unsigned f13 : 1; 112 unsigned f14 : 1; 113 unsigned f15 : 1; 114 unsigned f16 : 1; 115 } bits; 116 } flags; 117 PSI_P next; 118 } PSI; 119 120 #define PSI_NODE(i) ((i)->node) 121 #define PSI_ALL(i) ((i)->flags.all) 122 #define PSI_FT(i) ((i)->flags.bits.f1) 123 #define PSI_ZTRP(i) ((i)->flags.bits.f2) 124 #define PSI_EXIT(i) ((i)->flags.bits.f4) 125 #define PSI_NEXT(i) ((i)->next) 126 #define GET_PSI(i) i = (PSI *)getitem(PSI_AREA, sizeof(PSI)) 127 128 /* * * * * Bit Vector Set Representation * * * * */ 129 130 #define BITS_PER_BYTE 8 131 132 typedef int BV; 133 typedef struct { 134 BV *stg_base; 135 int stg_avail; 136 BV *nme_base; 137 int nme_avail; 138 } SET_BASE; 139 140 #define BV_BITS (sizeof(BV) * BITS_PER_BYTE) 141 142 /* * * * * Optimizer Augmented AST * * * * */ 143 144 typedef struct {/* foreach ast index */ 145 int invar; /* field for marking an AST invariant/variant */ 146 } OAST; 147 148 /* * * * * Flow Graph Node * * * * */ 149 150 typedef struct { 151 int lineno; /* line number of the node */ 152 int first; /* first std in node */ 153 int last; /* last std in node */ 154 int lnext; /* next lexical node */ 155 int lprev; /* previous lexical node */ 156 int dfn; /* depth first number */ 157 int dom; /* immediate dominator */ 158 int rdfn; /* reverse graph depth first number */ 159 int rdfo; /* reverse depth first number */ 160 int pdom; /* immediate post-dominator */ 161 int vtx; /* sorted vertex-dfn array */ 162 int rvtx; /* sorted vertex-rdfn array */ 163 int rdfovtx; /* sorted vertex-rdfo array */ 164 int loop; /* loop containing the node */ 165 int next; /* next in regions list */ 166 int natnxt; /* next in natural loop list */ 167 int fdef; /* first definition */ 168 int scr; /* scratch field -- BIH_ASSN for vectorizer */ 169 int scr2; /* scratch field -- BIH_RGSET for vectorizer */ 170 int atomic; /* in atomic-update region */ 171 PSI_P pred; /* predecssor list */ 172 PSI_P succ; /* successor list */ 173 BV *in; 174 BV *out; 175 BV *uninited; /* set if variable is not assigned/initialized, 176 currently ignore host program assignment */ 177 int par; /* nest level of parallelism */ 178 int parloop; /* nest level of parallelism */ 179 union { 180 struct { 181 unsigned ft : 1; 182 unsigned head : 1; 183 unsigned tail : 1; 184 unsigned ex : 1; 185 unsigned en : 1; 186 unsigned xt : 1; 187 unsigned qjsr : 1; /* used only by the optimizer */ 188 unsigned mexits : 1; 189 unsigned innermost : 1; 190 unsigned ztrp : 1; 191 unsigned done : 1; 192 unsigned inq : 1; 193 unsigned visited : 1; 194 unsigned ptr_store : 1; /* store via pointer */ 195 unsigned jmp_tbl : 1; /* a jump uses a jump table */ 196 unsigned cs : 1; /* in a critical section */ 197 unsigned master : 1; /* in a master/serial section */ 198 unsigned parsect : 1; 199 unsigned task : 1; /* in a task */ 200 unsigned ctlequiv : 1; /* control-equivalent to loop header */ 201 unsigned mark : 1; 202 unsigned sdscunsafe : 1; 203 unsigned malf_lp : 1; /* in a malformed loop */ 204 unsigned spare : 7; 205 } bits; 206 UINT all; 207 } flags; 208 } FG; 209 210 #define FG_LINENO(i) opt.fgb.stg_base[i].lineno 211 #define FG_STDFIRST(i) opt.fgb.stg_base[i].first 212 #define FG_STDLAST(i) opt.fgb.stg_base[i].last 213 #define FG_LABEL(i) STD_LABEL(FG_STDFIRST(i)) 214 #define FG_LNEXT(i) opt.fgb.stg_base[i].lnext 215 #define FG_LPREV(i) opt.fgb.stg_base[i].lprev 216 #define FG_DFN(i) opt.fgb.stg_base[i].dfn 217 #define FG_DOM(i) opt.fgb.stg_base[i].dom 218 #define FG_RDFN(i) opt.fgb.stg_base[i].rdfn 219 #define FG_RDFO(i) opt.fgb.stg_base[i].rdfo 220 #define FG_PDOM(i) opt.fgb.stg_base[i].pdom 221 #define FG_PRED(i) opt.fgb.stg_base[i].pred 222 #define FG_SUCC(i) opt.fgb.stg_base[i].succ 223 #define FG_LOOP(i) opt.fgb.stg_base[i].loop 224 #define FG_NEXT(i) opt.fgb.stg_base[i].next 225 #define FG_NATNXT(i) opt.fgb.stg_base[i].natnxt 226 #define FG_FDEF(i) opt.fgb.stg_base[i].fdef 227 #define FG_IN(i) opt.fgb.stg_base[i].in 228 #define FG_OUT(i) opt.fgb.stg_base[i].out 229 #define FG_UNINITED(i) opt.fgb.stg_base[i].uninited 230 #define FG_ATOMIC(i) opt.fgb.stg_base[i].atomic 231 #define FG_FT(i) opt.fgb.stg_base[i].flags.bits.ft 232 #define FG_HEAD(i) opt.fgb.stg_base[i].flags.bits.head 233 #define FG_TAIL(i) opt.fgb.stg_base[i].flags.bits.tail 234 #define FG_EX(i) opt.fgb.stg_base[i].flags.bits.ex 235 #define FG_EXSDSCUNSAFE(i) opt.fgb.stg_base[i].flags.bits.sdscunsafe 236 #define FG_EN(i) opt.fgb.stg_base[i].flags.bits.en 237 #define FG_XT(i) opt.fgb.stg_base[i].flags.bits.xt 238 #define FG_QJSR(i) opt.fgb.stg_base[i].flags.bits.qjsr 239 #define FG_MEXITS(i) opt.fgb.stg_base[i].flags.bits.mexits 240 #define FG_INNERMOST(i) opt.fgb.stg_base[i].flags.bits.innermost 241 #define FG_ZTRP(i) opt.fgb.stg_base[i].flags.bits.ztrp 242 #define FG_DONE(i) opt.fgb.stg_base[i].flags.bits.done 243 #define FG_INQ(i) opt.fgb.stg_base[i].flags.bits.inq 244 #define FG_VISITED(i) opt.fgb.stg_base[i].flags.bits.visited 245 #define FG_PTR_STORE(i) opt.fgb.stg_base[i].flags.bits.ptr_store 246 #define FG_JMP_TBL(i) opt.fgb.stg_base[i].flags.bits.jmp_tbl 247 #define FG_PAR(i) opt.fgb.stg_base[i].par 248 #define FG_CS(i) opt.fgb.stg_base[i].flags.bits.cs 249 #define FG_MASTER(i) opt.fgb.stg_base[i].flags.bits.master 250 #define FG_PARLOOP(i) opt.fgb.stg_base[i].parloop 251 #define FG_PARSECT(i) opt.fgb.stg_base[i].flags.bits.parsect 252 #define FG_TASK(i) opt.fgb.stg_base[i].flags.bits.task 253 #define FG_CTLEQUIV(i) opt.fgb.stg_base[i].flags.bits.ctlequiv 254 #define FG_MARK(i) opt.fgb.stg_base[i].flags.bits.mark 255 #define FG_MALF_LP(i) opt.fgb.stg_base[i].flags.bits.malf_lp 256 #define FG_ALL(i) opt.fgb.stg_base[i].flags.all 257 #define VTX_NODE(i) opt.fgb.stg_base[i].vtx 258 #define RVTX_NODE(i) opt.fgb.stg_base[i].rvtx 259 #define RDFOVTX_NODE(i) opt.fgb.stg_base[i].rdfovtx 260 261 /*** BIH-related flags for which there are HPF equivalents in the flowgraph ***/ 262 /*** Needed for modules which are shared with pghpf ***/ 263 #define FG_BIH(i) (i) 264 #define FG_TO_BIH(i) FG_BIH(i) 265 #define BIH_TO_FG(i) (i) 266 #define BIH_LINENO(i) FG_LINENO(i) 267 #define BIH_LABEL(i) FG_LABEL(i) 268 #define BIH_ILTFIRST(i) FG_STDFIRST(i) 269 #define BIH_ILTLAST(i) FG_STDLAST(i) 270 #define BIH_NEXT(i) FG_LNEXT(i) 271 #define BIH_PREV(i) FG_LPREV(i) 272 #define BIH_ASSN(i) opt.fgb.stg_base[i].scr 273 #define BIH_RGSET(i) opt.fgb.stg_base[i].scr2 274 #define BIH_FLAGS(i) FG_FLAGS(i) 275 #define BIH_FT(i) FG_FT(i) 276 #define BIH_EN(i) FG_EN(i) 277 #define BIH_EX(i) FG_EX(i) 278 #define BIH_EXSDSCUNSAFE(i) FG_EXSDSCUNSAFE(i) 279 #define BIH_XT(i) FG_XT(i) 280 #define BIH_ZTRP(i) FG_ZTRP(i) 281 #define BIH_HEAD(i) FG_HEAD(i) 282 #define BIH_TAIL(i) FG_TAIL(i) 283 #define BIH_INNERMOST(i) FG_INNERMOST(i) 284 #define BIH_QJSR(i) FG_QJSR(i) 285 #define BIH_MEXITS(i) FG_MEXITS(i) 286 #define BIH_PAR(i) FG_PAR(i) 287 #define BIH_CS(i) FG_CS(i) 288 #define BIH_MASTER(i) FG_MASTER(i) 289 #define BIH_PARLOOP(i) FG_PARLOOP(i) 290 #define BIH_PARSECT(i) FG_PARSECT(i) 291 #define BIH_TASK(i) FG_TASK(i) 292 293 /*** ILT-related flags for which there are HPF equivalents in the STD ***/ 294 /*** Needed for modules which are shared with pghpf ***/ 295 296 #define NEW_NODE(after) add_fg(after) 297 298 /* * * * * Flowgraph Edge * * * * */ 299 300 typedef struct { 301 int pred; /* the edge (pred, succ) */ 302 int succ; 303 int next; /* next edge with same succ ("head"), initially -1 */ 304 } EDGE; 305 306 #define EDGE_PRED(i) opt.rteb.stg_base[i].pred 307 #define EDGE_SUCC(i) opt.rteb.stg_base[i].succ 308 #define EDGE_NEXT(i) opt.rteb.stg_base[i].next 309 #define NUM_RTE (opt.rteb.stg_avail) 310 311 /* * * * * Stores in a Loop * * * * */ 312 313 typedef struct {/* store table entry */ 314 int nm; /* names of item being stored */ 315 INT16 type; /* type of store: 316 * 0 - addr is "constant" 317 * 1 - addr is "variable" 318 */ 319 UINT16 next; /* next store item in loop; 0 terminates list */ 320 } STORE; 321 322 #define STORE_NM(i) opt.storeb.stg_base[i].nm 323 #define STORE_TYPE(i) opt.storeb.stg_base[i].type 324 #define STORE_NEXT(i) opt.storeb.stg_base[i].next 325 326 typedef struct STL_TAG {/* list item for stores in a loop */ 327 UINT16 store; /* index into store table of first store */ 328 INT16 unused; 329 struct STL_TAG *nextsibl; /* next STL for any sibling loops 330 * ie. (next node in parent's child list 331 */ 332 struct STL_TAG *childlst; /* child list STL for any nested loops */ 333 } STL; 334 335 /* * * * * Loop Table * * * * */ 336 337 typedef struct { 338 int level; /* level number of loop */ 339 int parent; /* parent of loop */ 340 int head; /* head (FG node) of the loop */ 341 int tail; /* tail (FG node) of the loop */ 342 int fg; /* head of the region list */ 343 int loop; /* loop for the sorted list */ 344 int edge; /* retreating edge index */ 345 int child; /* loop immediately enclosed by loop; 0 if 346 * innermost 347 */ 348 int sibling; /* next loop at the same level of the loop; 349 * the loops immediately enclosed by a loop 350 * are represented by the list beginning with 351 * child, and linked using the sibling field. 352 * a sibling value of 0 terminates the list. 353 */ 354 int parloop; /* loop is to be executed in parallel; nest level of parallelism */ 355 union { 356 struct { 357 unsigned innermost : 1; /* loop is an innermost loop */ 358 unsigned callfg : 1; /* loop or any enclosed loop contains 359 * external calls 360 */ 361 unsigned ext_store : 1; /* loop or any enclosed loop contains a 362 * store into an external variable or a 363 * variable with its & taken 364 */ 365 unsigned ptr_store : 1; /* loop or any enclosed loop contains a 366 * store via a pointer 367 */ 368 unsigned zerotrip : 1; /* loop was converted from a 369 * while or for to if-do-while 370 */ 371 unsigned ptr_load : 1; /* loop or any enclosed loop contains a 372 * load via a pointer 373 */ 374 unsigned nobla : 1; /* loop or any enclosed loop contains a 375 * block with its BIH_NOBLA flag set. 376 */ 377 unsigned qjsr : 1; /* loop or any enclosed loop contains a 378 * block with BIH_QJSR set 379 */ 380 unsigned mexits : 1; /* loop contains multiple exits */ 381 unsigned jmp_tbl : 1; /* loop or any enclosed loop contains a 382 * jump using a jump tbl 383 */ 384 unsigned invarif : 1; /* invarif loop optz. performed for loop or 385 * a descendant 386 */ 387 unsigned cs : 1; /* region contains a block with BIH_CS set; 388 * not propagated to its parent's LP_CS. 389 */ 390 unsigned csect : 1; /* loop or any enclosed loop contains a block 391 * with BIH_CS set. 392 */ 393 unsigned mark : 1; /* general save area */ 394 unsigned forall : 1; /* loop is a forall 'loop' */ 395 unsigned master : 1; /* loop contains a master/serial region */ 396 unsigned parregn : 1; /* region contains a block with BIH_PAR set: 397 * 1. the loop may be a parallel loop 398 * (LP_PARLOOP is set), 399 * 2. the loop is not executed in parallel 400 * but contains a parallel region (the 401 * loop's head BIH_PAR is not set), 402 * 3. the loop is contained within a parallel 403 * region (the LP_PARLOOP is not set). 404 */ 405 unsigned parsect : 1; /* region contains a block with BIH_PARSECT 406 * set. 407 */ 408 unsigned callinternal : 1; /* contains call to internal subprogram */ 409 unsigned xtndrng : 1; /* extended range loop */ 410 unsigned cncall : 1; /* all calls in loop are call safe */ 411 unsigned vollab : 1; /* loop contains block labeled volatile */ 412 unsigned sdscunsafe : 1; /* loop contains a call to a routine that 413 * modifies section descriptors 414 */ 415 unsigned task : 1; /* loop contains a task */ 416 unsigned tail_aexe : 1; /* tail is always executed */ 417 unsigned spare : 6; 418 } bits; 419 UINT all; 420 } flags; 421 STL *stl; /* list of stores in loop and 422 * contained loops 423 */ 424 BV *lin; /* set of variables live-in to loop */ 425 BV *lout; /* set of variables live-out of loop */ 426 PSI_P exits; /* list of natural loop exits - for live var*/ 427 Q_ITEM *stl_par; /* list of nmes of non-private vars which are 428 * assigned while in a critical section of 429 * a loop or a contained loop, a parallel 430 * section of a loop or a contained loop, 431 * or in a parallel region. 432 */ 433 int count; /* number of loops enclosed by the loop, 434 * inclusive. 435 */ 436 int hstdf; /* invariant: list of stmt will be hoisted out of loop */ 437 int dstdf; /* invariant: deallocate stmts will drop out of loop */ 438 } LP; 439 440 #define LP_LEVEL(i) opt.lpb.stg_base[i].level 441 #define LP_PARENT(i) opt.lpb.stg_base[i].parent 442 #define LP_HEAD(i) opt.lpb.stg_base[i].head 443 #define LP_TAIL(i) opt.lpb.stg_base[i].tail 444 #define LP_FG(i) opt.lpb.stg_base[i].fg 445 #define LP_LOOP(i) opt.lpb.stg_base[i].loop 446 #define LP_EDGE(i) opt.lpb.stg_base[i].edge 447 #define LP_CHILD(i) opt.lpb.stg_base[i].child 448 #define LP_SIBLING(i) opt.lpb.stg_base[i].sibling 449 #define LP_RGSET(i) opt.lpb.stg_base[i].rgset 450 #define LP_INNERMOST(i) opt.lpb.stg_base[i].flags.bits.innermost 451 #define LP_CALLFG(i) opt.lpb.stg_base[i].flags.bits.callfg 452 #define LP_CALLSDSCUNSAFE(i) opt.lpb.stg_base[i].flags.bits.sdscunsafe 453 #define LP_CALLINTERNAL(i) opt.lpb.stg_base[i].flags.bits.callinternal 454 #define LP_EXT_STORE(i) opt.lpb.stg_base[i].flags.bits.ext_store 455 #define LP_PTR_STORE(i) opt.lpb.stg_base[i].flags.bits.ptr_store 456 #define LP_PTR_LOAD(i) opt.lpb.stg_base[i].flags.bits.ptr_load 457 #define LP_ZEROTRIP(i) opt.lpb.stg_base[i].flags.bits.zerotrip 458 #define LP_NOBLA(i) opt.lpb.stg_base[i].flags.bits.nobla 459 #define LP_QJSR(i) opt.lpb.stg_base[i].flags.bits.qjsr 460 #define LP_MEXITS(i) opt.lpb.stg_base[i].flags.bits.mexits 461 #define LP_JMP_TBL(i) opt.lpb.stg_base[i].flags.bits.jmp_tbl 462 #define LP_INVARIF(i) opt.lpb.stg_base[i].flags.bits.invarif 463 #define LP_PARLOOP(i) opt.lpb.stg_base[i].parloop 464 #define LP_CS(i) opt.lpb.stg_base[i].flags.bits.cs 465 #define LP_CSECT(i) opt.lpb.stg_base[i].flags.bits.csect 466 #define LP_MARK(i) opt.lpb.stg_base[i].flags.bits.mark 467 #define LP_FORALL(i) opt.lpb.stg_base[i].flags.bits.forall 468 #define LP_MASTER(i) opt.lpb.stg_base[i].flags.bits.master 469 #define LP_PARREGN(i) opt.lpb.stg_base[i].flags.bits.parregn 470 #define LP_PARSECT(i) opt.lpb.stg_base[i].flags.bits.parsect 471 #define LP_XTNDRNG(i) opt.lpb.stg_base[i].flags.bits.xtndrng 472 #define LP_CNCALL(i) opt.lpb.stg_base[i].flags.bits.cncall 473 #define LP_VOLLAB(i) opt.lpb.stg_base[i].flags.bits.vollab 474 #define LP_TASK(i) opt.lpb.stg_base[i].flags.bits.task 475 #define LP_TAIL_AEXE(i) opt.lpb.stg_base[i].flags.bits.tail_aexe 476 #define LP_ALL(i) opt.lpb.stg_base[i].flags.all 477 #define LP_STL(i) opt.lpb.stg_base[i].stl 478 #define LP_LIN(i) opt.lpb.stg_base[i].lin 479 #define LP_LOUT(i) opt.lpb.stg_base[i].lout 480 #define LP_EXITS(i) opt.lpb.stg_base[i].exits 481 #define LP_STL_PAR(i) opt.lpb.stg_base[i].stl_par 482 #define LP_COUNT(i) opt.lpb.stg_base[i].count 483 #define LP_HSTDF(i) opt.lpb.stg_base[i].hstdf 484 #define LP_DSTDF(i) opt.lpb.stg_base[i].dstdf 485 486 typedef struct UD_TAG {/* def list for a use */ 487 int def; /* index into def table */ 488 struct UD_TAG *next; 489 } UD; 490 491 /* * * * * Scalar Uses * * * * */ 492 493 typedef struct {/* use table entry */ 494 int nm; 495 int fg; 496 int std; 497 int ast; /* A_ID ast of the use */ 498 int addr; /* address ast of the use */ 499 union { 500 int all; 501 struct { 502 unsigned exposed : 1; /* use is reached from the beginning 503 * of the block 504 */ 505 unsigned cse : 1; /* use is cse of a variable which is 506 * due to the postfix operator 507 */ 508 unsigned precise : 1; /* address is precise/function-invariant */ 509 unsigned arg : 1; /* use is an argument use */ 510 unsigned doinit : 1; /* use created when creating a doinit def */ 511 unsigned mark1 : 1; /* mark used by fusion, others? */ 512 unsigned mark2 : 1; /* mark used by fusion, others? */ 513 unsigned loop : 1; /* added at loop entry */ 514 unsigned aggr : 1; /* use is of an aggregate */ 515 } bits; 516 } flags; 517 UD *ud; /* defs reaching this use */ 518 } USE; 519 520 #define USE_NM(i) opt.useb.stg_base[i].nm 521 #define USE_FG(i) opt.useb.stg_base[i].fg 522 #define USE_STD(i) opt.useb.stg_base[i].std 523 #define USE_AST(i) opt.useb.stg_base[i].ast 524 #define USE_ADDR(i) opt.useb.stg_base[i].addr 525 #define USE_EXPOSED(i) opt.useb.stg_base[i].flags.bits.exposed 526 #define USE_CSE(i) opt.useb.stg_base[i].flags.bits.cse 527 #define USE_PRECISE(i) opt.useb.stg_base[i].flags.bits.precise 528 #define USE_ARG(i) opt.useb.stg_base[i].flags.bits.arg 529 #define USE_DOINIT(i) opt.useb.stg_base[i].flags.bits.doinit 530 #define USE_MARK1(i) opt.useb.stg_base[i].flags.bits.mark1 531 #define USE_MARK2(i) opt.useb.stg_base[i].flags.bits.mark2 532 #define USE_LOOPENTRY(i) opt.useb.stg_base[i].flags.bits.loop 533 #define USE_AGGR(i) opt.useb.stg_base[i].flags.bits.aggr 534 #define USE_UD(i) opt.useb.stg_base[i].ud 535 536 typedef struct DU_TAG {/* use list for a definition */ 537 int use; /* index into use table */ 538 struct DU_TAG *next; 539 } DU; 540 541 /* * * * * Scalar Definitions * * * * */ 542 /* NOTES: 543 * A called function implicitly defines those variables which can be affected 544 * by a call (e.g., variables, file static variables, &, etc.). In 545 * order to track these implicit definitions, definition 1 is reserved as 546 * the def implied by a call. If a block contains a call, definition 1 will 547 * be in its GEN set. We use just 1 definition instead of adding definitions 548 * for each of the call-affected variables to the block containing the call. 549 * The IN and OUT sets of a block will contain this def if any call can reach 550 * the block. 551 * A store via pointer implicitly defines those variables whose address 552 * has been taken. Definition 2 is reserved as the def implied by a store 553 * via a pointer. If a block contains a store via a pointer, def 2 will be 554 * in its GEN set. 555 * 556 * Definition 3 is the first user def. 557 */ 558 typedef struct {/* def table entry */ 559 int fg; 560 int std; 561 int nm; 562 int lhs; /* lefthand side of the def - A_ID ast of the 563 * destination */ 564 int addr; /* address ast of the destination */ 565 int rhs; /* righthand side of the def - source ast */ 566 int next; /* next def for this names */ 567 int lnext; /* next definition in fg; 0 terminates list*/ 568 union { 569 UINT all; 570 struct { 571 unsigned gen : 1; /* def reaches end of the block */ 572 unsigned cnst : 1; /* def's value is a constant. */ 573 unsigned delete : 1; /* def has been deleted */ 574 unsigned self : 1; /* sym defined appears in def expr */ 575 unsigned confl : 1; /* def's msize conflicts with a use's msize */ 576 unsigned doinit : 1; /* initial def for a do/forall */ 577 unsigned doend : 1; /* increment def for a enddo/endforall */ 578 unsigned arg : 1; /* sym appears as an actual argument*/ 579 unsigned other : 1; /* other implicit def: allocate status, etc. */ 580 unsigned precise : 1; /* address is precise/function-invariant */ 581 unsigned mark1 : 1; 582 unsigned mark2 : 1; 583 unsigned loop : 1; /* added at loop entry */ 584 unsigned aggr : 1; /* def is of an aggregate */ 585 } bits; 586 } flags; 587 DU *du; /* uses reached by this def */ 588 DU *csel; /* cse uses not reached by this def; occurs 589 * for postfix expressions: i = j = k++; 590 * k's csel includes the cse uses of k stored 591 * into i and j. 592 */ 593 } DEF; 594 595 #define DEF_FG(i) opt.defb.stg_base[i].fg 596 #define DEF_STD(i) opt.defb.stg_base[i].std 597 #define DEF_NM(i) opt.defb.stg_base[i].nm 598 #define DEF_LHS(i) opt.defb.stg_base[i].lhs 599 #define DEF_ADDR(i) opt.defb.stg_base[i].addr 600 #define DEF_RHS(i) opt.defb.stg_base[i].rhs 601 #define DEF_NEXT(i) opt.defb.stg_base[i].next 602 #define DEF_LNEXT(i) opt.defb.stg_base[i].lnext 603 #define DEF_ALL(i) opt.defb.stg_base[i].flags.all 604 #define DEF_GEN(i) opt.defb.stg_base[i].flags.bits.gen 605 #define DEF_CONST(i) opt.defb.stg_base[i].flags.bits.cnst 606 #define DEF_DELETE(i) opt.defb.stg_base[i].flags.bits.delete 607 #define DEF_SELF(i) opt.defb.stg_base[i].flags.bits.self 608 #define DEF_CONFL(i) opt.defb.stg_base[i].flags.bits.confl 609 #define DEF_DOINIT(i) opt.defb.stg_base[i].flags.bits.doinit 610 #define DEF_DOEND(i) opt.defb.stg_base[i].flags.bits.doend 611 #define DEF_ARG(i) opt.defb.stg_base[i].flags.bits.arg 612 #define DEF_OTHER(i) opt.defb.stg_base[i].flags.bits.other 613 #define DEF_PRECISE(i) opt.defb.stg_base[i].flags.bits.precise 614 #define DEF_MARK1(i) opt.defb.stg_base[i].flags.bits.mark1 615 #define DEF_MARK2(i) opt.defb.stg_base[i].flags.bits.mark2 616 #define DEF_LOOPENTRY(i) opt.defb.stg_base[i].flags.bits.loop 617 #define DEF_AGGR(i) opt.defb.stg_base[i].flags.bits.aggr 618 #define DEF_DU(i) opt.defb.stg_base[i].du 619 #define DEF_CSEL(i) opt.defb.stg_base[i].csel 620 621 /* Predefined defs. 622 * Define def values for the definition implied by a call, a store via a 623 * pointer and the first user definition. 624 */ 625 #define CALL_DEF 1 626 #define PTR_STORE_DEF 2 627 #define QJSR_DEF 3 628 #define FIRST_DEF 4 629 630 /* * * * * Invariant ILI Attributes * * * * */ 631 632 #define NOT_INV -1 633 #define INV -2 634 #define T_INV -3 /* probably not used */ 635 636 #define AST_INVG(i) opt.astb.stg_base[i].invar 637 #define AST_INVP(i, j) opt.astb.stg_base[i].invar = (j) 638 #define AST_ISINV(i) (AST_INVG(i) < -1) 639 #define AST_ISINV_TEMP(i) (AST_INVG(i) < -1) 640 #define IS_INVARIANT(i) (AST_ISINV(i) || AST_ISINV_TEMP(i)) 641 642 #define ILI_ISINV(i) AST_ISINV(i) 643 644 /* * * * * optimizer global data * * * * */ 645 646 typedef struct { 647 int num_nodes; /* number of nodes in a flow graph */ 648 int dfn; /* number of nodes which have dfn's */ 649 STG_DECLARE(fgb, FG); /* flow graph memory area */ 650 STG_DECLARE(rteb, EDGE); 651 int exitfg; /* fg of a functions's exit block */ 652 int nloops; /* number of loops in a function */ 653 STG_DECLARE(lpb, LP); /* pointer to loop table */ 654 STG_DECLARE(storeb, STORE); 655 STG_DECLARE(defb, DEF); 656 STG_DECLARE(useb, USE); 657 STG_DECLARE(invb, int); 658 int nsyms; 659 int ndefs; 660 SET_BASE def_setb; 661 int pre_fg; /* preheader flowgraph node of a loop */ 662 int exit_fg; /* exit flowgraph node of a loop */ 663 int rat; /* rat pointer for the current loop */ 664 int head_label; /* counter for new loop header labels */ 665 int exit_label; /* counter for exit block labels */ 666 struct { /* countable loop info found in induction 667 * and used by peephole 668 */ 669 int top; /* label of top of loop */ 670 int cnt; /* ast ptr of loop count */ 671 int cnt_sym; /* loop count temporary if reg is needed */ 672 int skip; /* ast ptr of loop skip */ 673 int branch; /* branch ast to be replaced */ 674 } cntlp; 675 int zstride_ast; /* list of ZSTRIDE check ast which need to be 676 * added before a loop; uses an undefined 677 * operand (# MAX_OPNDS) to link together 678 * (cleared when added ast added to block). 679 */ 680 int sc; /* storage class used for optimizer-created 681 * temporaries (SC_LOCAL, SC_PRIVATE). 682 */ 683 STG_DECLARE(astb, OAST); 684 } OPT; 685 686 OPT opt; 687 688 /***** optimize.c *****/ 689 void optshrd_init(void); 690 void optshrd_finit(void); 691 void optshrd_fend(void); 692 void optshrd_end(void); 693 694 #define HLOPT_INDUC 0x1 695 #define HLOPT_ENDTEST 0x2 696 #define HLOPT_ALL 0x3 /* 'or' of all HLOPT_... bits */ 697 void hlopt_init(int); 698 void hlopt_end(int, int); 699 700 void optimize(int); 701 void add_loop_preheader(int); 702 void add_loop_exit(int); 703 void add_single_loop_exit(int); 704 705 /***** fgraph.c *****/ 706 void flowgraph(void); 707 int add_fg(int); 708 void delete_fg(int); 709 PSI_P add_succ(int, int); 710 PSI_P add_pred(int, int); 711 void rm_edge(int, int); 712 int add_to_parent(int, int); 713 void dump_node(int); 714 void rdilts(int); 715 void wrilts(int); 716 void unlnkilt(int, int, int); 717 void delilt(int); 718 void dmpilt(int); 719 void dump_flowgraph(void); 720 721 /***** findloop.c *****/ 722 #include "findloop.h" 723 724 /***** flow.c *****/ 725 void flow(void); 726 void flow_end(void); 727 int update_stl(int, int); 728 LOGICAL is_live_in(int, int); 729 LOGICAL is_live_out(int, int); 730 void delete_stores(void); 731 void use_before_def(void); 732 void add_new_uses(int, int, int, int); 733 734 /***** invar.c *****/ 735 void invariant(int); 736 void invariant_nomotion(int); 737 void invariant_mark(int, int); 738 void invariant_unmark(void); 739 void invariant_unmarkv(void); 740 LOGICAL is_invariant(int); 741 LOGICAL is_sym_invariant_safe(int, int); 742 743 /***** induc.c *****/ 744 void induction_init(void); 745 void induction_end(void); 746 void induction(int); 747 int get_loop_count(int); 748 void compute_last_values(int, int); 749 void end_loop_count(void); 750 751 /***** optutil.c *****/ 752 void bv_zero(int *, int); 753 void bv_copy(int *, int *, int); 754 void bv_union(int *, int *, int); 755 void bv_sub(int *, int *, int); 756 void bv_set(int *, int); 757 void bv_off(int *, int); 758 LOGICAL bv_notequal(int *, int *, int); 759 LOGICAL bv_mem(int *, int); 760 void bv_print(int *, int); 761 int get_otemp(void); 762 LOGICAL is_optsym(int); 763 LOGICAL is_sym_optsafe(int, int); 764 LOGICAL is_sym_live_safe(int, int); 765 LOGICAL is_call_safe(int); 766 LOGICAL is_ptr_safe(int); 767 LOGICAL is_sym_ptrsafe(int); 768 int pred_of_loop(int); 769 int find_rdef(int, int, LOGICAL); 770 LOGICAL is_sym_exit_live(int); 771 LOGICAL is_sym_imp_live(int); 772 LOGICAL is_sym_entry_live(int); 773 LOGICAL is_store_via_ptr(int); 774 LOGICAL can_copy_def(int, int, LOGICAL); 775 LOGICAL def_ok(int, int, int); 776 LOGICAL is_avail_expr(int, int, int, int, int); 777 LOGICAL is_call_in_path(int, int, int, int); 778 LOGICAL is_ptr_in_path(int, int, int, int); 779 LOGICAL single_ud(int); 780 LOGICAL only_one_ud(int); 781 LOGICAL is_def_imp_live(int); 782 void rm_def_rloop(int, int); 783 int copy_to_loop(int, int); 784 void points_to(void); /* pointsto.c */ 785 void f90_fini_pointsto(void); /* pointsto.c */ 786 LOGICAL lhs_needtmp(int, int, int); 787 void postdominators(void); 788 void findlooptopsort(void); 789 void reorderloops(); 790 void putstdpta(int); 791 void putstdassigns(int); 792 void unconditional_branches(void); 793 void bv_intersect(BV *a, BV *b, UINT len); 794 void bv_intersect3(BV *a, BV *b, BV *c, UINT len); 795 void optimize_alloc(void); /* commopt.c */ 796 void points_to_anal(void); /* pointsto.c */ 797 void fini_points_to_all(void); /* pointsto.c */ 798 bool pta_stride1(int ptrstdx, int ptrsptr); /* pointsto.c */ 799 void pstride_analysis(void); /* pstride.c */ 800 void fini_pstride_analysis(void); /* pstride.c */ 801 void call_analyze(void); /* rest.c */ 802 void convert_output(void); /* outconv.c */ 803 void sectfloat(void); /* outconv.c */ 804 void sectinline(void); /* outconv.c */ 805 void linearize_arrays(void); /* outconv.c */ 806 void hoist_stmt(int std, int fg, int l); /* outconv.c */ 807 void redundss(void); /* redundss.c */ 808 809 /* ipa.c */ 810 extern int IPA_Vestigial; 811 int IPA_isnoconflict(int sptr); /* main.c wrapper */ 812 int IPA_noconflict(int sptr); /* ipa.c */ 813 void ipa_fini(void); /* ipa.c */ 814 void ipa_closefile(void); /* ipa.c */ 815 int IPA_arg_alloc(int funcsptr, int argnum); 816 int IPA_func_argalloc_safe(int sptr); 817 int IPA_func_globalalloc_safe(int sptr); 818 int IPA_safe(int sptr); 819 void ipa_restore_all(void); 820 void ipa_restore_back(void); 821 long IPA_sstride(int sptr); /* ipa.c */ 822 long IPA_pstride(int sptr); /* ipa.c */ 823 void ipa_mfilename(char *name); 824 825 /* ipasave.c */ 826 void ipasave_fini(void); 827 void ipasave_closefile(void); 828 void ipasave(void); 829 int ipa_return_in_argument(int func); 830 int idsym(int cls, int id); 831 void ipasave_compname(char *, int, char **); 832 void ipasave_compsw(char *); 833 void ipasave_mfilename(char *); 834 835 /* dump.c */ 836 void dstdp(int stdx); 837 void dumpdtypes(void); 838 void dastree(int astx); 839 void dsa(void); 840 void dast(int astx); 841 void past(int astx); 842 void dstda(void); 843 void dsym(int sptr); 844 void dstdpa(void); 845