[Subzero][MIPS32] Implements 64-bit shl, lshr, ashr for MIPS

src/IceTargetLoweringMIPS32.cpp

 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief Implements the TargetLoweringMIPS32 class, which consists almost
@@ skipping 1777 matching lines @@
                                         Variable *Dest, Operand *Src0,
                                         Operand *Src1) {
   InstArithmetic::OpKind Op = Instr->getOp();
   switch (Op) {
   case InstArithmetic::Add:
   case InstArithmetic::And:
   case InstArithmetic::Or:
   case InstArithmetic::Sub:
   case InstArithmetic::Xor:
   case InstArithmetic::Mul:
+  case InstArithmetic::Shl:
+  case InstArithmetic::Lshr:
+  case InstArithmetic::Ashr:
     break;
   default:
     UnimplementedLoweringError(this, Instr);
     return;
   }
   auto *DestLo = llvm::cast<Variable>(loOperand(Dest));
   auto *DestHi = llvm::cast<Variable>(hiOperand(Dest));
   Variable *Src0LoR = legalizeToReg(loOperand(Src0));
   Variable *Src1LoR = legalizeToReg(loOperand(Src1));
   Variable *Src0HiR = legalizeToReg(hiOperand(Src0));
@@ skipping 60 matching lines @@
     _mflo(T1, T_Lo);
     _mfhi(T2, T_Hi);
     _mov(DestLo, T1);
     _mul(TM1, Src0HiR, Src1LoR);
     _mul(TM2, Src0LoR, Src1HiR);
     _addu(TM3, TM1, T2);
     _addu(TM4, TM3, TM2);
     _mov(DestHi, TM4);
     return;
   }
+  case InstArithmetic::Shl: {
+    auto *T_Lo = I32Reg();
+    auto *T_Hi = I32Reg();
+    auto *T1_Lo = I32Reg();
+    auto *T1_Hi = I32Reg();
+    auto *T1 = I32Reg();
+    auto *T2 = I32Reg();
+    auto *T3 = I32Reg();
+    auto *T4 = I32Reg();
+    auto *T5 = I32Reg();
+    auto *T6 = I32Reg();
+    // The hi part of source 1 is not used since source 1 will contain value 64
+    // at the max
+    Context.insert<InstFakeUse>(Src1HiR);

[Jim Stichnoth, 2016/09/21 16:59:25]

Is the FakeUse (here and below) really necessary?  Consider these examples:

define internal i64 @shift1(i64 %opnd, i32 %shift32) {
  %shift64 = zext i32 %shift32 to i64
  br label %next
next:
  %result = shl i64 %opnd, %shift64
  ret i64 %result
}

define internal i64 @shift2(i64 %opnd, i64 %shift1, i64 %shift2) {
  %shift64 = add i64 %shift1, %shift2
  br label %next
next:
  %result = shl i64 %opnd, %shift64
  ret i64 %result
}

(The branch instructions are just so you can more easily see how each
instruction is individually lowered.)

In the first case, the zext puts a zero into the upper half of the i64, and then
the FakeUse forces that unused upper half to stay live.  Without the FakeUse, I
think the zero assignment would be naturally dead-code eliminated.  (This
assumes -O2 compilation).

In the second case, if you don't add the FakeUse, then the 64-bit add involving
the upper halves should be naturally dead-code eliminated.

[sagar.thakur, 2016/09/22 14:43:50]

Yes, the FakeUse should not be there.

+    _sllv(T1, Src0HiR, Src1LoR);
+    _addiu(T2, getZero(), -1);
+    _xor(T3, Src1LoR, T2);

[obucinac, 2016/09/21 16:33:31]

XOR with 0xFFFFFFFF lowers to NOT. For this case, you can use more efficient 
pseudo instruction NOT, based on NOR, available here:

https://codereview.chromium.org/2356293002/

[sagar.thakur, 2016/09/22 14:43:50]

Done.

+    _srl(T4, Src0LoR, 1);
+    _srlv(T5, T4, T3);
+    _or(T_Hi, T1, T5);
+    _sllv(T_Lo, Src0LoR, Src1LoR);
+
+    _mov(T1_Hi, T_Hi);
+    _mov(T1_Lo, T_Lo);
+    _andi(T6, Src1LoR, INT32_BITS);
+    _movn(T1_Hi, T_Lo, T6);
+    _movn(T1_Lo, getZero(), T6);
+    _mov(DestHi, T1_Hi);
+    _mov(DestLo, T1_Lo);
+    return;
+  }
+  case InstArithmetic::Lshr: {
+    auto *T_Lo = I32Reg();
+    auto *T_Hi = I32Reg();
+    auto *T1_Lo = makeReg(DestLo->getType());
+    auto *T1_Hi = makeReg(DestHi->getType());
+    auto *T1 = I32Reg();
+    auto *T2 = I32Reg();
+    auto *T3 = I32Reg();
+    auto *T4 = I32Reg();
+    auto *T5 = I32Reg();
+    auto *T6 = I32Reg();
+    // The hi part of source 1 is not used since source 1 will contain value 64
+    // at the max
+    Context.insert<InstFakeUse>(Src1HiR);
+    _srlv(T1, Src0LoR, Src1LoR);
+    _addiu(T2, getZero(), -1);
+    _xor(T3, Src1LoR, T2);
+    _sll(T4, Src0HiR, 1);
+    _sllv(T5, T4, T3);
+    _or(T_Lo, T1, T5);
+    _srlv(T_Hi, Src0HiR, Src1LoR);
+
+    _mov(T1_Hi, T_Hi);
+    _mov(T1_Lo, T_Lo);
+    _andi(T6, Src1LoR, INT32_BITS);
+    _movn(T1_Lo, T_Hi, T6);
+    _movn(T1_Hi, getZero(), T6);
+    _mov(DestHi, T1_Hi);
+    _mov(DestLo, T1_Lo);
+    return;
+  }
+  case InstArithmetic::Ashr: {
+    auto *T_Lo = I32Reg();
+    auto *T_Hi = I32Reg();
+    auto *T1_Lo = I32Reg();
+    auto *T1_Hi = I32Reg();
+    auto *T1 = I32Reg();
+    auto *T2 = I32Reg();
+    auto *T3 = I32Reg();
+    auto *T4 = I32Reg();
+    auto *T5 = I32Reg();
+    auto *T6 = I32Reg();
+    auto *T7 = I32Reg();
+    // The hi part of source 1 is not used since source 1 will contain value 64
+    // at the max
+    Context.insert<InstFakeUse>(Src1HiR);
+    _srlv(T1, Src0LoR, Src1LoR);
+    _addiu(T2, getZero(), -1);
+    _xor(T3, Src1LoR, T2);
+    _sll(T4, Src0HiR, 1);
+    _sllv(T5, T4, T3);
+    _or(T_Lo, T1, T5);
+    _srav(T_Hi, Src0HiR, Src1LoR);
+
+    _mov(T1_Hi, T_Hi);
+    _mov(T1_Lo, T_Lo);
+    _andi(T6, Src1LoR, INT32_BITS);
+    _movn(T1_Lo, T_Hi, T6);
+    _sra(T7, Src0HiR, INT32_BITS - 1);
+    _movn(T1_Hi, T7, T6);
+    _mov(DestHi, T1_Hi);
+    _mov(DestLo, T1_Lo);
+    return;
+  }
   default:
     UnimplementedLoweringError(this, Instr);
     return;
   }
 }
 
 void TargetMIPS32::lowerArithmetic(const InstArithmetic *Instr) {
   Variable *Dest = Instr->getDest();
   // We need to signal all the UnimplementedLoweringError errors before any
   // legalization into new variables, otherwise Om1 register allocation may fail
@@ skipping 1779 matching lines @@
   Str << "\t.set\t"
       << "nomips16\n";
 }
 
 SmallBitVector TargetMIPS32::TypeToRegisterSet[RCMIPS32_NUM];
 SmallBitVector TargetMIPS32::TypeToRegisterSetUnfiltered[RCMIPS32_NUM];
 SmallBitVector TargetMIPS32::RegisterAliases[RegMIPS32::Reg_NUM];
 
 } // end of namespace MIPS32
 } // end of namespace Ice