source: src/ResolvExpr/ConversionCost.cc@ 83ab931

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr no_list persistent-indexer pthread-emulation qualifiedEnum
Last change on this file since 83ab931 was 1dd1bd2, checked in by Aaron Moss <a3moss@…>, 7 years ago

Add var count and type specialization costs to resolver model
  • Property mode set to 100644
File size: 19.0 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, 0, 0 };
31 const Cost Cost::infinity = Cost{ -1, -1, -1, 1, -1, -1 };
32 const Cost Cost::unsafe = Cost{ 1, 0, 0, 0, 0, 0 };
33 const Cost Cost::poly = Cost{ 0, 1, 0, 0, 0, 0 };
34 const Cost Cost::var = Cost{ 0, 0, 1, 0, 0, 0 };
35 const Cost Cost::spec = Cost{ 0, 0, 0, -1, 0, 0 };
36 const Cost Cost::safe = Cost{ 0, 0, 0, 0, 1, 0 };
37 const Cost Cost::reference = Cost{ 0, 0, 0, 0, 0, 1 };
38
39#if 0
40#define PRINT(x) x
41#else
42#define PRINT(x)
43#endif
44 Cost conversionCost( Type *src, Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {
45 if ( TypeInstType *destAsTypeInst = dynamic_cast< TypeInstType* >( dest ) ) {
46 PRINT( std::cerr << "type inst " << destAsTypeInst->name; )
47 if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->name ) ) {
48 if ( eqvClass->type ) {
49 return conversionCost( src, eqvClass->type, indexer, env );
50 } else {
51 return Cost::infinity;
52 }
53 } else if ( NamedTypeDecl *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 SymTab::Indexer &, const TypeEnvironment & env ){
80 return ptrsAssignable( t1, t2, env );
81 });
82 } else {
83 PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
84 src->accept( converter );
85 if ( converter.pass.get_cost() == Cost::infinity ) {
86 return Cost::infinity;
87 } else {
88 return converter.pass.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, indexer, env );
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 PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
133 src->accept( converter );
134 return converter.pass.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 Cost cost = convertToReferenceCost( src, dest, sdepth-ddepth, indexer, env, func );
173 PRINT( std::cerr << "convertToReferenceCost result: " << cost << std::endl; )
174 return cost;
175 }
176
177 ConversionCost::ConversionCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc )
178 : dest( dest ), indexer( indexer ), cost( Cost::infinity ), env( env ), costFunc( costFunc ) {
179 }
180
181/*
182 Old
183 ===
184 Double
185 |
186 Float
187 |
188 ULong
189 / \
190 UInt Long
191 \ /
192 Int
193 |
194 Ushort
195 |
196 Short
197 |
198 Uchar
199 / \
200 Schar Char
201
202 New
203 ===
204 +-----LongDoubleComplex--+
205 LongDouble--+ | +-LongDoubleImag
206 | +---DoubleComplex---+ |
207 Double------+ | +----DoubleImag
208 | +-FloatComplex-+ |
209 Float---------+ +-------FloatImag
210 |
211 ULongLong
212 |
213 LongLong
214 |
215 ULong
216 / \
217 UInt Long
218 \ /
219 Int
220 |
221 Ushort
222 |
223 Short
224 |
225 Uchar
226 / \
227 Schar Char
228 \ /
229 Bool
230*/
231
232 static const int costMatrix[][ BasicType::NUMBER_OF_BASIC_TYPES ] = {
233 /* 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, F80, F128 */
234 /* Bool */ { 0, 1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 12, 13, 14, 12, 13, 14, -1, -1, -1, 10, 11, 14, 15},
235 /* Char */ { -1, 0, -1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 11, 12, 13, 11, 12, 13, -1, -1, -1, 9, 10, 13, 14},
236 /* SChar */ { -1, -1, 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 11, 12, 13, 11, 12, 13, -1, -1, -1, 9, 10, 13, 14},
237 /* UChar */ { -1, -1, -1, 0, 1, 2, 3, 4, 4, 5, 6, 7, 10, 11, 12, 10, 11, 12, -1, -1, -1, 8, 9, 12, 13},
238 /* Short */ { -1, -1, -1, -1, 0, 1, 2, 3, 3, 4, 5, 6, 9, 10, 11, 9, 10, 11, -1, -1, -1, 7, 8, 11, 12},
239 /* UShort */{ -1, -1, -1, -1, -1, 0, 1, 2, 2, 3, 4, 5, 8, 9, 10, 8, 9, 10, -1, -1, -1, 6, 7, 10, 11},
240 /* Int */ { -1, -1, -1, -1, -1, -1, 0, 1, 1, 2, 3, 4, 7, 8, 9, 7, 8, 9, -1, -1, -1, 5, 6, 9, 10},
241 /* UInt */ { -1, -1, -1, -1, -1, -1, -1, 0, -1, 1, 2, 3, 6, 7, 8, 6, 7, 8, -1, -1, -1, 4, 5, 8, 9},
242 /* Long */ { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 6, 7, 8, 6, 7, 8, -1, -1, -1, 4, 5, 8, 9},
243 /* ULong */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 5, 6, 7, 5, 6, 7, -1, -1, -1, 3, 4, 7, 8},
244 /* LLong */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 4, 5, 6, 4, 5, 6, -1, -1, -1, 2, 3, 6, 7},
245 /* ULLong */{ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 3, 4, 5, 3, 4, 5, -1, -1, -1, 1, 2, 5, 6},
246
247 /* Float */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 1, 2, 3, -1, -1, -1, -1, -1, 2, 3},
248 /* Double */{ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, -1, 1, 2, -1, -1, -1, -1, -1, 1, 2},
249 /* LDbl */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, 1, -1, -1, -1, -1, -1, -1, 1},
250 /* FCplex */{ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, -1, -1, -1, -1, -1, -1, -1},
251 /* DCplex */{ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, -1, -1, -1, -1, -1, -1, -1},
252 /* LDCplex */{ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1},
253 /* FImag */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 3, 0, 1, 2, -1, -1, -1, -1},
254 /* DImag */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, -1, 0, 1, -1, -1, -1, -1},
255 /* LDImag */{ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, 0, -1, -1, -1, -1},
256
257 /* I128 */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 3, 4, 3, 4, 5, -1, -1, -1, 0, 1, 4, 4},
258 /* U128 */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 3, 2, 3, 4, -1, -1, -1, -1, 0, 3, 3},
259
260 /* F80 */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, 1, -1, -1, -1, -1, -1, 0, 1},
261 /* F128 */ { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, 0},
262 };
263 static_assert(
264 sizeof(costMatrix)/sizeof(costMatrix[0][0]) == BasicType::NUMBER_OF_BASIC_TYPES*BasicType::NUMBER_OF_BASIC_TYPES,
265 "Each basic type kind should have a corresponding row in the cost matrix"
266 );
267
268
269 void ConversionCost::postvisit( VoidType * ) {
270 cost = Cost::infinity;
271 }
272
273 void ConversionCost::postvisit(BasicType *basicType) {
274 if ( BasicType *destAsBasic = dynamic_cast< BasicType* >( dest ) ) {
275 int tableResult = costMatrix[ basicType->get_kind() ][ destAsBasic->get_kind() ];
276 if ( tableResult == -1 ) {
277 cost = Cost::unsafe;
278 } else {
279 cost = Cost::zero;
280 cost.incSafe( tableResult );
281 } // if
282 } else if ( dynamic_cast< EnumInstType *>( dest ) ) {
283 // xxx - not positive this is correct, but appears to allow casting int => enum
284 cost = Cost::unsafe;
285 } // if
286 // no cases for zero_t/one_t because it should not be possible to convert int, etc. to zero_t/one_t.
287 }
288
289 void ConversionCost::postvisit( PointerType * pointerType ) {
290 if ( PointerType *destAsPtr = dynamic_cast< PointerType* >( dest ) ) {
291 PRINT( std::cerr << pointerType << " ===> " << destAsPtr << std::endl; )
292 Type::Qualifiers tq1 = pointerType->base->get_qualifiers();
293 Type::Qualifiers tq2 = destAsPtr->base->get_qualifiers();
294 if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers( pointerType->base, destAsPtr->base, indexer, env ) ) {
295 PRINT( std::cerr << " :: compatible and good qualifiers" << std::endl; )
296 if ( tq1 == tq2 ) {
297 // types are the same
298 cost = Cost::zero;
299 } else {
300 // types are the same, except otherPointer has more qualifiers
301 cost = Cost::safe;
302 }
303 } else {
304 int assignResult = ptrsAssignable( pointerType->base, destAsPtr->base, env );
305 PRINT( std::cerr << " :: " << assignResult << std::endl; )
306 if ( assignResult > 0 && tq1 <= tq2 ) {
307 // 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?
308 if ( tq1 == tq2 ) {
309 cost = Cost::safe;
310 } else if ( tq1 < tq2 ) {
311 cost = Cost::safe+Cost::safe;
312 }
313 } else if ( assignResult < 0 ) {
314 cost = Cost::unsafe;
315 } // if
316 // assignResult == 0 means Cost::Infinity
317 } // if
318 // case case for zero_t because it should not be possible to convert pointers to zero_t.
319 } // if
320 }
321
322 void ConversionCost::postvisit( ArrayType * ) {}
323
324 void ConversionCost::postvisit( ReferenceType * refType ) {
325 // Note: dest can never be a reference, since it would have been caught in an earlier check
326 assert( ! dynamic_cast< ReferenceType * >( dest ) );
327 // convert reference to rvalue: cv T1 & => T2
328 // recursively compute conversion cost from T1 to T2.
329 // cv can be safely dropped because of 'implicit dereference' behavior.
330 cost = costFunc( refType->base, dest, indexer, env );
331 if ( refType->base->get_qualifiers() == dest->get_qualifiers() ) {
332 cost.incReference(); // prefer exact qualifiers
333 } else if ( refType->base->get_qualifiers() < dest->get_qualifiers() ) {
334 cost.incSafe(); // then gaining qualifiers
335 } else {
336 cost.incUnsafe(); // lose qualifiers as last resort
337 }
338 PRINT( std::cerr << refType << " ==> " << dest << " " << cost << std::endl; )
339 }
340
341 void ConversionCost::postvisit( FunctionType * ) {}
342
343 void ConversionCost::postvisit( StructInstType * inst ) {
344 if ( StructInstType *destAsInst = dynamic_cast< StructInstType* >( dest ) ) {
345 if ( inst->name == destAsInst->name ) {
346 cost = Cost::zero;
347 } // if
348 } // if
349 }
350
351 void ConversionCost::postvisit( UnionInstType * inst ) {
352 if ( UnionInstType *destAsInst = dynamic_cast< UnionInstType* >( dest ) ) {
353 if ( inst->name == destAsInst->name ) {
354 cost = Cost::zero;
355 } // if
356 } // if
357 }
358
359 void ConversionCost::postvisit( EnumInstType * ) {
360 static Type::Qualifiers q;
361 static BasicType integer( q, BasicType::SignedInt );
362 cost = costFunc( &integer, dest, indexer, env ); // safe if dest >= int
363 if ( cost < Cost::unsafe ) {
364 cost.incSafe();
365 } // if
366 }
367
368 void ConversionCost::postvisit( TraitInstType * ) {}
369
370 void ConversionCost::postvisit( TypeInstType *inst ) {
371 if ( const EqvClass *eqvClass = env.lookup( inst->name ) ) {
372 cost = costFunc( eqvClass->type, dest, indexer, env );
373 } else if ( TypeInstType *destAsInst = dynamic_cast< TypeInstType* >( dest ) ) {
374 if ( inst->name == destAsInst->name ) {
375 cost = Cost::zero;
376 }
377 } else if ( NamedTypeDecl *namedType = indexer.lookupType( inst->name ) ) {
378 TypeDecl *type = dynamic_cast< TypeDecl* >( namedType );
379 // all typedefs should be gone by this point
380 assert( type );
381 if ( type->base ) {
382 cost = costFunc( type->base, dest, indexer, env ) + Cost::safe;
383 } // if
384 } // if
385 }
386
387 void ConversionCost::postvisit( TupleType * tupleType ) {
388 Cost c = Cost::zero;
389 if ( TupleType * destAsTuple = dynamic_cast< TupleType * >( dest ) ) {
390 std::list< Type * >::const_iterator srcIt = tupleType->types.begin();
391 std::list< Type * >::const_iterator destIt = destAsTuple->types.begin();
392 while ( srcIt != tupleType->types.end() && destIt != destAsTuple->types.end() ) {
393 Cost newCost = costFunc( *srcIt++, *destIt++, indexer, env );
394 if ( newCost == Cost::infinity ) {
395 return;
396 } // if
397 c += newCost;
398 } // while
399 if ( destIt != destAsTuple->types.end() ) {
400 cost = Cost::infinity;
401 } else {
402 cost = c;
403 } // if
404 } // if
405 }
406
407 void ConversionCost::postvisit( VarArgsType * ) {
408 if ( dynamic_cast< VarArgsType* >( dest ) ) {
409 cost = Cost::zero;
410 }
411 }
412
413 void ConversionCost::postvisit( ZeroType * ) {
414 if ( dynamic_cast< ZeroType * >( dest ) ) {
415 cost = Cost::zero;
416 } else if ( BasicType *destAsBasic = dynamic_cast< BasicType* >( dest ) ) {
417 // copied from visit(BasicType*) for signed int, but +1 for safe conversions
418 int tableResult = costMatrix[ BasicType::SignedInt ][ destAsBasic->get_kind() ];
419 if ( tableResult == -1 ) {
420 cost = Cost::unsafe;
421 } else {
422 cost = Cost::zero;
423 cost.incSafe( tableResult + 1 );
424 }
425 } else if ( dynamic_cast< PointerType* >( dest ) ) {
426 cost = Cost::safe;
427 }
428 }
429
430 void ConversionCost::postvisit( OneType * ) {
431 if ( dynamic_cast< OneType * >( dest ) ) {
432 cost = Cost::zero;
433 } else if ( BasicType *destAsBasic = dynamic_cast< BasicType* >( dest ) ) {
434 // copied from visit(BasicType*) for signed int, but +1 for safe conversions
435 int tableResult = costMatrix[ BasicType::SignedInt ][ destAsBasic->get_kind() ];
436 if ( tableResult == -1 ) {
437 cost = Cost::unsafe;
438 } else {
439 cost = Cost::zero;
440 cost.incSafe( tableResult + 1 );
441 }
442 }
443 }
444} // namespace ResolvExpr
445
446// Local Variables: //
447// tab-width: 4 //
448// mode: c++ //
449// compile-command: "make install" //
450// End: //
Note: See TracBrowser for help on using the repository browser.