[SelectionDAG] Utilize ARM shift behavior

[shawnl]

Summary

LLVM-IR shifts have UB if the shift amount is equal to or greater to
the shift range, but a number of architectures have well-defined
behavior in this case.

Utilize the behavior of ARM for shl and lshr to remove some code,
as can be seen in the tests.

Fixes PR41363

[nikic]

I suspect that it's not safe to do this in this form: While the shift instruction on the target might be well defined, this is still operating on ISD opcodes that consider out-of-bounds shifts to be undef. After you have eliminated the check, some other combine could come along and optimize the shift to undef based on that.

[craig.topper]

include/llvm/CodeGen/SelectionDAGNodes.h

729

Is this used?

[RKSimon]

Wouldn't it be better/safer to create ARMISD shift opcodes to handle this behaviour?

[dmgreen]

Hello

I was under the impression that the shift was by the bottom byte amount. i.e the mask is 255, and a shift of 256 is the same as a shift of 0. I have not tried it though.

For aarch64 the mask may to be the size of the datatype. The armarm will contain the correct information if you can decipher the pseudo code.

[bjope]

In D61400#1486885, @RKSimon wrote:

Wouldn't it be better/safer to create ARMISD shift opcodes to handle this behaviour?

I think so too. Even if this could be something that other targets could benefit from as well. And we need something safer since as @nikic mentioned this transform seem to be wrong (as it leaves the undefined shift unguarded, and later transforms might find that the shift count is out-of-bounds and remove the shift).

About the idea in general:
Our downstream target also accepts shift counts that are "out-of-bounds", so this looks like something we could benefit from. Although our target also does not have separate instructions for left/right shift. So basically a negative shift count in an SHL will become a right shift if we just lower the SHL into a target shift instruction. So the solution here would not work right out-of-the-box for our target (we would need some special "shift behavior"). So it might be difficult to make this generic enough to safely be reused by other targets (the different shift behaviors must be specified in detail).

About introducing target specific opcodes:
One tricky part is to decide when to introduce such target specific shifts. As soon as something is turned into a target specific ISD node you are "on you own" to handle further combines etc for that ISD node (including value tracking support etc). So usually you want to do it quite late. But then there is a risk that it is harder to detect the pattern (if other combines/legalization etc already has lowered/folded the SETCC etc into something else).

[efriedma]

Wouldn't it be better/safer to create ARMISD shift opcodes to handle this behaviour?

Agreed; we make assumptions about ISD::SHL etc. all over; changing that would be a lot of work, and might end up pessimizing code overall.

I was under the impression that the shift was by the bottom byte amount. i.e the mask is 255, and a shift of 256 is the same as a shift of 0. I have not tried it though.

This is true for NEON vectors, not scalars, as far as I can tell.

For aarch64 the mask may to be the size of the datatype. The armarm will contain the correct information if you can decipher the pseudo code.

Yes, lslv etc. masks the shift amount by the operand size.

[shawnl]

It is certainly not safe to do in LLVM-IR, but there has to be some point at which this can be done, and at this point it is still easy to match the pattern (although it does not match the -O0 pattern with an icmp instead of a select).

But yes, an ARMSHL/ARMLSR would be much safer.

include/llvm/CodeGen/SelectionDAGNodes.h

729

Oh, it is not any more...it will be removed.

[dmgreen]

I was under the impression that the shift was by the bottom byte amount. i.e the mask is 255, and a shift of 256 is the same as a shift of 0. I have not tried it though.

This is true for NEON vectors, not scalars, as far as I can tell.

The 8.1-m armarm seems to claim for LSL "The variable number of bits is read from the bottom byte of a register". It's an alias for MOV and there's a "shift_n = UInt(R[s]<7:0>);" in the pseudo code. I have been know to mis-read these things in the past though..

It's not the end of the world, but would mean that we would need to know that the shift amount is less that 256 as far as I understand.

[efriedma]

The 8.1-m armarm seems to claim for LSL "The variable number of bits is read from the bottom byte of a register"

You're right, sorry, I misread armarm.

[shawnl]

It's not the end of the world, but would mean that we would need to know that the shift amount is less that 256 as far as I understand.

It only works for this case:

if (n == 0)
return 0;
else
return (op0) << (64 - n);

include/llvm/CodeGen/ISDOpcodes.h

namespace ISD {
   }
 
   /// Return true if this is a setcc instruction that performs an unsigned
   /// comparison when used with integer operands.
   inline bool isUnsignedIntSetCC(CondCode Code) {
     return Code == SETUGT || Code == SETUGE || Code == SETULT || Code == SETULE;
   }
 
+  /// Return true if this is a setcc instruction that performs a greater-than
+  /// comparison when used with integer operands (signed or unsigned).
+  inline bool isGreaterThanIntSetCC(CondCode Code) {
+    return Code == SETGT || Code == SETGE || Code == SETUGT || Code == SETUGE;
+  }
+
   /// Return true if the specified condition returns true if the two operands to
   /// the condition are equal. Note that if one of the two operands is a NaN,
   /// this value is meaningless.
   inline bool isTrueWhenEqual(CondCode Cond) {
     return ((int)Cond & 1) != 0;
   }
 
   /// This function returns 0 if the condition is always false if an operand is

include/llvm/CodeGen/SelectionDAGNodes.h

public:
   bool hasOneUse() const {
     return !use_empty() && std::next(use_begin()) == use_end();
   }
 
   /// Return the number of uses of this node. This method takes
   /// time proportional to the number of uses.
   size_t use_size() const { return std::distance(use_begin(), use_end()); }
 
+  /// Return the number of uses of this node. This method takes
+  /// time proportional to the number of uses, limited to MaxDistance.
+  size_t use_size(size_t MaxDistance) const {
+    size_t Dist = 0;
+    for (auto I = use_begin(), E = use_end(); I != E; ++I)
+      if (Dist++ == MaxDistance)
+        break;
+    return Dist;
+  }
+
   /// Return the unique node id.
   int getNodeId() const { return NodeId; }
 
   /// Set unique node id.
   void setNodeId(int Id) { NodeId = Id; }
 
   /// Return the node ordering.
   unsigned getIROrder() const { return IROrder; }

include/llvm/CodeGen/TargetLowering.h

public:
   enum SelectSupportKind {
     ScalarValSelect,      // The target supports scalar selects (ex: cmov).
     ScalarCondVectorVal,  // The target supports selects with a scalar condition
                           // and vector values (ex: cmov).
     VectorMaskSelect      // The target supports vector selects with a vector
                           // mask (ex: x86 blends).
   };
 
+  /// Enum that describes the behavior of SHIFT instructions
+  enum ShiftBehavior {
+    ShiftStrict, // What LLVM IR defines, range 0 to bitwidth - 1
+    ShiftMasked,
+    ShiftOutOfRangeToZeroOrSignBit,
+  };
+
   /// Enum that specifies what an atomic load/AtomicRMWInst is expanded
   /// to, if at all. Exists because different targets have different levels of
   /// support for these atomic instructions, and also have different options
   /// w.r.t. what they should expand to.
   enum class AtomicExpansionKind {
     None,    // Don't expand the instruction.
     LLSC,    // Expand the instruction into loadlinked/storeconditional; used
              // by ARM/AArch64.
public:
 
   /// Return true if SHIFT instructions should be expanded to SHIFT_PARTS
   /// instructions, and false if a library call is preferred (e.g for code-size
   /// reasons).
   virtual bool shouldExpandShift(SelectionDAG &DAG, SDNode *N) const {
     return true;
   }
 
+  /// Return true if SHIFT instructions return 0 when the operand is equal or
+  /// greater than the bit width.
+  virtual enum ShiftBehavior getShiftBehavior() const { return ShiftStrict; }
+
   /// Return true if the target has native support for the specified value type.
   /// This means that it has a register that directly holds it without
   /// promotions or expansions.
   bool isTypeLegal(EVT VT) const {
     assert(!VT.isSimple() ||
            (unsigned)VT.getSimpleVT().SimpleTy < array_lengthof(RegClassForVT));
     return VT.isSimple() && RegClassForVT[VT.getSimpleVT().SimpleTy] != nullptr;
   }

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
 
     SDValue XformToShuffleWithZero(SDNode *N);
     SDValue reassociateOpsCommutative(unsigned Opc, const SDLoc &DL, SDValue N0,
                                       SDValue N1);
     SDValue reassociateOps(unsigned Opc, const SDLoc &DL, SDValue N0,
                            SDValue N1, SDNodeFlags Flags);
 
     SDValue visitShiftByConstant(SDNode *N, ConstantSDNode *Amt);
+    bool UnguardShift(SDNode *N, SDValue *Out);
 
     SDValue foldSelectOfConstants(SDNode *N);
     SDValue foldVSelectOfConstants(SDNode *N);
     SDValue foldBinOpIntoSelect(SDNode *BO);
     bool SimplifySelectOps(SDNode *SELECT, SDValue LHS, SDValue RHS);
     SDValue hoistLogicOpWithSameOpcodeHands(SDNode *N);
     SDValue SimplifySelect(const SDLoc &DL, SDValue N0, SDValue N1, SDValue N2);
     SDValue SimplifySelectCC(const SDLoc &DL, SDValue N0, SDValue N1,
if (CondVT.isInteger() &&
     if (VT.bitsEq(CondVT))
       return NotCond;
     return DAG.getZExtOrTrunc(NotCond, DL, VT);
   }
 
   return SDValue();
 }
 
+// If this select is guarding a shift from undefined behavior,
+// and on this platform that shift is well-defined, remove the select.
+bool DAGCombiner::UnguardShift(SDNode *N, SDValue *Out) {
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+  SDValue N2 = N->getOperand(2);
+  EVT VT = N->getValueType(0);
+  if (DAG.getTargetLoweringInfo().getShiftBehavior() !=
+      TargetLoweringBase::ShiftOutOfRangeToZeroOrSignBit)
+    return false;
+
+  // Are we selecting from a shift?
+  SDValue *Shift;
+  if (N1.getOpcode() == ISD::SHL || N1.getOpcode() == ISD::SRL) {
+    Shift = &N1;
+    if (!(N2.getOpcode() == ISD::Constant && N->getConstantOperandVal(2) == 0))
+      return false;
+  } else if (N2.getOpcode() == ISD::SHL || N2.getOpcode() == ISD::SRL) {
+    Shift = &N2;
+    if (!(N1.getOpcode() == ISD::Constant && N->getConstantOperandVal(1) == 0))
+      return false;
+  } else if (N1.getOpcode() == ISD::SRA) {
+    return false; // FIXME
+  } else if (N2.getOpcode() == ISD::SRA) {
+    return false; // FIXME
+  } else
+    return false;
+
+  // Is N0 a check?
+  enum ISD::NodeType O = (enum ISD::NodeType)N0->getOpcode();
+  if (O != ISD::SETCC)
+    return false;
+  CondCodeSDNode *Cond = dyn_cast<CondCodeSDNode>(N0->getOperand(2));
+  if (!Cond)
+    return false;
+  enum ISD::CondCode CC = Cond->get();
+  SDValue Walk = N0->getOperand(1);
+  if (Walk->getOpcode() == ISD::ZERO_EXTEND)
+    Walk = Walk->getOperand(0);
+  if (Walk->getOpcode() != ISD::Constant)
+    return false;
+  uint64_t Const = N0->getConstantOperandVal(1);
+
+  // Does the check guard against UB?
+  bool Succeeded = false;
+  if (ISD::isGreaterThanIntSetCC(CC)) {
+    if (!ISD::isTrueWhenEqual(CC))
+      Const++;
+    if (VT.getScalarSizeInBits() == Const) {
+      Walk = Shift->getOperand(1);
+      if (Walk->getOpcode() == ISD::ZERO_EXTEND)
+        Walk = Walk->getOperand(0);
+      if (N0->getOperand(0) == Walk)
+        Succeeded = true;
+    }
+  } else if (CC == ISD::SETEQ && Const == 0) {
+    Walk = Shift->getOperand(1);
+    if (Walk->getOpcode() == ISD::ZERO_EXTEND)
+      Walk = Walk->getOperand(0);
+    if (Walk->getOpcode() != ISD::SUB)
+      return false;
+    // Why is the constant on the left here, when in LLVM-IR it is always on the
+    // right?
+    if (Walk->getOperand(0)->getOpcode() == ISD::Constant &&
+        Walk->getConstantOperandVal(0) == VT.getScalarSizeInBits())
+      if (N0->getOperand(0) == Walk->getOperand(1))
+        Succeeded = true;
+  }
+
+  if (!Succeeded)
+    return false;
+  *Out = *Shift;
+  return true;
+}
+
 SDValue DAGCombiner::visitSELECT(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDValue N2 = N->getOperand(2);
   EVT VT = N->getValueType(0);
   EVT VT0 = N0.getValueType();
   SDLoc DL(N);
 
   if (SDValue V = DAG.simplifySelect(N0, N1, N2))
     return V;
 
   // fold (select X, X, Y) -> (or X, Y)
   // fold (select X, 1, Y) -> (or C, Y)
   if (VT == VT0 && VT == MVT::i1 && (N0 == N1 || isOneConstant(N1)))
     return DAG.getNode(ISD::OR, DL, VT, N0, N2);
 
   if (SDValue V = foldSelectOfConstants(N))
     return V;
 
+  SDValue Shift;
+  if (UnguardShift(N, &Shift))
+    return Shift;
+
   // fold (select C, 0, X) -> (and (not C), X)
   if (VT == VT0 && VT == MVT::i1 && isNullConstant(N1)) {
     SDValue NOTNode = DAG.getNOT(SDLoc(N0), N0, VT);
     AddToWorklist(NOTNode.getNode());
     return DAG.getNode(ISD::AND, DL, VT, NOTNode, N2);
   }
   // fold (select C, X, 1) -> (or (not C), X)
   if (VT == VT0 && VT == MVT::i1 && isOneConstant(N2)) {

lib/Target/AArch64/AArch64ISelLowering.h

public:
   }
 
   bool shouldExpandShift(SelectionDAG &DAG, SDNode *N) const override {
     if (DAG.getMachineFunction().getFunction().hasMinSize())
       return false;
     return true;
   }
 
+  enum ShiftBehavior getShiftBehavior() const override {
+    return ShiftOutOfRangeToZeroOrSignBit;
+  }
+
   bool shouldTransformSignedTruncationCheck(EVT XVT,
                                             unsigned KeptBits) const override {
     // For vectors, we don't have a preference..
     if (XVT.isVector())
       return false;
 
     auto VTIsOk = [](EVT VT) -> bool {
       return VT == MVT::i8 || VT == MVT::i16 || VT == MVT::i32 ||

lib/Target/ARM/ARMISelLowering.h

public:
     }
 
     bool hasStandaloneRem(EVT VT) const override {
       return HasStandaloneRem;
     }
 
     bool shouldExpandShift(SelectionDAG &DAG, SDNode *N) const override;
 
+    enum ShiftBehavior getShiftBehavior() const override {
+      return ShiftOutOfRangeToZeroOrSignBit;
+    }
+
     CCAssignFn *CCAssignFnForCall(CallingConv::ID CC, bool isVarArg) const;
     CCAssignFn *CCAssignFnForReturn(CallingConv::ID CC, bool isVarArg) const;
 
     /// Returns true if \p VecTy is a legal interleaved access type. This
     /// function checks the vector element type and the overall width of the
     /// vector.
     bool isLegalInterleavedAccessType(VectorType *VecTy,
                                       const DataLayout &DL) const;

lib/Target/X86/X86ISelLowering.h

public:
     }
 
     bool shouldExpandShift(SelectionDAG &DAG, SDNode *N) const override {
       if (DAG.getMachineFunction().getFunction().hasMinSize())
         return false;
       return true;
     }
 
+    enum ShiftBehavior getShiftBehavior() const override { return ShiftMasked; }
+
     bool shouldSplatInsEltVarIndex(EVT VT) const override;
 
     bool convertSetCCLogicToBitwiseLogic(EVT VT) const override {
       return VT.isScalarInteger();
     }
 
     /// Vector-sized comparisons are fast using PCMPEQ + PMOVMSK or PTEST.
     MVT hasFastEqualityCompare(unsigned NumBits) const override;

test/CodeGen/AArch64/unguard-shifts.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=aarch64-linux-gnu | FileCheck %s
+; ModuleID = 'shr.c'
+source_filename = "shr.c"
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @lshr(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: lshr:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    neg w8, w0
+; CHECK-NEXT:    mov w9, #-1
+; CHECK-NEXT:    lsr w0, w9, w8
+; CHECK-NEXT:    ret
+  %2 = icmp eq i32 %0, 0
+  %3 = sub nsw i32 32, %0
+  %4 = lshr i32 -1, %3
+  %5 = select i1 %2, i32 0, i32 %4
+  ret i32 %5
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @lshr2(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: lshr2:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #-1
+; CHECK-NEXT:    lsr w0, w8, w0
+; CHECK-NEXT:    ret
+  %2 = icmp sgt i32 %0, 31
+  %3 = lshr i32 -1, %0
+  %4 = select i1 %2, i32 0, i32 %3
+  ret i32 %4
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @lshr3(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: lshr3:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #-1
+; CHECK-NEXT:    lsr w0, w8, w0
+; CHECK-NEXT:    ret
+  %2 = icmp sgt i32 %0, 31
+  %3 = lshr i32 -1, %0
+  %4 = select i1 %2, i32 0, i32 %3
+  ret i32 %4
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @shl(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: shl:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    neg w8, w0
+; CHECK-NEXT:    mov w9, #-1
+; CHECK-NEXT:    lsl w0, w9, w8
+; CHECK-NEXT:    ret
+  %2 = icmp eq i32 %0, 0
+  %3 = sub nsw i32 32, %0
+  %4 = shl i32 -1, %3
+  %5 = select i1 %2, i32 0, i32 %4
+  ret i32 %5
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @shl2(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: shl2:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #-1
+; CHECK-NEXT:    lsl w0, w8, w0
+; CHECK-NEXT:    ret
+  %2 = icmp sgt i32 %0, 31
+  %3 = shl i32 -1, %0
+  %4 = select i1 %2, i32 0, i32 %3
+  ret i32 %4
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @shl3(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: shl3:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #-1
+; CHECK-NEXT:    lsl w0, w8, w0
+; CHECK-NEXT:    ret
+  %2 = icmp sgt i32 %0, 31
+  %3 = shl i32 -1, %0
+  %4 = select i1 %2, i32 0, i32 %3
+  ret i32 %4
+}
+
+attributes #0 = { norecurse nounwind readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="generic" "target-features"="+neon" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 7.0.1-8 (tags/RELEASE_701/final)"}

test/CodeGen/ARM/unguard-shifts.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=arm-eabi | FileCheck %s
+; ModuleID = 'shr.c'
+source_filename = "shr.c"
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv4t--linux-gnueabi"
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @lshr(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: lshr:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rsb r0, r0, #32
+; CHECK-NEXT:    mvn r1, #0
+; CHECK-NEXT:    lsr r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %2 = icmp eq i32 %0, 0
+  %3 = sub nsw i32 32, %0
+  %4 = lshr i32 -1, %3
+  %5 = select i1 %2, i32 0, i32 %4
+  ret i32 %5
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @lshr2(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: lshr2:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mvn r1, #0
+; CHECK-NEXT:    lsr r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %2 = icmp sgt i32 %0, 31
+  %3 = lshr i32 -1, %0
+  %4 = select i1 %2, i32 0, i32 %3
+  ret i32 %4
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @lshr3(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: lshr3:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mvn r1, #0
+; CHECK-NEXT:    lsr r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %2 = icmp sgt i32 %0, 31
+  %3 = lshr i32 -1, %0
+  %4 = select i1 %2, i32 0, i32 %3
+  ret i32 %4
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @shl(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: shl:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    rsb r0, r0, #32
+; CHECK-NEXT:    mvn r1, #0
+; CHECK-NEXT:    lsl r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %2 = icmp eq i32 %0, 0
+  %3 = sub nsw i32 32, %0
+  %4 = shl i32 -1, %3
+  %5 = select i1 %2, i32 0, i32 %4
+  ret i32 %5
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @shl2(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: shl2:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mvn r1, #0
+; CHECK-NEXT:    lsl r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %2 = icmp sgt i32 %0, 31
+  %3 = shl i32 -1, %0
+  %4 = select i1 %2, i32 0, i32 %3
+  ret i32 %4
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @shl3(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: shl3:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    mvn r1, #0
+; CHECK-NEXT:    lsl r0, r1, r0
+; CHECK-NEXT:    bx lr
+  %2 = icmp sgt i32 %0, 31
+  %3 = shl i32 -1, %0
+  %4 = select i1 %2, i32 0, i32 %3
+  ret i32 %4
+}
+
+attributes #0 = { norecurse nounwind readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="arm7tdmi" "target-features"="+armv4t,+soft-float,+strict-align,-crypto,-d16,-fp-armv8,-fp-only-sp,-fp16,-neon,-thumb-mode,-vfp2,-vfp3,-vfp4" "unsafe-fp-math"="false" "use-soft-float"="true" }
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 1, !"min_enum_size", i32 4}
+!2 = !{!"clang version 7.0.1-8 (tags/RELEASE_701/final)"}