[mips][microMIPS] Extending size reduction pass with ADDIUSP and ADDIUR1SP

[milena.vujosevic.janicic]

Summary

The patch extends size reduction pass for MicroMIPS.
The following instructions are examined and transformed, if possible:
ADDIU instruction is transformed into 16-bit instruction ADDIUSP
ADDIU instruction is transformed into 16-bit instruction ADDIUR1SP
Function InRange is changed to avoid left shifting of negative values, since
that caused some sanitizer tests to fail (so the previous patch
https://reviews.llvm.org/D33887 was reverted).

[sdardis]

lib/Target/Mips/MicroMipsSizeReduction.cpp

426 ↗

(On Diff #103564)

This is common between the two branches of the if, so it can be hoisted above the if.

429 ↗

(On Diff #103564)

This is common too, so it should be hoisted up.

462–463 ↗

(On Diff #103564)

Formatting: Break overly long conditional statements _after_ the '||' or '&&' operators, not before. i.e. This should be:

if (!Subtarget->inMicroMipsMode() || !Subtarget->hasMips32r2() ||
    Subtarget->hasMips32r6())

clang-format handles this.

[milena.vujosevic.janicic]

All the comments are taken into account.

[sdardis]

LGTM with nit addressed.

lib/Target/Mips/MicroMipsSizeReduction.cpp

443 ↗

(On Diff #104366)

Needs:

} else
  llvm_unreachable("Unknown operand transfer!");

llvm/trunk/lib/Target/Mips/MicroMipsSizeReduction.cpp

 
 namespace {
 
 /// Order of operands to transfer
 // TODO: Will be extended when additional optimizations are added
 enum OperandTransfer {
   OT_NA,          ///< Not applicable
   OT_OperandsAll, ///< Transfer all operands
+  OT_Operands02,  ///< Transfer operands 0 and 2
+  OT_Operand2,    ///< Transfer just operand 2
 };
 
 /// Reduction type
 // TODO: Will be extended when additional optimizations are added
 enum ReduceType {
   RT_OneInstr ///< Reduce one instruction into a smaller instruction
 };
 
private:
   // Attempts to reduce LBU/LHU instruction into LBU16/LHU16,
   // returns true on success.
   static bool ReduceLXUtoLXU16(MachineInstr *MI, const ReduceEntry &Entry);
 
   // Attempts to reduce SB/SH instruction into SB16/SH16,
   // returns true on success.
   static bool ReduceSXtoSX16(MachineInstr *MI, const ReduceEntry &Entry);
 
-  // Attempts to reduce arithmetic instructions, returns true on success
+  // Attempts to reduce arithmetic instructions, returns true on success.
   static bool ReduceArithmeticInstructions(MachineInstr *MI,
                                            const ReduceEntry &Entry);
 
-  // Changes opcode of an instruction
+  // Attempts to reduce ADDIU into ADDIUSP instruction,
+  // returns true on success.
+  static bool ReduceADDIUToADDIUSP(MachineInstr *MI, const ReduceEntry &Entry);
+
+  // Attempts to reduce ADDIU into ADDIUR1SP instruction,
+  // returns true on success.
+  static bool ReduceADDIUToADDIUR1SP(MachineInstr *MI,
+                                     const ReduceEntry &Entry);
+
+  // Changes opcode of an instruction.
   static bool ReplaceInstruction(MachineInstr *MI, const ReduceEntry &Entry);
 
-  // Table with transformation rules for each instruction
+  // Table with transformation rules for each instruction.
   static llvm::SmallVector<ReduceEntry, 16> ReduceTable;
 };
 
 char MicroMipsSizeReduce::ID = 0;
 const MipsInstrInfo *MicroMipsSizeReduce::MipsII;
 
 // This table must be sorted by WideOpc as a main criterion and
-// ReduceType as a sub-criterion (when wide opcodes are the same)
+// ReduceType as a sub-criterion (when wide opcodes are the same).
 llvm::SmallVector<ReduceEntry, 16> MicroMipsSizeReduce::ReduceTable = {
 
     // ReduceType, OpCodes, ReduceFunction,
     // OpInfo(TransferOperands),
     // ImmField(Shift, LBound, HBound, ImmFieldPosition)
+    {RT_OneInstr, OpCodes(Mips::ADDiu, Mips::ADDIUR1SP_MM),
+     ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)},
+    {RT_OneInstr, OpCodes(Mips::ADDiu, Mips::ADDIUSP_MM), ReduceADDIUToADDIUSP,
+     OpInfo(OT_Operand2), ImmField(0, 0, 0, 2)},
+    {RT_OneInstr, OpCodes(Mips::ADDiu_MM, Mips::ADDIUR1SP_MM),
+     ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)},
+    {RT_OneInstr, OpCodes(Mips::ADDiu_MM, Mips::ADDIUSP_MM),
+     ReduceADDIUToADDIUSP, OpInfo(OT_Operand2), ImmField(0, 0, 0, 2)},
     {RT_OneInstr, OpCodes(Mips::ADDu, Mips::ADDU16_MM),
      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
      ImmField(0, 0, 0, -1)},
     {RT_OneInstr, OpCodes(Mips::ADDu_MM, Mips::ADDU16_MM),
      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
      ImmField(0, 0, 0, -1)},
     {RT_OneInstr, OpCodes(Mips::LBu, Mips::LBU16_MM), ReduceLXUtoLXU16,
      OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 2)},
     {RT_OneInstr, OpCodes(Mips::LBu_MM, Mips::LBU16_MM), ReduceLXUtoLXU16,
      OpInfo(OT_OperandsAll), ImmField(0, -1, 15, 2)},
+    {RT_OneInstr, OpCodes(Mips::LEA_ADDiu, Mips::ADDIUR1SP_MM),
+     ReduceADDIUToADDIUR1SP, OpInfo(OT_Operands02), ImmField(2, 0, 64, 2)},
     {RT_OneInstr, OpCodes(Mips::LHu, Mips::LHU16_MM), ReduceLXUtoLXU16,
      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
     {RT_OneInstr, OpCodes(Mips::LHu_MM, Mips::LHU16_MM), ReduceLXUtoLXU16,
      OpInfo(OT_OperandsAll), ImmField(1, 0, 16, 2)},
     {RT_OneInstr, OpCodes(Mips::LW, Mips::LWSP_MM), ReduceXWtoXWSP,
      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
     {RT_OneInstr, OpCodes(Mips::LW_MM, Mips::LWSP_MM), ReduceXWtoXWSP,
      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
llvm::SmallVector<ReduceEntry, 16> MicroMipsSizeReduce::ReduceTable = {
     {RT_OneInstr, OpCodes(Mips::SUBu_MM, Mips::SUBU16_MM),
      ReduceArithmeticInstructions, OpInfo(OT_OperandsAll),
      ImmField(0, 0, 0, -1)},
     {RT_OneInstr, OpCodes(Mips::SW, Mips::SWSP_MM), ReduceXWtoXWSP,
      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
     {RT_OneInstr, OpCodes(Mips::SW_MM, Mips::SWSP_MM), ReduceXWtoXWSP,
      OpInfo(OT_OperandsAll), ImmField(2, 0, 32, 2)},
 };
-}
+} // namespace
 
-// Returns true if the machine operand MO is register SP
+// Returns true if the machine operand MO is register SP.
 static bool IsSP(const MachineOperand &MO) {
   if (MO.isReg() && ((MO.getReg() == Mips::SP)))
     return true;
   return false;
 }
 
 // Returns true if the machine operand MO is register $16, $17, or $2-$7.
 static bool isMMThreeBitGPRegister(const MachineOperand &MO) {
   if (MO.isReg() && Mips::GPRMM16RegClass.contains(MO.getReg()))
     return true;
   return false;
 }
 
 // Returns true if the machine operand MO is register $0, $17, or $2-$7.
 static bool isMMSourceRegister(const MachineOperand &MO) {
   if (MO.isReg() && Mips::GPRMM16ZeroRegClass.contains(MO.getReg()))
     return true;
   return false;
 }
 
 // Returns true if the operand Op is an immediate value
-// and writes the immediate value into variable Imm
+// and writes the immediate value into variable Imm.
 static bool GetImm(MachineInstr *MI, unsigned Op, int64_t &Imm) {
 
   if (!MI->getOperand(Op).isImm())
     return false;
   Imm = MI->getOperand(Op).getImm();
   return true;
 }
 
+// Returns true if the value is a valid immediate for ADDIUSP.
+static bool AddiuspImmValue(int64_t Value) {
+  int64_t Value2 = Value >> 2;
+  if (((Value & (int64_t)maskTrailingZeros<u_int64_t>(2)) == Value) &&
+      ((Value2 >= 2 && Value2 <= 257) || (Value2 >= -258 && Value2 <= -3)))
+    return true;
+  return false;
+}
+
 // Returns true if the variable Value has the number of least-significant zero
-// bits equal to Shift and if the shifted value is between the bounds
+// bits equal to Shift and if the shifted value is between the bounds.
 static bool InRange(int64_t Value, unsigned short Shift, int LBound,
                     int HBound) {
   int64_t Value2 = Value >> Shift;
-  if ((Value2 << Shift) == Value && (Value2 >= LBound) && (Value2 < HBound))
+  if (((Value & (int64_t)maskTrailingZeros<u_int64_t>(Shift)) == Value) &&
+      (Value2 >= LBound) && (Value2 < HBound))
     return true;
   return false;
 }
 
-// Returns true if immediate operand is in range
+// Returns true if immediate operand is in range.
 static bool ImmInRange(MachineInstr *MI, const ReduceEntry &Entry) {
 
   int64_t offset;
 
   if (!GetImm(MI, Entry.ImmField(), offset))
     return false;
 
   if (!InRange(offset, Entry.Shift(), Entry.LBound(), Entry.HBound()))
bool MicroMipsSizeReduce::ReduceArithmeticInstructions(
   if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
       !isMMThreeBitGPRegister(MI->getOperand(1)) ||
       !isMMThreeBitGPRegister(MI->getOperand(2)))
     return false;
 
   return ReplaceInstruction(MI, Entry);
 }
 
+bool MicroMipsSizeReduce::ReduceADDIUToADDIUR1SP(MachineInstr *MI,
+                                                 const ReduceEntry &Entry) {
+
+  if (!ImmInRange(MI, Entry))
+    return false;
+
+  if (!isMMThreeBitGPRegister(MI->getOperand(0)) || !IsSP(MI->getOperand(1)))
+    return false;
+
+  return ReplaceInstruction(MI, Entry);
+}
+
+bool MicroMipsSizeReduce::ReduceADDIUToADDIUSP(MachineInstr *MI,
+                                               const ReduceEntry &Entry) {
+
+  int64_t ImmValue;
+  if (!GetImm(MI, Entry.ImmField(), ImmValue))
+    return false;
+
+  if (!AddiuspImmValue(ImmValue))
+    return false;
+
+  if (!IsSP(MI->getOperand(0)) || !IsSP(MI->getOperand(1)))
+    return false;
+
+  return ReplaceInstruction(MI, Entry);
+}
+
 bool MicroMipsSizeReduce::ReduceLXUtoLXU16(MachineInstr *MI,
                                            const ReduceEntry &Entry) {
 
   if (!ImmInRange(MI, Entry))
     return false;
 
   if (!isMMThreeBitGPRegister(MI->getOperand(0)) ||
       !isMMThreeBitGPRegister(MI->getOperand(1)))
bool MicroMipsSizeReduce::ReduceMBB(MachineBasicBlock &MBB) {
   }
 
   return Modified;
 }
 
 bool MicroMipsSizeReduce::ReplaceInstruction(MachineInstr *MI,
                                              const ReduceEntry &Entry) {
 
-  MI->setDesc(MipsII->get(Entry.NarrowOpc()));
-  DEBUG(dbgs() << "Converted into 16-bit: " << *MI);
+  enum OperandTransfer OpTransfer = Entry.TransferOperands();
+
+  DEBUG(dbgs() << "Converting 32-bit: " << *MI);
   ++NumReduced;
+
+  if (OpTransfer == OT_OperandsAll) {
+    MI->setDesc(MipsII->get(Entry.NarrowOpc()));
+    DEBUG(dbgs() << "       to 16-bit: " << *MI);
     return true;
+  } else {
+    MachineBasicBlock &MBB = *MI->getParent();
+    const MCInstrDesc &NewMCID = MipsII->get(Entry.NarrowOpc());
+    DebugLoc dl = MI->getDebugLoc();
+    MachineInstrBuilder MIB = BuildMI(MBB, MI, dl, NewMCID);
+
+    if (OpTransfer == OT_Operand2)
+      MIB.add(MI->getOperand(2));
+    else if (OpTransfer == OT_Operands02) {
+      MIB.add(MI->getOperand(0));
+      MIB.add(MI->getOperand(2));
+    } else
+      llvm_unreachable("Unknown operand transfer!");
+
+    // Transfer MI flags.
+    MIB.setMIFlags(MI->getFlags());
+
+    DEBUG(dbgs() << "       to 16-bit: " << *MIB);
+    MBB.erase_instr(MI);
+    return true;
+  }
+  return false;
 }
 
 bool MicroMipsSizeReduce::runOnMachineFunction(MachineFunction &MF) {
 
   Subtarget = &static_cast<const MipsSubtarget &>(MF.getSubtarget());
 
   // TODO: Add support for other subtargets:
   // microMIPS32r6 and microMIPS64r6
-  if (!Subtarget->inMicroMipsMode() || !Subtarget->hasMips32r2())
+  if (!Subtarget->inMicroMipsMode() || !Subtarget->hasMips32r2() ||
+      Subtarget->hasMips32r6())
     return false;
 
   MipsII = static_cast<const MipsInstrInfo *>(Subtarget->getInstrInfo());
 
   bool Modified = false;
   MachineFunction::iterator I = MF.begin(), E = MF.end();
 
   for (; I != E; ++I)
     Modified |= ReduceMBB(*I);
   return Modified;
 }
 
 /// Returns an instance of the MicroMips size reduction pass.
 FunctionPass *llvm::createMicroMipsSizeReductionPass() {
   return new MicroMipsSizeReduce();
 }

llvm/trunk/test/CodeGen/Mips/micromips-sizereduction/micromips-addiur1sp-addiusp.ll

+; RUN: llc -march=mipsel -mcpu=mips32r2 -mattr=+micromips -verify-machineinstrs < %s | FileCheck %s
+
+define i32 @f1() {
+entry:
+; CHECK-LABEL: f1:
+; CHECK: addiusp
+; CHECK: addiur1sp
+; CHECK: addiusp
+  %a = alloca [10 x i32], align 4
+  %index = getelementptr inbounds [10 x i32], [10 x i32]* %a, i32 0, i32 0
+  call void @init(i32* %index)
+  %0 = load i32, i32* %index, align 4
+  ret i32 %0
+}
+
+declare void @init(i32*)
+