Update InstCombine to transform aggregate stores into scalar stores.

[deadalnix]

Summary

This is a first step toward getting proper support for aggregate loads and stores.

[reames]

This needs to go to llvm-commits. I'll review once that's done. I don't see anything major on a quick scan, but I haven't given it a careful read yet either.

[deadalnix]

What do you expect me to do except posting this in llvm-commit ?

I think this is pretty safe to get that in. This is straightforward and does not do much, but would serve as a base to continue the work.

[reames]

Nit picks inline. This is really close to ready for submission. The only change I'd really like to see is the change from BasicBlockPass to FunctionPass and the removal of dead member variables.

lib/Transforms/Scalar/AggregateMemAccessRemoval.cpp

11 ↗

(On Diff #20372)

Grammar. Possibly: "This transforms removes load ans stores of aggregate type by replacing them with equivalent scalar loads and stores."

Also, not that this doesn't handle *all* aggregate loads and stores (yet.)

36 ↗

(On Diff #20372)

Its more canonical to use a FunctionPass and a foreach loop using inst_range.

38 ↗

(On Diff #20372)

I don't think either of these are used in this version of the code?

45 ↗

(On Diff #20372)

What's this using line for?

60 ↗

(On Diff #20372)

If you use a function pass, this initialization function can just disappear. Along with the member variables.

[reames]

Added llvm-commits per http://llvm.org/docs/DeveloperPolicy.html.

[reames]

See review comments.

[deadalnix]

Make this a Function pass and address various comments. Removed many instance fields that where not necessary anymore.

[deadalnix]

ping ?

[chandlerc]

My primary question is why this isn't just an instcombine, using insertvalue / extractvalue to reconnect the aggregates?

[reames]

In D7780#133316, @chandlerc wrote:

My primary question is why this isn't just an instcombine, using insertvalue / extractvalue to reconnect the aggregates?

@chandlerc - Because we talked about that last time and it was rejected for some reason I don't really remember. I would strongly prefer we land this in something close to it's current form and then iterate in tree. This has topic has been stalled on census for months. Honestly, I sorta of agree with you, but let's revisit that separately.

@deadalnix - LGTM w/nits applied.

lib/Transforms/Scalar/AggregateMemAccessRemoval.cpp

91 ↗

(On Diff #20723)

You might want to make sure the size of the element is the size of the struct, otherwise we're loosing dereferencability information here.

95 ↗

(On Diff #20723)

Add a TODO about preserving metadata please.

102 ↗

(On Diff #20723)

This should be handled via an outer worklist not recursion, but please fix this as a separate change.

Actually, sorry, you're not testing this at all. *Delete* this line and then let's revisit in another change.

118 ↗

(On Diff #20723)

Add a test for this case please.

[deadalnix]

lib/Transforms/Scalar/AggregateMemAccessRemoval.cpp

102 ↗

(On Diff #20723)

What is wrong with using recursion here ?

118 ↗

(On Diff #20723)

I'm not sure if this is possible at all. This is more a sanity check than anything else. You can't store/load opaque structs to begin with.

[deadalnix]

lib/Transforms/Scalar/AggregateMemAccessRemoval.cpp

91 ↗

(On Diff #20723)

Is that possible that they differ for a one element struct ? I can add this as an assert because I don't think this possible at all that it does not match.

102 ↗

(On Diff #20723)

Also, this was tested in the whole diff. As only one element struct are supported now, I could write a test, but that would be very redundant with what already exists in D7607 .

[deadalnix]

Add assert to check size match.
Rebase and update load test (as load syntax changed).

[mehdi_amini]

lib/Transforms/Scalar/AggregateMemAccessRemoval.cpp

102 ↗

(On Diff #20723)

I don't like the approach "commit and fix in a separate change", unless there is a good reason and the "change" is already ready to follow. This is not a good process, and it build technical debt. Please do it right before committing.

Recursion is never a good idea unless you can prove that you won't explode the stack. LLVM is used in embedded environment where the stack size is limited. Even on a regular PC, you don't want to crash because you have a very long sequence of instruction and you recurse blindly.

[deadalnix]

lib/Transforms/Scalar/AggregateMemAccessRemoval.cpp

102 ↗

(On Diff #20723)

Well ok but:
1/ There is the whole diff to begin with, I've been asked to cut a minimal chunk of it to get review. Now you got to understand that, because it is minimal, it won't contains the whole thhing, pretty much by definition. You guys needs to agree on what the process is here. Either we get it in in one piece or in several, but we can't have both at once.
2/ There is bunch of code that recurse on what aggregate type contains already. If this is going to stack overflow, this is going to with this recursion or not. Additionnaly, you'd have to be doign fairly bizantine stuff to get aggregate nested so deep that you get a stack overflow. You'd have to have something like a struct of a struct of a struct of a struct .... of one element enough time to get a stack overflow.

[deadalnix]

• Rebase
• Create load and store with align directly instead of adding it later.
• Add comment about the recursion

[deadalnix]

Move all the things to InstCombine. Also, limit myself to store, as to keep thing minimal while we agree on the design.

[reames]

I'm okay with what's here once my fairly minor comments are addressed, but let's wait for Chandler to take a look as well.

(And thank you again for sticking it through a long review process!)

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

811

Rather than returning bool, please return the new Instruction or nullptr. This will allow us to add that new instruction to the worklist and will solve the deeply nested struct thing you were trying to address with recursion in the previous patch.

Alternatively, you could simple add the newly created store to the worklist within this function. I have no strong preference, but I suspect Chandler may care. It might be good to let him comment before actually making either change.

816

nit: Value *V

You should probably run this through clang-format.

825

Add a comment here that highlights the fact that the wrapped value can be smaller than the FCA and that we are possibly loosing dereferencability information here. We're okay with that for now, but it would be good to have it documented.

test/Transforms/InstCombine/aggregate-store.ll

15

Once you get the new stores onto the worklist, please add a test case for the nested struct case.

[deadalnix]

Add a test for struct in struct.
Fix pointer declaration style.

[deadalnix]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

811

None of this is not required, the builder sue a custom inserted that do it already. As for the bool return, I followed convention existing in the file.

825

It does not appear to be possible in the case where we have struct with one element.

[deadalnix]

Rebase
Friendly ping as the last requested update was done late on friday, so most likely is lost deep down in everybody's queue at this point.

[reames]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

811

I forgot about the custom inserter and the surrounding code appears to use a mixture of implicit and explicit adds. Comment withdrawn.

825

Ok. I haven't thought about this hard, but this seems likely to be true. Even if not, it's not a big deal at the moment.

[chandlerc]

LGTM, feel free to commit.

One nit, I would name the test case just "fca-decomposition" or something so we can add both load and store test cases to a single file.

[deadalnix]

Rebase and rename test

[deadalnix]

arc land

Is telling me that I can't land and

git svn dcommit

Ask me for my password (which ?). I've been through http://llvm.org/docs/Phabricator.html but couldn't find what i was looking for. What is the expected setup ?

[majnemer]

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

822

Please write this as StructType *ST

[mehdi_amini]

r232284

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

if (auto *BC = dyn_cast<BitCastInst>(V)) {
     return true;
   }
 
   // FIXME: We should also canonicalize loads of vectors when their elements are
   // cast to other types.
   return false;
 }
 
+static bool unpackStoreToAggregate(InstCombiner &IC, StoreInst &SI) {
+  // FIXME: We could probably with some care handle both volatile and atomic
+  // stores here but it isn't clear that this is important.
+  if (!SI.isSimple())
+    return false;
+
+  Value* V = SI.getValueOperand();
+  Type* T = V->getType();
+
+  if (!T->isAggregateType())
+    return false;
+
+  if (StructType* ST = dyn_cast<StructType>(T)) {
+    // If the struct only have one element, we unpack.
+    if (ST->getNumElements() == 1) {
+      V = IC.Builder->CreateExtractValue(V, 0);
+      combineStoreToNewValue(IC, SI, V);
+      return true;
+    }
+  }
+
+  return false;
+}
+
 /// equivalentAddressValues - Test if A and B will obviously have the same
 /// value. This includes recognizing that %t0 and %t1 will have the same
 /// value in code like this:
 ///   %t0 = getelementptr \@a, 0, 3
 ///   store i32 0, i32* %t0
 ///   %t1 = getelementptr \@a, 0, 3
 ///   %t2 = load i32* %t1
 ///
unsigned EffectiveStoreAlign = StoreAlign != 0 ? StoreAlign :
       DL->getABITypeAlignment(Val->getType());
 
     if (KnownAlign > EffectiveStoreAlign)
       SI.setAlignment(KnownAlign);
     else if (StoreAlign == 0)
       SI.setAlignment(EffectiveStoreAlign);
   }
 
+  // Try to canonicalize the stored type.
+  if (unpackStoreToAggregate(*this, SI))
+    return EraseInstFromFunction(SI);
+
   // Replace GEP indices if possible.
   if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Ptr, SI)) {
       Worklist.Add(NewGEPI);
       return &SI;
   }
 
   // Don't hack volatile/atomic stores.
   // FIXME: Some bits are legal for atomic stores; needs refactoring.

test/Transforms/InstCombine/aggregate-store.ll

+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+%A__vtbl = type { i8*, i32 (%A*)* }
+%A = type { %A__vtbl* }
+
+@A__vtblZ = constant %A__vtbl { i8* null, i32 (%A*)* @A.foo }
+
+declare i32 @A.foo(%A* nocapture %this)
+
+declare i8* @allocmemory(i64)
+
+define void @structs() {
+body:
+  %0 = tail call i8* @allocmemory(i64 32)
+  %1 = bitcast i8* %0 to %A*
+; CHECK: store %A__vtbl* @A__vtblZ
+  store %A { %A__vtbl* @A__vtblZ }, %A* %1, align 8
+  ret void
+}