[IPSCCP] Remove calls without side effects

[beanz]

Summary

When performing constant propagation for call instructions we have historically replaced all uses of the return from a call, but not removed the call itself. This is required for correctness if the calls have side effects, however the compiler should be able to safely remove calls that don't have side effects.

This allows the compiler to completely fold away calls to functions that have no side effects if the inputs are constant and the output can be determined at compile time.

[sanjoy]

lib/Transforms/Scalar/SCCP.cpp

1905

Can we just make this !Inst->mayHaveSideEffects() && !isa<TerminatorInst>(Inst)? Otherwise we're assuming that non-calls that aren't terminators are not side effecting, which may be correct specifically for the instructions that tryToReplaceWithConstant returns true for, but isn't true in general.

[beanz]

lib/Transforms/Scalar/SCCP.cpp

1905

The problem with that is that we do have instructions with side effects that we want to fold away. For example we have test/Transforms/SCCP/atomic-load-store.ll which tests that we do erase atomic loads and stores.

[davide]

lib/Transforms/Scalar/SCCP.cpp

1905

This seems to be on the right track.
What I think is that this check is leaking too much information. I'd move it to a separate function, something called isSafeToReplace().
I wonder if this should actually live in SCCP or in Instruction (or somewhere else), as the rules for folding away should be fairly general.

[majnemer]

lib/Transforms/Scalar/SCCP.cpp

1905

Could we just call isInstructionTriviallyDead? It already knows about terminators and all the other stuff. There is also wouldInstructionBeTriviallyDead if you want to query before the replacement.

[• dberlin]

lib/Transforms/Scalar/SCCP.cpp

1905

That would not return true for anything with side effects. So it will not handle the atomic loads and stores cases. mayHaveSideEffects will return true for anything that might write to memory. mayWriteToMemory will return true for any store, and any ordered load.

In fact, even getModRefInfo wouldn't help you with that here, it would do the same, and can't be overridden by anything more powerful right now (we only have an AA interface for callsites, the regular instructions are all single implementation in AliasAnalysis.cpp)

So TL; DR if you wanted to use isInstructionTriviallyDead, it would be something like isInstructionTriviallyDead || is a load || is a store || atomicrmw || cmpxchng || ....

[beanz]

Abstracting check for whether or not it is safe to remove an instruction as per the feedback from davide.

None of the other feedback seems to have consensus. Anything else I should change here or can this land?

Thanks!

[davide]

I don't think this function is general enough to live in Instruction.h, I'd keep it private to SCCP for now.
I think we need to reach consensus on how this will look like in the end, but this is probably fine for now.
I'd give @majnemer / @dberlin another change of commenting, but I guess this is fine to get in.

include/llvm/IR/Instruction.h

public:
   /// Return true if the instruction may have side effects.
   ///
   /// Note that this does not consider malloc and alloca to have side
   /// effects because the newly allocated memory is completely invisible to
   /// instructions which don't use the returned value.  For cases where this
   /// matters, isSafeToSpeculativelyExecute may be more appropriate.
   bool mayHaveSideEffects() const { return mayWriteToMemory() || mayThrow(); }
 
+  /// Return true if the instruction can be removed if the result is unused.
+  ///
+  /// When constant folding some instructions cannot be removed even if their
+  /// results are unused. Specifically terminator instructions and calls that
+  /// may have side effects cannot be removed without semantically changing the
+  /// generated program.
+  bool isSafeToRemove() const;
+  
   /// Return true if the instruction is a variety of EH-block.
   bool isEHPad() const {
     switch (getOpcode()) {
     case Instruction::CatchSwitch:
     case Instruction::CatchPad:
     case Instruction::CleanupPad:
     case Instruction::LandingPad:
       return true;

lib/IR/Instruction.cpp

if (const CallInst *CI = dyn_cast<CallInst>(this))
     return !CI->doesNotThrow();
   if (const auto *CRI = dyn_cast<CleanupReturnInst>(this))
     return CRI->unwindsToCaller();
   if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(this))
     return CatchSwitch->unwindsToCaller();
   return isa<ResumeInst>(this);
 }
 
+bool Instruction::isSafeToRemove() const {
+  return (!isa<CallInst>(this) || !this->mayHaveSideEffects()) &&
+         !isa<TerminatorInst>(this);
+}
+
 bool Instruction::isAssociative() const {
   unsigned Opcode = getOpcode();
   if (isAssociative(Opcode))
     return true;
 
   switch (Opcode) {
   case FMul:
   case FAdd:

lib/Transforms/Scalar/SCCP.cpp

for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
         continue;
       }
 
       for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
         Instruction *Inst = &*BI++;
         if (Inst->getType()->isVoidTy())
           continue;
         if (tryToReplaceWithConstant(Solver, Inst)) {
-          if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst))
+          if (Inst->isSafeToRemove())
             Inst->eraseFromParent();
           // Hey, we just changed something!
           MadeChanges = true;
           ++IPNumInstRemoved;
         }
       }
     }
 

test/Transforms/IPConstantProp/remove-call-inst.ll

 ; RUN: opt < %s -S -ipsccp | FileCheck %s
 ; PR5596
 
 ; IPSCCP should propagate the 0 argument, eliminate the switch, and propagate
 ; the result.
 
 ; CHECK: define i32 @main() #0 {
 ; CHECK-NEXT: entry:
-; CHECK-NEXT: %call2 = tail call i32 @wwrite(i64 0) [[NUW:#[0-9]+]]
+; CHECK-NOT: call
 ; CHECK-NEXT: ret i32 123
 
 define i32 @main() noreturn nounwind {
 entry:
   %call2 = tail call i32 @wwrite(i64 0) nounwind
   ret i32 %call2
 }
 
 define internal i32 @wwrite(i64 %i) nounwind readnone {
 entry:
   switch i64 %i, label %sw.default [
     i64 3, label %return
     i64 10, label %return
   ]
 
 sw.default:
   ret i32 123
 
 return:
   ret i32 0
 }
 
 ; CHECK: attributes #0 = { noreturn nounwind }
 ; CHECK: attributes #1 = { nounwind readnone }
-; CHECK: attributes [[NUW]] = { nounwind }

test/Transforms/IPConstantProp/user-with-multiple-uses.ll

 ; CHECK-NEXT: ret i32 123
 
 define i32 @main() noreturn nounwind {
 entry:
   %call2 = tail call i32 @wwrite(i64 0) nounwind
   ret i32 %call2
 }
 
-define internal i32 @wwrite(i64 %i) nounwind readnone {
+define internal i32 @wwrite(i64 %i) nounwind {
 entry:
   switch i64 %i, label %sw.default [
     i64 3, label %return
     i64 10, label %return
   ]
 
 sw.default:
   ret i32 123
 
 return:
   ret i32 0
 }
 
 ; CHECK: attributes #0 = { noreturn nounwind }
-; CHECK: attributes #1 = { nounwind readnone }
-; CHECK: attributes [[NUW]] = { nounwind }
+; CHECK: attributes #1 = { nounwind }