Missed optimization of empty `for` loop function into just `ret`

[Rageking8]

#include <unordered_map>

void foo(std::unordered_map<int, int> umap)
{
    for (const auto& i : umap) {}
}

foo(std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, std::allocator<std::pair<int const, int> > >): # @foo(std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, std::allocator<std::pair<int const, int> > >)
        add     rdi, 16
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        mov     rdi, qword ptr [rdi]
        test    rdi, rdi
        jne     .LBB0_1
        ret

https://godbolt.org/z/cdavsPGq5

Tested on x86-64 clang (trunk), the above function get fully optimized to just ret on gcc (trunk).

[nikic]

For some reason the optimized function is missing the mustprogress attribute, which is required for this optimization.

[antoniofrighetto]

@nikic, why is mustprogress required? Shouldn't the code be DCE'd regardless of the attribute?

[nikic]

@antoniofrighetto Without mustprogress the loop could be infinite and we would be required to preserve the divergence effect.

[antoniofrighetto]

@nikic, seems like we lose mustprogress when Inliner executes via mergeAttributesForInlining, due to 46a29e9. setAND for mustprogress looks too conservative to me, and it seems to lead to suboptimal optimizations. Shouldn't we want something like setSubset (a set containment-like behaviour)? I think the caller should continue retain mustprogress despite a callee being inlined – and the transitive closure of such a callee – having the attribute or not (cc/ @jdoerfert).

[nikic]

Where does the non-mustprogress function being inlined come from here?

I'm a bit unsure on the inlining semantics of mustprogress. I can definitely see the argument that if the caller is mustprogress, then any calls from that code must be as well. But I think this may not be desirable for FFI between C++ and other languages.

I believe one could build a coherent model where calling a non-mustprogress function from a mustprogress function counts as progress -- the current inlining implementation seems to operate under such a model.

[antoniofrighetto]

@nikic, I might be wrong, but the current inlining implementation seems to compute the logical AND of the attributes of the caller and the callee for attribute mustprogress, which does not really look semantic-preserving here. This is carried out in:

llvm-project/llvm/lib/Transforms/Utils/InlineFunction.cpp

Lines 2776 to 2777 in 888742a

	if (MergeAttributes)
	AttributeFuncs::mergeAttributesForInlining(*Caller, *CalledFunc);

Which in turns calls table-gen'd mergeFnAttrs:

llvm-project/llvm/utils/TableGen/Attributes.cpp

Line 99 in 888742a

OS << "static inline void mergeFnAttrs(Function &Caller,\n"

The merge rule is setAND (per commit above).

Prior to being inlined, function foo looks as follows:

; Function Attrs: mustprogress nounwind uwtable
define dso_local void @_Z3fooSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE(ptr noundef %umap) local_unnamed_addr #0 {
entry:
  %__begin1 = alloca %"struct.std::__detail::_Node_iterator", align 8
  %__end1 = alloca %"struct.std::__detail::_Node_iterator", align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %__begin1) #3
  %call = call ptr @_ZNSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE5beginEv(ptr noundef nonnull align 8 dereferenceable(56) %umap) #3
  store ptr %call, ptr %__begin1, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %__end1) #3
  %call2 = call ptr @_ZNSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE3endEv(ptr noundef nonnull align 8 dereferenceable(56) %umap) #3
  store ptr %call2, ptr %__end1, align 8
  br label %for.cond

for.cond:                                         ; preds = %for.body, %entry
  %call5 = call noundef zeroext i1 @_ZNSt8__detailneERKNS_19_Node_iterator_baseISt4pairIKiiELb0EEES6_(ptr noundef nonnull align 8 dereferenceable(8) %__begin1, ptr noundef nonnull align 8 dereferenceable(8) %__end1) #3
  br i1 %call5, label %for.body, label %for.cond.cleanup

for.cond.cleanup:                                 ; preds = %for.cond
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %__end1) #3
  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %__begin1) #3
  ret void

for.body:                                         ; preds = %for.cond
  %call6 = call noundef nonnull align 4 dereferenceable(8) ptr @_ZNKSt8__detail14_Node_iteratorISt4pairIKiiELb0ELb0EEdeEv(ptr noundef nonnull align 8 dereferenceable(8) %__begin1) #3
  %call7 = call noundef nonnull align 8 dereferenceable(8) ptr @_ZNSt8__detail14_Node_iteratorISt4pairIKiiELb0ELb0EEppEv(ptr noundef nonnull align 8 dereferenceable(8) %__begin1) #3
  br label %for.cond, !llvm.loop !5
}

The callee _ZNSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE5beginEv gets inlined, and being a non-must-progress function, the inlining leads to the following function:

; Function Attrs: nounwind uwtable
define dso_local void @_Z3fooSt13unordered_mapIiiSt4hashIiESt8equal_toIiESaISt4pairIKiiEEE(ptr noundef %umap) local_unnamed_addr #0 personality ptr @__gxx_personality_v0 {
entry:
  %__begin1 = alloca %"struct.std::__detail::_Node_iterator", align 8
  %__end1 = alloca %"struct.std::__detail::_Node_iterator", align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %__begin1) #3
  %_M_before_begin.i.i.i = getelementptr inbounds %"class.std::_Hashtable", ptr %umap, i64 0, i32 2
  %0 = load ptr, ptr %_M_before_begin.i.i.i, align 8, !tbaa !5
  store ptr %0, ptr %__begin1, align 8
  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %__end1) #3
  ; ...
  ; Same as above
  ; ...
}

[antoniofrighetto]

A bit sketchy, but for mustprogress we could have something as follows:

/// This function preserves the caller's attribute if it is set, 
/// and does not change it based on the callee's attribute.
template<typename AttrClass>
static void retainCallerAttribute(Function &Caller, const Function &Callee) {
  // If the attribute is set on the caller, keep it.
  if (AttrClass::isSet(Caller, AttrClass::getKind())) {
    return;
  }
  
  // The callee's attributes do not influence the caller's attributes,
  // no further action.
}

[antoniofrighetto]

To be clear, std::unordered_map begin method originally had mustprogress too, but it seems that, one of its callee (std::_Hashtable<int, std::pair<int const, int>, std::allocator<std::pair<int const, int> >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::begin()) which happens to be inlined, does not (unoptimized IR):

define linkonce_odr dso_local ptr @std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, std::allocator<std::pair<int const, int> > >::begin()(ptr noundef nonnull align 8 dereferenceable(56) %0) #0 comdat align 2 {
  %2 = alloca %"struct.std::__detail::_Node_iterator", align 8
  %3 = alloca ptr, align 8
  store ptr %0, ptr %3, align 8
  %4 = load ptr, ptr %3, align 8
  %5 = getelementptr inbounds %"class.std::unordered_map", ptr %4, i32 0, i32 0
  %6 = call ptr @std::_Hashtable<int, std::pair<int const, int>, std::allocator<std::pair<int const, int> >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::begin()(ptr noundef nonnull align 8 dereferenceable(56) %5) #3
  %7 = getelementptr inbounds %"struct.std::__detail::_Node_iterator", ptr %2, i32 0, i32 0
  %8 = getelementptr inbounds %"struct.std::__detail::_Node_iterator_base", ptr %7, i32 0, i32 0
  store ptr %6, ptr %8, align 8
  %9 = getelementptr inbounds %"struct.std::__detail::_Node_iterator", ptr %2, i32 0, i32 0
  %10 = getelementptr inbounds %"struct.std::__detail::_Node_iterator_base", ptr %9, i32 0, i32 0
  %11 = load ptr, ptr %10, align 8
  ret ptr %11
}

attributes #0 = { mustprogress noinline nounwind optnone uwtable "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { noinline noreturn nounwind uwtable "frame-pointer"="all" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #2 = { noinline nounwind optnone uwtable "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { nounwind }
attributes #4 = { noreturn nounwind }

Hence, eventually, std::unordered_map begin loses mustprogress too. Perhaps we could add mustprogress to the missing C++ functions, but I'm still not convinced with the current model used by the Inliner.

[firewave]

related: #51036