Context Navigation

source: src/ResolvExpr/ConversionCost.cc @ 2f42718

no_list

Last change on this file since 2f42718 was 2f42718, checked in by tdelisle <tdelisle@…>, 5 years ago
Parameters and return value of functions are now vectors (and some related clean-up)
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
29	namespace 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::safe = Cost{ 0, 0, 1, 0, 0, 0 };
35	const Cost Cost::var = Cost{ 0, 0, 0, 1, 0, 0 };
36	const Cost Cost::spec = 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::vector< Type * >::const_iterator srcIt = tupleType->types.begin();
391	std::vector< 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.

Download in other formats: