Mercurial Mercurial > matiec / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
stage3/constant_folding.cc
changeset 785 b08167f156a1
parent 783 3bd2704d9ba9
child 786 c370918ca7fb
child 787 6e2671e0f1a8
equal deleted inserted replaced
779:2ed03e0e0e41 785:b08167f156a1 
   115  *
 
   115  *
 
   116  *
 
   116  *
 
   117  * NOTE 2 
   117  * NOTE 2 
   118  *    This file does not print out any error messages!
 
   118  *    This file does not print out any error messages!
 
   119  *    We cannot really print out error messages when we find an overflow. Since each operation
 
   119  *    We cannot really print out error messages when we find an overflow. Since each operation
 
   120  *    (symbol in the absract syntax tree for that operation) will have up to 4 constant results,
 
   120  *    (symbol in the abstract syntax tree for that operation) will have up to 4 constant results,
 
   121  *    it may happen that some of them overflow, while other do not.
 
   121  *    it may happen that some of them overflow, while other do not.
 
   122  *    We must wait for data type checking to determine the exact data type of each expression
 
   122  *    We must wait for data type checking to determine the exact data type of each expression
 
   123  *    before we can decide whether or not we should print out an overflow error message.
 
   123  *    before we can decide whether or not we should print out an overflow error message.
 
   124  *
 
   124  *
 
   125  *    For this reason, this visitor merely annotates the abstract syntax tree, and leaves the
 
   125  *    For this reason, this visitor merely annotates the abstract syntax tree, and leaves the
 
   126  *    actuall printing of errors for the print_datatype_errors_c class!
 
   126  *    actually printing of errors for the print_datatype_errors_c class!
 
       
   127  *
 
       
   128  * NOTE 3
 
       
   129  *    Constant Folding class is extended with a implementation constant propagation algorithm
 
       
   130  *    by Mario de Sousa.
 
       
   131  *    Main idea is not to implement a general constant propagation algorithm but to reinterpret it
 
       
   132  *    for visitor classes.
 
       
   133  *    We declared a hash map, it contains a variables list linked with current constant values.
 
       
   134  *    During expression evaluation we can retrieve a constant value to symbolic variables getting it from the map.
 
       
   135  *    Also at join source points we use a meet semilattice rules to merge current values between a block
 
       
   136  *    and adjacent block.
 
       
   137  *
 
   127  */
 
   138  */
 
   128 
   139 
   129 #include "constant_folding.hh"
 
   140 #include "constant_folding.hh"
 
   130 #include <stdlib.h> /* required for malloc() */
 
   141 #include <stdlib.h> /* required for malloc() */
 
   131 
   142 
   939 /* B 1.4 - Variables */
 
   950 /* B 1.4 - Variables */
 
   940 /*********************/
 
   951 /*********************/
 
   941 void *constant_folding_c::visit(symbolic_variable_c *symbol) {
 
   952 void *constant_folding_c::visit(symbolic_variable_c *symbol) {
 
   942 	std::string varName;
 
   953 	std::string varName;
 
   943 
   954 
   944 	varName = convert.toString(symbol->var_name);
 
   955 	varName = get_var_name_c::get_name(symbol->var_name)->value;
 
   945 	if (values.count(varName) > 0) {
 
   956 	if (values.count(varName) > 0) {
 
   946 		symbol->const_value = values[varName];
 
   957 		symbol->const_value = values[varName];
 
   947 	}
 
   958 	}
 
   948 	return NULL;
 
   959 	return NULL;
 
   949 }
 
   960 }
 
   956 
   967 
   957 	values.clear(); /* Clear global map */
 
   968 	values.clear(); /* Clear global map */
 
   958 	search_var_instance_decl_c search_var_instance_decl(symbol);
 
   969 	search_var_instance_decl_c search_var_instance_decl(symbol);
 
   959 	function_param_iterator_c fpi(symbol);
 
   970 	function_param_iterator_c fpi(symbol);
 
   960 	while((var_name = fpi.next()) != NULL) {
 
   971 	while((var_name = fpi.next()) != NULL) {
 
   961 		std::string varName = convert.toString(var_name);
 
   972 		std::string varName = get_var_name_c::get_name(var_name)->value;
 
   962 		symbol_c   *varDecl = search_var_instance_decl.get_decl(var_name);
 
   973 		symbol_c   *varDecl = search_var_instance_decl.get_decl(var_name);
 
   963 		values[varName] = varDecl->const_value;
 
   974 		values[varName] = varDecl->const_value;
 
   964 	}
 
   975 	}
 
   965 	/* Add all variables declared into Values map and put them to initial value */
 
   976 	/* Add all variables declared into Values map and put them to initial value */
 
   966 	symbol->function_block_body->accept(*this);
 
   977 	symbol->function_block_body->accept(*this);
 
  1245 void *constant_folding_c::visit(assignment_statement_c *symbol) {
 
  1256 void *constant_folding_c::visit(assignment_statement_c *symbol) {
 
  1246 	std::string varName;
 
  1257 	std::string varName;
 
  1247 
  1258 
  1248 	symbol->r_exp->accept(*this);
 
  1259 	symbol->r_exp->accept(*this);
 
  1249 	symbol->l_exp->const_value = symbol->r_exp->const_value;
 
  1260 	symbol->l_exp->const_value = symbol->r_exp->const_value;
 
  1250 	varName = convert.toString(symbol->l_exp);
 
  1261 	varName = get_var_name_c::get_name(symbol->l_exp)->value;
 
  1251 	values[varName] = symbol->l_exp->const_value;
 
  1262 	values[varName] = symbol->l_exp->const_value;
 
       
  1263 
  1252 	return NULL;
 
  1264 	return NULL;
 
  1253 }
 
  1265 }
 
  1254 
  1266 
  1255 /********************************/
 
  1267 /********************************/
 
  1256 /* B 3.2.3 Selection Statements */
 
  1268 /* B 3.2.3 Selection Statements */
 
  1258 void *constant_folding_c::visit(if_statement_c *symbol) {
 
  1270 void *constant_folding_c::visit(if_statement_c *symbol) {
 
  1259 	std::map <std::string, symbol_c::const_value_t> values_incoming;
 
  1271 	std::map <std::string, symbol_c::const_value_t> values_incoming;
 
  1260 	std::map <std::string, symbol_c::const_value_t> values_statement_result;
 
  1272 	std::map <std::string, symbol_c::const_value_t> values_statement_result;
 
  1261 	std::map <std::string, symbol_c::const_value_t> values_elsestatement_result;
 
  1273 	std::map <std::string, symbol_c::const_value_t> values_elsestatement_result;
 
  1262 	std::map <std::string, symbol_c::const_value_t>::iterator itr;
 
  1274 	std::map <std::string, symbol_c::const_value_t>::iterator itr;
 
       
  1275 
       
  1276 	/* Optimize dead code */
 
       
  1277 	symbol->expression->accept(*this);
 
       
  1278 	if (VALID_CVALUE(bool, symbol->expression) && GET_CVALUE(bool, symbol->expression) == false)
 
       
  1279 		return NULL;
 
       
  1280 
  1263 	values_incoming = values; /* save incoming status */
 
  1281 	values_incoming = values; /* save incoming status */
 
  1264 
       
  1265 	symbol->statement_list->accept(*this);
 
  1282 	symbol->statement_list->accept(*this);
 
  1266 	values_statement_result = values;
 
  1283 	values_statement_result = values;
 
  1267 	if (NULL != symbol->else_statement_list) {
 
  1284 	if (NULL != symbol->else_statement_list) {
 
  1268 		values = values_incoming;
 
  1285 		values = values_incoming;
 
  1269 		symbol->else_statement_list->accept(*this);
 
  1286 		symbol->else_statement_list->accept(*this);
 
  1285 			COMPUTE_MEET_SEMILATTICE (  bool, c1, c2, value);
 
  1302 			COMPUTE_MEET_SEMILATTICE (  bool, c1, c2, value);
 
  1286 		} else
 
  1303 		} else
 
  1287 			value = values_statement_result[name];
 
  1304 			value = values_statement_result[name];
 
  1288 		values[name] = value;
 
  1305 		values[name] = value;
 
  1289 	}
 
  1306 	}
 
  1290 	return NULL;
 
  1307 
  1291 }
 
  1308 	return NULL;
 
  1292 
  1309 }
 
  1293 
  1310 
  1294 
  1311 /********************************/
 
       
  1312 /* B 3.2.4 Iteration Statements */
 
       
  1313 /********************************/
 
       
  1314 void *constant_folding_c::visit(for_statement_c *symbol) {
 
       
  1315 	std::map <std::string, symbol_c::const_value_t> values_incoming;
 
       
  1316 	std::map <std::string, symbol_c::const_value_t> values_statement_result;
 
       
  1317 	std::map <std::string, symbol_c::const_value_t>::iterator itr;
 
       
  1318 	std::string varName;
 
       
  1319 
       
  1320 	values_incoming = values; /* save incoming status */
 
       
  1321 	symbol->beg_expression->accept(*this);
 
       
  1322 	symbol->end_expression->accept(*this);
 
       
  1323 	varName =  get_var_name_c::get_name(symbol->control_variable)->value;
 
       
  1324 	values[varName] = symbol->beg_expression->const_value;
 
       
  1325 
       
  1326 	/* Optimize dead code */
 
       
  1327 	if (VALID_CVALUE(int64, symbol->beg_expression) && VALID_CVALUE(int64, symbol->end_expression) &&
 
       
  1328 		  GET_CVALUE(int64, symbol->beg_expression) >    GET_CVALUE(int64, symbol->end_expression))
 
       
  1329 		return NULL;
 
       
  1330 
       
  1331 	symbol->statement_list->accept(*this);
 
       
  1332 	values_statement_result = values;
 
       
  1333 	values.clear();
 
       
  1334 	itr = values_statement_result.begin();
 
       
  1335 	for ( ; itr != values_statement_result.end(); ++itr) {
 
       
  1336 		std::string name = itr->first;
 
       
  1337 		symbol_c::const_value_t value;
 
       
  1338 
       
  1339 		if (values_incoming.count(name) > 0) {
 
       
  1340 			symbol_c::const_value_t c1 = itr->second;
 
       
  1341 			symbol_c::const_value_t c2 = values_incoming[name];
 
       
  1342 			COMPUTE_MEET_SEMILATTICE (real64, c1, c2, value);
 
       
  1343 			COMPUTE_MEET_SEMILATTICE (uint64, c1, c2, value);
 
       
  1344 			COMPUTE_MEET_SEMILATTICE ( int64, c1, c2, value);
 
       
  1345 			COMPUTE_MEET_SEMILATTICE (  bool, c1, c2, value);
 
       
  1346 		} else
 
       
  1347 			value = values_statement_result[name];
 
       
  1348 		values[name] = value;
 
       
  1349 	}
 
       
  1350 
       
  1351 	return NULL;
 
       
  1352 }
 
       
  1353 
       
  1354 void *constant_folding_c::visit(while_statement_c *symbol) {
 
       
  1355 	std::map <std::string, symbol_c::const_value_t> values_incoming;
 
       
  1356 	std::map <std::string, symbol_c::const_value_t> values_statement_result;
 
       
  1357 	std::map <std::string, symbol_c::const_value_t>::iterator itr;
 
       
  1358 
       
  1359 	/* Optimize dead code */
 
       
  1360 	symbol->expression->accept(*this);
 
       
  1361 	if (VALID_CVALUE(bool, symbol->expression) && GET_CVALUE(bool, symbol->expression) == false)
 
       
  1362 		return NULL;
 
       
  1363 
       
  1364 	values_incoming = values; /* save incoming status */
 
       
  1365 	symbol->statement_list->accept(*this);
 
       
  1366 	values_statement_result = values;
 
       
  1367 	values.clear();
 
       
  1368 	itr = values_statement_result.begin();
 
       
  1369 	for ( ; itr != values_statement_result.end(); ++itr) {
 
       
  1370 		std::string name = itr->first;
 
       
  1371 		symbol_c::const_value_t value;
 
       
  1372 
       
  1373 		if (values_incoming.count(name) > 0) {
 
       
  1374 			symbol_c::const_value_t c1 = itr->second;
 
       
  1375 			symbol_c::const_value_t c2 = values_incoming[name];
 
       
  1376 			COMPUTE_MEET_SEMILATTICE (real64, c1, c2, value);
 
       
  1377 			COMPUTE_MEET_SEMILATTICE (uint64, c1, c2, value);
 
       
  1378 			COMPUTE_MEET_SEMILATTICE ( int64, c1, c2, value);
 
       
  1379 			COMPUTE_MEET_SEMILATTICE (  bool, c1, c2, value);
 
       
  1380 		} else
 
       
  1381 			value = values_statement_result[name];
 
       
  1382 		values[name] = value;
 
       
  1383 	}
 
       
  1384 
       
  1385 
       
  1386 	return NULL;
 
       
  1387 }
 
       
  1388 
       
  1389 void *constant_folding_c::visit(repeat_statement_c *symbol) {
 
       
  1390 	std::map <std::string, symbol_c::const_value_t> values_incoming;
 
       
  1391 	std::map <std::string, symbol_c::const_value_t> values_statement_result;
 
       
  1392 	std::map <std::string, symbol_c::const_value_t>::iterator itr;
 
       
  1393 
       
  1394 	/* Optimize dead code */
 
       
  1395 	symbol->expression->accept(*this);
 
       
  1396 	if (VALID_CVALUE(bool, symbol->expression) && GET_CVALUE(bool, symbol->expression) == false)
 
       
  1397 		return NULL;
 
       
  1398 
       
  1399 	values_incoming = values; /* save incoming status */
 
       
  1400 	symbol->statement_list->accept(*this);
 
       
  1401 	values_statement_result = values;
 
       
  1402 	values.clear();
 
       
  1403 	itr = values_statement_result.begin();
 
       
  1404 	for ( ; itr != values_statement_result.end(); ++itr) {
 
       
  1405 		std::string name = itr->first;
 
       
  1406 		symbol_c::const_value_t value;
 
       
  1407 
       
  1408 		if (values_incoming.count(name) > 0) {
 
       
  1409 			symbol_c::const_value_t c1 = itr->second;
 
       
  1410 			symbol_c::const_value_t c2 = values_incoming[name];
 
       
  1411 			COMPUTE_MEET_SEMILATTICE (real64, c1, c2, value);
 
       
  1412 			COMPUTE_MEET_SEMILATTICE (uint64, c1, c2, value);
 
       
  1413 			COMPUTE_MEET_SEMILATTICE ( int64, c1, c2, value);
 
       
  1414 			COMPUTE_MEET_SEMILATTICE (  bool, c1, c2, value);
 
       
  1415 		} else
 
       
  1416 			value = values_statement_result[name];
 
       
  1417 		values[name] = value;
 
       
  1418 	}
 
       
  1419 
       
  1420 
       
  1421 	return NULL;
 
       
  1422 }
 
       
  1423 
       
  1424 
       
  1425
matiec