Do not traverse ConstantData use-list in SLPVectorizer

[willir]

Summary

Walking the use list of a Constant (particularly, ConstantData)
is not scalable, since a given constant may be used by many
instructinos in many functions in many modules.

[nikic]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

989

Why does this check for ConstantData in particular?

[willir]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

989

Hi, thanks for the review.

Instances of ConstantData are unique for the entire an LLVMContext, so its uses can be spread across multiple functions and modules.
This commit is a part of a bigger project to remove use-list from ConstantData.

Here are some links for more info about it:
https://bugs.llvm.org/show_bug.cgi?id=30513
https://lists.llvm.org/pipermail/llvm-dev/2016-September/105157.html

[dexonsmith]

Adding some reviewers that have touched the SLPVectorizer recently to check this. (I have context on the motivation for the change and planned changes to the IR, but I don't know this pass well.)

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

989

It's possible that rejecting all Constants makes sense here, depending on whether this code needs to walk through GlobalValue-derived constants. I suspect it doesn't and we can just do Constant.

990–992

I think this comment will be more clear if it highlights the semantic problem. I suggest something like:

// Since this is a function pass, it doesn't make semantic sense to walk the
// users of a subclass of Constant. The users could be in another function,
// or even another module that happens to be in the same LLVMContext.

[willir]

Correct comment explaining the reason to skip ConstantData, as suggested by
@dexonsmith. At the moment isa<ConstantData>, I'm not sure whether using
isa<Constant> whould be better here.

[anton-afanasyev]

You are planning to revert this patch after ConstantData use-list removing, am I right?

[spatel]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

989

That sounds right to me - this pass is only concerned with "basic" integer/FP constants. For example, we have allConstant() around line 219:

/// \returns True if all of the values in \p VL are constants (but not
/// globals/constant expressions).

So I think it's safe to ignore any Constant here.

[willir]

In D94713#2504342, @anton-afanasyev wrote:

You are planning to revert this patch after ConstantData use-list removing, am I right?

Hi, well, not really, after ConstantData use-list removed, we definitely cannot walk its use-list.
We could change the check from isa to calling hasUseList(), but I'm not sure if it would be more readable here.

[willir]

Ignore all Constants, not just ConstantData

[spatel]

I have not followed the plans for changes to the IR, etc. But this doesn't seem to conflict with any optimizations that SLP tries to do, so LGTM.

[willir]

I don't have commit access. Would someone please commit for me?

• GIT_AUTHOR_NAME="Anton Rapetov"
• GIT_AUTHOR_EMAIL="[e-mail]"

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

class VLOperands {
     /// \Returns the additinal cost due to uses of \p LHS and \p RHS that are
     /// either external to the vectorized code, or require shuffling.
     int getExternalUsesCost(const std::pair<Value *, int> &LHS,
                             const std::pair<Value *, int> &RHS) {
       int Cost = 0;
       std::array<std::pair<Value *, int>, 2> Values = {{LHS, RHS}};
       for (int Idx = 0, IdxE = Values.size(); Idx != IdxE; ++Idx) {
         Value *V = Values[Idx].first;
+        if (isa<ConstantData>(V)) {
+          // Since this is a function pass, it doesn't make semantic sense to
+          // walk the users of a subclass of Constant. The users could be in
+          // another function, or even another module that happens to be in
+          // the same LLVMContext.
+          continue;
+        }
+
         // Calculate the absolute lane, using the minimum relative lane of LHS
         // and RHS as base and Idx as the offset.
         int Ln = std::min(LHS.second, RHS.second) + Idx;
         assert(Ln >= 0 && "Bad lane calculation");
         unsigned UsersBudget = LookAheadUsersBudget;
         for (User *U : V->users()) {
           if (const TreeEntry *UserTE = R.getTreeEntry(U)) {
             // The user is in the VectorizableTree. Check if we need to insert.