cmd/compile: loop invariant code motion #63670
Comments
gopherbot
added
the
compiler/runtime
|
Do you have a favorite reference for LCSSA? I understand what it's about from reading your patch (and I can see why we would want it) but there are also corner cases (multiple exits to different blocks, exits varying in loop level of target) and it would be nice to see that discussed. I tried searching, but mostly got references to LLVM and GCC internals. Also, how far are you into a performance evaluation for this? Experience in the past (I also tried this) was uncompelling on x86, better but not inspiring for arm64 and ppc64. But things are changing; I'm working on (internal use only) pure and const calls that would allow commoning, hoisting, and dead code elimination, and arm64 is used much more now in data centers than five years ago. |
dr2chase
added
NeedsFix
gopherbot
removed
the
NeedsFix
LLVM's doc is a good reference, maybe I can write some doc later either in go/doc or other place.
Yes! This is the most challenging part.
Experimental data(building go toolchain itself) shows that 98.27% loops can apply LCSSA. |
|
I agree that being able to hoist loads of constants and invariants should
help loops in ppc64 and probably arm64. Previous hoisting CLs didn't
attempt loads which is why there was not much benefit, and I couldn't make
it work because of what tighten does with loads is at odds with what
hoisting is trying to do.
I also recently tried to do a change to add PCALIGN to the top of loop body
but because of the way looprotate moved the blocks, the alignment couldn't
be inserted in the correct place. With this improved way of doing
looprotate it should be more straightforward to insert the PCALIGN in the
appropriate spot.
I have done some performance comparisons between gccgo and Golang on ppc64
since gccgo does better at optimizing loops in most cases on ppc64. That
can show what improvement is possible.
…On Mon, Oct 23, 2023 at 9:30 PM Yi Yang ***@***.***> wrote:
Do you have a favorite reference for LCSSA?
LLVM's doc
<https://llvm.org/docs/LoopTerminology.html#loop-closed-ssa-lcssa> is a
good reference, maybe I can write some doc later either in go/doc or other
place.
but there are also corner cases (multiple exits to different blocks, exits
varying in loop level of target) and it would be nice to see that discussed.
Yes! This is the most challenging part.
[image: image]
<https://user-images.githubusercontent.com/5010047/277528772-13f97a7b-4fd3-46f0-b668-cd41abea860a.png>
- For case 1, only one exit block, E1 doms use block, so we insert
proxy phi at E1
- For case2, all exits E1 and E2 dominates all predecessors of use
block, insert proxy phi p1,p2 at E1 and E2 respectively, and insert yet
another proxy phi p3 at use block to merge p1, p2.
- For case3, use block is reachable from E1 and E2, but not E3, this
is hard, maybe we need to we start from all loop exits(including inner loop
exits) though dominance frontier and see if we can reach to the use block.
THis is hard, we give up now.
Experimental data(building go toolchain itself shows that 98.27% loops can
apply LCSSA.
—
Reply to this email directly, view it on GitHub
<#63670 (comment)>, or
unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACH7BDAZ7M4ENQRHATOCOHLYA4R4HAVCNFSM6AAAAAA6K2QRESVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTONZWGM4TKMZXGM>
.
You are receiving this because you are subscribed to this thread.Message
ID: ***@***.***>
|
|
I tried your source tree. It looks like there is a bug when building the go1 benchmark test Fannkuch. This test used to be under test/bench/go1 but it was removed in go 1.21. If you go back to go 1.20 you can build it. One of the loops in the Fannkuch test doesn't exit. I also noticed that hoisting the NilCheck is not always a good thing. I found a similar problem recently with tighten when a load gets moved to a different block. There is a later pass to eliminate unnecessary NilChecks, but it only gets optimized if the NilCheck is in the same block as the load or store that uses the same pointer/address. Look at the loop in math.BenchmarkSqrtIndirectLatency. |
I don't think this should be a problem. True that hoisting and tightening are working in opposite directions, but tightening should never move anything into a loop, so as long as you're correctly hoisting out of a loop then tightening should not undo that work. (Or tightening has a bug.) |
|
(Or maybe you mean the rematerialization of constants that regalloc does? We could disable rematerialization for constants that would require a load from a constant pool.) |
I mean loads of constant values which shouldn't have any aliases. I think the rematerialization flag mostly controls where this gets loaded, and tighten has some effect on that. It's been a while since I tried to play with it. Base addresses of arrays, slices, etc. should be constant/invariant and hoisted instead of reloaded at each iteration. I can't seem to get that to happen. I should add that I don't know if there is anything in place right now to allow this type of hoisting even without the rematerialization done in regalloc. This statement is based on experimenting with various CLs that have tried to enable hoisting including the new one mentioned in this issue. |
|
Here's an example of what I meant above, from test/bench/go1.revcomp (back before it was removed) |
|
I think this is just a problem with our register allocator. At this point go/src/cmd/compile/internal/ssa/regalloc.go Line 1402 in 9cdcb01 |
Do you means something like loop alignment. That's interesting.
Thanks a lot! I'll fix this then. The current development is almost complete, and the remaining work mainly involves ensuring robustness and optimizing performance. I will try testing go1 benchmark and golang/benchmarks and then resolve any issues that may arise. (I am thinking about adding support for simple stress testing to the golang compiler, i.e. allow a pass runs between [start pass, end pass], and executing the pass after each pass within that range. This approach would greatly ensure the stability of optimization/transformation.) Update: I confirmed this bug, TBAA thinks they are NoAlias but actually they do alias, because unsafe pointer may aliases with everything |
Yes, there are several ports that support the PCALIGN directive and currently it is only used in assembly implementations. It would be worthwhile to have the compiler generate it for appropriate loops.
What do you mean by definition point for a constant? Do you mean that the loop hoisting code would generate the definition?
I still don't think the way NilChecks are hoisted is providing the best performance, as I mentioned earlier. |
|
Currently, if you have this before regalloc: Then after regalloc it moves v1 inside the loop We shouldn't do that move if the destination is in a loop. We should force |
The implementation consists of {Loop Invariant Code Motion, Loop Rotation,
Type-based Alias Analysis, Loop Closed SSA Form}
Testing: attached IR tests, codegen, go test, ssacheck,
golang/benchmarks, go-http-routing-benchmark
Co-authored-by: jeffery.wsj@alibaba-inc.com
Co-authored-by: denghui.ddh@alibaba-inc.com
Co-authored-by: lfkdsk@gmail.com
Co-authored-by: realfusionbolt@gmail.com
Updates golang#63670
|
Change https://go.dev/cl/551381 mentions this issue: |
|
Have I missed |
@randall77 Yes, that is what I was referring to in an earlier post. |
|
Regarding TBAA, please note that a pointer in Go might not actually point to memory allocated by Go, this may defeat all kinds of analysis as 2 completely unrelated pointers can point to elements of a C union and thus alias each other. |
|
Even while staying in go land almost most types can alias with each other. What you currently can't do is write to some offset which was originally allocated as a pointer as a non pointer (because you will be missing write barrier calls). The inverse might also be problematic (as you would have write barrier for things the GC does not think are pointers) I don't know. This is stronger than what we guarantee in documentation on some points. |
|
@merykitty @Jorropo That makes sense, I was convinced that cornerstone of TBAA (rule 7) does not hold in Golang, I'll revert TBAA along with some test fixes later. |
Hi, several months ago I submit a patch to implement LICM(#59194), but in that patch the performance improvement was not compelling, after some research we think we need to hoist the high-yield instructions (Load/Store/etc) to achieve a positive performance improvement. Since these high-yield instructions are usually not speculative execution, we may need to implement a fulll LICM with the following dependencies:
Overall, LCSSA opens the door to future loop optimizations, and LICM is expected to have attractive performance improvements on some benchmarks.
Because loop rotation significantly changes the control flow, it also affects block layout and register allocation, leading to regressions in some benchmarks. I have fixed some of these, but completely eliminating these regressions remains a long-term task. To prevent the patch from growing larger and mixing code changes that increase the difficulty of review, such as the fix to the register allocation algorithm and adjust to the block layouting algorithm, and to keep features independent, I have introduced
GOEXPERIMENT=loopoptsto control these optimizations, with the expectation of gradually fixing all the regressions and reducing compilation time in the follow-up patches.Below is a more detailed explanation of the changes, which may be helpful to the reviewer. Thank you for your patience!
1. Loop Invariant Code Motion
The main idea behind LICM is to move loop invariant values outside of the loop
so that they are only executed once, instead of being repeatedly executed with
each iteration of the loop. In the context of LICM, if a loop invariant can be
speculatively executed, then it can be freely hoisted to the loop entry.
However, if it cannot be speculatively executed, there is still a chance that
it can be hoisted outside the loop under a few prerequisites:
#1 Instruction is guaranteed to execute unconditionally#2 Instruction does not access memory locations that may alias with other memory operations inside the loopFor
#1, this is guaranteed by loop rotation, where the loop is guaranteed toexecute at least once after rotation. But that's not the whole story. If the
instruction is guarded by a conditional expression (e.g., loading from a memory
address usually guarded by an IsInBound check), in this case, we try to hoist
it only if the loop invariant dominates all loop exits, which implies that it
will be executed unconditionally as soon as it enters the loop.
For
#2, we rely on a simple but efficient type-based alias analysis to knowwhether two memory access instructions may access the same memory location.
2. Type-based Alias Analysis
Type-based Alias Analysis(TBAA) is described in Amer Diwan, Kathryn S. McKinley, J. Eliot B. Moss: Type-Based Alias Analysis. PLDI 1998
TBAA relies on the fact that Golang is a type-safe language, i.e. different
pointer types cannot be converted to each other in Golang. Under assumption,
TBAA attempts to identify whether two pointers may point to same memory based
on their type and value semantics. They can be summarized as follows rules:
3. Loop Close SSA Form
Loop closed SSA form(LCSSA) is a special form of SSA form, which is used to simplify
loop optimization. It ensures that all values defined inside the loop are only
used within loop. The transformation looks up loop uses outside the loop and
inserts the appropriate "proxy phi" at the loop exit, after which the outside
of the loop does not use the loop def directly but the proxy phi.
Previously, v5 used v3 directly, where v5 is in the loop exit which is outside
the loop. After LCSSA transformation, v5 uses v6, which in turn uses v3. Here,
v6 is the proxy phi. In the context of LCSSA, we can consider the use block of
v6 to be the loop header rather than the loop exit. This way, all values defined
in the loop are loop "closed", i.e. only used within the loop.
Any further changes to the loop definition only need to update the proxy phi,
rather than iterating through all its uses and handling properties such as
This significantly simplifies implementation of Loop Rotation
4. Loop Rotation
4.1 CFG transformation
Loop rotation, also known as loop inversion, it transforms while/for loop to
do-while style loop, e.g.
The original natural loop is in form of below IR
In the terminology, loop entry dominates the entire loop, loop header contains
the loop conditional test, loop body refers to the code that is repeated, loop
latch contains the backedge to loop header, for simple loops, the loop body is
equal to loop latch, and loop exit refers to the block that dominated by the
entire loop.
We move the conditional test from loop header to loop latch, incoming backedge
argument of conditional test should be updated as well otherwise we would lose
one update. Also note that any other uses of moved values should be updated
because moved Values now live in loop latch and may no longer dominates their
uses. At this point, loop latch determines whether loop continues or exits
based on rotated test.
Now loop header and loop body are executed unconditionally, this may changes
program semantics while original program executes them only if test is okay.
A so-called loop guard is inserted to ensure loop is executed at least once.
Loop header no longer dominates entire loop, loop guard dominates it instead.
If Values defined in the loop were used outside loop, all these uses should be
replaced by a new Phi node at loop exit which merges control flow from loop
header and loop guard. Based on Loop Closed SSA Form, these Phis have already
been created. All we need to do is simply reset their operands to accurately
reflect the fact that loop exit is a merge point now.
One of the main purposes of Loop Rotation is to assist other optimizations
such as LICM. They may require that the rotated loop has a proper while safe
block to place new Values, an optional loop land block is hereby created to
give these optimizations a chance to keep them from being homeless.
The detailed loop rotation algorithm is summarized as following steps
1.1 All uses of loop defined Values will be replaced by uses of proxy phis
2.1 Loop must be a natural loop and have a single exit and so on..
3.1. Rewire loop header to loop body unconditionally.
3.2 Rewire loop latch to header and exit based on new conditional test.
3.3 Create new loop guard block and rewire loop entry to loop guard.
3.4 Clone conditional test from loop header to loop guard.
3.5 Rewire loop guard to original loop header and loop exit
4.1 Move conditional test from loop header to loop latch
4.2 Update uses of moved Values because these defs no longer dominates uses after they were moved to loop latch
4.3 Add corresponding argument for phis at loop exits since new edge from loop guard to loop exit had been created
4.4 Update proxy phi to use the loop phi's incoming argument which comes from loop latch since loop latch may terminate the loop now
Some gory details in data dependencies after CFG transformation that deviate from
intuition need to be taken into account. This has led to a more complex loop
rotation implementation, making it less intuitive.
4.2 Fix Data Dependencies
The most challenging part of Loop Rotation is the update of data dependencies
(refer to steps 3 and 4 of the algorithm).
Update conditional test operands
In original while/for loop, a critical edge is inserted at the
end of each iteration, Phi values are updated. All subsequent
uses of Phi rely on updated values. However, when converted
to a do-while loop, Phi nodes may be used at the end of each
iteration before they are updated. Therefore, we need to
replace all subsequent uses of Phi with use of Phi parameter.
This way, it is equivalent to using updated values of Phi
values. Here is a simple example:
Normal case, if v2 uses v1 phi, and the backedge operand v4
of v1 phi is located in the loop latch block, we only need to
modify the usage of v1 by v2 to the usage of v4. This prevents
loss of updates, and the dominance relationship will not be
broken even after v2 is moved to the loop latch.
After updating uses of val, we may create yet another cyclic
dependency, i.e.
This is similiar to below case, and it would be properly handled
by updateMovedUses. For now, we just skip it to avoid infinite
recursion.
If there is a value v1 in the loop header that is used to define
a v2 phi in the same basic block, and this v2 phi is used in
turn to use the value v1, there is a cyclic dependencies, i.e.
In this case, we need to first convert the v1 phi into its
normal form, where its back edge parameter uses the value defined
in the loop latch.
After this, the strange v1 phi is treated in the same way as
other phis. After moving the conditional test to the loop latch,
the relevant parameters will also be updated, i.e., v2 will
use v3 instead of v1 phi:
Finally, since v3 is use of v2, after moving v2 to the loop
latch, updateMovedUses will update these uses and insert a
new v4 Phi.
Update uses of moved Values because these defs no longer dominates uses after they were moved to loop latch
If the loop conditional test is "trivial", we will move the chain of this
conditional test values to the loop latch, after that, they may not dominate
the in-loop uses anymore:
So we need to create a new phi v5 at the loop header to merge the control flow
from the loop guard to the loop header and the loop latch to the loop header
and use this phi to replace the in-loop use v4. e.g.
Add corresponding argument for phis at loop exits since new edge from loop guard to loop exit had been created
Loop header no longer dominates loop exit, a new edge from loop guard to loop
exit is created, this is not reflected in proxy phis in loop exits, i.e. these
proxy phis miss one argument that comes from loop guard, we need to reconcile
the divergence
Since LCSSA ensures that all loop uses are closed, i.e. any out-of-loop uses
are replaced by proxy phis in loop exit, we only need to add missing argument
v1' to v1 proxy phi
Update proxy phi to use the loop phi's incoming argument which comes from loop latch since loop latch may terminate the loop now
Loop latch now terminates the loop. If proxy phi uses the loop phi that lives
in loop header, it should be replaced by using the loop phi's incoming argument
which comes from loop latch instead, this avoids losing one update.
5. Bug Fix
The loop exit created by BlockJumpTable will not be discovered by
findExits().The current loop exits are only b23 and b43, but the expected ones should include b10 and b13.
6. Performance Regression
6.1 block layout
In original block layout algorithm, regardless of whether successors of the current basic block have
likelyattribute, the layout algorithm would place each successor right after the current basic block one by one. The improved algorithm employs a greedy approach, aiming to allocate the basic blocks of a "trace" together as much as possible, in order to minimize excessive jumps. i.e. For given IR:The final block orders are as follows:
6.2 register allocation
After loop rotation, there are some significant performance regression. Taking the strconv.Atoi benchmark as an example, the performance deteriorates by about 30%. In the following example:
In the code generated by the baseline, the loop includes 10 instructions
[26-35], whereas the optimized code contains 11 instructions[28-38]. This is because the baseline's loop increment instructioni++producedincq ax, while the optimized code generated is:The culprit is empty basic block created during the split critical edge after rotation, which affects the logic of register allocation;
During the register allocation process, for the instruction
v82 = ADDQconst <int> [1] v59, the register allocator checks if v59 is in the next basic block and examines the expected register for v59. For example, if v59 is in the next basic block and its expected register is R8, then the register allocator would also allocate the R8 register forv82 = ADDQconst <int> [1] v59, because the input and result are in the same register, allowing the production ofincq. However, after loop rotation, the next basic block for v82 is the newly inserted empty basic block from the split critical edge, preventing the register allocator from knowing the expected register for v59, so v82 and v59 end up being allocated to different registers, R8 and RAX, resulting in an extramovinstruction. The proposed fix is to skip empty basic block and directly check the next non-empty basic block for the expected register.6.3 high branch miss
BenchmarkSrcsetFilterNoSpecialsshows noticeable performance regression due to high branch mispredictions after the optimizationThe program execution flow is b16->b19->b103->b17->b16(loop), but b103 is placed below the loop latch b17, leading to high branch misses as illustrated above (
ja 8b(goto b103),jmp 7f(goto b17), andjg 30(goto b16)). I propose to always place the loop header(or loop latch after real rotation) to the bottom of the loop.7. Test fix
7.1 codegen/issue58166.go
codegen/issue58166.gofails, it expected loop increment to generateincq, but instead, it ended up generatingleaq+mov.During register allocation, v114 couldn't be allocated to the same register r8 as v149, due to the fact that there were two uses of v114 (v136 and v146) right after v149. As a result, unexpected instructions were produced.
After loop rotation, the schedule pass calculated scores for b26, resulting in the following order:
An optimization was made as per https://go-review.googlesource.com/c/go/+/463751, which prioritizes values that are used within their live blocks. Since v149 is used by v91 in the same block, it has a higher priority.
The proposed fix is that if a value is used by a control value, then it should have the lowest priority. This would allow v146 and v91 to be scheduled closely together. After this scheduling, there would be no use of v114 after v146, thus allowing v146 and v114 to be allocated to the same register, ultimately generating an incq instruction.
7.2 test/nilptr3.go
Loop rotation duplicates conditional test Values into loop gaurd block:
So we need to add a
loop nilcheckelimpass after all other loop opts to remove thev6 NilCheckin the loop guard, but that's not the whole story.The code
_ = x[9]is expected to generate a nilcheck, buttightenpass will move the LoweredNilCheck from the loop entry b1 to the loop guard. At that point, there happens to be a CMPQconstload in the loop guard that meets the conditions forlate nilcheckelim, resulting in the elimination of the LoweredNilCheck as well. Therefore, we also need to modify the test to no longer expect the generated code to contain a nilcheck.7.3 test/writebarrier.go
We added
loop optpass afterwritebarrierpass,*x = ybecomes dead store, simply removing ERROR directive fixes this case.The text was updated successfully, but these errors were encountered: