What every compiler writer should know about programmers [pdf]

Re:What every compiler writer should know about programmers ... by Someone on Thursday March 03, 2016 @07:52PM (#11221242)

This:

    k<16; dd=d[++k]

, whenever the code reached the end of the loop, effectively becomes

    dd=d[++k]
    if(k<16) goto startOfLoop;

That, in turn is equivalent to:

    k+=1
    dd=d[k]
    if(k<16) goto startOfLoop

In the second line, k is used to index into array d. Conforming programs do not access memory outside of arrays, so the compiler can infer that

  0 <= k < 16

Given that, it is clear that the goto startOfLoop branch will always be taken. Inside the loop, the program accesses some memory, but that data never is visible to the outside world, so the compiler can optimize away the memory reads and writes.

The compiler is that aggressive because it has to be in real world programs. For example, compilers using C as their target instruction set may generate bounds checks for every array access, trusting the C compiler to remove as many as possible of them. Macros are another common cause of superfluous source statements that programmers will expect the compiler to optimize away.

I think it will be very tricky to detect cases where compilers should be wary of applying 'obvious' optimizations.

[ Parent | on HN ]

Re:What every compiler writer should know about programmers ... by AntonErtl on Saturday March 05, 2016 @01:05PM (#11230227)

I would be pretty miffed if I wrote a, say, Pascal compilers with array bounds checks, and the compiler "optimized" the checks away just because accessing a[i] would be undefined behaviour. OTOH, in a loop like

for (i=0; i<16; i++) { if (i>=0 && i<16) do something with a[i] else report an error;

you can certainly optimize the if to if(1). That's an optimization*.

[ Parent | on HN ]

Re:What every compiler writer should know about programmers ... by Someone on Saturday March 05, 2016 @09:10PM (#11232156)

No, it would not. Compilers can remove boundary checks that provably happen after accessing an item of an array, not those before the array is accessed.

For your example, the Pascal code (at least, I hope this is Pascal; it has been a while since I wrote any):

  if (i>=0 and i<16) then
  begin
    x := a[i]
  end
  else
  begin
    ReportError;
  end

is equivalent to the C code:

  if (i>=0 && i<16)
  {
    if(i>=0 && i<16)
    {
       x = a[i]
    } else {
      RuntimeAbort(“Array access outside bounds");
    }
  } else {
    ReportError();
  }

A good Pascal compiler, like a good C compiler, would optimise away that second boundary check and the call to RuntimeAbort. Neither compiler is allowed to optimise away the first check.

[ Parent | on HN ]

Re:What every compiler writer should know about programmers ... by AntonErtl on Sunday March 06, 2016 @05:35AM (#11233209)

The point of my posting was that you don't need "optimizations" to optimize away redundant bounds checks, optimization* is able to do it just fine. Sorry if I did not get that across clearly. What does your "No, it would not" refer to?

[ Parent | on HN ]