source: src/ResolvExpr/ConversionCost.cc@ 6ccfb7f

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 6ccfb7f was 8135d4c, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

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