llvm dev - May 2010 - [LLVMdev] All CallInsts mayHaveSideEffects

Hi,

All CallInsts should return true for Instruction::mayHaveSideEffects() because
functions are not guaranteed to halt.

Inliner::runOnSCC calls isInstructionTriviallyDead to determine whether code can
be dead code eliminated. isInstructionTriviallyDead returns true if
Instruction::mayHaveSideEffects() returns false. A function that potentially
runs forever based on its input but does not write to memory will be dead code
eliminated when the Inliner runs.

Here is a simple example of how things can go horribly wrong:

#include <stdio.h>
#include <stdlib.h>

void inf(void) {
  while(1);
}

int main(int argc, char **argv) {
  inf();
  return 0;
}

void foo(void) {
  printf("Hello world!\n");
  exit(0);
}

For recent versions of clang (svn rev 102637) when compiled with -O1 or higher
the result is:
Hello world!

The reason is that LLVM annotates inf as noreturn, so the ret instruction at the
end of main is replaced with unreachable. Then the inf function is dead-code
eliminated by the Inliner pass. Thus main will consist of a single unreachable
instruction, which allows control to fall through to the foo function.

My suggested patch is as follows:

Index: include/llvm/Instruction.h
==================================================================---
include/llvm/Instruction.h  (revision 102637)
+++ include/llvm/Instruction.h  (working copy)
@@ -245,7 +245,9 @@
   /// instructions which don't used the returned value.  For cases where
this
   /// matters, isSafeToSpeculativelyExecute may be more appropriate.
   bool mayHaveSideEffects() const {
-    return mayWriteToMemory() || mayThrow();
+    const unsigned opcode = getOpcode();
+    return mayWriteToMemory() || mayThrow() ||
+      opcode == Call || opcode == Invoke;
   }
 
   /// isSafeToSpeculativelyExecute - Return true if the instruction does not

Sincerely yours,
Tom

This is a known bug:
http://llvm.org/bugs/show_bug.cgi?id=965

There has been some discussion about it and similar problems, and the
desire is to perform some analysis on functions to determine if they
are known to halt trivially, ie they have no loops and call no other
functions that are not known to halt.

LLVM still wants to be able to delete calls to trivial read-only functions.

Reid

On Mon, May 10, 2010 at 8:28 PM, Thomas B. Jablin
<tjablin at cs.princeton.edu> wrote:
> Hi,
>
> All CallInsts should return true for Instruction::mayHaveSideEffects()
because functions are not guaranteed to halt.
>
> Inliner::runOnSCC calls isInstructionTriviallyDead to determine whether
code can be dead code eliminated. isInstructionTriviallyDead returns true if
Instruction::mayHaveSideEffects() returns false. A function that potentially
runs forever based on its input but does not write to memory will be dead code
eliminated when the Inliner runs.
>
> Here is a simple example of how things can go horribly wrong:
>
> #include <stdio.h>
> #include <stdlib.h>
>
> void inf(void) {
>  while(1);
> }
>
> int main(int argc, char **argv) {
>  inf();
>  return 0;
> }
>
> void foo(void) {
>  printf("Hello world!\n");
>  exit(0);
> }
>
> For recent versions of clang (svn rev 102637) when compiled with -O1 or
higher the result is:
> Hello world!
>
> The reason is that LLVM annotates inf as noreturn, so the ret instruction
at the end of main is replaced with unreachable. Then the inf function is
dead-code eliminated by the Inliner pass. Thus main will consist of a single
unreachable instruction, which allows control to fall through to the foo
function.
>
> My suggested patch is as follows:
>
> Index: include/llvm/Instruction.h
> ==================================================================> ---
include/llvm/Instruction.h  (revision 102637)
> +++ include/llvm/Instruction.h  (working copy)
> @@ -245,7 +245,9 @@
>   /// instructions which don't used the returned value.  For cases
where this
>   /// matters, isSafeToSpeculativelyExecute may be more appropriate.
>   bool mayHaveSideEffects() const {
> -    return mayWriteToMemory() || mayThrow();
> +    const unsigned opcode = getOpcode();
> +    return mayWriteToMemory() || mayThrow() ||
> +      opcode == Call || opcode == Invoke;
>   }
>
>   /// isSafeToSpeculativelyExecute - Return true if the instruction does
not
>
> Sincerely yours,
> Tom
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>