nsz Git - libfirm/blob - ir/tv/tv.c

   1 /*
   2  * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Representation of and static computations on target machine
  23  *           values.
  24  * @date     2003
  25  * @author   Mathias Heil
  26  * @version  $Id$
  27  * @brief
  28  *
  29  * Values are stored in a format depending upon chosen arithmetic
  30  * module. Default uses strcalc and fltcalc.
  31  * This implementation assumes:
  32  *  - target has IEEE-754 floating-point arithmetic.
  33  */
  34 #include "config.h"
  35
  36 #include <assert.h>
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include <stdlib.h>
  40 #include <strings.h>
  41
  42 #include "bitfiddle.h"
  43 #include "tv_t.h"
  44 #include "set.h"
  45 #include "entity_t.h"
  46 #include "irmode_t.h"
  47 #include "irnode.h"
  48 #include "strcalc.h"
  49 #include "fltcalc.h"
  50 #include "irtools.h"
  51 #include "xmalloc.h"
  52 #include "firm_common.h"
  53 #include "error.h"
  54
  55 /** Size of hash tables.  Should correspond to average number of distinct constant
  56     target values */
  57 #define N_CONSTANTS 2048
  58
  59 /* unused, float to int doesn't work yet */
  60 typedef enum float_to_int_mode {
  61         TRUNCATE,
  62         ROUND
  63 } float_to_int_mode;
  64
  65 static float_to_int_mode current_float_to_int_mode = TRUNCATE;
  66
  67 #define SWITCH_NOINFINITY 0
  68 #define SWITCH_NODENORMALS 0
  69
  70 /****************************************************************************
  71  *   local definitions and macros
  72  ****************************************************************************/
  73 #ifndef NDEBUG
  74 #  define TARVAL_VERIFY(a) tarval_verify((a))
  75 #else
  76 #  define TARVAL_VERIFY(a) ((void)0)
  77 #endif
  78
  79 #define INSERT_TARVAL(tv) ((ir_tarval*)set_insert(tarvals, (tv), sizeof(ir_tarval), hash_tv((tv))))
  80 #define FIND_TARVAL(tv) ((ir_tarval*)set_find(tarvals, (tv), sizeof(ir_tarval), hash_tv((tv))))
  81
  82 #define INSERT_VALUE(val, size) (set_insert(values, (val), size, hash_val((val), size)))
  83 #define FIND_VALUE(val, size) (set_find(values, (val), size, hash_val((val), size)))
  84
  85 #define fail_verify(a) _fail_verify((a), __FILE__, __LINE__)
  86
  87 /** A set containing all existing tarvals. */
  88 static struct set *tarvals = NULL;
  89 /** A set containing all existing values. */
  90 static struct set *values = NULL;
  91
  92 /** The carry flag for SOME operations. -1 means UNDEFINED here */
  93 static int carry_flag = -1;
  94
  95 /** The integer overflow mode. */
  96 static tarval_int_overflow_mode_t int_overflow_mode = TV_OVERFLOW_WRAP;
  97
  98 /** if this is set non-zero, the constant folding for floating point is OFF */
  99 static int no_float = 0;
 100
 101 /** IEEE-754r half precision */
 102 static const ieee_descriptor_t half_desc     = {  5,  10, 0, NORMAL };
 103 /** IEEE-754 single precision */
 104 static const ieee_descriptor_t single_desc   = {  8,  23, 0, NORMAL };
 105 /** IEEE-754 double precision */
 106 static const ieee_descriptor_t double_desc   = { 11,  52, 0, NORMAL };
 107 /** Intel x87 extended precision */
 108 static const ieee_descriptor_t extended_desc = { 15,  63, 1, NORMAL };
 109
 110 /** IEEE-754r quad precision */
 111 static const ieee_descriptor_t quad_desc     = { 15, 112, 0, NORMAL };
 112
 113 /****************************************************************************
 114  *   private functions
 115  ****************************************************************************/
 116 #ifndef NDEBUG
 117 static unsigned hash_val(const void *value, size_t length);
 118 static unsigned hash_tv(ir_tarval *tv);
 119 static void _fail_verify(ir_tarval *tv, const char* file, int line)
 120 {
 121         /* print a memory image of the tarval and throw an assertion */
 122         if (tv)
 123                 panic("%s:%d: Invalid tarval: mode: %F\n value: [%p]", file, line, tv->mode, tv->value);
 124         else
 125                 panic("%s:%d: Invalid tarval (null)", file, line);
 126 }
 127 #ifdef __GNUC__
 128 inline static void tarval_verify(ir_tarval *tv) __attribute__ ((unused));
 129 #endif
 130
 131 inline static void tarval_verify(ir_tarval *tv)
 132 {
 133         assert(tv);
 134         assert(tv->mode);
 135         assert(tv->value);
 136
 137         if ((tv == tarval_bad) || (tv == tarval_undefined)) return;
 138         if ((tv == tarval_b_true) || (tv == tarval_b_false)) return;
 139
 140         if (!FIND_TARVAL(tv)) fail_verify(tv);
 141         if (tv->length > 0 && !FIND_VALUE(tv->value, tv->length)) fail_verify(tv);
 142 }
 143 #endif /* NDEBUG */
 144
 145 /** Hash a tarval. */
 146 static unsigned hash_tv(ir_tarval *tv)
 147 {
 148         return (unsigned)((PTR_TO_INT(tv->value) ^ PTR_TO_INT(tv->mode)) + tv->length);
 149 }
 150
 151 /** Hash a value. Treat it as a byte array. */
 152 static unsigned hash_val(const void *value, size_t length)
 153 {
 154         size_t i;
 155         unsigned hash = 0;
 156
 157         /* scramble the byte - array */
 158         for (i = 0; i < length; ++i) {
 159                 hash += (hash << 5) ^ (hash >> 27) ^ ((char*)value)[i];
 160                 hash += (hash << 11) ^ (hash >> 17);
 161         }
 162
 163         return hash;
 164 }
 165
 166 static int cmp_tv(const void *p1, const void *p2, size_t n)
 167 {
 168         const ir_tarval *tv1 = (const ir_tarval*) p1;
 169         const ir_tarval *tv2 = (const ir_tarval*) p2;
 170         (void) n;
 171
 172         assert(tv1->kind == k_tarval);
 173         assert(tv2->kind == k_tarval);
 174         if (tv1->mode < tv2->mode)
 175                 return -1;
 176         if (tv1->mode > tv2->mode)
 177                 return 1;
 178         if (tv1->length < tv2->length)
 179                 return -1;
 180         if (tv1->length > tv2->length)
 181                 return 1;
 182         if (tv1->value < tv2->value)
 183                 return -1;
 184         if (tv1->value > tv2->value)
 185                 return 1;
 186
 187         return 0;
 188 }
 189
 190 /** finds tarval with value/mode or creates new tarval */
 191 static ir_tarval *get_tarval(const void *value, size_t length, ir_mode *mode)
 192 {
 193         ir_tarval tv;
 194
 195         tv.kind   = k_tarval;
 196         tv.mode   = mode;
 197         tv.length = length;
 198         if (length > 0) {
 199                 /* if there already is such a value, it is returned, else value
 200                  * is copied into the set */
 201                 char *temp = (char*) alloca(length);
 202                 memcpy(temp, value, length);
 203                 if (get_mode_arithmetic(mode) == irma_twos_complement) {
 204                         sign_extend(temp, mode);
 205                 }
 206                 tv.value = INSERT_VALUE(temp, length);
 207         } else {
 208                 tv.value = value;
 209         }
 210         /* if there is such a tarval, it is returned, else tv is copied
 211          * into the set */
 212         return (ir_tarval *)INSERT_TARVAL(&tv);
 213 }
 214
 215 /**
 216  * handle overflow
 217  */
 218 static ir_tarval *get_tarval_overflow(const void *value, size_t length, ir_mode *mode)
 219 {
 220         char *temp;
 221
 222         switch (get_mode_sort(mode)) {
 223         case irms_reference:
 224                 /* addresses always wrap around */
 225                 temp = (char*) alloca(sc_get_buffer_length());
 226                 memcpy(temp, value, sc_get_buffer_length());
 227                 sc_truncate(get_mode_size_bits(mode), temp);
 228                 /* the sc_ module expects that all bits are set ... */
 229                 sign_extend(temp, mode);
 230                 return get_tarval(temp, length, mode);
 231
 232         case irms_int_number:
 233                 if (sc_comp(value, get_mode_max(mode)->value) == 1) {
 234                         switch (tarval_get_integer_overflow_mode()) {
 235                         case TV_OVERFLOW_SATURATE:
 236                                 return get_mode_max(mode);
 237                         case TV_OVERFLOW_WRAP:
 238                                 temp = (char*) alloca(sc_get_buffer_length());
 239                                 memcpy(temp, value, sc_get_buffer_length());
 240                                 sc_truncate(get_mode_size_bits(mode), temp);
 241                                 /* the sc_ module expects that all bits are set ... */
 242                                 sign_extend(temp, mode);
 243                                 return get_tarval(temp, length, mode);
 244                         case TV_OVERFLOW_BAD:
 245                                 return tarval_bad;
 246                         default:
 247                                 return get_tarval(value, length, mode);
 248                         }
 249                 }
 250                 if (sc_comp(value, get_mode_min(mode)->value) == -1) {
 251                         switch (tarval_get_integer_overflow_mode()) {
 252                         case TV_OVERFLOW_SATURATE:
 253                                 return get_mode_min(mode);
 254                         case TV_OVERFLOW_WRAP: {
 255                                 char *temp = (char*) alloca(sc_get_buffer_length());
 256                                 memcpy(temp, value, sc_get_buffer_length());
 257                                 sc_truncate(get_mode_size_bits(mode), temp);
 258                                 return get_tarval(temp, length, mode);
 259                         }
 260                         case TV_OVERFLOW_BAD:
 261                                 return tarval_bad;
 262                         default:
 263                                 return get_tarval(value, length, mode);
 264                         }
 265                 }
 266                 break;
 267
 268         case irms_float_number:
 269 #ifdef SWITCH_NOINFINITY
 270                 if (fc_is_inf((const fp_value*) value)) {
 271                         /* clip infinity to maximum value */
 272                         return fc_is_negative((const fp_value*) value) ? get_mode_min(mode) : get_mode_max(mode);
 273                 }
 274 #endif
 275
 276 #ifdef SWITCH_NODENORMALS
 277                 if (fc_is_subnormal((const fp_value*) value)) {
 278                         /* clip denormals to zero */
 279                         return get_mode_null(mode);
 280                 }
 281 #endif
 282                 break;
 283
 284         default:
 285                 break;
 286         }
 287         return get_tarval(value, length, mode);
 288 }
 289
 290 /*
 291  *   public variables declared in tv.h
 292  */
 293 static ir_tarval reserved_tv[6];
 294
 295 ir_tarval *tarval_b_false     = &reserved_tv[0];
 296 ir_tarval *tarval_b_true      = &reserved_tv[1];
 297 ir_tarval *tarval_bad         = &reserved_tv[2];
 298 ir_tarval *tarval_undefined   = &reserved_tv[3];
 299 ir_tarval *tarval_reachable   = &reserved_tv[4];
 300 ir_tarval *tarval_unreachable = &reserved_tv[5];
 301
 302 /**
 303  * get the float descriptor for given mode.
 304  */
 305 static const ieee_descriptor_t *get_descriptor(const ir_mode *mode)
 306 {
 307         switch (get_mode_size_bits(mode)) {
 308         case 16:  return &half_desc;
 309         case 32:  return &single_desc;
 310         case 64:  return &double_desc;
 311         case 80:
 312         case 96:
 313         case 128: return &extended_desc; /* FIXME: HACK for x86 where we have
 314                                                                                 sizeof(long double)==16 with 10 byte
 315                                                                                 real payload */
 316         /* case 128: return &quad_desc; */
 317         default:
 318                 panic("Unsupported mode in get_descriptor()");
 319         }
 320 }
 321
 322 ir_tarval *new_integer_tarval_from_str(const char *str, size_t len, char sign,
 323                                        unsigned char base, ir_mode *mode)
 324 {
 325         void *buffer;
 326         int   ok;
 327
 328         buffer = alloca(sc_get_buffer_length());
 329
 330         ok = sc_val_from_str(sign, base, str, len, buffer);
 331         if (!ok)
 332                 return tarval_bad;
 333
 334         return get_tarval_overflow(buffer, sc_get_buffer_length(), mode);
 335 }
 336
 337 static ir_tarval *new_tarval_from_str_int(const char *str, size_t len,
 338                                           ir_mode *mode)
 339 {
 340         void    *buffer;
 341         unsigned base = 10;
 342         char     sign = 1;
 343         int      ok;
 344
 345         /* skip leading spaces */
 346         while (len > 0 && str[0] == ' ') {
 347                 ++str;
 348                 --len;
 349         }
 350         if (len == 0)
 351                 return tarval_bad;
 352
 353         /* 1 sign character allowed */
 354         if (str[0] == '-') {
 355                 sign = -1;
 356                 ++str;
 357                 --len;
 358         } else if (str[0] == '+') {
 359                 ++str;
 360                 --len;
 361         }
 362
 363         /* a number starting with '0x' is hexadeciaml,
 364          * a number starting with '0' (and at least 1 more char) is octal */
 365         if (len >= 2 && str[0] == '0') {
 366                 if (str[1] == 'x' || str[1] == 'X') {
 367                         str += 2;
 368                         len -= 2;
 369                         base = 16;
 370                 } else {
 371                         ++str;
 372                         --len;
 373                         base = 8;
 374                 }
 375         }
 376         if (len == 0)
 377                 return tarval_bad;
 378
 379         buffer = alloca(sc_get_buffer_length());
 380
 381         ok = sc_val_from_str(sign, base, str, len, buffer);
 382         if (!ok)
 383                 return tarval_bad;
 384
 385         return get_tarval_overflow(buffer, sc_get_buffer_length(), mode);
 386 }
 387
 388 /*
 389  * Constructors =============================================================
 390  */
 391 ir_tarval *new_tarval_from_str(const char *str, size_t len, ir_mode *mode)
 392 {
 393         const ieee_descriptor_t *desc;
 394
 395         assert(str);
 396         assert(len);
 397         assert(mode);
 398
 399         switch (get_mode_sort(mode)) {
 400         case irms_control_flow:
 401         case irms_memory:
 402         case irms_auxiliary:
 403                 panic("Unsupported tarval creation with mode %F", mode);
 404
 405         case irms_internal_boolean:
 406                 /* match [tT][rR][uU][eE]|[fF][aA][lL][sS][eE] */
 407                 if (!strcasecmp(str, "true"))
 408                         return tarval_b_true;
 409                 else if (!strcasecmp(str, "false"))
 410                         return tarval_b_false;
 411                 else
 412                         /* XXX This is C semantics */
 413                         return atoi(str) ? tarval_b_true : tarval_b_false;
 414
 415         case irms_float_number:
 416                 desc = get_descriptor(mode);
 417                 fc_val_from_str(str, len, desc, NULL);
 418                 return get_tarval(fc_get_buffer(), fc_get_buffer_length(), mode);
 419
 420         case irms_reference:
 421                 if (!strcasecmp(str, "null"))
 422                         return get_tarval_null(mode);
 423                 /* FALLTHROUGH */
 424         case irms_int_number:
 425                 return new_tarval_from_str_int(str, len, mode);
 426         }
 427         panic("Unsupported tarval creation with mode %F", mode);
 428 }
 429
 430 /*
 431  * helper function, create a tarval from long
 432  */
 433 ir_tarval *new_tarval_from_long(long l, ir_mode *mode)
 434 {
 435         assert(mode);
 436
 437         switch (get_mode_sort(mode))   {
 438         case irms_internal_boolean:
 439                 /* XXX C semantics ! */
 440                 return l ? tarval_b_true : tarval_b_false ;
 441
 442         case irms_reference:
 443                 /* same as integer modes */
 444         case irms_int_number:
 445                 sc_val_from_long(l, NULL);
 446                 return get_tarval(sc_get_buffer(), sc_get_buffer_length(), mode);
 447
 448         case irms_float_number:
 449                 return new_tarval_from_double((long double)l, mode);
 450
 451         default:
 452                 panic("unsupported mode sort");
 453         }
 454 }
 455
 456 /* returns non-zero if can be converted to long */
 457 int tarval_is_long(ir_tarval *tv)
 458 {
 459         if (!mode_is_int(tv->mode) && !mode_is_reference(tv->mode))
 460                 return 0;
 461
 462         if (get_mode_size_bits(tv->mode) > (int) (sizeof(long) << 3)) {
 463                 /* the value might be too big to fit in a long */
 464                 sc_max_from_bits(sizeof(long) << 3, 0, NULL);
 465                 if (sc_comp(sc_get_buffer(), tv->value) == -1) {
 466                         /* really doesn't fit */
 467                         return 0;
 468                 }
 469         }
 470         return 1;
 471 }
 472
 473 /* this might overflow the machine's long, so use only with small values */
 474 long get_tarval_long(ir_tarval* tv)
 475 {
 476         assert(tarval_is_long(tv) && "tarval too big to fit in long");
 477
 478         return sc_val_to_long(tv->value);
 479 }
 480
 481 ir_tarval *new_tarval_from_long_double(long double d, ir_mode *mode)
 482 {
 483         const ieee_descriptor_t *desc;
 484
 485         assert(mode && (get_mode_sort(mode) == irms_float_number));
 486         desc = get_descriptor(mode);
 487         fc_val_from_ieee754(d, desc, NULL);
 488         return get_tarval(fc_get_buffer(), fc_get_buffer_length(), mode);
 489 }
 490
 491 ir_tarval *new_tarval_from_double(double d, ir_mode *mode)
 492 {
 493         return new_tarval_from_long_double(d, mode);
 494 }
 495
 496 /* returns non-zero if can be converted to double */
 497 int tarval_is_double(ir_tarval *tv)
 498 {
 499         assert(tv);
 500
 501         return (get_mode_sort(tv->mode) == irms_float_number);
 502 }
 503
 504 long double get_tarval_long_double(ir_tarval *tv)
 505 {
 506         assert(tarval_is_double(tv));
 507
 508         return fc_val_to_ieee754((const fp_value*) tv->value);
 509 }
 510
 511 double get_tarval_double(ir_tarval *tv)
 512 {
 513         return get_tarval_long_double(tv);
 514 }
 515
 516
 517 /*
 518  * Access routines for tarval fields ========================================
 519  */
 520
 521 /* get the mode of the tarval */
 522 ir_mode *(get_tarval_mode)(const ir_tarval *tv)
 523 {
 524         return _get_tarval_mode(tv);
 525 }
 526
 527 /*
 528  * Special value query functions ============================================
 529  *
 530  * These functions calculate and return a tarval representing the requested
 531  * value.
 532  * The functions get_mode_{Max,Min,...} return tarvals retrieved from these
 533  * functions, but these are stored on initialization of the irmode module and
 534  * therefore the irmode functions should be preferred to the functions below.
 535  */
 536
 537 ir_tarval *(get_tarval_bad)(void)
 538 {
 539         return _get_tarval_bad();
 540 }
 541
 542 ir_tarval *(get_tarval_undefined)(void)
 543 {
 544         return _get_tarval_undefined();
 545 }
 546
 547 ir_tarval *(get_tarval_b_false)(void)
 548 {
 549         return _get_tarval_b_false();
 550 }
 551
 552 ir_tarval *(get_tarval_b_true)(void)
 553 {
 554         return _get_tarval_b_true();
 555 }
 556
 557 ir_tarval *(get_tarval_reachable)(void)
 558 {
 559         return _get_tarval_reachable();
 560 }
 561
 562 ir_tarval *(get_tarval_unreachable)(void)
 563 {
 564         return _get_tarval_unreachable();
 565 }
 566
 567 ir_tarval *get_tarval_max(ir_mode *mode)
 568 {
 569         const ieee_descriptor_t *desc;
 570
 571         assert(mode);
 572         if (get_mode_n_vector_elems(mode) > 1) {
 573                 /* vector arithmetic not implemented yet */
 574                 return tarval_bad;
 575         }
 576
 577         switch (get_mode_sort(mode)) {
 578         case irms_control_flow:
 579         case irms_memory:
 580         case irms_auxiliary:
 581                 panic("mode %F does not support maximum value", mode);
 582
 583         case irms_internal_boolean:
 584                 return tarval_b_true;
 585
 586         case irms_float_number:
 587                 desc = get_descriptor(mode);
 588                 fc_get_max(desc, NULL);
 589                 return get_tarval(fc_get_buffer(), fc_get_buffer_length(), mode);
 590
 591         case irms_reference:
 592         case irms_int_number:
 593                 sc_max_from_bits(get_mode_size_bits(mode), mode_is_signed(mode), NULL);
 594                 return get_tarval(sc_get_buffer(), sc_get_buffer_length(), mode);
 595         }
 596         return tarval_bad;
 597 }
 598
 599 ir_tarval *get_tarval_min(ir_mode *mode)
 600 {
 601         const ieee_descriptor_t *desc;
 602
 603         assert(mode);
 604         if (get_mode_n_vector_elems(mode) > 1) {
 605                 /* vector arithmetic not implemented yet */
 606                 return tarval_bad;
 607         }
 608
 609         switch (get_mode_sort(mode)) {
 610         case irms_control_flow:
 611         case irms_memory:
 612         case irms_auxiliary:
 613                 panic("mode %F does not support minimum value", mode);
 614
 615         case irms_internal_boolean:
 616                 return tarval_b_false;
 617
 618         case irms_float_number:
 619                 desc = get_descriptor(mode);
 620                 fc_get_min(desc, NULL);
 621                 return get_tarval(fc_get_buffer(), fc_get_buffer_length(), mode);
 622
 623         case irms_reference:
 624         case irms_int_number:
 625                 sc_min_from_bits(get_mode_size_bits(mode), mode_is_signed(mode), NULL);
 626                 return get_tarval(sc_get_buffer(), sc_get_buffer_length(), mode);
 627         }
 628         return tarval_bad;
 629 }
 630
 631 /** The bit pattern for the pointer NULL */
 632 static long _null_value = 0;
 633
 634 ir_tarval *get_tarval_null(ir_mode *mode)
 635 {
 636         assert(mode);
 637
 638         if (get_mode_n_vector_elems(mode) > 1) {
 639                 /* vector arithmetic not implemented yet */
 640                 return tarval_bad;
 641         }
 642
 643         switch (get_mode_sort(mode)) {
 644         case irms_control_flow:
 645         case irms_memory:
 646         case irms_auxiliary:
 647                 panic("mode %F does not support null value", mode);
 648
 649         case irms_float_number:
 650                 return new_tarval_from_double(0.0, mode);
 651
 652         case irms_internal_boolean:
 653         case irms_int_number:
 654                 return new_tarval_from_long(0l,  mode);
 655
 656         case irms_reference:
 657                 return new_tarval_from_long(_null_value, mode);
 658         }
 659         return tarval_bad;
 660 }
 661
 662 ir_tarval *get_tarval_one(ir_mode *mode)
 663 {
 664         assert(mode);
 665
 666         if (get_mode_n_vector_elems(mode) > 1)
 667                 panic("vector arithmetic not implemented yet");
 668
 669         switch (get_mode_sort(mode)) {
 670         case irms_control_flow:
 671         case irms_memory:
 672         case irms_auxiliary:
 673                 panic("mode %F does not support one value", mode);
 674
 675         case irms_internal_boolean:
 676                 return tarval_b_true;
 677
 678         case irms_float_number:
 679                 return new_tarval_from_double(1.0, mode);
 680
 681         case irms_reference:
 682         case irms_int_number:
 683                 return new_tarval_from_long(1l, mode);
 684         }
 685         return tarval_bad;
 686 }
 687
 688 ir_tarval *get_tarval_all_one(ir_mode *mode)
 689 {
 690         assert(mode);
 691
 692         if (get_mode_n_vector_elems(mode) > 1)
 693                 panic("vector arithmetic not implemented yet");
 694
 695         switch (get_mode_sort(mode)) {
 696         case irms_control_flow:
 697         case irms_memory:
 698         case irms_auxiliary:
 699                 panic("mode %F does not support all-one value", mode);
 700
 701         case irms_int_number:
 702         case irms_internal_boolean:
 703         case irms_reference:
 704                 return tarval_not(get_mode_null(mode));
 705
 706
 707         case irms_float_number:
 708                 return new_tarval_from_double(1.0, mode);
 709         }
 710         return tarval_bad;
 711 }
 712
 713 int tarval_is_constant(ir_tarval *tv)
 714 {
 715         int num_res = sizeof(reserved_tv) / sizeof(reserved_tv[0]);
 716
 717         /* reserved tarvals are NOT constants. Note that although
 718            tarval_b_true and tarval_b_false are reserved, they are constants of course. */
 719         return (tv < &reserved_tv[2] || tv > &reserved_tv[num_res - 1]);
 720 }
 721
 722 ir_tarval *get_tarval_minus_one(ir_mode *mode)
 723 {
 724         assert(mode);
 725
 726         if (get_mode_n_vector_elems(mode) > 1)
 727                 panic("vector arithmetic not implemented yet");
 728
 729         switch (get_mode_sort(mode)) {
 730         case irms_control_flow:
 731         case irms_memory:
 732         case irms_auxiliary:
 733         case irms_internal_boolean:
 734                 panic("mode %F does not support minus one value", mode);
 735
 736         case irms_reference:
 737                 return tarval_bad;
 738
 739         case irms_float_number:
 740                 return mode_is_signed(mode) ? new_tarval_from_double(-1.0, mode) : tarval_bad;
 741
 742         case irms_int_number:
 743                 return new_tarval_from_long(-1l, mode);
 744         }
 745         return tarval_bad;
 746 }
 747
 748 ir_tarval *get_tarval_nan(ir_mode *mode)
 749 {
 750         const ieee_descriptor_t *desc;
 751
 752         assert(mode);
 753         if (get_mode_n_vector_elems(mode) > 1)
 754                 panic("vector arithmetic not implemented yet");
 755
 756         if (get_mode_sort(mode) == irms_float_number) {
 757                 desc = get_descriptor(mode);
 758                 fc_get_qnan(desc, NULL);
 759                 return get_tarval(fc_get_buffer(), fc_get_buffer_length(), mode);
 760         } else
 761                 panic("mode %F does not support NaN value", mode);
 762 }
 763
 764 ir_tarval *get_tarval_plus_inf(ir_mode *mode)
 765 {
 766         assert(mode);
 767         if (get_mode_n_vector_elems(mode) > 1)
 768                 panic("vector arithmetic not implemented yet");
 769
 770         if (get_mode_sort(mode) == irms_float_number) {
 771                 const ieee_descriptor_t *desc = get_descriptor(mode);
 772                 fc_get_plusinf(desc, NULL);
 773                 return get_tarval(fc_get_buffer(), fc_get_buffer_length(), mode);
 774         } else
 775                 panic("mode %F does not support +inf value", mode);
 776 }
 777
 778 ir_tarval *get_tarval_minus_inf(ir_mode *mode)
 779 {
 780         assert(mode);
 781
 782         if (get_mode_n_vector_elems(mode) > 1)
 783                 panic("vector arithmetic not implemented yet");
 784
 785         if (get_mode_sort(mode) == irms_float_number) {
 786                 const ieee_descriptor_t *desc = get_descriptor(mode);
 787                 fc_get_minusinf(desc, NULL);
 788                 return get_tarval(fc_get_buffer(), fc_get_buffer_length(), mode);
 789         } else
 790                 panic("mode %F does not support -inf value", mode);
 791 }
 792
 793 /*
 794  * Arithmetic operations on tarvals ========================================
 795  */
 796
 797 /*
 798  * test if negative number, 1 means 'yes'
 799  */
 800 int tarval_is_negative(ir_tarval *a)
 801 {
 802         if (get_mode_n_vector_elems(a->mode) > 1)
 803                 panic("vector arithmetic not implemented yet");
 804
 805         switch (get_mode_sort(a->mode)) {
 806         case irms_int_number:
 807                 if (!mode_is_signed(a->mode)) return 0;
 808                 else
 809                         return sc_comp(a->value, get_mode_null(a->mode)->value) == -1 ? 1 : 0;
 810
 811         case irms_float_number:
 812                 return fc_is_negative((const fp_value*) a->value);
 813
 814         default:
 815                 panic("mode %F does not support negation value", a->mode);
 816         }
 817 }
 818
 819 /*
 820  * test if null, 1 means 'yes'
 821  */
 822 int tarval_is_null(ir_tarval *a)
 823 {
 824         return
 825                 a != tarval_bad &&
 826                 a == get_mode_null(get_tarval_mode(a));
 827 }
 828
 829 /*
 830  * test if one, 1 means 'yes'
 831  */
 832 int tarval_is_one(ir_tarval *a)
 833 {
 834         return
 835                 a != tarval_bad &&
 836                 a == get_mode_one(get_tarval_mode(a));
 837 }
 838
 839 int tarval_is_all_one(ir_tarval *tv)
 840 {
 841         return
 842                 tv != tarval_bad &&
 843                 tv == get_mode_all_one(get_tarval_mode(tv));
 844 }
 845
 846 /*
 847  * test if one, 1 means 'yes'
 848  */
 849 int tarval_is_minus_one(ir_tarval *a)
 850 {
 851         return
 852                 a != tarval_bad &&
 853                 a == get_mode_minus_one(get_tarval_mode(a));
 854 }
 855
 856 /*
 857  * comparison
 858  */
 859 ir_relation tarval_cmp(ir_tarval *a, ir_tarval *b)
 860 {
 861         carry_flag = -1;
 862
 863         if (a == tarval_bad || b == tarval_bad) {
 864                 panic("Comparison with tarval_bad");
 865         }
 866
 867         if (a == tarval_undefined || b == tarval_undefined)
 868                 return ir_relation_false;
 869
 870         if (a->mode != b->mode)
 871                 return ir_relation_false;
 872
 873         if (get_mode_n_vector_elems(a->mode) > 1) {
 874                 /* vector arithmetic not implemented yet */
 875                 panic("cmp not implemented for vector modes");
 876         }
 877
 878         /* Here the two tarvals are unequal and of the same mode */
 879         switch (get_mode_sort(a->mode)) {
 880         case irms_control_flow:
 881         case irms_memory:
 882         case irms_auxiliary:
 883                 if (a == b)
 884                         return ir_relation_equal;
 885                 return ir_relation_false;
 886
 887         case irms_float_number:
 888                 /*
 889                  * BEWARE: we cannot compare a == b here, because
 890                  * a NaN is always Unordered to any other value, even to itself!
 891                  */
 892                 switch (fc_comp((const fp_value*) a->value, (const fp_value*) b->value)) {
 893                 case -1: return ir_relation_less;
 894                 case  0: return ir_relation_equal;
 895                 case  1: return ir_relation_greater;
 896                 case  2: return ir_relation_unordered;
 897                 default: return ir_relation_false;
 898                 }
 899         case irms_reference:
 900         case irms_int_number:
 901                 if (a == b)
 902                         return ir_relation_equal;
 903                 return sc_comp(a->value, b->value) == 1 ? ir_relation_greater : ir_relation_less;
 904
 905         case irms_internal_boolean:
 906                 if (a == b)
 907                         return ir_relation_equal;
 908                 return a == tarval_b_true ? ir_relation_greater : ir_relation_less;
 909         }
 910         return ir_relation_false;
 911 }
 912
 913 /*
 914  * convert to other mode
 915  */
 916 ir_tarval *tarval_convert_to(ir_tarval *src, ir_mode *dst_mode)
 917 {
 918         char                    *buffer;
 919         fp_value                *res = NULL;
 920         const ieee_descriptor_t *desc;
 921         int                      len;
 922
 923         carry_flag = -1;
 924
 925         assert(src);
 926         assert(dst_mode);
 927
 928         if (src->mode == dst_mode)
 929                 return src;
 930
 931         if (get_mode_n_vector_elems(src->mode) > 1) {
 932                 /* vector arithmetic not implemented yet */
 933                 return tarval_bad;
 934         }
 935
 936         switch (get_mode_sort(src->mode)) {
 937         case irms_control_flow:
 938         case irms_memory:
 939         case irms_auxiliary:
 940                 break;
 941
 942                 /* cast float to something */
 943         case irms_float_number:
 944                 switch (get_mode_sort(dst_mode)) {
 945                 case irms_float_number:
 946                         desc = get_descriptor(dst_mode);
 947                         fc_cast((const fp_value*) src->value, desc, NULL);
 948                         return get_tarval(fc_get_buffer(), fc_get_buffer_length(), dst_mode);
 949
 950                 case irms_int_number:
 951                         switch (current_float_to_int_mode) {
 952                         case TRUNCATE:
 953                                 res = fc_int((const fp_value*) src->value, NULL);
 954                                 break;
 955                         case ROUND:
 956                                 res = fc_rnd((const fp_value*) src->value, NULL);
 957                                 break;
 958                         }
 959                         buffer = (char*) alloca(sc_get_buffer_length());
 960                         if (! fc_flt2int(res, buffer, dst_mode))
 961                                 return tarval_bad;
 962                         return get_tarval(buffer, sc_get_buffer_length(), dst_mode);
 963
 964                 default:
 965                         /* the rest can't be converted */
 966                         return tarval_bad;
 967                 }
 968                 break;
 969
 970         /* cast int/characters to something */
 971         case irms_int_number:
 972                 switch (get_mode_sort(dst_mode)) {
 973
 974                 case irms_reference:
 975                 case irms_int_number:
 976                         buffer = (char*) alloca(sc_get_buffer_length());
 977                         memcpy(buffer, src->value, sc_get_buffer_length());
 978                         sign_extend(buffer, dst_mode);
 979                         return get_tarval_overflow(buffer, src->length, dst_mode);
 980
 981                 case irms_internal_boolean:
 982                         /* XXX C semantics */
 983                         if (src == get_mode_null(src->mode)) return tarval_b_false;
 984                         else return tarval_b_true;
 985
 986                 case irms_float_number:
 987                         /* XXX floating point unit does not understand internal integer
 988                          * representation, convert to string first, then create float from
 989                          * string */
 990                         buffer = (char*) alloca(100);
 991                         /* decimal string representation because hexadecimal output is
 992                          * interpreted unsigned by fc_val_from_str, so this is a HACK */
 993                         len = snprintf(buffer, 100, "%s",
 994                                 sc_print(src->value, get_mode_size_bits(src->mode), SC_DEC, mode_is_signed(src->mode)));
 995                         buffer[100 - 1] = '\0';
 996                         desc = get_descriptor(dst_mode);
 997                         fc_val_from_str(buffer, len, desc, NULL);
 998                         return get_tarval(fc_get_buffer(), fc_get_buffer_length(), dst_mode);
 999
1000                 default:
1001                         break;
1002                 }
1003                 break;
1004
1005         case irms_internal_boolean:
1006                 /* beware: this is C semantic for the INTERNAL boolean mode */
1007                 if (get_mode_sort(dst_mode) == irms_int_number)
1008                         return src == tarval_b_true ? get_mode_one(dst_mode) : get_mode_null(dst_mode);
1009                 break;
1010
1011         case irms_reference:
1012                 if (get_mode_sort(dst_mode) == irms_int_number) {
1013                         buffer = (char*) alloca(sc_get_buffer_length());
1014                         memcpy(buffer, src->value, sc_get_buffer_length());
1015                         sign_extend(buffer, src->mode);
1016                         return get_tarval_overflow(buffer, src->length, dst_mode);
1017                 }
1018                 break;
1019         }
1020
1021         return tarval_bad;
1022 }
1023
1024 /*
1025  * bitwise negation
1026  */
1027 ir_tarval *tarval_not(ir_tarval *a)
1028 {
1029         char *buffer;
1030
1031         carry_flag = -1;
1032
1033         /* works for vector mode without changes */
1034
1035         switch (get_mode_sort(a->mode)) {
1036         case irms_reference:
1037         case irms_int_number:
1038                 buffer = (char*) alloca(sc_get_buffer_length());
1039                 sc_not(a->value, buffer);
1040                 return get_tarval(buffer, a->length, a->mode);
1041
1042         case irms_internal_boolean:
1043                 if (a == tarval_b_true)
1044                         return tarval_b_false;
1045                 if (a == tarval_b_false)
1046                         return tarval_b_true;
1047                 return tarval_bad;
1048
1049         default:
1050                 panic("bitwise negation is only allowed for integer and boolean");
1051         }
1052 }
1053
1054 /*
1055  * arithmetic negation
1056  */
1057 ir_tarval *tarval_neg(ir_tarval *a)
1058 {
1059         char *buffer;
1060
1061         assert(mode_is_num(a->mode)); /* negation only for numerical values */
1062
1063         carry_flag = -1;
1064
1065         /* note: negation is allowed even for unsigned modes. */
1066
1067         if (get_mode_n_vector_elems(a->mode) > 1) {
1068                 /* vector arithmetic not implemented yet */
1069                 return tarval_bad;
1070         }
1071
1072         switch (get_mode_sort(a->mode)) {
1073         case irms_int_number:
1074                 buffer = (char*) alloca(sc_get_buffer_length());
1075                 sc_neg(a->value, buffer);
1076                 return get_tarval_overflow(buffer, a->length, a->mode);
1077
1078         case irms_float_number:
1079                 /* it should be safe to enable this even if other arithmetic is disabled */
1080                 /*if (no_float)
1081                         return tarval_bad;*/
1082
1083                 fc_neg((const fp_value*) a->value, NULL);
1084                 return get_tarval_overflow(fc_get_buffer(), fc_get_buffer_length(), a->mode);
1085
1086         default:
1087                 return tarval_bad;
1088         }
1089 }
1090
1091 /*
1092  * addition
1093  */
1094 ir_tarval *tarval_add(ir_tarval *a, ir_tarval *b)
1095 {
1096         char *buffer;
1097
1098         carry_flag = -1;
1099
1100         if (get_mode_n_vector_elems(a->mode) > 1 || get_mode_n_vector_elems(b->mode) > 1) {
1101                 /* vector arithmetic not implemented yet */
1102                 return tarval_bad;
1103         }
1104
1105         if (mode_is_reference(a->mode) && a->mode != b->mode) {
1106                 b = tarval_convert_to(b, a->mode);
1107         } else if (mode_is_reference(b->mode) && b->mode != a->mode) {
1108                 a = tarval_convert_to(a, b->mode);
1109         }
1110
1111         assert(a->mode == b->mode);
1112
1113         switch (get_mode_sort(a->mode)) {
1114         case irms_reference:
1115         case irms_int_number:
1116                 /* modes of a,b are equal, so result has mode of a as this might be the character */
1117                 buffer = (char*) alloca(sc_get_buffer_length());
1118                 sc_add(a->value, b->value, buffer);
1119                 carry_flag = sc_get_bit_at(buffer, get_mode_size_bits(a->mode));
1120                 return get_tarval_overflow(buffer, a->length, a->mode);
1121
1122         case irms_float_number:
1123                 if (no_float)
1124                         return tarval_bad;
1125
1126                 fc_add((const fp_value*) a->value, (const fp_value*) b->value, NULL);
1127                 return get_tarval_overflow(fc_get_buffer(), fc_get_buffer_length(), a->mode);
1128
1129         default:
1130                 return tarval_bad;
1131         }
1132 }
1133
1134 /*
1135  * subtraction
1136  */
1137 ir_tarval *tarval_sub(ir_tarval *a, ir_tarval *b, ir_mode *dst_mode)
1138 {
1139         char    *buffer;
1140
1141         carry_flag = -1;
1142
1143         if (get_mode_n_vector_elems(a->mode) > 1 || get_mode_n_vector_elems(b->mode) > 1) {
1144                 /* vector arithmetic not implemented yet */
1145                 return tarval_bad;
1146         }
1147
1148         if (dst_mode != NULL) {
1149                 if (a->mode != dst_mode)
1150                         a = tarval_convert_to(a, dst_mode);
1151                 if (b->mode != dst_mode)
1152                         b = tarval_convert_to(b, dst_mode);
1153         }
1154         assert(a->mode == b->mode);
1155
1156         switch (get_mode_sort(a->mode)) {
1157         case irms_reference:
1158         case irms_int_number:
1159                 /* modes of a,b are equal, so result has mode of a as this might be the character */
1160                 buffer = (char*) alloca(sc_get_buffer_length());
1161                 sc_sub(a->value, b->value, buffer);
1162                 carry_flag = sc_get_bit_at(buffer, get_mode_size_bits(a->mode));
1163                 return get_tarval_overflow(buffer, a->length, a->mode);
1164
1165         case irms_float_number:
1166                 if (no_float)
1167                         return tarval_bad;
1168
1169                 fc_sub((const fp_value*) a->value, (const fp_value*) b->value, NULL);
1170                 return get_tarval_overflow(fc_get_buffer(), fc_get_buffer_length(), a->mode);
1171
1172         default:
1173                 return tarval_bad;
1174         }
1175 }
1176
1177 /*
1178  * multiplication
1179  */
1180 ir_tarval *tarval_mul(ir_tarval *a, ir_tarval *b)
1181 {
1182         char *buffer;
1183
1184         assert(a->mode == b->mode);
1185
1186         carry_flag = -1;
1187
1188         if (get_mode_n_vector_elems(a->mode) > 1) {
1189                 /* vector arithmetic not implemented yet */
1190                 return tarval_bad;
1191         }
1192
1193         switch (get_mode_sort(a->mode)) {
1194         case irms_int_number:
1195                 /* modes of a,b are equal */
1196                 buffer = (char*) alloca(sc_get_buffer_length());
1197                 sc_mul(a->value, b->value, buffer);
1198                 return get_tarval_overflow(buffer, a->length, a->mode);
1199
1200         case irms_float_number:
1201                 if (no_float)
1202                         return tarval_bad;
1203
1204                 fc_mul((const fp_value*) a->value, (const fp_value*) b->value, NULL);
1205                 return get_tarval_overflow(fc_get_buffer(), fc_get_buffer_length(), a->mode);
1206
1207         default:
1208                 return tarval_bad;
1209         }
1210 }
1211
1212 /*
1213  * division
1214  * overflow is impossible, but look out for division by zero
1215  */
1216 ir_tarval *tarval_div(ir_tarval *a, ir_tarval *b)
1217 {
1218         ir_mode *mode = a->mode;
1219         assert(mode == b->mode);
1220
1221         carry_flag = -1;
1222
1223         if (get_mode_n_vector_elems(mode) > 1) {
1224                 /* vector arithmetic not implemented yet */
1225                 return tarval_bad;
1226         }
1227
1228         if (mode_is_int(mode)) {
1229                 /* x/0 error */
1230                 if (b == get_mode_null(mode))
1231                         return tarval_bad;
1232
1233                 /* modes of a,b are equal */
1234                 sc_div(a->value, b->value, NULL);
1235                 return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1236         } else {
1237                 assert(mode_is_float(mode));
1238                 fc_div((const fp_value*) a->value, (const fp_value*) b->value, NULL);
1239                 return get_tarval_overflow(fc_get_buffer(), fc_get_buffer_length(), mode);
1240         }
1241 }
1242
1243 /*
1244  * remainder
1245  * overflow is impossible, but look out for division by zero
1246  */
1247 ir_tarval *tarval_mod(ir_tarval *a, ir_tarval *b)
1248 {
1249         assert((a->mode == b->mode) && mode_is_int(a->mode));
1250
1251         carry_flag = -1;
1252
1253         if (get_mode_n_vector_elems(a->mode) > 1) {
1254                 /* vector arithmetic not implemented yet */
1255                 return tarval_bad;
1256         }
1257
1258         /* x/0 error */
1259         if (b == get_mode_null(b->mode)) return tarval_bad;
1260         /* modes of a,b are equal */
1261         sc_mod(a->value, b->value, NULL);
1262         return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1263 }
1264
1265 /*
1266  * integer division AND remainder
1267  * overflow is impossible, but look out for division by zero
1268  */
1269 ir_tarval *tarval_divmod(ir_tarval *a, ir_tarval *b, ir_tarval **mod)
1270 {
1271         int len = sc_get_buffer_length();
1272         char *div_res = (char*) alloca(len);
1273         char *mod_res = (char*) alloca(len);
1274
1275         assert((a->mode == b->mode) && mode_is_int(a->mode));
1276
1277         carry_flag = -1;
1278
1279         if (get_mode_n_vector_elems(a->mode) > 1) {
1280                 /* vector arithmetic not implemented yet */
1281                 return tarval_bad;
1282         }
1283
1284
1285         /* x/0 error */
1286         if (b == get_mode_null(b->mode)) return tarval_bad;
1287         /* modes of a,b are equal */
1288         sc_divmod(a->value, b->value, div_res, mod_res);
1289         *mod = get_tarval(mod_res, len, a->mode);
1290         return get_tarval(div_res, len, a->mode);
1291 }
1292
1293 /*
1294  * absolute value
1295  */
1296 ir_tarval *tarval_abs(ir_tarval *a)
1297 {
1298         char *buffer;
1299
1300         carry_flag = -1;
1301         assert(mode_is_num(a->mode));
1302
1303         if (get_mode_n_vector_elems(a->mode) > 1) {
1304                 /* vector arithmetic not implemented yet */
1305                 return tarval_bad;
1306         }
1307
1308         switch (get_mode_sort(a->mode)) {
1309         case irms_int_number:
1310                 if (sc_comp(a->value, get_mode_null(a->mode)->value) == -1) {
1311                         buffer = (char*) alloca(sc_get_buffer_length());
1312                         sc_neg(a->value, buffer);
1313                         return get_tarval_overflow(buffer, a->length, a->mode);
1314                 }
1315                 return a;
1316
1317         case irms_float_number:
1318                 /* it should be safe to enable this even if other arithmetic is disabled */
1319                 /*if (no_float)
1320                         return tarval_bad;*/
1321
1322                 if (fc_comp((const fp_value*) a->value,
1323                     (const fp_value*) get_mode_null(a->mode)->value) == -1) {
1324                         fc_neg((const fp_value*) a->value, NULL);
1325                         return get_tarval_overflow(fc_get_buffer(), fc_get_buffer_length(), a->mode);
1326                 }
1327                 return a;
1328
1329         default:
1330                 break;
1331         }
1332         return tarval_bad;
1333 }
1334
1335 /*
1336  * bitwise and
1337  */
1338 ir_tarval *tarval_and(ir_tarval *a, ir_tarval *b)
1339 {
1340         assert(a->mode == b->mode);
1341
1342         /* works even for vector modes */
1343         carry_flag = 0;
1344
1345         switch (get_mode_sort(a->mode)) {
1346         case irms_internal_boolean:
1347                 return (a == tarval_b_false) ? a : b;
1348
1349         case irms_int_number:
1350                 sc_and(a->value, b->value, NULL);
1351                 return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1352
1353         default:
1354                 panic("operation not defined on mode");
1355         }
1356 }
1357
1358 ir_tarval *tarval_andnot(ir_tarval *a, ir_tarval *b)
1359 {
1360         assert(a->mode == b->mode);
1361
1362         /* works even for vector modes */
1363         carry_flag = 0;
1364
1365         switch (get_mode_sort(a->mode)) {
1366         case irms_internal_boolean:
1367                 return a == tarval_b_true && b == tarval_b_false ? tarval_b_true : tarval_b_false;
1368
1369         case irms_int_number:
1370                 sc_andnot(a->value, b->value, NULL);
1371                 return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1372
1373         default:
1374                 panic("operation not defined on mode");
1375         }
1376 }
1377
1378 /*
1379  * bitwise or
1380  */
1381 ir_tarval *tarval_or(ir_tarval *a, ir_tarval *b)
1382 {
1383         assert(a->mode == b->mode);
1384
1385         /* works even for vector modes */
1386         carry_flag = 0;
1387
1388         switch (get_mode_sort(a->mode)) {
1389         case irms_internal_boolean:
1390                 return (a == tarval_b_true) ? a : b;
1391
1392         case irms_int_number:
1393                 sc_or(a->value, b->value, NULL);
1394                 return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1395
1396         default:
1397                 panic("operation not defined on mode");
1398         }
1399 }
1400
1401 /*
1402  * bitwise exclusive or (xor)
1403  */
1404 ir_tarval *tarval_eor(ir_tarval *a, ir_tarval *b)
1405 {
1406         assert((a->mode == b->mode));
1407
1408         /* works even for vector modes */
1409         carry_flag = 0;
1410
1411         switch (get_mode_sort(a->mode)) {
1412         case irms_internal_boolean:
1413                 return (a == b)? tarval_b_false : tarval_b_true;
1414
1415         case irms_int_number:
1416                 sc_xor(a->value, b->value, NULL);
1417                 return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1418
1419         default:
1420                 panic("operation not defined on mode");
1421         }
1422 }
1423
1424 /*
1425  * bitwise left shift
1426  */
1427 ir_tarval *tarval_shl(ir_tarval *a, ir_tarval *b)
1428 {
1429         char *temp_val = NULL;
1430
1431         assert(mode_is_int(a->mode) && mode_is_int(b->mode));
1432
1433         carry_flag = -1;
1434
1435         if (get_mode_n_vector_elems(a->mode) > 1 || get_mode_n_vector_elems(a->mode) > 1) {
1436                 /* vector arithmetic not implemented yet */
1437                 return tarval_bad;
1438         }
1439
1440         if (get_mode_modulo_shift(a->mode) != 0) {
1441                 temp_val = (char*) alloca(sc_get_buffer_length());
1442
1443                 sc_val_from_ulong(get_mode_modulo_shift(a->mode), temp_val);
1444                 sc_mod(b->value, temp_val, temp_val);
1445         } else
1446                 temp_val = (char*)b->value;
1447
1448         sc_shl(a->value, temp_val, get_mode_size_bits(a->mode), mode_is_signed(a->mode), NULL);
1449         return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1450 }
1451
1452 /*
1453  * bitwise unsigned right shift
1454  */
1455 ir_tarval *tarval_shr(ir_tarval *a, ir_tarval *b)
1456 {
1457         char *temp_val = NULL;
1458
1459         assert(mode_is_int(a->mode) && mode_is_int(b->mode));
1460
1461         carry_flag = -1;
1462
1463         if (get_mode_n_vector_elems(a->mode) > 1 || get_mode_n_vector_elems(a->mode) > 1) {
1464                 /* vector arithmetic not implemented yet */
1465                 return tarval_bad;
1466         }
1467
1468         if (get_mode_modulo_shift(a->mode) != 0) {
1469                 temp_val = (char*) alloca(sc_get_buffer_length());
1470
1471                 sc_val_from_ulong(get_mode_modulo_shift(a->mode), temp_val);
1472                 sc_mod(b->value, temp_val, temp_val);
1473         } else
1474                 temp_val = (char*)b->value;
1475
1476         sc_shr(a->value, temp_val, get_mode_size_bits(a->mode), mode_is_signed(a->mode), NULL);
1477         return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1478 }
1479
1480 /*
1481  * bitwise signed right shift
1482  */
1483 ir_tarval *tarval_shrs(ir_tarval *a, ir_tarval *b)
1484 {
1485         char *temp_val = NULL;
1486
1487         assert(mode_is_int(a->mode) && mode_is_int(b->mode));
1488
1489         carry_flag = -1;
1490
1491         if (get_mode_n_vector_elems(a->mode) > 1 || get_mode_n_vector_elems(a->mode) > 1) {
1492                 /* vector arithmetic not implemented yet */
1493                 return tarval_bad;
1494         }
1495
1496         if (get_mode_modulo_shift(a->mode) != 0) {
1497                 temp_val = (char*) alloca(sc_get_buffer_length());
1498
1499                 sc_val_from_ulong(get_mode_modulo_shift(a->mode), temp_val);
1500                 sc_mod(b->value, temp_val, temp_val);
1501         } else
1502                 temp_val = (char*)b->value;
1503
1504         sc_shrs(a->value, temp_val, get_mode_size_bits(a->mode), mode_is_signed(a->mode), NULL);
1505         return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1506 }
1507
1508 /*
1509  * bitwise rotation to left
1510  */
1511 ir_tarval *tarval_rotl(ir_tarval *a, ir_tarval *b)
1512 {
1513         char *temp_val = NULL;
1514
1515         assert(mode_is_int(a->mode) && mode_is_int(b->mode));
1516
1517         carry_flag = -1;
1518
1519         if (get_mode_n_vector_elems(a->mode) > 1 || get_mode_n_vector_elems(a->mode) > 1) {
1520                 /* vector arithmetic not implemented yet */
1521                 return tarval_bad;
1522         }
1523
1524         if (get_mode_modulo_shift(a->mode) != 0) {
1525                 temp_val = (char*) alloca(sc_get_buffer_length());
1526
1527                 sc_val_from_ulong(get_mode_modulo_shift(a->mode), temp_val);
1528                 sc_mod(b->value, temp_val, temp_val);
1529         } else
1530                 temp_val = (char*)b->value;
1531
1532         sc_rotl(a->value, temp_val, get_mode_size_bits(a->mode), mode_is_signed(a->mode), NULL);
1533         return get_tarval(sc_get_buffer(), sc_get_buffer_length(), a->mode);
1534 }
1535
1536 /*
1537  * carry flag of the last operation
1538  */
1539 int tarval_carry(void)
1540 {
1541         if (carry_flag == -1)
1542                 panic("Carry undefined for the last operation");
1543         return carry_flag;
1544 }
1545
1546 /*
1547  * Output of tarvals
1548  */
1549 int tarval_snprintf(char *buf, size_t len, ir_tarval *tv)
1550 {
1551         static const tarval_mode_info default_info = { TVO_NATIVE, NULL, NULL };
1552
1553         const char *str;
1554         char tv_buf[100];
1555         const tarval_mode_info *mode_info;
1556         const char *prefix, *suffix;
1557
1558         mode_info = (const tarval_mode_info*) tv->mode->tv_priv;
1559         if (! mode_info)
1560                 mode_info = &default_info;
1561         prefix = mode_info->mode_prefix ? mode_info->mode_prefix : "";
1562         suffix = mode_info->mode_suffix ? mode_info->mode_suffix : "";
1563
1564         switch (get_mode_sort(tv->mode)) {
1565         case irms_reference:
1566                 if (tv == tv->mode->null) return snprintf(buf, len, "NULL");
1567                 /* FALLTHROUGH */
1568         case irms_int_number:
1569                 switch (mode_info->mode_output) {
1570
1571                 case TVO_DECIMAL:
1572                         str = sc_print(tv->value, get_mode_size_bits(tv->mode), SC_DEC, mode_is_signed(tv->mode));
1573                         break;
1574
1575                 case TVO_OCTAL:
1576                         str = sc_print(tv->value, get_mode_size_bits(tv->mode), SC_OCT, 0);
1577                         break;
1578
1579                 case TVO_NATIVE:
1580                         prefix = "0x";
1581                 case TVO_HEX:
1582                 default:
1583                         str = sc_print(tv->value, get_mode_size_bits(tv->mode), SC_HEX, 0);
1584                         break;
1585                 }
1586                 return snprintf(buf, len, "%s%s%s", prefix, str, suffix);
1587
1588         case irms_float_number:
1589                 switch (mode_info->mode_output) {
1590                 case TVO_HEX:
1591                         return snprintf(buf, len, "%s%s%s", prefix, fc_print((const fp_value*) tv->value, tv_buf, sizeof(tv_buf), FC_PACKED), suffix);
1592
1593                 case TVO_HEXFLOAT:
1594                         return snprintf(buf, len, "%s%s%s", prefix, fc_print((const fp_value*) tv->value, tv_buf, sizeof(tv_buf), FC_HEX), suffix);
1595
1596                 case TVO_FLOAT:
1597                 case TVO_NATIVE:
1598                 default:
1599                         return snprintf(buf, len, "%s%s%s", prefix, fc_print((const fp_value*) tv->value, tv_buf, sizeof(tv_buf), FC_DEC), suffix);
1600                 }
1601                 break;
1602
1603         case irms_internal_boolean:
1604                 switch (mode_info->mode_output) {
1605
1606                 case TVO_DECIMAL:
1607                 case TVO_OCTAL:
1608                 case TVO_HEX:
1609                 case TVO_BINARY:
1610                         return snprintf(buf, len, "%s%c%s", prefix, (tv == tarval_b_true) ? '1' : '0', suffix);
1611
1612                 case TVO_NATIVE:
1613                 default:
1614                         return snprintf(buf, len, "%s%s%s", prefix, (tv == tarval_b_true) ? "true" : "false", suffix);
1615                 }
1616
1617         case irms_control_flow:
1618         case irms_memory:
1619         case irms_auxiliary:
1620                 if (tv == tarval_bad)
1621                         return snprintf(buf, len, "<TV_BAD>");
1622                 if (tv == tarval_undefined)
1623                         return snprintf(buf, len, "<TV_UNDEF>");
1624                 if (tv == tarval_unreachable)
1625                         return snprintf(buf, len, "<TV_UNREACHABLE>");
1626                 if (tv == tarval_reachable)
1627                         return snprintf(buf, len, "<TV_REACHABLE>");
1628                 return snprintf(buf, len, "<TV_??""?>");
1629         }
1630
1631         return 0;
1632 }
1633
1634 /**
1635  * Output of tarvals to stdio.
1636  */
1637 int tarval_printf(ir_tarval *tv)
1638 {
1639         char buf[1024];
1640         int res;
1641
1642         res = tarval_snprintf(buf, sizeof(buf), tv);
1643         assert(res < (int) sizeof(buf) && "buffer to small for tarval_snprintf");
1644         printf("%s", buf);
1645         return res;
1646 }
1647
1648 char *get_tarval_bitpattern(ir_tarval *tv)
1649 {
1650         int i, j, pos = 0;
1651         int n = get_mode_size_bits(tv->mode);
1652         int bytes = (n + 7) / 8;
1653         char *res = XMALLOCN(char, n + 1);
1654         unsigned char byte;
1655
1656         for (i = 0; i < bytes; i++) {
1657                 byte = get_tarval_sub_bits(tv, i);
1658                 for (j = 1; j < 256; j <<= 1)
1659                         if (pos < n)
1660                                 res[pos++] = j & byte ? '1' : '0';
1661         }
1662
1663         res[n] = '\0';
1664
1665         return res;
1666 }
1667
1668 /*
1669  * access to the bitpattern
1670  */
1671 unsigned char get_tarval_sub_bits(ir_tarval *tv, unsigned byte_ofs)
1672 {
1673         switch (get_mode_arithmetic(tv->mode)) {
1674         case irma_twos_complement:
1675                 return sc_sub_bits(tv->value, get_mode_size_bits(tv->mode), byte_ofs);
1676         case irma_ieee754:
1677                 return fc_sub_bits((const fp_value*) tv->value, get_mode_size_bits(tv->mode), byte_ofs);
1678         default:
1679                 panic("get_tarval_sub_bits(): arithmetic mode not supported");
1680         }
1681 }
1682
1683 /*
1684  * Specify the output options of one mode.
1685  *
1686  * This functions stores the modinfo, so DO NOT DESTROY it.
1687  *
1688  * Returns zero on success.
1689  */
1690 int  set_tarval_mode_output_option(ir_mode *mode, const tarval_mode_info *modeinfo)
1691 {
1692         assert(mode);
1693
1694         mode->tv_priv = modeinfo;
1695         return 0;
1696 }
1697
1698 /*
1699  * Returns the output options of one mode.
1700  *
1701  * This functions returns the mode info of a given mode.
1702  */
1703 const tarval_mode_info *get_tarval_mode_output_option(ir_mode *mode)
1704 {
1705         assert(mode);
1706
1707         return (const tarval_mode_info*) mode->tv_priv;
1708 }
1709
1710 /*
1711  * Returns non-zero if a given (integer) tarval has only one single bit
1712  * set.
1713  */
1714 int tarval_is_single_bit(ir_tarval *tv)
1715 {
1716         int i, l;
1717         int bits;
1718
1719         if (!tv || tv == tarval_bad) return 0;
1720         if (! mode_is_int(tv->mode)) return 0;
1721
1722         l = get_mode_size_bytes(tv->mode);
1723         for (bits = 0, i = l - 1; i >= 0; --i) {
1724                 unsigned char v = get_tarval_sub_bits(tv, (unsigned)i);
1725
1726                 /* check for more than one bit in these */
1727                 if (v) {
1728                         if (v & (v-1))
1729                                 return 0;
1730                         if (++bits > 1)
1731                                 return 0;
1732                 }
1733         }
1734         return bits;
1735 }
1736
1737 /*
1738  * Return the number of set bits in a given (integer) tarval.
1739  */
1740 int get_tarval_popcount(ir_tarval *tv)
1741 {
1742         int i, l;
1743         int bits;
1744
1745         if (!tv || tv == tarval_bad) return -1;
1746         if (! mode_is_int(tv->mode)) return -1;
1747
1748         l = get_mode_size_bytes(tv->mode);
1749         for (bits = 0, i = l - 1; i >= 0; --i) {
1750                 unsigned char v = get_tarval_sub_bits(tv, (unsigned)i);
1751
1752                 bits += popcount(v);
1753         }
1754         return bits;
1755 }
1756
1757 /**
1758  * Return the number of the lowest set bit in a given (integer) tarval.
1759  *
1760  * @param tv    the tarval
1761  *
1762  * @return number of lowest set bit or -1 on error
1763  */
1764 int get_tarval_lowest_bit(ir_tarval *tv)
1765 {
1766         int i, l;
1767
1768         if (!tv || tv == tarval_bad) return -1;
1769         if (! mode_is_int(tv->mode)) return -1;
1770
1771         l = get_mode_size_bytes(tv->mode);
1772         for (i = 0; i < l; ++i) {
1773                 unsigned char v = get_tarval_sub_bits(tv, (unsigned)i);
1774
1775                 if (v)
1776                         return ntz(v) + i * 8;
1777         }
1778         return -1;
1779 }
1780
1781 /*
1782  * Returns non-zero if the mantissa of a floating point IEEE-754
1783  * tarval is zero (i.e. 1.0Exxx)
1784  */
1785 int tarval_ieee754_zero_mantissa(ir_tarval *tv)
1786 {
1787         assert(get_mode_arithmetic(tv->mode) == irma_ieee754);
1788         return fc_zero_mantissa((const fp_value*) tv->value);
1789 }
1790
1791 /* Returns the exponent of a floating point IEEE-754 tarval. */
1792 int tarval_ieee754_get_exponent(ir_tarval *tv)
1793 {
1794         assert(get_mode_arithmetic(tv->mode) == irma_ieee754);
1795         return fc_get_exponent((const fp_value*) tv->value);
1796 }
1797
1798 /*
1799  * Check if the tarval can be converted to the given mode without
1800  * precision loss.
1801  */
1802 int tarval_ieee754_can_conv_lossless(ir_tarval *tv, ir_mode *mode)
1803 {
1804         const ieee_descriptor_t *desc = get_descriptor(mode);
1805         return fc_can_lossless_conv_to((const fp_value*) tv->value, desc);
1806 }
1807
1808 /* Set the immediate precision for IEEE-754 results. */
1809 unsigned tarval_ieee754_set_immediate_precision(unsigned bits)
1810 {
1811         return fc_set_immediate_precision(bits);
1812 }
1813
1814 /* Returns non-zero if the result of the last IEEE-754 operation was exact. */
1815 unsigned tarval_ieee754_get_exact(void)
1816 {
1817         return fc_is_exact();
1818 }
1819
1820 /* Return the size of the mantissa in bits (including possible
1821    implicit bits) for the given mode. */
1822 unsigned tarval_ieee754_get_mantissa_size(const ir_mode *mode)
1823 {
1824         const ieee_descriptor_t *desc;
1825
1826         assert(get_mode_arithmetic(mode) == irma_ieee754);
1827         desc = get_descriptor(mode);
1828
1829         return desc->mantissa_size + desc->explicit_one;
1830 }
1831
1832 /* check if its the a floating point NaN */
1833 int tarval_is_NaN(ir_tarval *tv)
1834 {
1835         if (! mode_is_float(tv->mode))
1836                 return 0;
1837         return fc_is_nan((const fp_value*) tv->value);
1838 }
1839
1840 /* check if its the a floating point +inf */
1841 int tarval_is_plus_inf(ir_tarval *tv)
1842 {
1843         if (! mode_is_float(tv->mode))
1844                 return 0;
1845         return fc_is_inf((const fp_value*) tv->value)
1846                 && !fc_is_negative((const fp_value*) tv->value);
1847 }
1848
1849 /* check if its the a floating point -inf */
1850 int tarval_is_minus_inf(ir_tarval *tv)
1851 {
1852         if (! mode_is_float(tv->mode))
1853                 return 0;
1854         return fc_is_inf((const fp_value*) tv->value)
1855                 && fc_is_negative((const fp_value*) tv->value);
1856 }
1857
1858 /* check if the tarval represents a finite value */
1859 int tarval_is_finite(ir_tarval *tv)
1860 {
1861         if (mode_is_float(tv->mode))
1862                 return !fc_is_nan((const fp_value*) tv->value)
1863                         && !fc_is_inf((const fp_value*) tv->value);
1864         return 1;
1865 }
1866
1867 /*
1868  * Sets the overflow mode for integer operations.
1869  */
1870 void tarval_set_integer_overflow_mode(tarval_int_overflow_mode_t ov_mode)
1871 {
1872         int_overflow_mode = ov_mode;
1873 }
1874
1875 /* Get the overflow mode for integer operations. */
1876 tarval_int_overflow_mode_t tarval_get_integer_overflow_mode(void)
1877 {
1878         return int_overflow_mode;
1879 }
1880
1881 /* Enable/Disable floating point constant folding. */
1882 void tarval_enable_fp_ops(int enable)
1883 {
1884         no_float = !enable;
1885 }
1886
1887 int tarval_fp_ops_enabled(void)
1888 {
1889         return !no_float;
1890 }
1891
1892 /**
1893  * default mode_info for output as HEX
1894  */
1895 static const tarval_mode_info hex_output = {
1896         TVO_HEX,
1897         "0x",
1898         NULL,
1899 };
1900
1901 /*
1902  * Initialization of the tarval module: called before init_mode()
1903  */
1904 void init_tarval_1(long null_value, int support_quad_precision)
1905 {
1906         /* if these assertion fail, tarval_is_constant() will follow ... */
1907         assert(tarval_b_false == &reserved_tv[0] && "b_false MUST be the first reserved tarval!");
1908         assert(tarval_b_true  == &reserved_tv[1] && "b_true MUST be the second reserved tarval!");
1909
1910         _null_value = null_value;
1911
1912         /* initialize the sets holding the tarvals with a comparison function and
1913          * an initial size, which is the expected number of constants */
1914         tarvals = new_set(cmp_tv, N_CONSTANTS);
1915         values  = new_set(memcmp, N_CONSTANTS);
1916         /* calls init_strcalc() with needed size */
1917         init_fltcalc(support_quad_precision ? 112 : 64);
1918 }
1919
1920 /*
1921  * Initialization of the tarval module: called after init_mode()
1922  */
1923 void init_tarval_2(void)
1924 {
1925         tarval_bad->kind          = k_tarval;
1926         tarval_bad->mode          = mode_BAD;
1927         tarval_bad->value         = INT_TO_PTR(resid_tarval_bad);
1928
1929         tarval_undefined->kind    = k_tarval;
1930         tarval_undefined->mode    = mode_ANY;
1931         tarval_undefined->value   = INT_TO_PTR(resid_tarval_undefined);
1932
1933         tarval_b_true->kind       = k_tarval;
1934         tarval_b_true->mode       = mode_b;
1935         tarval_b_true->value      = INT_TO_PTR(resid_tarval_b_true);
1936
1937         tarval_b_false->kind      = k_tarval;
1938         tarval_b_false->mode      = mode_b;
1939         tarval_b_false->value     = INT_TO_PTR(resid_tarval_b_false);
1940
1941         tarval_unreachable->kind  = k_tarval;
1942         tarval_unreachable->mode  = mode_X;
1943         tarval_unreachable->value = INT_TO_PTR(resid_tarval_unreachable);
1944
1945         tarval_reachable->kind    = k_tarval;
1946         tarval_reachable->mode    = mode_X;
1947         tarval_reachable->value   = INT_TO_PTR(resid_tarval_reachable);
1948
1949         /*
1950          * assign output modes that are compatible with the
1951          * old implementation: Hex output
1952          */
1953         set_tarval_mode_output_option(mode_Bs, &hex_output);
1954         set_tarval_mode_output_option(mode_Bu, &hex_output);
1955         set_tarval_mode_output_option(mode_Hs, &hex_output);
1956         set_tarval_mode_output_option(mode_Hu, &hex_output);
1957         set_tarval_mode_output_option(mode_Is, &hex_output);
1958         set_tarval_mode_output_option(mode_Iu, &hex_output);
1959         set_tarval_mode_output_option(mode_Ls, &hex_output);
1960         set_tarval_mode_output_option(mode_Lu, &hex_output);
1961         set_tarval_mode_output_option(mode_P,  &hex_output);
1962 }
1963
1964 /* free all memory occupied by tarval. */
1965 void finish_tarval(void)
1966 {
1967         finish_strcalc();
1968         finish_fltcalc();
1969         del_set(tarvals); tarvals = NULL;
1970         del_set(values);  values = NULL;
1971 }
1972
1973 int (is_tarval)(const void *thing)
1974 {
1975         return _is_tarval(thing);
1976 }