IM: LICM - Block hotness metric for code hoisting

NEW
Unassigned

Status

()

8 years ago
5 years ago

People

(Reporter: ascheff, Unassigned)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

(Reporter)

Description

8 years ago
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
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?
Yeah, maybe somehow this knowledge fits into the TypeOracle's role.
(Reporter)

Comment 3

8 years ago
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.
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?
(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.
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.
(Reporter)

Comment 7

8 years ago
That sort of data would be awesome to have available.
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.
Assignee: general → nobody
You need to log in before you can comment on or make changes to this bug.