[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

429

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

432

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

461–463

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

Needs:

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

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));
+    }
+
+    // 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();
 }

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*)
+