[FuncAttr] Incorrect norecurse inference in both PostOrderFunctionAttrsPass and ReversePostOrderFunctionAttrsPass

[usha1830]

While working on improving the norecurse attribute inference in #139943, we came across a couple of cases of incorrect inference in PO and RPO FunctionAttr pass.

As per my understanding, both of these cases are not possible to reach through compiler analysis/transformations unless forced using
-mllvm -force-attribute=<fname>:norecurse

1. https://godbolt.org/z/cMxYE8qaW

define dso_local void @norecurse_fn() norecurse {
entry:
  tail call fastcc void @a(i32 0)
  ret void
}

define internal fastcc void @a(i32 range(i32 0, 2) %c) {
entry:
  %tobool.not = icmp eq i32 %c, 0
  br i1 %tobool.not, label %if.end, label %if.then

if.then:                                          ; preds = %entry
  tail call void @calls_norecurse()
  br label %if.end

if.end:                                           ; preds = %if.then, %entry
  ret void
}

define dso_local noundef i32 @main() norecurse {
entry:
  tail call fastcc void @foo()
  ret i32 1
}

define internal fastcc void @foo() {
entry:
  tail call void @norecurse_fn()
  tail call fastcc void @a(i32 1)
  ret void
}

declare void @calls_norecurse()

ReversePostOrderPass adds the norecurse attribute to function a, even when there is a possible recursion as a -> calls_norecurse (external function without definition) -> norecurse_fn -> a

This issue occurs because RPO norecurse attribute inference solely work based on the fact that all callers of function being examined are marked norecurse, which happens to be true when walking in top-down manner.

In this case, the norecurse attribute on norecurse_fn is not correct as it is not an internal function and can be called from external function which may introduce some indirect recursion.

2. https://godbolt.org/z/WcTvdTaa1

define void @a(i32 %c) {
  %tobool.not = icmp ne i32 %c, 0
  br i1 %tobool.not, label %if.then, label %if.end

if.then:
  call void @calls_b()
  br label %if.end

if.end:
  ret void
}

declare void @calls_b() norecurse

;define void @b() norecurse {
;  call void @a(i32 0)
;  ret void
;}

In this case, PostOrderFunctionAttrsPass infers norecurse on a which is incorrect. It relies on the fact that if all callees are norecurse, the caller is also norecurse.

Here as well, the norecurse attribute on calls_b is incorrect as its definition is not known.

CC: @nikic @david-arm

[usha1830]

Since the definition of the norecurse attribute changed in #157087, the example scenarios in this issue are no longer valid under the new definition.

Do we still want to update the Postorder and ReversePostOrder function attribute inference passes to handle these cases?

From what I can see, the only way to make this work would be to walk the entire call graph during norecurse inference (similar to the approach discussed here: #139943 (comment)
).

I’d like to hear your thoughts—should we fix this, and if so, do you have any other ideas on how to approach it?"

[nikic]

I believe that with #157087 there is nothing more to do here. Under the new definition, the inference is correct.