source: src/ResolvExpr/ConversionCost.cc @ 8e18b8e

new-envwith_gc
Last change on this file since 8e18b8e was 8e18b8e, checked in by Aaron Moss <a3moss@…>, 4 years ago

stop eagerly copying EqvClass? on lookup

  • Property mode set to 100644
File size: 18.3 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// ConversionCost.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sun May 17 07:06:19 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Mon Sep 25 15:43:34 2017
13// Update Count     : 10
14//
15
16#include "ConversionCost.h"
17
18#include <cassert>                       // for assert
19#include <list>                          // for list, list<>::const_iterator
20#include <string>                        // for operator==, string
21
22#include "Common/GC.h"                   // for new_static_root
23#include "ResolvExpr/Cost.h"             // for Cost
24#include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
25#include "SymTab/Indexer.h"              // for Indexer
26#include "SynTree/Declaration.h"         // for TypeDecl, NamedTypeDecl
27#include "SynTree/Type.h"                // for Type, BasicType, TypeInstType
28#include "typeops.h"                     // for typesCompatibleIgnoreQualifiers
29
30namespace ResolvExpr {
31        const Cost Cost::zero =      Cost(  0,  0,  0,  0 );
32        const Cost Cost::infinity =  Cost( -1, -1, -1, -1 );
33        const Cost Cost::unsafe =    Cost(  1,  0,  0,  0 );
34        const Cost Cost::poly =      Cost(  0,  1,  0,  0 );
35        const Cost Cost::safe =      Cost(  0,  0,  1,  0 );
36        const Cost Cost::reference = Cost(  0,  0,  0,  1 );
37
38#if 0
39#define PRINT(x) x
40#else
41#define PRINT(x)
42#endif
43        Cost conversionCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
44                if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
45                        PRINT( std::cerr << "type inst " << destAsTypeInst->name; )
46                        if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->name ) ) {
47                                if ( eqvClass->type ) {
48                                        return conversionCost( src, eqvClass->type, indexer, env );
49                                } else {
50                                        return Cost::infinity;
51                                }
52                        } else if ( NamedTypeDecl *namedType = indexer.lookupType( destAsTypeInst->name ) ) {
53                                PRINT( std::cerr << " found" << std::endl; )
54                                TypeDecl *type = dynamic_cast< TypeDecl* >( namedType );
55                                // all typedefs should be gone by this point
56                                assert( type );
57                                if ( type->base ) {
58                                        return conversionCost( src, type->base, indexer, env ) + Cost::safe;
59                                } // if
60                        } // if
61                        PRINT( std::cerr << " not found" << std::endl; )
62                } // if
63                PRINT(
64                        std::cerr << "src is ";
65                        src->print( std::cerr );
66                        std::cerr << std::endl << "dest is ";
67                        dest->print( std::cerr );
68                        std::cerr << std::endl << "env is" << std::endl;
69                        env.print( std::cerr, 8 );
70                )
71                if ( typesCompatibleIgnoreQualifiers( src, dest, indexer, env ) ) {
72                        PRINT( std::cerr << "compatible!" << std::endl; )
73                        return Cost::zero;
74                } else if ( dynamic_cast< VoidType* >( dest ) ) {
75                        return Cost::safe;
76                } else if ( ReferenceType * refType = dynamic_cast< ReferenceType * > ( dest ) ) {
77                        PRINT( std::cerr << "conversionCost: dest is reference" << std::endl; )
78                        return convertToReferenceCost( src, refType, indexer, env, [](Type * t1, Type * t2, const SymTab::Indexer &, const TypeEnvironment & env ){
79                                return ptrsAssignable( t1, t2, env );
80                        });
81                } else {
82                        PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
83                        src->accept( converter );
84                        if ( converter.pass.get_cost() == Cost::infinity ) {
85                                return Cost::infinity;
86                        } else {
87                                return converter.pass.get_cost() + Cost::zero;
88                        } // if
89                } // if
90        }
91
92        Cost convertToReferenceCost( Type * src, Type * dest, int diff, const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func ) {
93                PRINT( std::cerr << "convert to reference cost... diff " << diff << " " << src << " / " << dest << std::endl; )
94                if ( diff > 0 ) {
95                        // TODO: document this
96                        Cost cost = convertToReferenceCost( strict_dynamic_cast< ReferenceType * >( src )->base, dest, diff-1, indexer, env, func );
97                        cost.incReference();
98                        return cost;
99                } else if ( diff < -1 ) {
100                        // TODO: document this
101                        Cost cost = convertToReferenceCost( src, strict_dynamic_cast< ReferenceType * >( dest )->base, diff+1, indexer, env, func );
102                        cost.incReference();
103                        return cost;
104                } else if ( diff == 0 ) {
105                        ReferenceType * srcAsRef = dynamic_cast< ReferenceType * >( src );
106                        ReferenceType * destAsRef = dynamic_cast< ReferenceType * >( dest );
107                        if ( srcAsRef && destAsRef ) { // pointer-like conversions between references
108                                PRINT( std::cerr << "converting between references" << std::endl; )
109                                Type::Qualifiers tq1 = srcAsRef->base->get_qualifiers();
110                                Type::Qualifiers tq2 = destAsRef->base->get_qualifiers();
111                                if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers( srcAsRef->base, destAsRef->base, indexer, env ) ) {
112                                        PRINT( std::cerr << " :: compatible and good qualifiers" << std::endl; )
113                                        if ( tq1 == tq2 ) {
114                                                // types are the same
115                                                return Cost::zero;
116                                        } else {
117                                                // types are the same, except otherPointer has more qualifiers
118                                                return Cost::safe;
119                                        }
120                                } else {  // xxx - this discards reference qualifiers from consideration -- reducing qualifiers is a safe conversion; is this right?
121                                        int assignResult = func( srcAsRef->base, destAsRef->base, indexer, env );
122                                        PRINT( std::cerr << "comparing references: " << assignResult << " " << srcAsRef << " " << destAsRef << std::endl; )
123                                        if ( assignResult > 0 ) {
124                                                return Cost::safe;
125                                        } else if ( assignResult < 0 ) {
126                                                return Cost::unsafe;
127                                        } // if
128                                } // if
129                        } else {
130                                PRINT( std::cerr << "reference to rvalue conversion" << std::endl; )
131                                PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
132                                src->accept( converter );
133                                return converter.pass.get_cost();
134                        } // if
135                } else {
136                        ReferenceType * destAsRef = dynamic_cast< ReferenceType * >( dest );
137                        assert( diff == -1 && destAsRef );
138                        PRINT( std::cerr << "dest is: " << dest << " / src is: " << src << std::endl; )
139                        if ( typesCompatibleIgnoreQualifiers( src, destAsRef->base, indexer, env ) ) {
140                                PRINT( std::cerr << "converting compatible base type" << std::endl; )
141                                if ( src->get_lvalue() ) {
142                                        PRINT(
143                                                std::cerr << "lvalue to reference conversion" << std::endl;
144                                                std::cerr << src << " => " << destAsRef << std::endl;
145                                        )
146                                        // lvalue-to-reference conversion:  cv lvalue T => cv T &
147                                        if ( src->get_qualifiers() == destAsRef->base->get_qualifiers() ) {
148                                                return Cost::reference; // cost needs to be non-zero to add cast
149                                        } if ( src->get_qualifiers() < destAsRef->base->get_qualifiers() ) {
150                                                return Cost::safe; // cost needs to be higher than previous cast to differentiate adding qualifiers vs. keeping same
151                                        } else {
152                                                return Cost::unsafe;
153                                        } // if
154                                } else if ( destAsRef->base->get_const() ) {
155                                        PRINT( std::cerr << "rvalue to const ref conversion" << std::endl; )
156                                        // rvalue-to-const-reference conversion: T => const T &
157                                        return Cost::safe;
158                                } else {
159                                        PRINT( std::cerr << "rvalue to non-const reference conversion" << std::endl; )
160                                        // rvalue-to-reference conversion: T => T &
161                                        return Cost::unsafe;
162                                } // if
163                        } // if
164                        PRINT( std::cerr << "attempting to convert from incompatible base type -- fail" << std::endl; )
165                }
166                return Cost::infinity;
167        }
168
169        Cost convertToReferenceCost( Type * src, ReferenceType * dest, const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func ) {
170                int sdepth = src->referenceDepth(), ddepth = dest->referenceDepth();
171                Cost cost = convertToReferenceCost( src, dest, sdepth-ddepth, indexer, env, func );
172                PRINT( std::cerr << "convertToReferenceCost result: " << cost << std::endl; )
173                return cost;
174        }
175
176        ConversionCost::ConversionCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc )
177                : dest( dest ), indexer( indexer ), cost( Cost::infinity ), env( env ), costFunc( costFunc ) {
178        }
179
180/*
181            Old
182            ===
183           Double
184             |
185           Float
186             |
187           ULong
188           /   \
189        UInt    Long
190           \   /
191            Int
192             |
193           Ushort
194             |
195           Short
196             |
197           Uchar
198           /   \
199        Schar   Char
200
201                                New
202                                ===
203                       +-----LongDoubleComplex--+
204           LongDouble--+          |             +-LongDoubleImag
205             |         +---DoubleComplex---+         |
206           Double------+        |          +----DoubleImag
207             |           +-FloatComplex-+            |
208           Float---------+              +-------FloatImag
209             |
210          ULongLong
211             |
212          LongLong
213             |
214           ULong
215           /   \
216        UInt    Long
217           \   /
218            Int
219             |
220           Ushort
221             |
222           Short
223             |
224           Uchar
225           /   \
226        Schar   Char
227           \   /
228            Bool
229*/
230
231        static const int costMatrix[ BasicType::NUMBER_OF_BASIC_TYPES ][ BasicType::NUMBER_OF_BASIC_TYPES ] = {
232        /* Src \ Dest:  Bool    Char    SChar   UChar   Short   UShort  Int     UInt    Long    ULong   LLong   ULLong  Float   Double  LDbl    FCplex  DCplex  LDCplex FImag   DImag   LDImag  I128,   U128 */
233                /* Bool */      { 0,    1,              1,              2,              3,              4,              5,              6,              6,              7,              8,              9,              12,             13,             14,             12,             13,             14,             -1,             -1,             -1,             10,             11,     },
234                /* Char */      { -1,   0,              -1,             1,              2,              3,              4,              5,              5,              6,              7,              8,              11,             12,             13,             11,             12,             13,             -1,             -1,             -1,             9,              10,     },
235                /* SChar */ { -1,       -1,             0,              1,              2,              3,              4,              5,              5,              6,              7,              8,              11,             12,             13,             11,             12,             13,             -1,             -1,             -1,             9,              10,     },
236                /* UChar */ { -1,       -1,             -1,             0,              1,              2,              3,              4,              4,              5,              6,              7,              10,             11,             12,             10,             11,             12,             -1,             -1,             -1,             8,              9,      },
237                /* Short */ { -1,       -1,             -1,             -1,             0,              1,              2,              3,              3,              4,              5,              6,              9,              10,             11,             9,              10,             11,             -1,             -1,             -1,             7,              8,      },
238                /* UShort */{ -1,       -1,             -1,             -1,             -1,             0,              1,              2,              2,              3,              4,              5,              8,              9,              10,             8,              9,              10,             -1,             -1,             -1,             6,              7,      },
239                /* Int */       { -1,   -1,             -1,             -1,             -1,             -1,             0,              1,              1,              2,              3,              4,              7,              8,              9,              7,              8,              9,              -1,             -1,             -1,             5,              6,      },
240                /* UInt */      { -1,   -1,             -1,             -1,             -1,             -1,             -1,             0,              -1,             1,              2,              3,              6,              7,              8,              6,              7,              8,              -1,             -1,             -1,             4,              5,      },
241                /* Long */      { -1,   -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              1,              2,              3,              6,              7,              8,              6,              7,              8,              -1,             -1,             -1,             4,              5,      },
242                /* ULong */ { -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              1,              2,              5,              6,              7,              5,              6,              7,              -1,             -1,             -1,             3,              4,      },
243                /* LLong */ { -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              1,              4,              5,              6,              4,              5,              6,              -1,             -1,             -1,             2,              3,      },
244                /* ULLong */{ -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              3,              4,              5,              3,              4,              5,              -1,             -1,             -1,             1,              2,      },
245
246                /* Float */ { -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              1,              2,              1,              2,              3,              -1,             -1,             -1,             -1,             -1,     },
247                /* Double */{ -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              1,              -1,             1,              2,              -1,             -1,             -1,             -1,             -1,     },
248                /* LDbl */      { -1,   -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              -1,             -1,             1,              -1,             -1,             -1,             -1,             -1,     },
249                /* FCplex */{ -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              1,              2,              -1,             -1,             -1,             -1,             -1,     },
250                /* DCplex */{ -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              1,              -1,             -1,             -1,             -1,             -1,     },
251                /* LDCplex */{ -1,      -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             0,              -1,             -1,             -1,             -1,             -1,     },
252                /* FImag */ { -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             1,              2,              3,              0,              1,              2,              -1,             -1,     },
253                /* DImag */ { -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             1,              2,              -1,             0,              1,              -1,             -1,     },
254                /* LDImag */{ -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             1,              -1,             -1,             0,              -1,             -1,     },
255
256                /* I128 */  { -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             2,              3,              4,              3,              4,              5,              -1,             -1,             -1,             0,              1,      },
257                /* U128 */  { -1,       -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             -1,             1,              2,              3,              2,              3,              4,              -1,             -1,             -1,             -1,             0,      },
258        };
259
260        void ConversionCost::postvisit( VoidType * ) {
261                cost = Cost::infinity;
262        }
263
264        void ConversionCost::postvisit(BasicType *basicType) {
265                if ( BasicType *destAsBasic = dynamic_cast< BasicType* >( dest ) ) {
266                        int tableResult = costMatrix[ basicType->get_kind() ][ destAsBasic->get_kind() ];
267                        if ( tableResult == -1 ) {
268                                cost = Cost::unsafe;
269                        } else {
270                                cost = Cost::zero;
271                                cost.incSafe( tableResult );
272                        } // if
273                } else if ( dynamic_cast< EnumInstType *>( dest ) ) {
274                        // xxx - not positive this is correct, but appears to allow casting int => enum
275                        cost = Cost::unsafe;
276                } // if
277                // no cases for zero_t/one_t because it should not be possible to convert int, etc. to zero_t/one_t.
278        }
279
280        void ConversionCost::postvisit( PointerType * pointerType ) {
281                if ( PointerType *destAsPtr = dynamic_cast< PointerType* >( dest ) ) {
282                        PRINT( std::cerr << pointerType << " ===> " << destAsPtr << std::endl; )
283                        Type::Qualifiers tq1 = pointerType->base->get_qualifiers();
284                        Type::Qualifiers tq2 = destAsPtr->base->get_qualifiers();
285                        if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers( pointerType->base, destAsPtr->base, indexer, env ) ) {
286                                PRINT( std::cerr << " :: compatible and good qualifiers" << std::endl; )
287                                if ( tq1 == tq2 ) {
288                                        // types are the same
289                                        cost = Cost::zero;
290                                } else {
291                                        // types are the same, except otherPointer has more qualifiers
292                                        cost = Cost::safe;
293                                }
294                        } else {
295                                int assignResult = ptrsAssignable( pointerType->base, destAsPtr->base, env );
296                                PRINT( std::cerr << " :: " << assignResult << std::endl; )
297                                if ( assignResult > 0 && tq1 <= tq2 ) {
298                                        // xxx - want the case where qualifiers are added to be more expensive than the case where qualifiers are the same. Is 1 safe vs. 2 safe correct?
299                                        if ( tq1 == tq2 ) {
300                                                cost = Cost::safe;
301                                        } else if ( tq1 < tq2 ) {
302                                                cost = Cost::safe+Cost::safe;
303                                        }
304                                } else if ( assignResult < 0 ) {
305                                        cost = Cost::unsafe;
306                                } // if
307                                // assignResult == 0 means Cost::Infinity
308                        } // if
309                        // case case for zero_t because it should not be possible to convert pointers to zero_t.
310                } // if
311        }
312
313        void ConversionCost::postvisit( ArrayType * ) {}
314
315        void ConversionCost::postvisit( ReferenceType * refType ) {
316                // Note: dest can never be a reference, since it would have been caught in an earlier check
317                assert( ! dynamic_cast< ReferenceType * >( dest ) );
318                // convert reference to rvalue: cv T1 & => T2
319                // recursively compute conversion cost from T1 to T2.
320                // cv can be safely dropped because of 'implicit dereference' behavior.
321                cost = costFunc( refType->base, dest, indexer, env );
322                if ( refType->base->get_qualifiers() == dest->get_qualifiers() ) {
323                        cost.incReference();  // prefer exact qualifiers
324                } else if ( refType->base->get_qualifiers() < dest->get_qualifiers() ) {
325                        cost.incSafe(); // then gaining qualifiers
326                } else {
327                        cost.incUnsafe(); // lose qualifiers as last resort
328                }
329                PRINT( std::cerr << refType << " ==> " << dest << " " << cost << std::endl; )
330        }
331
332        void ConversionCost::postvisit( FunctionType * ) {}
333
334        void ConversionCost::postvisit( StructInstType * inst ) {
335                if ( StructInstType *destAsInst = dynamic_cast< StructInstType* >( dest ) ) {
336                        if ( inst->name == destAsInst->name ) {
337                                cost = Cost::zero;
338                        } // if
339                } // if
340        }
341
342        void ConversionCost::postvisit( UnionInstType * inst ) {
343                if ( UnionInstType *destAsInst = dynamic_cast< UnionInstType* >( dest ) ) {
344                        if ( inst->name == destAsInst->name ) {
345                                cost = Cost::zero;
346                        } // if
347                } // if
348        }
349
350        void ConversionCost::postvisit( EnumInstType * ) {
351                static Type::Qualifiers q;
352                static BasicType* integer = new_static_root<BasicType>( q, BasicType::SignedInt );
353                cost = costFunc( integer, dest, indexer, env );  // safe if dest >= int
354                if ( cost < Cost::unsafe ) {
355                        cost.incSafe();
356                } // if
357        }
358
359        void ConversionCost::postvisit( TraitInstType * ) {}
360
361        void ConversionCost::postvisit( TypeInstType *inst ) {
362                if ( const EqvClass *eqvClass = env.lookup( inst->name ) ) {
363                        cost = costFunc( eqvClass->type, dest, indexer, env );
364                } else if ( TypeInstType *destAsInst = dynamic_cast< TypeInstType* >( dest ) ) {
365                        if ( inst->name == destAsInst->name ) {
366                                cost = Cost::zero;
367                        }
368                } else if ( NamedTypeDecl *namedType = indexer.lookupType( inst->name ) ) {
369                        TypeDecl *type = dynamic_cast< TypeDecl* >( namedType );
370                        // all typedefs should be gone by this point
371                        assert( type );
372                        if ( type->base ) {
373                                cost = costFunc( type->base, dest, indexer, env ) + Cost::safe;
374                        } // if
375                } // if
376        }
377
378        void ConversionCost::postvisit( TupleType * tupleType ) {
379                Cost c = Cost::zero;
380                if ( TupleType * destAsTuple = dynamic_cast< TupleType * >( dest ) ) {
381                        std::list< Type * >::const_iterator srcIt = tupleType->types.begin();
382                        std::list< Type * >::const_iterator destIt = destAsTuple->types.begin();
383                        while ( srcIt != tupleType->types.end() && destIt != destAsTuple->types.end() ) {
384                                Cost newCost = costFunc( *srcIt++, *destIt++, indexer, env );
385                                if ( newCost == Cost::infinity ) {
386                                        return;
387                                } // if
388                                c += newCost;
389                        } // while
390                        if ( destIt != destAsTuple->types.end() ) {
391                                cost = Cost::infinity;
392                        } else {
393                                cost = c;
394                        } // if
395                } // if
396        }
397
398        void ConversionCost::postvisit( VarArgsType * ) {
399                if ( dynamic_cast< VarArgsType* >( dest ) ) {
400                        cost = Cost::zero;
401                }
402        }
403
404        void ConversionCost::postvisit( ZeroType * ) {
405                if ( dynamic_cast< ZeroType * >( dest ) ) {
406                        cost = Cost::zero;
407                } else if ( BasicType *destAsBasic = dynamic_cast< BasicType* >( dest ) ) {
408                        // copied from visit(BasicType*) for signed int, but +1 for safe conversions
409                        int tableResult = costMatrix[ BasicType::SignedInt ][ destAsBasic->get_kind() ];
410                        if ( tableResult == -1 ) {
411                                cost = Cost::unsafe;
412                        } else {
413                                cost = Cost::zero;
414                                cost.incSafe( tableResult + 1 );
415                        }
416                } else if ( dynamic_cast< PointerType* >( dest ) ) {
417                        cost = Cost::safe;
418                }
419        }
420
421        void ConversionCost::postvisit( OneType * ) {
422                if ( dynamic_cast< OneType * >( dest ) ) {
423                        cost = Cost::zero;
424                } else if ( BasicType *destAsBasic = dynamic_cast< BasicType* >( dest ) ) {
425                        // copied from visit(BasicType*) for signed int, but +1 for safe conversions
426                        int tableResult = costMatrix[ BasicType::SignedInt ][ destAsBasic->get_kind() ];
427                        if ( tableResult == -1 ) {
428                                cost = Cost::unsafe;
429                        } else {
430                                cost = Cost::zero;
431                                cost.incSafe( tableResult + 1 );
432                        }
433                }
434        }
435} // namespace ResolvExpr
436
437// Local Variables: //
438// tab-width: 4 //
439// mode: c++ //
440// compile-command: "make install" //
441// End: //
Note: See TracBrowser for help on using the repository browser.