msousa@443: /*
msousa@443:  *  matiec - a compiler for the programming languages defined in IEC 61131-3
msousa@443:  *
msousa@443:  *  Copyright (C) 2012  Mario de Sousa (msousa@fe.up.pt)
msousa@443:  *
msousa@443:  *  This program is free software: you can redistribute it and/or modify
msousa@443:  *  it under the terms of the GNU General Public License as published by
msousa@443:  *  the Free Software Foundation, either version 3 of the License, or
msousa@443:  *  (at your option) any later version.
msousa@443:  *
msousa@443:  *  This program is distributed in the hope that it will be useful,
msousa@443:  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
msousa@443:  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
msousa@443:  *  GNU General Public License for more details.
msousa@443:  *
msousa@443:  *  You should have received a copy of the GNU General Public License
msousa@443:  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
msousa@443:  *
msousa@443:  *
msousa@443:  * This code is made available on the understanding that it will not be
msousa@443:  * used in safety-critical situations without a full and competent review.
msousa@443:  */
msousa@443: 
msousa@443: /*
msousa@443:  * An IEC 61131-3 compiler.
msousa@443:  *
msousa@443:  * Based on the
msousa@443:  * FINAL DRAFT - IEC 61131-3, 2nd Ed. (2001-12-10)
msousa@443:  *
msousa@443:  */
msousa@443: 
msousa@443: 
msousa@443: /*
msousa@443:  *  Do flow control analysis of the IEC 61131-3 code.
msousa@443:  *
msousa@443:  *  We currently only do this for IL code.
msousa@443:  *  This class will annotate the abstract syntax tree, by filling in the
msousa@443:  *  prev_il_instruction variable in the il_instruction_c, so it points to
msousa@443:  *  the previous il_instruction_c object in the instruction list instruction_list_c.
msousa@453:  *
msousa@486:  *  Since IL code can contain jumps (JMP), the same il_instruction may effectively have
msousa@486:  *  several previous il_instructions. In order to accommodate this, each il_instruction
msousa@486:  *  will maintain a vector (i..e an array) of pointers to all the previous il_instructions.
msousa@486:  *  We do however attempt to guarantee that the first element in the vector (array) will preferentially
msousa@486:  *  point to the il instruction that is right before / imediately preceding the current il instructions, 
msousa@486:  *  i.e. the first element in the array will tend to point to the previous il_instruction
msousa@486:  *  that is not a jump JMP IL instruction!
msousa@486:  *
msousa@486:  *  The result will essentially be a graph of il_instruction_c objects, each 
msousa@453:  *  pointing to the previous il_instruction_c object.
msousa@453:  *
msousa@453:  *  The reality is we will get several independent and isolated linked lists
msousa@486:  *  (actually, since we now process labels correctly, this is really a graph):
msousa@453:  *  one for each block of IL code (e.g. inside a Function, FB or Program).
msousa@453:  *  Additionally, when the IL code has an expression (expression_c object), we will actually
msousa@453:  *  have one more isolated linked list for the IL code inside that expression.
msousa@453:  *
msousa@453:  *  e.g.
msousa@453:  *       line_1:   LD 1
msousa@453:  *       line_2:   ADD (42
msousa@453:  *       line_3:        ADD B
msousa@453:  *       line_4:        ADD C 
msousa@453:  *       line_5:       )
msousa@453:  *       line_6:   ADD D
msousa@453:  *       line_7:   ST  E
msousa@453:  * 
msousa@453:  *     will result in two independent linked lists:
msousa@453:  *       main list:  line_7 -> line_6 -> line2 -> line_1
msousa@453:  *       expr list:  lin4_4 -> line_3 -> (operand of line_2, i.e. '42')
msousa@453:  * 
msousa@453:  * 
msousa@453:  *     In the main list, each:
msousa@453:  *        line_x: IL_operation IL_operand
msousa@453:  *      is encoded as
msousa@453:  *          il_instruction_c(label, il_incomplete_instruction)
msousa@453:  *      these il_instruction_c objects will point back to the previous il_instruction_c object.
msousa@453:  *
msousa@453:  *     In the expr list, each 
msousa@453:  *        line_x:        IL_operation IL_operand
msousa@453:  *      is encoded as
msousa@453:  *          il_simple_instruction_c(il_simple_instruction)
msousa@453:  *      these il_simple_instruction_c objects will point back to the previous il_simple_instruction_c object,
msousa@453:  *      except the for the first il_simple_instruction_c object in the list, which will point back to
msousa@453:  *      the first il_operand (in the above example, '42'), or NULL is it does not exist.
msousa@453:  *          
msousa@453:  *
msousa@453:  * label:
msousa@453:  *   identifier_c  
msousa@453:  *   
msousa@453:  * il_incomplete_instruction:
msousa@453:  *   il_simple_operation   (il_simple_operation_c, il_function_call_c)
msousa@453:  * | il_expression         (il_expression_c)
msousa@453:  * | il_jump_operation     (il_jump_operation_c)
msousa@453:  * | il_fb_call            (il_fb_call_c)
msousa@453:  * | il_formal_funct_call  (il_formal_funct_call_c)
msousa@453:  * | il_return_operator    (RET_operator_c, RETC_operator_c, RETCN_operator_c)
msousa@453:  *  
msousa@453:  * 
msousa@453:  * il_expression_c(il_expr_operator, il_operand, simple_instr_list)
msousa@453:  * 
msousa@453:  * il_operand:
msousa@453:  *   variable            (symbolic_variable_c, direct_variable_c, array_variable_c, structured_variable_c)  
msousa@453:  * | enumerated_value    (enumerated_value_c)
msousa@453:  * | constant            (lots of literal classes _c)
msousa@453:  * 
msousa@453:  * simple_instr_list:
msousa@453:  *   list of il_simple_instruction
msousa@453:  * 
msousa@453:  * il_simple_instruction:
msousa@454:  *   il_simple_operation       (il_simple_operation_c, il_function_call_c)
msousa@453:  * | il_expression             (il_expression_c)
msousa@453:  * | il_formal_funct_call      (il_formal_funct_call_c)
msousa@453:  * 
msousa@443:  */
msousa@443: 
msousa@443: #include "flow_control_analysis.hh"
msousa@443: 
msousa@443: 
msousa@443: 
msousa@443: /* set to 1 to see debug info during execution */
msousa@443: static int debug = 0;
msousa@443: 
msousa@443: flow_control_analysis_c::flow_control_analysis_c(symbol_c *ignore) {
msousa@459:   prev_il_instruction = NULL;
msousa@459:   curr_il_instruction = NULL;
msousa@443: }
msousa@443: 
msousa@443: flow_control_analysis_c::~flow_control_analysis_c(void) {
msousa@443: }
msousa@443: 
msousa@443: 
msousa@443: 
msousa@443: /************************************/
msousa@443: /* B 1.5 Program organization units */
msousa@443: /************************************/
msousa@443: /*********************/
msousa@443: /* B 1.5.1 Functions */
msousa@443: /*********************/
msousa@443: void *flow_control_analysis_c::visit(function_declaration_c *symbol) {
msousa@459: 	search_il_label = new search_il_label_c(symbol);
msousa@443: 	if (debug) printf("Doing flow control analysis in body of function %s\n", ((token_c *)(symbol->derived_function_name))->value);
msousa@443: 	symbol->function_body->accept(*this);
msousa@459: 	delete search_il_label;
msousa@459: 	search_il_label = NULL;
msousa@443: 	return NULL;
msousa@443: }
msousa@443: 
msousa@443: /***************************/
msousa@443: /* B 1.5.2 Function blocks */
msousa@443: /***************************/
msousa@443: void *flow_control_analysis_c::visit(function_block_declaration_c *symbol) {
msousa@459: 	search_il_label = new search_il_label_c(symbol);
msousa@443: 	if (debug) printf("Doing flow control analysis in body of FB %s\n", ((token_c *)(symbol->fblock_name))->value);
msousa@443: 	symbol->fblock_body->accept(*this);
msousa@459: 	delete search_il_label;
msousa@459: 	search_il_label = NULL;
msousa@443: 	return NULL;
msousa@443: }
msousa@443: 
msousa@443: /********************/
msousa@443: /* B 1.5.3 Programs */
msousa@443: /********************/
msousa@443: void *flow_control_analysis_c::visit(program_declaration_c *symbol) {
msousa@459: 	search_il_label = new search_il_label_c(symbol);
msousa@443: 	if (debug) printf("Doing flow control analysis in body of program %s\n", ((token_c *)(symbol->program_type_name))->value);
msousa@443: 	symbol->function_block_body->accept(*this);
msousa@459: 	delete search_il_label;
msousa@459: 	search_il_label = NULL;
msousa@443: 	return NULL;
msousa@443: }
msousa@443: 
msousa@443: 
msousa@443: /********************************/
msousa@443: /* B 1.7 Configuration elements */
msousa@443: /********************************/
msousa@443: void *flow_control_analysis_c::visit(configuration_declaration_c *symbol) {
msousa@443: 	return NULL;
msousa@443: }
msousa@443: 
msousa@443: 
msousa@443: /****************************************/
msousa@443: /* B.2 - Language IL (Instruction List) */
msousa@443: /****************************************/
msousa@443: /***********************************/
msousa@443: /* B 2.1 Instructions and Operands */
msousa@443: /***********************************/
msousa@443: 
msousa@443: /*| instruction_list il_instruction */
msousa@443: // SYM_LIST(instruction_list_c)
msousa@443: void *flow_control_analysis_c::visit(instruction_list_c *symbol) {
msousa@463: 	prev_il_instruction_is_JMP_or_RET = false;
msousa@448: 	for(int i = 0; i < symbol->n; i++) {
msousa@448: 		prev_il_instruction = NULL;
msousa@448: 		if (i > 0) prev_il_instruction = symbol->elements[i-1];
msousa@459: 		curr_il_instruction = symbol->elements[i];
msousa@459: 		curr_il_instruction->accept(*this);
msousa@459: 		curr_il_instruction = NULL;
msousa@443: 	}
msousa@443: 	return NULL;
msousa@443: }
msousa@443: 
msousa@443: /* | label ':' [il_incomplete_instruction] eol_list */
msousa@443: // SYM_REF2(il_instruction_c, label, il_instruction)
msousa@443: // void *visit(instruction_list_c *symbol);
msousa@443: void *flow_control_analysis_c::visit(il_instruction_c *symbol) {
msousa@463: 	if ((NULL != prev_il_instruction) && (!prev_il_instruction_is_JMP_or_RET))
msousa@486: 		/* We try to guarantee that the previous il instruction that is in the previous line, will occupy the first element of the vector.
msousa@486: 		 * In order to do that, we use insert() instead of push_back()
msousa@486: 		 */
msousa@486: 		symbol->prev_il_instruction.insert(symbol->prev_il_instruction.begin() , prev_il_instruction);
msousa@459: 
msousa@463: 	/* check if it is an il_expression_c, a JMP[C[N]], or a RET, and if so, handle it correctly */
msousa@463: 	prev_il_instruction_is_JMP_or_RET = false;
msousa@452: 	if (NULL != symbol->il_instruction)
msousa@452: 		symbol->il_instruction->accept(*this);
msousa@453: 	return NULL;
msousa@443: }
msousa@443: 
msousa@443: 
msousa@459: 
msousa@459: /* | il_simple_operator [il_operand] */
msousa@459: // SYM_REF2(il_simple_operation_c, il_simple_operator, il_operand)
msousa@459: // void *flow_control_analysis_c::visit(il_simple_operation_c *symbol)
msousa@459: 
msousa@459: 
msousa@459: 
msousa@443: /* | function_name [il_operand_list] */
msousa@443: /* NOTE: The parameters 'called_function_declaration' and 'extensible_param_count' are used to pass data between the stage 3 and stage 4. */
msousa@443: // SYM_REF2(il_function_call_c, function_name, il_operand_list, symbol_c *called_function_declaration; int extensible_param_count;)
msousa@459: // void *flow_control_analysis_c::visit(il_function_call_c *symbol) 
msousa@459: 
msousa@443: 
msousa@443: /* | il_expr_operator '(' [il_operand] eol_list [simple_instr_list] ')' */
msousa@443: // SYM_REF3(il_expression_c, il_expr_operator, il_operand, simple_instr_list);
msousa@443: void *flow_control_analysis_c::visit(il_expression_c *symbol) {
msousa@453: 	if(NULL == symbol->simple_instr_list) 
msousa@453: 		/* nothing to do... */
msousa@453: 		return NULL;
msousa@453:   
msousa@459: 	symbol_c *save_prev_il_instruction = prev_il_instruction;
msousa@453: 	prev_il_instruction = symbol->il_operand;
msousa@453: 	symbol->simple_instr_list->accept(*this);
msousa@459: 	prev_il_instruction = save_prev_il_instruction;
msousa@459: 	return NULL;
msousa@459: }
msousa@459: 
msousa@459: 
msousa@459: /*  il_jump_operator label */
msousa@459: // SYM_REF2(il_jump_operation_c, il_jump_operator, label)
msousa@459: void *flow_control_analysis_c::visit(il_jump_operation_c *symbol) {
msousa@459:   /* search for the il_instruction_c containing the label */
msousa@459:   il_instruction_c *destination = search_il_label->find_label(symbol->label);
msousa@459: 
msousa@463:   /* give the visit(JMP_operator *) an oportunity to set the prev_il_instruction_is_JMP_or_RET flag! */
msousa@463:   symbol->il_jump_operator->accept(*this);
msousa@459:   /* add, to that il_instruction's list of prev_il_intsructions, the curr_il_instruction */
msousa@459:   if (NULL != destination)
msousa@459:     destination->prev_il_instruction.push_back(curr_il_instruction);
msousa@459:   return NULL;
msousa@459: }
msousa@459: 
msousa@459: 
msousa@443: /*   il_call_operator prev_declared_fb_name
msousa@443:  * | il_call_operator prev_declared_fb_name '(' ')'
msousa@443:  * | il_call_operator prev_declared_fb_name '(' eol_list ')'
msousa@443:  * | il_call_operator prev_declared_fb_name '(' il_operand_list ')'
msousa@443:  * | il_call_operator prev_declared_fb_name '(' eol_list il_param_list ')'
msousa@443:  */
msousa@443: /* NOTE: The parameter 'called_fb_declaration'is used to pass data between stage 3 and stage4 (although currently it is not used in stage 4 */
msousa@443: // SYM_REF4(il_fb_call_c, il_call_operator, fb_name, il_operand_list, il_param_list, symbol_c *called_fb_declaration)
msousa@459: // void *flow_control_analysis_c::visit(il_fb_call_c *symbol)
msousa@443: 
msousa@443: 
msousa@443: /* | function_name '(' eol_list [il_param_list] ')' */
msousa@443: /* NOTE: The parameter 'called_function_declaration' is used to pass data between the stage 3 and stage 4. */
msousa@443: // SYM_REF2(il_formal_funct_call_c, function_name, il_param_list, symbol_c *called_function_declaration; int extensible_param_count;)
msousa@459: // void *flow_control_analysis_c::visit(il_formal_funct_call_c *symbol)
msousa@459: 
msousa@443: 
msousa@443: 
msousa@452: //  void *visit(il_operand_list_c *symbol);
msousa@452: void *flow_control_analysis_c::visit(simple_instr_list_c *symbol) {
msousa@454: 	for(int i = 0; i < symbol->n; i++) {
msousa@453: 		/* The prev_il_instruction for element[0] was set in visit(il_expression_c *) */
msousa@453: 		if (i>0) prev_il_instruction = symbol->elements[i-1];
msousa@452: 		symbol->elements[i]->accept(*this);
msousa@452: 	}
msousa@452: 	return NULL;
msousa@452: }
msousa@452: 
msousa@453: 
msousa@453: // SYM_REF1(il_simple_instruction_c, il_simple_instruction, symbol_c *prev_il_instruction;)
msousa@453: void *flow_control_analysis_c::visit(il_simple_instruction_c*symbol) {
msousa@459: 	if (NULL != prev_il_instruction)
msousa@486: 		/* We try to guarantee that the previous il instruction that is in the previous line, will occupy the first element of the vector.
msousa@486: 		 * In order to do that, we use insert() instead of push_back()
msousa@486: 		 */
msousa@486: 		symbol->prev_il_instruction.insert(symbol->prev_il_instruction.begin() , prev_il_instruction);
msousa@453: 	return NULL;
msousa@453: }
msousa@453: 
msousa@453: 
msousa@443: /*
msousa@443:     void *visit(il_param_list_c *symbol);
msousa@443:     void *visit(il_param_assignment_c *symbol);
msousa@443:     void *visit(il_param_out_assignment_c *symbol);
msousa@443:  */
msousa@443: 
msousa@443: 
msousa@443: 
msousa@459: 
msousa@459: /*******************/
msousa@459: /* B 2.2 Operators */
msousa@459: /*******************/
msousa@459: // void *visit(   LD_operator_c *symbol);
msousa@459: // void *visit(  LDN_operator_c *symbol);
msousa@459: // void *visit(   ST_operator_c *symbol);
msousa@459: // void *visit(  STN_operator_c *symbol);
msousa@459: // void *visit(  NOT_operator_c *symbol);
msousa@459: // void *visit(    S_operator_c *symbol);
msousa@459: // void *visit(    R_operator_c *symbol);
msousa@459: // void *visit(   S1_operator_c *symbol);
msousa@459: // void *visit(   R1_operator_c *symbol);
msousa@459: // void *visit(  CLK_operator_c *symbol);
msousa@459: // void *visit(   CU_operator_c *symbol);
msousa@459: // void *visit(   CD_operator_c *symbol);
msousa@459: // void *visit(   PV_operator_c *symbol);
msousa@459: // void *visit(   IN_operator_c *symbol);
msousa@459: // void *visit(   PT_operator_c *symbol);
msousa@459: // void *visit(  AND_operator_c *symbol);
msousa@459: // void *visit(   OR_operator_c *symbol);
msousa@459: // void *visit(  XOR_operator_c *symbol);
msousa@459: // void *visit( ANDN_operator_c *symbol);
msousa@459: // void *visit(  ORN_operator_c *symbol);
msousa@459: // void *visit( XORN_operator_c *symbol);
msousa@459: // void *visit(  ADD_operator_c *symbol);
msousa@459: // void *visit(  SUB_operator_c *symbol);
msousa@459: // void *visit(  MUL_operator_c *symbol);
msousa@459: // void *visit(  DIV_operator_c *symbol);
msousa@459: // void *visit(  MOD_operator_c *symbol);
msousa@459: // void *visit(   GT_operator_c *symbol);
msousa@459: // void *visit(   GE_operator_c *symbol);
msousa@459: // void *visit(   EQ_operator_c *symbol);
msousa@459: // void *visit(   LT_operator_c *symbol);
msousa@459: // void *visit(   LE_operator_c *symbol);
msousa@459: // void *visit(   NE_operator_c *symbol);
msousa@459: // void *visit(  CAL_operator_c *symbol);
msousa@459: // void *visit( CALC_operator_c *symbol);
msousa@459: // void *visit(CALCN_operator_c *symbol);
msousa@463: 
msousa@463: /* this next visit function will be called directly from visit(il_instruction_c *) */
msousa@463: void *flow_control_analysis_c::visit(  RET_operator_c *symbol) {
msousa@463: 	prev_il_instruction_is_JMP_or_RET = true;
msousa@463: 	return NULL;
msousa@463: }
msousa@463: 
msousa@459: // void *visit( RETC_operator_c *symbol);
msousa@459: // void *visit(RETCN_operator_c *symbol);
msousa@463: 
msousa@463: /* this next visit function will be called from visit(il_jump_operation_c *) */
msousa@463: void *flow_control_analysis_c::visit(  JMP_operator_c *symbol) {
msousa@463: 	prev_il_instruction_is_JMP_or_RET = true;
msousa@463: 	return NULL;
msousa@463: }
msousa@463: 
msousa@459: // void *visit( JMPC_operator_c *symbol);
msousa@459: // void *visit(JMPCN_operator_c *symbol);
msousa@459: 
msousa@459: /* Symbol class handled together with function call checks */
msousa@459: // void *visit(il_assign_operator_c *symbol, variable_name);
msousa@459: /* Symbol class handled together with function call checks */
msousa@459: // void *visit(il_assign_operator_c *symbol, option, variable_name);
msousa@459: