1//
2// Copyright (c) 2002-2013 The ANGLE Project Authors. All rights reserved.
3// Use of this source code is governed by a BSD-style license that can be
4// found in the LICENSE file.
5//
6
7//
8// Build the intermediate representation.
9//
10
11#include <float.h>
12#include <limits.h>
13#include <algorithm>
14
15#include "compiler/HashNames.h"
16#include "compiler/localintermediate.h"
17#include "compiler/QualifierAlive.h"
18#include "compiler/RemoveTree.h"
19
20bool CompareStructure(const TType& leftNodeType, ConstantUnion* rightUnionArray, ConstantUnion* leftUnionArray);
21
22static TPrecision GetHigherPrecision( TPrecision left, TPrecision right ){
23    return left > right ? left : right;
24}
25
26const char* getOperatorString(TOperator op) {
27    switch (op) {
28      case EOpInitialize: return "=";
29      case EOpAssign: return "=";
30      case EOpAddAssign: return "+=";
31      case EOpSubAssign: return "-=";
32      case EOpDivAssign: return "/=";
33
34      // Fall-through.
35      case EOpMulAssign:
36      case EOpVectorTimesMatrixAssign:
37      case EOpVectorTimesScalarAssign:
38      case EOpMatrixTimesScalarAssign:
39      case EOpMatrixTimesMatrixAssign: return "*=";
40
41      // Fall-through.
42      case EOpIndexDirect:
43      case EOpIndexIndirect: return "[]";
44
45      case EOpIndexDirectStruct: return ".";
46      case EOpVectorSwizzle: return ".";
47      case EOpAdd: return "+";
48      case EOpSub: return "-";
49      case EOpMul: return "*";
50      case EOpDiv: return "/";
51      case EOpMod: UNIMPLEMENTED(); break;
52      case EOpEqual: return "==";
53      case EOpNotEqual: return "!=";
54      case EOpLessThan: return "<";
55      case EOpGreaterThan: return ">";
56      case EOpLessThanEqual: return "<=";
57      case EOpGreaterThanEqual: return ">=";
58
59      // Fall-through.
60      case EOpVectorTimesScalar:
61      case EOpVectorTimesMatrix:
62      case EOpMatrixTimesVector:
63      case EOpMatrixTimesScalar:
64      case EOpMatrixTimesMatrix: return "*";
65
66      case EOpLogicalOr: return "||";
67      case EOpLogicalXor: return "^^";
68      case EOpLogicalAnd: return "&&";
69      case EOpNegative: return "-";
70      case EOpVectorLogicalNot: return "not";
71      case EOpLogicalNot: return "!";
72      case EOpPostIncrement: return "++";
73      case EOpPostDecrement: return "--";
74      case EOpPreIncrement: return "++";
75      case EOpPreDecrement: return "--";
76
77      // Fall-through.
78      case EOpConvIntToBool:
79      case EOpConvFloatToBool: return "bool";
80
81      // Fall-through.
82      case EOpConvBoolToFloat:
83      case EOpConvIntToFloat: return "float";
84
85      // Fall-through.
86      case EOpConvFloatToInt:
87      case EOpConvBoolToInt: return "int";
88
89      case EOpRadians: return "radians";
90      case EOpDegrees: return "degrees";
91      case EOpSin: return "sin";
92      case EOpCos: return "cos";
93      case EOpTan: return "tan";
94      case EOpAsin: return "asin";
95      case EOpAcos: return "acos";
96      case EOpAtan: return "atan";
97      case EOpExp: return "exp";
98      case EOpLog: return "log";
99      case EOpExp2: return "exp2";
100      case EOpLog2: return "log2";
101      case EOpSqrt: return "sqrt";
102      case EOpInverseSqrt: return "inversesqrt";
103      case EOpAbs: return "abs";
104      case EOpSign: return "sign";
105      case EOpFloor: return "floor";
106      case EOpCeil: return "ceil";
107      case EOpFract: return "fract";
108      case EOpLength: return "length";
109      case EOpNormalize: return "normalize";
110      case EOpDFdx: return "dFdx";
111      case EOpDFdy: return "dFdy";
112      case EOpFwidth: return "fwidth";
113      case EOpAny: return "any";
114      case EOpAll: return "all";
115
116      default: break;
117    }
118    return "";
119}
120
121////////////////////////////////////////////////////////////////////////////
122//
123// First set of functions are to help build the intermediate representation.
124// These functions are not member functions of the nodes.
125// They are called from parser productions.
126//
127/////////////////////////////////////////////////////////////////////////////
128
129//
130// Add a terminal node for an identifier in an expression.
131//
132// Returns the added node.
133//
134TIntermSymbol* TIntermediate::addSymbol(int id, const TString& name, const TType& type, const TSourceLoc& line)
135{
136    TIntermSymbol* node = new TIntermSymbol(id, name, type);
137    node->setLine(line);
138
139    return node;
140}
141
142//
143// Connect two nodes with a new parent that does a binary operation on the nodes.
144//
145// Returns the added node.
146//
147TIntermTyped* TIntermediate::addBinaryMath(TOperator op, TIntermTyped* left, TIntermTyped* right, const TSourceLoc& line, TSymbolTable& symbolTable)
148{
149    switch (op) {
150        case EOpEqual:
151        case EOpNotEqual:
152            if (left->isArray())
153                return 0;
154            break;
155        case EOpLessThan:
156        case EOpGreaterThan:
157        case EOpLessThanEqual:
158        case EOpGreaterThanEqual:
159            if (left->isMatrix() || left->isArray() || left->isVector() || left->getBasicType() == EbtStruct) {
160                return 0;
161            }
162            break;
163        case EOpLogicalOr:
164        case EOpLogicalXor:
165        case EOpLogicalAnd:
166            if (left->getBasicType() != EbtBool || left->isMatrix() || left->isArray() || left->isVector()) {
167                return 0;
168            }
169            break;
170        case EOpAdd:
171        case EOpSub:
172        case EOpDiv:
173        case EOpMul:
174            if (left->getBasicType() == EbtStruct || left->getBasicType() == EbtBool)
175                return 0;
176        default: break;
177    }
178
179    //
180    // First try converting the children to compatible types.
181    //
182    if (left->getType().getStruct() && right->getType().getStruct()) {
183        if (left->getType() != right->getType())
184            return 0;
185    } else {
186        TIntermTyped* child = addConversion(op, left->getType(), right);
187        if (child)
188            right = child;
189        else {
190            child = addConversion(op, right->getType(), left);
191            if (child)
192                left = child;
193            else
194                return 0;
195        }
196    }
197
198    //
199    // Need a new node holding things together then.  Make
200    // one and promote it to the right type.
201    //
202    TIntermBinary* node = new TIntermBinary(op);
203    node->setLine(line);
204
205    node->setLeft(left);
206    node->setRight(right);
207    if (!node->promote(infoSink))
208        return 0;
209
210    //
211    // See if we can fold constants.
212    //
213    TIntermTyped* typedReturnNode = 0;
214    TIntermConstantUnion *leftTempConstant = left->getAsConstantUnion();
215    TIntermConstantUnion *rightTempConstant = right->getAsConstantUnion();
216    if (leftTempConstant && rightTempConstant) {
217        typedReturnNode = leftTempConstant->fold(node->getOp(), rightTempConstant, infoSink);
218
219        if (typedReturnNode)
220            return typedReturnNode;
221    }
222
223    return node;
224}
225
226//
227// Connect two nodes through an assignment.
228//
229// Returns the added node.
230//
231TIntermTyped* TIntermediate::addAssign(TOperator op, TIntermTyped* left, TIntermTyped* right, const TSourceLoc& line)
232{
233    //
234    // Like adding binary math, except the conversion can only go
235    // from right to left.
236    //
237    TIntermBinary* node = new TIntermBinary(op);
238    node->setLine(line);
239
240    TIntermTyped* child = addConversion(op, left->getType(), right);
241    if (child == 0)
242        return 0;
243
244    node->setLeft(left);
245    node->setRight(child);
246    if (! node->promote(infoSink))
247        return 0;
248
249    return node;
250}
251
252//
253// Connect two nodes through an index operator, where the left node is the base
254// of an array or struct, and the right node is a direct or indirect offset.
255//
256// Returns the added node.
257// The caller should set the type of the returned node.
258//
259TIntermTyped* TIntermediate::addIndex(TOperator op, TIntermTyped* base, TIntermTyped* index, const TSourceLoc& line)
260{
261    TIntermBinary* node = new TIntermBinary(op);
262    node->setLine(line);
263    node->setLeft(base);
264    node->setRight(index);
265
266    // caller should set the type
267
268    return node;
269}
270
271//
272// Add one node as the parent of another that it operates on.
273//
274// Returns the added node.
275//
276TIntermTyped* TIntermediate::addUnaryMath(TOperator op, TIntermNode* childNode, const TSourceLoc& line, TSymbolTable& symbolTable)
277{
278    TIntermUnary* node;
279    TIntermTyped* child = childNode->getAsTyped();
280
281    if (child == 0) {
282        infoSink.info.message(EPrefixInternalError, line, "Bad type in AddUnaryMath");
283        return 0;
284    }
285
286    switch (op) {
287        case EOpLogicalNot:
288            if (child->getType().getBasicType() != EbtBool || child->getType().isMatrix() || child->getType().isArray() || child->getType().isVector()) {
289                return 0;
290            }
291            break;
292
293        case EOpPostIncrement:
294        case EOpPreIncrement:
295        case EOpPostDecrement:
296        case EOpPreDecrement:
297        case EOpNegative:
298            if (child->getType().getBasicType() == EbtStruct || child->getType().isArray())
299                return 0;
300        default: break;
301    }
302
303    //
304    // Do we need to promote the operand?
305    //
306    // Note: Implicit promotions were removed from the language.
307    //
308    TBasicType newType = EbtVoid;
309    switch (op) {
310        case EOpConstructInt:   newType = EbtInt;   break;
311        case EOpConstructBool:  newType = EbtBool;  break;
312        case EOpConstructFloat: newType = EbtFloat; break;
313        default: break;
314    }
315
316    if (newType != EbtVoid) {
317        child = addConversion(op, TType(newType, child->getPrecision(), EvqTemporary,
318            child->getNominalSize(),
319            child->isMatrix(),
320            child->isArray()),
321            child);
322        if (child == 0)
323            return 0;
324    }
325
326    //
327    // For constructors, we are now done, it's all in the conversion.
328    //
329    switch (op) {
330        case EOpConstructInt:
331        case EOpConstructBool:
332        case EOpConstructFloat:
333            return child;
334        default: break;
335    }
336
337    TIntermConstantUnion *childTempConstant = 0;
338    if (child->getAsConstantUnion())
339        childTempConstant = child->getAsConstantUnion();
340
341    //
342    // Make a new node for the operator.
343    //
344    node = new TIntermUnary(op);
345    node->setLine(line);
346    node->setOperand(child);
347
348    if (! node->promote(infoSink))
349        return 0;
350
351    if (childTempConstant)  {
352        TIntermTyped* newChild = childTempConstant->fold(op, 0, infoSink);
353
354        if (newChild)
355            return newChild;
356    }
357
358    return node;
359}
360
361//
362// This is the safe way to change the operator on an aggregate, as it
363// does lots of error checking and fixing.  Especially for establishing
364// a function call's operation on it's set of parameters.  Sequences
365// of instructions are also aggregates, but they just direnctly set
366// their operator to EOpSequence.
367//
368// Returns an aggregate node, which could be the one passed in if
369// it was already an aggregate but no operator was set.
370//
371TIntermAggregate* TIntermediate::setAggregateOperator(TIntermNode* node, TOperator op, const TSourceLoc& line)
372{
373    TIntermAggregate* aggNode;
374
375    //
376    // Make sure we have an aggregate.  If not turn it into one.
377    //
378    if (node) {
379        aggNode = node->getAsAggregate();
380        if (aggNode == 0 || aggNode->getOp() != EOpNull) {
381            //
382            // Make an aggregate containing this node.
383            //
384            aggNode = new TIntermAggregate();
385            aggNode->getSequence().push_back(node);
386        }
387    } else
388        aggNode = new TIntermAggregate();
389
390    //
391    // Set the operator.
392    //
393    aggNode->setOp(op);
394    aggNode->setLine(line);
395
396    return aggNode;
397}
398
399//
400// Convert one type to another.
401//
402// Returns the node representing the conversion, which could be the same
403// node passed in if no conversion was needed.
404//
405// Return 0 if a conversion can't be done.
406//
407TIntermTyped* TIntermediate::addConversion(TOperator op, const TType& type, TIntermTyped* node)
408{
409    //
410    // Does the base type allow operation?
411    //
412    switch (node->getBasicType()) {
413        case EbtVoid:
414        case EbtSampler2D:
415        case EbtSamplerCube:
416            return 0;
417        default: break;
418    }
419
420    //
421    // Otherwise, if types are identical, no problem
422    //
423    if (type == node->getType())
424        return node;
425
426    //
427    // If one's a structure, then no conversions.
428    //
429    if (type.getStruct() || node->getType().getStruct())
430        return 0;
431
432    //
433    // If one's an array, then no conversions.
434    //
435    if (type.isArray() || node->getType().isArray())
436        return 0;
437
438    TBasicType promoteTo;
439
440    switch (op) {
441        //
442        // Explicit conversions
443        //
444        case EOpConstructBool:
445            promoteTo = EbtBool;
446            break;
447        case EOpConstructFloat:
448            promoteTo = EbtFloat;
449            break;
450        case EOpConstructInt:
451            promoteTo = EbtInt;
452            break;
453        default:
454            //
455            // implicit conversions were removed from the language.
456            //
457            if (type.getBasicType() != node->getType().getBasicType())
458                return 0;
459            //
460            // Size and structure could still differ, but that's
461            // handled by operator promotion.
462            //
463            return node;
464    }
465
466    if (node->getAsConstantUnion()) {
467
468        return (promoteConstantUnion(promoteTo, node->getAsConstantUnion()));
469    } else {
470
471        //
472        // Add a new newNode for the conversion.
473        //
474        TIntermUnary* newNode = 0;
475
476        TOperator newOp = EOpNull;
477        switch (promoteTo) {
478            case EbtFloat:
479                switch (node->getBasicType()) {
480                    case EbtInt:   newOp = EOpConvIntToFloat;  break;
481                    case EbtBool:  newOp = EOpConvBoolToFloat; break;
482                    default:
483                        infoSink.info.message(EPrefixInternalError, node->getLine(), "Bad promotion node");
484                        return 0;
485                }
486                break;
487            case EbtBool:
488                switch (node->getBasicType()) {
489                    case EbtInt:   newOp = EOpConvIntToBool;   break;
490                    case EbtFloat: newOp = EOpConvFloatToBool; break;
491                    default:
492                        infoSink.info.message(EPrefixInternalError, node->getLine(), "Bad promotion node");
493                        return 0;
494                }
495                break;
496            case EbtInt:
497                switch (node->getBasicType()) {
498                    case EbtBool:   newOp = EOpConvBoolToInt;  break;
499                    case EbtFloat:  newOp = EOpConvFloatToInt; break;
500                    default:
501                        infoSink.info.message(EPrefixInternalError, node->getLine(), "Bad promotion node");
502                        return 0;
503                }
504                break;
505            default:
506                infoSink.info.message(EPrefixInternalError, node->getLine(), "Bad promotion type");
507                return 0;
508        }
509
510        TType type(promoteTo, node->getPrecision(), EvqTemporary, node->getNominalSize(), node->isMatrix(), node->isArray());
511        newNode = new TIntermUnary(newOp, type);
512        newNode->setLine(node->getLine());
513        newNode->setOperand(node);
514
515        return newNode;
516    }
517}
518
519//
520// Safe way to combine two nodes into an aggregate.  Works with null pointers,
521// a node that's not a aggregate yet, etc.
522//
523// Returns the resulting aggregate, unless 0 was passed in for
524// both existing nodes.
525//
526TIntermAggregate* TIntermediate::growAggregate(TIntermNode* left, TIntermNode* right, const TSourceLoc& line)
527{
528    if (left == 0 && right == 0)
529        return 0;
530
531    TIntermAggregate* aggNode = 0;
532    if (left)
533        aggNode = left->getAsAggregate();
534    if (!aggNode || aggNode->getOp() != EOpNull) {
535        aggNode = new TIntermAggregate;
536        if (left)
537            aggNode->getSequence().push_back(left);
538    }
539
540    if (right)
541        aggNode->getSequence().push_back(right);
542
543    aggNode->setLine(line);
544
545    return aggNode;
546}
547
548//
549// Turn an existing node into an aggregate.
550//
551// Returns an aggregate, unless 0 was passed in for the existing node.
552//
553TIntermAggregate* TIntermediate::makeAggregate(TIntermNode* node, const TSourceLoc& line)
554{
555    if (node == 0)
556        return 0;
557
558    TIntermAggregate* aggNode = new TIntermAggregate;
559    aggNode->getSequence().push_back(node);
560    aggNode->setLine(line);
561
562    return aggNode;
563}
564
565//
566// For "if" test nodes.  There are three children; a condition,
567// a true path, and a false path.  The two paths are in the
568// nodePair.
569//
570// Returns the selection node created.
571//
572TIntermNode* TIntermediate::addSelection(TIntermTyped* cond, TIntermNodePair nodePair, const TSourceLoc& line)
573{
574    //
575    // For compile time constant selections, prune the code and
576    // test now.
577    //
578
579    if (cond->getAsTyped() && cond->getAsTyped()->getAsConstantUnion()) {
580        if (cond->getAsConstantUnion()->getBConst(0) == true)
581            return nodePair.node1 ? setAggregateOperator(nodePair.node1, EOpSequence, nodePair.node1->getLine()) : NULL;
582        else
583            return nodePair.node2 ? setAggregateOperator(nodePair.node2, EOpSequence, nodePair.node2->getLine()) : NULL;
584    }
585
586    TIntermSelection* node = new TIntermSelection(cond, nodePair.node1, nodePair.node2);
587    node->setLine(line);
588
589    return node;
590}
591
592
593TIntermTyped* TIntermediate::addComma(TIntermTyped* left, TIntermTyped* right, const TSourceLoc& line)
594{
595    if (left->getType().getQualifier() == EvqConst && right->getType().getQualifier() == EvqConst) {
596        return right;
597    } else {
598        TIntermTyped *commaAggregate = growAggregate(left, right, line);
599        commaAggregate->getAsAggregate()->setOp(EOpComma);
600        commaAggregate->setType(right->getType());
601        commaAggregate->getTypePointer()->setQualifier(EvqTemporary);
602        return commaAggregate;
603    }
604}
605
606//
607// For "?:" test nodes.  There are three children; a condition,
608// a true path, and a false path.  The two paths are specified
609// as separate parameters.
610//
611// Returns the selection node created, or 0 if one could not be.
612//
613TIntermTyped* TIntermediate::addSelection(TIntermTyped* cond, TIntermTyped* trueBlock, TIntermTyped* falseBlock, const TSourceLoc& line)
614{
615    //
616    // Get compatible types.
617    //
618    TIntermTyped* child = addConversion(EOpSequence, trueBlock->getType(), falseBlock);
619    if (child)
620        falseBlock = child;
621    else {
622        child = addConversion(EOpSequence, falseBlock->getType(), trueBlock);
623        if (child)
624            trueBlock = child;
625        else
626            return 0;
627    }
628
629    //
630    // See if all the operands are constant, then fold it otherwise not.
631    //
632
633    if (cond->getAsConstantUnion() && trueBlock->getAsConstantUnion() && falseBlock->getAsConstantUnion()) {
634        if (cond->getAsConstantUnion()->getBConst(0))
635            return trueBlock;
636        else
637            return falseBlock;
638    }
639
640    //
641    // Make a selection node.
642    //
643    TIntermSelection* node = new TIntermSelection(cond, trueBlock, falseBlock, trueBlock->getType());
644    node->getTypePointer()->setQualifier(EvqTemporary);
645    node->setLine(line);
646
647    return node;
648}
649
650//
651// Constant terminal nodes.  Has a union that contains bool, float or int constants
652//
653// Returns the constant union node created.
654//
655
656TIntermConstantUnion* TIntermediate::addConstantUnion(ConstantUnion* unionArrayPointer, const TType& t, const TSourceLoc& line)
657{
658    TIntermConstantUnion* node = new TIntermConstantUnion(unionArrayPointer, t);
659    node->setLine(line);
660
661    return node;
662}
663
664TIntermTyped* TIntermediate::addSwizzle(TVectorFields& fields, const TSourceLoc& line)
665{
666
667    TIntermAggregate* node = new TIntermAggregate(EOpSequence);
668
669    node->setLine(line);
670    TIntermConstantUnion* constIntNode;
671    TIntermSequence &sequenceVector = node->getSequence();
672    ConstantUnion* unionArray;
673
674    for (int i = 0; i < fields.num; i++) {
675        unionArray = new ConstantUnion[1];
676        unionArray->setIConst(fields.offsets[i]);
677        constIntNode = addConstantUnion(unionArray, TType(EbtInt, EbpUndefined, EvqConst), line);
678        sequenceVector.push_back(constIntNode);
679    }
680
681    return node;
682}
683
684//
685// Create loop nodes.
686//
687TIntermNode* TIntermediate::addLoop(TLoopType type, TIntermNode* init, TIntermTyped* cond, TIntermTyped* expr, TIntermNode* body, const TSourceLoc& line)
688{
689    TIntermNode* node = new TIntermLoop(type, init, cond, expr, body);
690    node->setLine(line);
691
692    return node;
693}
694
695//
696// Add branches.
697//
698TIntermBranch* TIntermediate::addBranch(TOperator branchOp, const TSourceLoc& line)
699{
700    return addBranch(branchOp, 0, line);
701}
702
703TIntermBranch* TIntermediate::addBranch(TOperator branchOp, TIntermTyped* expression, const TSourceLoc& line)
704{
705    TIntermBranch* node = new TIntermBranch(branchOp, expression);
706    node->setLine(line);
707
708    return node;
709}
710
711//
712// This is to be executed once the final root is put on top by the parsing
713// process.
714//
715bool TIntermediate::postProcess(TIntermNode* root)
716{
717    if (root == 0)
718        return true;
719
720    //
721    // First, finish off the top level sequence, if any
722    //
723    TIntermAggregate* aggRoot = root->getAsAggregate();
724    if (aggRoot && aggRoot->getOp() == EOpNull)
725        aggRoot->setOp(EOpSequence);
726
727    return true;
728}
729
730//
731// This deletes the tree.
732//
733void TIntermediate::remove(TIntermNode* root)
734{
735    if (root)
736        RemoveAllTreeNodes(root);
737}
738
739////////////////////////////////////////////////////////////////
740//
741// Member functions of the nodes used for building the tree.
742//
743////////////////////////////////////////////////////////////////
744
745//
746// Say whether or not an operation node changes the value of a variable.
747//
748// Returns true if state is modified.
749//
750bool TIntermOperator::modifiesState() const
751{
752    switch (op) {
753        case EOpPostIncrement:
754        case EOpPostDecrement:
755        case EOpPreIncrement:
756        case EOpPreDecrement:
757        case EOpAssign:
758        case EOpAddAssign:
759        case EOpSubAssign:
760        case EOpMulAssign:
761        case EOpVectorTimesMatrixAssign:
762        case EOpVectorTimesScalarAssign:
763        case EOpMatrixTimesScalarAssign:
764        case EOpMatrixTimesMatrixAssign:
765        case EOpDivAssign:
766            return true;
767        default:
768            return false;
769    }
770}
771
772//
773// returns true if the operator is for one of the constructors
774//
775bool TIntermOperator::isConstructor() const
776{
777    switch (op) {
778        case EOpConstructVec2:
779        case EOpConstructVec3:
780        case EOpConstructVec4:
781        case EOpConstructMat2:
782        case EOpConstructMat3:
783        case EOpConstructMat4:
784        case EOpConstructFloat:
785        case EOpConstructIVec2:
786        case EOpConstructIVec3:
787        case EOpConstructIVec4:
788        case EOpConstructInt:
789        case EOpConstructBVec2:
790        case EOpConstructBVec3:
791        case EOpConstructBVec4:
792        case EOpConstructBool:
793        case EOpConstructStruct:
794            return true;
795        default:
796            return false;
797    }
798}
799//
800// Make sure the type of a unary operator is appropriate for its
801// combination of operation and operand type.
802//
803// Returns false in nothing makes sense.
804//
805bool TIntermUnary::promote(TInfoSink&)
806{
807    switch (op) {
808        case EOpLogicalNot:
809            if (operand->getBasicType() != EbtBool)
810                return false;
811            break;
812        case EOpNegative:
813        case EOpPostIncrement:
814        case EOpPostDecrement:
815        case EOpPreIncrement:
816        case EOpPreDecrement:
817            if (operand->getBasicType() == EbtBool)
818                return false;
819            break;
820
821            // operators for built-ins are already type checked against their prototype
822        case EOpAny:
823        case EOpAll:
824        case EOpVectorLogicalNot:
825            return true;
826
827        default:
828            if (operand->getBasicType() != EbtFloat)
829                return false;
830    }
831
832    setType(operand->getType());
833    type.setQualifier(EvqTemporary);
834
835    return true;
836}
837
838//
839// Establishes the type of the resultant operation, as well as
840// makes the operator the correct one for the operands.
841//
842// Returns false if operator can't work on operands.
843//
844bool TIntermBinary::promote(TInfoSink& infoSink)
845{
846    // This function only handles scalars, vectors, and matrices.
847    if (left->isArray() || right->isArray()) {
848        infoSink.info.message(EPrefixInternalError, getLine(), "Invalid operation for arrays");
849        return false;
850    }
851
852    // GLSL ES 2.0 does not support implicit type casting.
853    // So the basic type should always match.
854    if (left->getBasicType() != right->getBasicType())
855        return false;
856
857    //
858    // Base assumption:  just make the type the same as the left
859    // operand.  Then only deviations from this need be coded.
860    //
861    setType(left->getType());
862
863    // The result gets promoted to the highest precision.
864    TPrecision higherPrecision = GetHigherPrecision(left->getPrecision(), right->getPrecision());
865    getTypePointer()->setPrecision(higherPrecision);
866
867    // Binary operations results in temporary variables unless both
868    // operands are const.
869    if (left->getQualifier() != EvqConst || right->getQualifier() != EvqConst) {
870        getTypePointer()->setQualifier(EvqTemporary);
871    }
872
873    int size = std::max(left->getNominalSize(), right->getNominalSize());
874
875    //
876    // All scalars. Code after this test assumes this case is removed!
877    //
878    if (size == 1) {
879        switch (op) {
880            //
881            // Promote to conditional
882            //
883            case EOpEqual:
884            case EOpNotEqual:
885            case EOpLessThan:
886            case EOpGreaterThan:
887            case EOpLessThanEqual:
888            case EOpGreaterThanEqual:
889                setType(TType(EbtBool, EbpUndefined));
890                break;
891
892            //
893            // And and Or operate on conditionals
894            //
895            case EOpLogicalAnd:
896            case EOpLogicalOr:
897                // Both operands must be of type bool.
898                if (left->getBasicType() != EbtBool || right->getBasicType() != EbtBool)
899                    return false;
900                setType(TType(EbtBool, EbpUndefined));
901                break;
902
903            default:
904                break;
905        }
906        return true;
907    }
908
909    // If we reach here, at least one of the operands is vector or matrix.
910    // The other operand could be a scalar, vector, or matrix.
911    // Are the sizes compatible?
912    //
913    if (left->getNominalSize() != right->getNominalSize()) {
914        // If the nominal size of operands do not match:
915        // One of them must be scalar.
916        if (left->getNominalSize() != 1 && right->getNominalSize() != 1)
917            return false;
918        // Operator cannot be of type pure assignment.
919        if (op == EOpAssign || op == EOpInitialize)
920            return false;
921    }
922
923    //
924    // Can these two operands be combined?
925    //
926    TBasicType basicType = left->getBasicType();
927    switch (op) {
928        case EOpMul:
929            if (!left->isMatrix() && right->isMatrix()) {
930                if (left->isVector())
931                    op = EOpVectorTimesMatrix;
932                else {
933                    op = EOpMatrixTimesScalar;
934                    setType(TType(basicType, higherPrecision, EvqTemporary, size, true));
935                }
936            } else if (left->isMatrix() && !right->isMatrix()) {
937                if (right->isVector()) {
938                    op = EOpMatrixTimesVector;
939                    setType(TType(basicType, higherPrecision, EvqTemporary, size, false));
940                } else {
941                    op = EOpMatrixTimesScalar;
942                }
943            } else if (left->isMatrix() && right->isMatrix()) {
944                op = EOpMatrixTimesMatrix;
945            } else if (!left->isMatrix() && !right->isMatrix()) {
946                if (left->isVector() && right->isVector()) {
947                    // leave as component product
948                } else if (left->isVector() || right->isVector()) {
949                    op = EOpVectorTimesScalar;
950                    setType(TType(basicType, higherPrecision, EvqTemporary, size, false));
951                }
952            } else {
953                infoSink.info.message(EPrefixInternalError, getLine(), "Missing elses");
954                return false;
955            }
956            break;
957        case EOpMulAssign:
958            if (!left->isMatrix() && right->isMatrix()) {
959                if (left->isVector())
960                    op = EOpVectorTimesMatrixAssign;
961                else {
962                    return false;
963                }
964            } else if (left->isMatrix() && !right->isMatrix()) {
965                if (right->isVector()) {
966                    return false;
967                } else {
968                    op = EOpMatrixTimesScalarAssign;
969                }
970            } else if (left->isMatrix() && right->isMatrix()) {
971                op = EOpMatrixTimesMatrixAssign;
972            } else if (!left->isMatrix() && !right->isMatrix()) {
973                if (left->isVector() && right->isVector()) {
974                    // leave as component product
975                } else if (left->isVector() || right->isVector()) {
976                    if (! left->isVector())
977                        return false;
978                    op = EOpVectorTimesScalarAssign;
979                    setType(TType(basicType, higherPrecision, EvqTemporary, size, false));
980                }
981            } else {
982                infoSink.info.message(EPrefixInternalError, getLine(), "Missing elses");
983                return false;
984            }
985            break;
986
987        case EOpAssign:
988        case EOpInitialize:
989        case EOpAdd:
990        case EOpSub:
991        case EOpDiv:
992        case EOpAddAssign:
993        case EOpSubAssign:
994        case EOpDivAssign:
995            if ((left->isMatrix() && right->isVector()) ||
996                (left->isVector() && right->isMatrix()))
997                return false;
998            setType(TType(basicType, higherPrecision, EvqTemporary, size, left->isMatrix() || right->isMatrix()));
999            break;
1000
1001        case EOpEqual:
1002        case EOpNotEqual:
1003        case EOpLessThan:
1004        case EOpGreaterThan:
1005        case EOpLessThanEqual:
1006        case EOpGreaterThanEqual:
1007            if ((left->isMatrix() && right->isVector()) ||
1008                (left->isVector() && right->isMatrix()))
1009                return false;
1010            setType(TType(EbtBool, EbpUndefined));
1011            break;
1012
1013        default:
1014            return false;
1015    }
1016
1017    return true;
1018}
1019
1020bool CompareStruct(const TType& leftNodeType, ConstantUnion* rightUnionArray, ConstantUnion* leftUnionArray)
1021{
1022    const TFieldList& fields = leftNodeType.getStruct()->fields();
1023
1024    size_t structSize = fields.size();
1025    size_t index = 0;
1026
1027    for (size_t j = 0; j < structSize; j++) {
1028        size_t size = fields[j]->type()->getObjectSize();
1029        for (size_t i = 0; i < size; i++) {
1030            if (fields[j]->type()->getBasicType() == EbtStruct) {
1031                if (!CompareStructure(*(fields[j]->type()), &rightUnionArray[index], &leftUnionArray[index]))
1032                    return false;
1033            } else {
1034                if (leftUnionArray[index] != rightUnionArray[index])
1035                    return false;
1036                index++;
1037            }
1038        }
1039    }
1040    return true;
1041}
1042
1043bool CompareStructure(const TType& leftNodeType, ConstantUnion* rightUnionArray, ConstantUnion* leftUnionArray)
1044{
1045    if (leftNodeType.isArray()) {
1046        TType typeWithoutArrayness = leftNodeType;
1047        typeWithoutArrayness.clearArrayness();
1048
1049        size_t arraySize = leftNodeType.getArraySize();
1050
1051        for (size_t i = 0; i < arraySize; ++i) {
1052            size_t offset = typeWithoutArrayness.getObjectSize() * i;
1053            if (!CompareStruct(typeWithoutArrayness, &rightUnionArray[offset], &leftUnionArray[offset]))
1054                return false;
1055        }
1056    } else
1057        return CompareStruct(leftNodeType, rightUnionArray, leftUnionArray);
1058
1059    return true;
1060}
1061
1062//
1063// The fold functions see if an operation on a constant can be done in place,
1064// without generating run-time code.
1065//
1066// Returns the node to keep using, which may or may not be the node passed in.
1067//
1068
1069TIntermTyped* TIntermConstantUnion::fold(TOperator op, TIntermTyped* constantNode, TInfoSink& infoSink)
1070{
1071    ConstantUnion *unionArray = getUnionArrayPointer();
1072    size_t objectSize = getType().getObjectSize();
1073
1074    if (constantNode) {  // binary operations
1075        TIntermConstantUnion *node = constantNode->getAsConstantUnion();
1076        ConstantUnion *rightUnionArray = node->getUnionArrayPointer();
1077        TType returnType = getType();
1078
1079        // for a case like float f = 1.2 + vec4(2,3,4,5);
1080        if (constantNode->getType().getObjectSize() == 1 && objectSize > 1) {
1081            rightUnionArray = new ConstantUnion[objectSize];
1082            for (size_t i = 0; i < objectSize; ++i)
1083                rightUnionArray[i] = *node->getUnionArrayPointer();
1084            returnType = getType();
1085        } else if (constantNode->getType().getObjectSize() > 1 && objectSize == 1) {
1086            // for a case like float f = vec4(2,3,4,5) + 1.2;
1087            unionArray = new ConstantUnion[constantNode->getType().getObjectSize()];
1088            for (size_t i = 0; i < constantNode->getType().getObjectSize(); ++i)
1089                unionArray[i] = *getUnionArrayPointer();
1090            returnType = node->getType();
1091            objectSize = constantNode->getType().getObjectSize();
1092        }
1093
1094        ConstantUnion* tempConstArray = 0;
1095        TIntermConstantUnion *tempNode;
1096
1097        bool boolNodeFlag = false;
1098        switch(op) {
1099            case EOpAdd:
1100                tempConstArray = new ConstantUnion[objectSize];
1101                {// support MSVC++6.0
1102                    for (size_t i = 0; i < objectSize; i++)
1103                        tempConstArray[i] = unionArray[i] + rightUnionArray[i];
1104                }
1105                break;
1106            case EOpSub:
1107                tempConstArray = new ConstantUnion[objectSize];
1108                {// support MSVC++6.0
1109                    for (size_t i = 0; i < objectSize; i++)
1110                        tempConstArray[i] = unionArray[i] - rightUnionArray[i];
1111                }
1112                break;
1113
1114            case EOpMul:
1115            case EOpVectorTimesScalar:
1116            case EOpMatrixTimesScalar:
1117                tempConstArray = new ConstantUnion[objectSize];
1118                {// support MSVC++6.0
1119                    for (size_t i = 0; i < objectSize; i++)
1120                        tempConstArray[i] = unionArray[i] * rightUnionArray[i];
1121                }
1122                break;
1123            case EOpMatrixTimesMatrix:
1124                if (getType().getBasicType() != EbtFloat || node->getBasicType() != EbtFloat) {
1125                    infoSink.info.message(EPrefixInternalError, getLine(), "Constant Folding cannot be done for matrix multiply");
1126                    return 0;
1127                }
1128                {// support MSVC++6.0
1129                    int size = getNominalSize();
1130                    tempConstArray = new ConstantUnion[size*size];
1131                    for (int row = 0; row < size; row++) {
1132                        for (int column = 0; column < size; column++) {
1133                            tempConstArray[size * column + row].setFConst(0.0f);
1134                            for (int i = 0; i < size; i++) {
1135                                tempConstArray[size * column + row].setFConst(tempConstArray[size * column + row].getFConst() + unionArray[i * size + row].getFConst() * (rightUnionArray[column * size + i].getFConst()));
1136                            }
1137                        }
1138                    }
1139                }
1140                break;
1141            case EOpDiv:
1142                tempConstArray = new ConstantUnion[objectSize];
1143                {// support MSVC++6.0
1144                    for (size_t i = 0; i < objectSize; i++) {
1145                        switch (getType().getBasicType()) {
1146            case EbtFloat:
1147                if (rightUnionArray[i] == 0.0f) {
1148                    infoSink.info.message(EPrefixWarning, getLine(), "Divide by zero error during constant folding");
1149                    tempConstArray[i].setFConst(unionArray[i].getFConst() < 0 ? -FLT_MAX : FLT_MAX);
1150                } else
1151                    tempConstArray[i].setFConst(unionArray[i].getFConst() / rightUnionArray[i].getFConst());
1152                break;
1153
1154            case EbtInt:
1155                if (rightUnionArray[i] == 0) {
1156                    infoSink.info.message(EPrefixWarning, getLine(), "Divide by zero error during constant folding");
1157                    tempConstArray[i].setIConst(INT_MAX);
1158                } else
1159                    tempConstArray[i].setIConst(unionArray[i].getIConst() / rightUnionArray[i].getIConst());
1160                break;
1161            default:
1162                infoSink.info.message(EPrefixInternalError, getLine(), "Constant folding cannot be done for \"/\"");
1163                return 0;
1164                        }
1165                    }
1166                }
1167                break;
1168
1169            case EOpMatrixTimesVector:
1170                if (node->getBasicType() != EbtFloat) {
1171                    infoSink.info.message(EPrefixInternalError, getLine(), "Constant Folding cannot be done for matrix times vector");
1172                    return 0;
1173                }
1174                tempConstArray = new ConstantUnion[getNominalSize()];
1175
1176                {// support MSVC++6.0
1177                    for (int size = getNominalSize(), i = 0; i < size; i++) {
1178                        tempConstArray[i].setFConst(0.0f);
1179                        for (int j = 0; j < size; j++) {
1180                            tempConstArray[i].setFConst(tempConstArray[i].getFConst() + ((unionArray[j*size + i].getFConst()) * rightUnionArray[j].getFConst()));
1181                        }
1182                    }
1183                }
1184
1185                tempNode = new TIntermConstantUnion(tempConstArray, node->getType());
1186                tempNode->setLine(getLine());
1187
1188                return tempNode;
1189
1190            case EOpVectorTimesMatrix:
1191                if (getType().getBasicType() != EbtFloat) {
1192                    infoSink.info.message(EPrefixInternalError, getLine(), "Constant Folding cannot be done for vector times matrix");
1193                    return 0;
1194                }
1195
1196                tempConstArray = new ConstantUnion[getNominalSize()];
1197                {// support MSVC++6.0
1198                    for (int size = getNominalSize(), i = 0; i < size; i++) {
1199                        tempConstArray[i].setFConst(0.0f);
1200                        for (int j = 0; j < size; j++) {
1201                            tempConstArray[i].setFConst(tempConstArray[i].getFConst() + ((unionArray[j].getFConst()) * rightUnionArray[i*size + j].getFConst()));
1202                        }
1203                    }
1204                }
1205                break;
1206
1207            case EOpLogicalAnd: // this code is written for possible future use, will not get executed currently
1208                tempConstArray = new ConstantUnion[objectSize];
1209                {// support MSVC++6.0
1210                    for (size_t i = 0; i < objectSize; i++)
1211                        tempConstArray[i] = unionArray[i] && rightUnionArray[i];
1212                }
1213                break;
1214
1215            case EOpLogicalOr: // this code is written for possible future use, will not get executed currently
1216                tempConstArray = new ConstantUnion[objectSize];
1217                {// support MSVC++6.0
1218                    for (size_t i = 0; i < objectSize; i++)
1219                        tempConstArray[i] = unionArray[i] || rightUnionArray[i];
1220                }
1221                break;
1222
1223            case EOpLogicalXor:
1224                tempConstArray = new ConstantUnion[objectSize];
1225                {// support MSVC++6.0
1226                    for (size_t i = 0; i < objectSize; i++)
1227                        switch (getType().getBasicType()) {
1228            case EbtBool: tempConstArray[i].setBConst((unionArray[i] == rightUnionArray[i]) ? false : true); break;
1229            default: assert(false && "Default missing");
1230                    }
1231                }
1232                break;
1233
1234            case EOpLessThan:
1235                assert(objectSize == 1);
1236                tempConstArray = new ConstantUnion[1];
1237                tempConstArray->setBConst(*unionArray < *rightUnionArray);
1238                returnType = TType(EbtBool, EbpUndefined, EvqConst);
1239                break;
1240            case EOpGreaterThan:
1241                assert(objectSize == 1);
1242                tempConstArray = new ConstantUnion[1];
1243                tempConstArray->setBConst(*unionArray > *rightUnionArray);
1244                returnType = TType(EbtBool, EbpUndefined, EvqConst);
1245                break;
1246            case EOpLessThanEqual:
1247                {
1248                    assert(objectSize == 1);
1249                    ConstantUnion constant;
1250                    constant.setBConst(*unionArray > *rightUnionArray);
1251                    tempConstArray = new ConstantUnion[1];
1252                    tempConstArray->setBConst(!constant.getBConst());
1253                    returnType = TType(EbtBool, EbpUndefined, EvqConst);
1254                    break;
1255                }
1256            case EOpGreaterThanEqual:
1257                {
1258                    assert(objectSize == 1);
1259                    ConstantUnion constant;
1260                    constant.setBConst(*unionArray < *rightUnionArray);
1261                    tempConstArray = new ConstantUnion[1];
1262                    tempConstArray->setBConst(!constant.getBConst());
1263                    returnType = TType(EbtBool, EbpUndefined, EvqConst);
1264                    break;
1265                }
1266
1267            case EOpEqual:
1268                if (getType().getBasicType() == EbtStruct) {
1269                    if (!CompareStructure(node->getType(), node->getUnionArrayPointer(), unionArray))
1270                        boolNodeFlag = true;
1271                } else {
1272                    for (size_t i = 0; i < objectSize; i++) {
1273                        if (unionArray[i] != rightUnionArray[i]) {
1274                            boolNodeFlag = true;
1275                            break;  // break out of for loop
1276                        }
1277                    }
1278                }
1279
1280                tempConstArray = new ConstantUnion[1];
1281                if (!boolNodeFlag) {
1282                    tempConstArray->setBConst(true);
1283                }
1284                else {
1285                    tempConstArray->setBConst(false);
1286                }
1287
1288                tempNode = new TIntermConstantUnion(tempConstArray, TType(EbtBool, EbpUndefined, EvqConst));
1289                tempNode->setLine(getLine());
1290
1291                return tempNode;
1292
1293            case EOpNotEqual:
1294                if (getType().getBasicType() == EbtStruct) {
1295                    if (CompareStructure(node->getType(), node->getUnionArrayPointer(), unionArray))
1296                        boolNodeFlag = true;
1297                } else {
1298                    for (size_t i = 0; i < objectSize; i++) {
1299                        if (unionArray[i] == rightUnionArray[i]) {
1300                            boolNodeFlag = true;
1301                            break;  // break out of for loop
1302                        }
1303                    }
1304                }
1305
1306                tempConstArray = new ConstantUnion[1];
1307                if (!boolNodeFlag) {
1308                    tempConstArray->setBConst(true);
1309                }
1310                else {
1311                    tempConstArray->setBConst(false);
1312                }
1313
1314                tempNode = new TIntermConstantUnion(tempConstArray, TType(EbtBool, EbpUndefined, EvqConst));
1315                tempNode->setLine(getLine());
1316
1317                return tempNode;
1318
1319            default:
1320                infoSink.info.message(EPrefixInternalError, getLine(), "Invalid operator for constant folding");
1321                return 0;
1322        }
1323        tempNode = new TIntermConstantUnion(tempConstArray, returnType);
1324        tempNode->setLine(getLine());
1325
1326        return tempNode;
1327    } else {
1328        //
1329        // Do unary operations
1330        //
1331        TIntermConstantUnion *newNode = 0;
1332        ConstantUnion* tempConstArray = new ConstantUnion[objectSize];
1333        for (size_t i = 0; i < objectSize; i++) {
1334            switch(op) {
1335                case EOpNegative:
1336                    switch (getType().getBasicType()) {
1337                        case EbtFloat: tempConstArray[i].setFConst(-unionArray[i].getFConst()); break;
1338                        case EbtInt:   tempConstArray[i].setIConst(-unionArray[i].getIConst()); break;
1339                        default:
1340                            infoSink.info.message(EPrefixInternalError, getLine(), "Unary operation not folded into constant");
1341                            return 0;
1342                    }
1343                    break;
1344                case EOpLogicalNot: // this code is written for possible future use, will not get executed currently
1345                    switch (getType().getBasicType()) {
1346                        case EbtBool:  tempConstArray[i].setBConst(!unionArray[i].getBConst()); break;
1347                        default:
1348                            infoSink.info.message(EPrefixInternalError, getLine(), "Unary operation not folded into constant");
1349                            return 0;
1350                    }
1351                    break;
1352                default:
1353                    return 0;
1354            }
1355        }
1356        newNode = new TIntermConstantUnion(tempConstArray, getType());
1357        newNode->setLine(getLine());
1358        return newNode;
1359    }
1360}
1361
1362TIntermTyped* TIntermediate::promoteConstantUnion(TBasicType promoteTo, TIntermConstantUnion* node)
1363{
1364    size_t size = node->getType().getObjectSize();
1365
1366    ConstantUnion *leftUnionArray = new ConstantUnion[size];
1367
1368    for (size_t i = 0; i < size; i++) {
1369
1370        switch (promoteTo) {
1371            case EbtFloat:
1372                switch (node->getType().getBasicType()) {
1373                    case EbtInt:
1374                        leftUnionArray[i].setFConst(static_cast<float>(node->getIConst(i)));
1375                        break;
1376                    case EbtBool:
1377                        leftUnionArray[i].setFConst(static_cast<float>(node->getBConst(i)));
1378                        break;
1379                    case EbtFloat:
1380                        leftUnionArray[i].setFConst(static_cast<float>(node->getFConst(i)));
1381                        break;
1382                    default:
1383                        infoSink.info.message(EPrefixInternalError, node->getLine(), "Cannot promote");
1384                        return 0;
1385                }
1386                break;
1387            case EbtInt:
1388                switch (node->getType().getBasicType()) {
1389                    case EbtInt:
1390                        leftUnionArray[i].setIConst(static_cast<int>(node->getIConst(i)));
1391                        break;
1392                    case EbtBool:
1393                        leftUnionArray[i].setIConst(static_cast<int>(node->getBConst(i)));
1394                        break;
1395                    case EbtFloat:
1396                        leftUnionArray[i].setIConst(static_cast<int>(node->getFConst(i)));
1397                        break;
1398                    default:
1399                        infoSink.info.message(EPrefixInternalError, node->getLine(), "Cannot promote");
1400                        return 0;
1401                }
1402                break;
1403            case EbtBool:
1404                switch (node->getType().getBasicType()) {
1405                    case EbtInt:
1406                        leftUnionArray[i].setBConst(node->getIConst(i) != 0);
1407                        break;
1408                    case EbtBool:
1409                        leftUnionArray[i].setBConst(node->getBConst(i));
1410                        break;
1411                    case EbtFloat:
1412                        leftUnionArray[i].setBConst(node->getFConst(i) != 0.0f);
1413                        break;
1414                    default:
1415                        infoSink.info.message(EPrefixInternalError, node->getLine(), "Cannot promote");
1416                        return 0;
1417                }
1418
1419                break;
1420            default:
1421                infoSink.info.message(EPrefixInternalError, node->getLine(), "Incorrect data type found");
1422                return 0;
1423        }
1424
1425    }
1426
1427    const TType& t = node->getType();
1428
1429    return addConstantUnion(leftUnionArray, TType(promoteTo, t.getPrecision(), t.getQualifier(), t.getNominalSize(), t.isMatrix(), t.isArray()), node->getLine());
1430}
1431
1432// static
1433TString TIntermTraverser::hash(const TString& name, ShHashFunction64 hashFunction)
1434{
1435    if (hashFunction == NULL || name.empty())
1436        return name;
1437    khronos_uint64_t number = (*hashFunction)(name.c_str(), name.length());
1438    TStringStream stream;
1439    stream << HASHED_NAME_PREFIX << std::hex << number;
1440    TString hashedName = stream.str();
1441    return hashedName;
1442}
1443