669517 - IM: LICM - Block hotness metric for code hoisting

Status: RESOLVED DUPLICATE of bug 1712078

(Core :: JavaScript Engine, defect)

Description

[Andrew Scheff]

Instructions that are in cold blocks within loops should probably not be hoisted.  There needs to be some way of determining block hotness for LICM, weather it's some simple analysis of the MIR Graph or information gathered on a previous pass

Comment 1

[Brian Hackett [Laid off!]]

Not sure how you could recover this from static analysis of the IR, don't you need to dynamically monitor hit counts for branches or basic blocks?

Comment 2

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

Yeah, maybe somehow this knowledge fits into the TypeOracle's role.

Comment 3

[Andrew Scheff]

For static analysis, I mean something like "if the block is on a branch within the loop, then an instruction in this block is not worth hoisting." This is obviously too restrictive, as a branch within a loop, if run at least a couple times, is worth hoisting code out of.  I think that the only way to really make this useful would be to have some richer information about hotness, perhaps from the TypeOracle or some still unwritten profiling pass.

Comment 4

[Ryan Pearl [:rpearl]]

I'm confused a bit. I was under the impression that code that was loop-invariant was hoisted out of the loop. If the entire branching structure within the loop is invariant throughout the loop, then surely it is worth hoisting out (so we run it once, instead of many times).

If there are instructions within a branch which are invariant, but the branch itself depends on a loop variable, then the instructions within the branch cannot be pulled out, since they are only run dependent on a loop variable and are thus not actually loop-invariant.

A branching structure in which internal instructions depend on the loop, but the condition does not is a more complex scenario, and I suspect is dealt with using other optimizations such as partial redundancy elimination.

In what scenarios is it worth gathering this hotness information? We're already only compiling hot code, I thought?

Comment 5

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

(In reply to comment #4)
> I'm confused a bit. I was under the impression that code that was
> loop-invariant was hoisted out of the loop. If the entire branching
> structure within the loop is invariant throughout the loop, then surely it
> is worth hoisting out

Potentially, though this infrastructure is not in place yet.

> If there are instructions within a branch which are invariant, but the
> branch itself depends on a loop variable, then the instructions within the
> branch cannot be pulled out, since they are only run dependent on a loop
> variable and are thus not actually loop-invariant.

A branch condition's invariance doesn't prevent you from hoisting loop-invariant instructions out of the branch, since we only hoist idempotent, uneffectful instructions. However, it might not be a good idea, for example:

 if (f())
    v = x.y;

If |f()| always returns false and you hoist the |x.y|, you could fail a guard that would never have otherwise ran.

Comment 6

[Brian Hackett [Laid off!]]

I think we should have accumulate profiling information when running in the interpreter and possibly in certain optimization levels of compiled code (warm but yet really hot).  This will be good not just for LICM but also trace compilation; the more information we have about which code is hot, the better we can decide what path(s) through a loop to trace, if any.

It should be sufficient to add profiling opcodes at the head of each basic block which accumulate counters, rather than tracking how hot each branch is and which direction it takes.

Comment 7

[Andrew Scheff]

That sort of data would be awesome to have available.

Comment 8

[David Mandelin [:dmandelin]]

It would be good to approach this in a data-driven way. E.g., one or both of

1. Find benchmarks/workloads where these decisions actually matter, find out what the best decisions are, and design around that.

2. Write some microbenchmarks and see what happens there for different hoisting policies, and design around that.

Note that this requires us to have the code generator in place and enough ops to write some decent tests.

Comment 9

[Julian Seward [:jseward]]

Closing as a dup of bug 1712078. The fix there is cruder than what is
discussed here, in that it is not directly hotness-metrics-based, but
works well enough for the one and only example we had where we
know overly-aggressive LICM to be a problem, that is, bug 1708381.
If we need something more sophisticated in future, we can reopen or
file a new bug.