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

    35

    36

    37

/* Do constant folding...

    38

 *

    39

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

    40

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

    41

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

    42

 *

    43

 * For example:

    44

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

    45

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

    46

 *       etc...

    47

 *

    48

 *

    49

 * NOTE 1 

    50

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

    51

 *        1 AND 0

    52

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

    53

 *

    54

 *      The same happens with 

    55

 *        1 + 2

    56

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

    57

 *

    58

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

    59

 *        - bool

    60

 *        - uint64

    61

 *        -  int64

    62

 *        - real64

    63

 *

    64

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

    65

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

    66

 *

    67

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

    68

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

    69

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

    70

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

    71

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

    72

 *              * operation assuming each type.

    73

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

    74

 *              * having more than one entry filled in!

    75

 *              **

    76

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

    77

 *                            cs_const_value, // const value is valid

    78

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

    79

 *                          } const_status_t;

    80

 *    

    81

 *             typedef struct {

    82

 *                 const_status_t status;

    83

 *                 real64_t       value; 

    84

 *             } const_value_real64_t;

    85

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

    86

 *             

    87

 *             typedef struct {

    88

 *                 const_status_t status;

    89

 *                 int64_t        value; 

    90

 *             } const_value_int64_t;

    91

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

    92

 *             

    93

 *             typedef struct {

    94

 *                 const_status_t status;

    95

 *                 uint64_t       value; 

    96

 *             } const_value_uint64_t;

    97

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

    98

 *             

    99

 *             typedef struct {

   100

 *                 const_status_t status;

   101

 *                 bool           value; 

   102

 *             } const_value_bool_t;

   103

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

   104

 *

   105

 *

   106

 *

   107

 * NOTE 2 

   108

 *    This file does not print out any error messages!

   109

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

   110

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

   111

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

   112

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

   113

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

   114

 *

   115

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

   116

 *    actuall printing of errors for the print_datatype_errors_c class!

   117

 */

   118

   119

#include "constant_folding.hh"

   120

#include <limits>

   121

#include <math.h> /* required for pow function, and HUGE_VAL, HUGE_VALF, HUGE_VALL */

   122

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

   123

   124

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

   125

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

   126

   127

   128

   129

#ifndef   UINT64_MAX 

   130

  #define UINT64_MAX (std::numeric_limits< uint64_t >::max())

   131

#endif

   132

#ifndef    INT64_MAX 

   133

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

   134

#endif

   135

#ifndef    INT64_MIN

   136

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

   137

#endif

   138

   139

#if    (real64_t  == float)

   140

  #define HUGE_VAL64  HUGE_VALF

   141

#elif  (real64_t  == double)

   142

  #define HUGE_VAL64  HUGE_VAL

   143

#elif  (real64_t  == long_double)

   144

  #define HUGE_VAL64  HUGE_VALL

   145

#else 

   146

  #error Could not determine which data type is being used for real64_t (defined in absyntax.hh). Aborting!

   147

#endif

   148

   149

   150

   151

   152

   153

   154

   155

   156

   157

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

   158

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

   159

   160

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

   161

  if (current_display_error_level >= error_level) {                                                                         \

   162

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

   163

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

   164

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

   165

    fprintf(stderr, __VA_ARGS__);                                                                                           \

   166

    fprintf(stderr, "\n");                                                                                                  \

   167

    error_count++;                                                                                                     \

   168

  }                                                                                                                         \

   169

}

   170

   171

   172

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

   173

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

   174

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

   175

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

   176

    fprintf(stderr, __VA_ARGS__);                                                                                           \

   177

    fprintf(stderr, "\n");                                                                                                  \

   178

    warning_found = true;                                                                                                   \

   179

}

   180

   181

   182

   183

   184

   185

   186

   187

   188

   189

   190

   191

   192

#define NEW_CVALUE(dtype, symbol) \

   193

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

   194

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

   195

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

   196

   197

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

   198

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

   199

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

   200

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

   201

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

   202

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

   203

   204

#define DO_BINARY_OPER(dtype, oper, otype)\

   205

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

   206

		NEW_CVALUE(otype, symbol);                                                                             \

   207

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

   208

	}

   209

   210

#define DO_UNARY_OPER(dtype, oper, arg)\

   211

	if (VALID_CVALUE(dtype, arg)) {                                                                                \

   212

		NEW_CVALUE(dtype, symbol);                                                                             \

   213

		SET_CVALUE(dtype, symbol, oper GET_CVALUE(dtype, arg));                                                \

   214

	}

   215

   216

   217

   218

   219

   220

/* NOTE:

   221

 *   Most of the conditions to detect overflows on signed and unsigned integer operations were adapted from

   222

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

   223

 *   https://www.securecoding.cert.org/confluence/display/seccode/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap

   224

 */

   225

   226

/* NOTE: If at all possible, all overflow tests are done by pre-condition tests, i.e. tests that 

   227

 *       can be run _before_ the operation is executed, and therefore without accessing the result!

   228

 *

   229

 *       The exception is for real/floating point values, that simply test if the result is NaN (not a number).

   230

 */

   231

   232

/* res = a + b */

   233

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

   234

	if (!VALID_CVALUE(uint64, res))

   235

		return;

   236

	/* Test by post-condition: If sum is smaller than either operand => overflow! */

   237

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

   238

	/* Test by pre-condition: If (UINT64_MAX - a) < b => overflow! */

   239

	if ((UINT64_MAX - GET_CVALUE(uint64, a)) < GET_CVALUE(uint64, b))

   240

		SET_OVFLOW(uint64, res);

   241

}

   242

   243

   244

/* res = a - b */

   245

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

   246

	if (!VALID_CVALUE(uint64, res))

   247

		return;

   248

	/* Test by post-condition: If diference is larger than a => overflow! */

   249

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

   250

	/* Test by pre-condition: if b > a => overflow! */

   251

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

   252

		SET_OVFLOW(uint64, res);

   253

}

   254

   255

   256

/* res = a * b */

   257

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

   258

	if (!VALID_CVALUE(uint64, res))

   259

		return;

   260

	/* Test by pre-condition: If (UINT64_MAX / a) < b => overflow! */

   261

	if ((UINT64_MAX / GET_CVALUE(uint64, a)) < GET_CVALUE(uint64, b))

   262

		SET_OVFLOW(uint64, res);

   263

}

   264

   265

   266

/* res = a / b */

   267

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

   268

	if (!VALID_CVALUE(uint64, res))

   269

		return;

   270

	if (GET_CVALUE(uint64, b) == 0) /* division by zero! */

   271

		SET_OVFLOW(uint64, res);

   272

}

   273

   274

   275

/* res = a MOD b */

   276

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

   277

	if (!VALID_CVALUE(uint64, res))

   278

		return;

   279

	/* no overflow condition exists, including division by zero, which IEC 61131-3 considers legal for MOD operation! */

   280

	if (false) 

   281

		SET_OVFLOW(uint64, res);

   282

}

   283

   284

   285

/* res = a + b */

   286

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

   287

	if (!VALID_CVALUE(int64, res))

   288

		return;

   289

	int64_t a = GET_CVALUE(int64, a_ptr);

   290

	int64_t b = GET_CVALUE(int64, b_ptr);

   291

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

   292

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

   293

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

   294

		SET_OVFLOW(int64, res);

   295

}

   296

   297

   298

/* res = a - b */

   299

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

   300

	if (!VALID_CVALUE(int64, res))

   301

		return;

   302

	int64_t a = GET_CVALUE(int64, a_ptr);

   303

	int64_t b = GET_CVALUE(int64, b_ptr);

   304

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

   305

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

   306

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

   307

		SET_OVFLOW(int64, res);

   308

}

   309

   310

   311

/* res = a * b */

   312

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

   313

	if (!VALID_CVALUE(int64, res))

   314

		return;

   315

	int64_t a = GET_CVALUE(int64, a_ptr);

   316

	int64_t b = GET_CVALUE(int64, b_ptr);

   317

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

   318

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

   319

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

   320

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

   321

		SET_OVFLOW(int64, res);

   322

}

   323

   324

   325

/* res = a / b */

   326

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

   327

	if (!VALID_CVALUE(int64, res))

   328

		return;

   329

	int64_t a = GET_CVALUE(int64, a_ptr);

   330

	int64_t b = GET_CVALUE(int64, b_ptr);

   331

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

   332

		SET_OVFLOW(int64, res);

   333

}

   334

   335

   336

/* res = a MOD b */

   337

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

   338

	if (!VALID_CVALUE(int64, res))

   339

		return;

   340

	int64_t a = GET_CVALUE(int64, a_ptr);

   341

	int64_t b = GET_CVALUE(int64, b_ptr);

   342

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

   343

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

   344

	 *

   345

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

   346

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

   347

	 *

   348

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

   349

	 */

   350

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

   351

		SET_OVFLOW(int64, res);

   352

}

   353

   354

   355

/* res = - a */

   356

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

   357

	if (!VALID_CVALUE(int64, res))

   358

		return;

   359

	int64_t a = GET_CVALUE(int64, a_ptr);

   360

	if (a == INT64_MIN)

   361

		SET_OVFLOW(int64, res);

   362

}

   363

   364

   365

   366

static void CHECK_OVERFLOW_real64(symbol_c *res_ptr) {

   367

	if (!VALID_CVALUE(real64, res_ptr))

   368

		return;

   369

	real64_t res = GET_CVALUE(real64, res_ptr);

   370

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

   371

	/* The IEC 61131-3 clearly states in section '2.5.1.5.2 Numerical functions':

   372

	 * "It is an error if the result of evaluation of one of these [numerical] functions exceeds the range of values

   373

	 *  specified for the data type of the function output, or if division by zero is attempted."

   374

	 * For this reason, any operation that has as a result a positive or negative inifinity, is also an error!

   375

	 */

   376

	if ((isnan(res)) || (res == HUGE_VAL64) || (res == -HUGE_VAL64))

   377

		SET_OVFLOW(real64, res_ptr);

   378

}

   379

   380

   381

   382

   383

   384

   385

   386

   387

   388

   389

   390

   391

   392

   393

constant_folding_c::constant_folding_c(symbol_c *symbol) {

   394

    error_count = 0;

   395

    warning_found = false;

   396

    current_display_error_level = 0;

   397

   398

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

   399

    symbol_c null_symbol;

   400

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

   401

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

   402

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

   403

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

   404

                                                   "However, more likely is the possible existance of overflow/underflow errors that are not detected.");

   405

}

   406

   407

   408

constant_folding_c::~constant_folding_c(void) {

   409

}

   410

   411

   412

int constant_folding_c::get_error_count() {

   413

	return error_count;

   414

}

   415

   416

   417

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

   418

/* B 1.2 - Constants */

   419

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

   420

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

   421

/* B 1.2.1 - Numeric Literals */

   422

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

   423

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

   424

	bool overflow;

   425

	NEW_CVALUE(real64, symbol);	SET_CVALUE(real64, symbol, extract_real_value(symbol, &overflow));

   426

	if (overflow) SET_OVFLOW(real64, symbol);

   427

	return NULL;

   428

}

   429

   430

   431

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

   432

	bool overflow;

   433

	NEW_CVALUE( int64, symbol);	SET_CVALUE( int64, symbol, extract_int64_value(symbol, &overflow));

   434

	if (overflow) SET_OVFLOW(int64, symbol);

   435

	NEW_CVALUE(uint64, symbol);	SET_CVALUE(uint64, symbol, extract_uint64_value(symbol, &overflow));

   436

	if (overflow) SET_OVFLOW(uint64, symbol);

   437

	return NULL;

   438

}

   439

   440

   441

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

   442

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

   443

	DO_UNARY_OPER(real64, -, symbol->exp);

   444

	CHECK_OVERFLOW_real64(symbol);

   445

	return NULL;

   446

}

   447

   448

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

   449

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

   450

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

   451

	DO_UNARY_OPER(int64, -, symbol->exp);

   452

	CHECK_OVERFLOW_int64_NEG(symbol, symbol->exp);

   453

	/* NOTE 1: INT64_MIN = -(INT64_MAX + 1)   ---> assuming two's complement representation!!!

   454

	 * NOTE 2: if the user happens to want INT_MIN, that value will first be parsed as a positive integer, before being negated here.

   455

	 * However, the positive value cannot be stored inside an int64! So, in this case, we will get the value from the uint64 cvalue.

   456

	 */

   457

	// if (INT64_MIN == -INT64_MAX - 1) // We do not really need to check that the platform uses two's complement

   458

	if (VALID_CVALUE(uint64, symbol->exp) && (GET_CVALUE(uint64, symbol->exp) == -INT64_MIN)) {

   459

		NEW_CVALUE(int64, symbol); // in principle, if the above condition is true, then no new cvalue was created by DO_UNARY_OPER(). Not that it would be a problem to create a new one!

   460

		SET_CVALUE(int64, symbol, INT64_MIN);

   461

	}

   462

	return NULL;

   463

}

   464

   465

   466

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

   467

	return NULL;

   468

}

   469

   470

   471

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

   472

	return NULL;

   473

}

   474

   475

   476

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

   477

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

   478

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

   479

	return NULL;

   480

}

   481

   482

   483

/*

   484

integer_literal:

   485

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

   486

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

   487

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

   488

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

   489

*/

   490

// SYM_REF2(integer_literal_c, type, value)

   491

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

   492

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

   493

	DO_UNARY_OPER( int64, /* none */, symbol->value);

   494

	DO_UNARY_OPER(uint64, /* none */, symbol->value);

   495

	return NULL;

   496

}

   497