How can I elide additional calls to an idempotent function?

Question

Is there a way to tell gcc that a function that has side effects should only be called once if two subsequent calls have the same arguments. I want the following behaviour:

foo(6);//run this function
foo(6);//optimize this away
foo(6);//optimize this away
foo(5);//run this function
foo(6);//run this function again

I can make foo check a global variable before it does any work, but that is less than optimal.

void inline foo(int i){
   static int last_i=i+1;
   if(last_i != i){
        last_i==i;
        //do_work...
    }
}

Since foo is an inline function the compiler should be able to look across invokations of foo() and see that it doesn't have to execute it. The problem is the compiler can't optimize like that for global variables, is there a way to let the compiler know it is safe to do so?

Answer 1

... a function that has side effects should only be called once if two subsequent calls have the same arguments...

That function has to be idempotent then although it has side effects.

C++ standard only distinguish functions with side effects (I/O functions) and without. From compilers point of view if the function is opaque (no definition in the same translation unit) then it must have side effects and therefore it is a compiler memory barrier and the compiler cannot optimize the call away or deduce the return value (unless it is a compiler intrinsic function like memcpy).

Idempotence, computer science meaning:

In computer science, the term idempotent is used more comprehensively to describe an operation that will produce the same results if executed once or multiple times.[4] This may have a different meaning depending on the context in which it is applied. In the case of methods or subroutine calls with side effects, for instance, it means that the modified state remains the same after the first call. In functional programming, though, an idempotent function is one that has the property f(f(x)) = f(x) for any value x.[5]

And C++ does not have that notion.

Answer 2

You could use static variables:

int foo(int param){
   static int last=0;
   static int result=1;
   if(last==param) return result;
   else{
      last=param;
      result=param/2+1;
      return result;
   }
}

Answer 3

in order for a compiler to optimize away a function with side effects it would have to understand the side effects it produces. GCC has no annotation to describe the type of side effects so it is not possible.

If the function is in the same compilation unit the compiler might be able to figure out the calls are redundant, but as that only works if the function is simple enough for the compiler to completely understand which is seldom the case. You are better of putting that logic into the caller or callee.

For completeness, if the function does not have side affects you can use __attribute__((pure)) and __attribute__((const)) to tell the compiler this.

Answer 4

No. This behavior is not part of the semantics of any language of the many I have seen and certainly not C/C++. Gcc can't provide options to compile code with wrong semantic behavior!

The reverse is possible however. If a function foo() is "pure" ie with no side effects then a good compiler will deal with eg y=foo(x)+foo(x); using only a single call to foo(). The Ada language provides a pragma to assert pureness for this purpose.