[LLVMdev] rotate

Cameron McInally cameron.mcinally at nyu.edu
Tue Jul 31 08:42:42 PDT 2012


Andy,

Here is the left circular shift operator patch. I apologize to the reviewer
in advance. The patch has a good bit of fine detail. Any
comments/criticisms?

Some caveats...

1) This is just the bare minimum needed to make the left circular shift
operator work (e.g. no instruction combining).

2) I tried my best to select operator names in the existing style; please
feel free to change them as appropriate.

Ty,
Cameron

On Tue, Jul 31, 2012 at 8:05 AM, Cameron McInally
<cameron.mcinally at nyu.edu>wrote:

> Oh, no. I should have been more clear. The patch was not rejected, just
> lost in the daily shuffle.
>
> I already have my employer's approval to send this upstream, so I will
> prepare a patch against trunk this morning.
>
> > I proposed a similar patch to LLVM (left circular shift) around 10/2011.
>> > Parts of my patch did make it into trunk about a year after, but others
>> > did not.
>>
>
> And now that I reread this... it should have been "month after", not "year
> after".
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120731/b0bb7528/attachment.html>
-------------- next part --------------
Index: include/llvm/Instruction.def
===================================================================
--- include/llvm/Instruction.def	(revision 161045)
+++ include/llvm/Instruction.def	(working copy)
@@ -121,58 +121,59 @@
 // Logical operators (integer operands)
 HANDLE_BINARY_INST(20, Shl  , BinaryOperator) // Shift left  (logical)
 HANDLE_BINARY_INST(21, LShr , BinaryOperator) // Shift right (logical)
-HANDLE_BINARY_INST(22, AShr , BinaryOperator) // Shift right (arithmetic)
-HANDLE_BINARY_INST(23, And  , BinaryOperator)
-HANDLE_BINARY_INST(24, Or   , BinaryOperator)
-HANDLE_BINARY_INST(25, Xor  , BinaryOperator)
-  LAST_BINARY_INST(25)
+HANDLE_BINARY_INST(22, CShl , BinaryOperator) // Circular shift left  (logical)
+HANDLE_BINARY_INST(23, AShr , BinaryOperator) // Shift right (arithmetic)
+HANDLE_BINARY_INST(24, And  , BinaryOperator)
+HANDLE_BINARY_INST(25, Or   , BinaryOperator)
+HANDLE_BINARY_INST(26, Xor  , BinaryOperator)
+  LAST_BINARY_INST(26)
 
 // Memory operators...
- FIRST_MEMORY_INST(26)
-HANDLE_MEMORY_INST(26, Alloca, AllocaInst)  // Stack management
-HANDLE_MEMORY_INST(27, Load  , LoadInst  )  // Memory manipulation instrs
-HANDLE_MEMORY_INST(28, Store , StoreInst )
-HANDLE_MEMORY_INST(29, GetElementPtr, GetElementPtrInst)
-HANDLE_MEMORY_INST(30, Fence , FenceInst )
-HANDLE_MEMORY_INST(31, AtomicCmpXchg , AtomicCmpXchgInst )
-HANDLE_MEMORY_INST(32, AtomicRMW , AtomicRMWInst )
-  LAST_MEMORY_INST(32)
+ FIRST_MEMORY_INST(27)
+HANDLE_MEMORY_INST(27, Alloca, AllocaInst)  // Stack management
+HANDLE_MEMORY_INST(28, Load  , LoadInst  )  // Memory manipulation instrs
+HANDLE_MEMORY_INST(29, Store , StoreInst )
+HANDLE_MEMORY_INST(30, GetElementPtr, GetElementPtrInst)
+HANDLE_MEMORY_INST(31, Fence , FenceInst )
+HANDLE_MEMORY_INST(32, AtomicCmpXchg , AtomicCmpXchgInst )
+HANDLE_MEMORY_INST(33, AtomicRMW , AtomicRMWInst )
+  LAST_MEMORY_INST(33)
 
 // Cast operators ...
 // NOTE: The order matters here because CastInst::isEliminableCastPair 
 // NOTE: (see Instructions.cpp) encodes a table based on this ordering.
- FIRST_CAST_INST(33)
-HANDLE_CAST_INST(33, Trunc   , TruncInst   )  // Truncate integers
-HANDLE_CAST_INST(34, ZExt    , ZExtInst    )  // Zero extend integers
-HANDLE_CAST_INST(35, SExt    , SExtInst    )  // Sign extend integers
-HANDLE_CAST_INST(36, FPToUI  , FPToUIInst  )  // floating point -> UInt
-HANDLE_CAST_INST(37, FPToSI  , FPToSIInst  )  // floating point -> SInt
-HANDLE_CAST_INST(38, UIToFP  , UIToFPInst  )  // UInt -> floating point
-HANDLE_CAST_INST(39, SIToFP  , SIToFPInst  )  // SInt -> floating point
-HANDLE_CAST_INST(40, FPTrunc , FPTruncInst )  // Truncate floating point
-HANDLE_CAST_INST(41, FPExt   , FPExtInst   )  // Extend floating point
-HANDLE_CAST_INST(42, PtrToInt, PtrToIntInst)  // Pointer -> Integer
-HANDLE_CAST_INST(43, IntToPtr, IntToPtrInst)  // Integer -> Pointer
-HANDLE_CAST_INST(44, BitCast , BitCastInst )  // Type cast
-  LAST_CAST_INST(44)
+ FIRST_CAST_INST(34)
+HANDLE_CAST_INST(34, Trunc   , TruncInst   )  // Truncate integers
+HANDLE_CAST_INST(35, ZExt    , ZExtInst    )  // Zero extend integers
+HANDLE_CAST_INST(36, SExt    , SExtInst    )  // Sign extend integers
+HANDLE_CAST_INST(37, FPToUI  , FPToUIInst  )  // floating point -> UInt
+HANDLE_CAST_INST(38, FPToSI  , FPToSIInst  )  // floating point -> SInt
+HANDLE_CAST_INST(39, UIToFP  , UIToFPInst  )  // UInt -> floating point
+HANDLE_CAST_INST(40, SIToFP  , SIToFPInst  )  // SInt -> floating point
+HANDLE_CAST_INST(41, FPTrunc , FPTruncInst )  // Truncate floating point
+HANDLE_CAST_INST(42, FPExt   , FPExtInst   )  // Extend floating point
+HANDLE_CAST_INST(43, PtrToInt, PtrToIntInst)  // Pointer -> Integer
+HANDLE_CAST_INST(44, IntToPtr, IntToPtrInst)  // Integer -> Pointer
+HANDLE_CAST_INST(45, BitCast , BitCastInst )  // Type cast
+  LAST_CAST_INST(45)
 
 // Other operators...
- FIRST_OTHER_INST(45)
-HANDLE_OTHER_INST(45, ICmp   , ICmpInst   )  // Integer comparison instruction
-HANDLE_OTHER_INST(46, FCmp   , FCmpInst   )  // Floating point comparison instr.
-HANDLE_OTHER_INST(47, PHI    , PHINode    )  // PHI node instruction
-HANDLE_OTHER_INST(48, Call   , CallInst   )  // Call a function
-HANDLE_OTHER_INST(49, Select , SelectInst )  // select instruction
-HANDLE_OTHER_INST(50, UserOp1, Instruction)  // May be used internally in a pass
-HANDLE_OTHER_INST(51, UserOp2, Instruction)  // Internal to passes only
-HANDLE_OTHER_INST(52, VAArg  , VAArgInst  )  // vaarg instruction
-HANDLE_OTHER_INST(53, ExtractElement, ExtractElementInst)// extract from vector
-HANDLE_OTHER_INST(54, InsertElement, InsertElementInst)  // insert into vector
-HANDLE_OTHER_INST(55, ShuffleVector, ShuffleVectorInst)  // shuffle two vectors.
-HANDLE_OTHER_INST(56, ExtractValue, ExtractValueInst)// extract from aggregate
-HANDLE_OTHER_INST(57, InsertValue, InsertValueInst)  // insert into aggregate
-HANDLE_OTHER_INST(58, LandingPad, LandingPadInst)  // Landing pad instruction.
-  LAST_OTHER_INST(58)
+ FIRST_OTHER_INST(46)
+HANDLE_OTHER_INST(46, ICmp   , ICmpInst   )  // Integer comparison instruction
+HANDLE_OTHER_INST(47, FCmp   , FCmpInst   )  // Floating point comparison instr.
+HANDLE_OTHER_INST(48, PHI    , PHINode    )  // PHI node instruction
+HANDLE_OTHER_INST(49, Call   , CallInst   )  // Call a function
+HANDLE_OTHER_INST(50, Select , SelectInst )  // select instruction
+HANDLE_OTHER_INST(51, UserOp1, Instruction)  // May be used internally in a pass
+HANDLE_OTHER_INST(52, UserOp2, Instruction)  // Internal to passes only
+HANDLE_OTHER_INST(53, VAArg  , VAArgInst  )  // vaarg instruction
+HANDLE_OTHER_INST(54, ExtractElement, ExtractElementInst)// extract from vector
+HANDLE_OTHER_INST(55, InsertElement, InsertElementInst)  // insert into vector
+HANDLE_OTHER_INST(56, ShuffleVector, ShuffleVectorInst)  // shuffle two vectors.
+HANDLE_OTHER_INST(57, ExtractValue, ExtractValueInst)// extract from aggregate
+HANDLE_OTHER_INST(58, InsertValue, InsertValueInst)  // insert into aggregate
+HANDLE_OTHER_INST(59, LandingPad, LandingPadInst)  // Landing pad instruction.
+  LAST_OTHER_INST(59)
 
 #undef  FIRST_TERM_INST
 #undef HANDLE_TERM_INST
Index: include/llvm/Constants.h
===================================================================
--- include/llvm/Constants.h	(revision 161045)
+++ include/llvm/Constants.h	(working copy)
@@ -864,6 +864,7 @@
   static Constant *getShl(Constant *C1, Constant *C2,
                           bool HasNUW = false, bool HasNSW = false);
   static Constant *getLShr(Constant *C1, Constant *C2, bool isExact = false);
+  static Constant *getCShl(Constant *C1, Constant *C2);
   static Constant *getAShr(Constant *C1, Constant *C2, bool isExact = false);
   static Constant *getTrunc   (Constant *C, Type *Ty);
   static Constant *getSExt    (Constant *C, Type *Ty);
Index: include/llvm/IRBuilder.h
===================================================================
--- include/llvm/IRBuilder.h	(revision 161045)
+++ include/llvm/IRBuilder.h	(working copy)
@@ -691,6 +691,19 @@
     return CreateLShr(LHS, ConstantInt::get(LHS->getType(), RHS), Name,isExact);
   }
 
+  Value *CreateCShl(Value *LHS, Value *RHS, const Twine &Name = "") {
+    if (Constant *LC = dyn_cast<Constant>(LHS))
+      if (Constant *RC = dyn_cast<Constant>(RHS))
+        return Insert(Folder.CreateCShl(LC, RC), Name);
+    return Insert(BinaryOperator::CreateCShl(LHS, RHS), Name);
+  }
+  Value *CreateCShl(Value *LHS, const APInt &RHS, const Twine &Name = "") {
+    return CreateCShl(LHS, ConstantInt::get(LHS->getType(), RHS), Name);
+  }
+  Value *CreateCShl(Value *LHS, uint64_t RHS, const Twine &Name = "") {
+    return CreateCShl(LHS, ConstantInt::get(LHS->getType(), RHS), Name);
+  }
+
   Value *CreateAShr(Value *LHS, Value *RHS, const Twine &Name = "",
                     bool isExact = false) {
     if (Constant *LC = dyn_cast<Constant>(LHS))
Index: include/llvm/Support/ConstantFolder.h
===================================================================
--- include/llvm/Support/ConstantFolder.h	(revision 161045)
+++ include/llvm/Support/ConstantFolder.h	(working copy)
@@ -80,6 +80,9 @@
                        bool isExact = false) const {
     return ConstantExpr::getLShr(LHS, RHS, isExact);
   }
+  Constant *CreateCShl(Constant *LHS, Constant *RHS) {
+    return ConstantExpr::getCShl(LHS, RHS);
+  }
   Constant *CreateAShr(Constant *LHS, Constant *RHS,
                        bool isExact = false) const {
     return ConstantExpr::getAShr(LHS, RHS, isExact);
Index: include/llvm-c/Core.h
===================================================================
--- include/llvm-c/Core.h	(revision 161045)
+++ include/llvm-c/Core.h	(working copy)
@@ -206,54 +206,55 @@
   /* Logical Operators */
   LLVMShl            = 20,
   LLVMLShr           = 21,
-  LLVMAShr           = 22,
-  LLVMAnd            = 23,
-  LLVMOr             = 24,
-  LLVMXor            = 25,
+  LLVMCShl           = 22,
+  LLVMAShr           = 23,
+  LLVMAnd            = 24,
+  LLVMOr             = 25,
+  LLVMXor            = 26,
 
   /* Memory Operators */
-  LLVMAlloca         = 26,
-  LLVMLoad           = 27,
-  LLVMStore          = 28,
-  LLVMGetElementPtr  = 29,
+  LLVMAlloca         = 27,
+  LLVMLoad           = 28,
+  LLVMStore          = 29,
+  LLVMGetElementPtr  = 30,
 
   /* Cast Operators */
-  LLVMTrunc          = 30,
-  LLVMZExt           = 31,
-  LLVMSExt           = 32,
-  LLVMFPToUI         = 33,
-  LLVMFPToSI         = 34,
-  LLVMUIToFP         = 35,
-  LLVMSIToFP         = 36,
-  LLVMFPTrunc        = 37,
-  LLVMFPExt          = 38,
-  LLVMPtrToInt       = 39,
-  LLVMIntToPtr       = 40,
-  LLVMBitCast        = 41,
+  LLVMTrunc          = 31,
+  LLVMZExt           = 32,
+  LLVMSExt           = 33,
+  LLVMFPToUI         = 34,
+  LLVMFPToSI         = 35,
+  LLVMUIToFP         = 36,
+  LLVMSIToFP         = 37,
+  LLVMFPTrunc        = 38,
+  LLVMFPExt          = 39,
+  LLVMPtrToInt       = 40,
+  LLVMIntToPtr       = 41,
+  LLVMBitCast        = 42,
 
   /* Other Operators */
-  LLVMICmp           = 42,
-  LLVMFCmp           = 43,
-  LLVMPHI            = 44,
-  LLVMCall           = 45,
-  LLVMSelect         = 46,
-  LLVMUserOp1        = 47,
-  LLVMUserOp2        = 48,
-  LLVMVAArg          = 49,
-  LLVMExtractElement = 50,
-  LLVMInsertElement  = 51,
-  LLVMShuffleVector  = 52,
-  LLVMExtractValue   = 53,
-  LLVMInsertValue    = 54,
+  LLVMICmp           = 43,
+  LLVMFCmp           = 44,
+  LLVMPHI            = 45,
+  LLVMCall           = 46,
+  LLVMSelect         = 47,
+  LLVMUserOp1        = 48,
+  LLVMUserOp2        = 49,
+  LLVMVAArg          = 50,
+  LLVMExtractElement = 51,
+  LLVMInsertElement  = 52,
+  LLVMShuffleVector  = 53,
+  LLVMExtractValue   = 54,
+  LLVMInsertValue    = 55,
 
   /* Atomic operators */
-  LLVMFence          = 55,
-  LLVMAtomicCmpXchg  = 56,
-  LLVMAtomicRMW      = 57,
+  LLVMFence          = 56,
+  LLVMAtomicCmpXchg  = 57,
+  LLVMAtomicRMW      = 58,
 
   /* Exception Handling Operators */
-  LLVMResume         = 58,
-  LLVMLandingPad     = 59
+  LLVMResume         = 59,
+  LLVMLandingPad     = 60
 
 } LLVMOpcode;
 
Index: lib/VMCore/Verifier.cpp
===================================================================
--- lib/VMCore/Verifier.cpp	(revision 161045)
+++ lib/VMCore/Verifier.cpp	(working copy)
@@ -1255,6 +1255,7 @@
     break;
   case Instruction::Shl:
   case Instruction::LShr:
+  case Instruction::CShl:
   case Instruction::AShr:
     Assert1(B.getType()->isIntOrIntVectorTy(),
             "Shifts only work with integral types!", &B);
Index: lib/VMCore/Constants.cpp
===================================================================
--- lib/VMCore/Constants.cpp	(revision 161045)
+++ lib/VMCore/Constants.cpp	(working copy)
@@ -2002,6 +2002,10 @@
              isExact ? PossiblyExactOperator::IsExact : 0);
 }
 
+Constant *ConstantExpr::getCShl(Constant *C1, Constant *C2) {
+  return get(Instruction::CShl, C1, C2);
+}
+
 Constant *ConstantExpr::getAShr(Constant *C1, Constant *C2, bool isExact) {
   return get(Instruction::AShr, C1, C2,
              isExact ? PossiblyExactOperator::IsExact : 0);
Index: lib/Transforms/InstCombine/InstCombine.h
===================================================================
--- lib/Transforms/InstCombine/InstCombine.h	(revision 161045)
+++ lib/Transforms/InstCombine/InstCombine.h	(working copy)
@@ -134,6 +134,7 @@
   Instruction *visitOr (BinaryOperator &I);
   Instruction *visitXor(BinaryOperator &I);
   Instruction *visitShl(BinaryOperator &I);
+  Instruction *visitCShl(BinaryOperator &I);
   Instruction *visitAShr(BinaryOperator &I);
   Instruction *visitLShr(BinaryOperator &I);
   Instruction *commonShiftTransforms(BinaryOperator &I);
Index: lib/Transforms/InstCombine/InstCombineShifts.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineShifts.cpp	(revision 161045)
+++ lib/Transforms/InstCombine/InstCombineShifts.cpp	(working copy)
@@ -311,9 +311,13 @@
 
 Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
                                                BinaryOperator &I) {
+  if (I.getOpcode() == Instruction::CShl) {
+    // Don't combine circular shifts for now.
+    return 0;
+  }
+
   bool isLeftShift = I.getOpcode() == Instruction::Shl;
   
-  
   // See if we can propagate this shift into the input, this covers the trivial
   // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
   if (I.getOpcode() != Instruction::AShr &&
@@ -527,7 +531,12 @@
   BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0);
   if (ShiftOp && !ShiftOp->isShift())
     ShiftOp = 0;
-  
+ 
+  if (ShiftOp && ShiftOp->getOpcode() == Instruction::CShl) {
+    // Don't combine circular shifts for now.
+    return 0;
+  }
+ 
   if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) {
 
     // This is a constant shift of a constant shift. Be careful about hiding
@@ -755,6 +764,11 @@
   return 0;
 }
 
+Instruction *InstCombiner::visitCShl(BinaryOperator &I) {
+  // Don't combine circular shifts for now.
+  return 0;
+}
+
 Instruction *InstCombiner::visitAShr(BinaryOperator &I) {
   if (Value *V = SimplifyAShrInst(I.getOperand(0), I.getOperand(1),
                                   I.isExact(), TD))
Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
===================================================================
--- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h	(revision 161045)
+++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h	(working copy)
@@ -483,6 +483,7 @@
   void visitXor (const User &I) { visitBinary(I, ISD::XOR); }
   void visitShl (const User &I) { visitShift(I, ISD::SHL); }
   void visitLShr(const User &I) { visitShift(I, ISD::SRL); }
+  void visitCShl(const User &I) { visitShift(I, ISD::ROTL); }
   void visitAShr(const User &I) { visitShift(I, ISD::SRA); }
   void visitICmp(const User &I);
   void visitFCmp(const User &I);


More information about the llvm-dev mailing list