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