What does an addition operation look like in intermediate code/three address code?

Question

If I write a function as follows

int sum(int i)
{ 
if(!i)
    return 0;
return sum(i--) + i;  //this line
}

How does the compiler represent the return statement in terms of three address code/intermediate code? Does

1) return i-- + sum(i) differ from 2) return sum(i) + i--?

My interpretation is that in the first case if i is added and then sum is recursively called with i-1 as parameter and in the other case sum is called with i as parameter and i-1 is added to it. Is that right? Can someone explain what happens at the compiler level?

Also what if modify 1) and 2) as

1)return i + sum(i--) and 2) return sum(i--) + i

what happens in the recursive sense? It will be an infinite loop I think but what about the i-- ?

@self.; `i` is modifying and its value is used in the same expression. The order of evaluation is not guaranteed whether `sum(i--)` is going to be evaluated first or `i` is evaluated first. — haccks, Jun 09 '14 at 15:41
@haccks: Not only is the evaluation order unspecified, but the attempted evaluation generates Undefined Behavior (anything can happen). It would be legal on a multiprocessor system for an expression like `i--` to lock `i`, read it, compute (i-1), store the new value, and release the lock (such behavior could be useful if hardware was set up to handle it cheaply). Since there would be no guarantee that the other read of `i` wouldn't get sequenced between the lock acquisition and release, it would be possible (though unlikely) that an expression like the above could generate a deadlock. — supercat, Jun 09 '14 at 16:51
@haccks: Your third comment made it sound as though the only "really undefined" aspect was the order of evaluation. My point was that the program need not behave as though one was evaluated before the other. Once the computer has received all input necessary to determine that execution can legally reach the aforementioned statement, the program is absolved of any requirement to behave as written. — supercat, Jun 09 '14 at 17:18
I don't understand why this has been marked duplicate? My question involves recursive behavior and intermediate code while the question referred here is something different. I'm not asking how i++ and i-- work — Dubby, Jun 09 '14 at 17:24
@supercat; In most cases I encountered the cause for UB is the order of evaluation (may be I am missing something or not on top of my head). If you have another example then let me know. — haccks, Jun 09 '14 at 17:24
@haccks: For simple cases where variables are read at illegal times, I've not seen implementations actually do anything particularly wacky, though I have seen cases where 8-bit compilers would evaluate an expression like `a=b+c+d;` by adding all the lower bytes and then all the upper bytes. I don't think I've seen such optimizations when the operands to the addition were anything other than simple variables, but it's not hard to imagine that something like `a=b+c+d(b++);`, with b initially 0x1FF, might end up performing the addition as though `b` were 0x2FF. — supercat, Jun 09 '14 at 17:33
@haccks: In any case, the fact that no present implementations do anything wacky doesn't mean that in the future an implementation won't be able to gain some performance edge or other benefit by generating code for e.g. `*ptr = a++;` which would work beautifully when `ptr` does not alias `a`, but would do something completely unexpected if `ptr` did alias `a`. Note, btw, that if execution of the above statement were preceded or followed by `if (ptr == &a)` a compiler would be allowed to assume the condition could never be true [since if ptr did alias a, ... — supercat, Jun 09 '14 at 17:36
...the compiler could do anything it wanted, including skipping code in the conditional]. If a conditional test caused the `*ptr = a++;` to be skipped, of course, there would be no unconditional behavior, but if the expression will be evaluated even if `ptr` aliased `a`, the compiler may do whatever it likes. — supercat, Jun 09 '14 at 17:40
@supercat I was going through a link which says the in C f() + g() is undefined behavior with no guarantee whether f or g executes first. Does this argument hold true when we write the recursive function Fib(n-1) + Fib(n-2) ? — Dubby, Jun 09 '14 at 17:47
@Dubby: The expression `a(b(),c())+d(e(),f())` may evaluate all of the methods in any order, subject to the constraints that once the first statement of a called method starts execution, nothing else in the expression may execute until the function returns. Further, both `b` and `c` must complete before the first statement of `a` executes, and likewise `e` and `f` before `d`, whether or not the called functions make use of the passed-in values. Subject to those constraints, the compiler may vary execution order however it sees fit--*even between repeated executions of the same statement*. — supercat, Jun 09 '14 at 18:04
@Dubby It was marked a duplicate because you code triggers undefinded behaviour. If you are not asking about order of mutation behaviour fix your code by replacing `i--` with the more appropriate `i-1` and fix the questions accordingly. — Sylwester, Jun 09 '14 at 21:02
@supercat could you mention the sequence points in this statement `(c = getchar()) != EOF` ? — Dubby, Jun 10 '14 at 06:39
@Dubby: EOF is generally a macro which resolves to a literal, but `getchar()` is generally a macro which resolves to an expression like `fgetc(stdin)` but there's no guarantee of that. I know of nothing that would guarantee that `getchar()` could not evaluate to to something like `((getchar_ready || do_getchar()), *getchar_input_buffer++)`, in which case it may not have the expected sequence points. — supercat, Jun 11 '14 at 13:48

What does an addition operation look like in intermediate code/three address code?

0 Answers0