Thread Safety Analysis: major update to thread safety TIL.

Numerous changes, including:
  * Changed the way variables and instructions are handled in basic blocks to
    be more efficient.
  * Eliminated SExprRef.
  * Simplified futures.
  * Fixed documentation.
  * Compute dominator and post dominator trees.

llvm-svn: 217556

1 files changed, 222 insertions, 64 deletions

diff --git a/clang/lib/Analysis/ThreadSafetyTIL.cpp b/clang/lib/Analysis/ThreadSafetyTIL.cpp
index 0bb7d4c2dbb..a15063631d9 100644
--- a/clang/lib/Analysis/ThreadSafetyTIL.cpp
+++ b/clang/lib/Analysis/ThreadSafetyTIL.cpp
@@ -48,12 +48,20 @@ StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op) {
 }
 
 
+SExpr* Future::force() {
+  Status = FS_evaluating;
+  Result = compute();
+  Status = FS_done;
+  return Result;
+}
+
+
 unsigned BasicBlock::addPredecessor(BasicBlock *Pred) {
   unsigned Idx = Predecessors.size();
   Predecessors.reserveCheck(1, Arena);
   Predecessors.push_back(Pred);
-  for (Variable *V : Args) {
-    if (Phi* Ph = dyn_cast<Phi>(V->definition())) {
+  for (SExpr *E : Args) {
+    if (Phi* Ph = dyn_cast<Phi>(E)) {
       Ph->values().reserveCheck(1, Arena);
       Ph->values().push_back(nullptr);
     }
@@ -61,105 +69,73 @@ unsigned BasicBlock::addPredecessor(BasicBlock *Pred) {
   return Idx;
 }
 
+
 void BasicBlock::reservePredecessors(unsigned NumPreds) {
   Predecessors.reserve(NumPreds, Arena);
-  for (Variable *V : Args) {
-    if (Phi* Ph = dyn_cast<Phi>(V->definition())) {
+  for (SExpr *E : Args) {
+    if (Phi* Ph = dyn_cast<Phi>(E)) {
       Ph->values().reserve(NumPreds, Arena);
     }
   }
 }
 
-void BasicBlock::renumberVars() {
-  unsigned VID = 0;
-  for (Variable *V : Args) {
-    V->setID(BlockID, VID++);
-  }
-  for (Variable *V : Instrs) {
-    V->setID(BlockID, VID++);
-  }
-}
-
-void SCFG::renumberVars() {
-  for (BasicBlock *B : Blocks) {
-    B->renumberVars();
-  }
-}
-
-
 
 // If E is a variable, then trace back through any aliases or redundant
 // Phi nodes to find the canonical definition.
 const SExpr *getCanonicalVal(const SExpr *E) {
-  while (auto *V = dyn_cast<Variable>(E)) {
-    const SExpr *D;
-    do {
-      if (V->kind() != Variable::VK_Let)
-        return V;
-      D = V->definition();
-      auto *V2 = dyn_cast<Variable>(D);
-      if (V2)
-        V = V2;
-      else
-        break;
-    } while (true);
-
-    if (ThreadSafetyTIL::isTrivial(D))
-      return D;
-
-    if (const Phi *Ph = dyn_cast<Phi>(D)) {
+  while (true) {
+    if (auto *V = dyn_cast<Variable>(E)) {
+      if (V->kind() == Variable::VK_Let) {
+        E = V->definition();
+        continue;
+      }
+    }
+    if (const Phi *Ph = dyn_cast<Phi>(E)) {
       if (Ph->status() == Phi::PH_SingleVal) {
         E = Ph->values()[0];
         continue;
       }
     }
-    return V;
+    break;
   }
   return E;
 }
 
 
-
 // If E is a variable, then trace back through any aliases or redundant
 // Phi nodes to find the canonical definition.
 // The non-const version will simplify incomplete Phi nodes.
 SExpr *simplifyToCanonicalVal(SExpr *E) {
-  while (auto *V = dyn_cast<Variable>(E)) {
-    SExpr *D;
-    do {
+  while (true) {
+    if (auto *V = dyn_cast<Variable>(E)) {
       if (V->kind() != Variable::VK_Let)
         return V;
-      D = V->definition();
-      auto *V2 = dyn_cast<Variable>(D);
-      if (V2)
-        V = V2;
-      else
-        break;
-    } while (true);
-
-    if (ThreadSafetyTIL::isTrivial(D))
-      return D;
-
-    if (Phi *Ph = dyn_cast<Phi>(D)) {
+      // Eliminate redundant variables, e.g. x = y, or x = 5,
+      // but keep anything more complicated.
+      if (til::ThreadSafetyTIL::isTrivial(V->definition())) {
+        E = V->definition();
+        continue;
+      }
+      return V;
+    }
+    if (auto *Ph = dyn_cast<Phi>(E)) {
       if (Ph->status() == Phi::PH_Incomplete)
-        simplifyIncompleteArg(V, Ph);
-
+        simplifyIncompleteArg(Ph);
+      // Eliminate redundant Phi nodes.
       if (Ph->status() == Phi::PH_SingleVal) {
         E = Ph->values()[0];
         continue;
       }
     }
-    return V;
+    return E;
   }
-  return E;
 }
 
 
-
 // Trace the arguments of an incomplete Phi node to see if they have the same
 // canonical definition.  If so, mark the Phi node as redundant.
 // getCanonicalVal() will recursively call simplifyIncompletePhi().
-void simplifyIncompleteArg(Variable *V, til::Phi *Ph) {
+void simplifyIncompleteArg(til::Phi *Ph) {
   assert(Ph && Ph->status() == Phi::PH_Incomplete);
 
   // eliminate infinite recursion -- assume that this node is not redundant.
@@ -168,18 +144,200 @@ void simplifyIncompleteArg(Variable *V, til::Phi *Ph) {
   SExpr *E0 = simplifyToCanonicalVal(Ph->values()[0]);
   for (unsigned i=1, n=Ph->values().size(); i<n; ++i) {
     SExpr *Ei = simplifyToCanonicalVal(Ph->values()[i]);
-    if (Ei == V)
+    if (Ei == Ph)
       continue;  // Recursive reference to itself.  Don't count.
     if (Ei != E0) {
       return;    // Status is already set to MultiVal.
     }
   }
   Ph->setStatus(Phi::PH_SingleVal);
-  // Eliminate Redundant Phi node.
-  V->setDefinition(Ph->values()[0]);
 }
 
 
+// Renumbers the arguments and instructions to have unique, sequential IDs.
+int BasicBlock::renumberInstrs(int ID) {
+  for (auto *Arg : Args)
+    Arg->setID(this, ID++);
+  for (auto *Instr : Instrs)
+    Instr->setID(this, ID++);
+  TermInstr->setID(this, ID++);
+  return ID;
+}
+
+// Sorts the CFGs blocks using a reverse post-order depth-first traversal.
+// Each block will be written into the Blocks array in order, and its BlockID
+// will be set to the index in the array.  Sorting should start from the entry
+// block, and ID should be the total number of blocks.
+int BasicBlock::topologicalSort(SimpleArray<BasicBlock*>& Blocks, int ID) {
+  if (Visited) return ID;
+  Visited = 1;
+  for (auto *Block : successors())
+    ID = Block->topologicalSort(Blocks, ID);
+  // set ID and update block array in place.
+  // We may lose pointers to unreachable blocks.
+  assert(ID > 0);
+  BlockID = --ID;
+  Blocks[BlockID] = this;
+  return ID;
+}
+
+// Performs a reverse topological traversal, starting from the exit block and
+// following back-edges.  The dominator is serialized before any predecessors,
+// which guarantees that all blocks are serialized after their dominator and
+// before their post-dominator (because it's a reverse topological traversal).
+// ID should be initially set to 0.
+//
+// This sort assumes that (1) dominators have been computed, (2) there are no
+// critical edges, and (3) the entry block is reachable from the exit block
+// and no blocks are accessable via traversal of back-edges from the exit that
+// weren't accessable via forward edges from the entry.
+int BasicBlock::topologicalFinalSort(SimpleArray<BasicBlock*>& Blocks, int ID) {
+  // Visited is assumed to have been set by the topologicalSort.  This pass
+  // assumes !Visited means that we've visited this node before.
+  if (!Visited) return ID;
+  Visited = 0;
+  if (DominatorNode.Parent)
+    ID = DominatorNode.Parent->topologicalFinalSort(Blocks, ID);
+  for (auto *Pred : Predecessors)
+    ID = Pred->topologicalFinalSort(Blocks, ID);
+  assert(ID < Blocks.size());
+  BlockID = ID++;
+  Blocks[BlockID] = this;
+  return ID;
+}
+
+// Computes the immediate dominator of the current block.  Assumes that all of
+// its predecessors have already computed their dominators.  This is achieved
+// by visiting the nodes in topological order.
+void BasicBlock::computeDominator() {
+  BasicBlock *Candidate = nullptr;
+  // Walk backwards from each predecessor to find the common dominator node.
+  for (auto *Pred : Predecessors) {
+    // Skip back-edges
+    if (Pred->BlockID >= BlockID) continue;
+    // If we don't yet have a candidate for dominator yet, take this one.
+    if (Candidate == nullptr) {
+      Candidate = Pred;
+      continue;
+    }
+    // Walk the alternate and current candidate back to find a common ancestor.
+    auto *Alternate = Pred;
+    while (Alternate != Candidate) {
+      if (Candidate->BlockID > Alternate->BlockID)
+        Candidate = Candidate->DominatorNode.Parent;
+      else
+        Alternate = Alternate->DominatorNode.Parent;
+    }
+  }
+  DominatorNode.Parent = Candidate;
+  DominatorNode.SizeOfSubTree = 1;
+}
+
+// Computes the immediate post-dominator of the current block.  Assumes that all
+// of its successors have already computed their post-dominators.  This is
+// achieved visiting the nodes in reverse topological order.
+void BasicBlock::computePostDominator() {
+  BasicBlock *Candidate = nullptr;
+  // Walk back from each predecessor to find the common post-dominator node.
+  for (auto *Succ : successors()) {
+    // Skip back-edges
+    if (Succ->BlockID <= BlockID) continue;
+    // If we don't yet have a candidate for post-dominator yet, take this one.
+    if (Candidate == nullptr) {
+      Candidate = Succ;
+      continue;
+    }
+    // Walk the alternate and current candidate back to find a common ancestor.
+    auto *Alternate = Succ;
+    while (Alternate != Candidate) {
+      if (Candidate->BlockID < Alternate->BlockID)
+        Candidate = Candidate->PostDominatorNode.Parent;
+      else
+        Alternate = Alternate->PostDominatorNode.Parent;
+    }
+  }
+  PostDominatorNode.Parent = Candidate;
+  PostDominatorNode.SizeOfSubTree = 1;
+}
+
+
+// Renumber instructions in all blocks
+void SCFG::renumberInstrs() {
+  int InstrID = 0;
+  for (auto *Block : Blocks)
+    InstrID = Block->renumberInstrs(InstrID);
+}
+
+
+static inline void computeNodeSize(BasicBlock *B,
+                                   BasicBlock::TopologyNode BasicBlock::*TN) {
+  BasicBlock::TopologyNode *N = &(B->*TN);
+  if (N->Parent) {
+    BasicBlock::TopologyNode *P = &(N->Parent->*TN);
+    // Initially set ID relative to the (as yet uncomputed) parent ID
+    N->NodeID = P->SizeOfSubTree;
+    P->SizeOfSubTree += N->SizeOfSubTree;
+  }
+}
+
+static inline void computeNodeID(BasicBlock *B,
+                                 BasicBlock::TopologyNode BasicBlock::*TN) {
+  BasicBlock::TopologyNode *N = &(B->*TN);
+  if (N->Parent) {
+    BasicBlock::TopologyNode *P = &(N->Parent->*TN);
+    N->NodeID += P->NodeID;    // Fix NodeIDs relative to starting node.
+  }
+}
+
+
+// Normalizes a CFG.  Normalization has a few major components:
+// 1) Removing unreachable blocks.
+// 2) Computing dominators and post-dominators
+// 3) Topologically sorting the blocks into the "Blocks" array.
+void SCFG::computeNormalForm() {
+  // Topologically sort the blocks starting from the entry block.
+  int NumUnreachableBlocks = Entry->topologicalSort(Blocks, Blocks.size());
+  if (NumUnreachableBlocks > 0) {
+    // If there were unreachable blocks shift everything down, and delete them.
+    for (size_t I = NumUnreachableBlocks, E = Blocks.size(); I < E; ++I) {
+      size_t NI = I - NumUnreachableBlocks;
+      Blocks[NI] = Blocks[I];
+      Blocks[NI]->BlockID = NI;
+      // FIXME: clean up predecessor pointers to unreachable blocks?
+    }
+    Blocks.drop(NumUnreachableBlocks);
+  }
+
+  // Compute dominators.
+  for (auto *Block : Blocks)
+    Block->computeDominator();
+
+  // Once dominators have been computed, the final sort may be performed.
+  int NumBlocks = Exit->topologicalFinalSort(Blocks, 0);
+  assert(NumBlocks == Blocks.size());
+  (void) NumBlocks;
+
+  // Renumber the instructions now that we have a final sort.
+  renumberInstrs();
+
+  // Compute post-dominators and compute the sizes of each node in the
+  // dominator tree.
+  for (auto *Block : Blocks.reverse()) {
+    Block->computePostDominator();
+    computeNodeSize(Block, &BasicBlock::DominatorNode);
+  }
+  // Compute the sizes of each node in the post-dominator tree and assign IDs in
+  // the dominator tree.
+  for (auto *Block : Blocks) {
+    computeNodeID(Block, &BasicBlock::DominatorNode);
+    computeNodeSize(Block, &BasicBlock::PostDominatorNode);
+  }
+  // Assign IDs in the post-dominator tree.
+  for (auto *Block : Blocks.reverse()) {
+    computeNodeID(Block, &BasicBlock::PostDominatorNode);
+  }
+}
+
 }  // end namespace til
 }  // end namespace threadSafety
 }  // end namespace clang