Skip redundant checks in AliasSet::aliasesUnknownInst

Project Infrastructure LLVM Dev List Archives
1

Dear llvm contributors,

Could you please advise me how to skip
checks, which are performed in AliasSet::aliasesUnknownInst, of
unknown instructions from different alias sets of an alias set tracker
that is a parameter of ‘AliasSetTracker::add(const AliasSetTracker
&AST)’?

If this wasn’t available at the moment and someone could review me, I
would try to implement it. A temporary patch can be found attached
(for example, ViewedInst can become a second parameter of
AliasSetTracker::addUnknown ). It
passes the LLVM regression tests and helps to reduce the runtime of
'opt -basicaa -licm out.opt.ll’ from 130ms to 67ms and the runtime of
'opt -basicaa -licm out.opt2.ll’ from 117ms to 62ms (out.opt.ll and
out.opt2.ll can be found on the following link
https://llvm.org/bugs/show_bug.cgi?id=23077).

Thank you for the attention!

0001-Mark-unknown-instructions-from-the-AST-parameter.patch (1.77 KB)

2

It sounds like UnknownInsts should really be a SmallSet, SmallPtrSet, or DenseSet (if you can’t do the others).

Otherwise, even with your patch, we are still wasting time traversing and copying and … the unknown instructions.

If that doesn’t work, I suspect the way you get dupes is through mergeSetIn, so you also could probably just change:

00061   } else if (ASHadUnknownInsts) {
00062     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
00063     AS.UnknownInsts.clear();
00064   }

You could insert the current unknown insts into a smallptrset, and then only append them to UnknownInsts if they aren’t in the set.

This should remove your dupes.

3

In addition to this, see my comments on the bug. LICM is using AST in a particular usage pattern when most of the work done by add(AST&) ends up being redundant for perfectly nested loops.

Philip

4

Thank you for the comments! I’ll try to respond to them soon.

5

Thank you for the comments! I’ll try to respond to them soon.

6

Thank you for the idea! Could you please explain it? If I’m not
mistaken, you advise to insert the unknown insts of an every AS from
AliasSetTracker::add(const AliasSetTracker &AST) into a smallptrset
and consequently append it to merged alias sets from
AliasSetTracker::findAliasSetForUnknownInst. I think that Philip
proposed something similar to your approach in
https://llvm.org/bugs/show_bug.cgi?id=23077.

7

Thank you for the idea! Could you please explain it?

Which part are you having trouble with, so i know where to concetrate?

If I’m not
mistaken, you advise to insert the unknown insts of an every AS from
AliasSetTracker::add(const AliasSetTracker &AST) into a smallptrset
and consequently append it to merged alias sets from
AliasSetTracker::findAliasSetForUnknownInst.

Well, no. This is not the only place duplication can occur, because the
merging of unknownInsts can occur through findAliasSetForPointer as well,
if that AS has unknown instructions.

See below.

I think that Philip
proposed something similar to your approach in
23077 – LICM seems unnecessarily slow.

You reported that you are finding duplicates on the unknown inst list.

The duplicates occur because we are not de-duplicating the unknowninst
lists attached to each AS when we merge them.

If you look at the code in mergeSetIn (used by both findAliasSetForPointer
and findAliasSetForUnknownInst) you can see when we merge AS's, we simply
append the list of unknowninsts from one AS into the "destination" AS,
without ever checking *whether that destination AS already contains any of
the same instructions on the unknowninst list*.

So things end up on the unknowninst lists multiple times.

There are many ways to solve this:

1. Don't use lists at all for unknowninsts for each AS, use SmallSets or
SmallPtrSets instead. Then any normal merging will deduplicate them for
you.
or
2. When merging AS's, deduplicate the unknown inst list by temporarily
storing it in a set.

#2 assumes that "merging AS's" is the only place that is causing duplicates.

8

I don’t see this in the bug report? Danny, I think your analysis is incorrect. If we’re merging two AliasSets, we have to consider where AliasSets can come from. Each instruction initially ends up in exactly one AliasSet. As a result, when we’re merging two ASTs (which covered different loops/instructions by definition), we should never see the same instruction twice when merging AliasSets. However, using a set to represent the unknown insts would still be useful. In particular, it would give us a fastpath for determining if a particular unknown instruction was already in an alias set. If we explicitly merged AliasSets from different ASTs (i.e. add all unknown at once to a single AliasSet, and then merge if needed), this would give us a fast way to avoid redundant aliasing checks when looking for things which need merged.

9

The patch sent to the mailing list does this:

+std::set<llvm::Instruction *> ViewedInst;

10

Hm, I’d thought I’d had a case where this could happen without duplicates in the original alias sets due to the repeated addition of elements from the same set, but now I’m not seeing it. Oh wait. Ah! The trick is that you don’t need to revisit the instructions you’ve already added. You “know” that the instruction you’re now querying can’t be in the same alias set as a previously added one, because, if it were, you’d have already merged them. That’s what this code is implementing. (Remember, we fall through to false here.) This code is incredibly complicated. :slight_smile:

11

Sorry for the confusion.