source: src/ResolvExpr/ConversionCost.cc @ eb0aedb

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since eb0aedb was eb0aedb, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

Minor code cleanup

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