contrib/gcc/tree-ssa-pre.c

76    SSA, values are never killed, so we don't need a kill set, or a
89    set.  Even in SSA form, values are not live over the entire
91    remove values from the ANTIC set once we go past the definition
141    expressions for use in the ANTIC sets, the EXP_GEN set, etc.
151    you will see "value.5 + value.7" in the set, instead of "a_55 +
164    track of values present in the set, and one that keeps track of
165    expressions present in the set.
169    set.  The sets represent values, and the elements can be values or
171    element can only appear once in each set.
173    Since each node in the set represents a value, we also want to be
174    able to map expression, set pairs to something that tells us
175    whether the value is present is a set.  We use a per-set bitmap for
183 /* A value set element.  Basically a single linked list of
190   /* A pointer to the next element of the value set.  */
195 /* A value set.  This is a singly linked list of value_set_node
197    the set.  This set must be kept in topologically sorted order.  */
205      necessary to keep the set in topologically sorted order because
206      of how the set is built.  */
212   /* True if the set is indexed, which means it contains a backing
214      set.  */
217   /* The bitmap of values that exist in the set.  May be NULL in an
218      empty or non-indexed set.  */
224 /* An unordered bitmap set.  One bitmap tracks values, the other,
235   /* The EXP_GEN set, which represents expressions/values generated in
239   /* The PHI_GEN set, which represents PHI results generated in a
243   /* The TMP_GEN set, which represents results/temporaries generated
247   /* The AVAIL_OUT set, which represents which values are available in
251   /* The ANTIC_IN set, which represents which values are anticipatable
255   /* The NEW_SETS set, which is used during insertion to augment the
256      AVAIL_OUT set of blocks with the new insertions performed during
468 /* Add expression E to the expression set of value V.  */
487 value_exists_in_set_bitmap (value_set_t set, tree v)
489   if (!set->values)
492   return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
499 value_remove_from_set_bitmap (value_set_t set, tree v)
501   gcc_assert (set->indexed);
503   if (!set->values)
506   bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
514 value_insert_into_set_bitmap (value_set_t set, tree v)
516   gcc_assert (set->indexed);
518   if (set->values == NULL)
519     set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
521   bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
525 /* Create a new bitmap set and return it.  */
536 /* Create a new set.  */
550 /* Insert an expression EXPR into a bitmapped set.  */
553 bitmap_insert_into_set (bitmap_set_t set, tree expr)
563     bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
564     bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
571 insert_into_set (value_set_t set, tree expr)
580   /* For indexed sets, insert the value into the set value bitmap.
583   if (set->indexed)
584     value_insert_into_set_bitmap (set, val);
588   set->length ++;
589   if (set->head == NULL)
591       set->head = set->tail = newnode;
595       set->tail->next = newnode;
596       set->tail = newnode;
600 /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
609 /* Perform bitmapped set operation DEST &= ORIG.  */
630 /* Perform bitmapped value set operation DEST = DEST & ~ORIG.  */
651 /* Return true if the bitmap set SET is empty.  */
654 bitmap_set_empty_p (bitmap_set_t set)
656   return bitmap_empty_p (set->values);
659 /* Copy the set ORIG to the set DEST.  */
680 set_remove (value_set_t set, tree expr)
684   /* Remove the value of EXPR from the bitmap, decrement the set
686   value_remove_from_set_bitmap (set, get_value_handle (expr));
687   set->length--;
689   for (node = set->head;
696 	    set->head = node->next;
700 	  if (node == set->tail)
701 	    set->tail = prev;
711 set_contains_value (value_set_t set, tree val)
713   /* All constants are in every set.  */
717   if (!set || set->length == 0)
720   return value_exists_in_set_bitmap (set, val);
723 /* Return true if bitmapped set SET contains the expression EXPR.  */
725 bitmap_set_contains (bitmap_set_t set, tree expr)
727   /* All constants are in every set.  */
734   return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
738 /* Return true if bitmapped set SET contains the value VAL.  */
741 bitmap_set_contains_value (bitmap_set_t set, tree val)
745   return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
751 bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
757   if (!bitmap_set_contains_value (set, lookfor))
765      expressions are in our set.  For large testcases, this is about
767      significant lose for some cases, we can choose which set to walk
768      based on the set size.  */
774 	  if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
776 	      bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
777 	      bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
784 /* Subtract bitmapped set B from value set A, and return the new set.  */
825 bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
828   if (bitmap_set_contains_value (set, val))
829     bitmap_set_replace_value (set, val, expr);
831     bitmap_insert_into_set (set, expr);
838 bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
845   if (!bitmap_set_contains_value (set, val))
846     bitmap_insert_into_set (set, expr);
852 value_insert_into_set (value_set_t set, tree expr)
861   if (!set_contains_value (set, val))
862     insert_into_set (set, expr);
869 bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
873   if (set)
879       EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
896 print_value_set (FILE *outfile, value_set_t set,
901   if (set)
903       for (node = set->head;
945 debug_value_set (value_set_t set, const char *setname, int blockindex)
947   print_value_set (stderr, set, setname, blockindex);
1032 phi_translate (tree expr, value_set_t set, basic_block pred,
1090 	    newop0 = phi_translate (find_leader (set, oldop0),
1091 				    set, pred, phiblock);
1096 		newop2 = phi_translate (find_leader (set, oldop2),
1097 					set, pred, phiblock);
1131 		    newval = phi_translate (find_leader (set, oldval),
1132 					    set, pred, phiblock);
1215 	newop0 = phi_translate (find_leader (set, oldop0),
1216 				set, pred, phiblock);
1223 	    newop1 = phi_translate (find_leader (set, oldop1),
1224 				    set, pred, phiblock);
1231 		newop2 = phi_translate (find_leader (set, oldop2),
1232 					set, pred, phiblock);
1240 		newop3 = phi_translate (find_leader (set, oldop3),
1241 					set, pred, phiblock);
1299 	newop1 = phi_translate (find_leader (set, oldop1),
1300 				set, pred, phiblock);
1303 	newop2 = phi_translate (find_leader (set, oldop2),
1304 				set, pred, phiblock);
1337 	newop1 = phi_translate (find_leader (set, oldop1),
1338 				set, pred, phiblock);
1395 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
1399   for (node = set->head;
1405       translated = phi_translate (node->expr, set, pred, phiblock);
1427    value) in a given set, and return it.  Return NULL if no leader is
1431 bitmap_find_leader (bitmap_set_t set, tree val)
1438   if (bitmap_set_contains_value (set, val))
1442 	 at the reverse mapping, which tells us the set of expressions
1444 	 value) and see if any of those expressions are in our set.
1446 	 less than the number of expressions in the set.  In fact, for
1450 	 choose which set to walk based on which set is smaller.  */
1458 	      if (bitmap_bit_p (set->expressions,
1469    value) in a given set, and return it.  Return NULL if no leader is
1473 find_leader (value_set_t set, tree val)
1484   if (set->length == 0)
1487   if (value_exists_in_set_bitmap (set, val))
1489       for (node = set->head;
1546 valid_in_set (value_set_t set, tree expr, basic_block block)
1556 	return set_contains_value (set, op1) && set_contains_value (set, op2);
1562 	return set_contains_value (set, op1);
1574 	    if (!set_contains_value (set, op0)
1575 		|| (op2 && !set_contains_value (set, op2)))
1581 		if (!set_contains_value (set, TREE_VALUE (arglist)))
1598 	    if (!set_contains_value (set, op0))
1607 		if (!set_contains_value (set, op1))
1612 		    && !set_contains_value (set, op2))
1617 		    && !set_contains_value (set, op3))
1641 /* Clean the set of expressions that are no longer valid in SET.  This
1646 clean (value_set_t set, basic_block block)
1650   node = set->head;
1654       if (!valid_in_set (set, node->expr, block))
1655 	set_remove (set, node->expr);
1662 /* Compute the ANTIC set for BLOCK.
1672    ANTIC_OUT, or to mark the antic_out set as deleted at the end
1840   /* Compute a set of representative vuse versions for each phi.  This
1984      KILL(block) = set of vuses killed in block.
2642            NEW_SETS set.
2872    any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
3148  	 add its value to the AVAIL_OUT set for the block.  Add the LHS
3372 /* Compute the AVAIL set for all basic blocks.
3438       /* Initially, the set of available values in BLOCK is that of
3519 		     and add its value to the AVAIL_OUT set for the block.
3792   value_set_node_pool = create_alloc_pool ("Value set nodes",