[Polly] [WIP] [ManagedMemoryRewrite] Rewrite global structs to managed memory.

[bollu]

Summary

This is highly WIP and contains a *lot* of code duplication between this code
path and the arrays code path. These will be merged together and cleaned up
once I clean up the code and test cases.

lib/CodeGen/ManagedMemoryRewrite.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/IRReader/IRReader.h"
 #include "llvm/Linker/Linker.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
static void expandConstantExpr(ConstantExpr *Cur, PollyIRBuilder &Builder,
   // they should mutate `I`.
   Cur = nullptr;
 
   Expands.insert(I);
   Parent->setOperand(index, I);
 
   // The things that `Parent` uses (its operands) should be created
   // before `Parent`.
+  // TODO: make a separate test case for this.
+  if (auto Phi = dyn_cast<PHINode>(Parent)) {
+      errs() << "**** INSERTING INTO PHI NODE!****\n";
+      BasicBlock *BB = Phi->getIncomingBlock(index);
+      Builder.SetInsertPoint(BB->getTerminator());
+      Builder.Insert(I);
+  } else {
       Builder.SetInsertPoint(Parent);
       Builder.Insert(I);
+  }
 
   for (unsigned i = 0; i < I->getNumOperands(); i++) {
     Value *Op = I->getOperand(i);
     assert(isa<Constant>(Op) && "constant must have a constant operand");
 
     if (ConstantExpr *CExprOp = dyn_cast<ConstantExpr>(Op))
       expandConstantExpr(CExprOp, Builder, I, i, Expands);
   }
static void getInstructionUsersOfValue(Value *V,
   } else {
     // Anything that is a `User` must be a constant or an instruction.
     auto *C = cast<Constant>(V);
     for (Use &CUse : C->uses())
       getInstructionUsersOfValue(CUse.getUser(), Owners);
   }
 }
 
+/// Look for `Needle` in `Haystack` and its operands, recursing on `Haystack`.
+static bool ValueContainsValue(Value *Haystack, Value *Needle) {
+    if (Haystack == Needle) return true;
+
+    if (User *U = dyn_cast<User>(Haystack)) {
+        for (unsigned i = 0; i < U->getNumOperands(); i++) {
+            Value *Op = U->getOperand(i);
+            if (ValueContainsValue(Op, Needle)) return true; 
+        }
+    }
+
+  return false;
+}
+
+
+static void
+replaceGlobalVariable(Module &M, const DataLayout &DL, GlobalVariable &GV,
+                   SmallPtrSet<GlobalVariable *, 4> &ReplacedGlobals) {
+    assert(!isa<ArrayType>(GV.getType()->getElementType()));
+
+  Type *GVElemTy = GV.getType()->getElementType();
+
+  const bool OnlyVisibleInsideModule = GV.hasPrivateLinkage() ||
+                                       GV.hasInternalLinkage() ||
+                                       IgnoreLinkageForGlobals;
+  if (!OnlyVisibleInsideModule) {
+    DEBUG(dbgs() << "Not rewriting (" << GV
+                 << ") to managed memory "
+                    "because it could be visible externally. To force rewrite, "
+                    "use -polly-acc-rewrite-ignore-linkage-for-globals.\n");
+    return;
+  }
+
+  if (!GV.hasInitializer() ||
+      !isa<ConstantAggregateZero>(GV.getInitializer())) {
+    DEBUG(dbgs() << "Not rewriting (" << GV
+                 << ") to managed memory "
+                    "because it has an initializer which is "
+                    "not a zeroinitializer.\n");
+    return;
+  }
+
+  // At this point, we have committed to replacing this array.
+  ReplacedGlobals.insert(&GV);
+
+  std::string NewName = GV.getName();
+  NewName += ".toptr";
+  GlobalVariable *Replacement =
+      cast<GlobalVariable>(M.getOrInsertGlobal(NewName, GVElemTy->getPointerTo()));
+  Replacement->setInitializer(ConstantPointerNull::get(GVElemTy->getPointerTo()));
+
+  Function *PollyMallocManaged = getOrCreatePollyMallocManaged(M);
+  std::string FnName = GV.getName();
+  FnName += ".constructor";
+  PollyIRBuilder Builder(M.getContext());
+  FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
+  const GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
+  Function *F = Function::Create(Ty, Linkage, FnName, &M);
+  BasicBlock *Start = BasicBlock::Create(M.getContext(), "entry", F);
+  Builder.SetInsertPoint(Start);
+
+  const uint64_t SizeInt = DL.getTypeAllocSize(GVElemTy);
+  Value *Size = Builder.getInt64(SizeInt);
+  Size->setName(".size");
+
+  Value *AllocatedMemRaw =
+      Builder.CreateCall(PollyMallocManaged, {Size}, "mem.raw");
+  Value *AllocatedMemTyped =
+      Builder.CreatePointerCast(AllocatedMemRaw, GVElemTy->getPointerTo(), "mem.typed");
+  Builder.CreateStore(AllocatedMemTyped, Replacement);
+  Builder.CreateRetVoid();
+
+  const int Priority = 0;
+  appendToGlobalCtors(M, F, Priority, Replacement);
+
+  SmallVector<Instruction *, 4> UserInsts;
+  // Get all instructions that use array. We need to do this weird thing
+  // because `Constant`s that contain this array neeed to be expanded into
+  // instructions so that we can replace their parameters. `Constant`s cannot
+  // be edited easily, so we choose to convert all `Constant`s to
+  // `Instruction`s and handle all of the uses of `Array` uniformly.
+  for (Use &U : GV.uses())
+    getInstructionUsersOfValue(U.getUser(), UserInsts);
+
+  for (Instruction *I : UserInsts) {
+
+      if (auto Phi = dyn_cast<PHINode>(I)) { 
+          errs() << "\n\n";
+          errs() << "Instruction:\n*" << *I << "Is a phi node that uses:\n" << GV << "\n";
+          // TODO: Store `Use` in `UserInstrs` because this will let us immediately
+          // access the PHI node.
+          for(unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {
+              if (!ValueContainsValue(Phi->getIncomingValue(i), &GV)) continue;
+              errs() << i << " is index containing GV\n";
+
+              // <ty>** -> <ty>*
+              BasicBlock *BB = Phi->getIncomingBlock(i);
+              Builder.SetInsertPoint(BB->getTerminator());
+              Value *PtrLoaded = Builder.CreateLoad(Replacement, std::string(GV.getName()) + "ptr.load");
+              rewriteOldValToNew(I, &GV, PtrLoaded, Builder);
+              errs() << "Inst BB Now: " << *(I->getParent()) << "\n";
+              errs() << "Prev BB Now: " << *BB << "\n";
+          }
+      } else {
+
+        Builder.SetInsertPoint(I);
+        // <ty>** -> <ty>*
+        Value *PtrLoaded = Builder.CreateLoad(Replacement, "ptr.load");
+        rewriteOldValToNew(I, &GV, PtrLoaded, Builder);
+      }
+  }
+}
+
 static void
 replaceGlobalArray(Module &M, const DataLayout &DL, GlobalVariable &Array,
                    SmallPtrSet<GlobalVariable *, 4> &ReplacedGlobals) {
   // We only want arrays.
   ArrayType *ArrayTy = dyn_cast<ArrayType>(Array.getType()->getElementType());
   if (!ArrayTy)
     return;
   Type *ElemTy = ArrayTy->getElementType();
if (Free) {
       Function *PollyFreeManaged = getOrCreatePollyFreeManaged(M);
       assert(PollyFreeManaged && "unable to create polly_freeManaged");
 
       replaceAllUsesAndConstantUses(Free, PollyFreeManaged, Builder);
       Free->eraseFromParent();
     }
 
     SmallPtrSet<GlobalVariable *, 4> GlobalsToErase;
-    for (GlobalVariable &Global : M.globals())
+    for (GlobalVariable &Global : M.globals()) {
+        if (isa<ArrayType>(Global.getType()->getElementType()))
             replaceGlobalArray(M, DL, Global, GlobalsToErase);
+        else
+            replaceGlobalVariable(M, DL, Global, GlobalsToErase);
+    }
     for (GlobalVariable *G : GlobalsToErase)
       G->eraseFromParent();
 
     // Rewrite allocas to cudaMallocs if we are asked to do so.
     if (RewriteAllocas) {
       SmallSet<AllocaInst *, 4> AllocasToBeManaged;
       for (Function &F : M.functions())
         getAllocasToBeManaged(F, AllocasToBeManaged);

test/GPGPU/managed-memory-rewrite-phi-node.ll

+; RUN: opt %loadPolly -S \
+; RUN: -polly-acc-rewrite-managed-memory \
+; RUN: -polly-acc-rewrite-ignore-linkage-for-globals < %s 
+
+source_filename = "bugpoint-output-1e7fd97.bc"
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+%"struct.array3_real(kind=8).3.29.107.289.315.341.419.471.549.627.653.679.809.835.1017.1043.1069.1145" = type { i8*, i64, i64, [3 x %struct.descriptor_dimension.0.26.104.286.312.338.416.468.546.624.650.676.806.832.1014.1040.1066.1144] }
+%struct.descriptor_dimension.0.26.104.286.312.338.416.468.546.624.650.676.806.832.1014.1040.1066.1144 = type { i64, i64, i64 }
+%"struct.array4_real(kind=8).4.30.108.290.316.342.420.472.550.628.654.680.810.836.1018.1044.1070.1146" = type { i8*, i64, i64, [4 x %struct.descriptor_dimension.0.26.104.286.312.338.416.468.546.624.650.676.806.832.1014.1040.1066.1144] }
+
+@__data_fields_MOD_w_g1 = external global %"struct.array3_real(kind=8).3.29.107.289.315.341.419.471.549.627.653.679.809.835.1017.1043.1069.1145", align 32
+@__data_fields_MOD_t_snow_mult = global %"struct.array4_real(kind=8).4.30.108.290.316.342.420.472.550.628.654.680.810.836.1018.1044.1070.1146" zeroinitializer, align 32
+
+; Function Attrs: nounwind uwtable
+define void @__src_allocation_MOD_deallocate_fields() #0 {
+entry:
+  br i1 undef, label %"252", label %"247"
+
+"247":                                            ; preds = %entry
+  br label %"256.sink.split"
+
+"252":                                            ; preds = %entry
+  br label %"256.sink.split"
+
+"256.sink.split":                                 ; preds = %"252", %"247"
+  %.sink = phi i8** [ getelementptr inbounds (%"struct.array3_real(kind=8).3.29.107.289.315.341.419.471.549.627.653.679.809.835.1017.1043.1069.1145", %"struct.array3_real(kind=8).3.29.107.289.315.341.419.471.549.627.653.679.809.835.1017.1043.1069.1145"* @__data_fields_MOD_w_g1, i64 0, i32 0), %"252" ], [ getelementptr inbounds (%"struct.array4_real(kind=8).4.30.108.290.316.342.420.472.550.628.654.680.810.836.1018.1044.1070.1146", %"struct.array4_real(kind=8).4.30.108.290.316.342.420.472.550.628.654.680.810.836.1018.1044.1070.1146"* @__data_fields_MOD_t_snow_mult, i64 0, i32 0), %"247" ]
+  ret void
+}
+
+attributes #0 = { nounwind uwtable }