[Info-vax] Anyone still around ? :-)

[Louis Krupp]

On Wed, 09 Oct 2019 20:29:16 -0600, Louis Krupp
<lkrupp at nospam.pssw.com.invalid> wrote:

>On Thu, 10 Oct 2019 00:40:35 +0200, hb <end.of at inter.net> wrote:
>
>>On 10/9/19 11:55 PM, Louis Krupp wrote:
>>> On Tue, 8 Oct 2019 07:19:39 -0700 (PDT), osuvman50 at gmail.com wrote:
>>> 
>>>> I was considering making a post about the failure of the C compiler's optimizer
>>>> to recognize and optimize the pattern:
>>>>
>>>>     choice = permutation % (CARDS_IN_DECK-i);
>>>>     permutation = permutation / (CARDS_IN_DECK-i);
>>>>
>>>> but didn't think I'd get any constructive responses. (refactoring to eliminate a
>>>> divide makes the whole program run 18% faster on both alpha and IA64).
>>> 
>>> For what it's worth, GNU C++ on Linux doesn't optimize it either, but
>>> GNU Fortran does at optimization level 1. If you have a FORTRAN
>>> compiler, you'll probably have to tweak this code a bit (getting rid
>>> of the colons, for example) to try it:
>>> 
>>> subroutine s(permutation, choice, i)
>>>     implicit none
>>>     integer :: permutation, choice, i
>>>     integer, parameter :: CARDS_IN_DECK = 52
>>>     choice = mod(permutation, (CARDS_IN_DECK-i))
>>>     permutation = permutation / (CARDS_IN_DECK-i)
>>> end subroutine
>>> 
>>> Louis
>>> 
>>
>>What kind of optimization do you expect?
>>
>>#define CARDS_IN_DECK 52
>>extern int permutation,  choice;
>>void foo (int i) {
>>        choice = permutation % (CARDS_IN_DECK-i);
>>        permutation = permutation / (CARDS_IN_DECK-i);
>>}
>>$
>>$ gcc -m64 -S -O3 foo.c
<snip>
>>$
>
>I expected what you got. My test case, which I should have posted, was
>a bit different:
>
>const int CARDS_IN_DECK = 52;
>
>void s(int& permutation, int& choice, int i)
>{
>    choice = permutation % (CARDS_IN_DECK-i);
>    permutation = permutation / (CARDS_IN_DECK-i);
>}
>
>and the results were:
>
>    movl    (%rdi), %eax
>    movl    $52, %ecx
>    subl    %edx, %ecx
>    cltd
>    idivl   %ecx
>    movl    %edx, (%rsi)
>    movl    (%rdi), %eax
>    cltd
>    idivl   %ecx
>    movl    %eax, (%rdi)
>    ret
>
>Changing permutation and choice to externals make all the difference,
>for whatever reason...
>

My guess -- in case anyone is wondering -- is that Fortran has
stricter anti-aliasing rules than C++. When the input permutation
argument is passed by value instead of by reference:

const int CARDS_IN_DECK = 52;

void s(int perm_in, int& perm_out, int& choice_out, int i)
{
    choice_out = perm_in % (CARDS_IN_DECK-i);
    perm_out = perm_in / (CARDS_IN_DECK-i);
}

GNU C++ does the expected optimization at -O1:

	movq	%rdx, %r8
	movl	%ecx, %eax
	movl	$52, %ecx
	subl	%eax, %ecx
	movl	%edi, %eax
	cltd
	idivl	%ecx
	movl	%edx, (%r8)
	movl	%eax, (%rsi)
	ret

Louis