Do not remove calls to functions that may not halt

[olista01]

Summary

This prevents LLVM from removing calls to functions if that function may not terminate. This was previously done by several passes (including ADCE and the inliner) in cases where the callee is otherwise side-effect free.

The actual fix is in Instruction.{h,cpp}, the rest of the changes are fixing up passes that were relying on the old behaviour, in cases such as intrinsics and known library functions where it is still safe to do this.

A few of the tests had to be modified as they were checking that calls were removed when this this is not safe to do so. The only test I am concerned about is LTO/X86/parallel.ll, which appears to be the only test for parallel LTO. I've relaxed it so that it passes, but I'm not sure if it is really testing the functionality any more.

[vsk]

Thanks, some minor comments inline --

include/llvm/Analysis/TargetLibraryInfo.h

249

It looks like many of these entries are shared with the switch in hasOptimizedCodeGen(). Could you consider sharing some of this code?

include/llvm/IR/Instruction.h

394

If you're open to an alternate name for this, how about "mayHaveSideEffectsOrNotTerminate"? Then "mayHaveSideEffectsIgnoringTermination" could be changed to "mayHaveSideEffects". IMO "IgnoringX" is a little hard to read. Up to you of course :).

include/llvm/Transforms/Utils/Local.h

66

"might have" -> "cannot have"?

lib/Transforms/Utils/Local.cpp

360

nit - extra line here

[olista01]

include/llvm/Analysis/TargetLibraryInfo.h

249

I'm not sure about this, the overlap between the two sets of functions doesn't have any meaning beyond "is side effect free and has optimised codegen", so I don't see what we gain by factoring it out.

include/llvm/IR/Instruction.h

394

I'm also not keen on the "IgnoringTermination" name, but I think non-termination should count as a side effect (unless ignoring it is safe for the given transformation, for example the change in SimplfyCFG.cpp), so I'd rather leave "mayHaveSideEffects" as the one that does take termination into account.

[t.p.northover]

Isn't it explicitly allowed in C and C++ if the function has no other effects?

I thought the consensus was that since:

• the only observable behaviour the compiler must preserve are (roughly) libcalls and volatile accesses,
• it may assume progress on these fronts is made by a well-defined program

any such non-terminating but otherwise side-effect free call was UB.

[• dberlin]

Right. This patch seems contrary to the consensus of the discussion
had about this on llvm-dev.

[olista01]

Ah, sorry, I hadn't found that llvm-dev thread, I'll drop this patch.

Out of interest, do you have a section reference for C99 or C++03 for non-termination without side-effects being UB? C++11 has 1.10/24, and C11 has 6.8.5/6, both of which makes this explicit, but the closest I can find in the older standards is this:

The least requirements on a conforming implementation are:

• At sequence points, volatile objects are stable in the sense that previous evaluations are complete and subsequent evaluations have not yet occurred.
• At program termination, all data written into files shall be identical to one of the possible results that execution of the program according to the abstract semantics would have produced.
• The input and output dynamics of interactive devices shall take place in such a fashion that prompting messages actually appear prior to a program waiting for input. What constitutes an interactive device is implementation-defined.

include/llvm/Analysis/DemandedBits.h

 
 namespace llvm {
 
 class FunctionPass;
 class Function;
 class Instruction;
 class DominatorTree;
 class AssumptionCache;
+class TargetLibraryInfo;
 
 struct DemandedBits : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   DemandedBits();
 
   bool runOnFunction(Function& F) override;
   void getAnalysisUsage(AnalysisUsage& AU) const override;
 
   /// Return the bits demanded from instruction I.
   APInt getDemandedBits(Instruction *I);
 
   /// Return true if, during analysis, I could not be reached.
   bool isInstructionDead(Instruction *I);
 
 private:
   void determineLiveOperandBits(const Instruction *UserI,
                                 const Instruction *I, unsigned OperandNo,
                                 const APInt &AOut, APInt &AB,
                                 APInt &KnownZero, APInt &KnownOne,
                                 APInt &KnownZero2, APInt &KnownOne2);
 
   AssumptionCache *AC;
   DominatorTree *DT;
+  TargetLibraryInfo *TLI;
 
   // The set of visited instructions (non-integer-typed only).
   SmallPtrSet<Instruction*, 128> Visited;
   DenseMap<Instruction *, APInt> AliveBits;
 };
 
 /// Create a demanded bits analysis pass.
 FunctionPass *createDemandedBitsPass();
 
 } // End llvm namespace
 
 #endif

include/llvm/Analysis/TargetLibraryInfo.h

bool hasOptimizedCodeGen(LibFunc::Func F) const {
     case LibFunc::memcmp:    case LibFunc::strcmp:     case LibFunc::strcpy:
     case LibFunc::stpcpy:    case LibFunc::strlen:     case LibFunc::strnlen:
     case LibFunc::memchr:
       return true;
     }
     return false;
   }
 
+  /// \brief Tests if the function is both available and known to be side-effect
+  /// free.
+  bool isSideEffectFree(LibFunc::Func F) const {
+    if (Impl->getState(F) == TargetLibraryInfoImpl::Unavailable)
+      return false;
+    switch (F) {
+    default: break;
+    case LibFunc::copysign:  case LibFunc::copysignf:  case LibFunc::copysignl:
+    case LibFunc::fabs:      case LibFunc::fabsf:      case LibFunc::fabsl:
+    case LibFunc::sin:       case LibFunc::sinf:       case LibFunc::sinl:
+    case LibFunc::cos:       case LibFunc::cosf:       case LibFunc::cosl:
+    case LibFunc::sqrt:      case LibFunc::sqrtf:      case LibFunc::sqrtl:
+    case LibFunc::sqrt_finite: case LibFunc::sqrtf_finite:
+                                                  case LibFunc::sqrtl_finite:
+    case LibFunc::fmax:      case LibFunc::fmaxf:      case LibFunc::fmaxl:
+    case LibFunc::fmin:      case LibFunc::fminf:      case LibFunc::fminl:
+    case LibFunc::floor:     case LibFunc::floorf:     case LibFunc::floorl:
+    case LibFunc::nearbyint: case LibFunc::nearbyintf: case LibFunc::nearbyintl:
+    case LibFunc::ceil:      case LibFunc::ceilf:      case LibFunc::ceill:
+    case LibFunc::rint:      case LibFunc::rintf:      case LibFunc::rintl:
+    case LibFunc::round:     case LibFunc::roundf:     case LibFunc::roundl:
+    case LibFunc::trunc:     case LibFunc::truncf:     case LibFunc::truncl:
+    case LibFunc::log2:      case LibFunc::log2f:      case LibFunc::log2l:
+    case LibFunc::exp2:      case LibFunc::exp2f:      case LibFunc::exp2l:
+    case LibFunc::memcmp:    case LibFunc::strcmp:     case LibFunc::strlen:
+    case LibFunc::strnlen:   case LibFunc::memchr:
+      return true;
+    }
+    return false;
+  }
+
   StringRef getName(LibFunc::Func F) const {
     auto State = Impl->getState(F);
     if (State == TargetLibraryInfoImpl::Unavailable)
       return StringRef();
     if (State == TargetLibraryInfoImpl::StandardName)
       return Impl->StandardNames[F];
     assert(State == TargetLibraryInfoImpl::CustomName);
     return Impl->CustomNames.find(F)->second;

include/llvm/IR/Instruction.h

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;
 
+  /// mayNotReturn - Return true if this is a function that may run forever
+  /// without returning.
+  ///
+  bool mayNotReturn() const;
+
   /// mayHaveSideEffects - 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() || !mayReturn();
+    return mayWriteToMemory() || mayThrow() || mayNotReturn();
+  }
+
+  /// mayHaveSideEffectsIgnoringTermination - Return true if the instruction may
+  /// have side effects, not considering non-termination to be a side-effect.
+  ///
+  bool mayHaveSideEffectsIgnoringTermination() const {
+    return mayWriteToMemory() || mayThrow();
   }
 
   /// \brief Return true if the instruction is a variety of EH-block.
   bool isEHPad() const {
     switch (getOpcode()) {
     case Instruction::CatchPad:
     case Instruction::CatchEndPad:
     case Instruction::CleanupPad:

include/llvm/Transforms/Utils/Local.h

 /// DeleteDeadConditions is true.
 bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
                             const TargetLibraryInfo *TLI = nullptr);
 
 //===----------------------------------------------------------------------===//
 //  Local dead code elimination.
 //
 
+/// isInstructionSideEffectFree - Return true if the instruction cannot have side
+/// effects.
+bool isInstructionSideEffectFree(Instruction *I,
+                                 const TargetLibraryInfo *TLI = nullptr);
+
 /// isInstructionTriviallyDead - Return true if the result produced by the
 /// instruction is not used, and the instruction has no side effects.
 ///
 bool isInstructionTriviallyDead(Instruction *I,
                                 const TargetLibraryInfo *TLI = nullptr);
 
 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 /// trivially dead instruction, delete it.  If that makes any of its operands

lib/Analysis/DemandedBits.cpp

 
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "demanded-bits"
 
 char DemandedBits::ID = 0;
 INITIALIZE_PASS_BEGIN(DemandedBits, "demanded-bits", "Demanded bits analysis",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(DemandedBits, "demanded-bits", "Demanded bits analysis",
                     false, false)
 
 DemandedBits::DemandedBits() : FunctionPass(ID) {
   initializeDemandedBitsPass(*PassRegistry::getPassRegistry());
 }
 
 void DemandedBits::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.setPreservesAll();
 }
 
-static bool isAlwaysLive(Instruction *I) {
+static bool isAlwaysLive(Instruction *I, const TargetLibraryInfo *TLI) {
   return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
-      I->isEHPad() || I->mayHaveSideEffects();
+      I->isEHPad() || !isInstructionSideEffectFree(I, TLI);
 }
 
 void DemandedBits::determineLiveOperandBits(
     const Instruction *UserI, const Instruction *I, unsigned OperandNo,
     const APInt &AOut, APInt &AB, APInt &KnownZero, APInt &KnownOne,
     APInt &KnownZero2, APInt &KnownOne2) {
   unsigned BitWidth = AB.getBitWidth();
 
if (OperandNo != 0)
       AB = AOut;
     break;
   }
 }
 
 bool DemandedBits::runOnFunction(Function& F) {
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   Visited.clear();
   AliveBits.clear();
 
   SmallVector<Instruction*, 128> Worklist;
 
   // Collect the set of "root" instructions that are known live.
   for (Instruction &I : instructions(F)) {
-    if (!isAlwaysLive(&I))
+    if (!isAlwaysLive(&I, TLI))
       continue;
 
     DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
     // For integer-valued instructions, set up an initial empty set of alive
     // bits and add the instruction to the work list. For other instructions
     // add their operands to the work list (for integer values operands, mark
     // all bits as live).
     if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
while (!Worklist.empty()) {
     // existing set, if any, and if that changes the set of alive bits, the
     // operand is added to the work-list.
     for (Use &OI : UserI->operands()) {
       if (Instruction *I = dyn_cast<Instruction>(OI)) {
         if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
           unsigned BitWidth = IT->getBitWidth();
           APInt AB = APInt::getAllOnesValue(BitWidth);
           if (UserI->getType()->isIntegerTy() && !AOut &&
-              !isAlwaysLive(UserI)) {
+              !isAlwaysLive(UserI, TLI)) {
             AB = APInt(BitWidth, 0);
           } else {
             // If all bits of the output are dead, then all bits of the input
             // Bits of each operand that are used to compute alive bits of the
             // output are alive, all others are dead.
             determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB,
                                      KnownZero, KnownOne,
                                      KnownZero2, KnownOne2);
APInt DemandedBits::getDemandedBits(Instruction *I) {
   const DataLayout &DL = I->getParent()->getModule()->getDataLayout();
   if (AliveBits.count(I))
     return AliveBits[I];
   return APInt::getAllOnesValue(DL.getTypeSizeInBits(I->getType()));
 }
 
 bool DemandedBits::isInstructionDead(Instruction *I) {
   return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
-    !isAlwaysLive(I);
+    !isAlwaysLive(I, TLI);
 }
 
 FunctionPass *llvm::createDemandedBitsPass() {
   return new DemandedBits();
 }

lib/IR/Instruction.cpp

 }
 
 bool Instruction::mayReturn() const {
   if (const CallInst *CI = dyn_cast<CallInst>(this))
     return !CI->doesNotReturn();
   return true;
 }
 
+bool Instruction::mayNotReturn() const {
+  // We can only be certain about this for intrinsics, because we don't have a
+  // function attribute which represents "guaranteed to return" (all intrinsics
+  // are guaranteed to return, except for those which have doesNotReturn set).
+  if (const CallInst *CI = dyn_cast<CallInst>(this)) {
+    if (const Function *F = CI->getCalledFunction())
+      return !F->isIntrinsic() || CI->doesNotReturn();
+    return true;
+  }
+
+  if (isa<InvokeInst>(this))
+    return true;
+
+  return false;
+}
+
 /// isAssociative - Return true if the instruction is associative:
 ///
 ///   Associative operators satisfy:  x op (y op z) === (x op y) op z
 ///
 /// In LLVM, the Add, Mul, And, Or, and Xor operators are associative.
 ///
 bool Instruction::isAssociative(unsigned Opcode) {
   return Opcode == And || Opcode == Or || Opcode == Xor ||

lib/Transforms/Scalar/ADCE.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Pass.h"
+#include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "adce"
 
 STATISTIC(NumRemoved, "Number of instructions removed");
 
 namespace {
 struct ADCE : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   ADCE() : FunctionPass(ID) {
     initializeADCEPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function& F) override;
 
   void getAnalysisUsage(AnalysisUsage& AU) const override {
     AU.setPreservesCFG();
     AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
   }
 };
 }
 
 char ADCE::ID = 0;
 INITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false)
 
 bool ADCE::runOnFunction(Function& F) {
   if (skipOptnoneFunction(F))
     return false;
 
+  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+
   SmallPtrSet<Instruction*, 128> Alive;
   SmallVector<Instruction*, 128> Worklist;
 
   // Collect the set of "root" instructions that are known live.
   for (Instruction &I : instructions(F)) {
     if (isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) || I.isEHPad() ||
-        I.mayHaveSideEffects()) {
+        !isInstructionSideEffectFree(&I, &TLI)) {
       Alive.insert(&I);
       Worklist.push_back(&I);
     }
   }
 
   // Propagate liveness backwards to operands.
   while (!Worklist.empty()) {
     Instruction *Curr = Worklist.pop_back_val();

lib/Transforms/Scalar/TailRecursionElimination.cpp

 bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) {
   // FIXME: We can move load/store/call/free instructions above the call if the
   // call does not mod/ref the memory location being processed.
   if (I->mayHaveSideEffects())  // This also handles volatile loads.
     return false;
 
   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
     // Loads may always be moved above calls without side effects.
-    if (CI->mayHaveSideEffects()) {
+    if (CI->mayHaveSideEffectsIgnoringTermination()) {
       // Non-volatile loads may be moved above a call with side effects if it
       // does not write to memory and the load provably won't trap.
       // FIXME: Writes to memory only matter if they may alias the pointer
       // being loaded from.
       if (CI->mayWriteToMemory() ||
           !isSafeToLoadUnconditionally(L->getPointerOperand(), L,
                                        L->getAlignment()))
         return false;

lib/Transforms/Utils/Local.cpp

 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LibCallSemantics.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
   return false;
 }
 
 
 //===----------------------------------------------------------------------===//
 //  Local dead code elimination.
 //
 
-/// isInstructionTriviallyDead - Return true if the result produced by the
-/// instruction is not used, and the instruction has no side effects.
+/// isInstructionSideEffectFree - Return true if the instruction might have side
+/// effects.
 ///
-bool llvm::isInstructionTriviallyDead(Instruction *I,
+bool llvm::isInstructionSideEffectFree(Instruction *I,
                                          const TargetLibraryInfo *TLI) {
-  if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
-
-  // We don't want the landingpad-like instructions removed by anything this
-  // general.
-  if (I->isEHPad())
-    return false;
-
-  // We don't want debug info removed by anything this general, unless
-  // debug info is empty.
-  if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
-    if (DDI->getAddress())
-      return false;
-    return true;
-  }
-  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
-    if (DVI->getValue())
-      return false;
-    return true;
-  }
-
   if (!I->mayHaveSideEffects()) return true;
 
   // Special case intrinsics that "may have side effects" but can be deleted
   // when dead.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     // Safe to delete llvm.stacksave if dead.
     if (II->getIntrinsicID() == Intrinsic::stacksave)
       return true;
bool llvm::isInstructionSideEffectFree(Instruction *I,
   }
 
   if (isAllocLikeFn(I, TLI)) return true;
 
   if (CallInst *CI = isFreeCall(I, TLI))
     if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
       return C->isNullValue() || isa<UndefValue>(C);
 
+  // Some library calls are known to be side-effect free.
+  if (CallInst *CI = dyn_cast<CallInst>(I)) {
+    Function *Callee = CI->getCalledFunction();
+    if (Callee) {
+      StringRef FnName = Callee->getName();
+      LibFunc::Func TLIFn;
+      if (TLI && TLI->getLibFunc(FnName, TLIFn) && TLI->has(TLIFn) &&
+          TLI->isSideEffectFree(TLIFn)) {
+        return true;
+      }
+    }
+  }
+
   return false;
 }
 
+/// isInstructionTriviallyDead - Return true if the result produced by the
+/// instruction is not used, and the instruction has no side effects.
+///
+bool llvm::isInstructionTriviallyDead(Instruction *I,
+                                      const TargetLibraryInfo *TLI) {
+  if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
+
+  // We don't want the landingpad-like instructions removed by anything this
+  // general.
+  if (I->isEHPad())
+    return false;
+
+  // We don't want debug info removed by anything this general, unless
+  // debug info is empty.
+  if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
+    if (DDI->getAddress())
+      return false;
+    return true;
+  }
+  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
+    if (DVI->getValue())
+      return false;
+    return true;
+  }
+
+  return isInstructionSideEffectFree(I, TLI);
+}
+
 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 /// trivially dead instruction, delete it.  If that makes any of its operands
 /// trivially dead, delete them too, recursively.  Return true if any
 /// instructions were deleted.
 bool
 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
                                                  const TargetLibraryInfo *TLI) {
   Instruction *I = dyn_cast<Instruction>(V);

lib/Transforms/Utils/SimplifyCFG.cpp

while (RI1 != RE1 && RI2 != RE2) {
     auto InstPair = std::make_pair(I1, I2);
     // I1 and I2 should have a single use in the same PHI node, and they
     // perform the same operation.
     // Cannot move control-flow-involving, volatile loads, vaarg, etc.
     if (isa<PHINode>(I1) || isa<PHINode>(I2) ||
         isa<TerminatorInst>(I1) || isa<TerminatorInst>(I2) ||
         I1->isEHPad() || I2->isEHPad() ||
         isa<AllocaInst>(I1) || isa<AllocaInst>(I2) ||
-        I1->mayHaveSideEffects() || I2->mayHaveSideEffects() ||
+        I1->mayHaveSideEffectsIgnoringTermination() ||
+        I2->mayHaveSideEffectsIgnoringTermination() ||
         I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() ||
         !I1->hasOneUse() || !I2->hasOneUse() ||
         !JointValueMap.count(InstPair))
       return Changed;
 
     // Check whether we should swap the operands of ICmpInst.
     // TODO: Add support of communativity.
     ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2);

test/LTO/X86/parallel.ll

 ; CHECK0-NOT: bar
 define void @foo() {
   call void @bar()
   ret void
 }
 
 ; CHECK1-NOT: foo
 ; CHECK1: T bar
-; CHECK1-NOT: foo
+; CHECK1: U foo
 define void @bar() {
   call void @foo()
   ret void
 }

test/Transforms/ADCE/noreturn.ll

+; RUN: opt -adce -S < %s | FileCheck %s
+
+; The call to @foo cannot be dropped as it may not terminate, even though it is
+; otherwise side-effect free.
+declare void @foo() readnone nounwind
+; The call to @fmaxf can be dropped as it is a known library function, which is
+; guaranteed to terminate.
+declare float @fmaxf(float %a, float %b) readnone nounwind
+declare void @side_effect()
+
+define void @test_call() {
+entry:
+; CHECK-LABEL: define void @test_call()
+; CHECK: tail call void @foo
+; CHECK-NOT: tail call float @fmaxf
+; CHECK: tail call void @side_effect
+  tail call void @foo()
+  %max = tail call float @fmaxf(float 1.0, float 2.0)
+  tail call void @side_effect()
+  ret void
+}

test/Transforms/BDCE/basic.ll

 ; RUN: opt -S -bdce -instsimplify < %s | FileCheck %s
 ; RUN: opt -S -instsimplify < %s | FileCheck %s -check-prefix=CHECK-IO
 target datalayout = "E-m:e-i64:64-n32:64"
 target triple = "powerpc64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind readnone
 define signext i32 @bar(i32 signext %x) #0 {
 entry:
-  %call = tail call signext i32 @foo(i32 signext 5) #0
-  %and = and i32 %call, 4
+  %call0 = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call0, 4
   %or = or i32 %and, %x
   %call1 = tail call signext i32 @foo(i32 signext 3) #0
   %and2 = and i32 %call1, 8
   %or3 = or i32 %or, %and2
   %call4 = tail call signext i32 @foo(i32 signext 2) #0
   %and5 = and i32 %call4, 16
   %or6 = or i32 %or3, %and5
   %call7 = tail call signext i32 @foo(i32 signext 1) #0
   %and8 = and i32 %call7, 32
   %or9 = or i32 %or6, %and8
   %call10 = tail call signext i32 @foo(i32 signext 0) #0
   %and11 = and i32 %call10, 64
   %or12 = or i32 %or9, %and11
   %call13 = tail call signext i32 @foo(i32 signext 4) #0
   %and14 = and i32 %call13, 128
   %or15 = or i32 %or12, %and14
   %shr = ashr i32 %or15, 4
   ret i32 %shr
 
 ; CHECK-LABEL: @bar
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: %call0
+; CHECK: tail call signext i32 @foo(i32 signext 3)
+; CHECK-NOT: %call1
 ; CHECK: tail call signext i32 @foo(i32 signext 2)
 ; CHECK: tail call signext i32 @foo(i32 signext 1)
 ; CHECK: tail call signext i32 @foo(i32 signext 0)
 ; CHECK: tail call signext i32 @foo(i32 signext 4)
 ; CHECK: ret i32
 
 ; Check that instsimplify is not doing this all on its own.
 ; CHECK-IO-LABEL: @bar

 ; CHECK-IO: ret i32
 }
 
 declare signext i32 @goo(i32 signext) #1
 
 ; Function Attrs: nounwind readnone
 define signext i32 @tar1(i32 signext %x) #0 {
 entry:
-  %call = tail call signext i32 @foo(i32 signext 5) #0
-  %and = and i32 %call, 33554432
+  %call0 = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call0, 33554432
   %or = or i32 %and, %x
   %call1 = tail call signext i32 @foo(i32 signext 3) #0
   %and2 = and i32 %call1, 67108864
   %or3 = or i32 %or, %and2
   %call4 = tail call signext i32 @foo(i32 signext 2) #0
   %and5 = and i32 %call4, 16
   %or6 = or i32 %or3, %and5
   %call7 = tail call signext i32 @foo(i32 signext 1) #0
   %and8 = and i32 %call7, 32
   %or9 = or i32 %or6, %and8
   %call10 = tail call signext i32 @foo(i32 signext 0) #0
   %and11 = and i32 %call10, 64
   %or12 = or i32 %or9, %and11
   %call13 = tail call signext i32 @foo(i32 signext 4) #0
   %and14 = and i32 %call13, 128
   %or15 = or i32 %or12, %and14
   %bs = tail call i32 @llvm.bswap.i32(i32 %or15) #0
   %shr = ashr i32 %bs, 4
   ret i32 %shr
 
 ; CHECK-LABEL: @tar1
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: %call0
+; CHECK: tail call signext i32 @foo(i32 signext 3)
+; CHECK-NOT: %call1
 ; CHECK: tail call signext i32 @foo(i32 signext 2)
 ; CHECK: tail call signext i32 @foo(i32 signext 1)
 ; CHECK: tail call signext i32 @foo(i32 signext 0)
 ; CHECK: tail call signext i32 @foo(i32 signext 4)
 ; CHECK: ret i32
 }
 
 ; Function Attrs: nounwind readnone
 declare i32 @llvm.bswap.i32(i32) #0
 
 ; Function Attrs: nounwind readnone
 define signext i32 @tar2(i32 signext %x) #0 {
 entry:
-  %call = tail call signext i32 @foo(i32 signext 5) #0
-  %and = and i32 %call, 33554432
+  %call0 = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call0, 33554432
   %or = or i32 %and, %x
   %call1 = tail call signext i32 @foo(i32 signext 3) #0
   %and2 = and i32 %call1, 67108864
   %or3 = or i32 %or, %and2
   %call4 = tail call signext i32 @foo(i32 signext 2) #0
   %and5 = and i32 %call4, 16
   %or6 = or i32 %or3, %and5
   %call7 = tail call signext i32 @foo(i32 signext 1) #0
   %and8 = and i32 %call7, 32
   %or9 = or i32 %or6, %and8
   %call10 = tail call signext i32 @foo(i32 signext 0) #0
   %and11 = and i32 %call10, 64
   %or12 = or i32 %or9, %and11
   %call13 = tail call signext i32 @foo(i32 signext 4) #0
   %and14 = and i32 %call13, 128
   %or15 = or i32 %or12, %and14
   %shl = shl i32 %or15, 10
   ret i32 %shl
 
 ; CHECK-LABEL: @tar2
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: %call0
+; CHECK: tail call signext i32 @foo(i32 signext 3)
+; CHECK-NOT: %call1
 ; CHECK: tail call signext i32 @foo(i32 signext 2)
 ; CHECK: tail call signext i32 @foo(i32 signext 1)
 ; CHECK: tail call signext i32 @foo(i32 signext 0)
 ; CHECK: tail call signext i32 @foo(i32 signext 4)
 ; CHECK: ret i32
 }
 
 ; Function Attrs: nounwind readnone
 define signext i32 @tar3(i32 signext %x) #0 {
 entry:
-  %call = tail call signext i32 @foo(i32 signext 5) #0
-  %and = and i32 %call, 33554432
+  %call0 = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call0, 33554432
   %or = or i32 %and, %x
   %call1 = tail call signext i32 @foo(i32 signext 3) #0
   %and2 = and i32 %call1, 67108864
   %or3 = or i32 %or, %and2
   %call4 = tail call signext i32 @foo(i32 signext 2) #0
   %and5 = and i32 %call4, 16
   %or6 = or i32 %or3, %and5
   %call7 = tail call signext i32 @foo(i32 signext 1) #0
   %and8 = and i32 %call7, 32
   %or9 = or i32 %or6, %and8
   %call10 = tail call signext i32 @foo(i32 signext 0) #0
   %and11 = and i32 %call10, 64
   %or12 = or i32 %or9, %and11
   %call13 = tail call signext i32 @foo(i32 signext 4) #0
   %and14 = and i32 %call13, 128
   %or15 = or i32 %or12, %and14
   %add = add i32 %or15, 5
   %shl = shl i32 %add, 10
   ret i32 %shl
 
 ; CHECK-LABEL: @tar3
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: %call0
+; CHECK: tail call signext i32 @foo(i32 signext 3)
+; CHECK-NOT: %call1
 ; CHECK: tail call signext i32 @foo(i32 signext 2)
 ; CHECK: tail call signext i32 @foo(i32 signext 1)
 ; CHECK: tail call signext i32 @foo(i32 signext 0)
 ; CHECK: tail call signext i32 @foo(i32 signext 4)
 ; CHECK: ret i32
 }
 
 ; Function Attrs: nounwind readnone
 define signext i32 @tar4(i32 signext %x) #0 {
 entry:
-  %call = tail call signext i32 @foo(i32 signext 5) #0
-  %and = and i32 %call, 33554432
+  %call0 = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call0, 33554432
   %or = or i32 %and, %x
   %call1 = tail call signext i32 @foo(i32 signext 3) #0
   %and2 = and i32 %call1, 67108864
   %or3 = or i32 %or, %and2
   %call4 = tail call signext i32 @foo(i32 signext 2) #0
   %and5 = and i32 %call4, 16
   %or6 = or i32 %or3, %and5
   %call7 = tail call signext i32 @foo(i32 signext 1) #0
   %and8 = and i32 %call7, 32
   %or9 = or i32 %or6, %and8
   %call10 = tail call signext i32 @foo(i32 signext 0) #0
   %and11 = and i32 %call10, 64
   %or12 = or i32 %or9, %and11
   %call13 = tail call signext i32 @foo(i32 signext 4) #0
   %and14 = and i32 %call13, 128
   %or15 = or i32 %or12, %and14
   %sub = sub i32 %or15, 5
   %shl = shl i32 %sub, 10
   ret i32 %shl
 
 ; CHECK-LABEL: @tar4
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: %call0
+; CHECK: tail call signext i32 @foo(i32 signext 3)
+; CHECK-NOT: %call1
 ; CHECK: tail call signext i32 @foo(i32 signext 2)
 ; CHECK: tail call signext i32 @foo(i32 signext 1)
 ; CHECK: tail call signext i32 @foo(i32 signext 0)
 ; CHECK: tail call signext i32 @foo(i32 signext 4)
 ; CHECK: ret i32
 }
 
 ; Function Attrs: nounwind readnone
 define signext i32 @tar5(i32 signext %x) #0 {
 entry:
-  %call = tail call signext i32 @foo(i32 signext 5) #0
-  %and = and i32 %call, 33554432
+  %call0 = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call0, 33554432
   %or = or i32 %and, %x
   %call1 = tail call signext i32 @foo(i32 signext 3) #0
   %and2 = and i32 %call1, 67108864
   %or3 = or i32 %or, %and2
   %call4 = tail call signext i32 @foo(i32 signext 2) #0
   %and5 = and i32 %call4, 16
   %or6 = or i32 %or3, %and5
   %call7 = tail call signext i32 @foo(i32 signext 1) #0
   %and8 = and i32 %call7, 32
   %or9 = or i32 %or6, %and8
   %call10 = tail call signext i32 @foo(i32 signext 0) #0
   %and11 = and i32 %call10, 64
   %or12 = or i32 %or9, %and11
   %call13 = tail call signext i32 @foo(i32 signext 4) #0
   %and14 = and i32 %call13, 128
   %or15 = or i32 %or12, %and14
   %xor = xor i32 %or15, 5
   %shl = shl i32 %xor, 10
   ret i32 %shl
 
 ; CHECK-LABEL: @tar5
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: %call0
+; CHECK: tail call signext i32 @foo(i32 signext 3)
+; CHECK-NOT: %call1
 ; CHECK: tail call signext i32 @foo(i32 signext 2)
 ; CHECK: tail call signext i32 @foo(i32 signext 1)
 ; CHECK: tail call signext i32 @foo(i32 signext 0)
 ; CHECK: tail call signext i32 @foo(i32 signext 4)
 ; CHECK: ret i32
 }
 
 ; Function Attrs: nounwind readnone
 define signext i32 @tar7(i32 signext %x, i1 %b) #0 {
 entry:
-  %call = tail call signext i32 @foo(i32 signext 5) #0
-  %and = and i32 %call, 33554432
+  %call0 = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call0, 33554432
   %or = or i32 %and, %x
   %call1 = tail call signext i32 @foo(i32 signext 3) #0
   %and2 = and i32 %call1, 67108864
   %or3 = or i32 %or, %and2
   %call4 = tail call signext i32 @foo(i32 signext 2) #0
   %and5 = and i32 %call4, 16
   %or6 = or i32 %or3, %and5
   %call7 = tail call signext i32 @foo(i32 signext 1) #0
   %and8 = and i32 %call7, 32
   %or9 = or i32 %or6, %and8
   %call10 = tail call signext i32 @foo(i32 signext 0) #0
   %and11 = and i32 %call10, 64
   %or12 = or i32 %or9, %and11
   %call13 = tail call signext i32 @foo(i32 signext 4) #0
   %and14 = and i32 %call13, 128
   %or15 = or i32 %or12, %and14
   %v = select i1 %b, i32 %or15, i32 5
   %shl = shl i32 %v, 10
   ret i32 %shl
 
 ; CHECK-LABEL: @tar7
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: %call0
+; CHECK: tail call signext i32 @foo(i32 signext 3)
+; CHECK-NOT: %call1
 ; CHECK: tail call signext i32 @foo(i32 signext 2)
 ; CHECK: tail call signext i32 @foo(i32 signext 1)
 ; CHECK: tail call signext i32 @foo(i32 signext 0)
 ; CHECK: tail call signext i32 @foo(i32 signext 4)
 ; CHECK: ret i32
 }
 
 ; Function Attrs: nounwind readnone
 define signext i16 @tar8(i32 signext %x) #0 {
 entry:
-  %call = tail call signext i32 @foo(i32 signext 5) #0
-  %and = and i32 %call, 33554432
+  %call0 = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call0, 33554432
   %or = or i32 %and, %x
   %call1 = tail call signext i32 @foo(i32 signext 3) #0
   %and2 = and i32 %call1, 67108864
   %or3 = or i32 %or, %and2
   %call4 = tail call signext i32 @foo(i32 signext 2) #0
   %and5 = and i32 %call4, 16
   %or6 = or i32 %or3, %and5
   %call7 = tail call signext i32 @foo(i32 signext 1) #0
   %and8 = and i32 %call7, 32
   %or9 = or i32 %or6, %and8
   %call10 = tail call signext i32 @foo(i32 signext 0) #0
   %and11 = and i32 %call10, 64
   %or12 = or i32 %or9, %and11
   %call13 = tail call signext i32 @foo(i32 signext 4) #0
   %and14 = and i32 %call13, 128
   %or15 = or i32 %or12, %and14
   %tr = trunc i32 %or15 to i16
   ret i16 %tr
 
 ; CHECK-LABEL: @tar8
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
-; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: %call0
+; CHECK: tail call signext i32 @foo(i32 signext 3)
+; CHECK-NOT: %call1
 ; CHECK: tail call signext i32 @foo(i32 signext 2)
 ; CHECK: tail call signext i32 @foo(i32 signext 1)
 ; CHECK: tail call signext i32 @foo(i32 signext 0)
 ; CHECK: tail call signext i32 @foo(i32 signext 4)
 ; CHECK: ret i16
 }
 
 attributes #0 = { nounwind readnone }
 attributes #1 = { nounwind }
 

test/Transforms/Inline/delete-call.ll

 ; REQUIRES: asserts
 ; RUN: opt -S -inline -stats < %s 2>&1 | FileCheck %s
 ; CHECK: Number of functions inlined
 
 ; RUN: opt -S -inline -functionattrs -stats < %s 2>&1 | FileCheck -check-prefix=CHECK-FUNCTIONATTRS %s
-; CHECK-FUNCTIONATTRS: Number of call sites deleted, not inlined
+; FIXME: If we could prove that @test always terminates, we could remove the
+;        call without doing a full inlining.
+; CHECK-FUNCTIONATTRS-NOT: Number of call sites deleted, not inlined
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32"
 target triple = "i386-apple-darwin9.8"
 
 define internal i32 @test(i32 %x, i32 %y, i32 %z) nounwind {
 entry:
   %0 = add nsw i32 %y, %z                         ; <i32> [#uses=1]
   %1 = mul i32 %0, %x                             ; <i32> [#uses=1]

test/Transforms/Inline/noreturn.ll

+; RUN: opt -inline -S < %s | FileCheck %s
+
+; The call to @foo cannot be dropped as it may not terminate, even though it is
+; otherwise side-effect free.
+define void @foo() readnone nounwind noinline {
+entry:
+  br label %loop
+
+loop:
+  br label %loop
+}
+declare void @side_effect()
+
+define void @test_call() {
+entry:
+; CHECK-LABEL: define void @test_call()
+; CHECK: tail call void @foo
+; CHECK: tail call void @side_effect
+  tail call void @foo()
+  tail call void @side_effect()
+  ret void
+}

test/Transforms/InstCombine/nothrow.ll

-; RUN: opt < %s -instcombine -S | not grep call
+; RUN: opt < %s -instcombine -S | FileCheck %s
 ; rdar://6880732
 declare double @t1(i32) readonly
 
 define void @t2() nounwind {
-  call double @t1(i32 42)  ;; dead call even though callee is not nothrow.
+  call double @t1(i32 42)
+; FIXME: If we could prove that @t1 always terminates, we could remove the call.
+; CHECK: call double @t1
   ret void
 }

test/Transforms/InstSimplify/call.ll

 
 ; Test a non-intrinsic that we know about as a library call.
 declare float @fabs(float %x)
 
 define float @test_fabs_libcall() {
 ; CHECK-LABEL: @test_fabs_libcall(
 
   %x = call float @fabs(float -42.0)
-; This is still a real function call, so instsimplify won't nuke it -- other
-; passes have to do that.
-; CHECK-NEXT: call float @fabs
+; CHECK-NOT: call float @fabs
 
   ret float %x
 ; CHECK-NEXT: ret float 4.2{{0+}}e+01
 }
 
 
 declare float @llvm.fabs.f32(float) nounwind readnone
 declare float @llvm.floor.f32(float) nounwind readnone