source: src/ResolvExpr/ConversionCost.cc @ 982832e

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 982832e was 982832e, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

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