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
24Expression *semantic(Expression *e, Scope *sc);
25
26/*************************************
27 * If variable has a const initializer,
28 * return that initializer.
29 */
30
31Expression *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    }
135L1:
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
139Lerror:
140    return new ErrorExp();
141}
142
143
144Expression *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
179Expression *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