[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

728

I think it's "gleaned"

736

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

736

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

public:
   }
 
   /// Evaluate a call to function F, returning true if successful, false if we
   /// can't evaluate it.  ActualArgs contains the formal arguments for the
   /// function.
   bool EvaluateFunction(Function *F, Constant *&RetVal,
                         const SmallVectorImpl<Constant*> &ActualArgs);
 
-  /// Evaluate all instructions in block BB, returning true if successful, false
-  /// if we can't evaluate it.  NewBB returns the next BB that control flows
-  /// into, or null upon return.
-  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
+  const DenseMap<Constant *, Constant *> &getMutatedMemory() const {
+    return MutatedMemory;
+  }
+
+  const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const {
+    return Invariants;
+  }
+
+private:
+  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
+                     bool &StrippedPointerCastsForAliasAnalysis);
 
   Constant *getVal(Value *V) {
     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
     Constant *R = ValueStack.back().lookup(V);
     assert(R && "Reference to an uncomputed value!");
     return R;
   }
 
   void setVal(Value *V, Constant *C) {
     ValueStack.back()[V] = C;
   }
 
   /// Casts call result to a type of bitcast call expression
   Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
 
-  const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
-    return MutatedMemory;
-  }
-
-  const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
-    return Invariants;
-  }
-
-private:
   /// Given call site return callee and list of its formal arguments
   Function *getCalleeWithFormalArgs(CallBase &CB,
                                     SmallVectorImpl<Constant *> &Formals);
 
   /// Given call site and callee returns list of callee formal argument
   /// values converting them when necessary
   bool getFormalParams(CallBase &CB, Function *F,
                        SmallVectorImpl<Constant *> &Formals);

llvm/lib/Transforms/Utils/Evaluator.cpp

if (auto *FT =
     if (!RV)
       LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
   }
   return RV;
 }
 
 /// Evaluate all instructions in block BB, returning true if successful, false
 /// if we can't evaluate it.  NewBB returns the next BB that control flows into,
-/// or null upon return.
-bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
-                              BasicBlock *&NextBB) {
+/// or null upon return. StrippedPointerCastsForAliasAnalysis is set to true if
+/// we looked through pointer casts to evaluate something.
+bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
+                              bool &StrippedPointerCastsForAliasAnalysis) {
   // This is the main evaluation loop.
   while (true) {
     Constant *InstResult = nullptr;
 
     LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
 
     if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
       if (!SI->isSimple()) {
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 =
bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
   BasicBlock *CurBB = &F->front();
 
   BasicBlock::iterator CurInst = CurBB->begin();
 
   while (true) {
     BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
     LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
 
-    if (!EvaluateBlock(CurInst, NextBB))
+    bool StrippedPointerCastsForAliasAnalysis = false;
+
+    if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
       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 gleaned looking
+        // through stripping pointer casts.
+        if (StrippedPointerCastsForAliasAnalysis &&
+            !RI->getReturnValue()->getType()->isVoidTy()) {
+          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)
       return false;  // looped!

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 = !{}