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

   125

#include <string.h>  /* required for strlen() */

   126

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

   127

#include <errno.h>   /* required for errno */

   128

   129

   130

   131

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

   132

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

   133

   134

   135

   136

#ifndef   UINT64_MAX 

   137

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

   138

#endif

   139

#ifndef    INT64_MAX 

   140

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

   141

#endif

   142

#ifndef    INT64_MIN

   143

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

   144

#endif

   145

   146

#if    (real64_t  == float)

   147

  #define HUGE_VAL64  HUGE_VALF

   148

#elif  (real64_t  == double)

   149

  #define HUGE_VAL64  HUGE_VAL

   150

#elif  (real64_t  == long_double)

   151

  #define HUGE_VAL64  HUGE_VALL

   152

#else 

   153

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

   154

#endif

   155

   156

   157

   158

   159

   160

   161

   162

   163

   164

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

   165

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

   166

   167

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

   168

  if (current_display_error_level >= error_level) {                                                                         \

   169

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

   170

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

   171

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

   172

    fprintf(stderr, __VA_ARGS__);                                                                                           \

   173

    fprintf(stderr, "\n");                                                                                                  \

   174

    error_count++;                                                                                                     \

   175

  }                                                                                                                         \

   176

}

   177

   178

   179

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

   180

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

   181

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

   182

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

   183

    fprintf(stderr, __VA_ARGS__);                                                                                           \

   184

    fprintf(stderr, "\n");                                                                                                  \

   185

    warning_found = true;                                                                                                   \

   186

}

   187

   188

   189

   190

   191

   192

   193

   194

   195

   196

   197

   198

   199

#define NEW_CVALUE(dtype, symbol) \

   200

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

   201

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

   202

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

   203

   204

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

   205

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

   206

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

   207

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

   208

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

   209

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

   210

   211

#define DO_BINARY_OPER(dtype, oper, otype)\

   212

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

   213

		NEW_CVALUE(otype, symbol);                                                                             \

   214

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

   215

	}

   216

   217

#define DO_UNARY_OPER(dtype, oper, arg)\

   218

	if (VALID_CVALUE(dtype, arg)) {                                                                                \

   219

		NEW_CVALUE(dtype, symbol);                                                                             \

   220

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

   221

	}

   222

   223

   224

   225

   226

   227

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

   228

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

   229

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

   230

/***            convert string to numerical value                    ***/

   231

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

   232

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

   233

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

   234

   235

   236

   237

  /* To allow the compiler to be portable, we cannot assume that int64_t is mapped onto long long int,

   238

   * so we cannot call strtoll() and strtoull() in extract_int64() and extract_uint64().

   239

   *

   240

   * So, we create our own strtouint64() and strtoint64() functions.

   241

   * (We actually call them matiec_strtoint64() so they will not clash with any function

   242

   *  that may be added to the standard library in the future).

   243

   * We actually create several of each, and let the compiler choose which is the correct one,

   244

   * by having it resolve the call to the overloaded function. For the C++ compiler to be able

   245

   * to resolve this ambiguity, we need to add a dummy parameter to each function!

   246

   *

   247

   * TODO: support platforms in which int64_t is mapped onto int !! Is this really needed?

   248

   */

   249

static  int64_t matiec_strtoint64 (         long      int *dummy, const char *nptr, char **endptr, int base) {return strtol  (nptr, endptr, base);}

   250

static  int64_t matiec_strtoint64 (         long long int *dummy, const char *nptr, char **endptr, int base) {return strtoll (nptr, endptr, base);}

   251

   252

static uint64_t matiec_strtouint64(unsigned long      int *dummy, const char *nptr, char **endptr, int base) {return strtoul (nptr, endptr, base);}

   253

static uint64_t matiec_strtouint64(unsigned long long int *dummy, const char *nptr, char **endptr, int base) {return strtoull(nptr, endptr, base);}

   254

   255

   256

/* extract the value of an integer from an integer_c object !! */

   257

/* NOTE: it must ignore underscores! */

   258

/* NOTE: To follow the basic structure used throughout the compiler's code, we should really be

   259

 * writing this as a visitor_c (and do away with the dynamic casts!), but since we only have 3 distinct 

   260

 * symbol class types to handle, it is probably easier to read if we write it as a standard function... 

   261

 */

   262

int64_t extract_int64_value(symbol_c *sym, bool *overflow) {

   263

  int64_t      ret;

   264

  std::string  str = "";

   265

  char        *endptr;

   266

  const char  *value;

   267

  int          base;

   268

  integer_c         *integer;

   269

  hex_integer_c     *hex_integer;

   270

  octal_integer_c   *octal_integer;

   271

  binary_integer_c  *binary_integer;

   272

   273

   if       ((integer        = dynamic_cast<integer_c *>(sym))        != NULL) {value = integer       ->value + 0; base = 10;}

   274

   else  if ((hex_integer    = dynamic_cast<hex_integer_c *>(sym))    != NULL) {value = hex_integer   ->value + 3; base = 16;}

   275

   else  if ((octal_integer  = dynamic_cast<octal_integer_c *>(sym))  != NULL) {value = octal_integer ->value + 2; base =  8;}

   276

   else  if ((binary_integer = dynamic_cast<binary_integer_c *>(sym)) != NULL) {value = binary_integer->value + 2; base =  2;}

   277

   else  ERROR;

   278

   279

  for(unsigned int i = 0; i < strlen(value); i++)

   280

    if (value[i] != '_')  str += value[i];

   281

   282

  errno = 0; // since strtoXX() may legally return 0, we must set errno to 0 to detect errors correctly!

   283

  ret = matiec_strtoint64((int64_t *)NULL, str.c_str(), &endptr, base);

   284

  if (overflow != NULL)

   285

    *overflow = (errno == ERANGE);

   286

  if (((errno != 0) && (errno != ERANGE)) || (*endptr != '\0'))

   287

    ERROR;

   288

   289

  return ret;

   290

}

   291

   292

   293

   294

uint64_t extract_uint64_value(symbol_c *sym, bool *overflow) {

   295

  uint64_t     ret;

   296

  std::string  str = "";

   297

  char        *endptr;

   298

  const char  *value;

   299

  int          base;

   300

  integer_c         *integer;

   301

  hex_integer_c     *hex_integer;

   302

  octal_integer_c   *octal_integer;

   303

  binary_integer_c  *binary_integer;

   304

   305

   if       ((integer        = dynamic_cast<integer_c *>(sym))        != NULL) {value = integer       ->value + 0; base = 10;}

   306

   else  if ((hex_integer    = dynamic_cast<hex_integer_c *>(sym))    != NULL) {value = hex_integer   ->value + 3; base = 16;}

   307

   else  if ((octal_integer  = dynamic_cast<octal_integer_c *>(sym))  != NULL) {value = octal_integer ->value + 2; base =  8;}

   308

   else  if ((binary_integer = dynamic_cast<binary_integer_c *>(sym)) != NULL) {value = binary_integer->value + 2; base =  2;}

   309

   else  ERROR;

   310

   311

  for(unsigned int i = 0; i < strlen(value); i++)

   312

    if (value[i] != '_')  str += value[i];

   313

   314

  errno = 0; // since strtoXX() may legally return 0, we must set errno to 0 to detect errors correctly!

   315

  ret = matiec_strtouint64((uint64_t *)NULL, str.c_str(), &endptr, base);

   316

  if (overflow != NULL)

   317

    *overflow = (errno == ERANGE);

   318

  if (((errno != 0) && (errno != ERANGE)) || (*endptr != '\0'))

   319

    ERROR;

   320

   321

  return ret;

   322

}

   323

   324

   325

   326

/* extract the value of a real from an real_c object !! */

   327

/* NOTE: it must ignore underscores! */

   328

/* From iec_bison.yy

   329

 *  real:

   330

 *   real_token		{$$ = new real_c($1, locloc(@$));}

   331

 * | fixed_point_token	{$$ = new real_c($1, locloc(@$));}

   332

 *

   333

 * From iec_flex.ll

   334

 * {real}			{yylval.ID=strdup(yytext); return real_token;}

   335

 * {fixed_point}		{yylval.ID=strdup(yytext); return fixed_point_token;}

   336

 *

   337

 * real		{integer}\.{integer}{exponent}

   338

 * fixed_point		{integer}\.{integer}

   339

 * exponent        [Ee]([+-]?){integer}

   340

 * integer         {digit}((_?{digit})*)

   341

 */

   342

real64_t extract_real_value(symbol_c *sym, bool *overflow) {

   343

  std::string str = "";

   344

  real_c *real_sym;

   345

  char   *endptr;

   346

  real64_t ret;

   347

   348

  if ((real_sym = dynamic_cast<real_c *>(sym)) == NULL) ERROR;

   349

  for(unsigned int i = 0; i < strlen(real_sym->value); i++)

   350

    if (real_sym->value[i] != '_') str += real_sym->value[i];

   351

   352

  errno = 0; // since strtoXX() may legally return 0, we must set errno to 0 to detect errors correctly!

   353

  #if    (real64_t  == float)

   354

    ret = strtof(str.c_str(),  &endptr);

   355

  #elif  (real64_t  == double)

   356

    ret = strtod(str.c_str(),  &endptr);

   357

  #elif  (real64_t  == long_double)

   358

    ret = strtold(str.c_str(), &endptr);

   359

  #else 

   360

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

   361

  #endif

   362

  if (overflow != NULL)

   363

    *overflow = (errno == ERANGE);

   364

  if (((errno != 0) && (errno != ERANGE)) || (*endptr != '\0'))

   365

    ERROR;

   366

   367

  return ret;

   368

}

   369

   370

   371

   372

   373

   374

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

   375

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

   376

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

   377

/***        Functions to check for overflow situation                ***/

   378

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

   379

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

   380

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

   381

   382

   383

/* NOTE:

   384

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

   385

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

   386

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

   387

 */

   388

   389

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

   390

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

   391

 *

   392

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

   393

 */

   394

   395

/* res = a + b */

   396

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

   397

	if (!VALID_CVALUE(uint64, res))

   398

		return;

   399

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

   400

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

   401

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

   402

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

   403

		SET_OVFLOW(uint64, res);

   404

}

   405

   406

   407

/* res = a - b */

   408

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

   409

	if (!VALID_CVALUE(uint64, res))

   410

		return;

   411

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

   412

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

   413

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

   414

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

   415

		SET_OVFLOW(uint64, res);

   416

}

   417

   418

   419

/* res = a * b */

   420

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

   421

	if (!VALID_CVALUE(uint64, res))

   422

		return;

   423

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

   424

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

   425

		SET_OVFLOW(uint64, res);

   426

}

   427

   428

   429

/* res = a / b */

   430

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

   431

	if (!VALID_CVALUE(uint64, res))

   432

		return;

   433

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

   434

		SET_OVFLOW(uint64, res);

   435

}

   436

   437

   438

/* res = a MOD b */

   439

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

   440

	if (!VALID_CVALUE(uint64, res))

   441

		return;

   442

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

   443

	if (false) 

   444

		SET_OVFLOW(uint64, res);

   445

}

   446

   447

   448

/* res = a + b */

   449

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

   450

	if (!VALID_CVALUE(int64, res))

   451

		return;

   452

	int64_t a = GET_CVALUE(int64, a_ptr);

   453

	int64_t b = GET_CVALUE(int64, b_ptr);

   454

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

   455

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

   456

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

   457

		SET_OVFLOW(int64, res);

   458

}

   459

   460

   461

/* res = a - b */

   462

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

   463

	if (!VALID_CVALUE(int64, res))

   464

		return;

   465

	int64_t a = GET_CVALUE(int64, a_ptr);

   466

	int64_t b = GET_CVALUE(int64, b_ptr);

   467

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

   468

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

   469

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

   470

		SET_OVFLOW(int64, res);

   471

}

   472

   473

   474

/* res = a * b */

   475

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

   476

	if (!VALID_CVALUE(int64, res))

   477

		return;

   478

	int64_t a = GET_CVALUE(int64, a_ptr);

   479

	int64_t b = GET_CVALUE(int64, b_ptr);

   480

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

   481

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

   482

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

   483

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

   484

		SET_OVFLOW(int64, res);

   485

}

   486

   487

   488

/* res = a / b */

   489

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

   490

	if (!VALID_CVALUE(int64, res))

   491

		return;

   492

	int64_t a = GET_CVALUE(int64, a_ptr);

   493

	int64_t b = GET_CVALUE(int64, b_ptr);

   494

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

   495

		SET_OVFLOW(int64, res);

   496

}