[Beignet] [PATCH] GBE: Support storing/loading pointers to/from private array

Ruiling Song ruiling.song at intel.com
Thu May 21 01:39:05 PDT 2015


The idea is create two additional array for holding
pointer-base and bti.

Signed-off-by: Ruiling Song <ruiling.song at intel.com>
---
 backend/src/llvm/llvm_gen_backend.cpp | 210 ++++++++++++++++++++++++++++++++--
 1 file changed, 200 insertions(+), 10 deletions(-)

diff --git a/backend/src/llvm/llvm_gen_backend.cpp b/backend/src/llvm/llvm_gen_backend.cpp
index aec04fb..e5ba119 100644
--- a/backend/src/llvm/llvm_gen_backend.cpp
+++ b/backend/src/llvm/llvm_gen_backend.cpp
@@ -489,7 +489,7 @@ namespace gbe
     map<Value *, Value *> BtiValueMap;
     // map ptr to it's base
     map<Value *, Value *> pointerBaseMap;
-
+    std::set<Value *> addrStoreInst;
     typedef map<Value *, Value *>::iterator PtrBaseMapIter;
     /*! We visit each function twice. Once to allocate the registers and once to
      *  emit the Gen IR instructions
@@ -565,13 +565,14 @@ namespace gbe
       BtiMap.clear();
       BtiValueMap.clear();
       pointerBaseMap.clear();
+      addrStoreInst.clear();
       // Reset for next function
       btiBase = BTI_RESERVED_NUM;
       return false;
     }
     /*! Given a possible pointer value, find out the interested escape like
         load/store or atomic instruction */
-    void findPointerEscape(Value *ptr, std::set<Value *> &mixedPtr, bool recordMixed);
+    void findPointerEscape(Value *ptr, std::set<Value *> &mixedPtr, bool recordMixed, std::vector<Value *> &revisit);
     /*! For all possible pointers, GlobalVariable, function pointer argument,
         alloca instruction, find their pointer escape points */
     void analyzePointerOrigin(Function &F);
@@ -580,6 +581,8 @@ namespace gbe
     bool isSingleBti(Value *Val);
     Value *getBtiRegister(Value *v);
     Value *getPointerBase(Value *ptr);
+    void processPointerArray(Value *ptr, Value *bti, Value *base);
+    void handleStoreLoadAddress(Function &F);
 
     MDNode *getKernelFunctionMetadata(Function *F);
     virtual bool doFinalization(Module &M) { return false; }
@@ -730,10 +733,13 @@ namespace gbe
     return false;
   }
 
-  void GenWriter::findPointerEscape(Value *ptr,  std::set<Value *> &mixedPtr, bool bFirstPass) {
+  void GenWriter::findPointerEscape(Value *ptr,  std::set<Value *> &mixedPtr, bool bFirstPass, std::vector<Value *> &revisit) {
     std::vector<Value*> workList;
     std::set<Value *> visited;
+    // loadInst result maybe used as pointer
+    std::set<LoadInst *> ptrCandidate;
 
+    bool isPointerArray = false;
     if (ptr->use_empty()) return;
 
     workList.push_back(ptr);
@@ -741,7 +747,6 @@ namespace gbe
     for (unsigned i = 0; i < workList.size(); i++) {
       Value *work = workList[i];
       if (work->use_empty()) continue;
-
       for (Value::use_iterator iter = work->use_begin(); iter != work->use_end(); ++iter) {
       // After LLVM 3.5, use_iterator points to 'Use' instead of 'User',
       // which is more straightforward.
@@ -750,6 +755,24 @@ namespace gbe
   #else
         User *theUser = iter->getUser();
   #endif
+        // becareful with sub operation
+        if (isa<BinaryOperator>(theUser) && dyn_cast<BinaryOperator>(theUser)->getOpcode() == Instruction::Sub) {
+          // check both comes from ptrtoInt, don't need to traverse ptrdiff
+          Value *op0 = theUser->getOperand(0);
+          Value *op1 = theUser->getOperand(1);
+          if ((isa<Instruction>(op0) && dyn_cast<Instruction>(op0)->getOpcode() == Instruction::PtrToInt)
+              &&(isa<Instruction>(op1) && dyn_cast<Instruction>(op1)->getOpcode() == Instruction::PtrToInt)) {
+            continue;
+          }
+        }
+
+        if (isa<Instruction>(theUser)) {
+          // some GlobalVariable maybe used in the function which is not current processed.
+          // such kind of user should be skipped
+          if (dyn_cast<Instruction>(theUser)->getParent()->getParent() != Func)
+            continue;
+        }
+
         bool visitedInThisSource = visited.find(theUser) != visited.end();
 
         if (isa<SelectInst>(theUser) || isa<PHINode>(theUser))
@@ -797,8 +820,32 @@ namespace gbe
         }
 
         // pointer address is used as the ValueOperand in store instruction, should be skipped
-        if (StoreInst *load = dyn_cast<StoreInst>(theUser)) {
-          if (load->getValueOperand() == work) {
+        if (StoreInst *store = dyn_cast<StoreInst>(theUser)) {
+          if (store->getValueOperand() == work) {
+            addrStoreInst.insert(store);
+            Value * pointerOperand = store->getPointerOperand();
+            // check whether the pointerOperand already visited or not,
+            // if not visited, then we need to record all the loadInst
+            // on the origin of pointerOperand
+            // if visited, that is the origin of the pointerOperand already
+            // traversed, we need to the traverse again to record all the LoadInst
+            PtrOrigMapIter pointerOpIter = pointerOrigMap.find(pointerOperand);
+            bool pointerVisited = pointerOpIter != pointerOrigMap.end();
+            if (pointerVisited) {
+              revisit.push_back((*pointerOpIter).second[0]);
+            }
+
+            PtrOrigMapIter ptrIter = pointerOrigMap.find(work);
+            if (ptrIter == pointerOrigMap.end()) {
+              // create new one
+              SmallVector<Value *, 4> pointers;
+              pointers.push_back(ptr);
+              pointerOrigMap.insert(std::make_pair(work, pointers));
+            } else {
+              // update the pointer source here,
+              (*ptrIter).second[0] = ptr;
+            }
+
             continue;
           }
         }
@@ -812,9 +859,15 @@ namespace gbe
           }
           Value *pointer = NULL;
           if (isa<LoadInst>(theUser)) {
+            ptrCandidate.insert(cast<LoadInst>(theUser));
             pointer = dyn_cast<LoadInst>(theUser)->getPointerOperand();
           } else if (isa<StoreInst>(theUser)) {
             pointer = dyn_cast<StoreInst>(theUser)->getPointerOperand();
+            // Check whether we have stored a address to this pointer
+            // if yes, we need to traverse the ptrCandidate, as they are loaded pointers
+            if (addrStoreInst.find(theUser) != addrStoreInst.end()) {
+              isPointerArray = true;
+            }
           } else if (isa<CallInst>(theUser)) {
             // atomic/read(write)image
             CallInst *ci = dyn_cast<CallInst>(theUser);
@@ -843,7 +896,17 @@ namespace gbe
         }
       }
     }
+
+    if (isPointerArray) {
+      GBE_ASSERT((isa<AllocaInst>(ptr) || ptrCandidate.empty())
+                && "storing/loading pointers only support private array");
+      for (auto x : ptrCandidate) {
+        revisit.push_back(x);
+      }
+    }
+    ptrCandidate.clear();
   }
+
   bool GenWriter::isSingleBti(Value *Val) {
     // self + others same --> single
     // all same  ---> single
@@ -967,6 +1030,7 @@ namespace gbe
     } else {
       if (isSingleBti(Val)) {
         PtrOrigMapIter iter = pointerOrigMap.find(Val);
+        GBE_ASSERT(iter != pointerOrigMap.end());
         Value * bti = getBtiRegister((*iter).second[0]);
         BtiValueMap.insert(std::make_pair(Val, bti));
         return bti;
@@ -976,6 +1040,7 @@ namespace gbe
 
           IRBuilder<> Builder(si->getParent());
           PtrOrigMapIter iter = pointerOrigMap.find(Val);
+          GBE_ASSERT(iter != pointerOrigMap.end());
           Value *trueVal = getBtiRegister((*iter).second[0]);
           Value *falseVal = getBtiRegister((*iter).second[1]);
           Builder.SetInsertPoint(si);
@@ -989,6 +1054,7 @@ namespace gbe
 
           PHINode *btiPhi = Builder.CreatePHI(IntegerType::get(Val->getContext(), 32), phi->getNumIncomingValues());
           PtrOrigMapIter iter = pointerOrigMap.find(Val);
+          GBE_ASSERT(iter != pointerOrigMap.end());
           SmallVector<Value *, 4> &pointers = (*iter).second;
           unsigned srcNum = pointers.size();
           for (unsigned x = 0; x < srcNum; x++) {
@@ -1105,6 +1171,91 @@ namespace gbe
     }
   }
 
+  void GenWriter::processPointerArray(Value *ptr, Value *bti, Value *base) {
+    std::vector<Value*> workList;
+    std::set<Value *> visited;
+
+    if (ptr->use_empty()) return;
+
+    workList.push_back(ptr);
+
+    for (unsigned i = 0; i < workList.size(); i++) {
+      Value *work = workList[i];
+      if (work->use_empty()) continue;
+
+      for (Value::use_iterator iter = work->use_begin(); iter != work->use_end(); ++iter) {
+      // After LLVM 3.5, use_iterator points to 'Use' instead of 'User',
+      // which is more straightforward.
+  #if (LLVM_VERSION_MAJOR == 3) && (LLVM_VERSION_MINOR < 5)
+        User *theUser = *iter;
+  #else
+        User *theUser = iter->getUser();
+  #endif
+        if(visited.find(theUser) != visited.end())
+          continue;
+
+        visited.insert(theUser);
+
+        if (isa<LoadInst>(theUser) || isa<StoreInst>(theUser) || isa<CallInst>(theUser)) {
+          if (isa<CallInst>(theUser)) {
+            Function *F = dyn_cast<CallInst>(theUser)->getCalledFunction();
+            if (!F || F->getIntrinsicID() != 0) continue;
+          }
+          bool isLoad; Value *pointerOp;
+
+          IRBuilder<> Builder(cast<Instruction>(theUser)->getParent());
+          if (isa<LoadInst>(theUser)) {
+            pointerOp = dyn_cast<LoadInst>(theUser)->getPointerOperand();
+            isLoad = true;
+          } else {
+            pointerOp = dyn_cast<StoreInst>(theUser)->getPointerOperand();
+            isLoad = false;
+          }
+          Builder.SetInsertPoint(cast<Instruction>(theUser));
+
+          Type *int32Ty = Type::getInt32Ty(ptr->getContext());
+          Value *v1 = Builder.CreatePtrToInt(pointerOp, int32Ty);
+
+          PtrOrigMapIter originIter = pointerOrigMap.find(pointerOp);
+          GBE_ASSERT(originIter != pointerOrigMap.end());
+
+          Value *v2 = Builder.CreatePtrToInt(originIter->second[0], int32Ty);
+          Value *v3 = Builder.CreatePtrToInt(base, int32Ty);
+          Value *v4 = Builder.CreatePtrToInt(bti, int32Ty);
+          // newLocBase = (pointer - origin) + base_start
+          Value *diff = Builder.CreateSub(v1, v2);
+          Value *newLocBase = Builder.CreateAdd(v3, diff);
+          newLocBase = Builder.CreateIntToPtr(newLocBase, Type::getInt32PtrTy(ptr->getContext()));
+          // newLocBti = (pointer - origin) + bti_start
+          Value *newLocBti = Builder.CreateAdd(v4, diff);
+          newLocBti = Builder.CreateIntToPtr(newLocBti, Type::getInt32PtrTy(ptr->getContext()));
+
+          // later GenWriter instruction translation needs this map info
+          BtiValueMap.insert(std::make_pair(newLocBti, ConstantInt::get(Type::getInt32Ty(ptr->getContext()), BTI_PRIVATE)));
+          pointerBaseMap.insert(std::make_pair(newLocBti, ConstantPointerNull::get(cast<PointerType>(pointerOp->getType()))));
+
+          BtiValueMap.insert(std::make_pair(newLocBase, ConstantInt::get(Type::getInt32Ty(ptr->getContext()), BTI_PRIVATE)));
+          pointerBaseMap.insert(std::make_pair(newLocBase, ConstantPointerNull::get(cast<PointerType>(pointerOp->getType()))));
+
+          if (isLoad) {
+            Value *loadedBase = Builder.CreateLoad(newLocBase);
+            Value *loadedBti = Builder.CreateLoad(newLocBti);
+
+            BtiValueMap.insert(std::make_pair(theUser, loadedBti));
+            pointerBaseMap.insert(std::make_pair(theUser, loadedBase));
+          } else {
+            Value *valueOp = cast<StoreInst>(theUser)->getValueOperand();
+            Value *tmp = Builder.CreatePtrToInt(getPointerBase(valueOp), Type::getInt32Ty(ptr->getContext()));
+            Builder.CreateStore(tmp, newLocBase);
+            Builder.CreateStore(getBtiRegister(valueOp), newLocBti);
+          }
+        } else {
+          workList.push_back(theUser);
+        }
+      }
+    }
+  }
+
   void GenWriter::analyzePointerOrigin(Function &F) {
     // used to record where the pointers get mixed (i.e. select or phi instruction)
     std::set<Value *> mixedPtr;
@@ -1114,37 +1265,76 @@ namespace gbe
     // and update the sources correctly. For pointers reachable from mixed-pointer, we will set
     // its direct mixed-pointer parent as it's pointer origin.
 
+    std::vector<Value *> revisit;
     // GlobalVariable
     Module::GlobalListType &globalList = const_cast<Module::GlobalListType &> (TheModule->getGlobalList());
     for(auto i = globalList.begin(); i != globalList.end(); i ++) {
       GlobalVariable &v = *i;
       if(!v.isConstantUsed()) continue;
-      findPointerEscape(&v, mixedPtr, true);
+      findPointerEscape(&v, mixedPtr, true, revisit);
     }
     // function argument
     for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
       if (I->getType()->isPointerTy()) {
-        findPointerEscape(I, mixedPtr, true);
+        findPointerEscape(I, mixedPtr, true, revisit);
       }
     }
     // alloca
     BasicBlock &bb = F.getEntryBlock();
     for (BasicBlock::iterator iter = bb.begin(), iterE = bb.end(); iter != iterE; ++iter) {
       if (AllocaInst *ai = dyn_cast<AllocaInst>(iter)) {
-        findPointerEscape(ai, mixedPtr, true);
+        findPointerEscape(ai, mixedPtr, true, revisit);
       }
     }
+    // storing/loading pointer would introduce revisit
+    for (std::vector<Value *>::iterator iter = revisit.begin(); iter != revisit.end(); ++iter) {
+      findPointerEscape(*iter, mixedPtr, true, revisit);
+    }
+
     // the second pass starts from mixed pointer
     for (std::set<Value *>::iterator iter = mixedPtr.begin(); iter != mixedPtr.end(); ++iter) {
-      findPointerEscape(*iter, mixedPtr, false);
+      findPointerEscape(*iter, mixedPtr, false, revisit);
     }
 
     for (std::set<Value *>::iterator iter = mixedPtr.begin(); iter != mixedPtr.end(); ++iter) {
       getBtiRegister(*iter);
     }
+
     for (std::set<Value *>::iterator iter = mixedPtr.begin(); iter != mixedPtr.end(); ++iter) {
       getPointerBase(*iter);
     }
+    handleStoreLoadAddress(F);
+  }
+  void GenWriter::handleStoreLoadAddress(Function &F) {
+    std::set<Value *> processed;
+    for (std::set<Value *>::iterator iter = addrStoreInst.begin(); iter != addrStoreInst.end(); ++iter) {
+      StoreInst *store = cast<StoreInst>(*iter);
+      Value *pointerOp = store->getPointerOperand();
+      PtrOrigMapIter ptrIter = pointerOrigMap.find(pointerOp);
+      GBE_ASSERT(ptrIter != pointerOrigMap.end());
+      Value *base = (*ptrIter).second[0];
+
+      if (processed.find(base) != processed.end()) {
+        continue;
+      }
+      processed.insert(base);
+
+      if (!isa<AllocaInst>(base)) continue;
+
+      Value *ArraySize = cast<AllocaInst>(base)->getArraySize();
+
+      BasicBlock &entry = F.getEntryBlock();
+      BasicBlock::iterator bbIter = entry.begin();
+      while (isa<AllocaInst>(bbIter)) ++bbIter;
+
+      IRBuilder<> Builder(&entry);
+      Builder.SetInsertPoint(bbIter);
+
+      PointerType * AITy = cast<AllocaInst>(base)->getType();
+      Value * btiArray = Builder.CreateAlloca(AITy->getElementType(), ArraySize, base->getName() + ".bti");
+      Value * pointerBaseArray = Builder.CreateAlloca(AITy->getElementType(), ArraySize, base->getName() + ".pointer-base");
+      processPointerArray(base, btiArray, pointerBaseArray);
+    }
   }
 
   void getSequentialData(const ConstantDataSequential *cda, void *ptr, uint32_t &offset) {
-- 
2.3.6



More information about the Beignet mailing list