Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.std.c > #1854 > unrolled thread

Loop Invariance Optimization Opportunity?

Back to article view | Back to comp.std.c

Contents

  Loop Invariance Optimization Opportunity? Shao Miller <sha0.miller@gmail.com> - 2013-01-18 08:25 -0500
    Re: Loop Invariance Optimization Opportunity? Wojtek Lerch <wojtek_l@yahoo.ca> - 2013-01-18 12:25 -0500
      Re: Loop Invariance Optimization Opportunity? Shao Miller <sha0.miller@gmail.com> - 2013-01-18 15:36 -0500
        Re: Loop Invariance Optimization Opportunity? Shao Miller <sha0.miller@gmail.com> - 2013-01-21 00:43 -0500

#1854 — Loop Invariance Optimization Opportunity?

The code below demonstrates a loop where the termination condition might 
present an opportunity for invariance.  The code attempts to avoid 
violating "effective type" rules[6.5p7], but there could be an error.

GCC without an -O, with -O2, and with -O3 didn't make any difference in 
the behaviour.  If an invariance optimization is used, the loop should 
iterate 42 times, instead of 21.

   #include <stddef.h>
   #include <stdio.h>

   struct visible {
       float f;
       int i;
     };

   int looper(long * lp, struct visible * vis) {
       int c;

       /*
        * '*lp' isn't expected to alias into '*vis'
        * '*vis = *vis' might be optimized away
        * '(*vis = *vis)' yields an rvalue
        * The 'i' member value of the _rvalue_ is read,
        * possibly optimized to be read just once
        */
       for (c = 0; c < (*vis = *vis).i; ++c)
         --*lp;

       return c;
     }

   int int_and_long(unsigned char * ptr, int i) {
       long l = i;
       unsigned char
         * ip = (void *) &i,
         * const ipe = (void *) (&i + 1),
         * lp = (void *) &l;

       if (sizeof i != sizeof l)
         return 1;

       /* Combine object representation from 'int'/'long' */
       while (ip < ipe) {
           if (*ip != *lp)
             return 1;
           *ptr++ = *ip++ & *lp++;
         }
       return 0;
     }

   int main(void) {
       /* Union type not visible to looper */
       union {
           struct visible vis;
           struct invisible {
               char a, b, c, d;
               long l;
             } invis;
         } u;
       /* Point these at 'u.vis.i'/'u.invis.l' */
       unsigned char * ptr =
         (unsigned char *) &u + offsetof(struct invisible, l);
       long * lp = (long *) ptr;

       if (offsetof(struct visible, i) != offsetof(struct invisible, l))
         return 0;

       /*
        * Make a hybrid 'long'/'int' with value 42, without
        * using membership of 'u'
        */
       if (int_and_long(ptr, 42))
         return 0;

       /* Invoke the looper.  42 or 21?! */
       printf("Looped: %d\n", looper(lp, (void *) &u));
       return 0;
     }

-- 
- Shao Miller
--
"Thank you for the kind words; those are the kind of words I like to hear.

Cheerily,"  -- Richard Harter

[toc] | [next] | [standalone]

#1855

On 18-Jan-13 8:25 AM, Shao Miller wrote:
> GCC without an -O, with -O2, and with -O3 didn't make any difference in
> the behaviour.  If an invariance optimization is used, the loop should
> iterate 42 times, instead of 21.

Have you tried you moving "looper" into a separate translation unit?

I'm getting 42 with GCC 4.4.2, but 21 with GCC 4.6.3.

[toc] | [prev] | [next] | [standalone]

#1858

On 1/18/2013 12:25, Wojtek Lerch wrote:
> On 18-Jan-13 8:25 AM, Shao Miller wrote:
>> GCC without an -O, with -O2, and with -O3 didn't make any difference in
>> the behaviour.  If an invariance optimization is used, the loop should
>> iterate 42 times, instead of 21.
>
> Have you tried you moving "looper" into a separate translation unit?
>
> I'm getting 42 with GCC 4.4.2, but 21 with GCC 4.6.3.

Aha!  Thank you for those measurements!  Just out of curiosity, were you 
using a >= C99 mode (where effective type is applicable)?

I had used -ansi and -std=c99 with GCC 4.5.3 for Cygwin, originally.

GCC 4.7.2 on Linux x86:

   gcc -ansi -pedantic -Wall -Wextra -Werror -o rvalue rvalue.c : 21

All combinations of -std=c99, -std=c1x, -std=c11, -O2, -O3 made no 
difference.

CLANG 3.0 on Linux x86:

   clang -ansi -pedantic -Wall -Wextra -Werror -o rvalue rvalue.c : 21

All combinations of -std=c99, -std=c1x, -O2, -O3 made no difference.

Copying the 'struct visible' definition into rvalue2.c and moving 
'looper' into it didn't change clang's behaviour.

   gcc -O2 -ansi -pedantic -Wall -Wextra -Werror -o rvalue rvalue.c 
rvalue2.c : 22 (?!)

Same with -O3.  Same with -std=c99, -std=c1x, -std=c11 or any of these 
with -O3.

I cannot reproduce 42. :(

-- 
- Shao Miller
--
"Thank you for the kind words; those are the kind of words I like to hear.

Cheerily,"  -- Richard Harter

[toc] | [prev] | [next] | [standalone]

#1873

On 1/18/2013 15:36, Shao Miller wrote:
>
> I cannot reproduce 42. :(
>

I was able to reproduce 42 by:

   - Using GCC with -O3
   - Using two translation units
   - Changing the code to have '((void) 0, *vis).i' instead of '(*vis = 
*vis).i'.

Using the comma operator is probably a better demonstration of not 
possibly changing any effective type considerations, anyway.

-- 
- Shao Miller
--
"Thank you for the kind words; those are the kind of words I like to hear.

Cheerily,"  -- Richard Harter

[toc] | [prev] | [standalone]

Back to top | Article view | comp.std.c

csiph-web