rol/ror llvm instruction set

Hi,

I was looking around the LLVM instruction set and I failed to find ROL and ROR instructions. Is there any plans on adding these instructions to LLVM?

The reason that I am asking is for cryptographical algorithms which are becoming ever more important rotation is a major operation. Thus including such instruction could reduce 3 instructions {shl, shr, or} into {rol | ror} which could gain considerable performance. However, the increased performance is not confined within crypto algorithms.

-- Kasra

Not sure what you mean:

  $ cat t.c
unsigned int rol(unsigned int i) {
   return i << 1 | i >> 31;
}
mrs $ clang -S t.c -O2
mrs $ cat t.s

  .text
  .align 4,0x90
  .globl _rol
_rol:
  movl 4(%esp), %eax
  roll %eax
  ret

?

I was looking around the LLVM instruction set and I failed to find
ROL and ROR instructions. Is there any plans on adding these
instructions to LLVM?

Not sure what you mean:

He's referring to the LLVM IR, I think, and it's true that doesn't have rotates. The LLVM back ends do know about rotate instructions on targets that have them, though, and the llvm optimizers are pretty smart about recognizing the usual ways to express rotate with shift/and/or, as below.

Look in the DAGCombiner.cpp file to see which patterns it translates
into ROTL and ROTR instructions.

-bw

From: Bill Wendling <isanbard@gmail.com>
Subject: Re: [LLVMdev] rol/ror llvm instruction set
To: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>
Cc: kasra_n500@yahoo.com
Date: Tuesday, February 3, 2009, 2:52 PM
>
>
>>> I was looking around the LLVM instruction set
and I failed to find
>>> ROL and ROR instructions. Is there any plans
on adding these
>>> instructions to LLVM?
>>
>> Not sure what you mean:
>
> He's referring to the LLVM IR, I think, and
it's true that doesn't
> have rotates. The LLVM back ends do know about rotate
instructions on
> targets that have them, though, and the llvm
optimizers are pretty
> smart about recognizing the usual ways to express
rotate with shift/
> and/or, as below.
>
Look in the DAGCombiner.cpp file to see which patterns it
translates
into ROTL and ROTR instructions.

-bw

I guess the backends could know about the instructions. But I am not convinced why it is beneficial not to have ROR and ROL instructions within llvm.

Look in the DAGCombiner.cpp file to see which patterns it
translates
into ROTL and ROTR instructions.

Right, I sure will do.

-- Kasra

I guess I could ask you the opposite question: What is the benefit of
having these? They would have to be mappable to the source language in
some way. I'm not sure about Ada, but I don't know of a "rotate"
operator for any of the C variants, or any other high-level language.
(This could be my lack of knowledge about other languages.) In C, you
specify a rotate by doing shifts and bit-wise operations.

This isn't to say that LLVM IR is C-specific. Just that if you did
have an LLVM rotate instruction, it would have to be generated by the
front-end -- currently by recognizing the same things that the DAG
combiner recognizes. And then it may need to be "lowered" for various
platforms that don't support it, which is greater than the number of
platforms that don't have shifts.

If a language came along that had rotate as a primitive and that
generated LLVM IR, then you could probably convince people that having
the rotates as LLVM IR instructions would be a benefit. We're not
above changing the language to support good things. :slight_smile:

-bw

How would it be beneficial to have them, if we already generate them at the target level properly? Adding instructions "just because" doesn't seem wise.

-Owen

You could not be more right. However, rotations was not widely implemented on machines when C and C++ was evolved. Python and other high level languages are just too high level (hence, inefficient) to have such semantics.

The argument sounds fine, however, remember that the number of platforms that don't implement an instruction could not be a point of simile.

Say we have 100 Linux distribution that do not have a certain feature, we can't conclude that that feature is not a common feature. We should consider the mainstream Linux distributions (and even if we may the giant of current desktops Windows).

Since x86 is about (if I am not wrong) 95% of the desktop PC's we could say rotation is implemented on most of the machines where LLVM will be running.

I bet out of the people who are reading/following this thread majority are running under x86 any way :smiley:

So I guess what I am saying is rotations is very wide spread except that there are many machines out there that do not implement it however, the number of machine that do is far grater.

-- Kasra

If you look at it the way you are it sounds fine. :smiley:

However, if we have 1 instruction we reduce the amount of time we will spend optomising.

I argued on my previous post that rotations are implemented on most machine (x86 platform). Thus it seems right to include 1 instruction in llvm and translate it to 3 instruction older architectures that have not implemented the rotation instruction yet.

I am sure that it is only matter of time before architectures without rotation instruction implementing it. Because of cryptography, it is becoming much more popular about 500% growth over the past decade (AES competitors against SHA-3 competitors). Crypto algorithms really like rotations since it is easily analysed and could be implemented efficiently

-- Kasra

I would like to include rotations in my HLL implementation but I am not averse
to encoding them myself.

I would not bet against you on that. :slight_smile: And, truth be told, it
probably wouldn't be too much of a hardship for platforms that don't
support rotates to lower them. But it's currently just extra work that
we don't need until we have a reason to add the rotate instructions.

-bw

Kasra wrote:

From: Owen Anderson <resistor@mac.com>
Subject: Re: [LLVMdev] rol/ror llvm instruction set
To: kasra_n500@yahoo.com, "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>
Date: Tuesday, February 3, 2009, 4:20 PM

I guess the backends could know about the

instructions. But I am not convinced why it is beneficial
not to have ROR and ROL instructions within llvm.
How would it be beneficial to have them, if we already
generate them at the target level properly? Adding
instructions "just because" doesn't seem wise.

-Owen

If you look at it the way you are it sounds fine. :smiley:

However, if we have 1 instruction we reduce the amount of time we will spend optomising.

No, it's the other way around. Adding rotate means we have two instructions that represent nearly the same thing, and the optimizers will have to match them both.

Designing the IR for a compiler is an art. LLVM has always tried to keep the number of instructions minimal, within reason. This means we write less code when working on an optimizer, analyzer, file formats, etc.

Unless you can show a strong case that rotate expresses something that is difficult to capture in the current IR, I don't think we're interested in adding it. You'd have better luck trying to convince me that we should replace shift with rotate than to suggest we have both.

Nick

Hi Bill,

I guess I could ask you the opposite question: What is the benefit of
having these? They would have to be mappable to the source language in
some way. I'm not sure about Ada, but I don't know of a "rotate"
operator for any of the C variants, or any other high-level language..

Ada has rotate.

Ciao,

Duncan.

Ada has so much. :slight_smile: How do you stand on the "LLVM IR-level rotate
instruction" issue? Has it been a pain for you to produce good code
without it?

-bw

> Ada has rotate.
>
Ada has so much. :slight_smile:

Too right :slight_smile:

How do you stand on the "LLVM IR-level rotate
instruction" issue? Has it been a pain for you to produce good code
without it?

Nope. In the cases I've looked at (not many!) it produced
a rotate machine operation in the final assembler.

Ciao,

Duncan.