[DONE] Constant Sequences for Constant Materialization

[kper]

Constant materialization is the term for building constants with machine instructions. This is necessary because a 32 bit architecture has 32 bit registers and can therefore store immediates up to 32 bits. However, machine instructions do not have such large immediate fields and need to split up the computation into multiple machine instructions.

At the moment, the constant materialization is heavily tailored to RISC-V. The LCB has a classification pass to discover the meaning of an instruction. Particularly, for RISC-V it will identify LUI and ADDI and write them into the file rv32imConstMatInt. In this class is a method to construct a sequence of instructions for the given value.

The implementation looks like this for riscv32 and was copied from upstream LLVM:

InstSeq generateInstSeqImpl(int64_t Val, rv32imMatInt::InstSeq &Res ) {
    if (isInt<32>(Val)) {
        // Depending on the active bits in the immediate Value v, the following
        // instruction sequences are emitted:
        //
        // v == 0                        : ADDI
        // v[0,12) != 0 && v[12,32) == 0 : ADDI
        // v[0,12) == 0 && v[12,32) != 0 : LUI
        // v[0,32) != 0                  : LUI+ADDI(W)
        auto Hi20 = RV3264I_Utype_immUp_encoding(2047 + 1 + Val);
        int64_t Lo12 = SignExtend64<12>(Val);

        if (Hi20)
          Res.emplace_back(rv32im::LUI, Hi20);

        if (Lo12 || Hi20 == 0) {
          unsigned AddiOpc = rv32im::ADDI;
          Res.emplace_back(AddiOpc, Lo12);
        }
        return Res;
      }

      int64_t Lo12 = SignExtend64<12>(Val);
      Val = (uint64_t)Val - (uint64_t)Lo12;

      int ShiftAmount = 0;
      bool Unsigned = false;

      // Val might now be valid for LUI without needing a shift.
      if (!isInt<32>(Val)) {
        ShiftAmount = llvm::countr_zero((uint64_t)Val);
        Val >>= ShiftAmount;

        // If the remaining bits don't fit in 12 bits, we might be able to reduce
        // the // shift amount in order to use LUI which will zero the lower 12
        // bits.
        if (ShiftAmount > 12 && !isInt<12>(Val)) {
          if (isInt<32>((uint64_t)Val << 12)) {
            // Reduce the shift amount and add zeros to the LSBs so it will match
            // LUI.
            ShiftAmount -= 12;
            Val = (uint64_t)Val << 12;
          }
        }
      }

      generateInstSeqImpl(Val, Res);

      // Skip shift if we were able to use LUI directly.
      if (ShiftAmount) {
        unsigned Opc = rv32im::SLLI;
        Res.emplace_back(Opc, ShiftAmount);
      }

      if (Lo12) {
        Res.emplace_back(rv32im::ADDI, Lo12);
      }

    return Res;
  }

The constant 4095 will be lowered to LUI a1,0x1 and ADDI a1,a1,-1. Notice that first the upper immediates get written which clears the lower bits and then ADDI adds the lower bits to the register. Unfortunately, this is different than Aarch64 and will not work.

movz    r0, #0x1234             ; r0 = 0x00001234
movk    r0, #0xABCD, LSL #16    ; r0 = 0xABCD1234

At the moment, I don't see any way to automatically detect how to build constants. I, therefore, see the need to change the language. In the old-vadl implementation, we had constant sequence to specify exactly that.

RISC-V:

constant sequence( rd : Bits<5>, val : SInt<32> ) =
{
      LUI ( rd, hi20( val )     )
      ADDI( rd, rd, lo12( val ) )
}
    
constant sequence( rd : Bits<5>, val : UInt<32> ) =
{
      LUI ( rd, hi20( val )     )
      ADDI( rd, rd, lo12( val ) )
}
    
constant sequence( rd : Bits<5>, imm : SInt<12> ) =
{
   ADDI{ rd = rd, rs1 = 0, imm = imm }
}

What if I have 64 bit registers and only riscv's LUI and ADDI? The compiler backend should automatically handle that by using a constant pool for example.

Aarch64:

constant sequence( rd : Bits<6>, imm : UInt<64> ) =
{
   MOVZ{ rd = rd, imm16 = imm & 0xFFFF }
   MOVK{ rd = rd, imm16 = (imm >> 16) & 0xFFFF }
   MOVK{ rd = rd, imm16 = (imm >> 32) & 0xFFFF }
   MOVK { rd = rd, imm16 = (imm >> 48) & 0xFFFF } 
}

I propose to add a new syntax element constant sequence which behaves exactly like a pseudo instruction but must not be handled by the AsmPrinter or AsmParser.

---

Note that this also a requires a change in ISelLowering since we construct a HI, LO pair for addresses.

template <class NodeTy>
SDValue rv32imTargetLowering::getAddr(NodeTy *N, SelectionDAG &DAG, bool IsLocal) const
{
    SDLoc DL(N);
    EVT Ty = getPointerTy(DAG.getDataLayout());

    // PC relative address
    if (isPositionIndependent())
    {
        SDValue Addr = getTargetNode(N, DL, Ty, DAG, 0);
        if (IsLocal)
        {
            report_fatal_error("Unsupported position independent local address loading");
        }
        // GOT access
        report_fatal_error("Unsupported position independent local address loading");
    }

    // address does not rely on PC
    switch (getTargetMachine().getCodeModel())
    {
    default:
    {
        report_fatal_error("Unsupported code model for lowering");
    }
    case CodeModel::Small:
    {
        SDValue AddrHi = getTargetNode(N, DL, Ty, DAG, rv32imBaseInfo::MO_RV3264I_hi_Itype_imm);
        SDValue AddrLo = getTargetNode(N, DL, Ty, DAG, rv32imBaseInfo::MO_RV3264I_lo_Itype_imm);
        SDValue MNHi = DAG.getNode(rv32imISD::HI, DL, Ty, AddrHi);
        return DAG.getNode(rv32imISD::ADD_LO, DL, Ty, MNHi, AddrLo);
    }
    }
}

[Jozott00]

This was implemented across PRs #86, #91, #93, #131, and #134.