5 files changed, 138 insertions, 15 deletions

diff --git a/contrib/llvm-project/clang/lib/Analysis/AnalysisDeclContext.cpp b/contrib/llvm-project/clang/lib/Analysis/AnalysisDeclContext.cpp
index d8466ac34a3d..06f1f813aeed 100644
--- a/contrib/llvm-project/clang/lib/Analysis/AnalysisDeclContext.cpp
+++ b/contrib/llvm-project/clang/lib/Analysis/AnalysisDeclContext.cpp
@@ -387,7 +387,7 @@ std::string AnalysisDeclContext::getFunctionName(const Decl *D) {
     OS << ' ' << OMD->getSelector().getAsString() << ']';
   }
 
-  return OS.str();
+  return Str;
 }
 
 LocationContextManager &AnalysisDeclContext::getLocationContextManager() {
diff --git a/contrib/llvm-project/clang/lib/Analysis/CFG.cpp b/contrib/llvm-project/clang/lib/Analysis/CFG.cpp
index abf65e3efce9..9ef3b5b6277a 100644
--- a/contrib/llvm-project/clang/lib/Analysis/CFG.cpp
+++ b/contrib/llvm-project/clang/lib/Analysis/CFG.cpp
@@ -1820,8 +1820,6 @@ void CFGBuilder::addScopesEnd(LocalScope::const_iterator B,
 
   for (VarDecl *VD : llvm::reverse(DeclsWithEndedScope))
     appendScopeEnd(Block, VD, S);
-
-  return;
 }
 
 /// addAutomaticObjDtors - Add to current block automatic objects destructors
diff --git a/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
index bb7eb9971068..413e8d14bf0a 100644
--- a/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ b/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -11,15 +11,82 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include <utility>
 #include <vector>
 
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
+#include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/Support/raw_ostream.h"
 
-using namespace clang;
-using namespace dataflow;
+namespace clang {
+namespace dataflow {
+
+/// Computes the input state for a given basic block by joining the output
+/// states of its predecessors.
+///
+/// Requirements:
+///
+///   All predecessors of `Block` except those with loop back edges must have
+///   already been transferred. States in `BlockStates` that are set to
+///   `llvm::None` represent basic blocks that are not evaluated yet.
+static TypeErasedDataflowAnalysisState computeBlockInputState(
+    std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
+    const CFGBlock &Block, const Environment &InitEnv,
+    TypeErasedDataflowAnalysis &Analysis) {
+  // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
+  // to enable building analyses like computation of dominators that initialize
+  // the state of each basic block differently.
+  TypeErasedDataflowAnalysisState State = {Analysis.typeErasedInitialElement(),
+                                           InitEnv};
+  for (const CFGBlock *Pred : Block.preds()) {
+    // Skip if the `Block` is unreachable or control flow cannot get past it.
+    if (!Pred || Pred->hasNoReturnElement())
+      continue;
+
+    // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
+    // loop back edge to `Block`.
+    const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
+        BlockStates[Pred->getBlockID()];
+    if (!MaybePredState.hasValue())
+      continue;
+
+    const TypeErasedDataflowAnalysisState &PredState =
+        MaybePredState.getValue();
+    Analysis.joinTypeErased(State.Lattice, PredState.Lattice);
+    State.Env.join(PredState.Env);
+  }
+  return State;
+}
+
+TypeErasedDataflowAnalysisState transferBlock(
+    std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
+    const CFGBlock &Block, const Environment &InitEnv,
+    TypeErasedDataflowAnalysis &Analysis,
+    std::function<void(const CFGStmt &,
+                       const TypeErasedDataflowAnalysisState &)>
+        HandleTransferredStmt) {
+  TypeErasedDataflowAnalysisState State =
+      computeBlockInputState(BlockStates, Block, InitEnv, Analysis);
+  for (const CFGElement &Element : Block) {
+    // FIXME: Evaluate other kinds of `CFGElement`.
+    const llvm::Optional<CFGStmt> Stmt = Element.getAs<CFGStmt>();
+    if (!Stmt.hasValue())
+      continue;
+
+    // FIXME: Evaluate the statement contained in `Stmt`.
+
+    State.Lattice = Analysis.transferTypeErased(Stmt.getValue().getStmt(),
+                                                State.Lattice, State.Env);
+    if (HandleTransferredStmt != nullptr)
+      HandleTransferredStmt(Stmt.getValue(), State);
+  }
+  return State;
+}
 
 std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
 runTypeErasedDataflowAnalysis(const CFG &Cfg,
@@ -29,7 +96,59 @@ runTypeErasedDataflowAnalysis(const CFG &Cfg,
   // are specified in the header. This could be done by remembering
   // what options were used to build `Cfg` and asserting on them here.
 
-  // FIXME: Implement work list-based algorithm to compute the fixed
-  // point of `Analysis::transform` for every basic block in `Cfg`.
-  return {};
+  PostOrderCFGView POV(&Cfg);
+  ForwardDataflowWorklist Worklist(Cfg, &POV);
+
+  std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates;
+  BlockStates.resize(Cfg.size(), llvm::None);
+
+  // The entry basic block doesn't contain statements so it can be skipped.
+  const CFGBlock &Entry = Cfg.getEntry();
+  BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
+                                     InitEnv};
+  Worklist.enqueueSuccessors(&Entry);
+
+  // Bugs in lattices and transfer functions can prevent the analysis from
+  // converging. To limit the damage (infinite loops) that these bugs can cause,
+  // limit the number of iterations.
+  // FIXME: Consider making the maximum number of iterations configurable.
+  // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number
+  // of iterations, number of functions that time out, etc.
+  unsigned Iterations = 0;
+  static constexpr unsigned MaxIterations = 1 << 16;
+  while (const CFGBlock *Block = Worklist.dequeue()) {
+    if (++Iterations > MaxIterations) {
+      llvm::errs() << "Maximum number of iterations reached, giving up.\n";
+      break;
+    }
+
+    const llvm::Optional<TypeErasedDataflowAnalysisState> &OldBlockState =
+        BlockStates[Block->getBlockID()];
+    TypeErasedDataflowAnalysisState NewBlockState =
+        transferBlock(BlockStates, *Block, InitEnv, Analysis);
+
+    if (OldBlockState.hasValue() &&
+        Analysis.isEqualTypeErased(OldBlockState.getValue().Lattice,
+                                   NewBlockState.Lattice) &&
+        OldBlockState->Env == NewBlockState.Env) {
+      // The state of `Block` didn't change after transfer so there's no need to
+      // revisit its successors.
+      continue;
+    }
+
+    BlockStates[Block->getBlockID()] = std::move(NewBlockState);
+
+    // Do not add unreachable successor blocks to `Worklist`.
+    if (Block->hasNoReturnElement())
+      continue;
+
+    Worklist.enqueueSuccessors(Block);
+  }
+  // FIXME: Consider evaluating unreachable basic blocks (those that have a
+  // state set to `llvm::None` at this point) to also analyze dead code.
+
+  return BlockStates;
 }
+
+} // namespace dataflow
+} // namespace clang
diff --git a/contrib/llvm-project/clang/lib/Analysis/ThreadSafety.cpp b/contrib/llvm-project/clang/lib/Analysis/ThreadSafety.cpp
index b196ffa73cbf..9cc990bd35a3 100644
--- a/contrib/llvm-project/clang/lib/Analysis/ThreadSafety.cpp
+++ b/contrib/llvm-project/clang/lib/Analysis/ThreadSafety.cpp
@@ -418,7 +418,6 @@ public:
 private:
   Context::Factory ContextFactory;
   std::vector<VarDefinition> VarDefinitions;
-  std::vector<unsigned> CtxIndices;
   std::vector<std::pair<const Stmt *, Context>> SavedContexts;
 
 public:
@@ -731,8 +730,6 @@ void LocalVariableMap::traverseCFG(CFG *CFGraph,
                                    std::vector<CFGBlockInfo> &BlockInfo) {
   PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
 
-  CtxIndices.resize(CFGraph->getNumBlockIDs());
-
   for (const auto *CurrBlock : *SortedGraph) {
     unsigned CurrBlockID = CurrBlock->getBlockID();
     CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID];
diff --git a/contrib/llvm-project/clang/lib/Analysis/UninitializedValues.cpp b/contrib/llvm-project/clang/lib/Analysis/UninitializedValues.cpp
index 67cd39728c35..a38ae34f4b81 100644
--- a/contrib/llvm-project/clang/lib/Analysis/UninitializedValues.cpp
+++ b/contrib/llvm-project/clang/lib/Analysis/UninitializedValues.cpp
@@ -591,8 +591,8 @@ public:
 
         if (AtPredExit == MayUninitialized) {
           // If the predecessor's terminator is an "asm goto" that initializes
-          // the variable, then it won't be counted as "initialized" on the
-          // non-fallthrough paths.
+          // the variable, then don't count it as "initialized" on the indirect
+          // paths.
           CFGTerminator term = Pred->getTerminator();
           if (const auto *as = dyn_cast_or_null<GCCAsmStmt>(term.getStmt())) {
             const CFGBlock *fallthrough = *Pred->succ_begin();
@@ -810,13 +810,22 @@ void TransferFunctions::VisitGCCAsmStmt(GCCAsmStmt *as) {
   if (!as->isAsmGoto())
     return;
 
-  for (const Expr *o : as->outputs())
-    if (const VarDecl *VD = findVar(o).getDecl())
+  ASTContext &C = ac.getASTContext();
+  for (const Expr *O : as->outputs()) {
+    const Expr *Ex = stripCasts(C, O);
+
+    // Strip away any unary operators. Invalid l-values are reported by other
+    // semantic analysis passes.
+    while (const auto *UO = dyn_cast<UnaryOperator>(Ex))
+      Ex = stripCasts(C, UO->getSubExpr());
+
+    if (const VarDecl *VD = findVar(Ex).getDecl())
       if (vals[VD] != Initialized)
         // If the variable isn't initialized by the time we get here, then we
         // mark it as potentially uninitialized for those cases where it's used
         // on an indirect path, where it's not guaranteed to be defined.
         vals[VD] = MayUninitialized;
+  }
 }
 
 void TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) {