nsz Git - libfirm/blob - ir/ana/vrp.c

   1 /*
   2  * Copyright (C) 1995-2009 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       analyze graph to provide value range information
  23  * @author      Jonas Fietz
  24  * @version     $Id$
  25  */
  26 #include "config.h"
  27
  28 #include "config.h"
  29 #include "irtypes.h"
  30 #include "vrp.h"
  31 #include "irouts.h"
  32 #include "irgraph_t.h"
  33 #include "irpass.h"
  34 #include "list.h"
  35 #include "irgwalk.h"
  36 #include "iredges.h"
  37 #include "tv.h"
  38
  39
  40 static char v;
  41 static void *VISITED = &v;
  42
  43 typedef struct worklist_t worklist_t;
  44 struct worklist_t {
  45          struct list_head nodes;
  46         ir_node *node;
  47 };
  48
  49 struct vrp_env_t {
  50         worklist_t *worklist;
  51 };
  52
  53 int update_vrp_data(ir_node *node)
  54 {
  55
  56         tarval *new_bits_set = get_tarval_bad();
  57         tarval *new_bits_not_set = get_tarval_bad();
  58         tarval *new_range_bottom = get_tarval_bad();
  59         tarval *new_range_top = get_tarval_bad();
  60         ir_node *new_bits_node = NULL;
  61         ir_node *new_range_node = NULL;
  62         enum range_types new_range_type = VRP_UNDEFINED;
  63         enum range_ops new_range_op = VRP_NONE;
  64         int something_changed = 0;
  65
  66         node->vrp.valid = 1;
  67         /* TODO: Check if all predecessors have valid VRP information*/
  68
  69
  70         if (!mode_is_int(get_irn_mode(node))) {
  71                 return 0; /* we don't optimize for non-int-nodes*/
  72         }
  73
  74         if (is_Const(node)) {
  75                 tarval *tv = get_Const_tarval(node);
  76
  77                 new_bits_set = tv;
  78                 new_bits_not_set = tarval_not(tv);
  79                 new_range_bottom = tv;
  80                 new_range_top = tv;
  81                 new_range_type = VRP_RANGE;
  82         } else if (is_And(node)) {
  83                 ir_node *pred0 = get_And_left(node);
  84                 ir_node *pred1 = get_And_right(node);
  85                 tarval *tmp;
  86
  87                 new_bits_set = tarval_and(pred0->vrp.bits_set, pred1->vrp.bits_set);
  88                 new_bits_not_set = tarval_or(pred0->vrp.bits_not_set, pred1->vrp.bits_not_set);
  89
  90                 tmp = tarval_not(pred0->vrp.bits_set);
  91                 tmp = tarval_eor(pred0->vrp.bits_not_set, tmp);
  92                 /*check if one of the predecessors is completely determined*/
  93                 if (tarval_is_null(tmp)) {
  94                         new_bits_node = pred1;
  95                 }
  96
  97                 tmp = tarval_not(pred1->vrp.bits_set);
  98                 tmp = tarval_eor(pred1->vrp.bits_not_set, tmp);
  99                 if (tarval_is_null(tmp)) {
 100                         new_bits_node = pred0;
 101                 }
 102         } else if (is_Add(node)) {
 103                 ir_node *pred0 = get_Add_left(node);
 104                 ir_node *pred1 = get_Add_right(node);
 105                 int overflow_top, overflow_bottom;
 106                 tarval *new_top, *new_bottom;
 107
 108                 if (pred0->vrp.range_type == VRP_UNDEFINED || pred1->vrp.range_type ==
 109                                 VRP_UNDEFINED || pred0->vrp.range_type == VRP_VARYING ||
 110                                 pred1->vrp.range_type == VRP_VARYING) {
 111                         return 0;
 112                 }
 113
 114                 new_top = tarval_add(pred0->vrp.range_top, pred1->vrp.range_top);
 115                 overflow_top = tarval_carry();
 116                 new_bottom = tarval_add(pred0->vrp.range_bottom, pred1->vrp.range_bottom);
 117                 overflow_bottom = tarval_carry();
 118
 119                 if (!overflow_top && !overflow_bottom && pred0->vrp.range_type == VRP_RANGE
 120                                 &&pred1->vrp.range_type == VRP_RANGE) {
 121                         new_range_bottom = new_bottom;
 122                         new_range_top = new_top;
 123                         new_range_type = VRP_RANGE;
 124                 }
 125
 126                 if (overflow_top || overflow_bottom) {
 127                         /* TODO Implement overflow handling*/
 128                         new_range_type = VRP_UNDEFINED;
 129                 }
 130         } else if (is_Sub(node)) {
 131                 ir_node *pred0 = get_Sub_left(node);
 132                 ir_node *pred1 = get_Sub_right(node);
 133                 int overflow_top, overflow_bottom;
 134                 tarval *new_top, *new_bottom;
 135
 136                 if (pred0->vrp.range_type == VRP_UNDEFINED || pred1->vrp.range_type ==
 137                                 VRP_UNDEFINED) {
 138                         return 0;
 139                 }
 140
 141                 new_top = tarval_sub(pred0->vrp.range_top, pred1->vrp.range_top, NULL);
 142                 overflow_top = tarval_carry();
 143                 new_bottom = tarval_sub(pred0->vrp.range_bottom, pred1->vrp.range_bottom, NULL);
 144                 overflow_bottom = tarval_carry();
 145
 146                 if (!overflow_top && !overflow_bottom && pred0->vrp.range_type == VRP_RANGE
 147                                 &&pred1->vrp.range_type == VRP_RANGE) {
 148                         new_range_bottom = new_bottom;
 149                         new_range_top = new_top;
 150                         new_range_type = VRP_RANGE;
 151                 }
 152
 153                 if (overflow_top || overflow_bottom) {
 154                         /* TODO Implement overflow handling*/
 155                 }
 156         } else if (is_Or(node)) {
 157                 ir_node *a = get_Or_left(node);
 158                 ir_node *b = get_Or_right(node);
 159                 tarval *tmp;
 160
 161                 new_bits_set = tarval_or(a->vrp.bits_set, b->vrp.bits_set);
 162                 new_bits_not_set = tarval_and(a->vrp.bits_not_set, b->vrp.bits_not_set);
 163
 164                 tmp = tarval_not(a->vrp.bits_set);
 165                 tmp = tarval_eor(a->vrp.bits_not_set, tmp);
 166                 /*check if one of the predecessors is completely determined*/
 167                 if (tarval_is_null(tmp)) {
 168                         new_bits_node = b;
 169                 }
 170
 171                 tmp = tarval_not(b->vrp.bits_set);
 172                 tmp = tarval_eor(b->vrp.bits_not_set, tmp);
 173                 if (tarval_is_null(tmp)) {
 174                         new_bits_node = a;
 175                 }
 176
 177         } else if (is_Rotl(node)) {
 178                 ir_node *a = get_Rotl_left(node);
 179                 ir_node *b = get_Rotl_right(node);
 180
 181                 /* We can only compute this if the right value is a constant*/
 182                 if (is_Const(b)) {
 183                         tarval *bits_set, *bits_not_set;
 184                         bits_set = tarval_rotl(a->vrp.bits_set, get_Const_tarval(b));
 185                         bits_not_set = tarval_rotl(a->vrp.bits_not_set, get_Const_tarval(b));
 186
 187                         new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
 188                         new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
 189                 }
 190
 191         } else if (is_Shl(node)) {
 192                 ir_node *a = get_Shl_left(node);
 193                 ir_node *b = get_Shl_right(node);
 194
 195                 /* We can only compute this if the right value is a constant*/
 196                 if (is_Const(b)) {
 197                         tarval *bits_set, *bits_not_set;
 198                         ir_mode *m = get_tarval_mode(node->vrp.bits_not_set);
 199                         bits_set = tarval_shl(a->vrp.bits_set, get_Const_tarval(b));
 200                         bits_not_set = tarval_shl(a->vrp.bits_not_set, get_Const_tarval(b));
 201
 202                         new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
 203                         new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
 204
 205                         bits_not_set = tarval_not( tarval_shl(
 206                                                                                 get_mode_all_one(m),
 207                                                                                 get_Const_tarval(b)));
 208                         new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);
 209
 210                 }
 211
 212         } else if (is_Shr(node)) {
 213                 ir_node *a = get_Shr_left(node);
 214                 ir_node *b = get_Shr_right(node);
 215
 216                 /* We can only compute this if the right value is a constant*/
 217                 if (is_Const(b)) {
 218                         tarval *bits_set, *bits_not_set;
 219                         ir_mode *m = get_tarval_mode(node->vrp.bits_not_set);
 220                         bits_set = tarval_shr(a->vrp.bits_set, get_Const_tarval(b));
 221                         bits_not_set = tarval_shr(a->vrp.bits_not_set, get_Const_tarval(b));
 222
 223                         new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
 224                         new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
 225
 226                         bits_not_set = tarval_not( tarval_shr(
 227                                                                                 get_mode_all_one(m),
 228                                                                                 get_Const_tarval(b)));
 229                         new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);
 230                 }
 231
 232         } else if (is_Shrs(node)) {
 233                 ir_node *a = get_Shrs_left(node);
 234                 ir_node *b = get_Shrs_right(node);
 235
 236                 /* We can only compute this if the right value is a constant*/
 237                 if (is_Const(b)) {
 238                         tarval *bits_set, *bits_not_set;
 239                         ir_mode *m = get_tarval_mode(node->vrp.bits_not_set);
 240                         bits_set = tarval_shrs(a->vrp.bits_set, get_Const_tarval(b));
 241                         bits_not_set = tarval_shrs(a->vrp.bits_not_set, get_Const_tarval(b));
 242
 243                         new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
 244                         new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
 245
 246                         bits_not_set = tarval_not( tarval_shrs(
 247                                                                                 get_mode_all_one(m),
 248                                                                                 get_Const_tarval(b)));
 249                         new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);
 250                 }
 251
 252         } else if (is_Eor(node)) {
 253                 ir_node *a = get_Eor_left(node);
 254                 ir_node *b = get_Eor_right(node);
 255
 256                 tarval *bits_set, *bits_not_set;
 257                 bits_not_set = tarval_or(
 258                                                         tarval_and(a->vrp.bits_set, b->vrp.bits_set),
 259                                                         tarval_and(a->vrp.bits_not_set,
 260                                                                 b->vrp.bits_not_set));
 261
 262                 bits_set = tarval_or(
 263                                                 tarval_and(a->vrp.bits_set, b->vrp.bits_not_set),
 264                                                 tarval_and(a->vrp.bits_not_set, b->vrp.bits_set));
 265
 266                 new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
 267                 new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
 268
 269         } else if (is_Id(node)) {
 270                 ir_node *pred = get_Id_pred(node);
 271                 new_bits_set = pred->vrp.bits_set;
 272                 new_bits_not_set = pred->vrp.bits_not_set;
 273                 new_range_top = pred->vrp.range_top;
 274                 new_range_bottom = pred->vrp.range_bottom;
 275                 new_range_type = pred->vrp.range_type;
 276
 277         } else if (is_Not(node)) {
 278                 ir_node *pred = get_Not_op(node);
 279                 new_bits_set = tarval_or(pred->vrp.bits_not_set, node->vrp.bits_set);
 280                 new_bits_not_set = tarval_or(pred->vrp.bits_set, node->vrp.bits_not_set);
 281
 282         } else if (is_Conv(node)) {
 283                 ir_node *pred = get_Conv_op(node);
 284                 ir_mode *old_mode = get_irn_mode(pred);
 285                 ir_mode *new_mode;
 286                 tarval *bits_not_set;
 287
 288                 if (!mode_is_int(old_mode))
 289                         return 0;
 290
 291                 new_mode = get_irn_mode(node);
 292
 293                 /* The second and is needed if target type is smaller*/
 294                 bits_not_set = tarval_not(
 295                                                         tarval_convert_to(get_mode_all_one(old_mode),
 296                                                                 new_mode
 297                                                                 ));
 298                 bits_not_set = tarval_or(bits_not_set, tarval_convert_to(pred->vrp.bits_not_set, new_mode));
 299                 new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
 300                 new_bits_set = tarval_and(
 301                                 tarval_not(bits_not_set), tarval_convert_to(pred->vrp.bits_set, new_mode));
 302
 303                 if (tarval_cmp(pred->vrp.range_top, get_mode_max(new_mode)) == pn_Cmp_Le) {
 304                         node->vrp.range_top = pred->vrp.range_top;
 305                 }
 306
 307                 if (tarval_cmp(pred->vrp.range_bottom, get_mode_min(new_mode)) == pn_Cmp_Ge) {
 308                         node->vrp.range_bottom = pred->vrp.range_bottom;
 309                 }
 310
 311         } else if (is_Confirm(node)) {
 312                 pn_Cmp cmp = get_Confirm_cmp(node);
 313                 ir_node *bound = get_Confirm_bound(node);
 314
 315                 /** @todo: Handle non-Const bounds */
 316
 317                 if (cmp == pn_Cmp_Lg) {
 318                         /** @todo: Is there some way to preserve the information? */
 319                         new_range_type = VRP_ANTIRANGE;
 320                         if (is_Const(bound)) {
 321                                 new_range_top = get_Const_tarval(bound);
 322                                 new_range_bottom = get_Const_tarval(bound);
 323                         }
 324                 } else if (cmp == pn_Cmp_Le) {
 325                         if (node->vrp.range_type == VRP_UNDEFINED) {
 326                                 new_range_type = VRP_RANGE;
 327                                 if (is_Const(bound)) {
 328                                         new_range_top = get_Const_tarval(bound);
 329                                 }
 330                                 new_range_bottom = get_tarval_min(get_irn_mode(node));
 331                         } else if (node->vrp.range_type == VRP_RANGE) {
 332                                 if (is_Const(bound)) {
 333                                         if (tarval_cmp(node->vrp.range_top,
 334                                                                 get_Const_tarval(bound)) == pn_Cmp_Le) {
 335                                                 new_range_top = get_Const_tarval(bound);
 336                                         }
 337                                         new_range_bottom = get_tarval_min(get_irn_mode(node));
 338
 339                                 } else if (node->vrp.range_type == VRP_ANTIRANGE) {
 340                                         /** @todo: How do we manage not to get a never ending loop? */
 341                                 }
 342                         }
 343                 }
 344
 345         } else if (is_Phi(node)) {
 346                 /* combine all ranges*/
 347                 ir_node *pred;
 348                 int num = get_Phi_n_preds(node);
 349                 pn_Cmp cmp;
 350                 int i;
 351                 tarval *range_top, *range_bottom, *bits_set, *bits_not_set;
 352                 enum range_types range_type;
 353
 354                 assert(num > 0);
 355
 356                 pred = get_Phi_pred(node,0);
 357                 range_top = pred->vrp.range_top;
 358                 range_bottom = pred->vrp.range_bottom;
 359                 range_type = pred->vrp.range_type;
 360                 bits_set = pred->vrp.bits_set;
 361                 bits_not_set = pred->vrp.bits_not_set;
 362
 363                 for (i = 1; i < num; i++) {
 364                         pred = get_Phi_pred(node, i);
 365                         if (range_type == VRP_RANGE && pred->vrp.range_type ==
 366                                         VRP_RANGE) {
 367                                 cmp = tarval_cmp(range_top, pred->vrp.range_top);
 368                                 if (cmp == pn_Cmp_Lt) {
 369                                         range_top = pred->vrp.range_top;
 370                                 }
 371                                 cmp = tarval_cmp(range_bottom, pred->vrp.range_bottom);
 372                                 if (cmp == pn_Cmp_Gt) {
 373                                         range_bottom = pred->vrp.range_bottom;
 374                                 }
 375                         } else {
 376                                 range_type = VRP_VARYING;
 377                                 break;
 378                         }
 379                 }
 380
 381                 new_range_type = range_type;
 382                 new_range_top = range_top;
 383                 new_range_bottom = range_bottom;
 384
 385         } else {
 386                 /* unhandled, therefore never updated*/
 387                 return 0;
 388         }
 389
 390
 391
 392         /* TODO: Check, if there can be information derived from any of these:
 393         is_Abs(node) is_Alloc(node) is_Anchor(node) is_Borrow(node) is_Bound(node)
 394         is_Break(node) is_Builtin(node) is_Call(node) is_CallBegin(node)
 395         is_Carry(node) is_Cast(node) is_Cmp(node) is_Cond(node)
 396         is_CopyB(node) is_Div(node) is_DivMod(node) is_Dummy(node)
 397         is_End(node) is_EndExcept(node) is_EndReg(node) is_Filter(node) is_Free(node)
 398         is_IJmp(node) is_InstOf(node) is_Jmp(node) is_Load(node) is_Minus(node)
 399         is_Mod(node) is_Mul(node) is_Mulh(node) is_Mux(node) is_NoMem(node)
 400         is_Pin(node) is_Proj(node) is_Quot(node)
 401         is_Raise(node) is_Return(node) is_Sel(node) is_Start(node) is_Store(node)
 402         is_SymConst(node) is_Sync(node) is_Tuple(node)
 403         */
 404
 405         /* Merge the newly calculated values with those that might already exist*/
 406
 407         if (new_bits_set != tarval_bad) {
 408                 new_bits_set = tarval_or(new_bits_set, node->vrp.bits_set);
 409                 if (tarval_cmp(new_bits_set, node->vrp.bits_set) != pn_Cmp_Eq) {
 410                         something_changed = 1;
 411                         node->vrp.bits_set = new_bits_set;
 412                 }
 413         }
 414
 415         if (new_bits_not_set != tarval_bad) {
 416                 new_bits_not_set = tarval_or(new_bits_not_set, node->vrp.bits_not_set);
 417
 418                 if (tarval_cmp(new_bits_not_set, node->vrp.bits_not_set) != pn_Cmp_Eq) {
 419                         something_changed = 1;
 420                         node->vrp.bits_not_set = new_bits_not_set;
 421                 }
 422         }
 423
 424         if (node->vrp.bits_node == NULL && new_bits_node != NULL) {
 425                 something_changed = 1;
 426                 node->vrp.bits_node = new_bits_node;
 427         }
 428
 429         if (node->vrp.range_type == VRP_UNDEFINED &&
 430                         new_range_type != VRP_UNDEFINED) {
 431                 something_changed = 1;
 432                 node->vrp.range_type = new_range_type;
 433                 node->vrp.range_bottom = new_range_bottom;
 434                 node->vrp.range_top = new_range_top;
 435                 node->vrp.range_op = new_range_op;
 436                 node->vrp.range_node = new_range_node;
 437
 438         } else if (node->vrp.range_type == VRP_RANGE) {
 439                 if (new_range_type == VRP_RANGE) {
 440                         if ((new_range_node == NULL && node->vrp.range_node == NULL) ||
 441                                         (new_range_node == node->vrp.range_node &&
 442                                          new_range_op == node->vrp.range_op)) {
 443                                 if (tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Lt) {
 444                                         something_changed = 1;
 445                                         node->vrp.range_bottom = new_range_bottom;
 446                                 }
 447                                 if (tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Gt) {
 448                                         something_changed = 1;
 449                                         node->vrp.range_top = new_range_top;
 450                                 }
 451                         }
 452
 453                         /* prefer the absolute value*/
 454                         if (new_range_node == NULL && node->vrp.range_node != NULL) {
 455                                 something_changed = 1;
 456                                 node->vrp.range_node = NULL;
 457                                 node->vrp.range_top = new_range_top;
 458                                 node->vrp.range_bottom = new_range_bottom;
 459                         }
 460                 }
 461
 462                 if (new_range_type == VRP_ANTIRANGE) {
 463                         /* if they are overlapping, cut the range.*/
 464                         /* TODO: Maybe we can preserve more information here*/
 465                         if (new_range_node == NULL && node->vrp.range_node == NULL) {
 466                                 if (tarval_cmp(node->vrp.range_bottom, new_range_top) == pn_Cmp_Gt &&
 467                                                 tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Gt) {
 468                                         something_changed = 1;
 469                                         node->vrp.range_bottom = new_range_top;
 470
 471                                 } else if (tarval_cmp(node->vrp.range_top, new_range_bottom) == pn_Cmp_Gt &&
 472                                                 tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Lt) {
 473                                         something_changed = 1;
 474                                         node->vrp.range_top = new_range_bottom;
 475                                 }
 476
 477                                 /* We can not handle the case where the anti range is in the*/
 478                                 /* range*/
 479                         }
 480
 481                         /* prefer the absolute value*/
 482                         if (new_range_node == NULL && node->vrp.range_node != NULL) {
 483                                 something_changed = 1;
 484                                 node->vrp.range_node = NULL;
 485                                 node->vrp.range_top = new_range_top;
 486                                 node->vrp.range_bottom = new_range_bottom;
 487                         }
 488                 }
 489         } else if (node->vrp.range_type == VRP_ANTIRANGE) {
 490                 if (new_range_type == VRP_ANTIRANGE) {
 491                         if ((new_range_node == NULL && node->vrp.range_node == NULL) ||
 492                                         (new_range_node == node->vrp.range_node &&
 493                                          new_range_op == node->vrp.range_op)) {
 494                                 if (tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Gt) {
 495                                         something_changed = 1;
 496                                         node->vrp.range_bottom = new_range_bottom;
 497                                 }
 498                                 if (tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Lt) {
 499                                         something_changed = 1;
 500                                         node->vrp.range_top = new_range_top;
 501                                 }
 502                         }
 503
 504                         /* prefer the absolute value*/
 505                         if (new_range_node == NULL && node->vrp.range_node != NULL) {
 506                                 something_changed = 1;
 507                                 node->vrp.range_node = NULL;
 508                                 node->vrp.range_top = new_range_top;
 509                                 node->vrp.range_bottom = new_range_bottom;
 510                         }
 511                 }
 512
 513                 if (new_range_type == VRP_RANGE) {
 514                         if ((new_range_node == NULL && node->vrp.range_node == NULL) ||
 515                                         (new_range_node == node->vrp.range_node &&
 516                                          new_range_op == node->vrp.range_op)) {
 517                                 if (tarval_cmp(node->vrp.range_bottom, new_range_top) == pn_Cmp_Gt) {
 518                                         something_changed = 1;
 519                                         node->vrp.range_bottom = new_range_top;
 520                                 }
 521                                 if (tarval_cmp(node->vrp.range_top, new_range_bottom) == pn_Cmp_Lt) {
 522                                         something_changed = 1;
 523                                         node->vrp.range_top = new_range_bottom;
 524                                 }
 525                         }
 526
 527                         /* prefer the absolute value*/
 528                         if (new_range_node == NULL && node->vrp.range_node != NULL) {
 529                                 something_changed = 1;
 530                                 node->vrp.range_node = NULL;
 531                                 node->vrp.range_top = new_range_top;
 532                                 node->vrp.range_bottom = new_range_bottom;
 533                         }
 534                 }
 535         }
 536
 537         assert(tarval_is_null(
 538                                 tarval_and(node->vrp.bits_set, node->vrp.bits_not_set)));
 539
 540         return something_changed;
 541 }
 542
 543 void vrp_first_pass(ir_node *n, void *e)
 544 {
 545         ir_node *succ;
 546         worklist_t *tmp_entry;
 547         int i;
 548         struct vrp_env_t *env = e;
 549
 550         if (is_Block(n))
 551                 return;
 552
 553         set_irn_link(n, VISITED);
 554
 555         update_vrp_data(n);
 556
 557         for (i = get_irn_n_outs(n) - 1; i >=0; --i) {
 558                 succ =  get_irn_out(n, i);
 559                 if (get_irn_link(succ) == VISITED) {
 560                         /* we found a loop*/
 561
 562                         tmp_entry = XMALLOC(worklist_t);
 563                         tmp_entry->node = n;
 564                         list_add(&(tmp_entry->nodes), &(env->worklist->nodes));
 565
 566
 567                 }
 568         }
 569 }
 570
 571
 572 void set_vrp_data(ir_graph *irg)
 573 {
 574
 575         ir_node *succ;
 576         int i;
 577         worklist_t worklist;
 578         worklist_t *tmp_entry, *tmp_entry2;
 579         struct vrp_env_t env;
 580
 581         if (!irg) {
 582                 /* no graph, skip */
 583                 return;
 584         }
 585
 586         assure_irg_outs(irg); /* ensure that out edges are consistent*/
 587
 588 /*      edges_activate(irg);*/
 589
 590         INIT_LIST_HEAD(&worklist.nodes);
 591
 592         env.worklist = &worklist;
 593         irg_walk_graph(irg, NULL, vrp_first_pass, &env);
 594
 595
 596
 597         /* while there are entries in the worklist, continue*/
 598         while ( !list_empty(&worklist.nodes) ) {
 599
 600                 list_head *pos, *next;
 601                 list_for_each_safe(pos, next, &worklist.nodes) {
 602
 603                         tmp_entry = list_entry(pos, worklist_t, nodes);
 604
 605                         if (update_vrp_data(tmp_entry->node)) {
 606                                 /* if something changed, add successors to worklist*/
 607                                 for (i = get_irn_n_outs(tmp_entry->node) - 1; i >=0; --i) {
 608                                         succ =  get_irn_out(tmp_entry->node, i);
 609
 610                                         tmp_entry2 = XMALLOC(worklist_t);
 611                                         tmp_entry2->node = succ;
 612                                         list_add(&(tmp_entry2->nodes), &worklist.nodes);
 613                                 }
 614                         }
 615
 616                         list_del(pos);
 617                         xfree(tmp_entry);
 618                 }
 619         }
 620 }
 621
 622
 623 ir_graph_pass_t *set_vrp_pass(const char *name)
 624 {
 625         return def_graph_pass(name ? name : "set_vrp", set_vrp_data);
 626 }
 627
 628 pn_Cmp vrp_cmp(ir_node *left, ir_node *right)
 629 {
 630         if (!left->vrp.valid || !right->vrp.valid) {
 631                 return pn_Cmp_False;
 632         }
 633
 634         if (left->vrp.range_type == VRP_RANGE && right->vrp.range_type == VRP_RANGE) {
 635                 if (tarval_cmp(left->vrp.range_top, right->vrp.range_bottom) == pn_Cmp_Lt) {
 636                         return pn_Cmp_Lt;
 637                 }
 638                 if (tarval_cmp(left->vrp.range_bottom, right->vrp.range_top) == pn_Cmp_Gt) {
 639                         return pn_Cmp_Gt;
 640                 }
 641         }
 642
 643         if (!tarval_is_null(tarval_and(left->vrp.bits_set, right->vrp.bits_not_set)) ||
 644                         !tarval_is_null(tarval_and(left->vrp.bits_not_set, right->vrp.bits_set))) {
 645                 return pn_Cmp_Lg;
 646         }
 647         /* TODO: We can get way more information here*/
 648
 649         return pn_Cmp_False;
 650 }