[RISCV] Prevent overflowing the small size of InstSeq in generateInstSeq.

[craig.topper]

Summary

The small size is 8 which is the worst case of the core recursive
algorithm.

The special cases use the core algorithm and append additonal
instructions. We were pushing the extra instructions before checking
the profitability. This could lead to 9 and maybe 10 instructions
in the sequence which overflows the small size.

This patch does the profitability check before inserting the
extra instructions so that we don't create 9 or 10 insruction
sequences.

Alternative we could bump the small size to 9 or 10, but then
we're pushing things that are never going be used.

[craig.topper]

Ping

[asb]

Sorry for the slow review, I was mostly out / traveling last week.

The original logic was written to be dumb but easy to follow, and in the absence of benchmarking data I'd be tempted to just bump the size to keep the logic that way. But this change seems correct and I've got not real objection to it if it's your preferred approach.

[craig.topper]

In D152308#4414826, @asb wrote:

Sorry for the slow review, I was mostly out / traveling last week.

The original logic was written to be dumb but easy to follow, and in the absence of benchmarking data I'd be tempted to just bump the size to keep the logic that way. But this change seems correct and I've got not real objection to it if it's your preferred approach.

I'm not sure how to enforce the small size is sufficient if we do go that way. I was wondering if this sequence was a good candidate for the StaticVector proposed in https://reviews.llvm.org/D112175. I tried to make InstSeq into my own simplified static vector with a buffer of 8 and that's how I found the overflow.

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

 //===- RISCVMatInt.cpp - Immediate materialisation -------------*- C++ -*--===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
if ((Val & 0xfff) != 0 && (Val & 1) == 0 && Res.size() >= 2) {
     // If we can use C.LI+C.SLLI instead of LUI+ADDI(W) prefer that since
     // its more compressible. But only if LUI+ADDI(W) isn't fusable.
     // NOTE: We don't check for C extension to minimize differences in generated
     // code.
     bool IsShiftedCompressible =
               isInt<6>(ShiftedVal) && !ActiveFeatures[RISCV::TuneLUIADDIFusion];
     RISCVMatInt::InstSeq TmpSeq;
     generateInstSeqImpl(ShiftedVal, ActiveFeatures, TmpSeq);
-    TmpSeq.emplace_back(RISCV::SLLI, TrailingZeros);
 
     // Keep the new sequence if it is an improvement.
-    if (TmpSeq.size() < Res.size() || IsShiftedCompressible)
+    if ((TmpSeq.size() + 1) < Res.size() || IsShiftedCompressible) {
+      TmpSeq.emplace_back(RISCV::SLLI, TrailingZeros);
       Res = TmpSeq;
     }
+  }
 
   // If we have a 1 or 2 instruction sequence this is the best we can do. This
   // will always be true for RV32 and will often be true for RV64.
   if (Res.size() <= 2)
     return Res;
 
   assert(ActiveFeatures[RISCV::Feature64Bit] &&
          "Expected RV32 to only need 2 instructions");
 
   // If the constant is positive we might be able to generate a shifted constant
   // with no leading zeros and use a final SRLI to restore them.
   if (Val > 0) {
     assert(Res.size() > 2 && "Expected longer sequence");
     unsigned LeadingZeros = llvm::countl_zero((uint64_t)Val);
     uint64_t ShiftedVal = (uint64_t)Val << LeadingZeros;
     // Fill in the bits that will be shifted out with 1s. An example where this
     // helps is trailing one masks with 32 or more ones. This will generate
     // ADDI -1 and an SRLI.
     ShiftedVal |= maskTrailingOnes<uint64_t>(LeadingZeros);
 
     RISCVMatInt::InstSeq TmpSeq;
     generateInstSeqImpl(ShiftedVal, ActiveFeatures, TmpSeq);
-    TmpSeq.emplace_back(RISCV::SRLI, LeadingZeros);
 
     // Keep the new sequence if it is an improvement.
-    if (TmpSeq.size() < Res.size())
+    if ((TmpSeq.size() + 1) < Res.size()) {
+      TmpSeq.emplace_back(RISCV::SRLI, LeadingZeros);
       Res = TmpSeq;
+    }
 
     // Some cases can benefit from filling the lower bits with zeros instead.
     ShiftedVal &= maskTrailingZeros<uint64_t>(LeadingZeros);
     TmpSeq.clear();
     generateInstSeqImpl(ShiftedVal, ActiveFeatures, TmpSeq);
-    TmpSeq.emplace_back(RISCV::SRLI, LeadingZeros);
 
     // Keep the new sequence if it is an improvement.
-    if (TmpSeq.size() < Res.size())
+    if ((TmpSeq.size() + 1) < Res.size()) {
+      TmpSeq.emplace_back(RISCV::SRLI, LeadingZeros);
       Res = TmpSeq;
+    }
 
     // If we have exactly 32 leading zeros and Zba, we can try using zext.w at
     // the end of the sequence.
     if (LeadingZeros == 32 && ActiveFeatures[RISCV::FeatureStdExtZba]) {
       // Try replacing upper bits with 1.
       uint64_t LeadingOnesVal = Val | maskLeadingOnes<uint64_t>(LeadingZeros);
       TmpSeq.clear();
       generateInstSeqImpl(LeadingOnesVal, ActiveFeatures, TmpSeq);
-      TmpSeq.emplace_back(RISCV::ADD_UW, 0);
 
       // Keep the new sequence if it is an improvement.
-      if (TmpSeq.size() < Res.size())
+      if ((TmpSeq.size() + 1) < Res.size()) {
+        TmpSeq.emplace_back(RISCV::ADD_UW, 0);
         Res = TmpSeq;
       }
     }
+  }
 
   // If the Low and High halves are the same, use pack. The pack instruction
   // packs the XLEN/2-bit lower halves of rs1 and rs2 into rd, with rs1 in the
   // lower half and rs2 in the upper half.
   if (Res.size() > 2 && ActiveFeatures[RISCV::FeatureStdExtZbkb]) {
     int64_t LoVal = SignExtend64<32>(Val);
     int64_t HiVal = SignExtend64<32>(Val >> 32);
     if (LoVal == HiVal) {
       RISCVMatInt::InstSeq TmpSeq;
       generateInstSeqImpl(LoVal, ActiveFeatures, TmpSeq);
+      if ((TmpSeq.size() + 1) < Res.size()) {
         TmpSeq.emplace_back(RISCV::PACK, 0);
-      if (TmpSeq.size() < Res.size())
         Res = TmpSeq;
       }
     }
+  }
 
   // Perform optimization with BCLRI/BSETI in the Zbs extension.
   if (Res.size() > 2 && ActiveFeatures[RISCV::FeatureStdExtZbs]) {
     // 1. For values in range 0xffffffff 7fffffff ~ 0xffffffff 00000000,
     //    call generateInstSeqImpl with Val|0x80000000 (which is expected be
     //    an int32), then emit (BCLRI r, 31).
     // 2. For values in range 0x80000000 ~ 0xffffffff, call generateInstSeqImpl
     //    with Val&~0x80000000 (which is expected to be an int32), then
     //    emit (BSETI r, 31).
     int64_t NewVal;
     unsigned Opc;
     if (Val < 0) {
       Opc = RISCV::BCLRI;
       NewVal = Val | 0x80000000ll;
     } else {
       Opc = RISCV::BSETI;
       NewVal = Val & ~0x80000000ll;
     }
     if (isInt<32>(NewVal)) {
       RISCVMatInt::InstSeq TmpSeq;
       generateInstSeqImpl(NewVal, ActiveFeatures, TmpSeq);
+      if ((TmpSeq.size() + 1) < Res.size()) {
         TmpSeq.emplace_back(Opc, 31);
-      if (TmpSeq.size() < Res.size())
         Res = TmpSeq;
       }
+    }
 
     // Try to use BCLRI for upper 32 bits if the original lower 32 bits are
     // negative int32, or use BSETI for upper 32 bits if the original lower
     // 32 bits are positive int32.
     int32_t Lo = Lo_32(Val);
     uint32_t Hi = Hi_32(Val);
     Opc = 0;
     RISCVMatInt::InstSeq TmpSeq;
if ((Val % 3) == 0 && isInt<32>(Val / 3)) {
       Opc = RISCV::SH2ADD;
     } else if ((Val % 9) == 0 && isInt<32>(Val / 9)) {
       Div = 9;
       Opc = RISCV::SH3ADD;
     }
     // Build the new instruction sequence.
     if (Div > 0) {
       generateInstSeqImpl(Val / Div, ActiveFeatures, TmpSeq);
+      if ((TmpSeq.size() + 1) < Res.size()) {
         TmpSeq.emplace_back(Opc, 0);
-      if (TmpSeq.size() < Res.size())
         Res = TmpSeq;
+      }
     } else {
       // Try to use LUI+SH*ADD+ADDI.
       int64_t Hi52 = ((uint64_t)Val + 0x800ull) & ~0xfffull;
       int64_t Lo12 = SignExtend64<12>(Val);
       Div = 0;
       if (isInt<32>(Hi52 / 3) && (Hi52 % 3) == 0) {
         Div = 3;
         Opc = RISCV::SH1ADD;
       } else if (isInt<32>(Hi52 / 5) && (Hi52 % 5) == 0) {
         Div = 5;
         Opc = RISCV::SH2ADD;
       } else if (isInt<32>(Hi52 / 9) && (Hi52 % 9) == 0) {
         Div = 9;
         Opc = RISCV::SH3ADD;
       }
       // Build the new instruction sequence.
       if (Div > 0) {
         // For Val that has zero Lo12 (implies Val equals to Hi52) should has
         // already been processed to LUI+SH*ADD by previous optimization.
         assert(Lo12 != 0 &&
                "unexpected instruction sequence for immediate materialisation");
         assert(TmpSeq.empty() && "Expected empty TmpSeq");
         generateInstSeqImpl(Hi52 / Div, ActiveFeatures, TmpSeq);
+        if ((TmpSeq.size() + 2) < Res.size()) {
           TmpSeq.emplace_back(Opc, 0);
           TmpSeq.emplace_back(RISCV::ADDI, Lo12);
-        if (TmpSeq.size() < Res.size())
           Res = TmpSeq;
         }
       }
     }
+  }
 
   // Perform optimization with rori in the Zbb and th.srri in the XTheadBb
   // extension.
   if (Res.size() > 2 && (ActiveFeatures[RISCV::FeatureStdExtZbb] ||
                          ActiveFeatures[RISCV::FeatureVendorXTHeadBb])) {
     if (unsigned Rotate = extractRotateInfo(Val)) {
       RISCVMatInt::InstSeq TmpSeq;
       uint64_t NegImm12 = llvm::rotl<uint64_t>(Val, Rotate);