Differential D43876
[LoopUnroll] Peel off iterations if it makes conditions true/false. Authored by fhahn on Feb 28 2018, 9:41 AM.
Details If the loop body contains conditions of the form IndVar < #constant, we This improves codegen for PR34364.
Diff Detail
Event Timeline
Comment Actions Update to use SCEV. It now uses a rather simple approach: evaluate AddRec at the DesiredPeelCount and then try to add the recurrence step until the predicate is not known any longer. We could probably compute the number of iterations directly, but I could not find any existing function in SCEV that would handle all predicates. But we only loop for MaxPeelCount iterations at max, and MaxPeelCount should be low.
Comment Actions I believe this has lots of potential (not just for constant). What other follow-up commits are you planning on ? Comment Actions I am open for suggestions. I think peeling off iterations at the end as Roman suggested might be worthwhile too. And opportunistically peeling off a few iterations, if the distance between start and end are low, but unrolling does not apply. Comment Actions
Peeling off iterations at the end might hit the case I'm trying to optimize. I will be happy to support it.
Comment Actions
Great! Is there any code/examples you could share that would benefit?
Comment Actions
Hopefully, below C code should show the case I'm pursuing. In this loop, we know that the condition is false only in the last one iteration. void test (int* p, int* p2, int* p3, int v, int L) { unsigned int M = *p;
int k;
for (k = 1; k <= M; k++) {
p2[k] = v;
if (k < M) {
p3[k] = v;
}
}} Comment Actions Just FYI, I am also currently working on a pass to handle slightly more generic cases within the loop body, such like: for (unsigned i = 0; i; i < 1000; ++i) { if (i < M) ... something else ... something else } My transformation operates on the unrolled version and also attempts to remove selects if the loop body has been simplified into one block. Hopefully I will be able to get an initial version up for review and discussion next week. Comment Actions Interesting. What transformation is this pass doing? Loop peeling should handle cases like that for constant bounds. Non-constant bounds still won't be peeled, so it should not interfere with your transformation. Comment Actions Yes, this is a really nice approach for lower constant bounds. My transform selects a region of conditionally executed blocks and then attempts to hoist conditional statements into the head block of that region. Currently I can find loop unrolled induction variable idioms as well as finding a connected path of conditional values. From there I can produce a fast path free of compares and branches, as well as leaving the original code as a fallback. I also split and remove selects because performing conditional moves is still expensive on our small cores as well as the increased register pressure they create. Comment Actions
Will your pass merge some blocks under same condition into a group in the loop? I'm curious if the conditional branch is removed in the loop?
I'm not sure if I fully understand what your pass will do. It would be great if you can show how this code would be transformed after your pass ? Comment Actions To remove the conditional branch in general, I think we can split the loop like : Min = min(1000, M);
unsigned i;
for (i = 0; i; i < Min; ++i) {
... something
}
for (; i; i < 1000; ++i) {
... something else
}@samparker, will your pass perform something like this or something else ? I believe peeling is a special case of such loop splitting, but peeling itself is worthwhile to do for a low constant bound.
Comment Actions @mkazantsev thank you very much for having a look. I hope I addressed your feedback. Are you concerned about having the loop that evaluates the predicate at the current iteration?
Comment Actions Thanks. Updated to use getInversePredicate
Comment Actions I think it is a bug to be fixed.
Comment Actions Thanks again! I've added a test case to make sure we do not peel the inner loop if the condition depends ARs of the outer loop
Comment Actions LGTM. I would rather prefer removing the restriction on RightSCEV being AR in this patch and then making a follow-up if you need some extra logic for it, but it's up to you.
Comment Actions Thanks again for having a look. I'll drop the bail out and add a test before I commit the change.
Comment Actions Rebased. I had to add -unroll-peel-max-count=0 to the new test case added in D43931, as loop peeling now covers that case too Comment Actions Hi Florian, I was wondering if we could avoid peeling in this case until we have some type of cost model that can determine if peeling would prevent inlining. Also, after looking at the code (which I can't share here) you might also notice that the amount of code being peeled in this case is fairly large relative to the amount of code being removed from the loop. It might also make sense to have a heuristic that takes code size into consideration when peeling, if that hasn't already been done. Thoughts? Chad Comment Actions Hi Chad, Thanks for making me aware of this, I originally thought considering MaxPeelCount should help us avoid those cases. I will follow this up with patches in the following days. I think there are a couple of things that can be done to make the peeling more conservative for now. First, only peel if we can proof that the condition is known to be true in the peeled part and false in the loop (or vice versa). Otherwise we cannot simplify the loop body and peeling is likely not very beneficial. Second, have a simple cost function, that takes the size of the loop body vs the eliminated instructions into account. Also, D43878, which enables induction variable simplification after peeling is not committed yet, so currently the loop body may not be simplified after peeling, even if it could be. Cheers, Comment Actions You're welcome, Florian. And thanks for following up on this (and all the great work you're doing here)! Comment Actions @mcrosier I've submitted D44983 for review. It prevents peeling, if we cannot simplify the loop body after peeling. Peeling if we cannot simplify the loop body afterwards is likely not beneficial. It would be great if you could check if that helps in your case. If it's not easy for you to check, I can try and test it myself. Coming up with some additional heuristics, e.g. based on the number of instructions peeled and not eliminated, should be possible, but without knowing the inlining situation we would probably have to choose a rather arbitrary threshold. Comment Actions Unfortunately, D44983 does not fix this case. I'm going to dig into this now. I'll update you once I have some additional findings. Comment Actions Thanks for letting me know, so it looks like we need better size based heuristics as well. I'll take a closer look at what happens in FullPelBlockMotionBiPred soon. Comment Actions I had a closer look at FullPelBlockMotionBiPred and we peeled off an iteration because we have something like if (i % 2) {
...
if (i != 0) {...}
...
}Peeling based on those nested conditional is likely to increase the code size too much compared to the benefit. D45374 only considers conditions in blocks that are executed on every iteration. Comment Actions IIUC, D45374 should fix the regression in h264ref we're seeing (but I haven't tested it yet). However, I wanted to share with you my findings. Currently, loop peeling will not peel a loop if it includes a function call that is likely to be inlined (i.e., is not marked with a noinline attribute, has internal linkage and has a single use). This is exactly the case we're dealing with here except FullPelBlockMotionBiPred isn't marked as internal until the LTO phase of compilation. Thus, one possible approach would be to defer peeling until the LTO phase. After r329392, this can be accomplished with a small change to the pass manager: diff --git a/lib/Transforms/IPO/PassManagerBuilder.cpp b/lib/Transforms/IPO/PassManagerBuilder.cpp index 1def2e8..b06ca2a 100644 --- a/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -651,7 +651,10 @@ void PassManagerBuilder::populateModulePassManager( addInstructionCombiningPass(MPM); if (!DisableUnrollLoops) { - MPM.add(createLoopUnrollPass(OptLevel)); // Unroll small loops + if (PrepareForLTO) + MPM.add(createSimpleLoopUnrollPass(OptLevel)); // Unroll small loops + else + MPM.add(createLoopUnrollPass(OptLevel)); // Unroll small loops // LoopUnroll may generate some redundency to cleanup. addInstructionCombiningPass(MPM); However, I haven't run any performance tests (but I do know if fixes the h264ref regression) nor do I know if the community would be interested in such an approach. A more targeted approach might be to only prevent peeling of the loop (rather than disable peeling entirely) during the first phase of LTO if the loop has any calls. Comment Actions
ThinLTO doesn't run vectorization or unrolling before link-time; among other reasons, it avoids problems like this. You might want to consider making non-thin LTO work the same way. Comment Actions Thanks for the suggestion, Eli. Given this is already the behavior of ThinLTO, I'm going to investigate this further. Comment Actions Came across this patch and curious, is "Peeling off iterations at the end" supposed to work by now (if so, I don't see it)? | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||