(impala) branch master updated: IMPALA-11917: Codegen branch-free reads of nullable scalar slots

[mi...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

asf-gitbox-commits pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git


The following commit(s) were added to refs/heads/master by this push:
     new 893cf933b IMPALA-11917: Codegen branch-free reads of nullable scalar slots
893cf933b is described below

commit 893cf933b6880ab7dd30bc9f6b16eac71c92e8f5
Author: Michael Smith <mi...@cloudera.com>
AuthorDate: Thu Oct 1 11:35:35 2026 -0700

    IMPALA-11917: Codegen branch-free reads of nullable scalar slots
    
    After the LLVM 22 upgrade, TPC-DS Q99's streaming aggregation was ~20%
    slower than with LLVM 5. Its UpdateTuple compiled to 269 instructions
    with 22 branches (LLVM 5: 84 instructions, 5 branches).
    
    GetSlotRef wraps each slot read in a null-check diamond. Once several
    reads of the same slots are inlined into a single function, LLVM 22
    no longer merges these diamonds. Each read keeps its own branch and
    conditional load, and the packed *Val is rebuilt via shifts and cmovs.
    Replacing the phi with a select after the branch doesn't help, because
    InstCombine converts a select back into a phi when a dominating branch
    tests the same condition.
    
    When the tuple is not nullable and the slot is a nullable simple scalar
    (i.e. not string, timestamp, collection, struct or variant), GetSlotRef
    now loads the slot unconditionally and selects on the null bit. This
    is safe because the slot is always within the tuple's memory. With no
    branch on the null bit, LLVM combines the null checks and CSEs the
    loads across expressions, so UpdateTuple compiles to 88 instructions
    with 6 branches. 09:AGGREGATE STREAMING in Q99 drops from 39-41ms to
    32-33ms, matching LLVM 5.
    
    Codegen for other types didn't change as they showed no improvement.
    
    Testing:
    - Q99 results on tpcds20_parquet match with codegen enabled and
      disabled.
    - Ran tests/query_test/test_tpcds_queries.py.
    
    Change-Id: I6edaf90100cc3360a7c93d3218eb6956fcec24f0
    Assisted-by: Claude Opus 5.5 (GitHub Copilot)
    Reviewed-on: http://gerrit.cloudera.org:8080/24997
    Reviewed-by: Michael Smith <mi...@cloudera.com>
    Reviewed-by: Joe McDonnell <jo...@cloudera.com>
    Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
 be/src/codegen/codegen-anyval.cc | 25 ++++++++++++++++++++
 be/src/codegen/codegen-anyval.h  | 10 ++++++++
 be/src/exprs/slot-ref.cc         | 50 +++++++++++++++++++++++++++++++++++++++-
 be/src/exprs/slot-ref.h          |  6 +++++
 4 files changed, 90 insertions(+), 1 deletion(-)

diff --git a/be/src/codegen/codegen-anyval.cc b/be/src/codegen/codegen-anyval.cc
index 77e8cdf38..095a3910f 100644
--- a/be/src/codegen/codegen-anyval.cc
+++ b/be/src/codegen/codegen-anyval.cc
@@ -41,6 +41,23 @@ const char* CodegenAnyVal::LLVM_DECIMALVAL_NAME   = "struct.impala_udf::DecimalV
 const char* CodegenAnyVal::LLVM_DATEVAL_NAME      = "struct.impala_udf::DateVal";
 const char* CodegenAnyVal::LLVM_COLLECTIONVAL_NAME = "struct.impala_udf::CollectionVal";
 
+bool CodegenAnyVal::IsSimpleType(const ColumnType& type) {
+  switch (type.type) {
+    case TYPE_BOOLEAN:
+    case TYPE_TINYINT:
+    case TYPE_SMALLINT:
+    case TYPE_INT:
+    case TYPE_BIGINT:
+    case TYPE_FLOAT:
+    case TYPE_DOUBLE:
+    case TYPE_DECIMAL:
+    case TYPE_DATE:
+      return true;
+    default:
+      return false;
+  }
+}
+
 llvm::Type* CodegenAnyVal::GetLoweredType(LlvmCodeGen* cg, const ColumnType& type) {
   switch (type.type) {
     case TYPE_BOOLEAN: // i16
@@ -803,6 +820,14 @@ CodegenAnyVal CodegenAnyVal::GetNonNullVal(LlvmCodeGen* codegen, LlvmBuilder* bu
   return CodegenAnyVal(codegen, builder, type, value, name);
 }
 
+CodegenAnyVal CodegenAnyVal::GetNullableVal(LlvmCodeGen* codegen, LlvmBuilder* builder,
+    const ColumnType& type, llvm::Value* val, llvm::Value* is_null, const char* name) {
+  CodegenAnyVal result = GetNonNullVal(codegen, builder, type, name);
+  result.SetVal(val);
+  result.SetIsNull(is_null);
+  return result;
+}
+
 // Returns the last block generated so we can set it as a predecessor in PHI nodes.
 llvm::BasicBlock* CodegenAnyVal::CreateStructValFromReadWriteInfo(
     const CodegenAnyValReadWriteInfo& read_write_info,
diff --git a/be/src/codegen/codegen-anyval.h b/be/src/codegen/codegen-anyval.h
index 161222821..ce7690831 100644
--- a/be/src/codegen/codegen-anyval.h
+++ b/be/src/codegen/codegen-anyval.h
@@ -96,6 +96,10 @@ class CodegenAnyVal {
       const ColumnType& type, llvm::Function* fn, llvm::ArrayRef<llvm::Value*> args,
       const char* name = "");
 
+  /// Returns true if values of 'type' consist of a single scalar that can be read from a
+  /// slot with one load and set with SetVal(). Types default to false when not listed.
+  static bool IsSimpleType(const ColumnType& type);
+
   /// Returns the lowered AnyVal type associated with 'type'.
   /// E.g.: TYPE_BOOLEAN (which corresponds to a BooleanVal) => i16
   static llvm::Type* GetLoweredType(LlvmCodeGen* cg, const ColumnType& type);
@@ -120,6 +124,12 @@ class CodegenAnyVal {
   static CodegenAnyVal GetNonNullVal(LlvmCodeGen* codegen, LlvmBuilder* builder,
       const ColumnType& type, const char* name = "");
 
+  /// Return a *Val with value 'val' and null flag 'is_null'. 'type' must be a type that
+  /// supports SetVal().
+  static CodegenAnyVal GetNullableVal(LlvmCodeGen* codegen, LlvmBuilder* builder,
+      const ColumnType& type, llvm::Value* val, llvm::Value* is_null,
+      const char* name = "");
+
   /// Creates a wrapper around a lowered *Val value.
   //
   /// Instructions for manipulating the value are generated using 'builder'. The insert
diff --git a/be/src/exprs/slot-ref.cc b/be/src/exprs/slot-ref.cc
index 9c314bdcf..bc08440a8 100644
--- a/be/src/exprs/slot-ref.cc
+++ b/be/src/exprs/slot-ref.cc
@@ -222,7 +222,9 @@ Status SlotRef::GetCodegendComputeFnImpl(LlvmCodeGen* codegen, llvm::Function**
   llvm::Value* row_ptr = args[1];
 
   LlvmBuilder builder(codegen->context());
-  CodegenAnyVal result_value = CodegenValue(codegen, &builder, *fn, eval_ptr, row_ptr);
+  CodegenAnyVal result_value = CanCodegenBranchFree() ?
+      CodegenValueBranchFree(codegen, &builder, *fn, row_ptr) :
+      CodegenValue(codegen, &builder, *fn, eval_ptr, row_ptr);
   builder.CreateRet(result_value.GetLoweredValue());
 
   *fn = codegen->FinalizeFunction(*fn);
@@ -231,6 +233,52 @@ Status SlotRef::GetCodegendComputeFnImpl(LlvmCodeGen* codegen, llvm::Function**
   return Status::OK();
 }
 
+bool SlotRef::CanCodegenBranchFree() const {
+  // A null tuple pointer cannot be dereferenced, so nullable tuples need the branch.
+  if (tuple_is_nullable_ || null_indicator_offset_.bit_mask == 0) return false;
+  // Only types whose value is a single scalar load are supported; others have multiple
+  // components (ptr/len, date/time) or child slots.
+  return CodegenAnyVal::IsSimpleType(type_);
+}
+
+// Resulting IR for a nullable int slot in a non-nullable tuple:
+//
+// define i64 @GetSlotRef(ptr %eval, ptr %row) {
+// entry:
+//   %tuple_ptr_addr = getelementptr inbounds ptr, ptr %row, i32 0
+//   %tuple_ptr = load ptr, ptr %tuple_ptr_addr, align 8
+//   %null_byte_ptr = getelementptr inbounds i8, ptr %tuple_ptr, i32 20
+//   %null_byte = load i8, ptr %null_byte_ptr, align 1
+//   %null_mask = and i8 %null_byte, 2
+//   %is_null = icmp ne i8 %null_mask, 0
+//   %slot_addr = getelementptr inbounds i8, ptr %tuple_ptr, i32 4
+//   %val = load i32, ptr %slot_addr, align 4
+//   %val_or_zero = select i1 %is_null, i32 0, i32 %val
+//   ...
+//   ret i64 %result
+// }
+CodegenAnyVal SlotRef::CodegenValueBranchFree(LlvmCodeGen* codegen,
+    LlvmBuilder* builder, llvm::Function* fn, llvm::Value* row_ptr) {
+  DCHECK(CanCodegenBranchFree());
+  builder->SetInsertPoint(llvm::BasicBlock::Create(codegen->context(), "entry", fn));
+  llvm::Value* tuple_ptr_addr = builder->CreateInBoundsGEP(codegen->ptr_type(), row_ptr,
+      codegen->GetI32Constant(tuple_idx_), "tuple_ptr_addr");
+  llvm::Value* tuple_ptr =
+      builder->CreateLoad(codegen->ptr_type(), tuple_ptr_addr, "tuple_ptr");
+  llvm::Value* is_null = SlotDescriptor::CodegenIsNull(
+      codegen, builder, null_indicator_offset_, tuple_ptr);
+  // The slot is always part of the tuple's memory, so reading it is safe even if null.
+  llvm::Value* slot_ptr = builder->CreateInBoundsGEP(codegen->i8_type(), tuple_ptr,
+      codegen->GetI32Constant(slot_offset_), "slot_addr");
+  llvm::Value* val =
+      builder->CreateAnyValLoad(codegen->GetSlotType(type_), slot_ptr, type_, "val");
+  llvm::Value* val_or_zero = builder->CreateSelect(
+      is_null, llvm::Constant::getNullValue(val->getType()), val, "val_or_zero");
+
+  return CodegenAnyVal::GetNullableVal(
+      codegen, builder, type_, val_or_zero, is_null, "result");
+}
+
 // Generates null checking code: null checking may be generated for the tuple and for the
 // slot based on 'tuple_is_nullable' and 'slot_is_nullable'. If any one of the checks
 // returns null, control is transferred to 'next_block_if_null', otherwise to
diff --git a/be/src/exprs/slot-ref.h b/be/src/exprs/slot-ref.h
index 33f2cd7bb..50fdbebf9 100644
--- a/be/src/exprs/slot-ref.h
+++ b/be/src/exprs/slot-ref.h
@@ -90,6 +90,12 @@ class SlotRef : public ScalarExpr {
   CodegenAnyVal CodegenValue(LlvmCodeGen* codegen, LlvmBuilder* builder,
       llvm::Function* fn, llvm::Value* eval_ptr, llvm::Value* row_ptr,
       llvm::BasicBlock* entry_block = nullptr);
+  /// Returns true if CodegenValueBranchFree() can be used for this slot.
+  bool CanCodegenBranchFree() const;
+  /// Reads the slot unconditionally and selects on the null bit, avoiding the
+  /// null-check diamond that LLVM fails to merge once several reads are inlined.
+  CodegenAnyVal CodegenValueBranchFree(LlvmCodeGen* codegen, LlvmBuilder* builder,
+      llvm::Function* fn, llvm::Value* row_ptr);
   void CodegenNullChecking(LlvmCodeGen* codegen, LlvmBuilder* builder, llvm::Function* fn,
       llvm::BasicBlock* next_block_if_null, llvm::BasicBlock* next_block_if_not_null,
       llvm::Value* tuple_ptr);