Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

DeadCodeElimination does not see into method ensures #1786

Closed
headius opened this issue Jul 3, 2014 · 17 comments
Closed

DeadCodeElimination does not see into method ensures #1786

headius opened this issue Jul 3, 2014 · 17 comments

Comments

@headius
Copy link
Member

@headius headius commented Jul 3, 2014

For this code:

def foo
  osync = @sync
  p osync
  return self
ensure
  @sync = osync
end

DCE appears to be wiping out necessary initialization of "osync" that I'm doing in my EnsureTempsAssigned pass.

Here's the IR before DCE, with assignments intact:

Instructions:
BB [1:LBL_5:-1]
    %t_osync_2 = nil
    %v_0 = nil
BB [2:LBL_6:-1]
    %self = recv_self
    check_arity(0, 0, -1, false, -1)
    %t_%block_1 = recv_closure
    thread_poll
BB [3:LBL_0:-1]
    line_num(1)
    %t_osync_2 = get_field(%self, @sync)
    line_num(2)
    noresult_call(FUNCTIONAL, 'p', %self, [%t_osync_2])
    line_num(3)
    %v_0 = copy(%self)
BB [4:LBL_4:-1]
    line_num(5)
    put_field(%self, @sync) = %t_osync_2
    return(%v_0)
BB [5:LBL_3:-1]
    %v_0 = recv_jruby_exc
    line_num(5)
    put_field(%self, @sync) = %t_osync_2
    throw(%v_0)
BB [8:LBL_7:-1]
    return(nil)

And here it is after:

Instructions:
BB [1:LBL_5:-1]
BB [2:LBL_6:-1]
    %self = recv_self
    check_arity(0, 0, -1, false, -1)
    thread_poll
BB [3:LBL_0:-1]
    line_num(1)
    %t_osync_2 = get_field(%self, @sync)
    line_num(2)
    noresult_call(FUNCTIONAL, 'p', %self, [%t_osync_2])
    line_num(3)
    %v_0 = copy(%self)
BB [4:LBL_4:-1]
    line_num(5)
    put_field(%self, @sync) = %t_osync_2
    return(%v_0)
BB [5:LBL_3:-1]
    %v_0 = recv_jruby_exc
    line_num(5)
    put_field(%self, @sync) = %t_osync_2
    throw(%v_0)
BB [8:LBL_7:-1]
    return(nil)

This blocks JIT because I have no way to ensure I'm initializing all JVM locals (mapped to IR temp vars) at the IR level.

@headius headius added ir labels Jul 3, 2014
@headius
Copy link
Member Author

@headius headius commented Jul 3, 2014

@headius
Copy link
Member Author

@headius headius commented Jul 3, 2014

To get around this for now, I am disabling DCE (currently run all the time in response to runDeadCodeAndVarLoadStorePasses called from prepareForInterpretation).

headius added a commit that referenced this issue Jul 4, 2014
@subbuss
Copy link
Contributor

@subbuss subbuss commented Jul 4, 2014

This is because I assumed that get_field instruction will always complete and not throw a ruby exception (java exceptions would presumably be handled in the runtime). Is that false? In that scenario, you dont need another init of osync to nil (or in other words, that init you added is truly dead). Try setting the exception flag for GET_FIELD in Operation.java as follows and see if that fixes it.

GET_FIELD(OpFlags.f_is_load | OpFlags.f_can_raise_exception),

@enebo
Copy link
Member

@enebo enebo commented Jul 4, 2014

I think the issue here is that when @headius sets up the equivalent of a try/catch for the method the assignment of that temp is essentially in what is the body of the try and the int to nil would have come before.

Perhaps we can not eliminate the nil init if it is inside an exception handling BB?

@enebo
Copy link
Member

@enebo enebo commented Jul 4, 2014

Wow that last sentence is %t_osync_2 = nil cannot be removed if it is referenced by any exception handler BB (which I think is known at CFG build time).

@enebo
Copy link
Member

@enebo enebo commented Jul 5, 2014

Notes from talking to subbu...

CFG should add new exception edges from one BB before a try to each catch BB. This should end up solving the liveness of those tempvars if they are really living or not. The basis of this problem looks like this in Java:

class C {
    public void foo() {
        int a;
        try {
            a = 1;
        } catch (Exception e) {
            System.out.println("a: " + a);
        }
    }
}

In this snippet 'int a' represents our init temp.

@subbuss
Copy link
Contributor

@subbuss subbuss commented Jul 5, 2014

Try: ast --ir -e "a = 1; begin; b = 1; ensure; p a, b; end" or ast --ir -e "a = 1; begin; b = 1; rescue => e; p a, b; end"

You will notice that by the time DCE is done, it effectively eliminates the begin-ensure and the begin-resuce since it figures that they are spurious, i.e. the dataflow analysis does a finer grained analysis on a per-instruction level by testing whether those can throw ruby exceptions or not. Right now, it doesn't assume that just because a protected region is entered, control can enter the rescue handler from the top of the protected region (which is what the the javac/jvm bytecode assumption seems to be) .. If you try to javac the snippet that Tom added above, it won't compile .. neither will any of the java-equivalent variants of the code above. So, one way to mimic jvm requirement is to forcibly add a dummy edge from the protected region predecessor to the handler (which if done will block the opts that we are currently able to do with the snippets above). To be continued ....

@headius
Copy link
Member Author

@headius headius commented Jul 5, 2014

This is because I assumed that get_field instruction will always complete

That's certainly reasonable. In my original case, however, there's at least one line that can cause an exception: p osync. That keeps the ensure from being removed, but for whatever reason the ensure's eventual use of the osync variable does not keep our nil initialization alive.

I can remove spurious code to simplify the case:

def foo
  a = 1
  p a
ensure
  p a
end

This method does nothing except local variable assignment and calls to p. However, it blows up on JVM JIT because DCE does not ensure a has been assigned outside of the ensure-protected body.

@subbuss
Copy link
Contributor

@subbuss subbuss commented Jul 5, 2014

Right, that is because the DCE reasons that a =1 won't thrown an exception (which it won't), and hence will always be initialized. The bytecode spec has stricter constraints. For now, turning off DCE is a good enough soln. to get you unblocked on getting JIT done, but let us discuss what is a good / cheap solution that works. Adding the dummy exception edge (as in earlier comments) will solve this problem, but it also seems quite conservative.

@subbuss
Copy link
Contributor

@subbuss subbuss commented Jul 5, 2014

Put another way, our analyses effectively shrinks protected regions till it hits the first exception-throwing instruction, but leaves the exception regions unshrunk ==> the JIT and hence JVM cannot exploit this information. So, perhaps, this should be the very first thing done during cfg building so that the first instruction in any protected region is always an exception-throwing instruction. With that fix, all dataflow analyses will do the right thing. So, in this example, the code effectively should effectively get rewritten to:

def foo
   a = 1
   begin
     p a
   ensure
     p a
   end
end```

@headius
Copy link
Member Author

@headius headius commented Jul 5, 2014

Yeah that seems like it would work properly. If the exceptional region shrinks to the first instruction that might cause an exception, it should move non-exceptional init outside that region. Where is that shrinking done?

@subbuss
Copy link
Contributor

@subbuss subbuss commented Jul 6, 2014

To recap the brief IRC discussion from the afternoon, the thing to reason about is what happens when you hit control-flow instructions while inspecting protected code.

Thinking about this some more, the core logic is to find a single-entry-single-exit control-flow region within the protected code that has no excepting instructions and move that out of the protected code.

begin
  a = 1
  c = a == 1 ? code-path-1 : code-path-2
  p a, c
rescue
  ...
end

can be transformed to:

a = 1
c = a == 1 ? code-path-1: code-path-2
begin
  p a, c
rescue
  ...
end

only if both code-path-1 and code-path-2 don't have excepting instrs. otherwise, the branch and both code paths stay behind.

This is probably best done as a post-cfg-build pass and the details need working out, and anecdotally, this seems straightforward, but requires some more analysis in the general case. "The Program Structure Tree: Computing Control Regions in Linear Time" might be relevant here.

@enebo
Copy link
Member

@enebo enebo commented Jul 7, 2014

Is the reason this cannot be done at CFG time is because we have not added the init temp decls? Or is it for a cleaner separation of logic? We could add those as part of CFG building and during optimize() shift non-side-effect things before the begin starts?

It might read cleaner as a pass but the idea of requiring m*n linear passes makes me want m to be as small as possible.

@subbuss
Copy link
Contributor

@subbuss subbuss commented Jul 7, 2014

Cannot be done at CFG build time, because the SESE region identification requires the CFG. This will be faster pass since we are primarily examining only basic blocks, not instructions (by setting flags on the basic-block while cfg is being built ... the flag would be: bb.canRaiseException() ..). That said, i haven't thought about this a whole lot yet.

@subbuss
Copy link
Contributor

@subbuss subbuss commented Jul 14, 2014

A quick update. I got this implemented over the weekend -- need to test it a bit more throughly.

subbuss added a commit that referenced this issue Jul 17, 2014
* This was an experimental fix for issue #1786.
* Now abandoning that experiment, but this shrinking is potentially
  interesting on its own merit. For now, committing this code for
  putting this in git history.
@enebo enebo added this to the JRuby 9.0.0.0 milestone Jan 15, 2015
@enebo
Copy link
Member

@enebo enebo commented Jan 15, 2015

Marking for 9k but we now do nil inits now after we run DCE. The problem has been mitigated but it would be nice to solve this in a more robust way. (probably not 9k initial release issue)

@subbuss
Copy link
Contributor

@subbuss subbuss commented Jan 15, 2015

I am going to close this and open a new issue that is about handling the nil initialization problem more generally. Now that ensure tmp vars are assigned pass runs at the end just before ir -> bytecode compilation, it handles JVM semantics of having the necessary inits.

That said, we need a generic solution that ensures that all local/tmps are assigned - this will also let us get rid of the return lookup-var OR return nil pattern in DynamicScope, interpreter, and jit.

@subbuss subbuss closed this as completed Jan 15, 2015
@headius headius removed this from the JRuby 9.0.0.0 milestone Jan 16, 2015
@headius headius added this to the JRuby 9.0.0.0-pre1 milestone Jan 16, 2015
@headius headius added this to the JRuby 9.0.0.0-pre1 milestone Jan 16, 2015
@headius headius removed this from the JRuby 9.0.0.0 milestone Jan 16, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

3 participants