1

I'm using the following C code:

  unsigned int d = 5;
  return (n >> d)|(n << (32 - d));

Here is the generated assembly using gcc 4.9.2 (target=mips64-elf, however I assume that the target you use in this case does not matter)

  sll $2,$4,27 
  sra $4,$4,5  

  or  $2,$2,$4 
  j $31

What should be the C construct to make gcc generate a rotate instruction?

phuclv
  • 37,963
  • 15
  • 156
  • 475
Cherry Vanc
  • 781
  • 1
  • 4
  • 19
  • 1
    It does matter what target you use, obviously. It also matters what cpu you specified, because not all mips have hardware rotate. – Jester Nov 07 '14 at 00:50
  • There might be a `__builtin_`-esque intrinsic provided by GCC – Drew McGowen Nov 07 '14 at 03:36
  • 1
    according to [See MIPS run](http://books.google.co.in/books?id=kk8G2gK4Tw8C&pg=PA217&lpg=PA217&dq=mips+rotate+instruction&source=bl&ots=c-0Sk6JyWw&sig=yScr_S6Aoa3yPY5Xvcylv_OFIrM&hl=en&sa=X&ei=PmdcVPm4D4LiuQSt3IG4Aw&ved=0CEkQ6AEwBw#v=onepage&q=mips%20rotate%20instruction&f=false), rotate instructions are only available since MIPS32/64R2 – phuclv Nov 07 '14 at 07:30
  • [UTD's paper](https://www.utdallas.edu/~dodge/EE2310/lec14.pdf) said that "Note that in the MIPS computer, rol and ror are pseudo instructions, which are actually performed using both left and right shifts and an OR-ing of the two resulting shifts" but without specific microarchitecture – phuclv Nov 07 '14 at 07:32
  • I think UTD paper is out of date. MIPS64r2 does seem to have rotate opcodes http://scc.ustc.edu.cn/zlsc/lxwycj/200910/W020100308600769158777.pdf – Cherry Vanc Nov 07 '14 at 08:17
  • 1
    So, have you used the `--march=mips64r2` option? – Jester Nov 07 '14 at 12:41
  • To separate "recognize the rotate pattern in C code" from "generate a rotate instruction", you could compile with `-fdump-tree-optimized` and look at the file it writes. – Marc Glisse Nov 07 '14 at 16:35
  • Yes I was compiling with -mips64r2. Here is what I see in dump file ;; Function rightRotate (rightRotate, funcdef_no=1, decl_uid=993, symbol_order=1) rightRotate (int n) { int _2; int _3; int _4; : # DEBUG d => 5 _2 = n_1(D) >> 5; _3 = n_1(D) << 27; _4 = _3 | _2; return _4; } I think the issue is that the compiler hasnt been able to "recognise the rotate pattern" – Cherry Vanc Nov 07 '14 at 18:20
  • I've just had a look at gcc's builtins and there's no rotate builtin both [here](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) and [here](https://gcc.gnu.org/onlinedocs/gcc/Target-Builtins.html#Target-Builtins). Did you try a higher optimization level? – phuclv Nov 07 '14 at 19:29
  • Yes, I have tried O2, and O3. I am using the following flags to compile -mips64r2 -g -O3 -fno-delayed-branch – Cherry Vanc Nov 07 '14 at 21:15
  • 1
    https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/tree-ssa-forwprop.c?revision=217213&view=markup#l1758 gcc has code to recognize rotate, but it is still missing some https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62263. – Marc Glisse Nov 07 '14 at 21:27
  • 1
    Ah, your type needs to be unsigned, or the right shift won't do what you expect... – Marc Glisse Nov 07 '14 at 21:38
  • I think this should be closed, because you used `unsigned int` in the question but `int` in the source code. [GCC 4.1.2 recognizes the rotate even at `-O1`](https://godbolt.org/z/fiDvP7) – phuclv Feb 09 '19 at 09:02

1 Answers1

3

From the dump you show in the comments, it appears that n is signed. This means that, if n<0, the right shift may not be the logical shift that you expect. To get a valid rotate pattern, you need to make n unsigned.

Marc Glisse
  • 7,550
  • 2
  • 30
  • 53