Compute the def-use list on-demand by walking the dominator tree.

Compute the def-use list on-demand by walking the dominator tree.

This replaces the previous implementation that maintained the def-use lists.

R=vegorov@google.com,kmillikin@google.com

Committed: https://code.google.com/p/dart/source/detail?r=11241

[zerny-google, 2012-08-23 12:27:23]

Hopefully this marks the end of the def-use list triathlon.

[Kevin Millikin (Google), 2012-08-23 13:35:34]

LGTM, with some comments below.

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:155: static void ComputeUsesInBlock(BlockEntryInstr*
block) {
Name is not quite right, because it computes uses for a whole (sub)tree. 
ComputeUsesRecursive?

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:168: ComputeInstructionUses(instr);
Name is not quite right.  It sounds like it's computing the instruction uses for
'instr', but it's recording the input uses of instr.  RecordInputUsed(instr);
RecordEnvironmentUses(instr)?

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:175: // Add phi uses on back-edges.
Not just back edges, all successor edges.

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:203: DefUseCleanup cleanup(this);
I don't really like the verification.  It's a bit confusing, and we normally use
ASSERTs to indicate/check pre- and post-conditions (i.e., they should be true in
release builds but are just not checked).

I think we could probably just get rid of it.

[Vyacheslav Egorov (Google), 2012-08-23 13:51:10]

lgtm

I am concerned however that use lists are not maintained automatically and
transparently. The probability of getting inconsistent state of use-chain seems
pretty high to me.

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/compiler.cc...
runtime/vm/compiler.cc:185: ASSERT(flow_graph->ComputeUseLists());
ASSERT is compiled out in Release mode so this will not be executed and in the
same time ComputeUseList always returns true? This is confusing.

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:147: use->set_instruction(instr);
This code for placing use into the list is duplicated in several places.
Consider refactoring it into a helper function.

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:207: return true;
what is the reason to have return values which is always true?

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph.h
File runtime/vm/flow_graph.h (right):

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.h:61: bool ComputeUseLists();
please add a comment explaining the meaning of the return value.

[zerny-google, 2012-08-23 14:07:37]

On 2012/08/23 13:51:10, Vyacheslav Egorov (Google) wrote:
> lgtm
> 
> I am concerned however that use lists are not maintained automatically and
> transparently. The probability of getting inconsistent state of use-chain
seems
> pretty high to me.

After some discussion we seemed to agree that it would be easier and more
efficient to not maintain them and compute them before use instead. This avoids
the complex and error prone bookkeeping in CL 10828365.


>
https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/compiler.cc...
> runtime/vm/compiler.cc:185: ASSERT(flow_graph->ComputeUseLists());
> ASSERT is compiled out in Release mode so this will not be executed and in the
> same time ComputeUseList always returns true? This is confusing.

Yes. Those were intended simply to check that a transformation phase has not
messed up the UseVal's, eg, by forgetting to copy it if used in several
instructions. As Kevin wrote, we don't really need the verification code (albit
it is nice to catch the missing CopyValue() calls early) and so these asserts
and the code can be removed.


>
https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
> runtime/vm/flow_graph.cc:147: use->set_instruction(instr);
> This code for placing use into the list is duplicated in several places.
> Consider refactoring it into a helper function.

Sure.


>
https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
> runtime/vm/flow_graph.cc:207: return true;
> what is the reason to have return values which is always true?

It was simply to validate the use of UseVals.


>
https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
> runtime/vm/flow_graph.h:61: bool ComputeUseLists();
> please add a comment explaining the meaning of the return value.

If the verification code should stay I will be sure to add a comment to that
effect.

[zerny-google, 2012-08-23 16:11:20]

Update based on your reviews.

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:147: use->set_instruction(instr);
On 2012/08/23 13:51:10, Vyacheslav Egorov (Google) wrote:
> This code for placing use into the list is duplicated in several places.
> Consider refactoring it into a helper function.

Done. (Added AddToInputUse/AddToEnvUse on UseVal)

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:155: static void ComputeUsesInBlock(BlockEntryInstr*
block) {
On 2012/08/23 13:35:34, kmillikin wrote:
> Name is not quite right, because it computes uses for a whole (sub)tree. 
> ComputeUsesRecursive?

Done.

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:168: ComputeInstructionUses(instr);
On 2012/08/23 13:35:34, kmillikin wrote:
> Name is not quite right.  It sounds like it's computing the instruction uses
for
> 'instr', but it's recording the input uses of instr.  RecordInputUsed(instr);
> RecordEnvironmentUses(instr)?

Yes. Similar to this, instr_use has been replaced by input_use throughout now.

https://chromiumcodereview.appspot.com/10879036/diff/1/runtime/vm/flow_graph....
runtime/vm/flow_graph.cc:203: DefUseCleanup cleanup(this);
On 2012/08/23 13:35:34, kmillikin wrote:
> I don't really like the verification.  It's a bit confusing, and we normally
use
> ASSERTs to indicate/check pre- and post-conditions (i.e., they should be true
in
> release builds but are just not checked).
> 
> I think we could probably just get rid of it.

I can pull this out, but if so, it is really hard to catch the error of
duplicating the instance of a Value. The effect of doing so is simply that the
instruction_/use_index_ are overwritten and we can end up missing a use when
replacing values.

What should we do?

[Kevin Millikin (Google), 2012-08-24 08:53:05]

OK, LGTM.  It seems like a good idea to keep the verification asserts after all.

https://chromiumcodereview.appspot.com/10879036/diff/4002/runtime/vm/flow_gra...
File runtime/vm/flow_graph.cc (right):

https://chromiumcodereview.appspot.com/10879036/diff/4002/runtime/vm/flow_gra...
runtime/vm/flow_graph.cc:71: class DefUseCleanup : public FlowGraphVisitor {
While it's a noun, this isn't a very tangible name for the class.

I think it's fine to just make it a free function that iterates blocks (in any
order) and instructions in each block.

You could also consider replacing the CleanupInstruction function with virtual
functions on the instruction classes.  The mutually exclusive AsJoinEntry,
AsDefinition is a bit distracting.

https://chromiumcodereview.appspot.com/10879036/diff/4002/runtime/vm/flow_gra...
runtime/vm/flow_graph.cc:75: void CleanupInstruction(Instruction* instr) {
I like "ResetInstruction" slightly better.  Cleanup sounds a bit like something
that goes after an algorithm, not before.

https://chromiumcodereview.appspot.com/10879036/diff/4002/runtime/vm/flow_gra...
runtime/vm/flow_graph.cc:91: use->set_instruction(NULL);
Here you could just use a virtual Reset function on values:

for (...) {
  instr->InputAt(i)->Reset();
}