Closed Bug 669789 Opened 13 years ago Closed 13 years ago

IonMonkey: perform algebraic simplification and constant folding

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: rpearl, Assigned: rpearl)

References

(Blocks 1 open bug)

Details

Attachments

(1 file)

Follow up to Bug 659729.
We should perform expression tree manipulations while doing global value numbering in order to uncover more congruences between expressions; currently we do not discover that |x & y| is equivalent to |y & x|, for example.
If you don't know the types of the things involved, equivalences like these usually don't hold.

var x = { valueOf: function() { print("hello"); } };
var y = { valueOf: function() { print("world"); } };
x & y;
y & x;

$ js test.js
hello
world
world
hello
Attached patch patch v0Splinter Review
There's a few things I don't like about this patch, and some repeated code, but I don't really know how to improve it. Suggestions welcome. But it's pretty maintainable as is, I think.
Attachment #551218 - Flags: review?(dvander)
http://hg.mozilla.org/projects/ionmonkey/rev/c88d2ecb2472
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
This was not the right bug.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Comment on attachment 551218 [details] [diff] [review]
patch v0

Review of attachment 551218 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ion/MIR.cpp
@@ +66,5 @@
> +{
> +    if (useGVN)
> +        return left->valueNumber() == right->valueNumber();
> +    else
> +        return left->id() == right->id();

No "else" here.

@@ +454,5 @@
> +    MDefinition *rhs = getOperand(1);
> +
> +    if (lhs->isConstant() && rhs->isConstant()) {
> +        js::Value v = Int32Value( lhs->toConstant()->value().toInt32()
> +                                & rhs->toConstant()->value().toInt32());

House style is for the & to be on the preceding line. If you think this pattern is frequent, you might want to add something like a static ToInt32(const Value &v)

@@ +549,5 @@
> +            val = Int32Value ( lhs->toConstant()->value().toInt32()
> +                             + rhs->toConstant()->value().toInt32());
> +            return MConstant::New(val);
> +        } else {
> +            val = Int32Value(0);

no else { } here

@@ +558,5 @@
> +                              + rhs->toConstant()->value().toDouble());
> +            return MConstant::New(val);
> +        } else {
> +            val = DoubleValue(0.0);
> +        }

Ditto

::: js/src/ion/ValueNumbering.cpp
@@ +71,5 @@
> +
> +    MDefinition *ins = def->foldsTo(useValueNumbers);
> +
> +    if (ins == def)
> +        return def;

Would it make more sense for foldsTo to return NULL if it does not create a new node?

@@ +80,5 @@
> +
> +        // We will only fold a phi into one of its operands.
> +        JS_ASSERT(!def->isPhi());
> +
> +        def->block()->insertAfter(def->toInstruction(), ins->toInstruction());

You mentioned there are a few things you don't like about this patch, if I had to guess they would be:
 1) the boolean input to foldsTo()
 2) that foldsTo() can create a node but not insert it, necessitating this line
    here

I can't immediately see anything better though. I like that we ask nodes to fold themselves, but we should keep our eyes out for a better way to communicate whether a new node was created. Well, ideally all required actions could be performed locally, because right now nodes are changing the graph in a way that is incomplete until GVN cleans up afterward.

One idea would be to separate foldTo into two separate functions: one that can only return existing nodes versus one that can only return new nodes. Another idea would be performing the graph manipulation inside MIR, though that feels nasty. We could also use a visitor, which would totally isolate the relevant code.

@@ +145,5 @@
>          for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
> +            for (MDefinitionIterator iter(*block); iter; ) {
> +                MDefinition *ins = simplify(*iter, false);
> +
> +                if (ins != *iter || !ins->hasUses()) {

Do you need an idempotency check here?

Also, one thing I realized over the weekend is that when we remove a def from the graph, it is still in its inputs' use chains, so we might need something more intelligent to detect dead code. Like a final backwards pass that marks whether an input is actually used.

@@ +250,5 @@
>              if (!nodes.append(block->getImmediatelyDominatedBlock(i)))
>                  return false;
>          }
> +        for (MDefinitionIterator iter(block); iter; ) {
> +            MDefinition *ins = simplify(*iter, true);

Same comments as above.
Attachment #551218 - Flags: review?(dvander) → review+
(In reply to David Anderson [:dvander] from comment #5)


> 
> Would it make more sense for foldsTo to return NULL if it does not create a
> new node?
>
We would then be making two checks: whether foldsTo is NULL, and whether it replaces the operand with one of its uses, unless we put the replacement code inside foldsTo as well. 
> 
> @@ +80,5 @@
> > +
> > +        // We will only fold a phi into one of its operands.
> > +        JS_ASSERT(!def->isPhi());
> > +
> > +        def->block()->insertAfter(def->toInstruction(), ins->toInstruction());
> 
> You mentioned there are a few things you don't like about this patch, if I
> had to guess they would be:
>  1) the boolean input to foldsTo()
>  2) that foldsTo() can create a node but not insert it, necessitating this
> line
>     here
> 
> I can't immediately see anything better though. I like that we ask nodes to
> fold themselves, but we should keep our eyes out for a better way to
> communicate whether a new node was created. Well, ideally all required
> actions could be performed locally, because right now nodes are changing the
> graph in a way that is incomplete until GVN cleans up afterward.
> 
> One idea would be to separate foldTo into two separate functions: one that
> can only return existing nodes versus one that can only return new nodes.
> Another idea would be performing the graph manipulation inside MIR, though
> that feels nasty. We could also use a visitor, which would totally isolate
> the relevant code.

Turning foldsTo into separate functions is a bit lame, since only one of them will ever have an effect (similarly, the branches of the if in the current foldsTo are disjoint).

I will leave the code-as is, and I have filed Bug 677415 to investigate coming back to it later.

http://hg.mozilla.org/projects/ionmonkey/rev/526fb26e0ecf
Status: REOPENED → RESOLVED
Closed: 13 years ago13 years ago
Resolution: --- → FIXED
Shouldn't the comment on http://hg.mozilla.org/projects/ionmonkey/rev/526fb26e0ecf#l1.228 be x ^ x => 0 ?

And there is a missing comment at http://hg.mozilla.org/projects/ionmonkey/rev/526fb26e0ecf#l1.164 which should be x & x => x
(In reply to Emil Hesslow from comment #7)
> Shouldn't the comment on
> http://hg.mozilla.org/projects/ionmonkey/rev/526fb26e0ecf#l1.228 be x ^ x =>
> 0 ?
> 
> And there is a missing comment at
> http://hg.mozilla.org/projects/ionmonkey/rev/526fb26e0ecf#l1.164 which
> should be x & x => x

Thanks for the minor nits. Addressed here:
http://hg.mozilla.org/projects/ionmonkey/rev/e998eb5a314b
You need to log in before you can comment on or make changes to this bug.