This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Ensure that isHighCostExpansion takes into account what is being divided
ClosedPublic

Authored by dmgreen on Feb 20 2019, 3:29 AM.

Details

Summary

A SCEV is not low-cost just because you can divide it by a power of 2. We need to also
check what we are dividing to make sure it too is not a high-code expansion. This helps
to not expand the exit value of certain loops, helping not to bloat the code.

The change in no-iv-rewrite.ll is reverting to back before rL194116, and looks a lot like
the other tests in replace-loop-exit-folds.ll.

Diff Detail

Event Timeline

dmgreen created this revision.Feb 20 2019, 3:29 AM
lebedev.ri resigned from this revision.Feb 20 2019, 4:12 AM
dmgreen added reviewers: spatel, RKSimon.

ping

This is targeted at codesize, but I ran the standard set of benchmarks and didn't see any changes that didn't look like noise.

RKSimon added inline comments.Mar 1 2019, 12:20 PM
lib/Analysis/ScalarEvolutionExpander.cpp
2073–2075

Please update the comment

sanjoy requested changes to this revision.Mar 1 2019, 4:48 PM

The change itself looks fine to me, but I'm a bit worried about the test changes. Is it possible that the tests were checking certain the correctness for certain expressions that we no longer check because these happen to be expensive? If that's the case maybe we should add a debug flag that disregards the "is expensive expansion" check to make sure the the same code paths remain tested?

Can you also add a specific test for this change in behavior? Even if it is incidentally tested by the other tests, it would be nicer to have a dedicated test.

This revision now requires changes to proceed.Mar 1 2019, 4:48 PM

Is it possible that the tests were checking the correctness for certain expressions that we no longer check because these happen to be expensive?

All the tests in replace-loop-exit-folds.ll are added for this patch. It's showing the changes produced by this patch, but the left hand files are not in-tree yet (it would have been clearer if I would have mentioned that). Most of the tests are a loop like this, with S being signed or unsigned, and with a while or a do loop. They were originally out of D52508 (but that doesn't fix most of the cases).

while(S >= 32) {
    S -= 32;
    something();
};
return S;

no-iv-rewrite.ll is returning back to what it was before rL194116, so is now testing the original point of the test again. The full diff for before and after is much like the other newly added tests (i.e. now a lot smaller):

 define i64 @cloneOr(i32 %limit, i64* %base) #0 {
 entry:
   %halfLim = ashr i32 %limit, 2
   %0 = sext i32 %halfLim to i64
-  %1 = icmp sgt i32 %halfLim, 2
-  %smax = select i1 %1, i32 %halfLim, i32 2
-  %2 = add i32 %smax, -1
-  %3 = zext i32 %2 to i64
-  %4 = lshr i64 %3, 1
-  %5 = shl i64 %4, 1
   br label %loop

 loop:                                             ; preds = %loop, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ 0, %entry ]
   %adr = getelementptr i64, i64* %base, i64 %indvars.iv
   %val = load i64, i64* %adr
+  %1 = or i64 %indvars.iv, 1
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
   %cmp = icmp slt i64 %indvars.iv.next, %0
   br i1 %cmp, label %loop, label %exit

 exit:                                             ; preds = %loop
   %val.lcssa = phi i64 [ %val, %loop ]
-  %6 = add i64 %5, 1
-  %result = and i64 %val.lcssa, %6
+  %t3.lcssa = phi i64 [ %1, %loop ]
+  %result = and i64 %val.lcssa, %t3.lcssa
   ret i64 %result
 }
dmgreen updated this revision to Diff 189080.Mar 3 2019, 7:10 AM

Altered comment, and just use indvars for the tests (not instcombine/loop-delete).

sanjoy accepted this revision.Mar 4 2019, 11:12 AM

Thanks for the explanation!

This revision is now accepted and ready to land.Mar 4 2019, 11:12 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptMar 5 2019, 4:12 AM