[InstSimplify] Treat invariant group insts as bitcasts for load operands

[aeubanks]

Summary

We can look through invariant group intrinsics for the purposes of
simplifying the result of a load.

Since intrinsics can't be constants, but we also don't want to
completely rewrite load constant folding, we convert the load operand to
a constant. For GEPs and bitcasts we just treat them as constants. For
invariant group intrinsics, we treat them as a bitcast.

[rnk]

I added @lebedev.ri as a reviewer, since Roman has done significant work on instcombine/instsimplify.

llvm/lib/Analysis/InstructionSimplify.cpp

5859

We already discarded constants above, so these don't have to be operators, they could be Instructions, BitCastInst, etc.

[lebedev.ri]

I think the recursion is unfortunate there. How about something like

static Constant *ConstructLoadOperandConstant(Value *Op) {
  SmallVector<Value*, 16> Worklist;
  
  OpStack.emplace_back(Op);
  for(int I = 0; I != OpStack.size(); ++I) {
    Value* Op = OpStack.back();
    
    if (isa<Constant>(Op))
      break; // YAY!

    if (auto *BC = dyn_cast<BitCastOperator>(Op))
      OpStack.emplace_back(BC->getOperand(0)); // Recurse.

    if (auto *GEP = dyn_cast<GEPOperator>(Op)) {
      if (all_of(ArrayRef<Value*>(GEP->operands()).drop_front(),
          [](Value*Op) { return isa<Constant>(Op); }))
        OpStack.emplace_back(GEP->getOperand(0)); // Recurse.
    }

    if (auto *II = dyn_cast<IntrinsicInst>(Op)) {
      if (II->getIntrinsicID() == Intrinsic::strip_invariant_group ||
          II->getIntrinsicID() == Intrinsic::launder_invariant_group)
        OpStack.emplace_back(II->getOperand(0)); // Recurse.
    }
    
    return nullptr; // Can't look past this instruction. Give up.
  }
  
  // Alright! Reconstruct this chain as constant expressions.
  Constant* NewOp = cast<Constant>(Worklist.pop_back_val());
  while(!OpStack.empty()) {
    Value* Op = OpStack.pop_back_val();

    if (isa<BitCastOperator>(Op))
      NewOp = ConstantExpr::getBitCast(NewOp, Op->getType());

    if (auto *GEP = dyn_cast<GEPOperator>(Op)) {
      SmallVector<Constant *> Idxs;
      Idxs.reserve(GEP->getNumOperands() - 1);
      for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I)
        Idxs.push_back(cast<Constant>(GEP->getOperand(I));
      return ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), NewOp,
                                            Idxs, GEP->isInBounds(),
                                            GEP->getInRangeIndex());
    }

    if (auto *II = dyn_cast<IntrinsicInst>(Op)) {
      if (II->getIntrinsicID() == Intrinsic::strip_invariant_group ||
          II->getIntrinsicID() == Intrinsic::launder_invariant_group)
        NewOp = ConstantExpr::getBitCast(NewOp, Op->getType());  
    }
    
    llvm_unreachable("Instruction handled in first loop but not here?");
  }
}
  
return NewOp;

llvm/lib/Analysis/InstructionSimplify.cpp

5855

Given load from \p Op, see if we can peel off certain pointer adjustments,
that are no-op for the purpose of the performing the load,
in the hope of eventually discovering that we are
actually loading from a constant.

5893–5894

As per D33619. and the default of the switch in SimplifyInstruction(),
we'll no longer call ConstantFoldInstruction(), but just the ConstantFoldLoadFromConstPtr().
Will we loose anything important because of that?

I would guess that iff we actually want to change that, perhaps it should be done afterwards,
and this should just continue to use ConstantFoldInstruction()?

llvm/test/Transforms/InstSimplify/invariant.group-load.ll

2

I'd like to see a bit more tests.
For example, this really needs negative tests.
What should happen if the @A isn't a constant?
One test with some pattern we can't handle would be good (non-constant gep indexes e.g.)

[Prazek]

In D101103#2718848, @lebedev.ri wrote:

I think the recursion is unfortunate there. How about something like

static Constant *ConstructLoadOperandConstant(Value *Op) {
  SmallVector<Value*, 16> Worklist;
  
  OpStack.emplace_back(Op);
  for(int I = 0; I != OpStack.size(); ++I) {
    Value* Op = OpStack.back();
    
    if (isa<Constant>(Op))
      break; // YAY!

    if (auto *BC = dyn_cast<BitCastOperator>(Op))
      OpStack.emplace_back(BC->getOperand(0)); // Recurse.

    if (auto *GEP = dyn_cast<GEPOperator>(Op)) {
      if (all_of(ArrayRef<Value*>(GEP->operands()).drop_front(),
          [](Value*Op) { return isa<Constant>(Op); }))
        OpStack.emplace_back(GEP->getOperand(0)); // Recurse.
    }

    if (auto *II = dyn_cast<IntrinsicInst>(Op)) {
      if (II->getIntrinsicID() == Intrinsic::strip_invariant_group ||
          II->getIntrinsicID() == Intrinsic::launder_invariant_group)
        OpStack.emplace_back(II->getOperand(0)); // Recurse.
    }
    
    return nullptr; // Can't look past this instruction. Give up.
  }
  
  // Alright! Reconstruct this chain as constant expressions.
  Constant* NewOp = cast<Constant>(Worklist.pop_back_val());
  while(!OpStack.empty()) {
    Value* Op = OpStack.pop_back_val();

    if (isa<BitCastOperator>(Op))
      NewOp = ConstantExpr::getBitCast(NewOp, Op->getType());

    if (auto *GEP = dyn_cast<GEPOperator>(Op)) {
      SmallVector<Constant *> Idxs;
      Idxs.reserve(GEP->getNumOperands() - 1);
      for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I)
        Idxs.push_back(cast<Constant>(GEP->getOperand(I));
      return ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), NewOp,
                                            Idxs, GEP->isInBounds(),
                                            GEP->getInRangeIndex());
    }

    if (auto *II = dyn_cast<IntrinsicInst>(Op)) {
      if (II->getIntrinsicID() == Intrinsic::strip_invariant_group ||
          II->getIntrinsicID() == Intrinsic::launder_invariant_group)
        NewOp = ConstantExpr::getBitCast(NewOp, Op->getType());  
    }
    
    llvm_unreachable("Instruction handled in first loop but not here?");
  }
}
  
return NewOp;

Also if you want to traverse bitcasts and invariant.group intrinsics, you could perhaps use `stripPointerCastsAndOffsets<PSK_ForAliasAnalysis>`

llvm/test/Transforms/InstSimplify/invariant.group-load.ll

13

Could you add similar test for launder.invariant.group as well?

[Prazek]

Out of curiosity: have you seen this pattern happening in the wild with -fstrict-vtable-pointers?

[aeubanks]

In D101103#2718965, @Prazek wrote:

Out of curiosity: have you seen this pattern happening in the wild with -fstrict-vtable-pointers?

Yes, it was causing a major size regression in one specific file (with rtti). I've managed to reduce it down to

struct A {
  int i;
  virtual void f();
  A(): i(4) {}
};

const A g;

int foo() {
  const A* a = &g;
  return a->i;
}

$ ./build/rel/bin/clang++ /tmp/a.cc -o - -S -emit-llvm -O2 -fstrict-vtable-pointers

%struct.A = type <{ i32 (...)**, i32, [4 x i8] }>

@_ZL1g = internal constant %struct.A <{ i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @_ZTV1A, i32 0, inrange i32 0, i32 2) to i32 (...)**), i32 4, [4 x i8] zeroinitializer }>, align 8
@_ZTV1A = external dso_local unnamed_addr constant { [3 x i8*] }, align 8
@llvm.global_ctors = appending global [0 x { i32, void ()*, i8* }] zeroinitializer

; Function Attrs: nofree nosync nounwind readnone uwtable willreturn mustprogress
define dso_local i32 @_Z8hahahahav() local_unnamed_addr #0 {
entry:
  %0 = tail call i8* @llvm.strip.invariant.group.p0i8(i8* bitcast (%struct.A* @_ZL1g to i8*))
  %i = getelementptr inbounds i8, i8* %0, i64 8
  %1 = bitcast i8* %i to i32*
  %2 = load i32, i32* %1, align 8, !tbaa !6
  ret i32 %2
}

$ ./build/rel/bin/clang++ /tmp/a.cc -o - -S -emit-llvm -O2

; Function Attrs: nofree norecurse nosync nounwind readnone uwtable willreturn mustprogress
define dso_local i32 @_Z8hahahahav() local_unnamed_addr #0 {
entry:
  ret i32 4
}

[aeubanks]

looks like the strip is coming from CodeGenFunction::EmitLValueForField():

if (auto *ClassDef = dyn_cast<CXXRecordDecl>(rec)) {
  if (CGM.getCodeGenOpts().StrictVTablePointers &&
      ClassDef->isDynamicClass()) {
    // Getting to any field of dynamic object requires stripping dynamic
    // information provided by invariant.group.  This is because accessing
    // fields may leak the real address of dynamic object, which could result
    // in miscompilation when leaked pointer would be compared.
    auto *stripped = Builder.CreateStripInvariantGroup(addr.getPointer());
    addr = Address(stripped, addr.getAlignment());
  }
}

is this actually true?

[Prazek]

In D101103#2721429, @aeubanks wrote:

looks like the strip is coming from CodeGenFunction::EmitLValueForField():

if (auto *ClassDef = dyn_cast<CXXRecordDecl>(rec)) {
  if (CGM.getCodeGenOpts().StrictVTablePointers &&
      ClassDef->isDynamicClass()) {
    // Getting to any field of dynamic object requires stripping dynamic
    // information provided by invariant.group.  This is because accessing
    // fields may leak the real address of dynamic object, which could result
    // in miscompilation when leaked pointer would be compared.
    auto *stripped = Builder.CreateStripInvariantGroup(addr.getPointer());
    addr = Address(stripped, addr.getAlignment());
  }
}

is this actually true?

It is essentially more complex case of leaking the value of the pointer through comparison (documented in the docs)

struct A {

virtual void foo();
int field;

};

struct B {
  void foo() override;
};

external A* clobber(A* a) {
  return new(a) B;
}

void bar(A *a) {
  int* addr =  &a->field;
  A* new_a = clobber(a);
  if (addr == &new_a->field) {
    new_a->foo();
  }
}

Here if you don't strip "virtual information" from the pointer before getting the address of the field, the compiler will be able to figure out that the address
of a and new_a is the same in the branch, which would result in RAUW of new_a for a, resulting in incorrect devirtualization.

[Prazek]

In D101103#2720276, @aeubanks wrote:

In D101103#2718965, @Prazek wrote:

Out of curiosity: have you seen this pattern happening in the wild with -fstrict-vtable-pointers?

Yes, it was causing a major size regression in one specific file (with rtti). I've managed to reduce it down to

struct A {
  int i;
  virtual void f();
  A(): i(4) {}
};

const A g;

int foo() {
  const A* a = &g;
  return a->i;
}

$ ./build/rel/bin/clang++ /tmp/a.cc -o - -S -emit-llvm -O2 -fstrict-vtable-pointers

%struct.A = type <{ i32 (...)**, i32, [4 x i8] }>

@_ZL1g = internal constant %struct.A <{ i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @_ZTV1A, i32 0, inrange i32 0, i32 2) to i32 (...)**), i32 4, [4 x i8] zeroinitializer }>, align 8
@_ZTV1A = external dso_local unnamed_addr constant { [3 x i8*] }, align 8
@llvm.global_ctors = appending global [0 x { i32, void ()*, i8* }] zeroinitializer

; Function Attrs: nofree nosync nounwind readnone uwtable willreturn mustprogress
define dso_local i32 @_Z8hahahahav() local_unnamed_addr #0 {
entry:
  %0 = tail call i8* @llvm.strip.invariant.group.p0i8(i8* bitcast (%struct.A* @_ZL1g to i8*))
  %i = getelementptr inbounds i8, i8* %0, i64 8
  %1 = bitcast i8* %i to i32*
  %2 = load i32, i32* %1, align 8, !tbaa !6
  ret i32 %2
}

$ ./build/rel/bin/clang++ /tmp/a.cc -o - -S -emit-llvm -O2

; Function Attrs: nofree norecurse nosync nounwind readnone uwtable willreturn mustprogress
define dso_local i32 @_Z8hahahahav() local_unnamed_addr #0 {
entry:
  ret i32 4
}

Nice finding!

[aeubanks]

rebase
add more tests
make operand constant construction not recursive
skip if load operand was initially constant

[Prazek]

llvm/lib/Analysis/InstructionSimplify.cpp

5871–5874

nit: personally I would reverse the logic:

if (II->getIntrinsicID() == Intrinsic::strip_invariant_group &&
    II->getIntrinsicID() == Intrinsic::launder_invariant_group)
  Worklist.push_back(II->getOperand(0));
else
  return nullptr;

I think it is more canonical and easier to read.
I guess also then you could simplify the assert you have later on to share some code (e.g. isInvariantGroupIntrinsic function)

[aeubanks]

use isLaunderOrStripInvariantGroup(), I forgot I had already made that

[aeubanks]

ping

[lebedev.ri]

LGTM

llvm/test/Transforms/InstSimplify/invariant.group-load.ll

2

Please precommit these tests.

[aeubanks]

rebase after precommitted test

[clin1]

Hi @aeubanks, we turned up a corner case where jump threading is creating a self-referential GEP:

%tmp27 = getelementptr inbounds i8, i8* %tmp27, i64 1

Surprisingly, this is allowed in unreachable code:
https://lists.llvm.org/pipermail/llvm-dev/2012-October/054719.html

The self reference causes InstSimplify to hang when it's called from JT.
Test case "reduced.ll" attached. Would you mind checking it out? Thank you!

reduced.ll4 KBDownload

[lebedev.ri]

In D101103#2808706, @clin1 wrote:

Hi @aeubanks, we turned up a corner case where jump threading is creating a self-referential GEP:

%tmp27 = getelementptr inbounds i8, i8* %tmp27, i64 1

Surprisingly, this is allowed in unreachable code:
https://lists.llvm.org/pipermail/llvm-dev/2012-October/054719.html

The self reference causes InstSimplify to hang when it's called from JT.
Test case "reduced.ll" attached. Would you mind checking it out? Thank you!

reduced.ll4 KBDownload

The fix should lie in jumpthreading - it should not deal with unreachable blocks.

[nikic]

While it may make sense to address this in JumpThreading in addition, I believe InstSimplify is intended to be robust against unreachable code. As InstSimplify can thread over phis, I don't think it's even possible for a caller to reliably prevent unreachable code from reaching InstSimplify.

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

5858–5859

Then i guess you want to add a SmallPtrSet<Value*> Visited; outside of the loop
insert into it in the beginning of the loop, and if insertion fails - return nullptr;.

[aeubanks]

check for self referential values

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyFreezeInst(Value *Op0, const SimplifyQuery &Q) {
   // We have room for improvement.
   return nullptr;
 }
 
 Value *llvm::SimplifyFreezeInst(Value *Op0, const SimplifyQuery &Q) {
   return ::SimplifyFreezeInst(Op0, Q);
 }
 
+static Constant *ConstructLoadOperandConstant(Value *Op) {
+  if (auto *C = dyn_cast<Constant>(Op))
+    return C;
+
+  if (auto *BC = dyn_cast<BitCastOperator>(Op)) {
+    if (auto *C = ConstructLoadOperandConstant(BC->getOperand(0))) {
+      return ConstantExpr::getBitCast(C, BC->getType());
+    }
+    return nullptr;
+  }
+  if (auto *GEP = dyn_cast<GEPOperator>(Op)) {
+    if (auto *C = ConstructLoadOperandConstant(GEP->getPointerOperand())) {
+      SmallVector<Constant *> Idxs;
+      for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I) {
+        if (auto *Idx = dyn_cast<Constant>(GEP->getOperand(I)))
+          Idxs.push_back(Idx);
+        else
+          return nullptr;
+      }
+      return ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), C,
+                                            Idxs, GEP->isInBounds(),
+                                            GEP->getInRangeIndex());
+    }
+    return nullptr;
+  }
+  if (auto *II = dyn_cast<IntrinsicInst>(Op)) {
+    if (II->getIntrinsicID() == Intrinsic::strip_invariant_group ||
+        II->getIntrinsicID() == Intrinsic::launder_invariant_group) {
+      if (auto *C = ConstructLoadOperandConstant(II->getOperand(0))) {
+        return ConstantExpr::getBitCast(C, II->getType());
+      }
+    }
+    return nullptr;
+  }
+  return nullptr;
+}
+
+static Value *SimplifyLoadInst(LoadInst *LI, const SimplifyQuery &Q) {
+  if (auto *C = dyn_cast<Constant>(LI->getPointerOperand()))
+    return ConstantFoldLoadFromConstPtr(C, LI->getType(), Q.DL);
+
+  if (auto *C = dyn_cast_or_null<Constant>(
+          ConstructLoadOperandConstant(LI->getPointerOperand())))
+    return ConstantFoldLoadFromConstPtr(C, LI->getType(), Q.DL);
+
+  return nullptr;
+}
+
 /// See if we can compute a simplified version of this instruction.
 /// If not, this returns null.
 
 Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ,
                                  OptimizationRemarkEmitter *ORE) {
   const SimplifyQuery Q = SQ.CxtI ? SQ : SQ.getWithInstruction(I);
   Value *Result;
 

 #undef HANDLE_CAST_INST
     Result =
         SimplifyCastInst(I->getOpcode(), I->getOperand(0), I->getType(), Q);
     break;
   case Instruction::Alloca:
     // No simplifications for Alloca and it can't be constant folded.
     Result = nullptr;
     break;
+  case Instruction::Load:
+    Result = SimplifyLoadInst(cast<LoadInst>(I), Q);
+    break;
   }
 
   /// If called on unreachable code, the above logic may report that the
   /// instruction simplified to itself.  Make life easier for users by
   /// detecting that case here, returning a safe value instead.
   return Result == I ? UndefValue::get(I->getType()) : Result;
 }
 

llvm/test/Transforms/InstSimplify/invariant.group-load.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=instsimplify -S < %s | FileCheck %s
+
+@A = linkonce_odr hidden constant { i64, i64 } { i64 2, i64 3 }
+
+declare i8* @llvm.strip.invariant.group.p0i8(i8* %p)
+
+define i64 @f() {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:    ret i64 3
+;
+  %p = bitcast { i64, i64 }* @A to i8*
+  %a = call i8* @llvm.strip.invariant.group.p0i8(i8* %p)
+  %b = getelementptr i8, i8* %a, i32 8
+  %c = bitcast i8* %b to i64*
+  %d = load i64, i64* %c
+  ret i64 %d
+}