All CallInsts mayHaveSideEffects

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

All CallInsts mayHaveSideEffects

Thomas B. Jablin
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
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: All CallInsts mayHaveSideEffects

Reid Kleckner
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
<[hidden email]> 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
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: All CallInsts mayHaveSideEffects

Thomas B. Jablin
In reply to this post by Thomas B. Jablin
Does any real code benefit from dead code eliminating read-only functions?
Tom

----- Original Message -----
From: "Reid Kleckner" <[hidden email]>
To: "Thomas B. Jablin" <[hidden email]>
Cc: "LLVM Developers Mailing List" <[hidden email]>
Sent: Monday, May 10, 2010 9:38:47 PM GMT -05:00 US/Canada Eastern
Subject: Re: [LLVMdev] All CallInsts mayHaveSideEffects

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
<[hidden email]> 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
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: All CallInsts mayHaveSideEffects

Samuel Crow
I'd imagine every get method in any C++ program would benefit from that sort of dead-code elimination.  Although simply inlining it might might be all that's really needed.



----- Original Message ----
> From: Thomas B. Jablin <[hidden email]>
> To: LLVM Developers Mailing List <[hidden email]>
> Sent: Mon, May 10, 2010 9:01:09 PM
> Subject: Re: [LLVMdev] All CallInsts mayHaveSideEffects
>
> Does any real code benefit from dead code eliminating read-only
> functions?
Tom

----- Original Message -----
From: "Reid Kleckner"
> <
> href="mailto:[hidden email]">[hidden email]>
To: "Thomas B. Jablin" <
> ymailto="mailto:[hidden email]"
> href="mailto:[hidden email]">[hidden email]>
Cc:
> "LLVM Developers Mailing List" <
> href="mailto:[hidden email]">[hidden email]>
Sent: Monday,
> May 10, 2010 9:38:47 PM GMT -05:00 US/Canada Eastern
Subject: Re: [LLVMdev]
> All CallInsts mayHaveSideEffects

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
<

> href="mailto:[hidden email]">[hidden email]>
> 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
>
> href="mailto:[hidden email]">[hidden email]        
> http://llvm.cs.uiuc.edu
>
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

_______________________________________________
LLVM
> Developers mailing list

> href="mailto:[hidden email]">[hidden email]      
>  
> >http://llvm.cs.uiuc.edu

> href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target=_blank
> >http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


     
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev