[Evaluator] Look through invariant.group intrinsics

[aeubanks]

Summary

Turning on -fstrict-vtable-pointers in Chrome caused an extra global
initializer. Turns out that a llvm.strip.invariant.group intrinsic was
causing GlobalOpt to fail to step through some simple code.

We can treat *.invariant.group uses as simply their operand.
Value::stripPointerCastsForAliasAnalysis() does exactly this. This
should be safe because the Evaluator does not skip memory accesses due
to invariants or alias analysis.

However, we don't want to leak that we've stripped arbitrary pointer
casts to users of Evaluator, so we bail out if we evaluate a function to
any constant, since we may have looked through *.invariant.group calls
and aliasing pointers cannot be arbitrarily substituted.

[aeubanks]

I'm not sure if this is actually sound or not, but I think it is

[aeubanks]

use Value::stripPointerCastsForAliasAnalysis()

[rnk]

I'm trying to understand the need to special case returns bit better. I'm thinking of this example:

p = ...;
p->vcall1();
q = strip(p);
q->vcall2();

If the evaluator was used to transform this program into this:

p = ...;
p->vcall1();
p->vcall2();

... then I guess that is a bug.

I think this is only an issue if we allow interleaving the evaluator with the memory optimizations that use the invariant group metadata. If we only use Evaluator within one globalopt pass as you have in this test case, there shouldn't be any issue. I checked, and Evaluator is also used for whole program devirtualization. I can imagine a sequence of transforms involving WPD that ends up being similar to what I have above, so I guess there is a real soundness issue.

How about we allow this evaluation just for globalopt, and then we don't allow it for whole-program devirtualization?

I guess the other thing to worry about is, are we sure this really is safe for globalopt? Globalopt could, for example, evaluate a store of a pointer that has been stripped into memory, and then some later pass can load it.

Maybe a more general solution would be to restrict the operations that can be performed on a stripped pointer. Strip is really used for two things: pointer comparisons and field loads and stores. Maybe the really sound way to handle this is to tag these values in the Evaluator to forbid other kinds of operations on them. =/

llvm/lib/Transforms/Utils/Evaluator.cpp

725

I think it's "gleaned"

733

I don't think we can use the LLVM type here as a way to check if any stripped values have leaked out, since ptrtoint exists.

[aeubanks]

llvm/lib/Transforms/Utils/Evaluator.cpp

733

If you have an int derived from a group invariant pointer, it must have been stripped. If you want to cast it back to a pointer and use it, you have to launder it again anyway. The Evaluator isn't changing any existing group invariant intrinsic instructions so I believe it's safe in all cases. I believe the only issue is if we return back an SSA value from the *caller*, which the Evaluator could do.

[aeubanks]

spelling

[aeubanks]

bail out when returning anything

[aeubanks]

ping

[rnk]

lgtm

My concerns are addressed now that you are checking for void types instead of pointer return types.

llvm/include/llvm/Transforms/Utils/Evaluator.h

private:
   /// These global variables have been marked invariant by the static
   /// constructor.
   SmallPtrSet<GlobalVariable*, 8> Invariants;
 
   /// These are constants we have checked and know to be simple enough to live
   /// in a static initializer of a global.
   SmallPtrSet<Constant*, 8> SimpleConstants;
 
+  /// Whether or not we've stripped pointer casts down to alias analysis info.
+  /// If we have, we can't return a pointer value since we may return aliasing
+  /// but separate pointers, which cannot be substituted for each other.
+  bool StrippedPointerCastsForAliasAnalysis = false;
+
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H

llvm/lib/Transforms/Utils/Evaluator.cpp

if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
         } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
           LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
           ++CurInst;
           continue;
         } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
           LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
           ++CurInst;
           continue;
+        } else {
+          Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
+          // Only attempt to getVal() if we've actually managed to strip
+          // anything away, or else we'll call getVal() on the current
+          // instruction.
+          if (Stripped != &*CurInst) {
+            InstResult = getVal(Stripped);
           }
-
-        LLVM_DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
+          if (InstResult) {
+            LLVM_DEBUG(dbgs()
+                       << "Stripped pointer casts for alias analysis for "
+                          "intrinsic call.\n");
+            StrippedPointerCastsForAliasAnalysis = true;
+          } else {
+            LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
             return false;
           }
+        }
+      }
 
+      if (!InstResult) {
         // Resolve function pointers.
         SmallVector<Constant *, 8> Formals;
         Function *Callee = getCalleeWithFormalArgs(CB, Formals);
         if (!Callee || Callee->isInterposable()) {
           LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
-        return false;  // Cannot resolve.
+          return false; // Cannot resolve.
         }
 
         if (Callee->isDeclaration()) {
           // If this is a function we can constant fold, do it.
           if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
             InstResult = castCallResultIfNeeded(CB.getCalledOperand(), C);
             if (!InstResult)
               return false;
             LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
                               << *InstResult << "\n");
           } else {
             LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
             return false;
           }
         } else {
           if (Callee->getFunctionType()->isVarArg()) {
-          LLVM_DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
+            LLVM_DEBUG(dbgs()
+                       << "Can not constant fold vararg function call.\n");
             return false;
           }
 
           Constant *RetVal = nullptr;
           // Execute the call, if successful, use the return value.
           ValueStack.emplace_back();
           if (!EvaluateFunction(Callee, RetVal, Formals)) {
             LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
             return false;
           }
           ValueStack.pop_back();
           InstResult = castCallResultIfNeeded(CB.getCalledOperand(), RetVal);
           if (RetVal && !InstResult)
             return false;
 
           if (InstResult) {
             LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
                               << *InstResult << "\n\n");
           } else {
             LLVM_DEBUG(dbgs()
                        << "Successfully evaluated function. Result: 0\n\n");
           }
         }
+      }
     } else if (CurInst->isTerminator()) {
       LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
 
       if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
         if (BI->isUnconditional()) {
           NextBB = BI->getSuccessor(0);
         } else {
           ConstantInt *Cond =
while (true) {
 
     if (!EvaluateBlock(CurInst, NextBB))
       return false;
 
     if (!NextBB) {
       // Successfully running until there's no next block means that we found
       // the return.  Fill it the return value and pop the call stack.
       ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
-      if (RI->getNumOperands())
+      if (RI->getNumOperands()) {
+        // The Evaluator can look through pointer casts as long as alias
+        // analysis holds because it's just a simple interpreter and doesn't
+        // skip memory accesses due to invariant group metadata, but we can't
+        // let users of Evaluator use a value that's been gleamed looking
+        // through stripping pointer casts since separate pointers that alias
+        // cannot necessarily be substituted for each other.
+        // FIXME: We could be more precise tracking if the return value had ever
+        // transitively been through a
+        // Value::stripPointerCastsForAliasAnalysis(), rather than giving up on
+        // all pointer return values.
+        if (StrippedPointerCastsForAliasAnalysis &&
+            RI->getReturnValue()->getType()->isPointerTy()) {
+          return false;
+        }
         RetVal = getVal(RI->getOperand(0));
+      }
       CallStack.pop_back();
       return true;
     }
 
     // Okay, we succeeded in evaluating this control flow.  See if we have
     // executed the new block before.  If so, we have a looping function,
     // which we cannot evaluate in reasonable time.
     if (!ExecutedBlocks.insert(NextBB).second)

llvm/test/Transforms/GlobalOpt/invariant.group.ll

 ; RUN: opt -S -globalopt < %s | FileCheck %s
 
-; This test is hint, what could globalOpt optimize and what it can't
-; FIXME: @tmp and @tmp2 can be safely set to 42
-; CHECK: @tmp = local_unnamed_addr global i32 0
-; CHECK: @tmp2 = local_unnamed_addr global i32 0
-; CHECK: @tmp3 = global i32 0
+; CHECK: @llvm.global_ctors = appending global [1 x {{.*}}@_GLOBAL__I_c
[e-mail]_ctors = appending global [3 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__I_a, i8* null }, { i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__I_b, i8* null }, { i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__I_c, i8* null }]
 
+; CHECK: @tmp = local_unnamed_addr global i32 42
+; CHECK: @tmp2 = local_unnamed_addr global i32 42
+; CHECK: @tmp3 = global i32 42
 @tmp = global i32 0
 @tmp2 = global i32 0
 @tmp3 = global i32 0
 @ptrToTmp3 = global i32* null
 
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__I_a, i8* null }]
-
 define i32 @TheAnswerToLifeTheUniverseAndEverything() {
   ret i32 42
 }
 
 define void @_GLOBAL__I_a() {
 enter:
   call void @_optimizable()
   call void @_not_optimizable()
enter:
 
   %val2 = load i32, i32* %1
   store i32 %val2, i32* @tmp2
   ret void
 }
 
 ; We can't step through launder.invariant.group here, because that would change
 ; this load in @usage_of_globals()
-; val = load i32, i32* %ptrVal, !invariant.group !0
+; %val = load i32, i32* %ptrVal, !invariant.group !0
 ; into
 ; %val = load i32, i32* @tmp3, !invariant.group !0
 ; and then we could assume that %val and %val2 to be the same, which coud be
 ; false, because @changeTmp3ValAndCallBarrierInside() may change the value
 ; of @tmp3.
 define void @_not_optimizable() {
 enter:
   store i32 13, i32* @tmp3, !invariant.group !0
 
   %0 = bitcast i32* @tmp3 to i8*
   %barr = call i8* @llvm.launder.invariant.group(i8* %0)
   %1 = bitcast i8* %barr to i32*
 
   store i32* %1, i32** @ptrToTmp3
   store i32 42, i32* %1, !invariant.group !0
 
   ret void
 }
+
 define void @usage_of_globals() {
 entry:
   %ptrVal = load i32*, i32** @ptrToTmp3
   %val = load i32, i32* %ptrVal, !invariant.group !0
 
   call void @changeTmp3ValAndCallBarrierInside()
   %val2 = load i32, i32* @tmp3, !invariant.group !0
   ret void;
 }
 
+@tmp4 = global i32 0
+
+define void @_GLOBAL__I_b() {
+enter:
+  %val = call i32 @TheAnswerToLifeTheUniverseAndEverything()
+  %p1 = bitcast i32* @tmp4 to i8*
+  %p2 = call i8* @llvm.strip.invariant.group.p0i8(i8* %p1)
+  %p3 = bitcast i8* %p2 to i32*
+  store i32 %val, i32* %p3
+  ret void
+}
+
+@tmp5 = global i32 0
+@tmp6 = global i32* null
+; CHECK: @tmp6 = local_unnamed_addr global i32* null
+
+define i32* @_dont_return_param(i32* %p) {
+  %p1 = bitcast i32* %p to i8*
+  %p2 = call i8* @llvm.launder.invariant.group(i8* %p1)
+  %p3 = bitcast i8* %p2 to i32*
+  ret i32* %p3
+}
+
+; We should bail out if we return any pointers derived via invariant.group intrinsics at any point.
+define void @_GLOBAL__I_c() {
+enter:
+  %tmp5 = call i32* @_dont_return_param(i32* @tmp5)
+  store i32* %tmp5, i32** @tmp6
+  ret void
+}
+
+
 declare void @changeTmp3ValAndCallBarrierInside()
 
 declare i8* @llvm.launder.invariant.group(i8*)
+declare i8* @llvm.strip.invariant.group.p0i8(i8*)
 
 !0 = !{}