source: src/ResolvExpr/ConversionCost.cc@ 0182bfa

new-env with_gc
Last change on this file since 0182bfa was 8e18b8e, checked in by Aaron Moss <a3moss@…>, 7 years ago

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