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

/* TODO: 

    36

 *         - Add support for comparison (= and !=) of enumeration literals!

    37

 *              We will need to add another const_value entry to the symbol_c, containing the 

    38

 *              possible enumeration value of the enum constant!

    39

 *              Doing this will allow us to more easily implement a constant_propagation_c later on!

    40

 *

    41

 *         - Add support for comparison (= and !=) of the exact same variable

    42

 *                (e.g. if (int_v = int_v) then ...)

    43

 */

    44

    45

    46

    47

/* Do constant folding...

    48

 *

    49

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

    50

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

    51

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

    52

 *

    53

 * For example:

    54

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

    55

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

    56

 *       etc...

    57

 *

    58

 *

    59

 * NOTE 1 

    60

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

    61

 *        1 AND 0

    62

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

    63

 *

    64

 *      The same happens with 

    65

 *        1 + 2

    66

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

    67

 *

    68

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

    69

 *        - bool

    70

 *        - uint64

    71

 *        -  int64

    72

 *        - real64

    73

 *

    74

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

    75

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

    76

 *

    77

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

    78

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

    79

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

    80

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

    81

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

    82

 *              * operation assuming each type.

    83

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

    84

 *              * having more than one entry filled in!

    85

 *              **

    86

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

    87

 *                            cs_const_value, // const value is valid

    88

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

    89

 *                          } const_status_t;

    90

 *    

    91

 *             typedef struct {

    92

 *                 const_status_t status;

    93

 *                 real64_t       value; 

    94

 *             } const_value_real64_t;

    95

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

    96

 *             

    97

 *             typedef struct {

    98

 *                 const_status_t status;

    99

 *                 int64_t        value; 

   100

 *             } const_value_int64_t;

   101

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

   102

 *             

   103

 *             typedef struct {

   104

 *                 const_status_t status;

   105

 *                 uint64_t       value; 

   106

 *             } const_value_uint64_t;

   107

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

   108

 *             

   109

 *             typedef struct {

   110

 *                 const_status_t status;

   111

 *                 bool           value; 

   112

 *             } const_value_bool_t;

   113

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

   114

 *

   115

 *

   116

 *

   117

 * NOTE 2 

   118

 *    This file does not print out any error messages!

   119

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

   120

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

   121

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

   122

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

   123

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

   124

 *

   125

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

   126

 *    actually printing of errors for the print_datatype_errors_c class!

   127

 *

   128

 * NOTE 3

   129

 *    Constant Folding class is extended with a implementation constant propagation algorithm

   130

 *    by Mario de Sousa.

   131

 *    Main idea is not to implement a general constant propagation algorithm but to reinterpret it

   132

 *    for visitor classes.

   133

 *    We declared a hash map, it contains a variables list linked with current constant values.

   134

 *    During expression evaluation we can retrieve a constant value to symbolic variables getting it from the map.

   135

 *    Also at join source points we use a meet semilattice rules to merge current values between a block

   136

 *    and adjacent block.

   137

 *

   138

 */

   139

   140

#include "constant_folding.hh"

   141

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

   142

   143

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

   144

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

   145

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

   146

   147

#include "../main.hh" // required for uint8_t, real_64_t, ..., and the macros NAN, INFINITY, INT8_MAX, REAL32_MAX, ... */

   148

   149

   150

   151

   152

   153

   154

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

   155

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

   156

   157

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

   158

  if (current_display_error_level >= error_level) {                                                                         \

   159

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

   160

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

   161

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

   162

    fprintf(stderr, __VA_ARGS__);                                                                                           \

   163

    fprintf(stderr, "\n");                                                                                                  \

   164

    error_count++;                                                                                                     \

   165

  }                                                                                                                         \

   166

}

   167

   168

   169

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

   170

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

   171

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

   172

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

   173

    fprintf(stderr, __VA_ARGS__);                                                                                           \

   174

    fprintf(stderr, "\n");                                                                                                  \

   175

    warning_found = true;                                                                                                   \

   176

}

   177

   178

   179

   180

   181

   182

   183

   184

   185

   186

   187

   188

   199

   200

#define ISEQUAL_CVALUE(dtype, symbol1, symbol2) \

   201

	(VALID_CVALUE(dtype, symbol1) && VALID_CVALUE(dtype, symbol2) && (GET_CVALUE(dtype, symbol1) == GET_CVALUE(dtype, symbol2))) 

   202

   203

#define DO_BINARY_OPER(oper_type, operation, res_type, operand1, operand2) {                                              \

   204

	if      (VALID_CVALUE(oper_type, operand1) && VALID_CVALUE(oper_type, operand2))                                  \

   205

		{SET_CVALUE(res_type, symbol, GET_CVALUE(oper_type, operand1) operation GET_CVALUE(oper_type, operand2));}\

   206

	else if (IS_OVFLOW   (oper_type, operand1) || IS_OVFLOW   (oper_type, operand2))                                  \

   207

		{SET_OVFLOW(res_type, symbol);}  /* does it really make sense to set OVFLOW when restype is boolean??  */ \

   208

	else if (IS_NONCONST (oper_type, operand1) || IS_NONCONST (oper_type, operand2))                                  \

   209

		{SET_NONCONST(res_type, symbol);}                                                                         \

   210

}

   211

   212

#define DO_UNARY_OPER(dtype, operation, operand) {                                                                        \

   213

	if      (VALID_CVALUE(dtype, operand))                                                                            \

   214

		{SET_CVALUE(dtype, symbol, operation GET_CVALUE(dtype, operand));}                                        \

   215

	else if (IS_OVFLOW   (dtype, operand))                                                                            \

   216

		{SET_OVFLOW(dtype, symbol);}                                                                              \

   217

	else if (IS_NONCONST (dtype, operand))                                                                            \

   218

		{SET_NONCONST(dtype, symbol);}                                                                            \

   219

}

   220

   221

/* Constant Propagation: Rules for Meet from "Cooper K., Torczon L. - Engineering a Compiler, Second Edition - 2011"

   222

 * at 9.3 Static Single-Assignment Form  page 517

   223

 * - any * undefined = any

   224

 * - any * non_const = non_const

   225

 * - constant * constant = constant  (if equal)

   226

 * - constant * constant = non_const (if not equal)

   227

 */

   228

#define COMPUTE_MEET_SEMILATTICE(dtype, c1, c2, resValue) {\

   233

		} else {\

   235

		}\

   236

}

   237

   239

   240

static map_values_t values;

   241

   242

   243

   244

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

   245

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

   246

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

   247

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

   248

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

   249

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

   250

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

   251

   252

   253

   254

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

   255

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

   256

   *

   257

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

   258

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

   259

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

   260

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

   261

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

   262

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

   263

   *

   264

   * TODO: support platforms (where the compiler will run) in which int64_t is mapped onto int !!

   265

   *       Is this really needed?

   266

   *       Currently, when trying to compile matiec on sych a platform, the C++ compiler will not

   267

   *       find any apropriate matiec_strtoint64() to call, so matiec will not be able to be compiled.

   268

   *       If you need this, you are welcome to fix it yourself...

   269

   */

   270

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

   271

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

   272

   273

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

   274

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

   275

   276

   277

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

   278

/* NOTE: it must ignore underscores! */

   279

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

   280

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

   281

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

   282

 */

   283

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

   284

  int64_t      ret;

   285

  std::string  str = "";

   286

  char        *endptr;

   287

  const char  *value = NULL;

   288

  int          base;

   289

  integer_c         *integer;

   290

  hex_integer_c     *hex_integer;

   291

  octal_integer_c   *octal_integer;

   292

  binary_integer_c  *binary_integer;

   293

   294

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

   295

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

   296

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

   297

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

   298

   else  ERROR;

   299

   300

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

   301

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

   302

   303

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

   304

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

   305

  if (overflow != NULL)

   306

    *overflow = (errno == ERANGE);

   307

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

   308

    ERROR;

   309

   310

  return ret;

   311

}

   312

   313

   314

   315

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

   316

  uint64_t     ret;

   317

  std::string  str = "";

   318

  char        *endptr;

   319

  const char  *value = NULL;

   320

  int          base;

   321

  integer_c         *integer;

   322

  hex_integer_c     *hex_integer;

   323

  octal_integer_c   *octal_integer;

   324

  binary_integer_c  *binary_integer;

   325

   326

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

   327

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

   328

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

   329

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

   330

   else  ERROR;

   331

   332

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

   333

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

   334

   335

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

   336

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

   337

  if (overflow != NULL)

   338

    *overflow = (errno == ERANGE);

   339

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

   340

    ERROR;

   341

   342

  return ret;

   343

}

   344

   345

   346

   347

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

   348

/* NOTE: it must ignore underscores! */

   349

/* From iec_bison.yy

   350

 *  real:

   351

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

   352

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

   353

 *

   354

 * From iec_flex.ll

   355

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

   356

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

   357

 *

   358

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

   359

 * fixed_point		{integer}\.{integer}

   360

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

   361

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

   362

 */

   363

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

   364

  std::string str = "";

   365

  real_c *real_sym;

   366

  fixed_point_c *fixed_point_sym;

   367

  char   *endptr;

   368

  real64_t ret;

   369

   370

  if ((real_sym = dynamic_cast<real_c *>(sym)) != NULL) {

   371

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

   372

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

   373

  }

   374

  else if ((fixed_point_sym = dynamic_cast<fixed_point_c *>(sym)) != NULL) {

   375

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

   376

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

   377

  }

   378

  else ERROR;

   379

   380

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

   381

  #if    (real64_tX  == float)

   382

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

   383

  #elif  (real64_tX  == double)

   384

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

   385

  #elif  (real64_tX  == long_double)

   386

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

   387

  #else 

   388

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

   389

  #endif

   390

  if (overflow != NULL)

   391

    *overflow = (errno == ERANGE);

   392

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

   393

    ERROR;

   394

   395

  return ret;

   396

}

   397

   398

   399

   400

   401

   402

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

   403

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

   404

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

   405

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

   406

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

   407

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

   408

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

   409

   410

   411

/* NOTE:

   412

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

   413

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

   414

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

   415

 */

   416

   417

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

   418

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

   419

 *

   420

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

   421

 */

   422

   423

/* res = a + b */

   424

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

   425

	if (!VALID_CVALUE(uint64, res))

   426

		return;

   427

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

   428

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

   429

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

   430

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

   431

		SET_OVFLOW(uint64, res);

   432

}

   433

   434

   435

/* res = a - b */

   436

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

   437

	if (!VALID_CVALUE(uint64, res))

   438

		return;

   439

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

   440

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

   441

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

   442

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

   443

		SET_OVFLOW(uint64, res);

   444

}

   445

   446

   447

/* res = a * b */

   448

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

   449

	if (!VALID_CVALUE(uint64, res))

   450

		return;

   451

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

   452

	if (0 == GET_CVALUE(uint64, a))

   453

		return; // multiplying by 0 will always result in 0, a valid result!	  

   454

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

   455

		SET_OVFLOW(uint64, res);

   456

}

   457

   458

   459

/* res = a / b */

   460

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

   461

	if (!VALID_CVALUE(uint64, res))

   462

		return;

   463

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

   464

		SET_OVFLOW(uint64, res);

   465

}

   466

   467

   468

/* res = a MOD b */

   469

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

   470

	if (!VALID_CVALUE(uint64, res))

   471

		return;

   472

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

   473

	if (false) 

   474

		SET_OVFLOW(uint64, res);

   475

}

   476

   477

   478

/* res = - a */

   479

static void CHECK_OVERFLOW_uint64_NEG(symbol_c *res, symbol_c *a) {

   480

	/* The only legal operation is res = -0, everything else is an overflow! */

   481

	if (VALID_CVALUE(uint64, a) && (GET_CVALUE(uint64, a) != 0))

   482

		SET_OVFLOW(uint64, res);

   483

}

   484

   485

   486

   487

   488

   489

   490

/* res = a + b */

   491

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

   492

	if (!VALID_CVALUE(int64, res))

   493

		return;

   494

	int64_t a = GET_CVALUE(int64, a_ptr);

   495

	int64_t b = GET_CVALUE(int64, b_ptr);