Re: [PATCH] Operator Strength Reduction on trees

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

On Thursday 11 January 2007 23:58, Robert Kennedy wrote:
> I'll let Dan Berlin chime in with his own thoughts about why GCC
> should incorporate this optimization, but for my part I'll say that
> when I started experimenting with GCC I noticed a lot of loops with
> unnecessary induction variables, and this optimization succeeds at
> reducing that problem significantly. The result is a significant
> speedup for many loops.

Do you have SPEC numbers or anything like that?
Code size numbers?

> I do have one example where this optimization results in worse code
> because it makes copyrename do the wrong thing. As a minimum, some
> additional tuning will probably be needed to overcome that problem. It
> is possible that some portion of IVOPTS should also be removed because
> this optimization subsumes it. I don't know IVOPTS well enough to be
> sure.

Well, I would certainly hope so, or...

> Compilation time is nearly unaffected in my experiments with compiling
> preprocessed GCC source. A bootstrapped GCC with this optimization
> seems to be about 0.6% slower than a bootstrapped GCC without it.

...this is pretty bad.  0.6% is _a lot_.  I've spent weeks to get
speed-ups of that magnitude.  I also wouldn't expect a loops-only,
and technically pretty simple pass like OSR to be this slow.  Is
there still room for further tuning?  Maybe cache the hash value
for reduce_op_hash (ah, hash tables, my favorite hot spot)?  Any
idea how to reduce this compiler slowdown further?


General remark: You may want to check the detailed dumps flags
instead of always dumping all information.  It is sometimes useful
to only dump the function, and not all the pass specific trace info.


+  calculate_dominance_info (CDI_DOMINATORS);

Why this line?  You already have dominance info up to date if you
have loops.



+  reduce_op_table = htab_create (23, reduce_op_hash, reduce_op_eq, free);
Magic number 23...?


+static basic_block
+block_meet (basic_block block1, basic_block block2)
+{
+    if (!block1)
+      return block2;
+    if (!block2)
+      return block1;
+
+    if (block1 != block2
+	&& dominated_by_p (CDI_DOMINATORS, block2, block1))
+      return block2;
+    if (block1 != block2
+	&& dominated_by_p (CDI_DOMINATORS, block1, block2))
+      return block1;
+    return NULL;
+}

Incorrect indentation.


+	  FOR_EACH_EDGE (pred, ei, bb_for_stmt (newdef)->preds)
+            {
+              tree newarg;
+              tree use;
+
+              usep = PHI_ARG_DEF_PTR (newdef, pred->dest_idx);
+              use = USE_FROM_PTR (usep);
+
+	      if (TREE_CODE (use) == SSA_NAME
+		  && OSR_INFO (use)->header == OSR_INFO (iv)->header)
+		{

Something funny happens here with indentation too, between "use" and "if".


+/* Return true if STMT1 dominates STMT2.  Only valid when bb_for_stmt
+   (stmt1) == bb_for_stmt (stmt2).  */
+
+static bool
+locally_dominates (tree stmt1, tree stmt2)
+{
+  block_stmt_iterator bsi;
+
+  bsi = bsi_for_stmt (stmt1);
+  while (!bsi_end_p (bsi))
+    {
+      if (bsi_stmt (bsi) == stmt2)
+	return true;
+      bsi_next (&bsi);
+    }
+  return false;
+}

What is this for?  Why can't you just insert at the start of the
basic block that both statements are in?


+/* Return the last non-control statement in a basic block, or NULL if
+   there is none.  */
+
+static tree
+last_nonjump_stmt (basic_block block)
+{
+  block_stmt_iterator last = bsi_last (block);
+  tree stmt;
+
+  if (bsi_end_p (last))
+    return NULL_TREE;
+  stmt = bsi_stmt (last);
+
+  while (stmt_ends_bb_p (stmt))
+    {
+      bsi_prev (&last);
+      if (bsi_end_p (last))
+	return NULL_TREE;
+      stmt = bsi_stmt (last);
+    }
+  return stmt; /* bsi_stmt (last); */
+}

Was there ever a statement that was not bsi_last, which did end the
basic block?  Seems to me that this means the block should have been
split.  In other words, I don't believe you need the while loop here.


+      if (opcode != MINUS_EXPR && TREE_CODE (op1) == SSA_NAME
+	  && OSR_INFO (op1)->header != NULL
+	  && (c = region_const_def (op2, OSR_INFO (op1)->header)))
+	{
+	  result = do_reduce (opcode, op1, c, false);
+	}
+      else if (opcode != MINUS_EXPR && TREE_CODE (op2) == SSA_NAME
+	       && OSR_INFO (op2)->header != NULL
+	       && (c = region_const_def (op1, OSR_INFO (op2)->header)))
+        {
+          result = do_reduce (opcode, op2, c, false);
+        }

Single statements following an if don't need { } in GNU-style.

This do_apply generally looks quite complicated to me.  Especially
the code to figure out where to place the new instructions.  See my
earlier comment about locally_dominates.  If you really need to do
this much work to figure out where to put the instruction, then you
should add some comments (maybe with some examples??) to explain
what is going on.  (But I think (hope? ;-) you can simply this whole
function somewhat.)


+	  {
+            c = region_const_def (op0, OSR_INFO (op1)->header);
+	    if (c)

Another strange indentation.


+/* Return true if RHS is one of the allowed IV operations, which
+   include +, -, and copy.
+   XXX: We could also allow some other things, like <<, if we really
+   wanted to.  */
+
+static bool
+okay_iv_op (tree rhs)

So, do we lower op*power_of_2 to shifts early in the tree optimizers?
May be worth handling then.  Did you investigate this?

IIUC you are looking for SCCs in the SSA graph.  This is something
Dan will also be doing with his new value numbering code.  Are the
two of you planning to try and share some code here?

Looks nice and clean overall.  Thanks for working on this!

Gr.
Steven