2 * Copyright (C) 1995-2009 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief analyze graph to provide value range information
30 #include "irgraph_t.h"
39 static void *VISITED = &v;
41 typedef struct worklist_t worklist_t;
43 struct list_head nodes;
51 int update_vrp_data( ir_node *node) {
53 tarval *new_bits_set = get_tarval_bad();
54 tarval *new_bits_not_set = get_tarval_bad();
55 tarval *new_range_bottom = get_tarval_bad();
56 tarval *new_range_top = get_tarval_bad();
57 ir_node *new_bits_node = NULL;
58 ir_node *new_range_node = NULL;
59 enum range_types new_range_type = VRP_UNDEFINED;
60 enum range_ops new_range_op = VRP_NONE;
63 // TODO: Check if all predecessors have valid VRP information
66 if (!mode_is_int(get_irn_mode(node))) {
67 return 0; // we don't optimize for non-int-nodes
71 tarval *tv = get_Const_tarval(node);
74 new_bits_not_set = tarval_not(tv);
75 new_range_bottom = tv;
77 new_range_type = VRP_RANGE;
78 } else if (is_And(node)) {
79 ir_node *pred0 = get_And_left(node);
80 ir_node *pred1 = get_And_right(node);
82 new_bits_set = tarval_and(pred0->vrp.bits_set, pred1->vrp.bits_set);
83 new_bits_not_set = tarval_or(pred0->vrp.bits_not_set, pred1->vrp.bits_not_set);
87 tmp = tarval_not(pred0->vrp.bits_set);
88 tmp = tarval_eor(pred0->vrp.bits_not_set, tmp);
89 //check if one of the predecessors is completely determined
90 if (tarval_is_null(tmp)) {
91 new_bits_node = pred1;
94 tmp = tarval_not(pred1->vrp.bits_set);
95 tmp = tarval_eor(pred1->vrp.bits_not_set, tmp);
96 if (tarval_is_null(tmp)) {
97 new_bits_node = pred0;
99 } else if (is_Add(node)) {
100 ir_node *pred0 = get_Add_left(node);
101 ir_node *pred1 = get_Add_right(node);
103 int overflow_top, overflow_bottom;
104 if (pred0->vrp.range_type == VRP_UNDEFINED || pred1->vrp.range_type ==
105 VRP_UNDEFINED || pred0->vrp.range_type == VRP_VARYING ||
106 pred1->vrp.range_type == VRP_VARYING) {
110 tarval *new_top = tarval_add(pred0->vrp.range_top, pred1->vrp.range_top);
111 overflow_top = tarval_carry();
112 tarval *new_bottom = tarval_add(pred0->vrp.range_bottom, pred1->vrp.range_bottom);
113 overflow_bottom = tarval_carry();
115 if (!overflow_top && !overflow_bottom && pred0->vrp.range_type == VRP_RANGE
116 &&pred1->vrp.range_type == VRP_RANGE) {
117 new_range_bottom = new_bottom;
118 new_range_top = new_top;
119 new_range_type = VRP_RANGE;
122 if (overflow_top || overflow_bottom) {
123 // TODO Implement overflow handling
124 new_range_type = VRP_UNDEFINED;
126 } else if (is_Sub(node)) {
127 ir_node *pred0 = get_Sub_left(node);
128 ir_node *pred1 = get_Sub_right(node);
130 if (pred0->vrp.range_type == VRP_UNDEFINED || pred1->vrp.range_type ==
135 int overflow_top, overflow_bottom;
136 tarval *new_top = tarval_sub(pred0->vrp.range_top, pred1->vrp.range_top, NULL);
137 overflow_top = tarval_carry();
138 tarval *new_bottom = tarval_sub(pred0->vrp.range_bottom, pred1->vrp.range_bottom, NULL);
139 overflow_bottom = tarval_carry();
141 if (!overflow_top && !overflow_bottom && pred0->vrp.range_type == VRP_RANGE
142 &&pred1->vrp.range_type == VRP_RANGE) {
143 new_range_bottom = new_bottom;
144 new_range_top = new_top;
145 new_range_type = VRP_RANGE;
148 if (overflow_top || overflow_bottom) {
149 // TODO Implement overflow handling
151 } else if (is_Or(node)) {
152 ir_node *a = get_Or_left(node);
153 ir_node *b = get_Or_right(node);
155 new_bits_set = tarval_or(a->vrp.bits_set, b->vrp.bits_set);
156 new_bits_not_set = tarval_and(a->vrp.bits_not_set, b->vrp.bits_not_set);
159 tmp = tarval_not(a->vrp.bits_set);
160 tmp = tarval_eor(a->vrp.bits_not_set, tmp);
161 //check if one of the predecessors is completely determined
162 if (tarval_is_null(tmp)) {
166 tmp = tarval_not(b->vrp.bits_set);
167 tmp = tarval_eor(b->vrp.bits_not_set, tmp);
168 if (tarval_is_null(tmp)) {
172 } else if (is_Rotl(node)) {
173 ir_node *a = get_Rotl_left(node);
174 ir_node *b = get_Rotl_right(node);
176 // We can only compute this if the right value is a constant
178 tarval *bits_set, *bits_not_set;
179 bits_set = tarval_rotl(a->vrp.bits_set, get_Const_tarval(b));
180 bits_not_set = tarval_rotl(a->vrp.bits_not_set, get_Const_tarval(b));
182 new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
183 new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
186 } else if (is_Shl(node)) {
187 ir_node *a = get_Shl_left(node);
188 ir_node *b = get_Shl_right(node);
190 // We can only compute this if the right value is a constant
192 tarval *bits_set, *bits_not_set;
193 bits_set = tarval_shl(a->vrp.bits_set, get_Const_tarval(b));
194 bits_not_set = tarval_shl(a->vrp.bits_not_set, get_Const_tarval(b));
195 ir_mode *m = get_tarval_mode(node->vrp.bits_not_set);
197 new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
198 new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
200 bits_not_set = tarval_not( tarval_shl(
201 get_tarval_all_one(m),
202 get_Const_tarval(b)));
203 new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);
207 } else if (is_Shr(node)) {
208 ir_node *a = get_Shr_left(node);
209 ir_node *b = get_Shr_right(node);
211 // We can only compute this if the right value is a constant
213 tarval *bits_set, *bits_not_set;
214 bits_set = tarval_shr(a->vrp.bits_set, get_Const_tarval(b));
215 bits_not_set = tarval_shr(a->vrp.bits_not_set, get_Const_tarval(b));
216 ir_mode *m = get_tarval_mode(node->vrp.bits_not_set);
218 new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
219 new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
221 bits_not_set = tarval_not( tarval_shr(
222 get_tarval_all_one(m),
223 get_Const_tarval(b)));
224 new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);
227 } else if (is_Shrs(node)) {
228 ir_node *a = get_Shrs_left(node);
229 ir_node *b = get_Shrs_right(node);
231 // We can only compute this if the right value is a constant
233 tarval *bits_set, *bits_not_set;
234 bits_set = tarval_shrs(a->vrp.bits_set, get_Const_tarval(b));
235 bits_not_set = tarval_shrs(a->vrp.bits_not_set, get_Const_tarval(b));
236 ir_mode *m = get_tarval_mode(node->vrp.bits_not_set);
238 new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
239 new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
241 bits_not_set = tarval_not( tarval_shrs(
242 get_tarval_all_one(m),
243 get_Const_tarval(b)));
244 new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);
247 } else if (is_Eor(node)) {
248 ir_node *a = get_Eor_left(node);
249 ir_node *b = get_Eor_right(node);
251 tarval *bits_set, *bits_not_set;
252 bits_not_set = tarval_or(
253 tarval_and(a->vrp.bits_set, b->vrp.bits_set),
254 tarval_and(a->vrp.bits_not_set,
255 b->vrp.bits_not_set));
257 bits_set = tarval_or(
258 tarval_and(a->vrp.bits_set, b->vrp.bits_not_set),
259 tarval_and(a->vrp.bits_not_set, b->vrp.bits_set));
261 new_bits_set = tarval_or(bits_set, node->vrp.bits_set);
262 new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
264 } else if (is_Id(node)) {
265 ir_node *pred = get_Id_pred(node);
266 new_bits_set = pred->vrp.bits_set;
267 new_bits_not_set = pred->vrp.bits_not_set;
268 new_range_top = pred->vrp.range_top;
269 new_range_bottom = pred->vrp.range_bottom;
270 new_range_type = pred->vrp.range_type;
272 } else if (is_Not(node)) {
273 ir_node *pred = get_Not_op(node);
274 new_bits_set = tarval_or(pred->vrp.bits_not_set, node->vrp.bits_set);
275 new_bits_not_set = tarval_or(pred->vrp.bits_set, node->vrp.bits_not_set);
277 } else if (is_Conv(node)) {
278 ir_node *pred = get_Conv_op(node);
279 if (!mode_is_int(get_irn_mode(pred)))
282 ir_mode *old_mode = get_irn_mode(pred);
283 ir_mode *new_mode = get_irn_mode(node);
285 // The second and is needed if target type is smaller
286 tarval *bits_not_set = tarval_not(
287 tarval_convert_to(get_tarval_all_one(old_mode),
290 bits_not_set = tarval_or(bits_not_set, tarval_convert_to(pred->vrp.bits_not_set, new_mode));
291 new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set);
292 new_bits_set = tarval_and(
293 tarval_not(bits_not_set), tarval_convert_to(pred->vrp.bits_set, new_mode));
295 if (tarval_cmp(pred->vrp.range_top, get_tarval_max(new_mode)) == pn_Cmp_Le) {
296 node->vrp.range_top = pred->vrp.range_top;
299 if (tarval_cmp(pred->vrp.range_bottom, get_tarval_min(new_mode)) == pn_Cmp_Ge) {
300 node->vrp.range_bottom = pred->vrp.range_bottom;
303 } else if (is_Confirm(node)) {
304 pn_Cmp cmp = get_Confirm_cmp(node);
305 ir_node *bound = get_Confirm_bound(node);
307 /** @todo: Handle non-Const bounds */
309 if (cmp == pn_Cmp_Lg) {
310 /** @todo: Is there some way to preserve the information? */
311 new_range_type = VRP_ANTIRANGE;
312 if (is_Const(bound)) {
313 new_range_top = get_Const_tarval(bound);
314 new_range_bottom = get_Const_tarval(bound);
316 } else if (cmp == pn_Cmp_Le) {
317 if (node->vrp.range_type == VRP_UNDEFINED) {
318 new_range_type = VRP_RANGE;
319 if (is_Const(bound)) {
320 new_range_top = get_Const_tarval(bound);
322 new_range_bottom = get_tarval_min(get_irn_mode(node));
323 } else if (node->vrp.range_type == VRP_RANGE) {
324 if (is_Const(bound)) {
325 if (tarval_cmp(node->vrp.range_top,
326 get_Const_tarval(bound)) == pn_Cmp_Le) {
327 new_range_top = get_Const_tarval(bound);
329 new_range_bottom = get_tarval_min(get_irn_mode(node));
331 } else if (node->vrp.range_type == VRP_ANTIRANGE) {
332 /** @todo: How do we manage not to get a never ending loop? */
337 } else if (is_Phi(node)) {
338 // combine all ranges
340 int num = get_Phi_n_preds(node);
343 tarval *range_top, *range_bottom, *bits_set, *bits_not_set;
344 enum range_types range_type;
348 pred = get_Phi_pred(node,0);
349 range_top = pred->vrp.range_top;
350 range_bottom = pred->vrp.range_bottom;
351 range_type = pred->vrp.range_type;
352 bits_set = pred->vrp.bits_set;
353 bits_not_set = pred->vrp.bits_not_set;
355 for(i = 1; i < num; i++) {
356 pred = get_Phi_pred(node, i);
357 if (range_type == VRP_RANGE && pred->vrp.range_type ==
359 cmp = tarval_cmp(range_top, pred->vrp.range_top);
360 if (cmp == pn_Cmp_Lt) {
361 range_top = pred->vrp.range_top;
363 cmp = tarval_cmp(range_bottom, pred->vrp.range_bottom);
364 if (cmp == pn_Cmp_Gt) {
365 range_bottom = pred->vrp.range_bottom;
368 range_type = VRP_VARYING;
373 new_range_type = range_type;
374 new_range_top = range_top;
375 new_range_bottom = range_bottom;
378 // unhandled, therefore never updated
384 /* TODO: Check, if there can be information derived from any of these:
385 is_Abs(node) is_Alloc(node) is_Anchor(node) is_Borrow(node) is_Bound(node)
386 is_Break(node) is_Builtin(node) is_Call(node) is_CallBegin(node)
387 is_Carry(node) is_Cast(node) is_Cmp(node) is_Cond(node)
388 is_CopyB(node) is_Div(node) is_DivMod(node) is_Dummy(node)
389 is_End(node) is_EndExcept(node) is_EndReg(node) is_Filter(node) is_Free(node)
390 is_IJmp(node) is_InstOf(node) is_Jmp(node) is_Load(node) is_Minus(node)
391 is_Mod(node) is_Mul(node) is_Mulh(node) is_Mux(node) is_NoMem(node)
392 is_Pin(node) is_Proj(node) is_Quot(node)
393 is_Raise(node) is_Return(node) is_Sel(node) is_Start(node) is_Store(node)
394 is_SymConst(node) is_Sync(node) is_Tuple(node)
396 int something_changed = 0;
398 // Merge the newly calculated values with those that might already exist
400 if (new_bits_set != tarval_bad) {
401 new_bits_set = tarval_or(new_bits_set, node->vrp.bits_set);
402 if (tarval_cmp(new_bits_set, node->vrp.bits_set) != pn_Cmp_Eq) {
403 something_changed = 1;
404 node->vrp.bits_set = new_bits_set;
408 if (new_bits_not_set != tarval_bad) {
409 new_bits_not_set = tarval_or(new_bits_not_set, node->vrp.bits_not_set);
411 if (tarval_cmp(new_bits_not_set, node->vrp.bits_not_set) != pn_Cmp_Eq) {
412 something_changed = 1;
413 node->vrp.bits_not_set = new_bits_not_set;
417 if (node->vrp.bits_node == NULL && new_bits_node != NULL) {
418 something_changed = 1;
419 node->vrp.bits_node = new_bits_node;
422 if (node->vrp.range_type == VRP_UNDEFINED &&
423 new_range_type != VRP_UNDEFINED) {
424 something_changed = 1;
425 node->vrp.range_type = new_range_type;
426 node->vrp.range_bottom = new_range_bottom;
427 node->vrp.range_top = new_range_top;
428 node->vrp.range_op = new_range_op;
429 node->vrp.range_node = new_range_node;
431 } else if (node->vrp.range_type == VRP_RANGE) {
432 if (new_range_type == VRP_RANGE) {
433 if ((new_range_node == NULL && node->vrp.range_node == NULL) ||
434 (new_range_node == node->vrp.range_node &&
435 new_range_op == node->vrp.range_op)) {
436 if (tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Lt) {
437 something_changed = 1;
438 node->vrp.range_bottom = new_range_bottom;
440 if (tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Gt) {
441 something_changed = 1;
442 node->vrp.range_top = new_range_top;
446 // prefer the absolute value
447 if (new_range_node == NULL && node->vrp.range_node != NULL) {
448 something_changed = 1;
449 node->vrp.range_node = NULL;
450 node->vrp.range_top = new_range_top;
451 node->vrp.range_bottom = new_range_bottom;
455 if (new_range_type == VRP_ANTIRANGE) {
456 // if they are overlapping, cut the range.
457 // TODO: Maybe we can preserve more information here
458 if (new_range_node == NULL && node->vrp.range_node == NULL) {
459 if (tarval_cmp(node->vrp.range_bottom, new_range_top) == pn_Cmp_Gt &&
460 tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Gt) {
461 something_changed = 1;
462 node->vrp.range_bottom = new_range_top;
464 } else if (tarval_cmp(node->vrp.range_top, new_range_bottom) == pn_Cmp_Gt &&
465 tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Lt) {
466 something_changed = 1;
467 node->vrp.range_top = new_range_bottom;
470 // We can not handle the case where the anti range is in the
474 // prefer the absolute value
475 if (new_range_node == NULL && node->vrp.range_node != NULL) {
476 something_changed = 1;
477 node->vrp.range_node = NULL;
478 node->vrp.range_top = new_range_top;
479 node->vrp.range_bottom = new_range_bottom;
482 } else if (node->vrp.range_type == VRP_ANTIRANGE) {
483 if (new_range_type == VRP_ANTIRANGE) {
484 if ((new_range_node == NULL && node->vrp.range_node == NULL) ||
485 (new_range_node == node->vrp.range_node &&
486 new_range_op == node->vrp.range_op)) {
487 if (tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Gt) {
488 something_changed = 1;
489 node->vrp.range_bottom = new_range_bottom;
491 if (tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Lt) {
492 something_changed = 1;
493 node->vrp.range_top = new_range_top;
497 // prefer the absolute value
498 if (new_range_node == NULL && node->vrp.range_node != NULL) {
499 something_changed = 1;
500 node->vrp.range_node = NULL;
501 node->vrp.range_top = new_range_top;
502 node->vrp.range_bottom = new_range_bottom;
506 if (new_range_type == VRP_RANGE) {
507 if ((new_range_node == NULL && node->vrp.range_node == NULL) ||
508 (new_range_node == node->vrp.range_node &&
509 new_range_op == node->vrp.range_op)) {
510 if (tarval_cmp(node->vrp.range_bottom, new_range_top) == pn_Cmp_Gt) {
511 something_changed = 1;
512 node->vrp.range_bottom = new_range_top;
514 if (tarval_cmp(node->vrp.range_top, new_range_bottom) == pn_Cmp_Lt) {
515 something_changed = 1;
516 node->vrp.range_top = new_range_bottom;
520 // prefer the absolute value
521 if (new_range_node == NULL && node->vrp.range_node != NULL) {
522 something_changed = 1;
523 node->vrp.range_node = NULL;
524 node->vrp.range_top = new_range_top;
525 node->vrp.range_bottom = new_range_bottom;
530 assert(tarval_is_null(
531 tarval_and(node->vrp.bits_set, node->vrp.bits_not_set)));
533 return something_changed;
536 void vrp_first_pass(ir_node *n, void *e) {
538 worklist_t *tmp_entry;
540 struct vrp_env_t *env;
545 env = (struct vrp_env_t *) e;
548 set_irn_link(n, VISITED);
552 for (i = get_irn_n_outs(n) - 1; i >=0; --i) {
553 succ = get_irn_out(n, i);
554 if (get_irn_link(succ) == VISITED) {
557 tmp_entry = (struct worklist_t *)malloc(sizeof(struct worklist_t));
559 list_add(&(tmp_entry->nodes), &(env->worklist->nodes));
567 void set_vrp_data(ir_graph *irg) {
572 worklist_t *tmp_entry, *tmp_entry2, *q;
573 struct vrp_env_t *env;
575 env = malloc(sizeof(struct vrp_env_t));
585 assure_irg_outs(irg); // ensure that out edges are consistent
587 // edges_activate(irg);
589 INIT_LIST_HEAD(&worklist.nodes);
591 env->worklist = &worklist;
592 irg_walk_graph(irg, NULL, vrp_first_pass, env);
596 // while there are entries in the worklist, continue
597 while( !list_empty(&worklist.nodes) ) {
599 struct list_head *pos;
600 list_for_each_safe(pos, q, &worklist.nodes) {
602 tmp_entry = list_entry(pos, struct worklist_t, nodes);
604 if (update_vrp_data(tmp_entry->node)) {
605 // if something changed, add successors to worklist
606 for (i = get_irn_n_outs(tmp_entry->node) - 1; i >=0; --i) {
607 succ = get_irn_out(tmp_entry->node, i);
609 tmp_entry2 = (struct worklist_t *)malloc(sizeof(struct worklist_t));
610 tmp_entry2->node = succ;
611 list_add(&(tmp_entry2->nodes), &worklist.nodes);
622 ir_graph_pass_t *set_vrp_pass(const char *name) {
623 return def_graph_pass(name ? name : "set_vrp", set_vrp_data);
626 pn_Cmp vrp_cmp(ir_node *left, ir_node *right) {
627 if (!left->vrp.valid || !right->vrp.valid) {
631 if (!(left->vrp.range_type == VRP_UNDEFINED ||
632 left->vrp.range_type == VRP_VARYING) && !(
633 right->vrp.range_type == VRP_UNDEFINED ||
634 right->vrp.range_type == VRP_VARYING)) {
636 tarval *lefttop = left->vrp.range_top;
637 tarval *leftbottom = left->vrp.range_bottom;
638 tarval *righttop = right->vrp.range_top;
639 tarval *rightbottom = right->vrp.range_bottom;
640 if (left->vrp.range_type == VRP_RANGE && right->vrp.range_type ==
642 if (tarval_cmp(lefttop, rightbottom) == pn_Cmp_Lt) {
645 if (tarval_cmp(leftbottom, righttop) == pn_Cmp_Gt) {
652 if (!tarval_is_null(tarval_and(left->vrp.bits_set, right->vrp.bits_not_set)) ||
653 !tarval_is_null(tarval_and(left->vrp.bits_not_set, right->vrp.bits_set))) {
656 // TODO: We can get way more information here