1 /**
2  * Compiler implementation of the
3  * $(LINK2 http://www.dlang.org, D programming language).
4  *
5  * Copyright:   Copyright (C) 1985-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:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
9  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/gflow.d, backend/gflow.d)
10  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/backend/gflow.d
11  */
12 
13 module dmd.backend.gflow;
14 
15 version (SCPP)
16     version = COMPILE;
17 version (MARS)
18     version = COMPILE;
19 
20 version (COMPILE)
21 {
22 
23 import core.stdc.stdio;
24 import core.stdc.stdlib;
25 import core.stdc..string;
26 
27 import dmd.backend.cc;
28 import dmd.backend.cdef;
29 import dmd.backend.code_x86;
30 import dmd.backend.oper;
31 import dmd.backend.global;
32 import dmd.backend.goh;
33 import dmd.backend.el;
34 import dmd.backend.outbuf;
35 import dmd.backend.ty;
36 import dmd.backend.type;
37 
38 import dmd.backend.barray;
39 import dmd.backend.dlist;
40 import dmd.backend.dvec;
41 
42 nothrow:
43 
44 void vec_setclear(size_t b, vec_t vs, vec_t vc) { vec_setbit(b, vs); vec_clearbit(b, vc); }
45 
46 bool Eunambig(elem* e) { return OTassign(e.Eoper) && e.EV.E1.Eoper == OPvar; }
47 
48 char symbol_isintab(Symbol *s) { return sytab[s.Sclass] & SCSS; }
49 
50 void util_free(void* p) { if (p) free(p); }
51 void *util_calloc(uint n, uint size) { void* p = calloc(n, size); assert(!(n * size) || p); return p; }
52 void *util_realloc(void* p, uint n, uint size) { void* q = realloc(p, n * size); assert(!(n * size) || q); return q; }
53 
54 extern (C++):
55 
56 
57 /* Since many routines are nearly identical, we can combine them with   */
58 /* this flag:                                                           */
59 
60 enum
61 {
62     AE = 1,
63     CP,
64     VBE
65 }
66 
67 
68 private __gshared
69 {
70     int flowxx;              // one of the above values
71 
72     vec_t ambigsym = null;
73 }
74 
75 
76 /***************** REACHING DEFINITIONS *********************/
77 
78 /************************************
79  * Compute reaching definitions (RDs).
80  * That is, for each block B and each program variable X
81  * find all elems that could be the last elem that defines
82  * X along some path to B.
83  * Binrd = the set of defs reaching the beginning of B.
84  * Boutrd = the set of defs reaching the end of B.
85  * Bkillrd = set of defs that are killed by some def in B.
86  * Bgenrd = set of defs in B that reach the end of B.
87  */
88 
89 void flowrd()
90 {
91     rdgenkill();            /* Compute Bgen and Bkill for RDs       */
92     if (go.defnod.length == 0)     /* if no definition elems               */
93         return;             /* no analysis to be done               */
94 
95     /* The transfer equation is:                                    */
96     /*      Bin = union of Bouts of all predecessors of B.          */
97     /*      Bout = (Bin - Bkill) | Bgen                             */
98     /* Using Ullman's algorithm:                                    */
99 
100     foreach (b; dfo[])
101         vec_copy(b.Boutrd, b.Bgen);
102 
103     bool anychng;
104     vec_t tmp = vec_calloc(go.defnod.length);
105     do
106     {
107         anychng = false;
108         foreach (b; dfo[])    // for each block
109         {
110             /* Binrd = union of Boutrds of all predecessors of b */
111             vec_clear(b.Binrd);
112             if (b.BC != BCcatch /*&& b.BC != BCjcatch*/)
113             {
114                 /* Set Binrd to 0 to account for:
115                  * i = 0;
116                  * try { i = 1; throw; } catch () { x = i; }
117                  */
118                 foreach (bp; ListRange(b.Bpred))
119                     vec_orass(b.Binrd,list_block(bp).Boutrd);
120             }
121             /* Bout = (Bin - Bkill) | Bgen */
122             vec_sub(tmp,b.Binrd,b.Bkill);
123             vec_orass(tmp,b.Bgen);
124             if (!anychng)
125                 anychng = !vec_equal(tmp,b.Boutrd);
126             vec_copy(b.Boutrd,tmp);
127         }
128     } while (anychng);              /* while any changes to Boutrd  */
129     vec_free(tmp);
130 
131     static if (0)
132     {
133         dbg_printf("Reaching definitions\n");
134         foreach (i, b; dfo[])    // for each block
135         {
136             assert(vec_numbits(b.Binrd) == go.defnod.length);
137             dbg_printf("B%d Bin ", cast(int)i); vec_println(b.Binrd);
138             dbg_printf("  Bgen "); vec_println(b.Bgen);
139             dbg_printf(" Bkill "); vec_println(b.Bkill);
140             dbg_printf("  Bout "); vec_println(b.Boutrd);
141         }
142     }
143 }
144 
145 /***************************
146  * Compute Bgen and Bkill for RDs.
147  */
148 
149 private void rdgenkill()
150 {
151     /* Compute number of definition elems. */
152     uint num_unambig_def = 0;
153     uint deftop = 0;
154     foreach (b; dfo[])    // for each block
155         if (b.Belem)
156         {
157             deftop += numdefelems(b.Belem, &num_unambig_def);
158         }
159 
160     /* Allocate array of pointers to all definition elems   */
161     /*      The elems are in dfo order.                     */
162     /*      go.defnod[]s consist of a elem pointer and a pointer */
163     /*      to the enclosing block.                         */
164     go.defnod.setLength(deftop);
165     if (deftop == 0)
166         return;
167 
168     /* Allocate buffer for the DNunambig vectors
169      */
170     const size_t dim = (deftop + (VECBITS - 1)) >> VECSHIFT;
171     const sz = (dim + 2) * num_unambig_def;
172     go.dnunambig.setLength(sz);
173     go.dnunambig[] = 0;
174 
175     go.defnod.setLength(0);
176     foreach (b; dfo[])    // for each block
177         if (b.Belem)
178             asgdefelems(b, b.Belem);    // fill in go.defnod[]
179     assert(go.defnod.length == deftop);
180 
181     initDNunambigVectors();
182 
183     foreach (b; dfo[])    // for each block
184     {
185         /* dump any existing vectors */
186         vec_free(b.Bgen);
187         vec_free(b.Bkill);
188         vec_free(b.Binrd);
189         vec_free(b.Boutrd);
190 
191         /* calculate and create new vectors */
192         rdelem(&(b.Bgen),&(b.Bkill),b.Belem);
193         if (b.BC == BCasm)
194         {
195             vec_clear(b.Bkill);        // KILL nothing
196             vec_set(b.Bgen);           // GEN everything
197         }
198         b.Binrd = vec_calloc(deftop);
199         b.Boutrd = vec_calloc(deftop);
200     }
201 }
202 
203 /**********************
204  * Compute and return # of definition elems in e.
205  */
206 
207 private uint numdefelems(elem *e, uint *pnum_unambig_def)
208 {
209     uint n = 0;
210     while (1)
211     {
212         assert(e);
213         if (OTdef(e.Eoper))
214         {
215             ++n;
216             if (OTassign(e.Eoper) && e.EV.E1.Eoper == OPvar)
217                 ++*pnum_unambig_def;
218         }
219         if (OTbinary(e.Eoper))
220         {
221             n += numdefelems(e.EV.E1, pnum_unambig_def);
222             e = e.EV.E2;
223         }
224         else if (OTunary(e.Eoper))
225         {
226             e = e.EV.E1;
227         }
228         else
229             break;
230     }
231     return n;
232 }
233 
234 /**************************
235  * Load go.defnod[] array.
236  * Loaded in order of execution of the elems. Not sure if this is
237  * necessary.
238  */
239 
240 private void asgdefelems(block *b,elem *n)
241 {
242     assert(b && n);
243     const op = n.Eoper;
244     if (ERTOL(n))
245     {
246         asgdefelems(b,n.EV.E2);
247         asgdefelems(b,n.EV.E1);
248     }
249     else if (OTbinary(op))
250     {
251         asgdefelems(b,n.EV.E1);
252         asgdefelems(b,n.EV.E2);
253     }
254     else if (OTunary(op))
255         asgdefelems(b,n.EV.E1);
256     if (OTdef(op))
257     {
258         n.Edef = cast(uint)go.defnod.length;
259         go.defnod.push(DefNode(n, b, null));
260     }
261     else
262         n.Edef = ~0;       // just to ensure it is not in the array
263 }
264 
265 /*************************************
266  * Allocate and initialize DNumambig vectors in go.defnod[]
267  */
268 
269 private void initDNunambigVectors()
270 {
271     //printf("initDNunambigVectors()\n");
272     const size_t numbits = go.defnod.length;
273     const size_t dim = (numbits + (VECBITS - 1)) >> VECSHIFT;
274 
275     uint j = 0;
276     foreach (const i; 0 .. go.defnod.length)
277     {
278         elem *e = go.defnod[i].DNelem;
279         if (OTassign(e.Eoper) && e.EV.E1.Eoper == OPvar)
280         {
281             vec_t v = &go.dnunambig[j] + 2;
282             assert(vec_dim(v) == 0);
283             vec_dim(v) = dim;
284             vec_numbits(v) = numbits;
285             j += dim + 2;
286             fillInDNunambig(v, e);
287             go.defnod[i].DNunambig = v;
288         }
289     }
290     assert(j <= go.dnunambig.length);
291 }
292 
293 /*************************************
294  * Allocate and compute rd GEN and KILL.
295  */
296 
297 private void rdelem(vec_t *pgen,vec_t *pkill,   /* where to put result          */
298         elem *n)                                /* tree to evaluate for GEN and KILL */
299 {
300     *pgen = vec_calloc(go.defnod.length);
301     *pkill = vec_calloc(go.defnod.length);
302     if (n)
303         accumrd(*pgen,*pkill,n);
304 }
305 
306 /**************************************
307  * Accumulate GEN and KILL vectors for this elem.
308  */
309 
310 private void accumrd(vec_t GEN,vec_t KILL,elem *n)
311 {
312     assert(GEN && KILL && n);
313     const op = n.Eoper;
314     if (OTunary(op))
315         accumrd(GEN,KILL,n.EV.E1);
316     else if (OTbinary(op))
317     {
318         if (op == OPcolon || op == OPcolon2)
319         {
320             vec_t Gl,Kl,Gr,Kr;
321             rdelem(&Gl,&Kl,n.EV.E1);
322             rdelem(&Gr,&Kr,n.EV.E2);
323 
324             switch (el_returns(n.EV.E1) * 2 | int(el_returns(n.EV.E2)))
325             {
326                 case 3: // E1 and E2 return
327                     /* GEN = (GEN - Kl) | Gl |
328                      *       (GEN - Kr) | Gr
329                      * KILL |= Kl & Kr
330                      * This simplifies to:
331                      * GEN = GEN | (Gl | Gr) | (GEN - (Kl & Kr)
332                      * KILL |= Kl & Kr
333                      */
334                     vec_andass(Kl,Kr);
335                     vec_orass(KILL,Kl);
336 
337                     vec_orass(Gl,Gr);
338                     vec_sub(Gr,GEN,Kl);  // (GEN - (Kl & Kr)
339                     vec_or(GEN,Gl,Gr);
340                     break;
341 
342                 case 2: // E1 returns
343                     /* GEN = (GEN - Kl) | Gl
344                      * KILL |= Kl
345                      */
346                     vec_subass(GEN,Kl);
347                     vec_orass(GEN,Gl);
348                     vec_orass(KILL,Kl);
349                     break;
350 
351                 case 1: // E2 returns
352                     /* GEN = (GEN - Kr) | Gr
353                      * KILL |= Kr
354                      */
355                     vec_subass(GEN,Kr);
356                     vec_orass(GEN,Gr);
357                     vec_orass(KILL,Kr);
358                     break;
359 
360                 case 0: // neither returns
361                     break;
362 
363                 default:
364                     assert(0);
365             }
366 
367             vec_free(Gl);
368             vec_free(Kl);
369             vec_free(Gr);
370             vec_free(Kr);
371         }
372         else if (op == OPandand || op == OPoror)
373         {
374             vec_t Gr,Kr;
375             accumrd(GEN,KILL,n.EV.E1);
376             rdelem(&Gr,&Kr,n.EV.E2);
377             if (el_returns(n.EV.E2))
378                 vec_orass(GEN,Gr);      // GEN |= Gr
379 
380             vec_free(Gr);
381             vec_free(Kr);
382         }
383         else if (OTrtol(op) && ERTOL(n))
384         {
385             accumrd(GEN,KILL,n.EV.E2);
386             accumrd(GEN,KILL,n.EV.E1);
387         }
388         else
389         {
390             accumrd(GEN,KILL,n.EV.E1);
391             accumrd(GEN,KILL,n.EV.E2);
392         }
393     }
394 
395     if (OTdef(op))                  /* if definition elem           */
396         updaterd(n,GEN,KILL);
397 }
398 
399 /******************** AVAILABLE EXPRESSIONS ***********************/
400 
401 /************************************
402  * Compute available expressions (AEs).
403  * That is, expressions whose result is still current.
404  * Bin = the set of AEs reaching the beginning of B.
405  * Bout = the set of AEs reaching the end of B.
406  */
407 
408 void flowae()
409 {
410     flowxx = AE;
411     flowaecp();
412 }
413 
414 /**************************** COPY PROPAGATION ************************/
415 
416 /***************************************
417  * Compute copy propagation info (CPs).
418  * Very similar to AEs (the same code is used).
419  * Using RDs for copy propagation is WRONG!
420  * That is, set of copy statements still valid.
421  * Bin = the set of CPs reaching the beginning of B.
422  * Bout = the set of CPs reaching the end of B.
423  */
424 
425 void flowcp()
426 {
427     flowxx = CP;
428     flowaecp();
429 }
430 
431 /*****************************************
432  * Common flow analysis routines for Available Expressions and
433  * Copy Propagation.
434  * Input:
435  *      flowxx
436  */
437 
438 private void flowaecp()
439 {
440     aecpgenkill(go);          // Compute Bgen and Bkill for AEs or CPs
441     if (go.exptop <= 1)        /* if no expressions                    */
442         return;
443 
444     /* The transfer equation is:                    */
445     /*      Bin = & Bout(all predecessors P of B)   */
446     /*      Bout = (Bin - Bkill) | Bgen             */
447     /* Using Ullman's algorithm:                    */
448 
449     vec_clear(startblock.Bin);
450     vec_copy(startblock.Bout,startblock.Bgen); /* these never change */
451     if (startblock.BC == BCiftrue)
452         vec_copy(startblock.Bout2,startblock.Bgen2); // these never change
453 
454     /* For all blocks except startblock     */
455     foreach (b; dfo[1 .. $])
456     {
457         vec_set(b.Bin);        /* Bin = all expressions        */
458 
459         /* Bout = (Bin - Bkill) | Bgen  */
460         vec_sub(b.Bout,b.Bin,b.Bkill);
461         vec_orass(b.Bout,b.Bgen);
462         if (b.BC == BCiftrue)
463         {
464             vec_sub(b.Bout2,b.Bin,b.Bkill2);
465             vec_orass(b.Bout2,b.Bgen2);
466         }
467     }
468 
469     vec_t tmp = vec_calloc(go.exptop);
470     bool anychng;
471     do
472     {
473         anychng = false;
474 
475         // For all blocks except startblock
476         foreach (b; dfo[1 .. $])
477         {
478             // Bin = & of Bout of all predecessors
479             // Bout = (Bin - Bkill) | Bgen
480 
481             bool first = true;
482             foreach (bl; ListRange(b.Bpred))
483             {
484                 block* bp = list_block(bl);
485                 if (bp.BC == BCiftrue && bp.nthSucc(0) != b)
486                 {
487                     if (first)
488                         vec_copy(b.Bin,bp.Bout2);
489                     else
490                         vec_andass(b.Bin,bp.Bout2);
491                 }
492                 else
493                 {
494                     if (first)
495                         vec_copy(b.Bin,bp.Bout);
496                     else
497                         vec_andass(b.Bin,bp.Bout);
498                 }
499                 first = false;
500             }
501             assert(!first);     // it must have had predecessors
502 
503             if (anychng)
504             {
505                 vec_sub(b.Bout,b.Bin,b.Bkill);
506                 vec_orass(b.Bout,b.Bgen);
507             }
508             else
509             {
510                 vec_sub(tmp,b.Bin,b.Bkill);
511                 vec_orass(tmp,b.Bgen);
512                 if (!vec_equal(tmp,b.Bout))
513                 {   // Swap Bout and tmp instead of
514                     // copying tmp over Bout
515                     vec_t v = tmp;
516                     tmp = b.Bout;
517                     b.Bout = v;
518                     anychng = true;
519                 }
520             }
521 
522             if (b.BC == BCiftrue)
523             {   // Bout2 = (Bin - Bkill2) | Bgen2
524                 if (anychng)
525                 {
526                     vec_sub(b.Bout2,b.Bin,b.Bkill2);
527                     vec_orass(b.Bout2,b.Bgen2);
528                 }
529                 else
530                 {
531                     vec_sub(tmp,b.Bin,b.Bkill2);
532                     vec_orass(tmp,b.Bgen2);
533                     if (!vec_equal(tmp,b.Bout2))
534                     {   // Swap Bout and tmp instead of
535                         // copying tmp over Bout2
536                         vec_t v = tmp;
537                         tmp = b.Bout2;
538                         b.Bout2 = v;
539                         anychng = true;
540                     }
541                 }
542             }
543         }
544     } while (anychng);
545     vec_free(tmp);
546 }
547 
548 /******************************
549  * A variable to avoid parameter overhead to asgexpelems().
550  */
551 
552 private __gshared block *this_block;
553 
554 /***********************************
555  * Compute Bgen and Bkill for AEs, CPs, and VBEs.
556  */
557 
558 private void aecpgenkill(ref GlobalOptimizer go)
559 {
560     /****************************
561      * Compute number of cp (copy propagation) elems.
562      * Mark cp elems by setting NFLaecp flag.
563      * Returns:
564      *      number of cp elems
565      */
566 
567     int numcpelems(elem *n)
568     {
569         while (1)
570         {
571             const op = n.Eoper;
572             if (OTunary(op))
573             {
574                 n.Nflags &= ~NFLaecp;
575                 n = n.EV.E1;
576                 continue;
577             }
578             else if (OTbinary(op))
579             {
580                 /* look for elem of the form OPvar=OPvar, where they aren't the */
581                 /* same variable.                                               */
582                 if ((op == OPeq || op == OPstreq) &&
583                     n.EV.E1.Eoper == OPvar &&
584                     n.EV.E2.Eoper == OPvar &&
585                     !((n.EV.E1.Ety | n.EV.E2.Ety) & (mTYvolatile | mTYshared)) &&
586                     n.EV.E1.EV.Vsym != n.EV.E2.EV.Vsym)
587                 {
588                     n.Nflags |= NFLaecp;
589                     return numcpelems(n.EV.E1) +
590                            numcpelems(n.EV.E2) +
591                            1;
592 
593                 }
594                 n.Nflags &= ~NFLaecp;
595                 int num = numcpelems(n.EV.E2);
596                 if (num)
597                     return num + numcpelems(n.EV.E1);
598                 n = n.EV.E1;
599                 continue;
600             }
601             else
602             {
603                 n.Nflags &= ~NFLaecp;
604                 return 0;
605             }
606         }
607     }
608 
609     /*****************************
610      * Accumulate number of expressions in go.exptop.
611      * Set NFLaecp as a flag indicating an AE elem.
612      * Returns:
613      *      true if this elem is a possible AE elem.
614      */
615 
616     int numaeelems(elem *n)
617     {
618         uint ae;
619 
620         assert(n);
621         const op = n.Eoper;
622         if (OTunary(op))
623         {
624             ae = numaeelems(n.EV.E1);
625             // Disallow starred references to avoid problems with VBE's
626             // being hoisted before tests of an invalid pointer.
627             if (flowxx == VBE && op == OPind)
628                 goto L1;
629         }
630         else if (OTbinary(op))
631             ae = numaeelems(n.EV.E1) & numaeelems(n.EV.E2);
632         else
633             ae = true;
634 
635         if (ae && OTae(op) && !(n.Ety & (mTYvolatile | mTYshared)) &&
636             // Disallow struct AEs, because we can't handle CSEs that are structs
637             tybasic(n.Ety) != TYstruct &&
638             tybasic(n.Ety) != TYarray)
639         {
640             n.Nflags |= NFLaecp;           /* remember for asgexpelems()   */
641             go.exptop++;
642         }
643         else
644         L1:
645             n.Nflags &= ~NFLaecp;
646         return n.Nflags & NFLaecp;
647     }
648 
649     /********************************
650      * Assign ae (or cp) elems to go.expnod[] (in order of evaluation).
651      */
652 
653     void asgexpelems(elem *n)
654     {
655         assert(n);
656         if (OTunary(n.Eoper))
657             asgexpelems(n.EV.E1);
658         else if (ERTOL(n))
659         {
660             asgexpelems(n.EV.E2);
661             asgexpelems(n.EV.E1);
662         }
663         else if (OTbinary(n.Eoper))
664         {
665             asgexpelems(n.EV.E1);
666             asgexpelems(n.EV.E2);
667         }
668 
669         if (n.Nflags & NFLaecp)              /* if an ae, cp or vbe elem     */
670         {
671             n.Eexp = go.exptop;              /* remember index into go.expnod[] */
672             go.expnod[go.exptop] = n;
673             if (go.expblk.length)
674                 go.expblk[go.exptop] = this_block;
675             go.exptop++;
676         }
677         else
678             n.Eexp = 0;
679     }
680 
681     go.expnod.setLength(0);             // dump any existing one
682 
683     /* Compute number of expressions */
684     go.exptop = 1;                     /* start at 1                   */
685     foreach (b; dfo[])
686         if (b.Belem)
687         {
688             if (flowxx == CP)
689                 go.exptop += numcpelems(b.Belem);
690             else // AE || VBE
691                 numaeelems(b.Belem);
692         }
693     if (go.exptop <= 1)                /* if no expressions            */
694         return;
695 
696     /* Allocate array of pointers to all expression elems.          */
697     /* (The elems are in order. Also, these expressions must not    */
698     /* have any side effects, and possibly should not be machine    */
699     /* dependent primitive addressing modes.)                       */
700     go.expnod.setLength(go.exptop);
701     go.expnod[0] = null;
702 
703     go.expblk.setLength(flowxx == VBE ? go.exptop : 0);
704 
705     go.exptop = 1;
706     foreach (b; dfo[])
707     {
708         this_block = b;    /* so asgexpelems knows about this */
709         if (b.Belem)
710             asgexpelems(b.Belem);
711     }
712     assert(go.exptop == go.expnod.length);
713 
714     defstarkill();                  /* compute go.defkill and go.starkill */
715 
716     static if (0)
717     {
718         assert(vec_numbits(go.defkill) == go.expnod.length);
719         assert(vec_numbits(go.starkill) == go.expnod.length);
720         assert(vec_numbits(go.vptrkill) == go.expnod.length);
721         dbg_printf("defkill  "); vec_println(go.defkill);
722         if (go.starkill)
723         {   dbg_printf("starkill "); vec_println(go.starkill);}
724         if (go.vptrkill)
725         {   dbg_printf("vptrkill "); vec_println(go.vptrkill); }
726     }
727 
728     foreach (i, b; dfo[])
729     {
730         /* dump any existing vectors    */
731         vec_free(b.Bin);
732         vec_free(b.Bout);
733         vec_free(b.Bgen);
734         vec_free(b.Bkill);
735         b.Bgen = vec_calloc(go.expnod.length);
736         b.Bkill = vec_calloc(go.expnod.length);
737         switch (b.BC)
738         {
739             case BCiftrue:
740                 vec_free(b.Bout2);
741                 vec_free(b.Bgen2);
742                 vec_free(b.Bkill2);
743                 elem* e;
744                 for (e = b.Belem; e.Eoper == OPcomma; e = e.EV.E2)
745                     accumaecp(b.Bgen,b.Bkill,e);
746                 if (e.Eoper == OPandand || e.Eoper == OPoror)
747                 {
748                     accumaecp(b.Bgen,b.Bkill,e.EV.E1);
749                     vec_t Kr = vec_calloc(go.expnod.length);
750                     vec_t Gr = vec_calloc(go.expnod.length);
751                     accumaecp(Gr,Kr,e.EV.E2);
752 
753                     // We might or might not have executed E2
754                     // KILL1 = KILL | Kr
755                     // GEN1 = GEN & ((GEN - Kr) | Gr)
756 
757                     // We definitely executed E2
758                     // KILL2 = (KILL - Gr) | Kr
759                     // GEN2 = (GEN - Kr) | Gr
760 
761                     const uint dim = cast(uint)vec_dim(Kr);
762                     vec_t KILL = b.Bkill;
763                     vec_t GEN = b.Bgen;
764 
765                     foreach (j; 0 .. dim)
766                     {
767                         vec_base_t KILL1 = KILL[j] | Kr[j];
768                         vec_base_t GEN1  = GEN[j] & ((GEN[j] & ~Kr[j]) | Gr[j]);
769 
770                         vec_base_t KILL2 = (KILL[j] & ~Gr[j]) | Kr[j];
771                         vec_base_t GEN2  = (GEN[j] & ~Kr[j]) | Gr[j];
772 
773                         KILL[j] = KILL1;
774                         GEN[j] = GEN1;
775                         Kr[j] = KILL2;
776                         Gr[j] = GEN2;
777                     }
778 
779                     if (e.Eoper == OPandand)
780                     {   b.Bkill  = Kr;
781                         b.Bgen   = Gr;
782                         b.Bkill2 = KILL;
783                         b.Bgen2  = GEN;
784                     }
785                     else
786                     {   b.Bkill  = KILL;
787                         b.Bgen   = GEN;
788                         b.Bkill2 = Kr;
789                         b.Bgen2  = Gr;
790                     }
791                 }
792                 else
793                 {
794                     accumaecp(b.Bgen,b.Bkill,e);
795                     b.Bgen2 = vec_clone(b.Bgen);
796                     b.Bkill2 = vec_clone(b.Bkill);
797                 }
798                 b.Bout2 = vec_calloc(go.expnod.length);
799                 break;
800 
801             case BCasm:
802                 vec_set(b.Bkill);              // KILL everything
803                 vec_clear(b.Bgen);             // GEN nothing
804                 break;
805 
806             default:
807                 // calculate GEN & KILL vectors
808                 if (b.Belem)
809                     accumaecp(b.Bgen,b.Bkill,b.Belem);
810                 break;
811         }
812         static if (0)
813         {
814             printf("block %d Bgen ",i); vec_println(b.Bgen);
815             printf("       Bkill "); vec_println(b.Bkill);
816         }
817         b.Bin = vec_calloc(go.expnod.length);
818         b.Bout = vec_calloc(go.expnod.length);
819     }
820 }
821 
822 /********************************
823  * Compute defkill, starkill and vptrkill vectors.
824  *      starkill:       set of expressions killed when a variable is
825  *                      changed that somebody could be pointing to.
826  *                      (not needed for cp)
827  *                      starkill is a subset of defkill.
828  *      defkill:        set of expressions killed by an ambiguous
829  *                      definition.
830  *      vptrkill:       set of expressions killed by an access to a vptr.
831  */
832 
833 private void defstarkill()
834 {
835     vec_free(go.vptrkill);
836     vec_free(go.defkill);
837     vec_free(go.starkill);             /* dump any existing ones       */
838     go.defkill = vec_calloc(go.exptop);
839     if (flowxx != CP)
840     {
841         go.starkill = vec_calloc(go.exptop);      /* and create new ones  */
842         go.vptrkill = vec_calloc(go.exptop);      /* and create new ones  */
843     }
844     else /* CP */
845     {
846         go.starkill = null;
847         go.vptrkill = null;
848     }
849 
850     if (!go.exptop)
851         return;
852 
853     if (flowxx == CP)
854     {
855         foreach (uint i; 1 .. go.exptop)
856         {
857             elem *n = go.expnod[i];
858             const op = n.Eoper;
859             assert(op == OPeq || op == OPstreq);
860             assert(n.EV.E1.Eoper==OPvar && n.EV.E2.Eoper==OPvar);
861 
862             // Set bit in defkill if either the left or the
863             // right variable is killed by an ambiguous def.
864 
865             if (Symbol_isAffected(*n.EV.E1.EV.Vsym) ||
866                 Symbol_isAffected(*n.EV.E2.EV.Vsym))
867             {
868                 vec_setbit(i,go.defkill);
869             }
870         }
871     }
872     else
873     {
874         foreach (uint i; 1 .. go.exptop)
875         {
876             elem *n = go.expnod[i];
877             const op = n.Eoper;
878             switch (op)
879             {
880                 case OPvar:
881                     if (Symbol_isAffected(*n.EV.Vsym))
882                         vec_setbit(i,go.defkill);
883                     break;
884 
885                 case OPind:         // if a 'starred' ref
886                     if (tybasic(n.EV.E1.Ety) == TYimmutPtr)
887                         break;
888                     goto case OPstrlen;
889 
890                 case OPstrlen:
891                 case OPstrcmp:
892                 case OPmemcmp:
893                 case OPbt:          // OPbt is like OPind
894                     vec_setbit(i,go.defkill);
895                     vec_setbit(i,go.starkill);
896                     break;
897 
898                 case OPvp_fp:
899                 case OPcvp_fp:
900                     vec_setbit(i,go.vptrkill);
901                     goto Lunary;
902 
903                 default:
904                     if (OTunary(op))
905                     {
906                     Lunary:
907                         if (vec_testbit(n.EV.E1.Eexp,go.defkill))
908                                 vec_setbit(i,go.defkill);
909                         if (vec_testbit(n.EV.E1.Eexp,go.starkill))
910                                 vec_setbit(i,go.starkill);
911                     }
912                     else if (OTbinary(op))
913                     {
914                         if (vec_testbit(n.EV.E1.Eexp,go.defkill) ||
915                             vec_testbit(n.EV.E2.Eexp,go.defkill))
916                                 vec_setbit(i,go.defkill);
917                         if (vec_testbit(n.EV.E1.Eexp,go.starkill) ||
918                             vec_testbit(n.EV.E2.Eexp,go.starkill))
919                                 vec_setbit(i,go.starkill);
920                     }
921                     break;
922             }
923         }
924     }
925 }
926 
927 /********************************
928  * Compute GEN and KILL vectors only for AEs.
929  * defkill and starkill are assumed to be already set up correctly.
930  * go.expnod[] is assumed to be set up correctly.
931  */
932 
933 void genkillae()
934 {
935     flowxx = AE;
936     assert(go.exptop > 1);
937     foreach (b; dfo[])
938     {
939         assert(b);
940         vec_clear(b.Bgen);
941         vec_clear(b.Bkill);
942         if (b.Belem)
943             accumaecp(b.Bgen,b.Bkill,b.Belem);
944         else if (b.BC == BCasm)
945         {
946             vec_set(b.Bkill);          // KILL everything
947             vec_clear(b.Bgen);         // GEN nothing
948         }
949     }
950 }
951 
952 /************************************
953  * Allocate and compute KILL and GEN vectors for a elem.
954  */
955 
956 private void aecpelem(vec_t *pgen,vec_t *pkill, elem *n)
957 {
958     *pgen = vec_calloc(go.exptop);
959     *pkill = vec_calloc(go.exptop);
960     if (n)
961     {
962         if (flowxx == VBE)
963             accumvbe(*pgen,*pkill,n);
964         else
965             accumaecp(*pgen,*pkill,n);
966     }
967 }
968 
969 /*************************************
970  * Accumulate GEN and KILL sets for AEs and CPs for this elem.
971  */
972 
973 private __gshared
974 {
975     vec_t GEN;       // use static copies to save on parameter passing
976     vec_t KILL;
977 }
978 
979 private void accumaecp(vec_t g,vec_t k,elem *n)
980 {   vec_t GENsave,KILLsave;
981 
982     assert(g && k);
983     GENsave = GEN;
984     KILLsave = KILL;
985     GEN = g;
986     KILL = k;
987     accumaecpx(n);
988     GEN = GENsave;
989     KILL = KILLsave;
990 }
991 
992 private void accumaecpx(elem *n)
993 {
994     elem *t;
995 
996     assert(n);
997     elem_debug(n);
998     const op = n.Eoper;
999 
1000     switch (op)
1001     {
1002         case OPvar:
1003         case OPconst:
1004         case OPrelconst:
1005             if ((flowxx == AE) && n.Eexp)
1006             {   uint b;
1007                 debug assert(go.expnod[n.Eexp] == n);
1008                 b = n.Eexp;
1009                 vec_setclear(b,GEN,KILL);
1010             }
1011             return;
1012 
1013         case OPcolon:
1014         case OPcolon2:
1015         {   vec_t Gl,Kl,Gr,Kr;
1016 
1017             aecpelem(&Gl,&Kl,n.EV.E1);
1018             aecpelem(&Gr,&Kr,n.EV.E2);
1019 
1020             /* KILL |= Kl | Kr           */
1021             /* GEN =((GEN - Kl) | Gl) &  */
1022             /*     ((GEN - Kr) | Gr)     */
1023 
1024             vec_orass(KILL,Kl);
1025             vec_orass(KILL,Kr);
1026 
1027             vec_sub(Kl,GEN,Kl);
1028             vec_sub(Kr,GEN,Kr);
1029             vec_orass(Kl,Gl);
1030             vec_orass(Kr,Gr);
1031             vec_and(GEN,Kl,Kr);
1032 
1033             vec_free(Gl);
1034             vec_free(Gr);
1035             vec_free(Kl);
1036             vec_free(Kr);
1037             break;
1038         }
1039 
1040         case OPandand:
1041         case OPoror:
1042         {   vec_t Gr,Kr;
1043 
1044             accumaecpx(n.EV.E1);
1045             aecpelem(&Gr,&Kr,n.EV.E2);
1046 
1047             if (el_returns(n.EV.E2))
1048             {
1049                 // KILL |= Kr
1050                 // GEN &= (GEN - Kr) | Gr
1051 
1052                 vec_orass(KILL,Kr);
1053                 vec_sub(Kr,GEN,Kr);
1054                 vec_orass(Kr,Gr);
1055                 vec_andass(GEN,Kr);
1056             }
1057 
1058             vec_free(Gr);
1059             vec_free(Kr);
1060             break;
1061         }
1062 
1063         case OPddtor:
1064         case OPasm:
1065             assert(!n.Eexp);                   // no ASM available expressions
1066             vec_set(KILL);                      // KILL everything
1067             vec_clear(GEN);                     // GEN nothing
1068             return;
1069 
1070         case OPeq:
1071         case OPstreq:
1072             accumaecpx(n.EV.E2);
1073             goto case OPnegass;
1074 
1075         case OPnegass:
1076             accumaecpx(n.EV.E1);
1077             t = n.EV.E1;
1078             break;
1079 
1080         case OPvp_fp:
1081         case OPcvp_fp:                          // if vptr access
1082             if ((flowxx == AE) && n.Eexp)
1083                 vec_orass(KILL,go.vptrkill);       // kill all other vptr accesses
1084             break;
1085 
1086         case OPprefetch:
1087             accumaecpx(n.EV.E1);                  // don't check E2
1088             break;
1089 
1090         default:
1091             if (OTunary(op))
1092             {
1093         case OPind:                             // most common unary operator
1094                 accumaecpx(n.EV.E1);
1095                 debug assert(!OTassign(op));
1096             }
1097             else if (OTbinary(op))
1098             {
1099                 if (OTrtol(op) && ERTOL(n))
1100                 {
1101                     accumaecpx(n.EV.E2);
1102                     accumaecpx(n.EV.E1);
1103                 }
1104                 else
1105                 {
1106                     accumaecpx(n.EV.E1);
1107                     accumaecpx(n.EV.E2);
1108                 }
1109                 if (OTassign(op))               // if assignment operator
1110                     t = n.EV.E1;
1111             }
1112             break;
1113     }
1114 
1115 
1116     /* Do copy propagation stuff first  */
1117 
1118     if (flowxx == CP)
1119     {
1120         if (!OTdef(op))                         /* if not def elem      */
1121             return;
1122         if (!Eunambig(n))                       /* if ambiguous def elem */
1123         {
1124             vec_orass(KILL,go.defkill);
1125             vec_subass(GEN,go.defkill);
1126         }
1127         else                                    /* unambiguous def elem */
1128         {
1129             assert(t.Eoper == OPvar);
1130             Symbol* s = t.EV.Vsym;                  // ptr to var being def'd
1131             foreach (uint i; 1 .. go.exptop)        // for each ae elem
1132             {
1133                 elem *e = go.expnod[i];
1134 
1135                 /* If it could be changed by the definition,     */
1136                 /* set bit in KILL.                              */
1137 
1138                 if (e.EV.E1.EV.Vsym == s || e.EV.E2.EV.Vsym == s)
1139                     vec_setclear(i,KILL,GEN);
1140             }
1141         }
1142 
1143         /* GEN CP elems */
1144         if (n.Eexp)
1145         {
1146             const uint b = n.Eexp;
1147             vec_setclear(b,GEN,KILL);
1148         }
1149 
1150         return;
1151     }
1152 
1153     /* Else Available Expression stuff  */
1154 
1155     if (n.Eexp)
1156     {
1157         const uint b = n.Eexp;             // add elem to GEN
1158         assert(go.expnod[b] == n);
1159         vec_setclear(b,GEN,KILL);
1160     }
1161     else if (OTdef(op))                         /* else if definition elem */
1162     {
1163         if (!Eunambig(n))                       /* if ambiguous def elem */
1164         {
1165             vec_orass(KILL,go.defkill);
1166             vec_subass(GEN,go.defkill);
1167             if (OTcalldef(op))
1168             {
1169                 vec_orass(KILL,go.vptrkill);
1170                 vec_subass(GEN,go.vptrkill);
1171             }
1172         }
1173         else                                    /* unambiguous def elem */
1174         {
1175             assert(t.Eoper == OPvar);
1176             Symbol* s = t.EV.Vsym;             // idx of var being def'd
1177             if (!(s.Sflags & SFLunambig))
1178             {
1179                 vec_orass(KILL,go.starkill);       /* kill all 'starred' refs */
1180                 vec_subass(GEN,go.starkill);
1181             }
1182             foreach (uint i; 1 .. go.exptop)        // for each ae elem
1183             {
1184                 elem *e = go.expnod[i];
1185                 const int eop = e.Eoper;
1186 
1187                 /* If it could be changed by the definition,     */
1188                 /* set bit in KILL.                              */
1189                 if (eop == OPvar)
1190                 {
1191                     if (e.EV.Vsym != s)
1192                         continue;
1193                 }
1194                 else if (OTunary(eop))
1195                 {
1196                     if (!vec_testbit(e.EV.E1.Eexp,KILL))
1197                         continue;
1198                 }
1199                 else if (OTbinary(eop))
1200                 {
1201                     if (!vec_testbit(e.EV.E1.Eexp,KILL) &&
1202                         !vec_testbit(e.EV.E2.Eexp,KILL))
1203                         continue;
1204                 }
1205                 else
1206                         continue;
1207 
1208                 vec_setclear(i,KILL,GEN);
1209             }
1210         }
1211 
1212         /* GEN the lvalue of an assignment operator      */
1213         if (OTassign(op) && !OTpost(op) && t.Eexp)
1214         {
1215             uint b = t.Eexp;
1216 
1217             vec_setclear(b,GEN,KILL);
1218         }
1219     }
1220 }
1221 
1222 /************************* LIVE VARIABLES **********************/
1223 
1224 /*********************************
1225  * Do live variable analysis (LVs).
1226  * A variable is 'live' at some point if there is a
1227  * subsequent use of it before a redefinition.
1228  * Binlv = the set of variables live at the beginning of B.
1229  * Boutlv = the set of variables live at the end of B.
1230  * Bgen = set of variables used before any definition in B.
1231  * Bkill = set of variables unambiguously defined before
1232  *       any use in B.
1233  * Note that Bgen & Bkill = 0.
1234  */
1235 
1236 void flowlv()
1237 {
1238     lvgenkill();            /* compute Bgen and Bkill for LVs.      */
1239     //assert(globsym.top);  /* should be at least some symbols      */
1240 
1241     /* Create a vector of all the variables that are live on exit   */
1242     /* from the function.                                           */
1243 
1244     vec_t livexit = vec_calloc(globsym.top);
1245     foreach (uint i; 0 .. globsym.top)
1246     {
1247         if (globsym.tab[i].Sflags & SFLlivexit)
1248             vec_setbit(i,livexit);
1249     }
1250 
1251     /* The transfer equation is:                            */
1252     /*      Bin = (Bout - Bkill) | Bgen                     */
1253     /*      Bout = union of Bin of all successors to B.     */
1254     /* Using Ullman's algorithm:                            */
1255 
1256     foreach (b; dfo[])
1257     {
1258         vec_copy(b.Binlv, b.Bgen);   // Binlv = Bgen
1259     }
1260 
1261     vec_t tmp = vec_calloc(globsym.top);
1262     uint cnt = 0;
1263     bool anychng;
1264     do
1265     {
1266         anychng = false;
1267 
1268         /* For each block B in reverse DFO order        */
1269         foreach_reverse (b; dfo[])
1270         {
1271             /* Bout = union of Bins of all successors to B. */
1272             bool first = true;
1273             foreach (bl; ListRange(b.Bsucc))
1274             {
1275                 const inlv = list_block(bl).Binlv;
1276                 if (first)
1277                     vec_copy(b.Boutlv, inlv);
1278                 else
1279                     vec_orass(b.Boutlv, inlv);
1280                 first = false;
1281             }
1282 
1283             if (first) /* no successors, Boutlv = livexit */
1284             {   //assert(b.BC==BCret||b.BC==BCretexp||b.BC==BCexit);
1285                 vec_copy(b.Boutlv,livexit);
1286             }
1287 
1288             /* Bin = (Bout - Bkill) | Bgen                  */
1289             vec_sub(tmp,b.Boutlv,b.Bkill);
1290             vec_orass(tmp,b.Bgen);
1291             if (!anychng)
1292                 anychng = !vec_equal(tmp,b.Binlv);
1293             vec_copy(b.Binlv,tmp);
1294         }
1295         cnt++;
1296         assert(cnt < 50);
1297     } while (anychng);
1298 
1299     vec_free(tmp);
1300     vec_free(livexit);
1301 
1302     static if (0)
1303     {
1304         printf("Live variables\n");
1305         foreach (i, b; dfo[])
1306         {
1307             printf("B%d IN\t", cast(int)i);
1308             vec_println(b.Binlv);
1309             printf("B%d GEN\t", cast(int)i);
1310             vec_println(b.Bgen);
1311             printf("  KILL\t");
1312             vec_println(b.Bkill);
1313             printf("  OUT\t");
1314             vec_println(b.Boutlv);
1315         }
1316     }
1317 }
1318 
1319 /***********************************
1320  * Compute Bgen and Bkill for LVs.
1321  * Allocate Binlv and Boutlv vectors.
1322  */
1323 
1324 private void lvgenkill()
1325 {
1326     /* Compute ambigsym, a vector of all variables that could be    */
1327     /* referenced by a *e or a call.                                */
1328 
1329     assert(ambigsym == null);
1330     ambigsym = vec_calloc(globsym.top);
1331     foreach (uint i; 0 .. globsym.top)
1332         if (!(globsym.tab[i].Sflags & SFLunambig))
1333             vec_setbit(i,ambigsym);
1334 
1335     foreach (b; dfo[])
1336     {
1337         vec_free(b.Bgen);
1338         vec_free(b.Bkill);
1339         lvelem(&(b.Bgen),&(b.Bkill),b.Belem);
1340         if (b.BC == BCasm)
1341         {
1342             vec_set(b.Bgen);
1343             vec_clear(b.Bkill);
1344         }
1345 
1346         vec_free(b.Binlv);
1347         vec_free(b.Boutlv);
1348         b.Binlv = vec_calloc(globsym.top);
1349         b.Boutlv = vec_calloc(globsym.top);
1350     }
1351 
1352     vec_free(ambigsym);             /* dump any existing one        */
1353     ambigsym = null;
1354 }
1355 
1356 /*****************************
1357  * Allocate and compute KILL and GEN for live variables.
1358  */
1359 
1360 private void lvelem(vec_t *pgen,vec_t *pkill,elem *n)
1361 {
1362     *pgen = vec_calloc(globsym.top);
1363     *pkill = vec_calloc(globsym.top);
1364     if (n && globsym.top)
1365         accumlv(*pgen,*pkill,n);
1366 }
1367 
1368 /**********************************************
1369  * Accumulate GEN and KILL sets for LVs for this elem.
1370  */
1371 
1372 private void accumlv(vec_t GEN,vec_t KILL,elem *n)
1373 {
1374     assert(GEN && KILL && n);
1375 
1376     while (1)
1377     {
1378         elem_debug(n);
1379         const op = n.Eoper;
1380         switch (op)
1381         {
1382             case OPvar:
1383                 if (symbol_isintab(n.EV.Vsym))
1384                 {
1385                     SYMIDX si = n.EV.Vsym.Ssymnum;
1386 
1387                     assert(cast(uint)si < globsym.top);
1388                     if (!vec_testbit(si,KILL))  // if not in KILL
1389                         vec_setbit(si,GEN);     // put in GEN
1390                 }
1391                 break;
1392 
1393             case OPcolon:
1394             case OPcolon2:
1395             {
1396                 vec_t Gl,Kl,Gr,Kr;
1397                 lvelem(&Gl,&Kl,n.EV.E1);
1398                 lvelem(&Gr,&Kr,n.EV.E2);
1399 
1400                 /* GEN |= (Gl | Gr) - KILL      */
1401                 /* KILL |= (Kl & Kr) - GEN      */
1402 
1403                 vec_orass(Gl,Gr);
1404                 vec_subass(Gl,KILL);
1405                 vec_orass(GEN,Gl);
1406                 vec_andass(Kl,Kr);
1407                 vec_subass(Kl,GEN);
1408                 vec_orass(KILL,Kl);
1409 
1410                 vec_free(Gl);
1411                 vec_free(Gr);
1412                 vec_free(Kl);
1413                 vec_free(Kr);
1414                 break;
1415             }
1416 
1417             case OPandand:
1418             case OPoror:
1419             {
1420                 vec_t Gr,Kr;
1421                 accumlv(GEN,KILL,n.EV.E1);
1422                 lvelem(&Gr,&Kr,n.EV.E2);
1423 
1424                 /* GEN |= Gr - KILL     */
1425                 /* KILL |= 0            */
1426 
1427                 vec_subass(Gr,KILL);
1428                 vec_orass(GEN,Gr);
1429 
1430                 vec_free(Gr);
1431                 vec_free(Kr);
1432                 break;
1433             }
1434 
1435             case OPasm:
1436                 vec_set(GEN);           /* GEN everything not already KILLed */
1437                 vec_subass(GEN,KILL);
1438                 break;
1439 
1440             case OPcall:
1441             case OPcallns:
1442             case OPstrcpy:
1443             case OPmemcpy:
1444             case OPmemset:
1445                 debug assert(OTrtol(op));
1446                 accumlv(GEN,KILL,n.EV.E2);
1447                 accumlv(GEN,KILL,n.EV.E1);
1448                 goto L1;
1449 
1450             case OPstrcat:
1451                 debug assert(!OTrtol(op));
1452                 accumlv(GEN,KILL,n.EV.E1);
1453                 accumlv(GEN,KILL,n.EV.E2);
1454             L1:
1455                 vec_orass(GEN,ambigsym);
1456                 vec_subass(GEN,KILL);
1457                 break;
1458 
1459             case OPeq:
1460             case OPstreq:
1461             {
1462                 /* Avoid GENing the lvalue of an =      */
1463                 accumlv(GEN,KILL,n.EV.E2);
1464                 elem *t = n.EV.E1;
1465                 if (t.Eoper != OPvar)
1466                     accumlv(GEN,KILL,t.EV.E1);
1467                 else /* unambiguous assignment */
1468                 {
1469                     Symbol* s = t.EV.Vsym;
1470                     symbol_debug(s);
1471 
1472                     uint tsz = tysize(t.Ety);
1473                     if (op == OPstreq)
1474                         tsz = cast(uint)type_size(n.ET);
1475 
1476                     /* if not GENed already, KILL it */
1477                     if (symbol_isintab(s) &&
1478                         !vec_testbit(s.Ssymnum,GEN) &&
1479                         t.EV.Voffset == 0 &&
1480                         tsz == type_size(s.Stype)
1481                        )
1482                     {
1483                         // printf("%s\n", s.Sident);
1484                         assert(cast(uint)s.Ssymnum < globsym.top);
1485                         vec_setbit(s.Ssymnum,KILL);
1486                     }
1487                 }
1488                 break;
1489             }
1490 
1491             case OPbt:                          // much like OPind
1492                 accumlv(GEN,KILL,n.EV.E1);
1493                 accumlv(GEN,KILL,n.EV.E2);
1494                 vec_orass(GEN,ambigsym);
1495                 vec_subass(GEN,KILL);
1496                 break;
1497 
1498             case OPind:
1499             case OPucall:
1500             case OPucallns:
1501             case OPstrlen:
1502                 accumlv(GEN,KILL,n.EV.E1);
1503 
1504                 /* If it was a *p elem, set bits in GEN for all symbols */
1505                 /* it could have referenced, but only if bits in KILL   */
1506                 /* are not already set.                                 */
1507 
1508                 vec_orass(GEN,ambigsym);
1509                 vec_subass(GEN,KILL);
1510                 break;
1511 
1512             default:
1513                 if (OTunary(op))
1514                 {
1515                     n = n.EV.E1;
1516                     continue;
1517                 }
1518                 else if (OTrtol(op) && ERTOL(n))
1519                 {
1520                     accumlv(GEN,KILL,n.EV.E2);
1521 
1522                     /* Note that lvalues of op=,i++,i-- elems */
1523                     /* are GENed.                               */
1524                     n = n.EV.E1;
1525                     continue;
1526                 }
1527                 else if (OTbinary(op))
1528                 {
1529                     accumlv(GEN,KILL,n.EV.E1);
1530                     n = n.EV.E2;
1531                     continue;
1532                 }
1533                 break;
1534         }
1535         break;
1536     }
1537 }
1538 
1539 /********************* VERY BUSY EXPRESSIONS ********************/
1540 
1541 /**********************************************
1542  * Compute very busy expressions(VBEs).
1543  * That is,expressions that are evaluated along
1544  * separate paths.
1545  * Bin = the set of VBEs at the beginning of B.
1546  * Bout = the set of VBEs at the end of B.
1547  * Bgen = set of expressions X+Y such that X+Y is
1548  *      evaluated before any def of X or Y.
1549  * Bkill = set of expressions X+Y such that X or Y could
1550  *      be defined before X+Y is computed.
1551  * Note that gen and kill are mutually exclusive.
1552  */
1553 
1554 void flowvbe()
1555 {
1556     flowxx = VBE;
1557     aecpgenkill(go);          // compute Bgen and Bkill for VBEs
1558     if (go.exptop <= 1)     /* if no candidates for VBEs            */
1559         return;
1560 
1561     /*foreach (uint i; 0 .. go.exptop)
1562             printf("go.expnod[%d] = 0x%x\n",i,go.expnod[i]);*/
1563 
1564     /* The transfer equation is:                    */
1565     /*      Bout = & Bin(all successors S of B)     */
1566     /*      Bin =(Bout - Bkill) | Bgen              */
1567     /* Using Ullman's algorithm:                    */
1568 
1569     /*printf("defkill = "); vec_println(go.defkill);
1570     printf("starkill = "); vec_println(go.starkill);*/
1571 
1572     foreach (b; dfo[])
1573     {
1574         /*printf("block %p\n",b);
1575         printf("Bgen = "); vec_println(b.Bgen);
1576         printf("Bkill = "); vec_println(b.Bkill);*/
1577 
1578         if (b.BC == BCret || b.BC == BCretexp || b.BC == BCexit)
1579             vec_clear(b.Bout);
1580         else
1581             vec_set(b.Bout);
1582 
1583         /* Bin = (Bout - Bkill) | Bgen  */
1584         vec_sub(b.Bin,b.Bout,b.Bkill);
1585         vec_orass(b.Bin,b.Bgen);
1586     }
1587 
1588     vec_t tmp = vec_calloc(go.exptop);
1589     bool anychng;
1590     do
1591     {
1592         anychng = false;
1593 
1594         /* for all blocks except return blocks in reverse dfo order */
1595         foreach_reverse (b; dfo[])
1596         {
1597             if (b.BC == BCret || b.BC == BCretexp || b.BC == BCexit)
1598                 continue;
1599 
1600             /* Bout = & of Bin of all successors */
1601             bool first = true;
1602             foreach (bl; ListRange(b.Bsucc))
1603             {
1604                 const vin = list_block(bl).Bin;
1605                 if (first)
1606                     vec_copy(b.Bout, vin);
1607                 else
1608                     vec_andass(b.Bout, vin);
1609 
1610                 first = false;
1611             }
1612 
1613             assert(!first);     // must have successors
1614 
1615             /* Bin = (Bout - Bkill) | Bgen  */
1616             vec_sub(tmp,b.Bout,b.Bkill);
1617             vec_orass(tmp,b.Bgen);
1618             if (!anychng)
1619                 anychng = !vec_equal(tmp,b.Bin);
1620             vec_copy(b.Bin,tmp);
1621         }
1622     } while (anychng);      /* while any changes occurred to any Bin */
1623     vec_free(tmp);
1624 }
1625 
1626 /*************************************
1627  * Accumulate GEN and KILL sets for VBEs for this elem.
1628  */
1629 
1630 private void accumvbe(vec_t GEN,vec_t KILL,elem *n)
1631 {
1632     elem *t;
1633 
1634     assert(GEN && KILL && n);
1635     const op = n.Eoper;
1636 
1637     switch (op)
1638     {
1639         case OPcolon:
1640         case OPcolon2:
1641         {
1642             vec_t Gl,Gr,Kl,Kr;
1643 
1644             aecpelem(&Gl,&Kl,n.EV.E1);
1645             aecpelem(&Gr,&Kr,n.EV.E2);
1646 
1647             /* GEN |=((Gr - Kl) | (Gl - Kr)) - KILL */
1648             vec_subass(Gr,Kl);
1649             vec_subass(Gl,Kr);
1650             vec_orass(Gr,Gl);
1651             vec_subass(Gr,KILL);
1652             vec_orass(GEN,Gr);
1653 
1654             /* KILL |=(Kl | Kr) - GEN       */
1655             vec_orass(Kl,Kr);
1656             vec_subass(Kl,GEN);
1657             vec_orass(KILL,Kl);
1658 
1659             vec_free(Gl);
1660             vec_free(Kl);
1661             vec_free(Gr);
1662             vec_free(Kr);
1663             break;
1664         }
1665 
1666         case OPandand:
1667         case OPoror:
1668             accumvbe(GEN,KILL,n.EV.E1);
1669             /* WARNING: just so happens that it works this way.     */
1670             /* Be careful about (b+c)||(b+c) being VBEs, only the   */
1671             /* first should be GENed. Doing things this way instead */
1672             /* of (GEN |= Gr - KILL) and (KILL |= Kr - GEN) will    */
1673             /* ensure this.                                         */
1674             accumvbe(GEN,KILL,n.EV.E2);
1675             break;
1676 
1677         case OPnegass:
1678             t = n.EV.E1;
1679             if (t.Eoper != OPvar)
1680             {
1681                 accumvbe(GEN,KILL,t.EV.E1);
1682                 if (OTbinary(t.Eoper))
1683                     accumvbe(GEN,KILL,t.EV.E2);
1684             }
1685             break;
1686 
1687         case OPcall:
1688         case OPcallns:
1689             accumvbe(GEN,KILL,n.EV.E2);
1690             goto case OPucall;
1691 
1692         case OPucall:
1693         case OPucallns:
1694             t = n.EV.E1;
1695             // Do not VBE indirect function calls
1696             if (t.Eoper == OPind)
1697                 t = t.EV.E1;
1698             accumvbe(GEN,KILL,t);
1699             break;
1700 
1701         case OPasm:                 // if the dreaded OPasm elem
1702             vec_set(KILL);          // KILL everything
1703             vec_subass(KILL,GEN);   // except for GENed stuff
1704             return;
1705 
1706         default:
1707             if (OTunary(op))
1708             {
1709                 t = n.EV.E1;
1710                 accumvbe(GEN,KILL,t);
1711             }
1712             else if (ERTOL(n))
1713             {
1714                 accumvbe(GEN,KILL,n.EV.E2);
1715                 t = n.EV.E1;
1716                 // do not GEN the lvalue of an assignment op
1717                 if (OTassign(op))
1718                 {
1719                     t = n.EV.E1;
1720                     if (t.Eoper != OPvar)
1721                     {
1722                         accumvbe(GEN,KILL,t.EV.E1);
1723                         if (OTbinary(t.Eoper))
1724                             accumvbe(GEN,KILL,t.EV.E2);
1725                     }
1726                 }
1727                 else
1728                     accumvbe(GEN,KILL,t);
1729             }
1730             else if (OTbinary(op))
1731             {
1732                 /* do not GEN the lvalue of an assignment op    */
1733                 if (OTassign(op))
1734                 {
1735                     t = n.EV.E1;
1736                     if (t.Eoper != OPvar)
1737                     {
1738                         accumvbe(GEN,KILL,t.EV.E1);
1739                         if (OTbinary(t.Eoper))
1740                             accumvbe(GEN,KILL,t.EV.E2);
1741                     }
1742                 }
1743                 else
1744                     accumvbe(GEN,KILL,n.EV.E1);
1745                 accumvbe(GEN,KILL,n.EV.E2);
1746             }
1747             break;
1748     }
1749 
1750     if (n.Eexp)                    /* if a vbe elem                */
1751     {
1752         const int ne = n.Eexp;
1753 
1754         assert(go.expnod[ne] == n);
1755         if (!vec_testbit(ne,KILL))      /* if not already KILLed */
1756         {
1757             /* GEN this expression only if it hasn't        */
1758             /* already been GENed in this block.            */
1759             /* (Don't GEN common subexpressions.)           */
1760             if (vec_testbit(ne,GEN))
1761                 vec_clearbit(ne,GEN);
1762             else
1763             {
1764                 vec_setbit(ne,GEN); /* GEN this expression  */
1765                 /* GEN all identical expressions            */
1766                 /* (operators only, as there is no point    */
1767                 /* to hoisting out variables and constants) */
1768                 if (!OTleaf(op))
1769                 {
1770                     foreach (uint i; 1 .. go.exptop)
1771                     {
1772                         if (op == go.expnod[i].Eoper &&
1773                             i != ne &&
1774                             el_match(n,go.expnod[i]))
1775                         {
1776                             vec_setbit(i,GEN);
1777                             assert(!vec_testbit(i,KILL));
1778                         }
1779                     }
1780                 }
1781             }
1782         }
1783         if (op == OPvp_fp || op == OPcvp_fp)
1784         {
1785             vec_orass(KILL,go.vptrkill);   /* KILL all vptr accesses */
1786             vec_subass(KILL,GEN);          /* except for GENed stuff */
1787         }
1788     }
1789     else if (OTdef(op))             /* if definition elem           */
1790     {
1791         if (!Eunambig(n))           /* if ambiguous definition      */
1792         {
1793             vec_orass(KILL,go.defkill);
1794             if (OTcalldef(op))
1795                 vec_orass(KILL,go.vptrkill);
1796         }
1797         else                    /* unambiguous definition       */
1798         {
1799             assert(t.Eoper == OPvar);
1800             Symbol* s = t.EV.Vsym;  // ptr to var being def'd
1801             if (!(s.Sflags & SFLunambig))
1802                 vec_orass(KILL,go.starkill);/* kill all 'starred' refs */
1803             foreach (uint i; 1 .. go.exptop)        // for each vbe elem
1804             {
1805                 elem *e = go.expnod[i];
1806                 uint eop = e.Eoper;
1807 
1808                 /* If it could be changed by the definition,     */
1809                 /* set bit in KILL.                              */
1810                 if (eop == OPvar)
1811                 {
1812                     if (e.EV.Vsym != s)
1813                         continue;
1814                 }
1815                 else if (OTbinary(eop))
1816                 {
1817                     if (!vec_testbit(e.EV.E1.Eexp,KILL) &&
1818                         !vec_testbit(e.EV.E2.Eexp,KILL))
1819                         continue;
1820                 }
1821                 else if (OTunary(eop))
1822                 {
1823                     if (!vec_testbit(e.EV.E1.Eexp,KILL))
1824                         continue;
1825                 }
1826                 else /* OPconst or OPrelconst or OPstring */
1827                     continue;
1828 
1829                 vec_setbit(i,KILL);     // KILL it
1830             } /* for */
1831         } /* if */
1832         vec_subass(KILL,GEN);
1833     } /* if */
1834 }
1835 
1836 }