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 . 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; conti@661: prev_il_instruction_is_JMP_or_RET = false; conti@661: search_il_label = NULL; msousa@443: } msousa@443: msousa@443: flow_control_analysis_c::~flow_control_analysis_c(void) { msousa@443: } msousa@443: msousa@443: msousa@672: void flow_control_analysis_c::link_insert(symbol_c *prev_instruction, symbol_c *next_instruction) { msousa@685: il_instruction_c *next_a = dynamic_cast(next_instruction); msousa@685: il_instruction_c *prev_a = dynamic_cast(prev_instruction); msousa@685: il_simple_instruction_c *next_b = dynamic_cast(next_instruction); msousa@685: il_simple_instruction_c *prev_b = dynamic_cast(prev_instruction); msousa@685: msousa@685: if (NULL != next_a) next_a->prev_il_instruction.insert(next_a->prev_il_instruction.begin(), prev_instruction); msousa@685: else if (NULL != next_b) next_b->prev_il_instruction.insert(next_b->prev_il_instruction.begin(), prev_instruction); msousa@685: else ERROR; msousa@685: msousa@685: if (NULL != prev_a) prev_a->next_il_instruction.insert(prev_a->next_il_instruction.begin(), next_instruction); msousa@685: else if (NULL != prev_b) prev_b->next_il_instruction.insert(prev_b->next_il_instruction.begin(), next_instruction); msousa@685: else ERROR; msousa@672: } msousa@672: msousa@672: msousa@672: void flow_control_analysis_c::link_pushback(symbol_c *prev_instruction, symbol_c *next_instruction) { msousa@672: il_instruction_c *next = dynamic_cast(next_instruction); msousa@672: il_instruction_c *prev = dynamic_cast(prev_instruction); msousa@672: if ((NULL == next) || (NULL == prev)) ERROR; msousa@672: msousa@672: next->prev_il_instruction.push_back(prev); msousa@672: prev->next_il_instruction.push_back(next); msousa@672: } msousa@672: 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@672: link_insert(prev_il_instruction, symbol); 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@690: /* Stage2 will insert an artificial (and equivalent) LD to the simple_instr_list if necessary. We can therefore ignore the 'il_operand' entry! */ msousa@690: // prev_il_instruction = symbol->il_operand; msousa@690: prev_il_instruction = NULL; 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: if (NULL != destination) msousa@672: link_pushback(curr_il_instruction, destination); 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@672: link_insert(prev_il_instruction, symbol); msousa@672: 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: