[GVN] Encode GEPs in offset representation

[nikic]

Summary

When using opaque pointers, convert GEPs into offset representation of the form P + V1 * Scale1 + V2 * Scale2 + ... + ConstantOffset. This allows us to recognize equivalent address calculations even if the GEPs don't use the same source element type.

This fixes an opaque pointer codegen regression seen in rustc.

[aeubanks]

llvm/lib/Transforms/Scalar/GVN.cpp

408

why don't we do this for typed pointers as well?

[aeubanks]

but lg anyway

[nikic]

llvm/lib/Transforms/Scalar/GVN.cpp

408

For typed pointers the source element type is implicitly encoded as part of the pointer operand, so this wouldn't do anything useful. To make this work with typed pointers, we'd have to change GVN to work on stripped pointers and then insert bitcasts as necessary during replacement.

llvm/include/llvm/Transforms/Scalar/GVN.h

 class AssumeInst;
 class AssumptionCache;
 class BasicBlock;
 class BranchInst;
 class CallInst;
 class ExtractValueInst;
 class Function;
 class FunctionPass;
+class GetElementPtrInst;
 class ImplicitControlFlowTracking;
 class LoadInst;
 class LoopInfo;
 class MemDepResult;
 class MemoryDependenceResults;
 class MemorySSA;
 class MemorySSAUpdater;
 class NonLocalDepResult;
class ValueTable {
     DominatorTree *DT = nullptr;
 
     uint32_t nextValueNumber = 1;
 
     Expression createExpr(Instruction *I);
     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
                              Value *LHS, Value *RHS);
     Expression createExtractvalueExpr(ExtractValueInst *EI);
+    Expression createGEPExpr(GetElementPtrInst *GEP);
     uint32_t lookupOrAddCall(CallInst *C);
     uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
                               uint32_t Num, GVNPass &Gvn);
     bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
                           const BasicBlock *PhiBlock, GVNPass &Gvn);
     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn);
 

llvm/lib/Transforms/Scalar/GVN.cpp

 };
 
 //===----------------------------------------------------------------------===//
 //                     ValueTable Internal Functions
 //===----------------------------------------------------------------------===//
 
 GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) {
   Expression e;
-  // For GEPs, disambiguate based on the source element type, which is not
-  // implied by the result type with opaque pointers. (Conversely, the source
-  // element type together with the operand types does imply the result type.)
-  if (const auto *GEP = dyn_cast<GetElementPtrInst>(I))
-    e.type = GEP->getSourceElementType();
-  else
-    e.type = I->getType();
   e.opcode = I->getOpcode();
   if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(I)) {
     // gc.relocate is 'special' call: its second and third operands are
     // not real values, but indices into statepoint's argument list.
     // Use the refered to values for purposes of identity.
     e.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
     e.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
     e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) {
   for (Use &Op : EI->operands())
     e.varargs.push_back(lookupOrAdd(Op));
 
   append_range(e.varargs, EI->indices());
 
   return e;
 }
 
+GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) {
+  Expression E;
+  Type *PtrTy = GEP->getType()->getScalarType();
+  const DataLayout &DL = GEP->getModule()->getDataLayout();
+  unsigned BitWidth = DL.getIndexTypeSizeInBits(PtrTy);
+  MapVector<Value *, APInt> VariableOffsets;
+  APInt ConstantOffset(BitWidth, 0);
+  if (PtrTy->isOpaquePointerTy() &&
+      GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) {
+    // For opaque pointers, convert into offset representation, to recognize
+    // equivalent address calculations that use different type encoding.
+    LLVMContext &Context = GEP->getContext();
+    E.opcode = GEP->getOpcode();
+    E.type = nullptr;
+    E.varargs.push_back(lookupOrAdd(GEP->getPointerOperand()));
+    for (const auto &Pair : VariableOffsets) {
+      E.varargs.push_back(lookupOrAdd(Pair.first));
+      E.varargs.push_back(lookupOrAdd(ConstantInt::get(Context, Pair.second)));
+    }
+    if (!ConstantOffset.isZero())
+      E.varargs.push_back(
+          lookupOrAdd(ConstantInt::get(Context, ConstantOffset)));
+  } else {
+    // If converting to offset representation fails (for typed pointers and
+    // scalable vectors), fall back to type-based implementation:
+    E.opcode = GEP->getOpcode();
+    E.type = GEP->getSourceElementType();
+    for (Use &Op : GEP->operands())
+      E.varargs.push_back(lookupOrAdd(Op));
+  }
+  return E;
+}
+
 //===----------------------------------------------------------------------===//
 //                     ValueTable External Functions
 //===----------------------------------------------------------------------===//
 
 GVNPass::ValueTable::ValueTable() = default;
 GVNPass::ValueTable::ValueTable(const ValueTable &) = default;
 GVNPass::ValueTable::ValueTable(ValueTable &&) = default;
 GVNPass::ValueTable::~ValueTable() = default;
switch (I->getOpcode()) {
     case Instruction::AddrSpaceCast:
     case Instruction::BitCast:
     case Instruction::Select:
     case Instruction::Freeze:
     case Instruction::ExtractElement:
     case Instruction::InsertElement:
     case Instruction::ShuffleVector:
     case Instruction::InsertValue:
-    case Instruction::GetElementPtr:
       exp = createExpr(I);
       break;
+    case Instruction::GetElementPtr:
+      exp = createGEPExpr(cast<GetElementPtrInst>(I));
+      break;
     case Instruction::ExtractValue:
       exp = createExtractvalueExpr(cast<ExtractValueInst>(I));
       break;
     case Instruction::PHI:
       valueNumbering[V] = nextValueNumber;
       NumberingPhi[nextValueNumber] = cast<PHINode>(V);
       return nextValueNumber++;
     default:

llvm/test/Transforms/GVN/opaque-ptr.ll

;
   call void @use(ptr %gep2)
   call void @use(ptr %gep3)
   ret void
 }
 
 define void @gep_cse_offset_canonicalization(ptr %p, i64 %idx, i64 %idx2) {
 ; CHECK-LABEL: @gep_cse_offset_canonicalization(
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr i64, ptr [[P:%.*]], i64 1
-; CHECK-NEXT:    [[GEP1_SAME1:%.*]] = getelementptr i32, ptr [[P]], i64 2
-; CHECK-NEXT:    [[GEP1_SAME2:%.*]] = getelementptr i8, ptr [[P]], i64 8
 ; CHECK-NEXT:    [[GEP1_DIFFERENT:%.*]] = getelementptr i8, ptr [[P]], i64 12
 ; CHECK-NEXT:    call void @use(ptr [[GEP1]])
-; CHECK-NEXT:    call void @use(ptr [[GEP1_SAME1]])
-; CHECK-NEXT:    call void @use(ptr [[GEP1_SAME2]])
+; CHECK-NEXT:    call void @use(ptr [[GEP1]])
+; CHECK-NEXT:    call void @use(ptr [[GEP1]])
 ; CHECK-NEXT:    call void @use(ptr [[GEP1_DIFFERENT]])
 ; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr i64, ptr [[P]], i64 [[IDX:%.*]]
-; CHECK-NEXT:    [[GEP2_SAME:%.*]] = getelementptr { i32, i32 }, ptr [[P]], i64 [[IDX]]
 ; CHECK-NEXT:    [[GEP2_DIFFERENT:%.*]] = getelementptr { i32, i32, i32 }, ptr [[P]], i64 [[IDX]]
 ; CHECK-NEXT:    call void @use(ptr [[GEP2]])
-; CHECK-NEXT:    call void @use(ptr [[GEP2_SAME]])
+; CHECK-NEXT:    call void @use(ptr [[GEP2]])
 ; CHECK-NEXT:    call void @use(ptr [[GEP2_DIFFERENT]])
 ; CHECK-NEXT:    [[GEP3:%.*]] = getelementptr { [0 x i32], [0 x i32] }, ptr [[P]], i64 0, i32 0, i64 [[IDX]]
-; CHECK-NEXT:    [[GEP3_SAME1:%.*]] = getelementptr { [0 x i32], [0 x i32] }, ptr [[P]], i64 0, i32 1, i64 [[IDX]]
-; CHECK-NEXT:    [[GEP3_SAME2:%.*]] = getelementptr { [0 x i32], [0 x i32] }, ptr [[P]], i64 1, i32 0, i64 [[IDX]]
 ; CHECK-NEXT:    [[GEP3_DIFFERENT:%.*]] = getelementptr { [0 x i32], [0 x i32] }, ptr [[P]], i64 0, i32 0, i64 [[IDX2:%.*]]
 ; CHECK-NEXT:    call void @use(ptr [[GEP3]])
-; CHECK-NEXT:    call void @use(ptr [[GEP3_SAME1]])
-; CHECK-NEXT:    call void @use(ptr [[GEP3_SAME2]])
+; CHECK-NEXT:    call void @use(ptr [[GEP3]])
+; CHECK-NEXT:    call void @use(ptr [[GEP3]])
 ; CHECK-NEXT:    call void @use(ptr [[GEP3_DIFFERENT]])
 ; CHECK-NEXT:    [[GEP4:%.*]] = getelementptr [4 x i32], ptr [[P]], i64 [[IDX]], i64 [[IDX2]]
-; CHECK-NEXT:    [[GEP4_SAME:%.*]] = getelementptr [4 x float], ptr [[P]], i64 [[IDX]], i64 [[IDX2]]
 ; CHECK-NEXT:    [[GEP4_DIFFERENT:%.*]] = getelementptr [4 x float], ptr [[P]], i64 [[IDX2]], i64 [[IDX]]
 ; CHECK-NEXT:    call void @use(ptr [[GEP4]])
-; CHECK-NEXT:    call void @use(ptr [[GEP4_SAME]])
+; CHECK-NEXT:    call void @use(ptr [[GEP4]])
 ; CHECK-NEXT:    call void @use(ptr [[GEP4_DIFFERENT]])
 ; CHECK-NEXT:    [[GEP5:%.*]] = getelementptr <vscale x 2 x i32>, ptr [[P]], i64 1
 ; CHECK-NEXT:    [[GEP5_SAME:%.*]] = getelementptr <vscale x 2 x float>, ptr [[P]], i64 1
 ; CHECK-NEXT:    [[GEP5_DIFFERENT:%.*]] = getelementptr <vscale x 2 x i64>, ptr [[P]], i64 1
 ; CHECK-NEXT:    call void @use(ptr [[GEP5]])
 ; CHECK-NEXT:    call void @use(ptr [[GEP5_SAME]])
 ; CHECK-NEXT:    call void @use(ptr [[GEP5_DIFFERENT]])
 ; CHECK-NEXT:    ret void
;
   call void @use(ptr %gep3.same2)
   call void @use(ptr %gep3.different)
   %gep4 = getelementptr [4 x i32], ptr %p, i64 %idx, i64 %idx2
   %gep4.same = getelementptr [4 x float], ptr %p, i64 %idx, i64 %idx2
   %gep4.different = getelementptr [4 x float], ptr %p, i64 %idx2, i64 %idx
   call void @use(ptr %gep4)
   call void @use(ptr %gep4.same)
   call void @use(ptr %gep4.different)
+  ; TODO: %gep5 and %gep5.same are equivalent as well.
   %gep5 = getelementptr <vscale x 2 x i32>, ptr %p, i64 1
   %gep5.same = getelementptr <vscale x 2 x float>, ptr %p, i64 1
   %gep5.different = getelementptr <vscale x 2 x i64>, ptr %p, i64 1
   call void @use(ptr %gep5)
   call void @use(ptr %gep5.same)
   call void @use(ptr %gep5.different)
   ret void
 }