667132 - IonMonkey: Fix greedy register allocation around loops

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: v1

This patch is really two things:
 (1) Fixes lots of bugs around phis in the greedy register allocator.
 (2) Introduces a new LDefinition policy, called REDEFINED. adrake suggested this as a way to deal with two cases:
    (a) box(constant-type, non-constant-data)
    (b) unbox(constant->type, non-constant-data)

     In both of these cases, we take in a register and basically do nothing. The allocator though sees a definition for these instructions and allocates a new register. "Redefinition" means that the definition specifies an existing virtual register, and the allocator ignores the definition completely. This required some rejiggering of the x86 code and I can't decide how ugly it is.

For the code: |var t; while (x) { t = t + 1; } return t;|

Before this patch:

    B0:
      5 parameter ([t:0 (arg -1)], [d:0 (arg -2)]) <|@
      0 move ()[(arg:-2) -> (ebx)] <|@
      7 box ([t:0 (edi)], [d:0 (esi)]) (c) <|@
      9 goto (B1) <|@
    B1:
      0 move ()[(esi) -> (ecx)] <|@
      12 unbox ([i:0 (ecx)]) (ecx), (edi) <|@
      13 testvandbranch (B2, B3) (arg:-1), (ebx) <|@
    B2:
      0 move ()[(edi) -> (ecx)], [(esi) -> (edx)] <|@
      14 return () (ecx), (edx) <|@
    B3:
      15 addi ([i:0 (ecx)]) (ecx), (c) <|@
      16 box ([t:0 (ebx)], [d:0 (edx)]) (ecx) <|@
      0 move ()[(ebx) -> (stack:i0)], [(edx) -> (stack:i1)] <|@
      0 move ()[(stack:i0) -> (edi)], [(stack:i1) -> (esi)] <|@
      18 goto (B1) <|@


After this patch:
    B0:
      5 parameter ([t (arg -1)], [d (arg -2)]) <|@
      0 move ()[(arg:-2) -> (edi)] <|@
      7 box ([t (ecx)], [d (esi)]) (c) <|@
      9 goto () <|@
    B1:
      11 unbox ([i:11 (r)]) (ecx), (esi) <|@
      12 testvandbranch (B2, B3) (arg:-1), (edi) <|@
    B2:
      0 move ()[(esi) -> (edx)] <|@
      13 return () (ecx), (edx) <|@
    B3:
      14 addi ([i (esi)]) (esi), (c) <|@
      15 box ([t (edi)], [d:15 (r)]) (esi) <|@
      0 move ()[(edi) -> (ecx)], [(edi) -> (esi)] <|@
      16 goto () <|@

Comment 1

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: v2

Fixes two thinkos around virtual registers.

Comment 2

[Andrew Drake [:adrake]]

Comment on attachment 542218 [details] [diff] [review]
v2

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

::: js/src/ion/LIR-Common.h
@@ +49,5 @@
>  
>  // Register spill/restore/resolve marker.
>  class LMove : public LInstructionHelper<0, 0, 0>
>  {
> +    RegisterSet freeRegs;

Presumably this is so the code generator has access to a list of temporaries it can take advantage of?

I can generate information of this form during reification or resolution without too much difficulty. It feels kind of hacky, but I can't think of a better solution to that problem.

::: js/src/ion/MIR.h
@@ +330,5 @@
>      void setEmitAtUses() {
>          setFlags(EMIT_AT_USES);
>      }
> +    bool isEffectful() {
> +        return hasFlags(EFFECTFUL);

This makes me want for the pseudo-monadic effect values Adobe's got...

::: js/src/ion/MIRGraph.h
@@ +411,4 @@
>      MBasicBlock *loopSuccessor_;
>  
> +    // The predecessor block which is the backedge of a loop header.
> +    MBasicBlock *backedge_;

Isn't this necessarily the predecessor of the loop successor block?

::: js/src/ion/x86/Lowering-x86.cpp
@@ +102,5 @@
>      }
>  
>      LUnbox *lir = new LUnbox(unbox->type());
> +    lir->setOperand(0, useType(inner));
> +    lir->setOperand(1, usePayloadInRegister(inner));

No use of VREG_DATA_OFFSET and VREG_TYPE_OFFSET in this kind of case?

Comment 3

[Andrew Drake [:adrake]]

(In reply to comment #2)
> ::: js/src/ion/MIRGraph.h
> @@ +411,4 @@
> >      MBasicBlock *loopSuccessor_;
> >  
> > +    // The predecessor block which is the backedge of a loop header.
> > +    MBasicBlock *backedge_;
> 
> Isn't this necessarily the predecessor of the loop successor block?

I've swung the other way on this one -- I actually want backedge in my register allocator, not loopSuccessor_ as the paper would have me believe. As I'm the only consumer of loopSuccessor_, want to just remove it while we're here?

Comment 4

[Andrew Drake [:adrake]]

I've rebased the patch in bug 657816 to make use of the backedge functionality.

Comment 5

[Andrew Drake [:adrake]]

Attachment: Asserting test case (generates critical edge which needs to be resolved)

This test case on at least x86_64 generates:

Assertion failure: def->policy() == LDefinition::PRESET, at /home/adrake/moz/ionmonkey/js/src/ion/GreedyAllocator.cpp:713

with this patch applied. This assertion does not trip with this patch not applied.

Comment 6

[Andrew Drake [:adrake]]

Comment on attachment 542218 [details] [diff] [review]
v2

Due to regression.

Comment 7

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: v3

After splitting critical edges the assert is gone. This is the same patch just rebased and removed stuff that shouldn't have been in there.

Comment 8

[Andrew Drake [:adrake]]

Comment on attachment 544006 [details] [diff] [review]
v3

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

Comment 9

[David Anderson [:dvander] - inactive, e-mail if emergency]

http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/38edcd488e16