1

/*

     2

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

     3

 *

     4

 *  Copyright (C) 2003-2011  Mario de Sousa (msousa@fe.up.pt)

     5

 *  Copyright (C) 2012       Manuele Conti (conti.ma@alice.it)

     6

 *

     7

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

     8

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

     9

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

    10

 *  (at your option) any later version.

    11

 *

    12

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

    13

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

    14

 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    15

 *  GNU General Public License for more details.

    16

 *

    17

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

    18

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

    19

 *

    20

 *

    21

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

    22

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

    23

 */

    24

    25

/*

    26

 * An IEC 61131-3 compiler.

    27

 *

    28

 * Based on the

    29

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

    30

 *

    31

 */

    32

    33

    34

/* NOTE:

    35

 *   Most of the conditions to detect overflows on signed (but not unsigned) integer operations were adapted from

    36

 *   https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false

    37

 */

    38

    39

    40

    41

/* Do constant folding...

    42

 *

    43

 * I.e., Determine the value of all expressions in which only constant values (i.e. literals) are used.

    44

 * The (constant) result of each operation is stored (annotated) in the respective operation symbol 

    45

 * (e.g.: add_expression_c) in the abstract syntax tree,

    46

 *

    47

 * For example:

    48

 *       2 + 3         -> the constant value '5'    is stored in the add_expression_c symbol.

    49

 *       22.2 - 5.0    -> the constant value '17.2' is stored in the add_expression_c symbol.

    50

 *       etc...

    51

 *

    52

 *

    53

 * NOTE 1 

    54

 *      Some operations and constants can have multiple data types. For example,

    55

 *        1 AND 0

    56

 *      may be either a BOOL, BYTE, WORD or LWORD.

    57

 *

    58

 *      The same happens with 

    59

 *        1 + 2

    60

 *      which may be signed (e.g. INT) or unsigned (UINT)

    61

 *

    62

 *      For the above reason, instead of storing a single constant value, we actually store 4:

    63

 *        - bool

    64

 *        - uint64

    65

 *        -  int64

    66

 *        - real64

    67

 *

    68

 *      Additionally, since the result of an operation may result in an overflow, we actually

    69

 *      store the result inside a struct (defined in absyntax.hh)

    70

 *

    71

 *             ** During stage 3 (semantic analysis/checking) we will be doing constant folding.

    72

 *              * That algorithm will anotate the abstract syntax tree with the result of operations

    73

 *              * on literals (i.e. 44 + 55 will store the result 99).

    74

 *              * Since the same source code (e.g. 1 + 0) may actually be a BOOL or an ANY_INT,

    75

 *              * or an ANY_BIT, we need to handle all possibilities, and determine the result of the

    76

 *              * operation assuming each type.

    77

 *              * For this reason, we have one entry for each possible type, with some expressions

    78

 *              * having more than one entry filled in!

    79

 *              **

    80

 *             typedef enum { cs_undefined,   // not defined --> const_value is not valid!

    81

 *                            cs_const_value, // const value is valid

    82

 *                            cs_overflow     // result produced overflow or underflow --> const_value is not valid!

    83

 *                          } const_status_t;

    84

 *    

    85

 *             typedef struct {

    86

 *                 const_status_t status;

    87

 *                 real64_t       value; 

    88

 *             } const_value_real64_t;

    89

 *             const_value_real64_t *const_value_real64; // when NULL --> UNDEFINED

    90

 *             

    91

 *             typedef struct {

    92

 *                 const_status_t status;

    93

 *                 int64_t        value; 

    94

 *             } const_value_int64_t;

    95

 *             const_value_int64_t *const_value_int64; // when NULL --> UNDEFINED

    96

 *             

    97

 *             typedef struct {

    98

 *                 const_status_t status;

    99

 *                 uint64_t       value; 

   100

 *             } const_value_uint64_t;

   101

 *             const_value_uint64_t *const_value_uint64; // when NULL --> UNDEFINED

   102

 *             

   103

 *             typedef struct {

   104

 *                 const_status_t status;

   105

 *                 bool           value; 

   106

 *             } const_value_bool_t;

   107

 *             const_value_bool_t *const_value_bool; // when NULL --> UNDEFINED

   108

 *

   109

 *

   110

 *

   111

 * NOTE 2 

   112

 *    This file does not print out any error messages!

   113

 *    We cannot really print out error messages when we find an overflow. Since each operation

   114

 *    (symbol in the absract syntax tree for that operation) will have up to 4 constant results,

   115

 *    it may happen that some of them overflow, while other do not.

   116

 *    We must wait for data type checking to determine the exact data type of each expression

   117

 *    before we can decide whether or not we should print out an overflow error message.

   118

 *

   119

 *    For this reason, this visitor merely annotates the abstract syntax tree, and leaves the

   120

 *    actuall printing of errors for the print_datatype_errors_c class!

   121

 */

   122

   123

#include "constant_folding.hh"

   124

#include <limits>

   125

#include <math.h> /* required for pow function */

   126

#include <stdlib.h> /* required for malloc() */

   127

   128

#if 1

   129

#define INT64_MAX (std::numeric_limits< int64_t >::max())

   130

#define INT64_MIN (std::numeric_limits< int64_t >::min()) 

   131

#else

   132

/* An alternative is to use the std::numeric_limits< uint64_t >::min() / max()  methods already defined in #include <limits> */

   133

#define __STDC_LIMIT_MACROS /* required for UINT64_MAX, INT64_MAX, INT64_MIN, ... */

   134

#include <stdint.h>         /* required for UINT64_MAX, INT64_MAX, INT64_MIN, ... */

   135

#endif

   136

   137

   138

#define FIRST_(symbol1, symbol2) (((symbol1)->first_order < (symbol2)->first_order)   ? (symbol1) : (symbol2))

   139

#define  LAST_(symbol1, symbol2) (((symbol1)->last_order  > (symbol2)->last_order)    ? (symbol1) : (symbol2))

   140

   141

#define STAGE3_ERROR(error_level, symbol1, symbol2, ...) {                                                                  \

   142

  if (current_display_error_level >= error_level) {                                                                         \

   143

    fprintf(stderr, "%s:%d-%d..%d-%d: error: ",                                                                             \

   144

            FIRST_(symbol1,symbol2)->first_file, FIRST_(symbol1,symbol2)->first_line, FIRST_(symbol1,symbol2)->first_column,\

   145

                                                 LAST_(symbol1,symbol2) ->last_line,  LAST_(symbol1,symbol2) ->last_column);\

   146

    fprintf(stderr, __VA_ARGS__);                                                                                           \

   147

    fprintf(stderr, "\n");                                                                                                  \

   148

    error_count++;                                                                                                     \

   149

  }                                                                                                                         \

   150

}

   151

   152

   153

#define STAGE3_WARNING(symbol1, symbol2, ...) {                                                                             \

   154

    fprintf(stderr, "%s:%d-%d..%d-%d: warning: ",                                                                           \

   155

            FIRST_(symbol1,symbol2)->first_file, FIRST_(symbol1,symbol2)->first_line, FIRST_(symbol1,symbol2)->first_column,\

   156

                                                 LAST_(symbol1,symbol2) ->last_line,  LAST_(symbol1,symbol2) ->last_column);\

   157

    fprintf(stderr, __VA_ARGS__);                                                                                           \

   158

    fprintf(stderr, "\n");                                                                                                  \

   159

    warning_found = true;                                                                                                   \

   160

}

   161

   162

   163

   164

   165

   166

   167

   168

   169

   170

   171

   172

   173

#define NEW_CVALUE(dtype, symbol) \

   174

 (symbol->const_value_##dtype) = new(symbol_c::const_value_##dtype##_t); \

   175

 if ((symbol->const_value_##dtype) == NULL) ERROR; \

   176

 (symbol->const_value_##dtype)->status = symbol_c::cs_undefined;

   177

   178

#define SET_CVALUE(dtype, symbol, new_value)  ((symbol)->const_value_##dtype->value) = new_value; ((symbol)->const_value_##dtype->status) = symbol_c::cs_const_value;  

   179

#define GET_CVALUE(dtype, symbol)             ((symbol)->const_value_##dtype->value) 

   180

#define SET_OVFLOW(dtype, symbol)             ((symbol)->const_value_##dtype->status) = symbol_c::cs_overflow

   181

    /* The following test is correct in the presence of a NULL pointer, as the logical evaluation will be suspended as soon as the first condition is false! */

   182

#define VALID_CVALUE(dtype, symbol)           ((NULL != (symbol)->const_value_##dtype) && (symbol_c::cs_const_value == (symbol)->const_value_##dtype->status))

   183

#define ISZERO_CVALUE(dtype, symbol)          ((VALID_CVALUE(dtype, symbol)) && (GET_CVALUE(dtype, symbol) == 0))

   184

#define DO_BIN_OPER(dtype, oper)\

   185

	if (VALID_CVALUE(dtype, symbol->r_exp) && VALID_CVALUE(dtype, symbol->l_exp)) {                                \

   186

		NEW_CVALUE(dtype, symbol);                                                                             \

   187

		SET_CVALUE(dtype, symbol, GET_CVALUE(dtype, symbol->l_exp) oper GET_CVALUE(dtype, symbol->r_exp));     \

   188

	}

   189

   190

   191

   192

   193

   194

   195

   196

   197

   198

   199

   200

/* res = a + b */

   201

static void CHECK_OVERFLOW_uint64_SUM(symbol_c *res, symbol_c *a, symbol_c *b) {

   202

	if (VALID_CVALUE(uint64, res))

   203

		/* If sum is smaller than either operand => overflow! */

   204

		if (GET_CVALUE(uint64, res) < GET_CVALUE(uint64, a))

   205

			SET_OVFLOW(uint64, res);

   206

}

   207

   208

/* res = a - b */

   209

static void CHECK_OVERFLOW_uint64_SUB(symbol_c *res, symbol_c *a, symbol_c *b) {

   210

	if (VALID_CVALUE(uint64, res))

   211

		/* If diference is larger than a => overflow! */

   212

		if (GET_CVALUE(uint64, res) > GET_CVALUE(uint64, a))

   213

			SET_OVFLOW(uint64, res);

   214

}

   215

   216

/* res = a * b */

   217

static void CHECK_OVERFLOW_uint64_MUL(symbol_c *res, symbol_c *a, symbol_c *b) {

   218

	if (VALID_CVALUE(uint64, res))

   219

		if (false /* TODO */)

   220

			SET_OVFLOW(uint64, res);

   221

}

   222

   223

/* res = a / b */

   224

static void CHECK_OVERFLOW_uint64_DIV(symbol_c *res, symbol_c *a, symbol_c *b) {

   225

	if (VALID_CVALUE(uint64, res))

   226

		if (false /* TODO */)

   227

			SET_OVFLOW(uint64, res);

   228

}

   229

   230

/* res = a MOD b */

   231

static void CHECK_OVERFLOW_uint64_MOD(symbol_c *res, symbol_c *a, symbol_c *b) {

   232

	if (VALID_CVALUE(uint64, res))

   233

		if (false /* TODO */)

   234

			SET_OVFLOW(uint64, res);

   235

}

   236

   237

/* res = a + b */

   238

static void CHECK_OVERFLOW_int64_SUM(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {

   239

	int64_t a = GET_CVALUE(int64, a_ptr);

   240

	int64_t b = GET_CVALUE(int64, b_ptr);

   241

	if (VALID_CVALUE(int64, res))

   242

		/* The following test is valid no matter what representation is being used (e.g. two's complement, etc...) */

   243

		if (((b > 0) && (a > (INT64_MAX - b)))

   244

		 || ((b < 0) && (a < (INT64_MIN - b))))

   245

			SET_OVFLOW(int64, res);

   246

}

   247

   248

/* res = a - b */

   249

static void CHECK_OVERFLOW_int64_SUB(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {

   250

	int64_t a = GET_CVALUE(int64, a_ptr);

   251

	int64_t b = GET_CVALUE(int64, b_ptr);

   252

	if (VALID_CVALUE(int64, res))

   253

		/* The following test is valid no matter what representation is being used (e.g. two's complement, etc...) */

   254

		if (((b > 0) && (a < (INT64_MIN + b)))

   255

		 || ((b < 0) && (a > (INT64_MAX + b))))

   256

			SET_OVFLOW(int64, res);

   257

}

   258

   259

   260

/* res = a * b */

   261

static void CHECK_OVERFLOW_int64_MUL(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {

   262

	int64_t a = GET_CVALUE(int64, a_ptr);

   263

	int64_t b = GET_CVALUE(int64, b_ptr);

   264

	if (VALID_CVALUE(int64, res))

   265

		if (   ( (a > 0) &&  (b > 0) &&             (a > (INT64_MAX / b))) 

   266

		    || ( (a > 0) && !(b > 0) &&             (b < (INT64_MIN / a))) 

   267

		    || (!(a > 0) &&  (b > 0) &&             (a < (INT64_MIN / b))) 

   268

		    || (!(a > 0) && !(b > 0) && (a != 0) && (b < (INT64_MAX / a))))

   269

			SET_OVFLOW(int64, res);

   270

}

   271

   272

   273

/* res = a / b */

   274

static void CHECK_OVERFLOW_int64_DIV(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {

   275

	int64_t a = GET_CVALUE(int64, a_ptr);

   276

	int64_t b = GET_CVALUE(int64, b_ptr);

   277

	if (VALID_CVALUE(int64, res))

   278

		if ((b == 0) || ((a == INT64_MIN) && (b == -1)))

   279

			SET_OVFLOW(int64, res);

   280

}

   281

   282

   283

/* res = a MOD b */

   284

static void CHECK_OVERFLOW_int64_MOD(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {

   285

	int64_t a = GET_CVALUE(int64, a_ptr);

   286

	int64_t b = GET_CVALUE(int64, b_ptr);

   287

	/* IEC 61131-3 standard says IN1 MOD IN2 must be equivalent to

   288

	 *  IF (IN2 = 0) THEN OUT:=0 ; ELSE OUT:=IN1 - (IN1/IN2)*IN2 ; END_IF

   289

	 *

   290

	 * Note that, when IN1 = INT64_MIN, and IN2 = -1, an overflow occurs in the division,

   291

	 * so although the MOD operation should be OK, acording to the above definition, we actually have an overflow!!

   292

	 *

   293

	 * On the other hand, division by 0 is OK!!

   294

	 */

   295

	if (VALID_CVALUE(int64, res))

   296

		if ((a == INT64_MIN) && (b == -1))

   297

			SET_OVFLOW(int64, res);

   298

}

   299

   300

   301

/* res = - a */

   302

static void CHECK_OVERFLOW_int64_NEG(symbol_c *res, symbol_c *a_ptr) {

   303

	int64_t a = GET_CVALUE(int64, a_ptr);

   304

	if (VALID_CVALUE(int64, res))

   305

		if (a == INT64_MIN)

   306

			SET_OVFLOW(int64, res);

   307

}

   308

   309

   310

   311

static void CHECK_OVERFLOW_real64(symbol_c *res) {

   312

	if (VALID_CVALUE(real64, res))

   313

        	/* NaN => underflow, overflow, number is a higher precision format, is a complex number (IEEE standard) */

   314

		 if (isnan(GET_CVALUE(real64, res)))

   315

			SET_OVFLOW(real64, res);

   316

}

   317

   318

   319

   320

   321

   322

   323

   324

   325

   326

   327

   328

   329

   330

   331

constant_folding_c::constant_folding_c(symbol_c *symbol) {

   332

    error_count = 0;

   333

    warning_found = false;

   334

    current_display_error_level = 0;

   335

   336

    /* check whether the platform on which the compiler is being run implements IEC 559 floating point data types. */

   337

    symbol_c null_symbol;

   338

    if (! (std::numeric_limits<real64_t>::is_iec559) )

   339

        STAGE3_WARNING(&null_symbol, &null_symbol, "The platform running the compiler does not implement IEC 559 floating point numbers. "

   340

                                                   "Any error and/or warning messages related to overflow/underflow of the result of operations on REAL/LREAL literals "

   341

                                                   " (i.e. constant folding) may themselves be erroneous, although are most probably correct.");

   342

}

   343

   344

   345

constant_folding_c::~constant_folding_c(void) {

   346

}

   347

   348

   349

int constant_folding_c::get_error_count() {

   350

	return error_count;

   351

}

   352

   353

   354

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

   355

/* B 1.2 - Constants */

   356

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

   357

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

   358

/* B 1.2.1 - Numeric Literals */

   359

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

   360

void *constant_folding_c::visit(real_c *symbol) {

   361

	NEW_CVALUE(real64, symbol);

   362

	SET_CVALUE(real64, symbol, extract_real_value(symbol));

   363

	return NULL;

   364

}

   365

   366

   367

void *constant_folding_c::visit(integer_c *symbol) {

   368

	NEW_CVALUE( int64, symbol);

   369

	SET_CVALUE( int64, symbol, extract_integer_value(symbol));

   370

	NEW_CVALUE(uint64, symbol);

   371

	SET_CVALUE(uint64, symbol, extract_integer_value(symbol));

   372

	return NULL;

   373

}

   374

   375

   376

void *constant_folding_c::visit(neg_real_c *symbol) {

   377

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

   378

	if (!VALID_CVALUE(real64, symbol->exp))

   379

		return NULL;

   380

	NEW_CVALUE(real64, symbol);

   381

	SET_CVALUE(real64, symbol, - GET_CVALUE( real64, symbol->exp));

   382

	CHECK_OVERFLOW_real64(symbol);

   383

	return NULL;

   384

}

   385

   386

/* | '-' integer	{$$ = new neg_integer_c($2, locloc(@$));} */

   387

void *constant_folding_c::visit(neg_integer_c *symbol) {

   388

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

   389

	if (VALID_CVALUE(int64, symbol->exp)) {

   390

		NEW_CVALUE( int64, symbol);

   391

		SET_CVALUE( int64, symbol, - GET_CVALUE( int64, symbol->exp));

   392

	}

   393

       	CHECK_OVERFLOW_int64_NEG(symbol, symbol->exp);

   394

	return NULL;

   395

}

   396

   397

   398

void *constant_folding_c::visit(binary_integer_c *symbol) {

   399

	return NULL;

   400

}

   401

   402

   403

void *constant_folding_c::visit(octal_integer_c *symbol) {

   404

	return NULL;

   405

}

   406

   407

   408

void *constant_folding_c::visit(hex_integer_c *symbol) {

   409

	NEW_CVALUE( int64, symbol);

   410

	SET_CVALUE( int64, symbol, extract_hex_value(symbol));

   411

	NEW_CVALUE(uint64, symbol);

   412

	SET_CVALUE(uint64, symbol, extract_hex_value(symbol));

   413

	return NULL;

   414

}

   415

   416

   417

/*

   418

integer_literal:

   419

  integer_type_name '#' signed_integer	{$$ = new integer_literal_c($1, $3, locloc(@$));}

   420

| integer_type_name '#' binary_integer	{$$ = new integer_literal_c($1, $3, locloc(@$));}

   421

| integer_type_name '#' octal_integer	{$$ = new integer_literal_c($1, $3, locloc(@$));}

   422

| integer_type_name '#' hex_integer	{$$ = new integer_literal_c($1, $3, locloc(@$));}

   423

*/

   424

// SYM_REF2(integer_literal_c, type, value)

   425

void *constant_folding_c::visit(integer_literal_c *symbol) {

   426

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

   427

	if (VALID_CVALUE( int64, symbol->value)) {

   428

		NEW_CVALUE( int64, symbol);

   429

		SET_CVALUE( int64, symbol, GET_CVALUE( int64, symbol->value));

   430

	}

   431

	if (VALID_CVALUE(uint64, symbol->value)) {

   432

		NEW_CVALUE(uint64, symbol);

   433

		SET_CVALUE(uint64, symbol, GET_CVALUE(uint64, symbol->value));

   434

	}

   435

	return NULL;

   436

}

   437

   438

   439

void *constant_folding_c::visit(real_literal_c *symbol) {

   440

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

   441

	if (VALID_CVALUE(real64, symbol->value)) {

   442

		NEW_CVALUE(real64, symbol);

   443

		SET_CVALUE(real64, symbol,  GET_CVALUE(real64, symbol->value));

   444

	}

   445

	return NULL;

   446

}

   447

   448

   449

void *constant_folding_c::visit(bit_string_literal_c *symbol) {

   450

	return NULL;

   451

}

   452

   453

   454

void *constant_folding_c::visit(boolean_literal_c *symbol) {

   455

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

   456

	if (VALID_CVALUE(bool, symbol->value)) {

   457

		NEW_CVALUE(bool, symbol);

   458

		SET_CVALUE(bool, symbol,  GET_CVALUE(  bool, symbol->value));

   459

	}

   460

	return NULL;

   461

}

   462

   463

   464

void *constant_folding_c::visit(boolean_true_c *symbol) {

   465

	NEW_CVALUE(bool, symbol);

   466

	SET_CVALUE(bool, symbol, true);

   467

	return NULL;

   468

}

   469

   470

   471

void *constant_folding_c::visit(boolean_false_c *symbol) {

   472

	NEW_CVALUE(bool, symbol);

   473

	SET_CVALUE(bool, symbol, false);

   474

	return NULL;

   475

}

   476

   477

   478

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

   479

/* B.3 - Language ST (Structured Text) */

   480

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

   481

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

   482

/* B 3.1 - Expressions */

   483

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

   484

void *constant_folding_c::visit(or_expression_c *symbol) {

   485

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

   486

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

   487

	DO_BIN_OPER(bool,   ||);

   488

	DO_BIN_OPER(uint64, | );

   489

	return NULL;

   490

}

   491

   492

   493

void *constant_folding_c::visit(xor_expression_c *symbol) {

   494

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

   495

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

   496

	DO_BIN_OPER(bool,   ^);

   497

	DO_BIN_OPER(uint64, ^);

   498

	return NULL;

   499

}

   500

   501