Is every intrinsic norecurse?

Hi folks,
I’ve been measuring some devirtualization statistics and I found that when barriers are introduced, the number of functions marked as norecurse is lower.
The llvm.group.barrier is obviously norecursive and I’ve been thinking: is every intrinsic norecurse?

I think it make sense to mark all of the intrinsics that can be considered as norecursive this way, so it won’t gonna stop the optimizer marking functions as norecurse.

Best
Piotr

To bring some statistics:

Number of functions marked as norecurse:
name before after delta%
LLVM normal 1252902 1400128 10.52%
LLVM devirtualization 1231893 1400129 12.02%
ChakraCore normal 181366 257878 29.67%
ChakraCore with devirtualization 164891 257893 36.06%

where:
normal is Release build,
devirtualization is Relase + -fstrict-vtable-pointers
before is what it is right now
after is how it is after marking every intrinsic with norecurse

As you can see we could mark from 10-40% more functions as norecurse if all of the intrinsics would be marked norecurse.
Let’s look at other numbers to see if it actually helps in optimizations:

Number of global variables removed

name before after delta%
LLVM normal 932 1344 30.65%
LLVM devirtualization 1206 1621 25.6%
ChakraCore normal 1060 1060 0%
ChakraCore devirtualization 1072 1072 0%

For ChakraCore it didn’t all statistics besides # of functions marked as norecurse didn’t change.

Hi folks,
I've been measuring some devirtualization statistics and I found that when barriers are introduced, the number of functions marked as norecurse is lower.
The llvm.group.barrier is obviously norecursive and I've been thinking: is every intrinsic norecurse?

I think it make sense to mark all of the intrinsics that can be considered as norecursive this way, so it won't gonna stop the optimizer marking functions as norecurse.

I'm not sure that it is a universal property of all intrinsics, strictly speaking. patchpoints, for example, might recurse? It is certainly true for most of them.

  -Hal

Yes, patchpoints and statepoints may recurse. For instance

void f() {
  llvm.patchpoint(&f);
}

has "mutual recursion" between the patchpoint intrinsic and f.

-- Sanjoy

Oh right, here is a patch: https://reviews.llvm.org/D33889. I hope it will get through because I spent much time fixing all of the tests :slight_smile:

Piotr

(adding back llvm-dev)

Hi David,The patch didn’t get a lot of attention, so probably others does not consider it a huge deal. Anyway, if someone is willing to review this, I can pursue rebasing it.

Piotr

From: piotrekpad@gmail.com [mailto:piotrekpad@gmail.com] On Behalf Of Piotr Padlewski
Sent: den 16 oktober 2017 17:33

Hi David,
The patch didn't get a lot of attention, so probably others does not
consider it a huge deal. Anyway, if someone is willing to review this, I
can pursue rebasing it.

Okay. We are interested in getting something akin to your patch delivered; at
least so that the dbg intrinsics gets marked as norecurse.

Unfortunately I'm not very familiar with more "esoteric" intrinsics, so I can't
bring anything special to the table when it comes to reviewing that the set of
exempted intrinsics is correct. Other than that I can gladly help in whatever
way to help this patch land.

(I rebased your patch, and it seems like there where only a few, minor updates
required in three files. Other than that, there are four tests in clang that
need some smaller fixes.)

Piotr

Best regards,
David

That list is not complete - pretty much every intrinsic that can throw
can also recurse (not for any fundamental reason -- just that
intrinsics that throw do that by calling some other function, and that
callee function can also be recursive). You may also want to ask Gor
about the coro_ intrinsics.

The way you're going about the change is risky though -- have you
considered adding a NoRecurse property instead? That way you can
start marking most of the "obviously" non-recursive intrinsics right
away and slowly expand the set.

This is asymmetric with "Throws", but for good reason - before Throws
every intrinsics was implicitly assumed to be no-throw, which is the
opposite situation from norecurse, IIUC.

-- Sanjoy

Hi,

Also, I think there is a bigger problem lurking than just with norecurse. I think that in general, functionattrs is not very good with attributes when intrinsics are present.

E.g.
https://bugs.llvm.org/show_bug.cgi?id=34696

Here dbg.value prevents both norecurse and readnone from being deduced.

So, it would be nice to fix this for norecurse, but it would be even nicer to fix it for intrinsics and attributes in general.

Regards,
Mikael

Hi,

Also, I think there is a bigger problem lurking than just with norecurse.

Yes

I think that in general, functionattrs is not very good with attributes
when intrinsics are present.

E.g.
https://bugs.llvm.org/show_bug.cgi?id=34696

Here dbg.value prevents both norecurse and readnone from being deduced.

A lot of these are the more general issue of intrinsics not being marked
with proper memory attributes as a form of attempted control
dependence/optimization blocking/etc

Intrinsics.td even says this.

So, it would be nice to fix this for norecurse, but it would be even nicer
to fix it for intrinsics and attributes in general.

Nobody as of yet has signed up to fix this, because it often requires
significant thinking about each intrinsic and what really should be
happening to it, modeling that, and teaching optimizers to deal with it.

Instead the large hammer is chosen.

Eventually it'll matter enough to performance for someone to do the work :slight_smile:

I agree with this, but I also agree with Sanjoy: We should add a NoRecurse property and mark intrinsics with it. This fits our general scheme for intrinsics (i.e., “if we say nothing, we assume the worst”). The fact that we model all sorts of dependencies as memory dependencies is also a problem, but a somewhat independent one. -Hal

part.

We *should* fix everything.
But we don't have to do that here, we can start with just adding NoRecurse.
We lose nothing, and gain something.