Support phi operand in __builtin_object_size folder

[serge-sans-paille]

Summary

The implementation is just a generalization of the Select handler.
We're no trying to be smart and compute any kind of fixed point.

[nikic]

llvm/lib/Analysis/MemoryBuiltins.cpp

815–816

Comment can be dropped.

838

Support for Exact mode?

It might be worthwhile to phrase this in terms of combine(SizeOffsetType, SizeOffsetType, EvalMode) -> SizeOffsetType and reuse that between the Select and the PHINode handling.

llvm/test/Transforms/InstCombine/builtin-object-size-phi.ll

1 ↗

(On Diff #416120)

This should run -instcombine only.

[serge-sans-paille]

Take nikic's comments into account

[serge-sans-paille]

nits

[nikic]

LGTM

llvm/lib/Analysis/MemoryBuiltins.cpp

823

Just as a note, because this is pre-existing behavior of the select code: I find it somewhat odd that we just check for the smaller/larger Size-Offset here, but return the full (Size, Offset) pair. So the Exact/Min/Max only applies to the Size-Offset value, while the Size or Offset values individual might not be Exact/Min/Max. Looking at how this is used, it probably doesn't matter in the end, but it looks a bit suspicious.

828

Needs a default llvm_unreachable to suppress warning (at least with GCC).

llvm/test/Transforms/InstCombine/builtin-object-size-phi.ll

1 ↗

(On Diff #416120)

Okay, this was seriously confusing... The fold did not happen without -instcombine, even though -instcombine had no effect on the IR.

The reason is that InstCombine required TLI, and then LowerConstantIntrinsics had an optional TLI dependency, so the no-op InstCombine had an effect.

I've fixed this in https://github.com/llvm/llvm-project/commit/ab2284a6437bff8ba14d21cd6f9da927351dc17a by making TLI non-optional.

You should be able to just use -lower-constant-intrinsics now, and move this to the LowerConstantIntrinsics directory.

llvm/include/llvm/Analysis/MemoryBuiltins.h

public:
   SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
   SizeOffsetType visitLoadInst(LoadInst &I);
   SizeOffsetType visitPHINode(PHINode&);
   SizeOffsetType visitSelectInst(SelectInst &I);
   SizeOffsetType visitUndefValue(UndefValue&);
   SizeOffsetType visitInstruction(Instruction &I);
 
 private:
+  SizeOffsetType combineSizeOffset(SizeOffsetType LHS, SizeOffsetType RHS);
   SizeOffsetType computeImpl(Value *V);
   bool CheckedZextOrTrunc(APInt &I);
 };
 
 using SizeOffsetEvalType = std::pair<Value *, Value *>;
 
 /// Evaluate the size and offset of an object pointed to by a Value*.
 /// May create code to compute the result at run-time.

llvm/lib/Analysis/MemoryBuiltins.cpp

 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <cstdint>
 #include <iterator>
+#include <numeric>
 #include <type_traits>
 #include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "memory-builtins"
 
 enum AllocType : uint8_t {
SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) {
   // clueless
   return unknown();
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) {
   ++ObjectVisitorLoad;
   return unknown();
 }
 
-SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) {
-  // too complex to analyze statically.
-  return unknown();
+SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS,
+                                                          SizeOffsetType RHS) {
+  if (!bothKnown(LHS) || !bothKnown(RHS))
+    return unknown();
+
+  switch (Options.EvalMode) {
+  case ObjectSizeOpts::Mode::Min:
+    return (getSizeWithOverflow(LHS).slt(getSizeWithOverflow(RHS))) ? LHS : RHS;
+  case ObjectSizeOpts::Mode::Max:
+    return (getSizeWithOverflow(LHS).sgt(getSizeWithOverflow(RHS))) ? LHS : RHS;
+  case ObjectSizeOpts::Mode::Exact:
+    return (getSizeWithOverflow(LHS).eq(getSizeWithOverflow(RHS))) ? LHS
+                                                                   : unknown();
+  }
+  llvm_unreachable("missing an eval mode");
+}
+
+SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode &PN) {
+  auto IncomingValues = PN.incoming_values();
+  return std::accumulate(IncomingValues.begin() + 1, IncomingValues.end(),
+                         compute(*IncomingValues.begin()),
+                         [this](SizeOffsetType LHS, Value *VRHS) {
+                           return combineSizeOffset(LHS, compute(VRHS));
+                         });
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
-  SizeOffsetType TrueSide  = compute(I.getTrueValue());
-  SizeOffsetType FalseSide = compute(I.getFalseValue());
-  if (bothKnown(TrueSide) && bothKnown(FalseSide)) {
-    if (TrueSide == FalseSide) {
-        return TrueSide;
-    }
-
-    APInt TrueResult = getSizeWithOverflow(TrueSide);
-    APInt FalseResult = getSizeWithOverflow(FalseSide);
-
-    if (TrueResult == FalseResult) {
-      return TrueSide;
-    }
-    if (Options.EvalMode == ObjectSizeOpts::Mode::Min) {
-      if (TrueResult.slt(FalseResult))
-        return TrueSide;
-      return FalseSide;
-    }
-    if (Options.EvalMode == ObjectSizeOpts::Mode::Max) {
-      if (TrueResult.sgt(FalseResult))
-        return TrueSide;
-      return FalseSide;
-    }
-  }
-  return unknown();
+  return combineSizeOffset(compute(I.getTrueValue()),
+                           compute(I.getFalseValue()));
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) {
   return std::make_pair(Zero, Zero);
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
   LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I

llvm/test/Transforms/LowerConstantIntrinsics/builtin-object-size-phi.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -lower-constant-intrinsics  -S < %s | FileCheck %s
+
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare dso_local noalias noundef i8* @malloc(i64 noundef) local_unnamed_addr
+declare i64 @llvm.objectsize.i64.p0i8(i8*, i1 immarg, i1 immarg, i1 immarg)
+
+@buffer = dso_local global [4 x i8] zeroinitializer, align 1
+
+define dso_local i64 @pick_max(i32 noundef %n) local_unnamed_addr {
+; CHECK-LABEL: @pick_max(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[COND]], label [[IF_ELSE:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[MALLOCED:%.*]] = call noalias dereferenceable_or_null(8) i8* @malloc(i64 noundef 8)
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[MALLOCED]], [[IF_ELSE]] ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @buffer, i64 0, i64 0), [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i64 8
+;
+entry:
+  %cond = icmp eq i32 %n, 0
+  br i1 %cond, label %if.else, label %if.end
+
+if.else:
+  %malloced = call noalias dereferenceable_or_null(8) i8* @malloc(i64 noundef 8)
+  br label %if.end
+
+if.end:
+  %p = phi i8* [ %malloced, %if.else ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @buffer, i64 0, i64 0), %entry ]
+  %size = call i64 @llvm.objectsize.i64.p0i8(i8* %p, i1 false, i1 true, i1 false)
+  ret i64 %size
+}
+
+define dso_local i64 @pick_min(i32 noundef %n) local_unnamed_addr {
+; CHECK-LABEL: @pick_min(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[COND]], label [[IF_ELSE:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[MALLOCED:%.*]] = call noalias dereferenceable_or_null(8) i8* @malloc(i64 noundef 8)
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[MALLOCED]], [[IF_ELSE]] ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @buffer, i64 0, i64 0), [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i64 4
+;
+entry:
+  %cond = icmp eq i32 %n, 0
+  br i1 %cond, label %if.else, label %if.end
+
+if.else:
+  %malloced = call noalias dereferenceable_or_null(8) i8* @malloc(i64 noundef 8)
+  br label %if.end
+
+if.end:
+  %p = phi i8* [ %malloced, %if.else ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @buffer, i64 0, i64 0), %entry ]
+  %size = call i64 @llvm.objectsize.i64.p0i8(i8* %p, i1 true, i1 true, i1 false)
+  ret i64 %size
+}