1 /** 2 * Compiler implementation of the 3 * $(LINK2 http://www.dlang.org, D programming language). 4 * 5 * Copyright: Copyright (C) 1986-1998 by Symantec 6 * Copyright (C) 2000-2020 by The D Language Foundation, All Rights Reserved 7 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) 8 * License: Distributed under the Boost Software License, Version 1.0. 9 * http://www.boost.org/LICENSE_1_0.txt 10 * Source: https://github.com/dlang/dmd/blob/master/src/dmd/backend/go.d 11 */ 12 13 module dmd.backend.go; 14 15 version (SPP) 16 { 17 } 18 else 19 { 20 21 import core.stdc.stdio; 22 import core.stdc.stdlib; 23 import core.stdc..string; 24 import core.stdc.time; 25 26 import dmd.backend.cc; 27 import dmd.backend.cdef; 28 import dmd.backend.oper; 29 import dmd.backend.global; 30 import dmd.backend.goh; 31 import dmd.backend.el; 32 import dmd.backend.ty; 33 import dmd.backend.type; 34 35 import dmd.backend.dlist; 36 import dmd.backend.dvec; 37 38 version (OSX) 39 { 40 /* Need this until the bootstrap compiler is upgraded 41 * https://github.com/dlang/druntime/pull/2237 42 */ 43 enum clock_t CLOCKS_PER_SEC = 1_000_000; // was 100 until OSX 10.4/10.5 44 } 45 46 extern (C++): 47 48 nothrow: 49 50 int os_clock(); 51 52 /* gdag.c */ 53 void builddags(); 54 void boolopt(); 55 void opt_arraybounds(); 56 57 /* gflow.c */ 58 void flowrd(); 59 void flowlv(); 60 void flowae(); 61 void flowvbe(); 62 void flowcp(); 63 void flowae(); 64 void genkillae(); 65 void flowarraybounds(); 66 int ae_field_affect(elem *lvalue,elem *e); 67 68 /* glocal.c */ 69 void localize(); 70 71 /* gloop.c */ 72 int blockinit(); 73 void compdom(); 74 void loopopt(); 75 void fillInDNunambig(vec_t v, elem *e); 76 void updaterd(elem *n,vec_t GEN,vec_t KILL); 77 78 /* gother.c */ 79 void rd_arraybounds(); 80 void rd_free(); 81 void constprop(); 82 void copyprop(); 83 void rmdeadass(); 84 void elimass(elem *); 85 void deadvar(); 86 void verybusyexp(); 87 list_t listrds(vec_t, elem *, vec_t); 88 89 /* gslice.c */ 90 void sliceStructs(symtab_t*, block*); 91 92 /***************************************************************************/ 93 94 extern (C) void mem_free(void* p); 95 96 void go_term() 97 { 98 vec_free(go.defkill); 99 vec_free(go.starkill); 100 vec_free(go.vptrkill); 101 go.defnod.__dtor(); 102 go.expnod.__dtor(); 103 go.expblk.__dtor(); 104 } 105 106 debug 107 { 108 // to print progress message and current trees set to 109 // DEBUG_TREES to 1 and uncomment next 2 lines 110 //debug = DEBUG_TREES; 111 debug (DEBUG_TREES) 112 void dbg_optprint(const(char) *); 113 else 114 void dbg_optprint(const(char) *c) 115 { 116 // to print progress message, undo comment 117 // printf(c); 118 } 119 } 120 else 121 { 122 void dbg_optprint(const(char) *c) { } 123 } 124 125 /************************************** 126 * Parse optimizer command line flag. 127 * Input: 128 * cp flag string 129 * Returns: 130 * 0 not recognized 131 * !=0 recognized 132 */ 133 134 int go_flag(char *cp) 135 { 136 enum GL // indices of various flags in flagtab[] 137 { 138 O,all,cnp,cp,cse,da,dc,dv,li,liv,local,loop, 139 none,o,reg,space,speed,time,tree,vbe,MAX 140 } 141 static immutable char*[GL.MAX] flagtab = 142 [ "O","all","cnp","cp","cse","da","dc","dv","li","liv","local","loop", 143 "none","o","reg","space","speed","time","tree","vbe" 144 ]; 145 static immutable mftype[GL.MAX] flagmftab = 146 [ 0,MFall,MFcnp,MFcp,MFcse,MFda,MFdc,MFdv,MFli,MFliv,MFlocal,MFloop, 147 0,0,MFreg,0,MFtime,MFtime,MFtree,MFvbe 148 ]; 149 150 //printf("go_flag('%s')\n", cp); 151 uint flag = binary(cp + 1,cast(const(char)**)flagtab.ptr,GL.MAX); 152 if (go.mfoptim == 0 && flag != -1) 153 go.mfoptim = MFall & ~MFvbe; 154 155 if (*cp == '-') /* a regular -whatever flag */ 156 { /* cp -> flag string */ 157 switch (flag) 158 { 159 case GL.all: 160 case GL.cnp: 161 case GL.cp: 162 case GL.dc: 163 case GL.da: 164 case GL.dv: 165 case GL.cse: 166 case GL.li: 167 case GL.liv: 168 case GL.local: 169 case GL.loop: 170 case GL.reg: 171 case GL.speed: 172 case GL.time: 173 case GL.tree: 174 case GL.vbe: 175 go.mfoptim &= ~flagmftab[flag]; /* clear bits */ 176 break; 177 case GL.o: 178 case GL.O: 179 case GL.none: 180 go.mfoptim |= MFall & ~MFvbe; // inverse of -all 181 break; 182 case GL.space: 183 go.mfoptim |= MFtime; /* inverse of -time */ 184 break; 185 case -1: /* not in flagtab[] */ 186 goto badflag; 187 default: 188 assert(0); 189 } 190 } 191 else if (*cp == '+') /* a regular +whatever flag */ 192 { /* cp -> flag string */ 193 switch (flag) 194 { 195 case GL.all: 196 case GL.cnp: 197 case GL.cp: 198 case GL.dc: 199 case GL.da: 200 case GL.dv: 201 case GL.cse: 202 case GL.li: 203 case GL.liv: 204 case GL.local: 205 case GL.loop: 206 case GL.reg: 207 case GL.speed: 208 case GL.time: 209 case GL.tree: 210 case GL.vbe: 211 go.mfoptim |= flagmftab[flag]; /* set bits */ 212 break; 213 case GL.none: 214 go.mfoptim &= ~MFall; /* inverse of +all */ 215 break; 216 case GL.space: 217 go.mfoptim &= ~MFtime; /* inverse of +time */ 218 break; 219 case -1: /* not in flagtab[] */ 220 goto badflag; 221 default: 222 assert(0); 223 } 224 } 225 if (go.mfoptim) 226 { 227 go.mfoptim |= MFtree | MFdc; // always do at least this much 228 config.flags4 |= (go.mfoptim & MFtime) ? CFG4speed : CFG4space; 229 } 230 else 231 { 232 config.flags4 &= ~CFG4optimized; 233 } 234 return 1; // recognized 235 236 badflag: 237 return 0; 238 } 239 240 debug (DEBUG_TREES) 241 { 242 void dbg_optprint(char *title) 243 { 244 block *b; 245 for (b = startblock; b; b = b.Bnext) 246 if (b.Belem) 247 { 248 printf("%s\n",title); 249 elem_print(b.Belem); 250 } 251 } 252 } 253 254 /**************************** 255 * Optimize function. 256 */ 257 258 void optfunc() 259 { 260 version (HTOD) 261 { 262 } 263 else 264 { 265 if (debugc) printf("optfunc()\n"); 266 dbg_optprint("optfunc\n"); 267 268 debug if (debugb) 269 { 270 printf("................Before optimization.........\n"); 271 WRfunc(); 272 } 273 274 if (localgot) 275 { // Initialize with: 276 // localgot = OPgot; 277 elem *e = el_long(TYnptr, 0); 278 e.Eoper = OPgot; 279 e = el_bin(OPeq, TYnptr, el_var(localgot), e); 280 startblock.Belem = el_combine(e, startblock.Belem); 281 } 282 283 // Each pass through the loop can reduce only one level of comma expression. 284 // The infinite loop check needs to take this into account. 285 // Add 100 just to give optimizer more rope to try to converge. 286 int iterationLimit = 0; 287 for (block* b = startblock; b; b = b.Bnext) 288 { 289 if (!b.Belem) 290 continue; 291 int d = el_countCommas(b.Belem) + 100; 292 if (d > iterationLimit) 293 iterationLimit = d; 294 } 295 296 // Some functions can take enormous amounts of time to optimize. 297 // We try to put a lid on it. 298 clock_t starttime = os_clock(); 299 int iter = 0; // iteration count 300 do 301 { 302 //printf("iter = %d\n", iter); 303 if (++iter > 200) 304 { assert(iter < iterationLimit); // infinite loop check 305 break; 306 } 307 version (MARS) 308 util_progress(); 309 else 310 file_progress(); 311 312 //printf("optelem\n"); 313 /* canonicalize the trees */ 314 foreach (b; BlockRange(startblock)) 315 if (b.Belem) 316 { 317 debug if (debuge) 318 { 319 printf("before\n"); 320 elem_print(b.Belem); 321 //el_check(b.Belem); 322 } 323 324 b.Belem = doptelem(b.Belem,bc_goal[b.BC] | GOALagain); 325 326 debug if (0 && debugf) 327 { 328 printf("after\n"); 329 elem_print(b.Belem); 330 } 331 } 332 //printf("blockopt\n"); 333 if (go.mfoptim & MFdc) 334 blockopt(0); // do block optimization 335 out_regcand(&globsym); // recompute register candidates 336 go.changes = 0; // no changes yet 337 sliceStructs(&globsym, startblock); 338 if (go.mfoptim & MFcnp) 339 constprop(); /* make relationals unsigned */ 340 if (go.mfoptim & (MFli | MFliv)) 341 loopopt(); /* remove loop invariants and */ 342 /* induction vars */ 343 /* do loop rotation */ 344 else 345 foreach (b; BlockRange(startblock)) 346 b.Bweight = 1; 347 dbg_optprint("boolopt\n"); 348 349 if (go.mfoptim & MFcnp) 350 boolopt(); // optimize boolean values 351 if (go.changes && go.mfoptim & MFloop && (os_clock() - starttime) < 30 * CLOCKS_PER_SEC) 352 continue; 353 354 if (go.mfoptim & MFcnp) 355 constprop(); /* constant propagation */ 356 if (go.mfoptim & MFcp) 357 copyprop(); /* do copy propagation */ 358 359 /* Floating point constants and string literals need to be 360 * replaced with loads from variables in read-only data. 361 * This can result in localgot getting needed. 362 */ 363 Symbol *localgotsave = localgot; 364 for (block* b = startblock; b; b = b.Bnext) 365 { 366 if (b.Belem) 367 { 368 b.Belem = doptelem(b.Belem,bc_goal[b.BC] | GOALstruct); 369 if (b.Belem) 370 b.Belem = el_convert(b.Belem); 371 } 372 } 373 if (localgot != localgotsave) 374 { /* Looks like we did need localgot, initialize with: 375 * localgot = OPgot; 376 */ 377 elem *e = el_long(TYnptr, 0); 378 e.Eoper = OPgot; 379 e = el_bin(OPeq, TYnptr, el_var(localgot), e); 380 startblock.Belem = el_combine(e, startblock.Belem); 381 } 382 383 /* localize() is after localgot, otherwise we wind up with 384 * more than one OPgot in a function, which mucks up OSX 385 * code generation which assumes at most one (localgotoffset). 386 */ 387 if (go.mfoptim & MFlocal) 388 localize(); // improve expression locality 389 if (go.mfoptim & MFda) 390 rmdeadass(); /* remove dead assignments */ 391 392 if (debugc) printf("changes = %d\n", go.changes); 393 if (!(go.changes && go.mfoptim & MFloop && (os_clock() - starttime) < 30 * CLOCKS_PER_SEC)) 394 break; 395 } while (1); 396 if (debugc) printf("%d iterations\n",iter); 397 398 if (go.mfoptim & MFdc) 399 blockopt(1); // do block optimization 400 401 for (block* b = startblock; b; b = b.Bnext) 402 { 403 if (b.Belem) 404 postoptelem(b.Belem); 405 } 406 if (go.mfoptim & MFvbe) 407 verybusyexp(); /* very busy expressions */ 408 if (go.mfoptim & MFcse) 409 builddags(); /* common subexpressions */ 410 if (go.mfoptim & MFdv) 411 deadvar(); /* eliminate dead variables */ 412 413 debug if (debugb) 414 { 415 printf(".............After optimization...........\n"); 416 WRfunc(); 417 } 418 419 // Prepare for code generator 420 for (block* b = startblock; b; b = b.Bnext) 421 { 422 block_optimizer_free(b); 423 } 424 } 425 } 426 427 }