1

/*

     2

 *  matiec - a compiler for the programming languages defined in IEC 61131-3

     3

 *

     4

 *  Copyright (C) 2012  Mario de Sousa (msousa@fe.up.pt)

     5

 *

     6

 *  This program is free software: you can redistribute it and/or modify

     7

 *  it under the terms of the GNU General Public License as published by

     8

 *  the Free Software Foundation, either version 3 of the License, or

     9

 *  (at your option) any later version.

    10

 *

    11

 *  This program is distributed in the hope that it will be useful,

    12

 *  but WITHOUT ANY WARRANTY; without even the implied warranty of

    13

 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    14

 *  GNU General Public License for more details.

    15

 *

    16

 *  You should have received a copy of the GNU General Public License

    17

 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.

    18

 *

    19

 *

    20

 * This code is made available on the understanding that it will not be

    21

 * used in safety-critical situations without a full and competent review.

    22

 */

    23

    24

/*

    25

 * An IEC 61131-3 compiler.

    26

 *

    27

 * Based on the

    28

 * FINAL DRAFT - IEC 61131-3, 2nd Ed. (2001-12-10)

    29

 *

    30

 */

    31

    32

    33

/*

    34

 *  Do flow control analysis of the IEC 61131-3 code.

    35

 *

    36

 *  We currently only do this for IL code.

    37

 *  This class will annotate the abstract syntax tree, by filling in the

    38

 *  prev_il_instruction variable in the il_instruction_c, so it points to

    39

 *  the previous il_instruction_c object in the instruction list instruction_list_c.

    40

 *

    41

 *  Since IL code can contain jumps (JMP), the same il_instruction may effectively have

    42

 *  several previous il_instructions. In order to accommodate this, each il_instruction

    43

 *  will maintain a vector (i..e an array) of pointers to all the previous il_instructions.

    44

 *  We do however attempt to guarantee that the first element in the vector (array) will preferentially

    45

 *  point to the il instruction that is right before / imediately preceding the current il instructions, 

    46

 *  i.e. the first element in the array will tend to point to the previous il_instruction

    47

 *  that is not a jump JMP IL instruction!

    48

 *

    49

 *  The result will essentially be a graph of il_instruction_c objects, each 

    50

 *  pointing to the previous il_instruction_c object.

    51

 *

    52

 *  The reality is we will get several independent and isolated linked lists

    53

 *  (actually, since we now process labels correctly, this is really a graph):

    54

 *  one for each block of IL code (e.g. inside a Function, FB or Program).

    55

 *  Additionally, when the IL code has an expression (expression_c object), we will actually

    56

 *  have one more isolated linked list for the IL code inside that expression.

    57

 *

    58

 *  e.g.

    59

 *       line_1:   LD 1

    60

 *       line_2:   ADD (42

    61

 *       line_3:        ADD B

    62

 *       line_4:        ADD C 

    63

 *       line_5:       )

    64

 *       line_6:   ADD D

    65

 *       line_7:   ST  E

    66

 * 

    67

 *     will result in two independent linked lists:

    68

 *       main list:  line_7 -> line_6 -> line2 -> line_1

    69

 *       expr list:  lin4_4 -> line_3 -> (operand of line_2, i.e. '42')

    70

 * 

    71

 * 

    72

 *     In the main list, each:

    73

 *        line_x: IL_operation IL_operand

    74

 *      is encoded as

    75

 *          il_instruction_c(label, il_incomplete_instruction)

    76

 *      these il_instruction_c objects will point back to the previous il_instruction_c object.

    77

 *

    78

 *     In the expr list, each 

    79

 *        line_x:        IL_operation IL_operand

    80

 *      is encoded as

    81

 *          il_simple_instruction_c(il_simple_instruction)

    82

 *      these il_simple_instruction_c objects will point back to the previous il_simple_instruction_c object,

    83

 *      except the for the first il_simple_instruction_c object in the list, which will point back to

    84

 *      the first il_operand (in the above example, '42'), or NULL is it does not exist.

    85

 *          

    86

 *

    87

 * label:

    88

 *   identifier_c  

    89

 *   

    90

 * il_incomplete_instruction:

    91

 *   il_simple_operation   (il_simple_operation_c, il_function_call_c)

    92

 * | il_expression         (il_expression_c)

    93

 * | il_jump_operation     (il_jump_operation_c)

    94

 * | il_fb_call            (il_fb_call_c)

    95

 * | il_formal_funct_call  (il_formal_funct_call_c)

    96

 * | il_return_operator    (RET_operator_c, RETC_operator_c, RETCN_operator_c)

    97

 *  

    98

 * 

    99

 * il_expression_c(il_expr_operator, il_operand, simple_instr_list)

   100

 * 

   101

 * il_operand:

   102

 *   variable            (symbolic_variable_c, direct_variable_c, array_variable_c, structured_variable_c)  

   103

 * | enumerated_value    (enumerated_value_c)

   104

 * | constant            (lots of literal classes _c)

   105

 * 

   106

 * simple_instr_list:

   107

 *   list of il_simple_instruction

   108

 * 

   109

 * il_simple_instruction:

   110

 *   il_simple_operation       (il_simple_operation_c, il_function_call_c)

   111

 * | il_expression             (il_expression_c)

   112

 * | il_formal_funct_call      (il_formal_funct_call_c)

   113

 * 

   114

 */

   115

   116

#include "flow_control_analysis.hh"

   117

   118

   119

   120

/* set to 1 to see debug info during execution */

   121

static int debug = 0;

   122

   123

flow_control_analysis_c::flow_control_analysis_c(symbol_c *ignore) {

   124

  prev_il_instruction = NULL;

   125

  curr_il_instruction = NULL;

   126

  prev_il_instruction_is_JMP_or_RET = false;

   127

  search_il_label = NULL;

   128

}

   129

   130

flow_control_analysis_c::~flow_control_analysis_c(void) {

   131

}

   132

   133

   134

void flow_control_analysis_c::link_insert(symbol_c *prev_instruction, symbol_c *next_instruction) {

   135

	il_instruction_c        *next_a = dynamic_cast<il_instruction_c        *>(next_instruction);

   136

	il_instruction_c        *prev_a = dynamic_cast<il_instruction_c        *>(prev_instruction);

   137

	il_simple_instruction_c *next_b = dynamic_cast<il_simple_instruction_c *>(next_instruction);

   138

	il_simple_instruction_c *prev_b = dynamic_cast<il_simple_instruction_c *>(prev_instruction);

   139

   140

	if       (NULL != next_a)  next_a->prev_il_instruction.insert(next_a->prev_il_instruction.begin(), prev_instruction);

   141

	else if  (NULL != next_b)  next_b->prev_il_instruction.insert(next_b->prev_il_instruction.begin(), prev_instruction);

   142

	else ERROR;

   143

   144

	if       (NULL != prev_a)  prev_a->next_il_instruction.insert(prev_a->next_il_instruction.begin(), next_instruction);

   145

	else if  (NULL != prev_b)  prev_b->next_il_instruction.insert(prev_b->next_il_instruction.begin(), next_instruction);

   146

	else ERROR;

   147

}

   148

   149

   150

void flow_control_analysis_c::link_pushback(symbol_c *prev_instruction, symbol_c *next_instruction) {

   151

	il_instruction_c *next = dynamic_cast<il_instruction_c *>(next_instruction);

   152

	il_instruction_c *prev = dynamic_cast<il_instruction_c *>(prev_instruction);

   153

	if ((NULL == next) || (NULL == prev)) ERROR;

   154

   155

	next->prev_il_instruction.push_back(prev);

   156

	prev->next_il_instruction.push_back(next);

   157

}

   158

   159

   160

/************************************/

   161

/* B 1.5 Program organization units */

   162

/************************************/

   163

/*********************/

   164

/* B 1.5.1 Functions */

   165

/*********************/

   166

void *flow_control_analysis_c::visit(function_declaration_c *symbol) {

   167

	search_il_label = new search_il_label_c(symbol);

   168

	if (debug) printf("Doing flow control analysis in body of function %s\n", ((token_c *)(symbol->derived_function_name))->value);

   169

	symbol->function_body->accept(*this);

   170

	delete search_il_label;

   171

	search_il_label = NULL;

   172

	return NULL;

   173

}

   174

   175

/***************************/

   176

/* B 1.5.2 Function blocks */

   177

/***************************/

   178

void *flow_control_analysis_c::visit(function_block_declaration_c *symbol) {

   179

	search_il_label = new search_il_label_c(symbol);

   180

	if (debug) printf("Doing flow control analysis in body of FB %s\n", ((token_c *)(symbol->fblock_name))->value);

   181

	symbol->fblock_body->accept(*this);

   182

	delete search_il_label;

   183

	search_il_label = NULL;

   184

	return NULL;

   185

}

   186

   187

/********************/

   188

/* B 1.5.3 Programs */

   189

/********************/

   190

void *flow_control_analysis_c::visit(program_declaration_c *symbol) {

   191

	search_il_label = new search_il_label_c(symbol);

   192

	if (debug) printf("Doing flow control analysis in body of program %s\n", ((token_c *)(symbol->program_type_name))->value);

   193

	symbol->function_block_body->accept(*this);

   194

	delete search_il_label;

   195

	search_il_label = NULL;

   196

	return NULL;

   197

}

   198

   199

   200

/********************************/

   201

/* B 1.7 Configuration elements */

   202

/********************************/

   203

void *flow_control_analysis_c::visit(configuration_declaration_c *symbol) {

   204

	return NULL;

   205

}

   206

   207

   208

/****************************************/

   209

/* B.2 - Language IL (Instruction List) */

   210

/****************************************/

   211

/***********************************/

   212

/* B 2.1 Instructions and Operands */

   213

/***********************************/

   214

   215

/*| instruction_list il_instruction */

   216

// SYM_LIST(instruction_list_c)

   217

void *flow_control_analysis_c::visit(instruction_list_c *symbol) {

   218

	prev_il_instruction_is_JMP_or_RET = false;

   219

	for(int i = 0; i < symbol->n; i++) {

   220

		prev_il_instruction = NULL;

   221

		if (i > 0) prev_il_instruction = symbol->get_element(i-1);

   222

		curr_il_instruction = symbol->get_element(i);

   223

		curr_il_instruction->accept(*this);

   224

		curr_il_instruction = NULL;

   225

	}

   226

	return NULL;

   227

}

   228

   229

/* | label ':' [il_incomplete_instruction] eol_list */

   230

// SYM_REF2(il_instruction_c, label, il_instruction)

   231

// void *visit(instruction_list_c *symbol);

   232

void *flow_control_analysis_c::visit(il_instruction_c *symbol) {

   233

	if ((NULL != prev_il_instruction) && (!prev_il_instruction_is_JMP_or_RET))

   234

		/* We try to guarantee that the previous il instruction that is in the previous line, will occupy the first element of the vector.

   235

		 * In order to do that, we use insert() instead of push_back()

   236

		 */

   237

		link_insert(prev_il_instruction, symbol);

   238

   239

	/* check if it is an il_expression_c, a JMP[C[N]], or a RET, and if so, handle it correctly */

   240

	prev_il_instruction_is_JMP_or_RET = false;

   241

	if (NULL != symbol->il_instruction)

   242

		symbol->il_instruction->accept(*this);

   243

	return NULL;

   244

}

   245

   246

   247

   248

/* | il_simple_operator [il_operand] */

   249

// SYM_REF2(il_simple_operation_c, il_simple_operator, il_operand)

   250

// void *flow_control_analysis_c::visit(il_simple_operation_c *symbol)

   251

   252

   253

   254

/* | function_name [il_operand_list] */

   255

/* NOTE: The parameters 'called_function_declaration' and 'extensible_param_count' are used to pass data between the stage 3 and stage 4. */

   256

// SYM_REF2(il_function_call_c, function_name, il_operand_list, symbol_c *called_function_declaration; int extensible_param_count;)

   257

// void *flow_control_analysis_c::visit(il_function_call_c *symbol) 

   258

   259

   260

/* | il_expr_operator '(' [il_operand] eol_list [simple_instr_list] ')' */

   261

// SYM_REF3(il_expression_c, il_expr_operator, il_operand, simple_instr_list);

   262

void *flow_control_analysis_c::visit(il_expression_c *symbol) {

   263

	if(NULL == symbol->simple_instr_list) 

   264

		/* nothing to do... */

   265

		return NULL;

   266

   267

	symbol_c *save_prev_il_instruction = prev_il_instruction;

   268

	/* Stage2 will insert an artificial (and equivalent) LD <il_operand> to the simple_instr_list if necessary. We can therefore ignore the 'il_operand' entry! */

   269

	// prev_il_instruction = symbol->il_operand;

   270

	prev_il_instruction = NULL;

   271

	symbol->simple_instr_list->accept(*this);

   272

	prev_il_instruction = save_prev_il_instruction;

   273

	return NULL;

   274

}

   275

   276

   277

/*  il_jump_operator label */

   278

// SYM_REF2(il_jump_operation_c, il_jump_operator, label)

   279

void *flow_control_analysis_c::visit(il_jump_operation_c *symbol) {

   280

  /* search for the il_instruction_c containing the label */

   281

  il_instruction_c *destination = search_il_label->find_label(symbol->label);

   282

   283

  /* give the visit(JMP_operator *) an oportunity to set the prev_il_instruction_is_JMP_or_RET flag! */

   284

  symbol->il_jump_operator->accept(*this);

   285

  if (NULL != destination)

   286

    link_pushback(curr_il_instruction, destination);

   287

  return NULL;

   288

}

   289

   290

   291

/*   il_call_operator prev_declared_fb_name

   292

 * | il_call_operator prev_declared_fb_name '(' ')'

   293

 * | il_call_operator prev_declared_fb_name '(' eol_list ')'

   294

 * | il_call_operator prev_declared_fb_name '(' il_operand_list ')'

   295

 * | il_call_operator prev_declared_fb_name '(' eol_list il_param_list ')'

   296

 */

   297

/* 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 */

   298

// SYM_REF4(il_fb_call_c, il_call_operator, fb_name, il_operand_list, il_param_list, symbol_c *called_fb_declaration)

   299

// void *flow_control_analysis_c::visit(il_fb_call_c *symbol)

   300

   301

   302

/* | function_name '(' eol_list [il_param_list] ')' */

   303

/* NOTE: The parameter 'called_function_declaration' is used to pass data between the stage 3 and stage 4. */

   304

// SYM_REF2(il_formal_funct_call_c, function_name, il_param_list, symbol_c *called_function_declaration; int extensible_param_count;)

   305

// void *flow_control_analysis_c::visit(il_formal_funct_call_c *symbol)

   306

   307

   308

   309

//  void *visit(il_operand_list_c *symbol);

   310

void *flow_control_analysis_c::visit(simple_instr_list_c *symbol) {

   311

	for(int i = 0; i < symbol->n; i++) {

   312

		/* The prev_il_instruction for element[0] was set in visit(il_expression_c *) */

   313

		if (i>0) prev_il_instruction = symbol->get_element(i-1);

   314

		symbol->get_element(i)->accept(*this);

   315

	}

   316

	return NULL;

   317

}

   318

   319

   320

// SYM_REF1(il_simple_instruction_c, il_simple_instruction, symbol_c *prev_il_instruction;)

   321

void *flow_control_analysis_c::visit(il_simple_instruction_c*symbol) {

   322

	if (NULL != prev_il_instruction)

   323

		/* We try to guarantee that the previous il instruction that is in the previous line, will occupy the first element of the vector.

   324

		 * In order to do that, we use insert() instead of push_back()

   325

		 */

   326

		link_insert(prev_il_instruction, symbol);

   327

   328

	return NULL;

   329

}

   330

   331

   332

/*

   333

    void *visit(il_param_list_c *symbol);

   334

    void *visit(il_param_assignment_c *symbol);

   335

    void *visit(il_param_out_assignment_c *symbol);

   336

 */

   337

   338

   339

   340

   341

/*******************/

   342

/* B 2.2 Operators */

   343

/*******************/

   344

// void *visit(   LD_operator_c *symbol);

   345

// void *visit(  LDN_operator_c *symbol);

   346

// void *visit(   ST_operator_c *symbol);

   347

// void *visit(  STN_operator_c *symbol);

   348

// void *visit(  NOT_operator_c *symbol);

   349

// void *visit(    S_operator_c *symbol);

   350

// void *visit(    R_operator_c *symbol);

   351

// void *visit(   S1_operator_c *symbol);

   352

// void *visit(   R1_operator_c *symbol);

   353

// void *visit(  CLK_operator_c *symbol);

   354

// void *visit(   CU_operator_c *symbol);

   355

// void *visit(   CD_operator_c *symbol);

   356

// void *visit(   PV_operator_c *symbol);

   357

// void *visit(   IN_operator_c *symbol);

   358

// void *visit(   PT_operator_c *symbol);

   359

// void *visit(  AND_operator_c *symbol);

   360

// void *visit(   OR_operator_c *symbol);

   361

// void *visit(  XOR_operator_c *symbol);

   362

// void *visit( ANDN_operator_c *symbol);

   363

// void *visit(  ORN_operator_c *symbol);

   364

// void *visit( XORN_operator_c *symbol);

   365

// void *visit(  ADD_operator_c *symbol);

   366

// void *visit(  SUB_operator_c *symbol);

   367

// void *visit(  MUL_operator_c *symbol);

   368

// void *visit(  DIV_operator_c *symbol);

   369

// void *visit(  MOD_operator_c *symbol);

   370

// void *visit(   GT_operator_c *symbol);

   371

// void *visit(   GE_operator_c *symbol);

   372

// void *visit(   EQ_operator_c *symbol);

   373

// void *visit(   LT_operator_c *symbol);

   374

// void *visit(   LE_operator_c *symbol);

   375

// void *visit(   NE_operator_c *symbol);

   376

// void *visit(  CAL_operator_c *symbol);

   377

// void *visit( CALC_operator_c *symbol);

   378

// void *visit(CALCN_operator_c *symbol);

   379

   380

/* this next visit function will be called directly from visit(il_instruction_c *) */

   381

void *flow_control_analysis_c::visit(  RET_operator_c *symbol) {

   382

	prev_il_instruction_is_JMP_or_RET = true;

   383

	return NULL;

   384

}

   385

   386

// void *visit( RETC_operator_c *symbol);

   387

// void *visit(RETCN_operator_c *symbol);

   388

   389

/* this next visit function will be called from visit(il_jump_operation_c *) */

   390

void *flow_control_analysis_c::visit(  JMP_operator_c *symbol) {

   391

	prev_il_instruction_is_JMP_or_RET = true;

   392

	return NULL;

   393

}

   394

   395

// void *visit( JMPC_operator_c *symbol);

   396

// void *visit(JMPCN_operator_c *symbol);

   397

   398

/* Symbol class handled together with function call checks */

   399

// void *visit(il_assign_operator_c *symbol, variable_name);

   400

/* Symbol class handled together with function call checks */

   401

// void *visit(il_assign_operator_c *symbol, option, variable_name);

   402