source: src/ResolvExpr/ConversionCost.cc @ 5af7306

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

Assorted bug fixes

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