Expose must alias information for global variables, implementing: DSGraph/mustalias.ll

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6973 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 86 insertions, 46 deletions

diff --git a/lib/Analysis/DataStructure/DataStructureAA.cpp b/lib/Analysis/DataStructure/DataStructureAA.cpp
index f39e2ad9b6..bb28389e56 100644
--- a/lib/Analysis/DataStructure/DataStructureAA.cpp
+++ b/lib/Analysis/DataStructure/DataStructureAA.cpp
@@ -40,9 +40,13 @@ namespace {
     // Implement the AliasAnalysis API
     //  
 
-    // alias - This is the only method here that does anything interesting...
     AliasResult alias(const Value *V1, unsigned V1Size,
                       const Value *V2, unsigned V2Size);
+
+    void getMustAliases(Value *P, std::vector<Value*> &RetVals);
+
+  private:
+    DSGraph *getGraphForValue(const Value *V);
   };
 
   // Register the pass...
@@ -52,66 +56,78 @@ namespace {
   RegisterAnalysisGroup<AliasAnalysis, DSAA> Y;
 }
 
-// getValueFunction - return the function containing the specified value if
-// available, or null otherwise.
+// getGraphForValue - Return the DSGraph to use for queries about the specified
+// value...
 //
-static const Function *getValueFunction(const Value *V) {
+DSGraph *DSAA::getGraphForValue(const Value *V) {
   if (const Instruction *I = dyn_cast<Instruction>(V))
-    return I->getParent()->getParent();
+    return &TD->getDSGraph(*I->getParent()->getParent());
   else if (const Argument *A = dyn_cast<Argument>(V))
-    return A->getParent();
+    return &TD->getDSGraph(*A->getParent());
   else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V))
-    return BB->getParent();
+    return &TD->getDSGraph(*BB->getParent());
   return 0;
 }
 
+// isSinglePhysicalObject - For now, the only case that we know that there is
+// only one memory object in the node is when there is a single global in the
+// node, and the only composition bit set is Global.
+//
+static bool isSinglePhysicalObject(DSNode *N) {
+  assert(N->isComplete() && "Can only tell if this is a complete object!");
+  return N->isGlobalNode() && N->getGlobals().size() == 1 &&
+         !N->isHeapNode() && !N->isAllocaNode() && !N->isUnknownNode();
+}
+
 // alias - This is the only method here that does anything interesting...
 AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size,
                                        const Value *V2, unsigned V2Size) {
   if (V1 == V2) return MustAlias;
 
-  const Function *F1 = getValueFunction(V1);
-  const Function *F2 = getValueFunction(V2);
-  assert((!F1 || !F2 || F1 == F2) && "Alias query for 2 different functions?");
+  DSGraph *G1 = getGraphForValue(V1);
+  DSGraph *G2 = getGraphForValue(V2);
+  assert((!G1 || !G2 || G1 == G2) && "Alias query for 2 different functions?");
   
-  if (F2) F1 = F2;
-  if (F1) {
-    // Get the graph for a function...
-    DSGraph &G = TD->getDSGraph(*F1);
-    hash_map<Value*, DSNodeHandle> &GSM = G.getScalarMap();
-    hash_map<Value*, DSNodeHandle>::iterator I = GSM.find((Value*)V1);
-    if (I != GSM.end()) {
-      assert(I->second.getNode() && "Scalar map points to null node?");
-      hash_map<Value*, DSNodeHandle>::iterator J = GSM.find((Value*)V2);
-      if (J != GSM.end()) {
-        assert(J->second.getNode() && "Scalar map points to null node?");
-
-        DSNode  *N1 = I->second.getNode(),  *N2 = J->second.getNode();
-        unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset();
+  // Get the graph to use...
+  DSGraph &G = *(G1 ? G1 : (G2 ? G2 : &TD->getGlobalsGraph()));
+
+  const DSGraph::ScalarMapTy &GSM = G.getScalarMap();
+  DSGraph::ScalarMapTy::const_iterator I = GSM.find((Value*)V1);
+  if (I != GSM.end()) {
+    assert(I->second.getNode() && "Scalar map points to null node?");
+    DSGraph::ScalarMapTy::const_iterator J = GSM.find((Value*)V2);
+    if (J != GSM.end()) {
+      assert(J->second.getNode() && "Scalar map points to null node?");
+
+      DSNode  *N1 = I->second.getNode(),  *N2 = J->second.getNode();
+      unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset();
         
-        // We can only make a judgement of one of the nodes is complete...
-        if (N1->isComplete() || N2->isComplete()) {
-          if (N1 != N2)
-            return NoAlias;   // Completely different nodes.
-
-          // Both point to the same node and same offset, and there is only one
-          // physical memory object represented in the node, return must alias.
-          //if (O1 == O2 && !N1->isMultiObject())
-          //  return MustAlias; // Exactly the same object & offset
-
-          // See if they point to different offsets...  if so, we may be able to
-          // determine that they do not alias...
-          if (O1 != O2) {
-            if (O2 < O1) {    // Ensure that O1 <= O2
-              std::swap(V1, V2);
-              std::swap(O1, O2);
-              std::swap(V1Size, V2Size);
-            }
-
-            // FIXME: This is not correct because we do not handle array
-            // indexing correctly with this check!
-            //if (O1+V1Size <= O2) return NoAlias;
+      // We can only make a judgement of one of the nodes is complete...
+      if (N1->isComplete() || N2->isComplete()) {
+        if (N1 != N2)
+          return NoAlias;   // Completely different nodes.
+
+        // Both point to the same node and same offset, and there is only one
+        // physical memory object represented in the node, return must alias.
+        //
+        // FIXME: This isn't correct because we do not handle array indexing
+        // correctly.
+
+        if (O1 == O2 && isSinglePhysicalObject(N1))
+          return MustAlias; // Exactly the same object & offset
+
+        // See if they point to different offsets...  if so, we may be able to
+        // determine that they do not alias...
+        if (O1 != O2) {
+          if (O2 < O1) {    // Ensure that O1 <= O2
+            std::swap(V1, V2);
+            std::swap(O1, O2);
+            std::swap(V1Size, V2Size);
           }
+
+          // FIXME: This is not correct because we do not handle array
+          // indexing correctly with this check!
+          //if (O1+V1Size <= O2) return NoAlias;
         }
       }
     }
@@ -121,3 +137,27 @@ AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size,
   // global queries...
   return getAnalysis<AliasAnalysis>().alias(V1, V1Size, V2, V2Size);
 }
+
+
+/// getMustAliases - If there are any pointers known that must alias this
+/// pointer, return them now.  This allows alias-set based alias analyses to
+/// perform a form a value numbering (which is exposed by load-vn).  If an alias
+/// analysis supports this, it should ADD any must aliased pointers to the
+/// specified vector.
+///
+void DSAA::getMustAliases(Value *P, std::vector<Value*> &RetVals) {
+  DSGraph *G = getGraphForValue(P);
+  if (!G) G = &TD->getGlobalsGraph();
+  
+  // The only must alias information we can currently determine occurs when the
+  // node for P is a global node with only one entry.
+  const DSGraph::ScalarMapTy &GSM = G->getScalarMap();
+  DSGraph::ScalarMapTy::const_iterator I = GSM.find(P);
+  if (I != GSM.end()) {
+    DSNode *N = I->second.getNode();
+    if (isSinglePhysicalObject(N))
+      RetVals.push_back(N->getGlobals()[0]);
+  }
+
+  return getAnalysis<AliasAnalysis>().getMustAliases(P, RetVals);
+}