620406 - Constant folding branch condition leads to assert in Assembler.cpp

Status: RESOLVED FIXED

(Core Graveyard :: Nanojit, defect, P2)

Description

[Edwin Smith]

Simple test:

test.as:
function test(s:String) {
  var x, y
  return x[y>>5]   <--- x is undefined, therefore branch-to-UPE is a jump.
}

$ asc test.as
$ avmshell -Dverifyonly test.abc
Assertion failure: !ins->callInfo()->_isPure || ins->isExtant() (.../nanojit/Assembler.cpp:2043)

The cause is related to:

1. AvmCore::integer() is marked pure, but should not be.  See bug 620403.

2. The unconditional branch makes the >> expresion dead, which should leave
   the implicit integer(y) call dead, but doesn't... the assert fires because
   the seemingly dead expression isn't dead (isExtant()==false, but isLive() == true).

Comment 1

[Edwin Smith]

Here is the relevant LIR.  Y is the undefined constant (4).  For the y>>5 expression, we generate a pure call to integer(4), then right shift it.

    integer1 = calli.none #integer ( immi5/*4*/ )
    rshi1 = rshi integer1, immi8/*5*/

Then we unconditionally branch, and emit some unreachable code, too:

    j -> unpatched
    getpropertylate_i1 = calli.all #getpropertylate_i ( parami1 immi5/*4*/ rshi1 )

The unreachable reference to rshi1 makes it "live" but doesn't assign it to any register.  In assembler.gen, we have:

  case LIR_rshi:
    ins->oprnd1()->setResultLive(); // sets integer1 live
    ins->oprnd2()->setResultLive(); // sets immi5 (4) live
    if (ins->isExtant())            // false
      asm_arith(ins);              // skipped
    break;

And the code for LIR_calli for a pure call to integer():

  case LIR_calli:
    for (int i = 0, argc = ins->argc(); i < argc; i++)
      ins->arg(i)->setResultLive();
    // It must be impure or pure-and-extant -- it couldn't be
    // pure-and-not-extant, because there's no way the codegen
    // for a call can be folded into the codegen of another
    // LIR instruction.
    NanoAssert(!ins->callInfo()->_isPure || ins->isExtant());
    asm_call(ins);
    break;

The assert imples that the only reason an instruction could be
live but !extant, is if it was folded into another instruction.
However, in this case, nothing was folded - the rshi wasn't folded,
it was in dead code, so its register assignments were cleared, but
its 'live' bit wasn't cleared.  We didn't assert in LIR_rshi because
it could have been folded in other scenarios.

Possible bugs:

1. handling of dead paths (code after an unconditional jump or after
a return) doesn't clear live bits.  (How could it?  how do we know
the instruction really is live?)

2. The assert is too strong on LIR_calli.  A call to a pure pure function
should behave just like a plain instruction.  Folding isn't the only way
a plain instruction can be !extant, therefore calls are subject to the
same situations.

Relaxing the assert is easy.  Rethinking "live" vs "extant" doesn't
seem quite as easy.  

This bug might be related to bug 607816

Comment 2

[Edwin Smith]

Attachment: Relax the assert in case LIR_call, and don't emit dead pure calls.

> 2. The assert is too strong on LIR_calli.

This is a patch that fixes bug #2, if we decide it's really a bug.

Rick - can you figure out if this is in any way related to bug 607816?

Nick - looking for input... whats the bug, really?  A third possible bug is that our frontend is emitting dead code.  But, I think we've had a few precedents where we decided the backend should "just work" even if the LIR code is dumb.

> 1. handling of dead paths (code after an unconditional jump or after
> a return) doesn't clear live bits.

Unreachable code is code that follows an unconditional branch, without a label:

  j -> somewhere
  /* no label */
  unreachable code

Since we assemble bottom-up, we dont know if some code is unreachable
until we see that unconditional branch. By then, there could be many
instructions we have marked (live=1, extant=1).

Anything that spilled will stay extant at this point.  (we clear register
assignments but we dont clear the inAr flag).  So, the only instructions
that get into this (live=1, extant=0) state are ones that haven't spilled.

The complexity of true unreachable code elimination seems beyond the scope
of the backend, without a lot of work.

Comment 3

[Nicholas Nethercote [inactive]]

Comment on attachment 498757 [details] [diff] [review]
Relax the assert in case LIR_call, and don't emit dead pure calls.

>--- a/nanojit/Assembler.cpp	Sat Dec 18 16:56:53 2010 -0500
>+++ b/nanojit/Assembler.cpp	Mon Dec 20 11:53:54 2010 -0500
>@@ -2036,12 +2036,14 @@
>                     countlir_call();
>                     for (int i = 0, argc = ins->argc(); i < argc; i++)
>                         ins->arg(i)->setResultLive();
>-                    // It must be impure or pure-and-extant -- it couldn't be
>-                    // pure-and-not-extant, because there's no way the codegen
>-                    // for a call can be folded into the codegen of another
>-                    // LIR instruction.
>-                    NanoAssert(!ins->callInfo()->_isPure || ins->isExtant());
>-                    asm_call(ins);
>+                    // Calls are not folded into other instructions,
>+                    // but they can be referenced by simple instructions that
>+                    // are foldable, such as LIR_rshi.  This can leave a pure
>+                    // call live but not extant.  We treat it like any other
>+                    // instruction in that situation.
>+                    if (!ins->callInfo()->_isPure || ins->isExtant()) {
>+                        asm_call(ins);
>+                    }
>                     break;

I didn't think of the case where the call's result was only used in code
that was dead due to an always-taken branch.  You are right, detecting
dead code of this sort is difficult with our backwards assembly pass, so
removing the assert is the best way to go.

But I think the comment isn't quite right because it doesn't mention the
dead code.  I suggest:

    You might think that a call cannot be pure-and-not-extant, because
    there's no way the codegen for a call can be folded into the codegen of
    another LIR instruction.  However, it's possible that a pure call, C,
    has a result that is only be used (directly or indirectly) in a section
    of code that is dead due to an always-taken branch.  C is dead, but the
    assembly pass doesn't realize is dead.  So C may end up non-extant, in
    which case we don't generate code for it.  See bug 620406 for an
    example.

It would also be worth adding a comment to isLive() to indicate that it is
conservative, ie. it can say that an instruction is live when it's really
dead due to always-taken branches.

Comment 4

[Edwin Smith]

Agreed.  Assembler's notion of "live" really just means an instruction has been used by another instruction the assembler visited.  The whole method could be unreachable, for all the assembler knows -- reachability is just not part of the equation at all.

Comment 5

[Edwin Smith]

Attachment: (v2) Relax the assert in case LIR_call, and don't emit dead pure calls.

Updated the comment, added comment to LIns.isLive().

Passed acceptance runs on tamarin.

Comment 6

[Nicholas Nethercote [inactive]]

Comment on attachment 499135 [details] [diff] [review]
(v2) Relax the assert in case LIR_call, and don't emit dead pure calls.

>         // Generally, void instructions (statements) are always live and
>         // non-void instructions (expressions) are live if used by another
>         // live instruction.  But there are some trickier cases.
>+        // Any non-void instruction can be marked isResultLive=1 even
>+        // when it is unreachable.  The assembler marks it live if it
>+        // sees any uses, regardless of whether those uses are in reachable
>+        // code or not.

Nit: Can you clarify slightly, eg. "when it is unreachable, eg. due to an always taken branch"?

Comment 7

[Edwin Smith]

sure, no problem.

Comment 8

[Edwin Smith]

NC: http://hg.mozilla.org/projects/nanojit-central/rev/5797090820d1

Comment 9

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/41739de5f01d

Comment 10

[Chris Leary [:cdleary] (not checking bugmail)]

cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/41739de5f01d