Context Navigation

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

ADTarm-ehast-experimentalcleanup-dtorsenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 2bfc6b2 was 00ac42e, checked in by Aaron Moss <a3moss@…>, 6 years ago
stop eagerly copying EqvClass? on lookup
Property mode set to `100644`
File size: 18.8 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 );
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	PRINT( std::cerr << "type inst " << destAsTypeInst->name; )
45	if ( const EqvClass* eqvClass = env.lookup( destAsTypeInst->name ) ) {
46	if ( eqvClass->type ) {
47	return conversionCost( src, eqvClass->type, indexer, env );
48	} else {
49	return Cost::infinity;
50	}
51	} else if ( NamedTypeDecl *namedType = indexer.lookupType( destAsTypeInst->name ) ) {
52	PRINT( std::cerr << " found" << std::endl; )
53	TypeDecl type = dynamic_cast< TypeDecl >( namedType );
54	// all typedefs should be gone by this point
55	assert( type );
56	if ( type->base ) {
57	return conversionCost( src, type->base, indexer, env ) + Cost::safe;
58	} // if
59	} // if
60	PRINT( std::cerr << " not found" << std::endl; )
61	} // if
62	PRINT(
63	std::cerr << "src is ";
64	src->print( std::cerr );
65	std::cerr << std::endl << "dest is ";
66	dest->print( std::cerr );
67	std::cerr << std::endl << "env is" << std::endl;
68	env.print( std::cerr, 8 );
69	)
70	if ( typesCompatibleIgnoreQualifiers( src, dest, indexer, env ) ) {
71	PRINT( std::cerr << "compatible!" << std::endl; )
72	return Cost::zero;
73	} else if ( dynamic_cast< VoidType* >( dest ) ) {
74	return Cost::safe;
75	} else if ( ReferenceType * refType = dynamic_cast< ReferenceType * > ( dest ) ) {
76	PRINT( std::cerr << "conversionCost: dest is reference" << std::endl; )
77	return convertToReferenceCost( src, refType, indexer, env, [](Type * t1, Type * t2, const SymTab::Indexer &, const TypeEnvironment & env ){
78	return ptrsAssignable( t1, t2, env );
79	});
80	} else {
81	PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
82	src->accept( converter );
83	if ( converter.pass.get_cost() == Cost::infinity ) {
84	return Cost::infinity;
85	} else {
86	return converter.pass.get_cost() + Cost::zero;
87	} // if
88	} // if
89	}
90
91	Cost convertToReferenceCost( Type * src, Type * dest, int diff, const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func ) {
92	PRINT( std::cerr << "convert to reference cost... diff " << diff << " " << src << " / " << dest << std::endl; )
93	if ( diff > 0 ) {
94	// TODO: document this
95	Cost cost = convertToReferenceCost( strict_dynamic_cast< ReferenceType * >( src )->base, dest, diff-1, indexer, env, func );
96	cost.incReference();
97	return cost;
98	} else if ( diff < -1 ) {
99	// TODO: document this
100	Cost cost = convertToReferenceCost( src, strict_dynamic_cast< ReferenceType * >( dest )->base, diff+1, indexer, env, func );
101	cost.incReference();
102	return cost;
103	} else if ( diff == 0 ) {
104	ReferenceType * srcAsRef = dynamic_cast< ReferenceType * >( src );
105	ReferenceType * destAsRef = dynamic_cast< ReferenceType * >( dest );
106	if ( srcAsRef && destAsRef ) { // pointer-like conversions between references
107	PRINT( std::cerr << "converting between references" << std::endl; )
108	Type::Qualifiers tq1 = srcAsRef->base->get_qualifiers();
109	Type::Qualifiers tq2 = destAsRef->base->get_qualifiers();
110	if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers( srcAsRef->base, destAsRef->base, indexer, env ) ) {
111	PRINT( std::cerr << " :: compatible and good qualifiers" << std::endl; )
112	if ( tq1 == tq2 ) {
113	// types are the same
114	return Cost::zero;
115	} else {
116	// types are the same, except otherPointer has more qualifiers
117	return Cost::safe;
118	}
119	} else { // xxx - this discards reference qualifiers from consideration -- reducing qualifiers is a safe conversion; is this right?
120	int assignResult = func( srcAsRef->base, destAsRef->base, indexer, env );
121	PRINT( std::cerr << "comparing references: " << assignResult << " " << srcAsRef << " " << destAsRef << std::endl; )
122	if ( assignResult > 0 ) {
123	return Cost::safe;
124	} else if ( assignResult < 0 ) {
125	return Cost::unsafe;
126	} // if
127	} // if
128	} else {
129	PRINT( std::cerr << "reference to rvalue conversion" << std::endl; )
130	PassVisitor<ConversionCost> converter( dest, indexer, env, conversionCost );
131	src->accept( converter );
132	return converter.pass.get_cost();
133	} // if
134	} else {
135	ReferenceType * destAsRef = dynamic_cast< ReferenceType * >( dest );
136	assert( diff == -1 && destAsRef );
137	PRINT( std::cerr << "dest is: " << dest << " / src is: " << src << std::endl; )
138	if ( typesCompatibleIgnoreQualifiers( src, destAsRef->base, indexer, env ) ) {
139	PRINT( std::cerr << "converting compatible base type" << std::endl; )
140	if ( src->get_lvalue() ) {
141	PRINT(
142	std::cerr << "lvalue to reference conversion" << std::endl;
143	std::cerr << src << " => " << destAsRef << std::endl;
144	)
145	// lvalue-to-reference conversion: cv lvalue T => cv T &
146	if ( src->get_qualifiers() == destAsRef->base->get_qualifiers() ) {
147	return Cost::reference; // cost needs to be non-zero to add cast
148	} if ( src->get_qualifiers() < destAsRef->base->get_qualifiers() ) {
149	return Cost::safe; // cost needs to be higher than previous cast to differentiate adding qualifiers vs. keeping same
150	} else {
151	return Cost::unsafe;
152	} // if
153	} else if ( destAsRef->base->get_const() ) {
154	PRINT( std::cerr << "rvalue to const ref conversion" << std::endl; )
155	// rvalue-to-const-reference conversion: T => const T &
156	return Cost::safe;
157	} else {
158	PRINT( std::cerr << "rvalue to non-const reference conversion" << std::endl; )
159	// rvalue-to-reference conversion: T => T &
160	return Cost::unsafe;
161	} // if
162	} // if
163	PRINT( std::cerr << "attempting to convert from incompatible base type -- fail" << std::endl; )
164	}
165	return Cost::infinity;
166	}
167
168	Cost convertToReferenceCost( Type * src, ReferenceType * dest, const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func ) {
169	int sdepth = src->referenceDepth(), ddepth = dest->referenceDepth();
170	Cost cost = convertToReferenceCost( src, dest, sdepth-ddepth, indexer, env, func );
171	PRINT( std::cerr << "convertToReferenceCost result: " << cost << std::endl; )
172	return cost;
173	}
174
175	ConversionCost::ConversionCost( Type *dest, const SymTab::Indexer &indexer, const TypeEnvironment &env, CostFunction costFunc )
176	: dest( dest ), indexer( indexer ), cost( Cost::infinity ), env( env ), costFunc( costFunc ) {
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 ] = {
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, F80, F128 */
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, 14, 15},
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, 13, 14},
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, 13, 14},
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, 12, 13},
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, 11, 12},
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, 10, 11},
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, 9, 10},
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, 8, 9},
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, 8, 9},
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, 7, 8},
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, 6, 7},
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, 5, 6},
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, 2, 3},
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, 1, 2},
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, -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, -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, -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, -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, -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, -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, -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, 4, 4},
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, 3, 3},
257
258	/* 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},
259	/* 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},
260	};
261	static_assert(
262	sizeof(costMatrix)/sizeof(costMatrix[0][0]) == BasicType::NUMBER_OF_BASIC_TYPES*BasicType::NUMBER_OF_BASIC_TYPES,
263	"Each basic type kind should have a corresponding row in the cost matrix"
264	);
265
266
267	void ConversionCost::postvisit( VoidType * ) {
268	cost = Cost::infinity;
269	}
270
271	void ConversionCost::postvisit(BasicType *basicType) {
272	if ( BasicType destAsBasic = dynamic_cast< BasicType >( dest ) ) {
273	int tableResult = costMatrix[ basicType->get_kind() ][ destAsBasic->get_kind() ];
274	if ( tableResult == -1 ) {
275	cost = Cost::unsafe;
276	} else {
277	cost = Cost::zero;
278	cost.incSafe( tableResult );
279	} // if
280	} else if ( dynamic_cast< EnumInstType *>( dest ) ) {
281	// xxx - not positive this is correct, but appears to allow casting int => enum
282	cost = Cost::unsafe;
283	} // if
284	// no cases for zero_t/one_t because it should not be possible to convert int, etc. to zero_t/one_t.
285	}
286
287	void ConversionCost::postvisit( PointerType * pointerType ) {
288	if ( PointerType destAsPtr = dynamic_cast< PointerType >( dest ) ) {
289	PRINT( std::cerr << pointerType << " ===> " << destAsPtr << std::endl; )
290	Type::Qualifiers tq1 = pointerType->base->get_qualifiers();
291	Type::Qualifiers tq2 = destAsPtr->base->get_qualifiers();
292	if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers( pointerType->base, destAsPtr->base, indexer, env ) ) {
293	PRINT( std::cerr << " :: compatible and good qualifiers" << std::endl; )
294	if ( tq1 == tq2 ) {
295	// types are the same
296	cost = Cost::zero;
297	} else {
298	// types are the same, except otherPointer has more qualifiers
299	cost = Cost::safe;
300	}
301	} else {
302	int assignResult = ptrsAssignable( pointerType->base, destAsPtr->base, env );
303	PRINT( std::cerr << " :: " << assignResult << std::endl; )
304	if ( assignResult > 0 && tq1 <= tq2 ) {
305	// 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?
306	if ( tq1 == tq2 ) {
307	cost = Cost::safe;
308	} else if ( tq1 < tq2 ) {
309	cost = Cost::safe+Cost::safe;
310	}
311	} else if ( assignResult < 0 ) {
312	cost = Cost::unsafe;
313	} // if
314	// assignResult == 0 means Cost::Infinity
315	} // if
316	// case case for zero_t because it should not be possible to convert pointers to zero_t.
317	} // if
318	}
319
320	void ConversionCost::postvisit( ArrayType * ) {}
321
322	void ConversionCost::postvisit( ReferenceType * refType ) {
323	// Note: dest can never be a reference, since it would have been caught in an earlier check
324	assert( ! dynamic_cast< ReferenceType * >( dest ) );
325	// convert reference to rvalue: cv T1 & => T2
326	// recursively compute conversion cost from T1 to T2.
327	// cv can be safely dropped because of 'implicit dereference' behavior.
328	cost = costFunc( refType->base, dest, indexer, env );
329	if ( refType->base->get_qualifiers() == dest->get_qualifiers() ) {
330	cost.incReference(); // prefer exact qualifiers
331	} else if ( refType->base->get_qualifiers() < dest->get_qualifiers() ) {
332	cost.incSafe(); // then gaining qualifiers
333	} else {
334	cost.incUnsafe(); // lose qualifiers as last resort
335	}
336	PRINT( std::cerr << refType << " ==> " << dest << " " << cost << std::endl; )
337	}
338
339	void ConversionCost::postvisit( FunctionType * ) {}
340
341	void ConversionCost::postvisit( StructInstType * inst ) {
342	if ( StructInstType destAsInst = dynamic_cast< StructInstType >( dest ) ) {
343	if ( inst->name == destAsInst->name ) {
344	cost = Cost::zero;
345	} // if
346	} // if
347	}
348
349	void ConversionCost::postvisit( UnionInstType * inst ) {
350	if ( UnionInstType destAsInst = dynamic_cast< UnionInstType >( dest ) ) {
351	if ( inst->name == destAsInst->name ) {
352	cost = Cost::zero;
353	} // if
354	} // if
355	}
356
357	void ConversionCost::postvisit( EnumInstType * ) {
358	static Type::Qualifiers q;
359	static BasicType integer( q, BasicType::SignedInt );
360	cost = costFunc( &integer, dest, indexer, env ); // safe if dest >= int
361	if ( cost < Cost::unsafe ) {
362	cost.incSafe();
363	} // if
364	}
365
366	void ConversionCost::postvisit( TraitInstType * ) {}
367
368	void ConversionCost::postvisit( TypeInstType *inst ) {
369	if ( const EqvClass *eqvClass = env.lookup( inst->name ) ) {
370	cost = costFunc( eqvClass->type, dest, indexer, env );
371	} else if ( TypeInstType destAsInst = dynamic_cast< TypeInstType >( dest ) ) {
372	if ( inst->name == destAsInst->name ) {
373	cost = Cost::zero;
374	}
375	} else if ( NamedTypeDecl *namedType = indexer.lookupType( inst->name ) ) {
376	TypeDecl type = dynamic_cast< TypeDecl >( namedType );
377	// all typedefs should be gone by this point
378	assert( type );
379	if ( type->base ) {
380	cost = costFunc( type->base, dest, indexer, env ) + Cost::safe;
381	} // if
382	} // if
383	}
384
385	void ConversionCost::postvisit( TupleType * tupleType ) {
386	Cost c = Cost::zero;
387	if ( TupleType * destAsTuple = dynamic_cast< TupleType * >( dest ) ) {
388	std::list< Type * >::const_iterator srcIt = tupleType->types.begin();
389	std::list< Type * >::const_iterator destIt = destAsTuple->types.begin();
390	while ( srcIt != tupleType->types.end() && destIt != destAsTuple->types.end() ) {
391	Cost newCost = costFunc( srcIt++, destIt++, indexer, env );
392	if ( newCost == Cost::infinity ) {
393	return;
394	} // if
395	c += newCost;
396	} // while
397	if ( destIt != destAsTuple->types.end() ) {
398	cost = Cost::infinity;
399	} else {
400	cost = c;
401	} // if
402	} // if
403	}
404
405	void ConversionCost::postvisit( VarArgsType * ) {
406	if ( dynamic_cast< VarArgsType* >( dest ) ) {
407	cost = Cost::zero;
408	}
409	}
410
411	void ConversionCost::postvisit( ZeroType * ) {
412	if ( dynamic_cast< ZeroType * >( dest ) ) {
413	cost = Cost::zero;
414	} else if ( BasicType destAsBasic = dynamic_cast< BasicType >( dest ) ) {
415	// copied from visit(BasicType*) for signed int, but +1 for safe conversions
416	int tableResult = costMatrix[ BasicType::SignedInt ][ destAsBasic->get_kind() ];
417	if ( tableResult == -1 ) {
418	cost = Cost::unsafe;
419	} else {
420	cost = Cost::zero;
421	cost.incSafe( tableResult + 1 );
422	}
423	} else if ( dynamic_cast< PointerType* >( dest ) ) {
424	cost = Cost::safe;
425	}
426	}
427
428	void ConversionCost::postvisit( OneType * ) {
429	if ( dynamic_cast< OneType * >( dest ) ) {
430	cost = Cost::zero;
431	} else if ( BasicType destAsBasic = dynamic_cast< BasicType >( dest ) ) {
432	// copied from visit(BasicType*) for signed int, but +1 for safe conversions
433	int tableResult = costMatrix[ BasicType::SignedInt ][ destAsBasic->get_kind() ];
434	if ( tableResult == -1 ) {
435	cost = Cost::unsafe;
436	} else {
437	cost = Cost::zero;
438	cost.incSafe( tableResult + 1 );
439	}
440	}
441	}
442	} // namespace ResolvExpr
443
444	// Local Variables: //
445	// tab-width: 4 //
446	// mode: c++ //
447	// compile-command: "make install" //
448	// End: //

Note: See TracBrowser for help on using the repository browser.

Download in other formats: