Reassociate: Fix miscompile for va_arg arguments.

[MatzeB]

Summary

isUnmovableInstruction() had a list of instructions hardcoded which are
considered unmovable. The list lacked (at least) an entry for the va_arg
and cmpxchg instructions.
Fix this by using !Instruction::mayRead() && isSafeToSpeculativelyExecute() instead of maintaining another
instruction list.

[MatzeB]

Note that this change takes the [USF]Div and [USF]Rem instructions out of the list, with llvms semantics they do not produce side effects (but just a poison value) so this should be fine. I'm also running the llvm-testsuite now to get some more testing for this change.

[bkramer]

In D11577#213912, @MatzeB wrote:

Note that this change takes the [USF]Div and [USF]Rem instructions out of the list, with llvms semantics they do not produce side effects (but just a poison value) so this should be fine. I'm also running the llvm-testsuite now to get some more testing for this change.

Integer div by zero will still trap so div and rem cannot be moved freely between basic blocks without changing behavior. I'm not sure if Reassociate performs movements that could move instructions into a different path in the CFG, but if it does we'll need something stronger like isSafeToSpeculativelyExecute.

[MatzeB]

Updated the patch to use a !I->mayRead() && isSafeToSpeculativelyExecute(I) to determine whether we can move an instruction around.

[MatzeB]

In D11577#213942, @bkramer wrote:

In D11577#213912, @MatzeB wrote:

Note that this change takes the [USF]Div and [USF]Rem instructions out of the list, with llvms semantics they do not produce side effects (but just a poison value) so this should be fine. I'm also running the llvm-testsuite now to get some more testing for this change.

Integer div by zero will still trap so div and rem cannot be moved freely between basic blocks without changing behavior. I'm not sure if Reassociate performs movements that could move instructions into a different path in the CFG, but if it does we'll need something stronger like isSafeToSpeculativelyExecute.

From what I can see it does not move the instructions into different CFG paths but just inside a basic block, but that may already fail if you reorder an instruction potentially triggering undefined behaviour and a call I think, so switching to isSafeToSpeculativelyExecute() is the right call.

[majnemer]

lib/Transforms/Scalar/Reassociate.cpp

278

Would it make sense to extract this logic into a hypothetical mayBeControlDependent ?

[MatzeB]

New revision, introducing a mayBeControlDependent() function.

[MatzeB]

Let's call the function mayBeStateDependent() as classical definitions of control dependence are more concerned with control flow while this function is mostly concerned with global state and memory contents (of course the global state is *also* control dependent).

[• dberlin]

So, these are either data dependent, control dependent, or both :)
(IE that is the correct terminology)

[MatzeB]

In D11577#214574, @dberlin wrote:

So, these are either data dependent, control dependent, or both :)
(IE that is the correct terminology)

If you think in that dichotomy, then it is a data dependence. However usually data dependence talks about variables or registers while this function specifically is about the things not modeled as variables/ssa values. It is about the global state/memory, that's why I put the "State" in the name data dependence would be too broad.

[• dberlin]

????

I'm not thinking in that dichotomy, that is the generally dichotomy
of dependences in compilers :).

Data dependence talks about memory all the time, in compiler
schedulers, in loop data dependence, etc. Heck, even in SSA.
So I honestly do not grasp the distinction you are trying to draw here.

It happens that in LLVM, explicitly represented data dependences do
not make instructions inherently immovable. The IR explicitly
represents these things well enough that we don't pay a high cost for
figuring out safe move locations for those things.

However, memory data dependences are implicit (becuase we lack
something like memoryssa), and the cost of figuring out where the safe
move points are is not worth it.
(IE none of these instructions are actually immovable, it's just that
we don't want to pay the cost to figure out the place we could move
them to :P. For some of them, there is usually only one correct place
anyway, like phi nodes. )

Not to bikeshed this too hard, but state dependent means nothing to
me, and it doesn't actually give anyone any idea what the function
should return for what.

[MatzeB]

My previous comment was probably worded to strongly. What I meant was that a function name of "ControlDependent" or "DataDependent" would have been too broad. I just realize that your comment was probably about my "of course the global state is *also* control dependent" remark which I admit is confusing and only makes sense if you have things like the value state dependence graphs or program expression graphs in mind where all control dependences usually manifest themselfes as data dependences on the memory values.

I was going for the term state because we do not just capture the contents of the computer memory but also things like input/output or program abortion because of undefined behaviour. Anyway I'm completely fine with calling this memory dependence which is by far the more popular term.

[MatzeB]

Uploaded a new version which calls the function mayBeMemoryDependent(). Change the title to make it clear that this is not just a cleanup.

[qcolombet]

Ping.

[mcrosier]

LGTM, but I don't want to undercut Daniel or David, so I won't make my vote official.

[• dberlin]

LGTM

[qcolombet]

Thanks.

Committed revision 244244.

include/llvm/Analysis/ValueTracking.h

namespace llvm {
   ///
   /// This method can return true for instructions that read memory;
   /// for such instructions, moving them may change the resulting value.
   bool isSafeToSpeculativelyExecute(const Value *V,
                                     const Instruction *CtxI = nullptr,
                                     const DominatorTree *DT = nullptr,
                                     const TargetLibraryInfo *TLI = nullptr);
 
+  /// Returns true if the result or effects of the given instructions \p I
+  /// depend on or influence global memory.
+  /// Memory dependence arises for example if the the instruction reads from
+  /// memory or may produce effects or undefined behaviour. Memory dependent
+  /// instructions generally cannot be reorderd with respect to other memory
+  /// dependent instructions or moved into non-dominated basic blocks.
+  /// Instructions which just compute a value based on the values of their
+  /// operands are not memory dependent.
+  bool mayBeMemoryDependent(const Instruction &I);
+
   /// isKnownNonNull - Return true if this pointer couldn't possibly be null by
   /// its definition.  This returns true for allocas, non-extern-weak globals
   /// and byval arguments.
   bool isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI = nullptr);
 
   /// isKnownNonNullAt - Return true if this pointer couldn't possibly be null.
   /// If the context instruction is specified perform context-sensitive analysis
   /// and return true if the pointer couldn't possibly be null at the specified

lib/Analysis/ValueTracking.cpp

bool llvm::isSafeToSpeculativelyExecute(const Value *V,
   case Instruction::LandingPad:
   case Instruction::AtomicRMW:
   case Instruction::AtomicCmpXchg:
   case Instruction::Resume:
     return false; // Misc instructions which have effects
   }
 }
 
+bool llvm::mayBeMemoryDependent(const Instruction &I) {
+  return I.mayReadOrWriteMemory() || !isSafeToSpeculativelyExecute(&I);
+}
+
 /// Return true if we know that the specified value is never null.
 bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) {
   // Alloca never returns null, malloc might.
   if (isa<AllocaInst>(V)) return true;
 
   // A byval, inalloca, or nonnull argument is never null.
   if (const Argument *A = dyn_cast<Argument>(V))
     return A->hasByValOrInAllocaAttr() || A->hasNonNullAttr();

lib/Transforms/Scalar/Reassociate.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/ValueHandle.h"
if (V->hasOneUse() && isa<Instruction>(V) &&
       (cast<Instruction>(V)->getOpcode() == Opcode1 ||
        cast<Instruction>(V)->getOpcode() == Opcode2) &&
       (!isa<FPMathOperator>(V) ||
        cast<Instruction>(V)->hasUnsafeAlgebra()))
     return cast<BinaryOperator>(V);
   return nullptr;
 }
 
-static bool isUnmovableInstruction(Instruction *I) {
-  switch (I->getOpcode()) {
-  case Instruction::PHI:
-  case Instruction::LandingPad:
-  case Instruction::Alloca:
-  case Instruction::Load:
-  case Instruction::Invoke:
-  case Instruction::UDiv:
-  case Instruction::SDiv:
-  case Instruction::FDiv:
-  case Instruction::URem:
-  case Instruction::SRem:
-  case Instruction::FRem:
-    return true;
-  case Instruction::Call:
-    return !isa<DbgInfoIntrinsic>(I);
-  default:
-    return false;
-  }
-}
-
 void Reassociate::BuildRankMap(Function &F) {
   unsigned i = 2;
 
   // Assign distinct ranks to function arguments.
   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
     ValueRankMap[&*I] = ++i;
     DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n");
   }
 
   ReversePostOrderTraversal<Function*> RPOT(&F);
   for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
          E = RPOT.end(); I != E; ++I) {
     BasicBlock *BB = *I;
     unsigned BBRank = RankMap[BB] = ++i << 16;
 
     // Walk the basic block, adding precomputed ranks for any instructions that
     // we cannot move.  This ensures that the ranks for these instructions are
     // all different in the block.
     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
-      if (isUnmovableInstruction(I))
+      if (mayBeMemoryDependent(*I))
         ValueRankMap[&*I] = ++BBRank;
   }
 }
 
 unsigned Reassociate::getRank(Value *V) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) {
     if (isa<Argument>(V)) return ValueRankMap[V];   // Function argument.

test/Transforms/Reassociate/vaarg_movable.ll

+; RUN: opt -S -reassociate -die < %s | FileCheck %s
+
+; The two va_arg instructions depend on the memory/context, are therfore not
+; identical and the sub should not be optimized to 0 by reassociate.
+;
+; CHECK-LABEL @func(
+; ...
+; CHECK: %v0 = va_arg i8** %varargs, i32
+; CHECK: %v1 = va_arg i8** %varargs, i32
+; CHECK: %v0.neg = sub i32 0, %v0
+; CHECK: %sub = add i32 %v0.neg, 1
+; CHECK: %add = add i32 %sub, %v1
+; ...
+; CHECK: ret i32 %add
+define i32 @func(i32 %dummy, ...) {
+  %varargs = alloca i8*, align 8
+  %varargs1 = bitcast i8** %varargs to i8*
+  call void @llvm.va_start(i8* %varargs1)
+  %v0 = va_arg i8** %varargs, i32
+  %v1 = va_arg i8** %varargs, i32
+  %sub = sub nsw i32 %v1, %v0
+  %add = add nsw i32 %sub, 1
+  call void @llvm.va_end(i8* %varargs1)
+  ret i32 %add
+}
+
+declare void @llvm.va_start(i8*)
+declare void @llvm.va_end(i8*)