llvm dev - Feb 2013 - [LLVMdev] [llvm] r175553 - Fix a bug in mayHaveSideEffects. Functions that do not return are now considered as instructions with side effects.

Hi Nadav,
> I almost missed your email because you replied only to the list.  I
understand your argument. I think that my fix addresses a part of it. It says
that instructions that do not return should not be removed.
> The current implementation of mayReturn is to check the 'noreturn'
function attribute. Are you suggesting to add a new attribute that is called
'mustreturn' ? It is as equally difficult to know if a function will
halt.
a function would only be 'mustreturn' [*] if you can prove that it must
return
in finite time.  By default functions would not be 'mustreturn'.  Of
course it
is not always possible to prove that a function must return even when it does;
in these cases the function would not be marked 'mustreturn', because
you only
mark functions that you can prove must return.  This is analogous to
'noreturn'
where you only mark a function 'noreturn' if you can prove it
doesn't return;
in difficult cases where it doesn't return but you failed to prove it then
the
function is not marked 'noreturn'.

The big difference between the mustreturn and noreturn approaches to the
infinite loop problem is that when the noreturn approach gets it wrong then
you get miscompilations, while when the mustreturn approach gets it wrong you
get missed optimizations, not miscompilations.  Summary: the MR approach is
always conservatively correct, while the NR rule is not.

Consider the different cases, comparing what happens with the following two
rules for a function (a function which otherwise wouldn't be considered to
have
side effects eg because it is readonly and nounwind):

   NR rule: the function is considered to have side-effects iff it has the 
noreturn attribute;

   MR rule: the function is considered to have side-effects iff it does not have
the mustreturn attribute.

Case 1: a function infinite loops in an obvious way.  The function will be
marked NR, and will not be marked MR.  Thus both rules say this function has
side effects.

Case 2: a function which obviously does not infinite loop.  The function will
not be marked NR, and will be marked MR.  Thus both rules say that this
function does not have side effects.

Case 3: a function which always or sometimes infinite loops, but it is too hard
for the optimizers to work this out.  Then the function will not be marked NR
(because we failed to prove it is NR, even though it may be), and will not be
marked MR (because we must fail to prove it is MR, since it is not MR).  Then
the NR rule will say that the function *does not have side-effects*, which is
wrong, and may lead to misoptimization.  The MR rule says the function *does
have side-effects* which is correct.

Case 4: a function which never infinite loops, but it is too hard for the
optimizers to work this out.  Then the function will not be marked NR (because
we must fail to prove it is NR, since it is not NR), and will not be marked MR
(because it was too hard to prove).  Then the NR says that the function does not
have side-effects, which is correct.  The MR rule says that the function does
have side-effects, which is wrong, but only results in missed optimizations,
*not* miscompilations.

Notice how in every case in which the NR rule says the function has side-effects
then the MR rule also says it has side-effects.  Thus if we implement the MR
rule then the NR rule you added is not useful.  On the other hand, as these
examples show, the NR rule is inadequate because it doesn't always say you
have
side-effects when sometimes you have.  By contrast, the MR rule is always
conservatively correct.

Ciao, Duncan.

[*] The difference between 'mustreturn' and my original 'finite'
is the question
of what you say for functions containing a call to 'exit' or something
like
that.  Such a function doesn't return so 'mustreturn' would be
confusing, on the
other hand it completes in finite time, thus 'finite' is not
unreasonable.  To
some extent which version is better is a judgement call, but I think the best
approach may fall out naturally once someone tries to implement a pass that
computes these attributes, as probably one of them is simpler to reason about,
but for the moment I don't know which one it is.
>
> Thanks,
> Nadav
>
> On Feb 20, 2013, at 5:10 AM, Duncan Sands <baldrick at free.fr>
wrote:
>
>> Hi Nadav,
>>
>> On 19/02/13 21:02, Nadav Rotem wrote:
>>> Author: nadav
>>> Date: Tue Feb 19 14:02:09 2013
>>> New Revision: 175553
>>>
>>> URL: http://llvm.org/viewvc/llvm-project?rev=175553&view=rev
>>> Log:
>>>
>>> Fix a bug in mayHaveSideEffects. Functions that do not return are
now considered as instructions with side effects.
>>
>> what's special about functions where we were able to tell it
doesn't return,
>> as compared to functions that don't return but we weren't
clever enough to
>> realize it?  For example, in your testcase, what if the loop was tricky
enough
>> that we didn't realize it looped forever, even though it did?
>>
>> I'm saying that your patch doesn't solve the "I called an
infinite looping
>> function" problem, it just makes it less obvious.
>>
>> In short, I think this is the wrong way round.  I reckon a better
strategy
>> would be to introduce a new attribute "finite" (we can argue
about the name),
>> which means that we know or proved that the function completes in
finite time.
>> Then functions which are not "finite" would be considered to
have side-effects.
>>
>> This way, functions which obviously infinite loop and functions which
also
>> infinite loop but we can't tell will both be considered to have
side-effects.
>>
>> Ciao, Duncan.
>>
>>>
>>> rdar://13227456
>>>
>>>
>>> Added:
>>>      llvm/trunk/test/Transforms/FunctionAttrs/noreturn.ll
>>> Modified:
>>>      llvm/trunk/include/llvm/IR/Instruction.h
>>>      llvm/trunk/lib/IR/Instruction.cpp
>>>
>>> Modified: llvm/trunk/include/llvm/IR/Instruction.h
>>> URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/IR/Instruction.h?rev=175553&r1=175552&r2=175553&view=diff
>>>
=============================================================================>>>
--- llvm/trunk/include/llvm/IR/Instruction.h (original)
>>> +++ llvm/trunk/include/llvm/IR/Instruction.h Tue Feb 19 14:02:09
2013
>>> @@ -309,6 +309,12 @@ public:
>>>     ///
>>>     bool mayThrow() const;
>>>
>>> +  /// mayReturn - Return true if this is a function that may
return.
>>> +  /// this is true for all normal instructions. The only exception
>>> +  /// is functions that are marked with the 'noreturn'
attribute.
>>> +  ///
>>> +  bool mayReturn() const;
>>> +
>>>     /// mayHaveSideEffects - Return true if the instruction may
have side effects.
>>>     ///
>>>     /// Note that this does not consider malloc and alloca to have
side
>>> @@ -316,7 +322,7 @@ public:
>>>     /// instructions which don't used the returned value.  For
cases where this
>>>     /// matters, isSafeToSpeculativelyExecute may be more
appropriate.
>>>     bool mayHaveSideEffects() const {
>>> -    return mayWriteToMemory() || mayThrow();
>>> +    return mayWriteToMemory() || mayThrow() || !mayReturn();
>>>     }
>>>
>>>     /// clone() - Create a copy of 'this' instruction that
is identical in all
>>>
>>> Modified: llvm/trunk/lib/IR/Instruction.cpp
>>> URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/IR/Instruction.cpp?rev=175553&r1=175552&r2=175553&view=diff
>>>
=============================================================================>>>
--- llvm/trunk/lib/IR/Instruction.cpp (original)
>>> +++ llvm/trunk/lib/IR/Instruction.cpp Tue Feb 19 14:02:09 2013
>>> @@ -455,14 +455,18 @@ bool Instruction::mayWriteToMemory() con
>>>     }
>>>   }
>>>
>>> -/// mayThrow - Return true if this instruction may throw an
exception.
>>> -///
>>>   bool Instruction::mayThrow() const {
>>>     if (const CallInst *CI = dyn_cast<CallInst>(this))
>>>       return !CI->doesNotThrow();
>>>     return isa<ResumeInst>(this);
>>>   }
>>>
>>> +bool Instruction::mayReturn() const {
>>> +  if (const CallInst *CI = dyn_cast<CallInst>(this))
>>> +    return !CI->doesNotReturn();
>>> +  return true;
>>> +}
>>> +
>>>   /// isAssociative - Return true if the instruction is
associative:
>>>   ///
>>>   ///   Associative operators satisfy:  x op (y op z) === (x op y)
op z
>>>
>>> Added: llvm/trunk/test/Transforms/FunctionAttrs/noreturn.ll
>>> URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/test/Transforms/FunctionAttrs/noreturn.ll?rev=175553&view=auto
>>>
=============================================================================>>>
--- llvm/trunk/test/Transforms/FunctionAttrs/noreturn.ll (added)
>>> +++ llvm/trunk/test/Transforms/FunctionAttrs/noreturn.ll Tue Feb 19
14:02:09 2013
>>> @@ -0,0 +1,18 @@
>>> +; RUN: opt < %s -functionattrs -instcombine -S | FileCheck %s
>>> +
>>> +define void @endless_loop() noreturn nounwind readnone ssp uwtable
{
>>> +entry:
>>> +  br label %while.body
>>> +
>>> +while.body:
>>> +  br label %while.body
>>> +}
>>> +;CHECK: @main
>>> +;CHECK: endless_loop
>>> +;CHECK: ret
>>> +define i32 @main() noreturn nounwind ssp uwtable {
>>> +entry:
>>> +  tail call void @endless_loop()
>>> +  unreachable
>>> +}
>>> +
>>>
>>>
>>> _______________________________________________
>>> llvm-commits mailing list
>>> llvm-commits at cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
>>>
>>
>> _______________________________________________
>> llvm-commits mailing list
>> llvm-commits at cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
>