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

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

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

38

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

45

What's this using line for?

60

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

92

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

96

Add a TODO about preserving metadata please.

103

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.

119

Add a test for this case please.

[deadalnix]

lib/Transforms/Scalar/AggregateMemAccessRemoval.cpp

103

What is wrong with using recursion here ?

119

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

92

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.

103

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

103

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

103

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 ↗

(On Diff #21330)

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 ↗

(On Diff #21330)

nit: Value *V

You should probably run this through clang-format.

825 ↗

(On Diff #21330)

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 ↗

(On Diff #21330)

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 ↗

(On Diff #21330)

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 ↗

(On Diff #21330)

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 ↗

(On Diff #21330)

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

825 ↗

(On Diff #21330)

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

815 ↗

(On Diff #21871)

Please write this as StructType *ST

[mehdi_amini]

r232284

include/llvm/InitializePasses.h

 void initializeStackMapLivenessPass(PassRegistry&);
 void initializeMachineCombinerPass(PassRegistry &);
 void initializeLoadCombinePass(PassRegistry&);
 void initializeRewriteSymbolsPass(PassRegistry&);
 void initializeWinEHPreparePass(PassRegistry&);
 void initializePlaceBackedgeSafepointsImplPass(PassRegistry&);
 void initializePlaceSafepointsPass(PassRegistry&);
 void initializeDwarfEHPreparePass(PassRegistry&);
+void initializeAggregateMemAccessRemovalPass(PassRegistry&);
 }
 
 #endif

include/llvm/Transforms/Scalar.h

 
 //===----------------------------------------------------------------------===//
 //
 // RewriteStatepointsForGC - Rewrite any gc.statepoints which do not yet have
 // explicit relocations to include explicit relocations.
 //
 FunctionPass *createRewriteStatepointsForGCPass();
 
+//===----------------------------------------------------------------------===//
+//
+// AggregateMemAccessRemoval - Convert aggregate load/store into
+// scalar load/store
+BasicBlockPass *createAggregateMemAccessRemovalPass();
+
 } // End llvm namespace
 
 #endif

lib/Transforms/IPO/PassManagerBuilder.cpp

if (OptLevel == 0) {
 
     addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
     return;
   }
 
   // Add LibraryInfo if we have some.
   if (LibraryInfo)
     MPM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
   
+  // Remove aggregate load/store
+  MPM.add(createAggregateMemAccessRemovalPass());
+
   addInitialAliasAnalysisPasses(MPM);
 
   if (!DisableUnitAtATime) {
     addExtensionsToPM(EP_ModuleOptimizerEarly, MPM);
 
     MPM.add(createIPSCCPPass());              // IP SCCP
     MPM.add(createGlobalOptimizerPass());     // Optimize out global vars
 

lib/Transforms/Scalar/AggregateMemAccessRemoval.cpp

+//===- AggregateMemAccessRemoval.cpp - Remove aggregate loads/stores ------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This transformation remove load and stores of aggregate type into
+/// scalar loads and stores. This will allow subsequent passes to
+/// optimize them properly.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar.h"
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/TargetFolder.h"
+#include "llvm/Pass.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "aggregate-removal"
+
+namespace {
+
+class AggregateMemAccessRemoval : public BasicBlockPass {
+  LLVMContext *C;
+  const DataLayout *DL;
+
+public:
+  AggregateMemAccessRemoval()
+      : BasicBlockPass(ID),
+        C(nullptr), DL(nullptr) { }
+
+  using llvm::Pass::doInitialization;
+  bool doInitialization(Function &) override;
+  bool runOnBasicBlock(BasicBlock &BB) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  const char *getPassName() const override { return "AggregateMemAccessRemoval"; }
+  static char ID;
+private:
+  SmallVector<Instruction*, 8> InstrsToErase;
+
+  void runOnLoad(LoadInst* LI);
+  void runOnStore(StoreInst* SI);
+};
+}
+
+bool AggregateMemAccessRemoval::doInitialization(Function &F) {
+  DEBUG(dbgs() << "AggregateMemAccessRemoval function: " << F.getName() << "\n");
+  C = &F.getContext();
+  DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
+  if (!DLP) {
+    DEBUG(dbgs() << "\tSkipping AggregateMemAccessRemoval -- no target data!\n");
+    return false;
+  }
+  DL = &DLP->getDataLayout();
+  return true;
+}
+
+bool AggregateMemAccessRemoval::runOnBasicBlock(BasicBlock &BB) {
+  if (skipOptnoneFunction(BB) || !DL)
+    return false;
+
+  for (auto &I : BB) {
+    LoadInst* LI = dyn_cast<LoadInst>(&I);
+    if (LI && LI->isUnordered()) {
+      runOnLoad(LI);
+      continue;
+    }
+    
+    StoreInst* SI = dyn_cast<StoreInst>(&I);
+    if (SI && SI->isUnordered()) {
+      runOnStore(SI);
+      continue;
+    }
+  }
+  
+  if (InstrsToErase.size() == 0)
+    return false;
+  
+  for (auto &I : InstrsToErase) {
+    I->eraseFromParent();
+  }
+  
+  InstrsToErase.clear();
+  return true;
+}
+
+void AggregateMemAccessRemoval::runOnLoad(LoadInst* LI) {
+  Type* T = LI->getType();
+  if (!T->isAggregateType())
+    return;
+
+  DEBUG(dbgs() << "\tload : " << *LI << "\n");
+
+  IRBuilder<> Builder(LI->getParent(), LI);
+  if (StructType *ST = dyn_cast<StructType>(T)) {
+    if (ST->isOpaque())
+      return;
+
+    // If the struct only have one element, we unpack.
+    if (ST->getNumElements() == 1) {
+      InstrsToErase.push_back(LI);
+      LoadInst* NewLI = Builder.CreateLoad(
+        Builder.CreateStructGEP(LI->getPointerOperand(), 0)
+      );
+      
+      Value* V = UndefValue::get(T);
+      V = Builder.CreateInsertValue(V, NewLI, 0);
+      LI->replaceAllUsesWith(V);
+      
+      runOnLoad(NewLI);
+      return;
+    }
+  }
+}
+
+void AggregateMemAccessRemoval::runOnStore(StoreInst* SI) {
+  Value* V = SI->getValueOperand();
+  Type* T = V->getType();
+  if (!T->isAggregateType())
+    return;
+
+  DEBUG(dbgs() << "\tstore : " << *SI << "\n");
+
+  IRBuilder<> Builder(SI->getParent(), SI);
+  if (StructType* ST = dyn_cast<StructType>(T)) {
+    if (ST->isOpaque())
+      return;
+
+    // If the struct only have one element, we unpack.
+    if (ST->getNumElements() == 1) {
+      InstrsToErase.push_back(SI);
+      runOnStore(Builder.CreateStore(
+        Builder.CreateExtractValue(V, 0),
+        Builder.CreateStructGEP(SI->getPointerOperand(), 0)
+      ));
+      return;
+    }
+  }
+}
+
+void AggregateMemAccessRemoval::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesCFG();
+}
+
+char AggregateMemAccessRemoval::ID = 0;
+
+BasicBlockPass *llvm::createAggregateMemAccessRemovalPass() {
+  return new AggregateMemAccessRemoval();
+}
+
+INITIALIZE_PASS(AggregateMemAccessRemoval, "aggregate-removal",
+                "Transform aggregate store/load into integrals.",
+                false, false)
+

lib/Transforms/Scalar/CMakeLists.txt

 add_llvm_library(LLVMScalarOpts
   ADCE.cpp
+  AggregateMemAccessRemoval.cpp
   AlignmentFromAssumptions.cpp
   BDCE.cpp
   ConstantHoisting.cpp
   ConstantProp.cpp
   CorrelatedValuePropagation.cpp
   DCE.cpp
   DeadStoreElimination.cpp
   EarlyCSE.cpp

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeStructurizeCFGPass(Registry);
   initializeSinkingPass(Registry);
   initializeTailCallElimPass(Registry);
   initializeSeparateConstOffsetFromGEPPass(Registry);
   initializeStraightLineStrengthReducePass(Registry);
   initializeLoadCombinePass(Registry);
   initializePlaceBackedgeSafepointsImplPass(Registry);
   initializePlaceSafepointsPass(Registry);
+  initializeAggregateMemAccessRemovalPass(Registry);
 }
 
 void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) {
   initializeScalarOpts(*unwrap(R));
 }
 
 void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createAggressiveDCEPass());

test/Transforms/AggregateMemAccessRemoval/load.ll

+; RUN: opt -aggregate-removal -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* }
+
+declare i8* @allocmemory(i64)
+
+define %A @structA() {
+body:
+  %0 = tail call i8* @allocmemory(i64 32)
+  %1 = bitcast i8* %0 to %A*
+; CHECK: load %A__vtbl**
+; CHECK: insertvalue %A undef, %A__vtbl* {{.*}}, 0
+  %2 = load %A* %1, align 8
+  ret %A %2
+}
+

test/Transforms/AggregateMemAccessRemoval/store.ll

+; RUN: opt -aggregate-removal -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
+}
+