1 
2 /* Compiler implementation of the D programming language
3  * Copyright (C) 1999-2019 by The D Language Foundation, All Rights Reserved
4  * written by Walter Bright
5  * http://www.digitalmars.com
6  * Distributed under the Boost Software License, Version 1.0
7  * http://www.boost.org/LICENSE_1_0.txt
8  * https://github.com/D-Programming-Language/dmd/blob/master/src/optimize.c
9  */
10 
11 #include "root/dsystem.h"
12 
13 #include "root/checkedint.h"
14 #include "lexer.h"
15 #include "mtype.h"
16 #include "expression.h"
17 #include "declaration.h"
18 #include "aggregate.h"
19 #include "init.h"
20 #include "enum.h"
21 #include "ctfe.h"
22 #include "errors.h"
23 
24 Expression *semantic(Expression *e, Scope *sc);
25 
26 /*************************************
27  * If variable has a const initializer,
28  * return that initializer.
29  */
30 
expandVar(int result,VarDeclaration * v)31 Expression *expandVar(int result, VarDeclaration *v)
32 {
33     //printf("expandVar(result = %d, v = %p, %s)\n", result, v, v ? v->toChars() : "null");
34 
35     Expression *e = NULL;
36     if (!v)
37         return e;
38     if (!v->originalType && v->semanticRun < PASSsemanticdone) // semantic() not yet run
39         v->semantic(NULL);
40 
41     if (v->isConst() || v->isImmutable() || v->storage_class & STCmanifest)
42     {
43         if (!v->type)
44         {
45             return e;
46         }
47         Type *tb = v->type->toBasetype();
48         if (v->storage_class & STCmanifest ||
49             v->type->toBasetype()->isscalar() ||
50             ((result & WANTexpand) && (tb->ty != Tsarray && tb->ty != Tstruct))
51            )
52         {
53             if (v->_init)
54             {
55                 if (v->inuse)
56                 {
57                     if (v->storage_class & STCmanifest)
58                     {
59                         v->error("recursive initialization of constant");
60                         goto Lerror;
61                     }
62                     goto L1;
63                 }
64                 Expression *ei = v->getConstInitializer();
65                 if (!ei)
66                 {
67                     if (v->storage_class & STCmanifest)
68                     {
69                         v->error("enum cannot be initialized with %s", v->_init->toChars());
70                         goto Lerror;
71                     }
72                     goto L1;
73                 }
74                 if (ei->op == TOKconstruct || ei->op == TOKblit)
75                 {
76                     AssignExp *ae = (AssignExp *)ei;
77                     ei = ae->e2;
78                     if (ei->isConst() == 1)
79                     {
80                     }
81                     else if (ei->op == TOKstring)
82                     {
83                         // Bugzilla 14459: We should not constfold the string literal
84                         // if it's typed as a C string, because the value expansion
85                         // will drop the pointer identity.
86                         if (!(result & WANTexpand) && ei->type->toBasetype()->ty == Tpointer)
87                             goto L1;
88                     }
89                     else
90                         goto L1;
91 
92                     if (ei->type == v->type)
93                     {
94                         // const variable initialized with const expression
95                     }
96                     else if (ei->implicitConvTo(v->type) >= MATCHconst)
97                     {
98                         // const var initialized with non-const expression
99                         ei = ei->implicitCastTo(NULL, v->type);
100                         ei = semantic(ei, NULL);
101                     }
102                     else
103                         goto L1;
104                 }
105                 else if (!(v->storage_class & STCmanifest) &&
106                          ei->isConst() != 1 && ei->op != TOKstring &&
107                          ei->op != TOKaddress)
108                 {
109                     goto L1;
110                 }
111                 if (!ei->type)
112                 {
113                     goto L1;
114                 }
115                 else
116                 {
117                     // Should remove the copy() operation by
118                     // making all mods to expressions copy-on-write
119                     e = ei->copy();
120                 }
121             }
122             else
123             {
124                 goto L1;
125             }
126             if (e->type != v->type)
127             {
128                 e = e->castTo(NULL, v->type);
129             }
130             v->inuse++;
131             e = e->optimize(result);
132             v->inuse--;
133         }
134     }
135 L1:
136     //if (e) printf("\te = %p, %s, e->type = %d, %s\n", e, e->toChars(), e->type->ty, e->type->toChars());
137     return e;
138 
139 Lerror:
140     return new ErrorExp();
141 }
142 
143 
fromConstInitializer(int result,Expression * e1)144 Expression *fromConstInitializer(int result, Expression *e1)
145 {
146     //printf("fromConstInitializer(result = %x, %s)\n", result, e1->toChars());
147     //static int xx; if (xx++ == 10) assert(0);
148     Expression *e = e1;
149     if (e1->op == TOKvar)
150     {
151         VarExp *ve = (VarExp *)e1;
152         VarDeclaration *v = ve->var->isVarDeclaration();
153         e = expandVar(result, v);
154         if (e)
155         {
156             // If it is a comma expression involving a declaration, we mustn't
157             // perform a copy -- we'd get two declarations of the same variable.
158             // See bugzilla 4465.
159             if (e->op == TOKcomma && ((CommaExp *)e)->e1->op == TOKdeclaration)
160                  e = e1;
161             else
162 
163             if (e->type != e1->type && e1->type && e1->type->ty != Tident)
164             {
165                 // Type 'paint' operation
166                 e = e->copy();
167                 e->type = e1->type;
168             }
169             e->loc = e1->loc;
170         }
171         else
172         {
173             e = e1;
174         }
175     }
176     return e;
177 }
178 
Expression_optimize(Expression * e,int result,bool keepLvalue)179 Expression *Expression_optimize(Expression *e, int result, bool keepLvalue)
180 {
181     class OptimizeVisitor : public Visitor
182     {
183     public:
184         int result;
185         bool keepLvalue;
186         Expression *ret;
187 
188         OptimizeVisitor(int result, bool keepLvalue)
189             : result(result), keepLvalue(keepLvalue)
190         {
191         }
192 
193         void error()
194         {
195             ret = new ErrorExp();
196         }
197 
198         bool expOptimize(Expression *&e, int flags, bool keepLvalue = false)
199         {
200             if (!e)
201                 return false;
202             Expression *ex = e->optimize(flags, keepLvalue);
203             if (ex->op == TOKerror)
204             {
205                 ret = ex;   // store error result
206                 return true;
207             }
208             else
209             {
210                 e = ex;     // modify original
211                 return false;
212             }
213         }
214 
215         bool unaOptimize(UnaExp *e, int flags)
216         {
217             return expOptimize(e->e1, flags);
218         }
219 
220         bool binOptimize(BinExp *e, int flags)
221         {
222             expOptimize(e->e1, flags);
223             expOptimize(e->e2, flags);
224             return ret->op == TOKerror;
225         }
226 
227         void visit(Expression *)
228         {
229             //printf("Expression::optimize(result = x%x) %s\n", result, e->toChars());
230         }
231 
232         void visit(VarExp *e)
233         {
234             if (keepLvalue)
235             {
236                 VarDeclaration *v = e->var->isVarDeclaration();
237                 if (v && !(v->storage_class & STCmanifest))
238                     return;
239             }
240             ret = fromConstInitializer(result, e);
241         }
242 
243         void visit(TupleExp *e)
244         {
245             expOptimize(e->e0, WANTvalue);
246             for (size_t i = 0; i < e->exps->dim; i++)
247             {
248                 expOptimize((*e->exps)[i], WANTvalue);
249             }
250         }
251 
252         void visit(ArrayLiteralExp *e)
253         {
254             if (e->elements)
255             {
256                 expOptimize(e->basis, result & WANTexpand);
257                 for (size_t i = 0; i < e->elements->dim; i++)
258                 {
259                     expOptimize((*e->elements)[i], result & WANTexpand);
260                 }
261             }
262         }
263 
264         void visit(AssocArrayLiteralExp *e)
265         {
266             assert(e->keys->dim == e->values->dim);
267             for (size_t i = 0; i < e->keys->dim; i++)
268             {
269                 expOptimize((*e->keys)[i], result & WANTexpand);
270                 expOptimize((*e->values)[i], result & WANTexpand);
271             }
272         }
273 
274         void visit(StructLiteralExp *e)
275         {
276             if (e->stageflags & stageOptimize) return;
277             int old = e->stageflags;
278             e->stageflags |= stageOptimize;
279             if (e->elements)
280             {
281                 for (size_t i = 0; i < e->elements->dim; i++)
282                 {
283                     expOptimize((*e->elements)[i], result & WANTexpand);
284                 }
285             }
286             e->stageflags = old;
287         }
288 
289         void visit(UnaExp *e)
290         {
291             //printf("UnaExp::optimize() %s\n", e->toChars());
292             if (unaOptimize(e, result))
293                 return;
294         }
295 
296         void visit(NegExp *e)
297         {
298             if (unaOptimize(e, result))
299                 return;
300 
301             if (e->e1->isConst() == 1)
302             {
303                 ret = Neg(e->type, e->e1).copy();
304             }
305         }
306 
307         void visit(ComExp *e)
308         {
309             if (unaOptimize(e, result))
310                 return;
311 
312             if (e->e1->isConst() == 1)
313             {
314                 ret = Com(e->type, e->e1).copy();
315             }
316         }
317 
318         void visit(NotExp *e)
319         {
320             if (unaOptimize(e, result))
321                 return;
322 
323             if (e->e1->isConst() == 1)
324             {
325                 ret = Not(e->type, e->e1).copy();
326             }
327         }
328 
329         void visit(SymOffExp *e)
330         {
331             assert(e->var);
332         }
333 
334         void visit(AddrExp *e)
335         {
336             //printf("AddrExp::optimize(result = %d) %s\n", result, e->toChars());
337 
338             /* Rewrite &(a,b) as (a,&b)
339              */
340             if (e->e1->op == TOKcomma)
341             {
342                 CommaExp *ce = (CommaExp *)e->e1;
343                 AddrExp *ae = new AddrExp(e->loc, ce->e2, e->type);
344                 ret = new CommaExp(ce->loc, ce->e1, ae);
345                 ret->type = e->type;
346                 return;
347             }
348 
349             // Keep lvalue-ness
350             if (expOptimize(e->e1, result, true))
351                 return;
352 
353             // Convert &*ex to ex
354             if (e->e1->op == TOKstar)
355             {
356                 Expression *ex = ((PtrExp *)e->e1)->e1;
357                 if (e->type->equals(ex->type))
358                     ret = ex;
359                 else if (e->type->toBasetype()->equivalent(ex->type->toBasetype()))
360                 {
361                     ret = ex->copy();
362                     ret->type = e->type;
363                 }
364                 return;
365             }
366             if (e->e1->op == TOKvar)
367             {
368                 VarExp *ve = (VarExp *)e->e1;
369                 if (!ve->var->isOut() && !ve->var->isRef() &&
370                     !ve->var->isImportedSymbol())
371                 {
372                     ret = new SymOffExp(e->loc, ve->var, 0, ve->hasOverloads);
373                     ret->type = e->type;
374                     return;
375                 }
376             }
377             if (e->e1->op == TOKindex)
378             {
379                 // Convert &array[n] to &array+n
380                 IndexExp *ae = (IndexExp *)e->e1;
381 
382                 if (ae->e2->op == TOKint64 && ae->e1->op == TOKvar)
383                 {
384                     sinteger_t index = ae->e2->toInteger();
385                     VarExp *ve = (VarExp *)ae->e1;
386                     if (ve->type->ty == Tsarray
387                         && !ve->var->isImportedSymbol())
388                     {
389                         TypeSArray *ts = (TypeSArray *)ve->type;
390                         sinteger_t dim = ts->dim->toInteger();
391                         if (index < 0 || index >= dim)
392                         {
393                             e->error("array index %lld is out of bounds [0..%lld]", index, dim);
394                             return error();
395                         }
396 
397                         bool overflow = false;
398                         const d_uns64 offset = mulu(index, ts->nextOf()->size(e->loc), overflow);
399                         if (overflow)
400                         {
401                             e->error("array offset overflow");
402                             return error();
403                         }
404 
405                         ret = new SymOffExp(e->loc, ve->var, offset);
406                         ret->type = e->type;
407                         return;
408                     }
409                 }
410             }
411         }
412 
413         void visit(PtrExp *e)
414         {
415             //printf("PtrExp::optimize(result = x%x) %s\n", result, e->toChars());
416             if (expOptimize(e->e1, result))
417                 return;
418             // Convert *&ex to ex
419             // But only if there is no type punning involved
420             if (e->e1->op == TOKaddress)
421             {
422                 Expression *ex = ((AddrExp *)e->e1)->e1;
423                 if (e->type->equals(ex->type))
424                     ret = ex;
425                 else if (e->type->toBasetype()->equivalent(ex->type->toBasetype()))
426                 {
427                     ret = ex->copy();
428                     ret->type = e->type;
429                 }
430             }
431             if (keepLvalue)
432                 return;
433 
434             // Constant fold *(&structliteral + offset)
435             if (e->e1->op == TOKadd)
436             {
437                 Expression *ex = Ptr(e->type, e->e1).copy();
438                 if (!CTFEExp::isCantExp(ex))
439                 {
440                     ret = ex;
441                     return;
442                 }
443             }
444 
445             if (e->e1->op == TOKsymoff)
446             {
447                 SymOffExp *se = (SymOffExp *)e->e1;
448                 VarDeclaration *v = se->var->isVarDeclaration();
449                 Expression *ex = expandVar(result, v);
450                 if (ex && ex->op == TOKstructliteral)
451                 {
452                     StructLiteralExp *sle = (StructLiteralExp *)ex;
453                     ex = sle->getField(e->type, (unsigned)se->offset);
454                     if (ex && !CTFEExp::isCantExp(ex))
455                     {
456                         ret = ex;
457                         return;
458                     }
459                 }
460             }
461         }
462 
463         void visit(DotVarExp *e)
464         {
465             //printf("DotVarExp::optimize(result = x%x) %s\n", result, e->toChars());
466             if (expOptimize(e->e1, result))
467                 return;
468             if (keepLvalue)
469                 return;
470 
471             Expression *ex = e->e1;
472 
473             if (ex->op == TOKvar)
474             {
475                 VarExp *ve = (VarExp *)ex;
476                 VarDeclaration *v = ve->var->isVarDeclaration();
477                 ex = expandVar(result, v);
478             }
479 
480             if (ex && ex->op == TOKstructliteral)
481             {
482                 StructLiteralExp *sle = (StructLiteralExp *)ex;
483                 VarDeclaration *vf = e->var->isVarDeclaration();
484                 if (vf && !vf->overlapped)
485                 {
486                     /* Bugzilla 13021: Prevent optimization if vf has overlapped fields.
487                      */
488                     ex = sle->getField(e->type, vf->offset);
489                     if (ex && !CTFEExp::isCantExp(ex))
490                     {
491                         ret = ex;
492                         return;
493                     }
494                 }
495             }
496         }
497 
498         void visit(NewExp *e)
499         {
500             expOptimize(e->thisexp, WANTvalue);
501 
502             // Optimize parameters
503             if (e->newargs)
504             {
505                 for (size_t i = 0; i < e->newargs->dim; i++)
506                 {
507                     expOptimize((*e->newargs)[i], WANTvalue);
508                 }
509             }
510 
511             if (e->arguments)
512             {
513                 for (size_t i = 0; i < e->arguments->dim; i++)
514                 {
515                     expOptimize((*e->arguments)[i], WANTvalue);
516                 }
517             }
518         }
519 
520         void visit(CallExp *e)
521         {
522             //printf("CallExp::optimize(result = %d) %s\n", result, e->toChars());
523 
524             // Optimize parameters with keeping lvalue-ness
525             if (expOptimize(e->e1, result))
526                 return;
527             if (e->arguments)
528             {
529                 Type *t1 = e->e1->type->toBasetype();
530                 if (t1->ty == Tdelegate) t1 = t1->nextOf();
531                 assert(t1->ty == Tfunction);
532                 TypeFunction *tf = (TypeFunction *)t1;
533                 for (size_t i = 0; i < e->arguments->dim; i++)
534                 {
535                     Parameter *p = Parameter::getNth(tf->parameters, i);
536                     bool keep = p && (p->storageClass & (STCref | STCout)) != 0;
537                     expOptimize((*e->arguments)[i], WANTvalue, keep);
538                 }
539             }
540         }
541 
542         void visit(CastExp *e)
543         {
544             //printf("CastExp::optimize(result = %d) %s\n", result, e->toChars());
545             //printf("from %s to %s\n", e->type->toChars(), e->to->toChars());
546             //printf("from %s\n", e->type->toChars());
547             //printf("e1->type %s\n", e->e1->type->toChars());
548             //printf("type = %p\n", e->type);
549             assert(e->type);
550             TOK op1 = e->e1->op;
551 
552             Expression *e1old = e->e1;
553             if (expOptimize(e->e1, result))
554                 return;
555             e->e1 = fromConstInitializer(result, e->e1);
556 
557             if (e->e1 == e1old &&
558                 e->e1->op == TOKarrayliteral &&
559                 e->type->toBasetype()->ty == Tpointer &&
560                 e->e1->type->toBasetype()->ty != Tsarray)
561             {
562                 // Casting this will result in the same expression, and
563                 // infinite loop because of Expression::implicitCastTo()
564                 return;            // no change
565             }
566 
567             if ((e->e1->op == TOKstring || e->e1->op == TOKarrayliteral) &&
568                 (e->type->ty == Tpointer || e->type->ty == Tarray))
569             {
570                 const d_uns64 esz = e->type->nextOf()->size(e->loc);
571                 const d_uns64 e1sz = e->e1->type->toBasetype()->nextOf()->size(e->e1->loc);
572                 if (esz == SIZE_INVALID || e1sz == SIZE_INVALID)
573                     return error();
574 
575                 if (e1sz == esz)
576                 {
577                     // Bugzilla 12937: If target type is void array, trying to paint
578                     // e->e1 with that type will cause infinite recursive optimization.
579                     if (e->type->nextOf()->ty == Tvoid)
580                         return;
581 
582                     ret = e->e1->castTo(NULL, e->type);
583                     //printf(" returning1 %s\n", ret->toChars());
584                     return;
585                 }
586             }
587 
588             if (e->e1->op == TOKstructliteral &&
589                 e->e1->type->implicitConvTo(e->type) >= MATCHconst)
590             {
591                 //printf(" returning2 %s\n", e->e1->toChars());
592             L1: // Returning e1 with changing its type
593                 ret = (e1old == e->e1 ? e->e1->copy() : e->e1);
594                 ret->type = e->type;
595                 return;
596             }
597 
598             /* The first test here is to prevent infinite loops
599              */
600             if (op1 != TOKarrayliteral && e->e1->op == TOKarrayliteral)
601             {
602                 ret = e->e1->castTo(NULL, e->to);
603                 return;
604             }
605             if (e->e1->op == TOKnull &&
606                 (e->type->ty == Tpointer || e->type->ty == Tclass || e->type->ty == Tarray))
607             {
608                 //printf(" returning3 %s\n", e->e1->toChars());
609                 goto L1;
610             }
611 
612             if (e->type->ty == Tclass && e->e1->type->ty == Tclass)
613             {
614                 // See if we can remove an unnecessary cast
615                 ClassDeclaration *cdfrom = e->e1->type->isClassHandle();
616                 ClassDeclaration *cdto = e->type->isClassHandle();
617                 if (cdto == ClassDeclaration::object && !cdfrom->isInterfaceDeclaration())
618                     goto L1;    // can always convert a class to Object
619                 // Need to determine correct offset before optimizing away the cast.
620                 // https://issues.dlang.org/show_bug.cgi?id=16980
621                 cdfrom->size(e->loc);
622                 assert(cdfrom->sizeok == SIZEOKdone);
623                 assert(cdto->sizeok == SIZEOKdone || !cdto->isBaseOf(cdfrom, NULL));
624                 int offset;
625                 if (cdto->isBaseOf(cdfrom, &offset) && offset == 0)
626                 {
627                     //printf(" returning4 %s\n", e->e1->toChars());
628                     goto L1;
629                 }
630             }
631 
632             // We can convert 'head const' to mutable
633             if (e->to->mutableOf()->constOf()->equals(e->e1->type->mutableOf()->constOf()))
634             {
635                 //printf(" returning5 %s\n", e->e1->toChars());
636                 goto L1;
637             }
638 
639             if (e->e1->isConst())
640             {
641                 if (e->e1->op == TOKsymoff)
642                 {
643                     if (e->type->toBasetype()->ty != Tsarray)
644                     {
645                         const d_uns64 esz = e->type->size(e->loc);
646                         const d_uns64 e1sz = e->e1->type->size(e->e1->loc);
647                         if (esz == SIZE_INVALID ||
648                             e1sz == SIZE_INVALID)
649                             return error();
650 
651                         if (esz == e1sz)
652                             goto L1;
653                     }
654                     return;
655                 }
656                 if (e->to->toBasetype()->ty != Tvoid)
657                 {
658                     if (e->e1->type->equals(e->type) && e->type->equals(e->to))
659                         ret = e->e1;
660                     else
661                         ret = Cast(e->loc, e->type, e->to, e->e1).copy();
662                 }
663             }
664             //printf(" returning6 %s\n", ret->toChars());
665         }
666 
667         void visit(BinExp *e)
668         {
669             //printf("BinExp::optimize(result = %d) %s\n", result, e->toChars());
670             // don't replace const variable with its initializer in e1
671             bool e2only = (e->op == TOKconstruct || e->op == TOKblit);
672             if (e2only ? expOptimize(e->e2, result) : binOptimize(e, result))
673                 return;
674 
675             if (e->op == TOKshlass || e->op == TOKshrass || e->op == TOKushrass)
676             {
677                 if (e->e2->isConst() == 1)
678                 {
679                     sinteger_t i2 = e->e2->toInteger();
680                     d_uns64 sz = e->e1->type->size(e->e1->loc);
681                     assert(sz != SIZE_INVALID);
682                     sz *= 8;
683                     if (i2 < 0 || (d_uns64)i2 >= sz)
684                     {
685                         e->error("shift assign by %lld is outside the range 0..%llu", i2, (ulonglong)sz - 1);
686                         return error();
687                     }
688                 }
689             }
690         }
691 
692         void visit(AddExp *e)
693         {
694             //printf("AddExp::optimize(%s)\n", e->toChars());
695 
696             if (binOptimize(e, result))
697                 return;
698 
699             if (e->e1->isConst() && e->e2->isConst())
700             {
701                 if (e->e1->op == TOKsymoff && e->e2->op == TOKsymoff)
702                     return;
703                 ret = Add(e->loc, e->type, e->e1, e->e2).copy();
704             }
705         }
706 
707         void visit(MinExp *e)
708         {
709             if (binOptimize(e, result))
710                 return;
711 
712             if (e->e1->isConst() && e->e2->isConst())
713             {
714                 if (e->e2->op == TOKsymoff)
715                     return;
716                 ret = Min(e->loc, e->type, e->e1, e->e2).copy();
717             }
718         }
719 
720         void visit(MulExp *e)
721         {
722             //printf("MulExp::optimize(result = %d) %s\n", result, e->toChars());
723 
724             if (binOptimize(e, result))
725                 return;
726 
727             if (e->e1->isConst() == 1 && e->e2->isConst() == 1)
728             {
729                 ret = Mul(e->loc, e->type, e->e1, e->e2).copy();
730             }
731         }
732 
733         void visit(DivExp *e)
734         {
735             //printf("DivExp::optimize(%s)\n", e->toChars());
736 
737             if (binOptimize(e, result))
738                 return;
739 
740             if (e->e1->isConst() == 1 && e->e2->isConst() == 1)
741             {
742                 ret = Div(e->loc, e->type, e->e1, e->e2).copy();
743             }
744         }
745 
746         void visit(ModExp *e)
747         {
748             if (binOptimize(e, result))
749                 return;
750 
751             if (e->e1->isConst() == 1 && e->e2->isConst() == 1)
752             {
753                 ret = Mod(e->loc, e->type, e->e1, e->e2).copy();
754             }
755         }
756 
757         void shift_optimize(BinExp *e, UnionExp (*shift)(Loc, Type *, Expression *, Expression *))
758         {
759             if (binOptimize(e, result))
760                 return;
761 
762             if (e->e2->isConst() == 1)
763             {
764                 sinteger_t i2 = e->e2->toInteger();
765                 d_uns64 sz = e->e1->type->size();
766                 assert(sz != SIZE_INVALID);
767                 sz *= 8;
768                 if (i2 < 0 || (d_uns64)i2 >= sz)
769                 {
770                     e->error("shift by %lld is outside the range 0..%llu", i2, (ulonglong)sz - 1);
771                     return error();
772                 }
773                 if (e->e1->isConst() == 1)
774                     ret = (*shift)(e->loc, e->type, e->e1, e->e2).copy();
775             }
776         }
777 
778         void visit(ShlExp *e)
779         {
780             //printf("ShlExp::optimize(result = %d) %s\n", result, e->toChars());
781             shift_optimize(e, &Shl);
782         }
783 
784         void visit(ShrExp *e)
785         {
786             //printf("ShrExp::optimize(result = %d) %s\n", result, e->toChars());
787             shift_optimize(e, &Shr);
788         }
789 
790         void visit(UshrExp *e)
791         {
792             //printf("UshrExp::optimize(result = %d) %s\n", result, toChars());
793             shift_optimize(e, &Ushr);
794         }
795 
796         void visit(AndExp *e)
797         {
798             if (binOptimize(e, result))
799                 return;
800 
801             if (e->e1->isConst() == 1 && e->e2->isConst() == 1)
802                 ret = And(e->loc, e->type, e->e1, e->e2).copy();
803         }
804 
805         void visit(OrExp *e)
806         {
807             if (binOptimize(e, result))
808                 return;
809 
810             if (e->e1->isConst() == 1 && e->e2->isConst() == 1)
811                 ret = Or(e->loc, e->type, e->e1, e->e2).copy();
812         }
813 
814         void visit(XorExp *e)
815         {
816             if (binOptimize(e, result))
817                 return;
818 
819             if (e->e1->isConst() == 1 && e->e2->isConst() == 1)
820                 ret = Xor(e->loc, e->type, e->e1, e->e2).copy();
821         }
822 
823         void visit(PowExp *e)
824         {
825             if (binOptimize(e, result))
826                 return;
827 
828             // Replace 1 ^^ x or 1.0^^x by (x, 1)
829             if ((e->e1->op == TOKint64 && e->e1->toInteger() == 1) ||
830                 (e->e1->op == TOKfloat64 && e->e1->toReal() == CTFloat::one))
831             {
832                 ret = new CommaExp(e->loc, e->e2, e->e1);
833                 ret->type = e->type;
834                 return;
835             }
836 
837             // Replace -1 ^^ x by (x&1) ? -1 : 1, where x is integral
838             if (e->e2->type->isintegral() && e->e1->op == TOKint64 && (sinteger_t)e->e1->toInteger() == -1L)
839             {
840                 ret = new AndExp(e->loc, e->e2, new IntegerExp(e->loc, 1, e->e2->type));
841                 ret->type = e->e2->type;
842                 ret = new CondExp(e->loc, ret, new IntegerExp(e->loc, -1L, e->type), new IntegerExp(e->loc, 1L, e->type));
843                 ret->type = e->type;
844                 return;
845             }
846 
847             // Replace x ^^ 0 or x^^0.0 by (x, 1)
848             if ((e->e2->op == TOKint64 && e->e2->toInteger() == 0) ||
849                 (e->e2->op == TOKfloat64 && e->e2->toReal() == CTFloat::zero))
850             {
851                 if (e->e1->type->isintegral())
852                     ret = new IntegerExp(e->loc, 1, e->e1->type);
853                 else
854                     ret = new RealExp(e->loc, CTFloat::one, e->e1->type);
855 
856                 ret = new CommaExp(e->loc, e->e1, ret);
857                 ret->type = e->type;
858                 return;
859             }
860 
861             // Replace x ^^ 1 or x^^1.0 by (x)
862             if ((e->e2->op == TOKint64 && e->e2->toInteger() == 1) ||
863                 (e->e2->op == TOKfloat64 && e->e2->toReal() == CTFloat::one))
864             {
865                 ret = e->e1;
866                 return;
867             }
868 
869             // Replace x ^^ -1.0 by (1.0 / x)
870             if ((e->e2->op == TOKfloat64 && e->e2->toReal() == CTFloat::minusone))
871             {
872                 ret = new DivExp(e->loc, new RealExp(e->loc, CTFloat::one, e->e2->type), e->e1);
873                 ret->type = e->type;
874                 return;
875             }
876 
877             // All other negative integral powers are illegal
878             if ((e->e1->type->isintegral()) && (e->e2->op == TOKint64) && (sinteger_t)e->e2->toInteger() < 0)
879             {
880                 e->error("cannot raise %s to a negative integer power. Did you mean (cast(real)%s)^^%s ?",
881                       e->e1->type->toBasetype()->toChars(), e->e1->toChars(), e->e2->toChars());
882                 return error();
883             }
884 
885             // If e2 *could* have been an integer, make it one.
886             if (e->e2->op == TOKfloat64 && (e->e2->toReal() == ldouble((sinteger_t)e->e2->toReal())))
887                 e->e2 = new IntegerExp(e->loc, e->e2->toInteger(), Type::tint64);
888 
889             if (e->e1->isConst() == 1 && e->e2->isConst() == 1)
890             {
891                 Expression *ex = Pow(e->loc, e->type, e->e1, e->e2).copy();
892                 if (!CTFEExp::isCantExp(ex))
893                 {
894                     ret = ex;
895                     return;
896                 }
897             }
898 
899             // (2 ^^ n) ^^ p -> 1 << n * p
900             if (e->e1->op == TOKint64 && e->e1->toInteger() > 0 &&
901                 !((e->e1->toInteger() - 1) & e->e1->toInteger()) &&
902                 e->e2->type->isintegral() && e->e2->type->isunsigned())
903             {
904                 dinteger_t i = e->e1->toInteger();
905                 dinteger_t mul = 1;
906                 while ((i >>= 1) > 1)
907                     mul++;
908                 Expression *shift = new MulExp(e->loc, e->e2, new IntegerExp(e->loc, mul, e->e2->type));
909                 shift->type = e->e2->type;
910                 shift = shift->castTo(NULL, Type::tshiftcnt);
911                 ret = new ShlExp(e->loc, new IntegerExp(e->loc, 1, e->e1->type), shift);
912                 ret->type = e->type;
913                 return;
914             }
915         }
916 
917         void visit(CommaExp *e)
918         {
919             //printf("CommaExp::optimize(result = %d) %s\n", result, e->toChars());
920             // Comma needs special treatment, because it may
921             // contain compiler-generated declarations. We can interpret them, but
922             // otherwise we must NOT attempt to constant-fold them.
923             // In particular, if the comma returns a temporary variable, it needs
924             // to be an lvalue (this is particularly important for struct constructors)
925 
926             expOptimize(e->e1, WANTvalue);
927             expOptimize(e->e2, result, keepLvalue);
928             if (ret->op == TOKerror)
929                 return;
930 
931             if (!e->e1 || e->e1->op == TOKint64 || e->e1->op == TOKfloat64 || !hasSideEffect(e->e1))
932             {
933                 ret = e->e2;
934                 if (ret)
935                     ret->type = e->type;
936             }
937 
938             //printf("-CommaExp::optimize(result = %d) %s\n", result, e->e->toChars());
939         }
940 
941         void visit(ArrayLengthExp *e)
942         {
943             //printf("ArrayLengthExp::optimize(result = %d) %s\n", result, e->toChars());
944 
945             if (unaOptimize(e, WANTexpand))
946                 return;
947 
948             // CTFE interpret static immutable arrays (to get better diagnostics)
949             if (e->e1->op == TOKvar)
950             {
951                 VarDeclaration *v = ((VarExp *)e->e1)->var->isVarDeclaration();
952                 if (v && (v->storage_class & STCstatic) && (v->storage_class & STCimmutable) && v->_init)
953                 {
954                     if (Expression *ci = v->getConstInitializer())
955                         e->e1 = ci;
956                 }
957             }
958 
959             if (e->e1->op == TOKstring || e->e1->op == TOKarrayliteral || e->e1->op == TOKassocarrayliteral ||
960                 e->e1->type->toBasetype()->ty == Tsarray)
961             {
962                 ret = ArrayLength(e->type, e->e1).copy();
963             }
964         }
965 
966         void visit(EqualExp *e)
967         {
968             //printf("EqualExp::optimize(result = %x) %s\n", result, e->toChars());
969             if (binOptimize(e, WANTvalue))
970                 return;
971 
972             Expression *e1 = fromConstInitializer(result, e->e1);
973             Expression *e2 = fromConstInitializer(result, e->e2);
974             if (e1->op == TOKerror)
975             {
976                 ret = e1;
977                 return;
978             }
979             if (e2->op == TOKerror)
980             {
981                 ret = e2;
982                 return;
983             }
984 
985             ret = Equal(e->op, e->loc, e->type, e1, e2).copy();
986             if (CTFEExp::isCantExp(ret))
987                 ret = e;
988         }
989 
990         void visit(IdentityExp *e)
991         {
992             //printf("IdentityExp::optimize(result = %d) %s\n", result, e->toChars());
993 
994             if (binOptimize(e, WANTvalue))
995                 return;
996 
997             if ((e->e1->isConst()     && e->e2->isConst()) ||
998                 (e->e1->op == TOKnull && e->e2->op == TOKnull)
999                 )
1000             {
1001                 ret = Identity(e->op, e->loc, e->type, e->e1, e->e2).copy();
1002                 if (CTFEExp::isCantExp(ret))
1003                     ret = e;
1004             }
1005         }
1006 
1007         /* It is possible for constant folding to change an array expression of
1008          * unknown length, into one where the length is known.
1009          * If the expression 'arr' is a literal, set lengthVar to be its length.
1010          */
1011         static void setLengthVarIfKnown(VarDeclaration *lengthVar, Expression *arr)
1012         {
1013             if (!lengthVar)
1014                 return;
1015             if (lengthVar->_init && !lengthVar->_init->isVoidInitializer())
1016                 return; // we have previously calculated the length
1017             size_t len;
1018             if (arr->op == TOKstring)
1019                 len = ((StringExp *)arr)->len;
1020             else if (arr->op == TOKarrayliteral)
1021                 len = ((ArrayLiteralExp *)arr)->elements->dim;
1022             else
1023             {
1024                 Type *t = arr->type->toBasetype();
1025                 if (t->ty == Tsarray)
1026                     len = (size_t)((TypeSArray *)t)->dim->toInteger();
1027                 else
1028                     return; // we don't know the length yet
1029             }
1030 
1031             Expression *dollar = new IntegerExp(Loc(), len, Type::tsize_t);
1032             lengthVar->_init = new ExpInitializer(Loc(), dollar);
1033             lengthVar->storage_class |= STCstatic | STCconst;
1034         }
1035 
1036         void visit(IndexExp *e)
1037         {
1038             //printf("IndexExp::optimize(result = %d) %s\n", result, e->toChars());
1039             if (expOptimize(e->e1, result & WANTexpand))
1040                 return;
1041 
1042             Expression *ex = fromConstInitializer(result, e->e1);
1043 
1044             // We might know $ now
1045             setLengthVarIfKnown(e->lengthVar, ex);
1046 
1047             if (expOptimize(e->e2, WANTvalue))
1048                 return;
1049             if (keepLvalue)
1050                 return;
1051             ret = Index(e->type, ex, e->e2).copy();
1052             if (CTFEExp::isCantExp(ret))
1053                 ret = e;
1054         }
1055 
1056         void visit(SliceExp *e)
1057         {
1058             //printf("SliceExp::optimize(result = %d) %s\n", result, e->toChars());
1059             if (expOptimize(e->e1, result & WANTexpand))
1060                 return;
1061             if (!e->lwr)
1062             {
1063                 if (e->e1->op == TOKstring)
1064                 {
1065                     // Convert slice of string literal into dynamic array
1066                     Type *t = e->e1->type->toBasetype();
1067                     if (Type *tn = t->nextOf())
1068                         ret = e->e1->castTo(NULL, tn->arrayOf());
1069                 }
1070             }
1071             else
1072             {
1073                 e->e1 = fromConstInitializer(result, e->e1);
1074                 // We might know $ now
1075                 setLengthVarIfKnown(e->lengthVar, e->e1);
1076                 expOptimize(e->lwr, WANTvalue);
1077                 expOptimize(e->upr, WANTvalue);
1078                 if (ret->op == TOKerror)
1079                     return;
1080                 ret = Slice(e->type, e->e1, e->lwr, e->upr).copy();
1081                 if (CTFEExp::isCantExp(ret))
1082                     ret = e;
1083             }
1084 
1085             // Bugzilla 14649: We need to leave the slice form so it might be
1086             // a part of array operation.
1087             // Assume that the backend codegen will handle the form `e[]`
1088             // as an equal to `e` itself.
1089             if (ret->op == TOKstring)
1090             {
1091                 e->e1 = ret;
1092                 e->lwr = NULL;
1093                 e->upr = NULL;
1094                 ret = e;
1095             }
1096             //printf("-SliceExp::optimize() %s\n", ret->toChars());
1097         }
1098 
1099         void visit(AndAndExp *e)
1100         {
1101             //printf("AndAndExp::optimize(%d) %s\n", result, e->toChars());
1102             if (expOptimize(e->e1, WANTvalue))
1103                 return;
1104 
1105             if (e->e1->isBool(false))
1106             {
1107                 // Replace with (e1, false)
1108                 ret = new IntegerExp(e->loc, 0, Type::tbool);
1109                 ret = Expression::combine(e->e1, ret);
1110                 if (e->type->toBasetype()->ty == Tvoid)
1111                 {
1112                     ret = new CastExp(e->loc, ret, Type::tvoid);
1113                     ret->type = e->type;
1114                 }
1115                 return;
1116             }
1117 
1118             if (expOptimize(e->e2, WANTvalue))
1119                 return;
1120 
1121             if (e->e1->isConst())
1122             {
1123                 if (e->e2->isConst())
1124                 {
1125                     bool n1 = e->e1->isBool(true);
1126                     bool n2 = e->e2->isBool(true);
1127                     ret = new IntegerExp(e->loc, n1 && n2, e->type);
1128                 }
1129                 else if (e->e1->isBool(true))
1130                 {
1131                     if (e->type->toBasetype()->ty == Tvoid)
1132                         ret = e->e2;
1133                     else
1134                     {
1135                         ret = new CastExp(e->loc, e->e2, e->type);
1136                         ret->type = e->type;
1137                     }
1138                 }
1139             }
1140         }
1141 
1142         void visit(OrOrExp *e)
1143         {
1144             //printf("OrOrExp::optimize(%d) %s\n", result, e->toChars());
1145             if (expOptimize(e->e1, WANTvalue))
1146                 return;
1147 
1148             if (e->e1->isBool(true))
1149             {
1150                 // Replace with (e1, true)
1151                 ret = new IntegerExp(e->loc, 1, Type::tbool);
1152                 ret = Expression::combine(e->e1, ret);
1153                 if (e->type->toBasetype()->ty == Tvoid)
1154                 {
1155                     ret = new CastExp(e->loc, ret, Type::tvoid);
1156                     ret->type = e->type;
1157                 }
1158                 return;
1159             }
1160 
1161             if (expOptimize(e->e2, WANTvalue))
1162                 return;
1163 
1164             if (e->e1->isConst())
1165             {
1166                 if (e->e2->isConst())
1167                 {
1168                     bool n1 = e->e1->isBool(true);
1169                     bool n2 = e->e2->isBool(true);
1170                     ret = new IntegerExp(e->loc, n1 || n2, e->type);
1171                 }
1172                 else if (e->e1->isBool(false))
1173                 {
1174                     if (e->type->toBasetype()->ty == Tvoid)
1175                         ret = e->e2;
1176                     else
1177                     {
1178                         ret = new CastExp(e->loc, e->e2, e->type);
1179                         ret->type = e->type;
1180                     }
1181                 }
1182             }
1183         }
1184 
1185         void visit(CmpExp *e)
1186         {
1187             //printf("CmpExp::optimize() %s\n", e->toChars());
1188             if (binOptimize(e, WANTvalue))
1189                 return;
1190 
1191             Expression *e1 = fromConstInitializer(result, e->e1);
1192             Expression *e2 = fromConstInitializer(result, e->e2);
1193 
1194             ret = Cmp(e->op, e->loc, e->type, e1, e2).copy();
1195             if (CTFEExp::isCantExp(ret))
1196                 ret = e;
1197         }
1198 
1199         void visit(CatExp *e)
1200         {
1201             //printf("CatExp::optimize(%d) %s\n", result, e->toChars());
1202 
1203             if (binOptimize(e, result))
1204                 return;
1205 
1206             if (e->e1->op == TOKcat)
1207             {
1208                 // Bugzilla 12798: optimize ((expr ~ str1) ~ str2)
1209                 CatExp *ce1 = (CatExp *)e->e1;
1210                 CatExp cex(e->loc, ce1->e2, e->e2);
1211                 cex.type = e->type;
1212                 Expression *ex = cex.optimize(result);
1213                 if (ex != &cex)
1214                 {
1215                     e->e1 = ce1->e1;
1216                     e->e2 = ex;
1217                 }
1218             }
1219 
1220             // optimize "str"[] -> "str"
1221             if (e->e1->op == TOKslice)
1222             {
1223                 SliceExp *se1 = (SliceExp *)e->e1;
1224                 if (se1->e1->op == TOKstring && !se1->lwr)
1225                     e->e1 = se1->e1;
1226             }
1227             if (e->e2->op == TOKslice)
1228             {
1229                 SliceExp *se2 = (SliceExp *)e->e2;
1230                 if (se2->e1->op == TOKstring && !se2->lwr)
1231                     e->e2 = se2->e1;
1232             }
1233 
1234             ret = Cat(e->type, e->e1, e->e2).copy();
1235             if (CTFEExp::isCantExp(ret))
1236                 ret = e;
1237         }
1238 
1239         void visit(CondExp *e)
1240         {
1241             if (expOptimize(e->econd, WANTvalue))
1242                 return;
1243             if (e->econd->isBool(true))
1244                 ret = e->e1->optimize(result, keepLvalue);
1245             else if (e->econd->isBool(false))
1246                 ret = e->e2->optimize(result, keepLvalue);
1247             else
1248             {
1249                 expOptimize(e->e1, result, keepLvalue);
1250                 expOptimize(e->e2, result, keepLvalue);
1251             }
1252         }
1253     };
1254 
1255     OptimizeVisitor v(result, keepLvalue);
1256     Expression *ex = NULL;
1257     v.ret = e;
1258 
1259     // Optimize the expression until it can no longer be simplified.
1260     size_t b = 0;
1261     while (1)
1262     {
1263         if (b++ == global.recursionLimit)
1264         {
1265             e->error("infinite loop while optimizing expression");
1266             fatal();
1267         }
1268         ex = v.ret;
1269         ex->accept(&v);
1270         if (ex == v.ret)
1271             break;
1272     }
1273     return ex;
1274 }
1275