[Committed] Reduce memory usage of DOM

[Roger Sayle]

Hi Jeff,

On Thu, 8 Jun 2006, Jeffrey Law wrote:
> I've never been a big fan of that code, but haven't come across a better
> way to accomplish the same thing yet.

For the record, my plan for an improved implementation looks like:

(i) Change avail_expr_hash such that all comparisons between
equivalent operands hash to the same value.  Rather than call
iterative_hash_expr directly, we check for COMPARISON_CLASS_P
and then perform the equivalent of the commutative_class_p
case ourselves.

(ii) Likewise in avail_expr_eq, any two comparisons between
common arguments are considered equivalent in the avail_exprs
hash table.

(iii) Then in lookup_avail_expr, we handle comparisons specially
by making use of a new fold-const.c subroutine, called something
like

/* Given the relational operation PRECEDENT which has Boolean
value VALUE, a constant typically boolean_true_node or
boolean_false_node, determine the value of the relational
operation CONSEQUENT.  Returns either boolean_true_node or
boolean_false_node if CONSEQUENT can be determined by the
state of PRECEDENT, or NULL_TREE otherwise.

For example, if "a < b" is true, then "b >= a" must be true.
*/

tree fold_cond_implies_cond (tree precedent, tree value, tree consequent)
{
  /* Implementation goes here! :-) */
}


Now each edge in DOM's cfg need only contain a single expression,
either "(cond,true)" or "(cond,false)".  Notice, that DOM never
needs to create a new tree expression directly, or even call
invert_truthvalue to populate the "else" edges.

The above subroutine can also be used profitably in fold-const.c
itself, allowing the folding of cond1 ? (cond2 ? X : Y) : Z" even
when cond1 is not operand_equal_p (or inverted_operand_p) to cond2.

Finally, the remaining tricky bit is in record_cond, where if we
already have a condition in the hash_table, we need to decide whether
to overwrite or update it with the new condition.  For example,
if "(a != b, true)" is already in the table, its better to replace
it with "(a > b, true)" which contains more information; in logic
if A->B, then its better to record A in the hash table.  I suspect
that it's always better to overwrite, as DOM itself should have
simplied away the condition being recorded if its state could be
infered from the current contents of the hash table.


The fold_cond_implies_cond can also be used to generalize things
further, such that "(x == 3, true)" would imply that "x == 4" is
false.  Notice, that in both schemes above, these hash to different
entries in avail_expr_hash_tab, so we miss them in DOM, but I believe
we normally handle them through CP and/or VRP.  The could even be
some benefit in tweaking the "custom hash" mechanism above such
that we can enchance DOM to catch these constant inferences and
half-open value ranges.


I think it'll work.  Let me know your thoughts.

Roger
--