[LoadStoreVectorizer] Split the chain if the prefix is empty

[volkan]

Summary

Currently, the vectorizer discards all of the instructions in the chain if
the vectorizable prefix is empty. Instead, we can try to vectorize smaller
chunks in order to increase the number of vector instructions generated.

[anna]

Could you please add some test cases?

[volkan]

Added a test case.

[volkan]

Updated the test case.

[jlebar]

lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

741

"less than or equal to VF" is redundant with <= VF in the code. Can we say "is too small" or "is smaller than the vector width"?

749

Don't we know a priori that Left will not vectorize, because its vectorizable prefix equals Chain's vectorizable prefix?

Which leads to another question: Why do we chop off VF elements rather than just one?

750

These return bools, so can we use ||?

test/Transforms/LoadStoreVectorizer/AMDGPU/empty-prefix.ll

4 ↗

(On Diff #78877)

Can we write this comment in the form of

1. "Check that we X"
2. Something that does not rely on implementation details of the LSV? That is, can we avoid the term "vectorizable prefix", or, if we must use it, can we define it here?

[asbirlea]

The problem you found is real, but this is not the right solution for it.
The issue is in "getVectorizablePrefix". When a load that aliases the store is found, it gives up trying to find a prefix. In reality, all stores that precede the aliasing load (you can view this as a memory barrier) could be safely vectorized.
I'll work on a patch to fix this.

Side note: The testcase you added is fairly large. The problem can be showcased with a much smaller example, along the lines: 4 stores, 4 loads, 4 stores, with the 8 stores forming a chain. "getVectorizablePrefix" should not give up after the first store, but allow all 4 stores that precede the aliasing load to be vectorized.

lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

bool Vectorizer::vectorizeStoreChain(
 
   if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
     InstructionsProcessed->insert(Chain.begin(), Chain.end());
     return false;
   }
 
   ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain);
   if (NewChain.empty()) {
-    // No vectorization possible.
+    // No vectorization possible if the number of instructions
+    // is less than or equal to VF.
+    if (ChainSize <= VF) {
       InstructionsProcessed->insert(Chain.begin(), Chain.end());
       return false;
     }
+    // Split the chain and try each slice seperately in order
+    // to increase the number of vector instructions generated.
+    ArrayRef<Instruction *> Left = Chain.slice(0, VF);
+    ArrayRef<Instruction *> Right = Chain.slice(VF);
+    return vectorizeStoreChain(Left, InstructionsProcessed) |
+           vectorizeStoreChain(Right, InstructionsProcessed);
+  }
   if (NewChain.size() == 1) {
     // Failed after the first instruction. Discard it and try the smaller chain.
     InstructionsProcessed->insert(NewChain.front());
     return false;
   }
 
   // Update Chain to the valid vectorizable subchain.
   Chain = NewChain;
bool Vectorizer::vectorizeLoadChain(
 
   if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
     InstructionsProcessed->insert(Chain.begin(), Chain.end());
     return false;
   }
 
   ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain);
   if (NewChain.empty()) {
-    // No vectorization possible.
+    // No vectorization possible if the number of instructions
+    // is less than or equal to VF.
+    if (ChainSize <= VF) {
       InstructionsProcessed->insert(Chain.begin(), Chain.end());
       return false;
     }
+    // Split the chain and try each slice seperately in order
+    // to increase the number of vector instructions generated.
+    ArrayRef<Instruction *> Left = Chain.slice(0, VF);
+    ArrayRef<Instruction *> Right = Chain.slice(VF);
+    return vectorizeLoadChain(Left, InstructionsProcessed) |
+           vectorizeLoadChain(Right, InstructionsProcessed);
+  }
   if (NewChain.size() == 1) {
     // Failed after the first instruction. Discard it and try the smaller chain.
     InstructionsProcessed->insert(NewChain.front());
     return false;
   }
 
   // Update Chain to the valid vectorizable subchain.
   Chain = NewChain;