[RISCV] transform MI to W variant to remove sext.w

[mohammed-nurulhoque]

Summary

Backwards search
The sext.w removal pass (before the new patch) checks if the input to sext.w is already in sign-extended form, so it can eliminate it. It does that by checking every definition/source that reaches the sext.w is an instruction that produces a sign-extended value, either by definition (e.g. ADDW), or it propagates sign-extension (e.g. OR) so we check its sources recursively.

Forward search
Sometimes, one of the sources is an instruction that doesn't always produce a sign-extended value, but it has a W-version that does (e.g. ADD / ADDW). If we transform the ADD to ADDW, the sext.w can be removed (assuming other def paths are satisfied), but this transformation is sound only if every use of this ADD/W only reqruires the lower 32-bits either directly (like sll %x, 32) or they propagate dependency (lower word of output only depends on lower word of input) so we check its uses recursively.

When searching backwards, if an instruction that can be replaced with W-variant is encountered, this pass runs the forward search to verify it can be replaced, then adds it to a list of fixable instructions. After verifying all paths, it replaces the instruction and removes the sext.w.

[mohammed-nurulhoque]

I addressed the comments made in https://reviews.llvm.org/D119532 here, except the one for ADD_UW. I couldn't find a straightforward way to find, given an operand, what's its order in its parent instruction! The way it is currently is correct, but of course it would be stronger if we can differentiate the 2 operands.

[mohammed-nurulhoque]

Added test cases

[craig.topper]

llvm/lib/Target/RISCV/RISCVSExtWRemoval.cpp

256

Drop else after return.

276

Why do we need a cast to uint32_t here?

[mohammed-nurulhoque]

Fix style and typos

[craig.topper]

llvm/lib/Target/RISCV/RISCVSExtWRemoval.cpp

478

If this converts a load instruction, you need to copy the MachineMemOperand.

[mohammed-nurulhoque]

Add memoperands to replacement instruction

[craig.topper]

LGTM

[mohammed-nurulhoque]

Thanks. Could you commit the change? Here are my details
Name: Mohammed Nurul Hoque
email: [e-mail]

llvm/lib/Target/RISCV/RISCVSExtWRemoval.cpp

 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "riscv-sextw-removal"
 
 STATISTIC(NumRemovedSExtW, "Number of removed sign-extensions");
+STATISTIC(NumTransformedToWInstrs,
+          "Number of instructions transformed to W-ops");
 
 static cl::opt<bool> DisableSExtWRemoval("riscv-disable-sextw-removal",
                                          cl::desc("Disable removal of sext.w"),
                                          cl::init(false), cl::Hidden);
 namespace {
 
 class RISCVSExtWRemoval : public MachineFunctionPass {
 public:

 char RISCVSExtWRemoval::ID = 0;
 INITIALIZE_PASS(RISCVSExtWRemoval, DEBUG_TYPE, "RISCV sext.w Removal", false,
                 false)
 
 FunctionPass *llvm::createRISCVSExtWRemovalPass() {
   return new RISCVSExtWRemoval();
 }
 
+// add uses of MI to the Worklist
+static void addUses(const MachineInstr &MI,
+                    SmallVectorImpl<const MachineInstr *> &Worklist,
+                    MachineRegisterInfo &MRI) {
+  for (auto &UserOp : MRI.reg_operands(MI.getOperand(0).getReg())) {
+    const auto *User = UserOp.getParent();
+    if (User == &MI) // ignore the def, current MI
+      continue;
+    Worklist.push_back(User);
+  }
+}
+
+// returns true if all uses of OrigMI only depend on the lower word of its
+// output, so we can transform OrigMI to the corresponding W-version.
+// TODO: handle multiple interdependent transformations
+static bool isAllUsesReadW(const MachineInstr &OrigMI,
+                           MachineRegisterInfo &MRI) {
+
+  SmallPtrSet<const MachineInstr *, 4> Visited;
+  SmallVector<const MachineInstr *, 4> Worklist;
+
+  Visited.insert(&OrigMI);
+  addUses(OrigMI, Worklist, MRI);
+
+  while (!Worklist.empty()) {
+    const MachineInstr *MI = Worklist.pop_back_val();
+
+    if (!Visited.insert(MI).second) {
+      // If we've looped back to OrigMI through a PHI cycle, we can't transform
+      // LD or LWU, because these operations use all 64 bits of input.
+      if (MI == &OrigMI) {
+        unsigned opcode = MI->getOpcode();
+        if (opcode == RISCV::LD || opcode == RISCV::LWU)
+          return false;
+      }
+      continue;
+    }
+
+    switch (MI->getOpcode()) {
+    case RISCV::ADDIW:
+    case RISCV::ADDW:
+    case RISCV::DIVUW:
+    case RISCV::DIVW:
+    case RISCV::MULW:
+    case RISCV::REMUW:
+    case RISCV::REMW:
+    case RISCV::SLLIW:
+    case RISCV::SLLW:
+    case RISCV::SRAIW:
+    case RISCV::SRAW:
+    case RISCV::SRLIW:
+    case RISCV::SRLW:
+    case RISCV::SUBW:
+    case RISCV::ROLW:
+    case RISCV::RORW:
+    case RISCV::RORIW:
+    case RISCV::CLZW:
+    case RISCV::CTZW:
+    case RISCV::CPOPW:
+    case RISCV::SLLI_UW:
+    case RISCV::FCVT_S_W:
+    case RISCV::FCVT_S_WU:
+    case RISCV::FCVT_D_W:
+    case RISCV::FCVT_D_WU:
+      continue;
+
+    // these overwrite higher input bits, otherwise the lower word of output
+    // depends only on the lower word of input. So check their uses read W.
+    case RISCV::SLLI:
+      if (MI->getOperand(2).getImm() >= 32)
+        continue;
+      addUses(*MI, Worklist, MRI);
+      continue;
+    case RISCV::ANDI:
+      if (isUInt<11>(MI->getOperand(2).getImm()))
+        continue;
+      addUses(*MI, Worklist, MRI);
+      continue;
+    case RISCV::ORI:
+      if (!isUInt<11>(MI->getOperand(2).getImm()))
+        continue;
+      addUses(*MI, Worklist, MRI);
+      continue;
+
+    case RISCV::BEXTI:
+      if (MI->getOperand(2).getImm() >= 32)
+        return false;
+      continue;
+
+    // For these, lower word of output in these operations, depends only on
+    // the lower word of input. So, we check all uses only read lower word.
+    case RISCV::COPY:
+    case RISCV::PHI:
+
+    case RISCV::ADD:
+    case RISCV::ADDI:
+    case RISCV::AND:
+    case RISCV::MUL:
+    case RISCV::OR:
+    case RISCV::SLL:
+    case RISCV::SUB:
+    case RISCV::XOR:
+    case RISCV::XORI:
+
+    case RISCV::ADD_UW:
+    case RISCV::ANDN:
+    case RISCV::CLMUL:
+    case RISCV::ORC_B:
+    case RISCV::ORN:
+    case RISCV::SEXT_B:
+    case RISCV::SEXT_H:
+    case RISCV::SH1ADD:
+    case RISCV::SH1ADD_UW:
+    case RISCV::SH2ADD:
+    case RISCV::SH2ADD_UW:
+    case RISCV::SH3ADD:
+    case RISCV::SH3ADD_UW:
+    case RISCV::XNOR:
+    case RISCV::ZEXT_H_RV64:
+      addUses(*MI, Worklist, MRI);
+      continue;
+    default:
+      return false;
+    }
+  }
+  return true;
+}
+
 // This function returns true if the machine instruction always outputs a value
 // where bits 63:32 match bit 31.
+// Alternatively, if the instruction can be converted to W variant
+// (e.g. ADD->ADDW) and all of its uses only use the lower word of its output,
+// then return true and add the instr to FixableDef to be convereted later
 // TODO: Allocate a bit in TSFlags for the W instructions?
 // TODO: Add other W instructions.
-static bool isSignExtendingOpW(const MachineInstr &MI) {
+static bool isSignExtendingOpW(MachineInstr &MI, MachineRegisterInfo &MRI,
+                               SmallPtrSetImpl<MachineInstr *> &FixableDef) {
   switch (MI.getOpcode()) {
   case RISCV::LUI:
   case RISCV::LW:
   case RISCV::ADDW:
   case RISCV::ADDIW:
   case RISCV::SUBW:
   case RISCV::MULW:
   case RISCV::SLLW:
case RISCV::CTZ:
     return true;
   // shifting right sufficiently makes the value 32-bit sign-extended
   case RISCV::SRAI:
     return MI.getOperand(2).getImm() >= 32;
   case RISCV::SRLI:
     return MI.getOperand(2).getImm() > 32;
   // The LI pattern ADDI rd, X0, imm is sign extended.
   case RISCV::ADDI:
-    return MI.getOperand(1).isReg() && MI.getOperand(1).getReg() == RISCV::X0;
+    if (MI.getOperand(1).isReg() && MI.getOperand(1).getReg() == RISCV::X0)
+      return true;
+    if (isAllUsesReadW(MI, MRI)) {
+      // transform to ADDIW
+      FixableDef.insert(&MI);
+      return true;
+    }
+    return false;
   // An ANDI with an 11 bit immediate will zero bits 63:11.
   case RISCV::ANDI:
     return isUInt<11>(MI.getOperand(2).getImm());
   // An ORI with an >11 bit immediate (negative 12-bit) will set bits 63:11.
   case RISCV::ORI:
     return !isUInt<11>(MI.getOperand(2).getImm());
   // Copying from X0 produces zero.
   case RISCV::COPY:
     return MI.getOperand(1).getReg() == RISCV::X0;
+
+  // With these opcode, we can "fix" them with the W-version
+  // if we know all users of the result only rely on bits 31:0
+  case RISCV::SLLI:
+    // SLLIW reads the lowest 5 bits, while SLLI reads lowest 6 bits
+    if (MI.getOperand(2).getImm() >= 32)
+      return false;
+    LLVM_FALLTHROUGH;
+  case RISCV::ADD:
+  case RISCV::LD:
+  case RISCV::LWU:
+  case RISCV::MUL:
+  case RISCV::SUB:
+    if (isAllUsesReadW(MI, MRI)) {
+      FixableDef.insert(&MI);
+      return true;
+    }
   }
 
   return false;
 }
 
-static bool isSignExtendedW(const MachineInstr &OrigMI,
-                            MachineRegisterInfo &MRI) {
+static bool isSignExtendedW(MachineInstr &OrigMI, MachineRegisterInfo &MRI,
+                            SmallPtrSetImpl<MachineInstr *> &FixableDef) {
 
   SmallPtrSet<const MachineInstr *, 4> Visited;
-  SmallVector<const MachineInstr *, 4> Worklist;
+  SmallVector<MachineInstr *, 4> Worklist;
 
   Worklist.push_back(&OrigMI);
 
   while (!Worklist.empty()) {
-    const MachineInstr *MI = Worklist.pop_back_val();
+    MachineInstr *MI = Worklist.pop_back_val();
 
     // If we already visited this instruction, we don't need to check it again.
     if (!Visited.insert(MI).second)
       continue;
 
     // If this is a sign extending operation we don't need to look any further.
-    if (isSignExtendingOpW(*MI))
+    if (isSignExtendingOpW(*MI, MRI, FixableDef))
       continue;
 
     // Is this an instruction that propagates sign extend.
     switch (MI->getOpcode()) {
     default:
       // Unknown opcode, give up.
       return false;
     case RISCV::COPY: {
       Register SrcReg = MI->getOperand(1).getReg();
 
       // TODO: Handle arguments and returns from calls?
 
       // If this is a copy from another register, check its source instruction.
       if (!SrcReg.isVirtual())
         return false;
-      const MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
+      MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
       if (!SrcMI)
         return false;
 
       // Add SrcMI to the worklist.
       Worklist.push_back(SrcMI);
       break;
     }
 
while (!Worklist.empty()) {
     case RISCV::ORI:
     case RISCV::XORI: {
       // |Remainder| is always <= |Dividend|. If D is 32-bit, then so is R.
       // DIV doesn't work because of the edge case 0xf..f 8000 0000 / (long)-1
       // Logical operations use a sign extended 12-bit immediate.
       Register SrcReg = MI->getOperand(1).getReg();
       if (!SrcReg.isVirtual())
         return false;
-      const MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
+      MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
       if (!SrcMI)
         return false;
 
       // Add SrcMI to the worklist.
       Worklist.push_back(SrcMI);
       break;
     }
     case RISCV::REMU:
case RISCV::PHI: {
 
       for (unsigned I = 1; I != E; I += D) {
         if (!MI->getOperand(I).isReg())
           return false;
 
         Register SrcReg = MI->getOperand(I).getReg();
         if (!SrcReg.isVirtual())
           return false;
-        const MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
+        MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
         if (!SrcMI)
           return false;
 
         // Add SrcMI to the worklist.
         Worklist.push_back(SrcMI);
       }
 
       break;
     }
     }
   }
 
   // If we get here, then every node we visited produces a sign extended value
   // or propagated sign extended values. So the result must be sign extended.
   return true;
 }
 
+static unsigned getWOp(unsigned Opcode) {
+  switch (Opcode) {
+  case RISCV::ADDI:
+    return RISCV::ADDIW;
+  case RISCV::ADD:
+    return RISCV::ADDW;
+  case RISCV::LD:
+  case RISCV::LWU:
+    return RISCV::LW;
+  case RISCV::MUL:
+    return RISCV::MULW;
+  case RISCV::SLLI:
+    return RISCV::SLLIW;
+  case RISCV::SUB:
+    return RISCV::SUBW;
+  default:
+    llvm_unreachable("Unexpected opcode for replacement with W variant");
+  }
+}
+
 bool RISCVSExtWRemoval::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()) || DisableSExtWRemoval)
     return false;
 
   MachineRegisterInfo &MRI = MF.getRegInfo();
   const RISCVSubtarget &ST = MF.getSubtarget<RISCVSubtarget>();
 
   if (!ST.is64Bit())
     return false;
 
-  bool MadeChange = false;
+  SmallPtrSet<MachineInstr *, 4> SExtWRemovalCands;
+
+  // Replacing instructions invalidates the MI iterator
+  // we collect the candidates, then iterate over them separately.
   for (MachineBasicBlock &MBB : MF) {
     for (auto I = MBB.begin(), IE = MBB.end(); I != IE;) {
       MachineInstr *MI = &*I++;
 
       // We're looking for the sext.w pattern ADDIW rd, rs1, 0.
       if (MI->getOpcode() != RISCV::ADDIW || !MI->getOperand(2).isImm() ||
           MI->getOperand(2).getImm() != 0 || !MI->getOperand(1).isReg())
         continue;
 
       // Input should be a virtual register.
       Register SrcReg = MI->getOperand(1).getReg();
       if (!SrcReg.isVirtual())
         continue;
 
-      const MachineInstr &SrcMI = *MRI.getVRegDef(SrcReg);
-      if (!isSignExtendedW(SrcMI, MRI))
-        continue;
+      SExtWRemovalCands.insert(MI);
+    }
+  }
+
+  bool MadeChange = false;
+  for (auto MI : SExtWRemovalCands) {
+    SmallPtrSet<MachineInstr *, 4> FixableDef;
+    Register SrcReg = MI->getOperand(1).getReg();
+    MachineInstr &SrcMI = *MRI.getVRegDef(SrcReg);
+
+    // If all definitions reaching MI sign-extend their output,
+    // then sext.w is redundant
+    if (!isSignExtendedW(SrcMI, MRI, FixableDef))
 
-      Register DstReg = MI->getOperand(0).getReg();
-      if (!MRI.constrainRegClass(SrcReg, MRI.getRegClass(DstReg)))
-        continue;
+    // Replace Fixable instructions with their W versions.
+    for (MachineInstr *Fixable : FixableDef) {
+      MachineBasicBlock &MBB = *Fixable->getParent();
+      const DebugLoc &DL = Fixable->getDebugLoc();
+      unsigned Code = getWOp(Fixable->getOpcode());
+      MachineInstrBuilder Replacement =
+          BuildMI(MBB, Fixable, DL, ST.getInstrInfo()->get(Code));
+      for (auto Op : Fixable->operands())
+        Replacement.add(Op);
+      for (auto Op : Fixable->memoperands())
+        Replacement.addMemOperand(Op);
+
+      LLVM_DEBUG(dbgs() << "Replacing " << *Fixable);
+      LLVM_DEBUG(dbgs() << "     with " << *Replacement);
+
+      Fixable->eraseFromParent();
+      ++NumTransformedToWInstrs;
+    }
 
-      LLVM_DEBUG(dbgs() << "Removing redundant sign-extension\n");
-      MRI.replaceRegWith(DstReg, SrcReg);
-      MRI.clearKillFlags(SrcReg);
-      MI->eraseFromParent();
-      ++NumRemovedSExtW;
-      MadeChange = true;
-    }
-  }
 
   return MadeChange;
 }

llvm/test/CodeGen/RISCV/rv64zbt.ll

; RV64ZBT-NEXT:    ret
   %1 = tail call i64 @llvm.fshr.i64(i64 %a, i64 %b, i64 %c)
   ret i64 %1
 }
 
 define signext i32 @fshri_i32(i32 signext %a, i32 signext %b) nounwind {
 ; RV64I-LABEL: fshri_i32:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    srliw a1, a1, 5
-; RV64I-NEXT:    slli a0, a0, 27
+; RV64I-NEXT:    slliw a0, a0, 27
 ; RV64I-NEXT:    or a0, a0, a1
-; RV64I-NEXT:    sext.w a0, a0
 ; RV64I-NEXT:    ret
 ;
 ; RV64ZBT-LABEL: fshri_i32:
 ; RV64ZBT:       # %bb.0:
 ; RV64ZBT-NEXT:    fsriw a0, a1, a0, 5
 ; RV64ZBT-NEXT:    ret
   %1 = tail call i32 @llvm.fshr.i32(i32 %a, i32 %b, i32 5)
   ret i32 %1
; RV64ZBT-NEXT:    ret
   %1 = tail call i64 @llvm.fshr.i64(i64 %a, i64 %b, i64 5)
   ret i64 %1
 }
 
 define signext i32 @fshli_i32(i32 signext %a, i32 signext %b) nounwind {
 ; RV64I-LABEL: fshli_i32:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    srliw a1, a1, 27
-; RV64I-NEXT:    slli a0, a0, 5
+; RV64I-NEXT:    slliw a0, a0, 5
 ; RV64I-NEXT:    or a0, a0, a1
-; RV64I-NEXT:    sext.w a0, a0
 ; RV64I-NEXT:    ret
 ;
 ; RV64ZBT-LABEL: fshli_i32:
 ; RV64ZBT:       # %bb.0:
 ; RV64ZBT-NEXT:    fsriw a0, a1, a0, 27
 ; RV64ZBT-NEXT:    ret
   %1 = tail call i32 @llvm.fshl.i32(i32 %a, i32 %b, i32 5)
   ret i32 %1

llvm/test/CodeGen/RISCV/sextw-removal.ll

bb2:                                              ; preds = %bb2, %bb
   %i4 = tail call float @baz(i32 signext %i3)
   %i5 = bitcast float %i4 to i32
   %i6 = fcmp oeq float %i4, zeroinitializer
   br i1 %i6, label %bb7, label %bb2
 
 bb7:                                              ; preds = %bb2
   ret void
 }
+
+; simple test for forward-searching. (and 1234) only uses lower word of input
+define signext i32 @test11(i64 %arg1, i64 %arg2, i64 %arg3)  {
+; CHECK-LABEL: test11:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    addi a2, a2, -1
+; CHECK-NEXT:    li a3, 256
+; CHECK-NEXT:  .LBB10_1: # %bb2
+; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    andi a0, a0, 1234
+; CHECK-NEXT:    addi a2, a2, 1
+; CHECK-NEXT:    addw a0, a0, a1
+; CHECK-NEXT:    bltu a2, a3, .LBB10_1
+; CHECK-NEXT:  # %bb.2: # %bb7
+; CHECK-NEXT:    ret
+;
+; NOREMOVAL-LABEL: test11:
+; NOREMOVAL:       # %bb.0: # %entry
+; NOREMOVAL-NEXT:    addi a2, a2, -1
+; NOREMOVAL-NEXT:    li a3, 256
+; NOREMOVAL-NEXT:  .LBB10_1: # %bb2
+; NOREMOVAL-NEXT:    # =>This Inner Loop Header: Depth=1
+; NOREMOVAL-NEXT:    andi a0, a0, 1234
+; NOREMOVAL-NEXT:    addi a2, a2, 1
+; NOREMOVAL-NEXT:    add a0, a0, a1
+; NOREMOVAL-NEXT:    bltu a2, a3, .LBB10_1
+; NOREMOVAL-NEXT:  # %bb.2: # %bb7
+; NOREMOVAL-NEXT:    sext.w a0, a0
+; NOREMOVAL-NEXT:    ret
+entry:
+  br label %bb2
+
+bb2:                                              ; preds = %bb2, %entry
+  %i1 = phi i64 [ %arg1, %entry ], [ %i5, %bb2 ]
+  %i2 = phi i64 [ %arg3, %entry ], [ %i3, %bb2 ]
+  %i3 = add i64 %i2, 1
+  %i4 = and i64 %i1, 1234
+  %i5 = add i64 %i4, %arg2
+  %i6 = icmp ugt i64 %i2, 255
+  br i1 %i6, label %bb7, label %bb2
+
+bb7:                                              ; preds = %bb2
+  %i7 = trunc i64 %i5 to i32
+  ret i32 %i7
+}
+
+; circular use-dependency and multiple transformations.
+define signext i32 @test12(i64 %arg1, i64 %arg2, i64 %arg3)  {
+; CHECK-LABEL: test12:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    addi a3, a2, -1
+; CHECK-NEXT:    li a4, 256
+; CHECK-NEXT:  .LBB11_1: # %bb2
+; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    xor a0, a0, a1
+; CHECK-NEXT:    mulw a2, a0, a1
+; CHECK-NEXT:    addw a0, a0, a2
+; CHECK-NEXT:    and a2, a2, a0
+; CHECK-NEXT:    addi a3, a3, 1
+; CHECK-NEXT:    add a0, a2, a1
+; CHECK-NEXT:    bltu a3, a4, .LBB11_1
+; CHECK-NEXT:  # %bb.2: # %bb7
+; CHECK-NEXT:    mv a0, a2
+; CHECK-NEXT:    ret
+;
+; NOREMOVAL-LABEL: test12:
+; NOREMOVAL:       # %bb.0: # %entry
+; NOREMOVAL-NEXT:    addi a2, a2, -1
+; NOREMOVAL-NEXT:    li a3, 256
+; NOREMOVAL-NEXT:  .LBB11_1: # %bb2
+; NOREMOVAL-NEXT:    # =>This Inner Loop Header: Depth=1
+; NOREMOVAL-NEXT:    xor a0, a0, a1
+; NOREMOVAL-NEXT:    mul a4, a0, a1
+; NOREMOVAL-NEXT:    add a0, a0, a4
+; NOREMOVAL-NEXT:    and a4, a4, a0
+; NOREMOVAL-NEXT:    addi a2, a2, 1
+; NOREMOVAL-NEXT:    add a0, a4, a1
+; NOREMOVAL-NEXT:    bltu a2, a3, .LBB11_1
+; NOREMOVAL-NEXT:  # %bb.2: # %bb7
+; NOREMOVAL-NEXT:    sext.w a0, a4
+; NOREMOVAL-NEXT:    ret
+entry:
+  br label %bb2
+
+bb2:                                              ; preds = %bb2, %entry
+  %i1 = phi i64 [ %arg1, %entry ], [ %i6, %bb2 ]
+  %i2 = phi i64 [ %arg3, %entry ], [ %i3, %bb2 ]
+  %i3 = add i64 %i2, 1
+  %i4 = xor i64 %i1, %arg2
+  %i5 = mul i64 %i4, %arg2
+  %i9 = add i64 %i4, %i5
+  %i8 = and i64 %i5, %i9
+  %i6 = add i64 %i8, %arg2
+  %i7 = icmp ugt i64 %i2, 255
+  br i1 %i7, label %bb7, label %bb2
+
+bb7:                                              ; preds = %bb2
+  %r = trunc i64 %i8 to i32
+  ret i32 %r
+}
+
+; Not optimized. sdiv doesn't only use lower word
+define signext i32 @test13(i64 %arg1, i64 %arg2, i64 %arg3)  {
+; CHECK-LABEL: test13:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    addi a2, a2, -1
+; CHECK-NEXT:    li a3, 256
+; CHECK-NEXT:  .LBB12_1: # %bb2
+; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    div a0, a0, a1
+; CHECK-NEXT:    addi a2, a2, 1
+; CHECK-NEXT:    add a0, a0, a1
+; CHECK-NEXT:    bltu a2, a3, .LBB12_1
+; CHECK-NEXT:  # %bb.2: # %bb7
+; CHECK-NEXT:    sext.w a0, a0
+; CHECK-NEXT:    ret
+;
+; NOREMOVAL-LABEL: test13:
+; NOREMOVAL:       # %bb.0: # %entry
+; NOREMOVAL-NEXT:    addi a2, a2, -1
+; NOREMOVAL-NEXT:    li a3, 256
+; NOREMOVAL-NEXT:  .LBB12_1: # %bb2
+; NOREMOVAL-NEXT:    # =>This Inner Loop Header: Depth=1
+; NOREMOVAL-NEXT:    div a0, a0, a1
+; NOREMOVAL-NEXT:    addi a2, a2, 1
+; NOREMOVAL-NEXT:    add a0, a0, a1
+; NOREMOVAL-NEXT:    bltu a2, a3, .LBB12_1
+; NOREMOVAL-NEXT:  # %bb.2: # %bb7
+; NOREMOVAL-NEXT:    sext.w a0, a0
+; NOREMOVAL-NEXT:    ret
+entry:
+  br label %bb2
+
+bb2:                                              ; preds = %bb2, %entry
+  %i1 = phi i64 [ %arg1, %entry ], [ %i5, %bb2 ]
+  %i2 = phi i64 [ %arg3, %entry ], [ %i3, %bb2 ]
+  %i3 = add i64 %i2, 1
+  %i4 = sdiv i64 %i1, %arg2
+  %i5 = add i64 %i4, %arg2
+  %i6 = icmp ugt i64 %i2, 255
+  br i1 %i6, label %bb7, label %bb2
+
+bb7:                                              ; preds = %bb2
+  %i8 = trunc i64 %i5 to i32
+  ret i32 %i8
+}