dmd.backend.go source code

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 }