--- On Tue, 2/3/09, Bill Wendling <isanbard at gmail.com> wrote:> From: Bill Wendling <isanbard at gmail.com> > Subject: Re: [LLVMdev] rol/ror llvm instruction set > To: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Cc: kasra_n500 at yahoo.com > Date: Tuesday, February 3, 2009, 2:52 PM > On Tue, Feb 3, 2009 at 2:45 PM, Dale Johannesen > <dalej at apple.com> wrote: > > > > On Feb 3, 2009, at 2:35 PMPST, Mike Stump wrote: > > > >> On Feb 3, 2009, at 2:28 PM, Kasra wrote: > >>> 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. > > -bwI 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
On Tue, Feb 3, 2009 at 3:54 PM, Kasra <kasra_n500 at yahoo.com> wrote:> > 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. >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. :-) -bw
On Feb 3, 2009, at 3:54 PM, Kasra wrote:> 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
--- On Tue, 2/3/09, Bill Wendling <isanbard at gmail.com> wrote:> From: Bill Wendling <isanbard at gmail.com> > Subject: Re: [LLVMdev] rol/ror llvm instruction set > To: kasra_n500 at yahoo.com, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Date: Tuesday, February 3, 2009, 4:17 PM > On Tue, Feb 3, 2009 at 3:54 PM, Kasra > <kasra_n500 at yahoo.com> wrote: > > > > 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. > > > 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. :-) > > -bwYou 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 :D 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
--- On Tue, 2/3/09, Owen Anderson <resistor at mac.com> wrote:> From: Owen Anderson <resistor at mac.com> > Subject: Re: [LLVMdev] rol/ror llvm instruction set > To: kasra_n500 at yahoo.com, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Date: Tuesday, February 3, 2009, 4:20 PM > On Feb 3, 2009, at 3:54 PM, Kasra wrote: > > 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. > > -OwenIf you look at it the way you are it sounds fine. :D 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
On Wednesday 04 February 2009 00:17:49 Bill Wendling wrote:> 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. :-)I would like to include rotations in my HLL implementation but I am not averse to encoding them myself. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e
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.