[CodeGenPrep]No negative cost in the ExtLd promotion

[junbuml]

Summary

This change prevent the signed value of cost from being negative as the value is passed as an unsigned argument.

[mcrosier]

LGTM.

[qcolombet]

Hi,

I didn't look at the test case you're adding, but I guess it exposes the problem. Could you describe how the cost becomes negative?

I have a hard time picturing that and I want to be sure we are not missing something.
Indeed, at the beginning TotalCreatedInstsCost is CreatedInstsCost + NewCreatedInstsCost. Both operands are unsigned values.
Thus TotalCreatedInstsCost > 0.
Then TotalCreatedInstsCost -= ExtCost with ExtCost being either 0 or 1.
Thus, TotalCreatedInstsCost will get < 0 if it was TotalCreatedInstsCost == 0 before that operation and ExtCost is 1. Given TotalCreatedInstsCost == 0, the created instructions are all free.

First, I am not saying that's impossible, I want to be sure this is what we want.
Second, TotalCreatedInstsCost becomes a benefit and I wonder if we want to keep propagating it instead of ceiling it at 0.

Thanks,
-Quentin

[junbuml]

Hi Quentin,

I believe the test case I added shows the case where TotalCreatedInstsCost becomes negative :

• In the very first call of extLdPromotion(), CreatedInstsCost is 0, ExtCost is 1 for the sext (%r), and NewCreatedInstsCost after promotion is 0 because the cost of sext becomes free after moving it up before %shl2.
• Therefore, TotalCreatedInstsCost -= ExtCost becomes negative.

I think propagating the negative value of TotalCreatedInstsCost is also possible, but I think ceiling it to 0 is simple and conservative enough to handle this corner case.

This patch is a small particle from D27853, which should be rebased based on this.

Thanks,
Jun

[junbuml]

Thanks Quentin for the review. I added a FIXME about propagating negative values.
I will commit it if you don't have any further objection, and revisit it to see if propagating negative values is reasonable.

[qcolombet]

Looks and sounds good to me!

Thanks,
Q

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

for (auto I : Exts) {
 
     // We would be able to merge only one extension in a load.
     // Therefore, if we have more than 1 new extension we heuristically
     // cut this search path, because it means we degrade the code quality.
     // With exactly 2, the transformation is neutral, because we will merge
     // one extension but leave one. However, we optimistically keep going,
     // because the new extension may be removed too.
     long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
-    TotalCreatedInstsCost -= ExtCost;
+    // FIXME: It would be possible to propagate a negative value instead of
+    // conservatively ceiling it to 0. 
+    TotalCreatedInstsCost =
+        std::max((long long)0, (TotalCreatedInstsCost - ExtCost));
     if (!StressExtLdPromotion &&
         (TotalCreatedInstsCost > 1 ||
          !isPromotedInstructionLegal(*TLI, *DL, PromotedVal))) {
       // The promotion is not profitable, rollback to the previous state.
       TPT.rollback(LastKnownGood);
       continue;
     }
     // The promotion is profitable.

llvm/trunk/test/CodeGen/AArch64/arm64-codegen-prepare-extload.ll

define i64 @doNotPromoteBecauseOfPairedLoad(i32* %p, i32 %cst) {
   %idxLd1 = getelementptr inbounds i32, i32* %p, i64 1
   %ld1 = load i32, i32* %idxLd1
   %res = add nsw i32 %ld1, %cst
   %sextres = sext i32 %res to i64
   %zextLd0 = zext i32 %ld0 to i64
   %final = add i64 %sextres, %zextLd0
   ret i64 %final
 }
+
+define i64 @promoteZextShl(i1 %c, i16* %P) {
+entry:
+; OPTALL-LABEL: promoteZextShl
+; OPTALL-LABEL: entry:
+; OPT: %[[LD:.*]] = load i16, i16* %P
+; OPT: %[[EXT:.*]] = zext i16 %[[LD]] to i64
+; OPT-LABEL: if.then:
+; OPT: shl nsw i64 %[[EXT]], 1
+; DISABLE-LABEL: if.then:
+; DISABLE: %r = sext i32 %shl2 to i64
+  %ld = load i16, i16* %P
+  br i1 %c, label %end, label %if.then
+if.then:
+  %z = zext i16 %ld to i32
+  %shl2 = shl nsw i32 %z, 1
+  %r = sext i32 %shl2 to i64
+  ret i64 %r
+end:
+  ret i64 0
+}