Closed Bug 607816 Opened 9 years ago Closed 9 years ago

Mechanism to specify calls that never return

Categories

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect, P2)

defect

Tracking

(Not tracked)

RESOLVED FIXED
Q3 11 - Serrano

People

(Reporter: rreitmai, Assigned: rreitmai)

References

Details

(Whiteboard: fixed-in-tamarin)

Attachments

(1 file, 6 obsolete files)

No description provided.
LIR does not have a means of specifying that a call will never return.

This can lead to odd code generation artifacts such as registers remaining live despite their being no way to reach a given block.

Assuming that the flow analysis that generated the LIR is correct this should not result in any bugs in the generated code, but it does mean that we could be generating useless restores.

For example 

  throw1 = callv
     push eax
     call throw
     add esp,16

     mov eax, 4  <= unreachable restore 
B2:
  ldi1 = immi5
     mov eax, 4


When we reach the throw1 (during our backwards assembly) we may have values in registers that refer to unreachable instructions.   Instead of generating restores for them, we can simply clear all register state prior to emitting the call.
Status: NEW → ASSIGNED
Blocks: 607110
Attached patch nanojit portion (obsolete) — Splinter Review
Attachment #486520 - Flags: review?(nnethercote)
Attachment #486520 - Flags: review?(wmaddox)
Attached patch codegen related change (obsolete) — Splinter Review
Attachment #486524 - Flags: review?(wmaddox)
Comment on attachment 486520 [details] [diff] [review]
nanojit portion

removing requests; test failures seen
Attachment #486520 - Flags: review?(wmaddox)
Attachment #486520 - Flags: review?(nnethercote)
Attachment #486524 - Flags: review?(wmaddox)
The patch might not be complete, some things to look at for this or a followup:

* VarTracker::alwaysThrows() could just test the new bit.  And, does that
  list match the changes in jit-calls.h?
* deadvars() analysis could/should treat a no-return function just like it
  treats a return (clear varlivein and taglivein).

Should "noreturn" be a different ARGTYPE?  (eg ARGTYPE_NEVER as opposed to ARGTYPE_V, I, UI, etc)?  I dont have a strong opinion, just wanted to make sure you considered the alternatives.
Is this perf-critical for Tamarin?
(In reply to comment #6)
> Is this perf-critical for Tamarin?

By "critical" I mean "will make a non-negligible difference in some cases".
The immediate impetus for this fix was to silence assertion failures in AR::checkForResourceLeaks(); it seems likely to give small-but-nonzero code quality improvements.
(In reply to comment #7)
> (In reply to comment #6)
> > Is this perf-critical for Tamarin?
> 
> By "critical" I mean "will make a non-negligible difference in some cases".

Sorry, thought I already replied to your question Nick, but as Steven mentions we should not see any difference in performance, as it affects non-reachable code.  It's really a correctness issue within RegAlloc.

That said, it is likely to shuffle register usage around, which could perturb the system in various ways.

So good points by all, I'll include performance runs.
(In reply to comment #5)
> The patch might not be complete, some things to look at for this or a followup:
> 
> * VarTracker::alwaysThrows() could just test the new bit.  And, does that
>   list match the changes in jit-calls.h?
> * deadvars() analysis could/should treat a no-return function just like it
>   treats a return (clear varlivein and taglivein).
> 

Good point and assuming we go ahead with this change, then its makes sense to have a follow-up bug for VarTracker and deadvars() to utilize this feature.

> Should "noreturn" be a different ARGTYPE?  (eg ARGTYPE_NEVER as opposed to
> ARGTYPE_V, I, UI, etc)?  I dont have a strong opinion, just wanted to make sure
> you considered the alternatives.

We could, but I look at this as a property of the function rather than as part of the signature, of which ARGTYPE implies to me.
I'd be highly suspicious if the return type were anything but ARGTYPE_VOID
No longer blocks: 607110
Blocks: 609028
Assignee: nobody → rreitmai
(In reply to comment #11)
> I'd be highly suspicious if the return type were anything but ARGTYPE_VOID

Agreed and I didn't mean to imply that the function return would be non-void.
Whether the function returns or not is similar in my mind as whether the function throws an exception or not. 

BTW, found the issue with the above patches...it turned out that I missed a _neverReturns = 0 assignment a to dynamically created CallInfo (InvokerCompiler).

A search of TM code shows a similar use , so I'll have to build 3 patches.
(In reply to comment #8)
> The immediate impetus for this fix was to silence assertion failures in
> AR::checkForResourceLeaks(); it seems likely to give small-but-nonzero code
> quality improvements.

The fact that there were asserts being silenced by this change means its
not just about reducing code size -- there is some bug that triggers
an assert, that must be a bug anyway.
targeted to spicy on the assumption there's an assert that needs fixing.
Target Milestone: --- → flash10.2.x-Spicy
Priority: -- → P2
When this patch is pulled into the respective repo's (TM, TR) , the associated patches must land, otherwise builds will break.
Attachment #486520 - Attachment is obsolete: true
Attachment #503707 - Flags: review?(nnethercote)
This patch minimally supports the neverReturns field of CallInfo for Tracemonkey.  JS_DEFINE_CALL_INFO was augmented with ", 0" in order to set the value to zero by default. 

Additionally dynamic instances of CallInfo creation in jstracer.cpp where modified to set the field to zero.

This patch is the minimum level of support to ensure builds works, if TM wants to make use of this feature, then subsequent patches could expose the field similar to what is done for the tamarin patch.
Attachment #503709 - Flags: review?(nnethercote)
Attached patch tamarin portion of the change (obsolete) — Splinter Review
Attachment #486524 - Attachment is obsolete: true
Attachment #503710 - Flags: review?(edwsmith)
Attachment #503707 - Flags: review?(edwsmith)
Any performance results?
Attachment #503707 - Flags: review?(nnethercote) → review+
Attachment #503709 - Flags: review?(nnethercote) → review+
Target Milestone: flash10.2.x-Spicy → flash10.x-Wasabi
This bug intends to silence assertion failures coming from the JIT, impliying that it is a correctness fix, not just eliminating some dead code.  But, what exactly is the bug that is being fixed?  

Is the problem that we are using the result of an expression at a point which is not dominated by the expression?  (basic SSA violation)
After talking about the assert and the test case in bug 609028, Rick and I think that TR is generating invalid LIR, in the sense that it contains a definition, a use, and a control flow path that skips the def, equivalent to:

  B1: if (c) {
  B2:   x = ...
      } else {
  B3:   call
      }
  B4: print(x)

This violates SSA semantics because the definition of x doesn't dominate the use of x.  adding the "noreturn" attribute to the call fixes it by deleting the B3->B4 edge, thus making B2 dominate B4.

If this is the case, this bug+patch is a valid fix, but not necessarily the only valid fix.  We just have to narrow down the realworld test case more to make we can isolate the problem.

It occurs to me that with a bit (maybe more than a bit), ValidateWriter, or a new analyzer, could build a CFG, find dominators, then exhaustively check every use to ensure it is dominated by a def.  In theory, a complaint from the register allocator is a sign of bad LIR, but a standalone LIR-only analyzer might pinpoint problems more clearly.
Here's a small TR-only patch that inserts a LIR_ret after noreturn functions, which should accomplish the same thing as a true no-return annotation.  The point is to prevent the assembler from propagating register state across an edge that is not truly there.

Again, I want to stress that this is only necessary when the LIR is organized in such a way that the edge MUST be removed, for the LIR to be valid SSA.  Simple example, based on the ABC attached to bug 614510:

    B1
   /  \
  B2  B3
   \  /
    B4

B1:
  jt condition B3
B2:
  x = ...
B3:
  call throw (never return)
B4:
  ... = x

We have a DEF in B2 and a USE in B4.  This is invalid SSA, as shown, because B2 does not dominate B4, because in LIR there is still a fallthrough path B3->B4.

Deleting edge B3->B4 makes it valid SSA.  The "noreturn" annotation from Rick, or my "insert a LIR_ret" patch, both accomplish this.  (Mine is a 2-line hack, Rick's is more precise).

Another fix is not to generate invalid SSA in the first place, by not emitting a DEF in B3 and a USE in B4.  For TR this probably involves changes to VarTracker's variable state tracking.  But, either way, valid SSA is required, and it seems critical that VarTracker and Assembler both be working with the same notion of what the shape of the CFG is.

We do need to write a validator for this!
Attachment #518739 - Flags: feedback?(rreitmai)
Flags: flashplayer-qrb+
Flags: flashplayer-injection-
Flags: flashplayer-bug-
Comment on attachment 518739 [details] [diff] [review]
Insert LIR_ret after calls that never return

Marking -ve only because I don't like the fact that it lives in the VarTracker.

My local change had it in LirHelper::vcallIns() which seems like a more natural fit, but requires more code, alwaysThrows() needs to be copied.
Attachment #518739 - Flags: feedback?(rreitmai) → feedback-
Alternate to prior patch in which the LIR_ret is injected via LirHelper.  alwaysThrows() was renamed and moved to make it visible outside of the VarTracker.
Attachment #518739 - Attachment is obsolete: true
Attachment #519196 - Flags: review?(edwsmith)
Attachment #519196 - Attachment is patch: true
Attachment #519196 - Attachment mime type: application/octet-stream → text/plain
Attachment #519196 - Flags: review?(edwsmith) → review+
Rick, is the r+ patch from comment #23 all that is required to address this issue?  Is this close to landing?
changeset: 6100:5536a71f53b9
user:      Rick Reitmaier <rreitmai>
summary:   Bug 607816 - nanojit: Mechanism to specify calls that never return (r=edwsmith)

http://hg.mozilla.org/tamarin-redux/rev/5536a71f53b9
Whiteboard: fixed-in-tamarin
Attachment #503707 - Attachment is obsolete: true
Attachment #503707 - Flags: review?(edwsmith)
Attachment #503709 - Attachment is obsolete: true
Attachment #503710 - Attachment is obsolete: true
Attachment #503710 - Flags: review?(edwsmith)
(In reply to comment #24)
> Rick, is the r+ patch from comment #23 all that is required to address this
> issue?  Is this close to landing?

A tamarin-only fix was decided to the be the best solution, change pushed.
Blocks: 607110
Summary: nanojit: Mechanism to specify calls that never return → Mechanism to specify calls that never return
Blocks: 614510
Blocks: 620860
Need to validate that this change fixes the following bugs (see dependency list); bug 614510, Bug 620860 and Bug 607110.
Target Milestone: Q2 11 - Wasabi → Q3 11 - Serrano
Rick: Any progress?
Closing this bug.

As stated in comment 27 it would be good to have the original authors of bug 620860 and bug 607110 confirm this fix.
Status: ASSIGNED → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.