Export clang-format16 via ydblib project

6e6be3a95868fde888d801b7590af4044049563f

18 files changed, 5725 insertions, 0 deletions

diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h
new file mode 100644
index 0000000000..15abbb3d58
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h
@@ -0,0 +1,61 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- CFGReachabilityAnalysis.h - Basic reachability analysis --*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a flow-sensitive, (mostly) path-insensitive reachability
+// analysis based on Clang's CFGs.  Clients can query if a given basic block
+// is reachable within the CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace clang {
+
+class CFG;
+class CFGBlock;
+
+// A class that performs reachability queries for CFGBlocks. Several internal
+// checks in this checker require reachability information. The requests all
+// tend to have a common destination, so we lazily do a predecessor search
+// from the destination node and cache the results to prevent work
+// duplication.
+class CFGReverseBlockReachabilityAnalysis {
+  using ReachableSet = llvm::BitVector;
+  using ReachableMap = llvm::DenseMap<unsigned, ReachableSet>;
+
+  ReachableSet analyzed;
+  ReachableMap reachable;
+
+public:
+  CFGReverseBlockReachabilityAnalysis(const CFG &cfg);
+
+  /// Returns true if the block 'Dst' can be reached from block 'Src'.
+  bool isReachable(const CFGBlock *Src, const CFGBlock *Dst);
+
+private:
+  void mapReachability(const CFGBlock *Dst);
+};
+
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/CalledOnceCheck.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/CalledOnceCheck.h
new file mode 100644
index 0000000000..a39d56f9e3
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/CalledOnceCheck.h
@@ -0,0 +1,137 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- CalledOnceCheck.h - Check 'called once' parameters -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines a check for function-like parameters that should be
+//  called exactly one time.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CALLEDONCECHECK_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_CALLEDONCECHECK_H
+
+namespace clang {
+
+class AnalysisDeclContext;
+class BlockDecl;
+class CFG;
+class Decl;
+class Expr;
+class ParmVarDecl;
+class Stmt;
+
+/// Classification of situations when parameter is not called on every path.
+/// \enum IfThen -- then branch of the if statement has no call.
+/// \enum IfElse -- else branch of the if statement has no call.
+/// \enum Switch -- one of the switch cases doesn't have a call.
+/// \enum SwitchSkipped -- there is no call if none of the cases appies.
+/// \enum LoopEntered -- no call when the loop is entered.
+/// \enum LoopSkipped -- no call when the loop is not entered.
+/// \enum FallbackReason -- fallback case when we were not able to figure out
+/// the reason.
+enum class NeverCalledReason {
+  IfThen,
+  IfElse,
+  Switch,
+  SwitchSkipped,
+  LoopEntered,
+  LoopSkipped,
+  FallbackReason,
+  LARGEST_VALUE = FallbackReason
+};
+
+class CalledOnceCheckHandler {
+public:
+  CalledOnceCheckHandler() = default;
+  virtual ~CalledOnceCheckHandler() = default;
+
+  /// Called when parameter is called twice.
+  /// \param Parameter -- parameter that should be called once.
+  /// \param Call -- call to report the warning.
+  /// \param PrevCall -- previous call.
+  /// \param IsCompletionHandler -- true, if parameter is a completion handler.
+  /// \param Poised -- true, if the second call is guaranteed to happen after
+  /// the first call.
+  virtual void handleDoubleCall(const ParmVarDecl *Parameter, const Expr *Call,
+                                const Expr *PrevCall, bool IsCompletionHandler,
+                                bool Poised) {}
+
+  /// Called when parameter is not called at all.
+  /// \param Parameter -- parameter that should be called once.
+  /// \param IsCompletionHandler -- true, if parameter is a completion handler.
+  virtual void handleNeverCalled(const ParmVarDecl *Parameter,
+                                 bool IsCompletionHandler) {}
+
+  /// Called when captured parameter is not called at all.
+  /// \param Parameter -- parameter that should be called once.
+  /// \param Where -- declaration that captures \p Parameter
+  /// \param IsCompletionHandler -- true, if parameter is a completion handler.
+  virtual void handleCapturedNeverCalled(const ParmVarDecl *Parameter,
+                                         const Decl *Where,
+                                         bool IsCompletionHandler) {}
+
+  /// Called when parameter is not called on one of the paths.
+  /// Usually we try to find a statement that is the least common ancestor of
+  /// the path containing the call and not containing the call.  This helps us
+  /// to pinpoint a bad path for the user.
+  /// \param Parameter -- parameter that should be called once.
+  /// \param Function -- function declaration where the problem occurred.
+  /// \param Where -- the least common ancestor statement.
+  /// \param Reason -- a reason describing the path without a call.
+  /// \param IsCalledDirectly -- true, if parameter actually gets called on
+  /// the other path.  It is opposed to be used in some other way (added to some
+  /// collection, passed as a parameter, etc.).
+  /// \param IsCompletionHandler -- true, if parameter is a completion handler.
+  virtual void handleNeverCalled(const ParmVarDecl *Parameter,
+                                 const Decl *Function, const Stmt *Where,
+                                 NeverCalledReason Reason,
+                                 bool IsCalledDirectly,
+                                 bool IsCompletionHandler) {}
+
+  /// Called when the block is guaranteed to be called exactly once.
+  /// It means that we can be stricter with what we report on that block.
+  /// \param Block -- block declaration that is known to be called exactly once.
+  virtual void
+  handleBlockThatIsGuaranteedToBeCalledOnce(const BlockDecl *Block) {}
+
+  /// Called when the block has no guarantees about how many times it can get
+  /// called.
+  /// It means that we should be more lenient with reporting warnings in it.
+  /// \param Block -- block declaration in question.
+  virtual void handleBlockWithNoGuarantees(const BlockDecl *Block) {}
+};
+
+/// Check given CFG for 'called once' parameter violations.
+///
+/// It traverses the function and tracks how such parameters are used.
+/// It detects two main violations:
+///   * parameter is called twice
+///   * parameter is not called
+///
+/// \param AC -- context.
+/// \param Handler -- a handler for found violations.
+/// \param CheckConventionalParameters -- true, if we want to check parameters
+/// not explicitly marked as 'called once', but having the same requirements
+/// according to conventions.
+void checkCalledOnceParameters(AnalysisDeclContext &AC,
+                               CalledOnceCheckHandler &Handler,
+                               bool CheckConventionalParameters);
+
+} // end namespace clang
+
+#endif /* LLVM_CLANG_ANALYSIS_ANALYSES_CALLEDONCECHECK_H */
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/Consumed.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/Consumed.h
new file mode 100644
index 0000000000..e45a3f75e0
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/Consumed.h
@@ -0,0 +1,282 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- Consumed.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// A intra-procedural analysis for checking consumed properties.  This is based,
+// in part, on research on linear types.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H
+
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Basic/PartialDiagnostic.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include <list>
+#include <memory>
+#include <utility>
+#include <vector>
+
+namespace clang {
+
+class AnalysisDeclContext;
+class CXXBindTemporaryExpr;
+class FunctionDecl;
+class PostOrderCFGView;
+class Stmt;
+class VarDecl;
+
+namespace consumed {
+
+  class ConsumedStmtVisitor;
+
+  enum ConsumedState {
+    // No state information for the given variable.
+    CS_None,
+
+    CS_Unknown,
+    CS_Unconsumed,
+    CS_Consumed
+  };
+
+  using OptionalNotes = SmallVector<PartialDiagnosticAt, 1>;
+  using DelayedDiag = std::pair<PartialDiagnosticAt, OptionalNotes>;
+  using DiagList = std::list<DelayedDiag>;
+
+  class ConsumedWarningsHandlerBase {
+  public:
+    virtual ~ConsumedWarningsHandlerBase();
+
+    /// Emit the warnings and notes left by the analysis.
+    virtual void emitDiagnostics() {}
+
+    /// Warn that a variable's state doesn't match at the entry and exit
+    /// of a loop.
+    ///
+    /// \param Loc -- The location of the end of the loop.
+    ///
+    /// \param VariableName -- The name of the variable that has a mismatched
+    /// state.
+    virtual void warnLoopStateMismatch(SourceLocation Loc,
+                                       StringRef VariableName) {}
+
+    /// Warn about parameter typestate mismatches upon return.
+    ///
+    /// \param Loc -- The SourceLocation of the return statement.
+    ///
+    /// \param ExpectedState -- The state the return value was expected to be
+    /// in.
+    ///
+    /// \param ObservedState -- The state the return value was observed to be
+    /// in.
+    virtual void warnParamReturnTypestateMismatch(SourceLocation Loc,
+                                                  StringRef VariableName,
+                                                  StringRef ExpectedState,
+                                                  StringRef ObservedState) {}
+
+    // FIXME: Add documentation.
+    virtual void warnParamTypestateMismatch(SourceLocation LOC,
+                                            StringRef ExpectedState,
+                                            StringRef ObservedState) {}
+
+    // FIXME: This can be removed when the attr propagation fix for templated
+    //        classes lands.
+    /// Warn about return typestates set for unconsumable types.
+    ///
+    /// \param Loc -- The location of the attributes.
+    ///
+    /// \param TypeName -- The name of the unconsumable type.
+    virtual void warnReturnTypestateForUnconsumableType(SourceLocation Loc,
+                                                        StringRef TypeName) {}
+
+    /// Warn about return typestate mismatches.
+    ///
+    /// \param Loc -- The SourceLocation of the return statement.
+    ///
+    /// \param ExpectedState -- The state the return value was expected to be
+    /// in.
+    ///
+    /// \param ObservedState -- The state the return value was observed to be
+    /// in.
+    virtual void warnReturnTypestateMismatch(SourceLocation Loc,
+                                             StringRef ExpectedState,
+                                             StringRef ObservedState) {}
+
+    /// Warn about use-while-consumed errors.
+    /// \param MethodName -- The name of the method that was incorrectly
+    /// invoked.
+    ///
+    /// \param State -- The state the object was used in.
+    ///
+    /// \param Loc -- The SourceLocation of the method invocation.
+    virtual void warnUseOfTempInInvalidState(StringRef MethodName,
+                                             StringRef State,
+                                             SourceLocation Loc) {}
+
+    /// Warn about use-while-consumed errors.
+    /// \param MethodName -- The name of the method that was incorrectly
+    /// invoked.
+    ///
+    /// \param State -- The state the object was used in.
+    ///
+    /// \param VariableName -- The name of the variable that holds the unique
+    /// value.
+    ///
+    /// \param Loc -- The SourceLocation of the method invocation.
+    virtual void warnUseInInvalidState(StringRef MethodName,
+                                       StringRef VariableName,
+                                       StringRef State,
+                                       SourceLocation Loc) {}
+  };
+
+  class ConsumedStateMap {
+    using VarMapType = llvm::DenseMap<const VarDecl *, ConsumedState>;
+    using TmpMapType =
+        llvm::DenseMap<const CXXBindTemporaryExpr *, ConsumedState>;
+
+  protected:
+    bool Reachable = true;
+    const Stmt *From = nullptr;
+    VarMapType VarMap;
+    TmpMapType TmpMap;
+
+  public:
+    ConsumedStateMap() = default;
+    ConsumedStateMap(const ConsumedStateMap &Other)
+        : Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap) {}
+
+    /// Warn if any of the parameters being tracked are not in the state
+    /// they were declared to be in upon return from a function.
+    void checkParamsForReturnTypestate(SourceLocation BlameLoc,
+      ConsumedWarningsHandlerBase &WarningsHandler) const;
+
+    /// Clear the TmpMap.
+    void clearTemporaries();
+
+    /// Get the consumed state of a given variable.
+    ConsumedState getState(const VarDecl *Var) const;
+
+    /// Get the consumed state of a given temporary value.
+    ConsumedState getState(const CXXBindTemporaryExpr *Tmp) const;
+
+    /// Merge this state map with another map.
+    void intersect(const ConsumedStateMap &Other);
+
+    void intersectAtLoopHead(const CFGBlock *LoopHead, const CFGBlock *LoopBack,
+      const ConsumedStateMap *LoopBackStates,
+      ConsumedWarningsHandlerBase &WarningsHandler);
+
+    /// Return true if this block is reachable.
+    bool isReachable() const { return Reachable; }
+
+    /// Mark the block as unreachable.
+    void markUnreachable();
+
+    /// Set the source for a decision about the branching of states.
+    /// \param Source -- The statement that was the origin of a branching
+    /// decision.
+    void setSource(const Stmt *Source) { this->From = Source; }
+
+    /// Set the consumed state of a given variable.
+    void setState(const VarDecl *Var, ConsumedState State);
+
+    /// Set the consumed state of a given temporary value.
+    void setState(const CXXBindTemporaryExpr *Tmp, ConsumedState State);
+
+    /// Remove the temporary value from our state map.
+    void remove(const CXXBindTemporaryExpr *Tmp);
+
+    /// Tests to see if there is a mismatch in the states stored in two
+    /// maps.
+    ///
+    /// \param Other -- The second map to compare against.
+    bool operator!=(const ConsumedStateMap *Other) const;
+  };
+
+  class ConsumedBlockInfo {
+    std::vector<std::unique_ptr<ConsumedStateMap>> StateMapsArray;
+    std::vector<unsigned int> VisitOrder;
+
+  public:
+    ConsumedBlockInfo() = default;
+
+    ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph)
+        : StateMapsArray(NumBlocks), VisitOrder(NumBlocks, 0) {
+      unsigned int VisitOrderCounter = 0;
+      for (const auto BI : *SortedGraph)
+        VisitOrder[BI->getBlockID()] = VisitOrderCounter++;
+    }
+
+    bool allBackEdgesVisited(const CFGBlock *CurrBlock,
+                             const CFGBlock *TargetBlock);
+
+    void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap,
+                 std::unique_ptr<ConsumedStateMap> &OwnedStateMap);
+    void addInfo(const CFGBlock *Block,
+                 std::unique_ptr<ConsumedStateMap> StateMap);
+
+    ConsumedStateMap* borrowInfo(const CFGBlock *Block);
+
+    void discardInfo(const CFGBlock *Block);
+
+    std::unique_ptr<ConsumedStateMap> getInfo(const CFGBlock *Block);
+
+    bool isBackEdge(const CFGBlock *From, const CFGBlock *To);
+    bool isBackEdgeTarget(const CFGBlock *Block);
+  };
+
+  /// A class that handles the analysis of uniqueness violations.
+  class ConsumedAnalyzer {
+    ConsumedBlockInfo BlockInfo;
+    std::unique_ptr<ConsumedStateMap> CurrStates;
+
+    ConsumedState ExpectedReturnState;
+
+    void determineExpectedReturnState(AnalysisDeclContext &AC,
+                                      const FunctionDecl *D);
+    bool splitState(const CFGBlock *CurrBlock,
+                    const ConsumedStmtVisitor &Visitor);
+
+  public:
+    ConsumedWarningsHandlerBase &WarningsHandler;
+
+    ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler)
+        : WarningsHandler(WarningsHandler) {}
+
+    ConsumedState getExpectedReturnState() const { return ExpectedReturnState; }
+
+    /// Check a function's CFG for consumed violations.
+    ///
+    /// We traverse the blocks in the CFG, keeping track of the state of each
+    /// value who's type has uniquness annotations.  If methods are invoked in
+    /// the wrong state a warning is issued.  Each block in the CFG is traversed
+    /// exactly once.
+    void run(AnalysisDeclContext &AC);
+  };
+
+} // namespace consumed
+
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/Dominators.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/Dominators.h
new file mode 100644
index 0000000000..8683e4f013
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/Dominators.h
@@ -0,0 +1,328 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//- Dominators.h - Implementation of dominators tree for Clang CFG -*- C++ -*-//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the dominators tree functionality for Clang CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
+
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/Support/GenericIteratedDominanceFrontier.h"
+#include "llvm/Support/GenericDomTree.h"
+#include "llvm/Support/GenericDomTreeConstruction.h"
+#include "llvm/Support/raw_ostream.h"
+
+// FIXME: There is no good reason for the domtree to require a print method
+// which accepts an LLVM Module, so remove this (and the method's argument that
+// needs it) when that is fixed.
+
+namespace llvm {
+
+class Module;
+
+} // namespace llvm
+
+namespace clang {
+
+using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;
+
+/// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
+template <bool IsPostDom>
+class CFGDominatorTreeImpl : public ManagedAnalysis {
+  virtual void anchor();
+
+public:
+  using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
+
+  CFGDominatorTreeImpl() = default;
+
+  CFGDominatorTreeImpl(CFG *cfg) {
+    buildDominatorTree(cfg);
+  }
+
+  ~CFGDominatorTreeImpl() override = default;
+
+  DominatorTreeBase &getBase() { return DT; }
+
+  CFG *getCFG() { return cfg; }
+
+  /// \returns the root CFGBlock of the dominators tree.
+  CFGBlock *getRoot() const {
+    return DT.getRoot();
+  }
+
+  /// \returns the root DomTreeNode, which is the wrapper for CFGBlock.
+  DomTreeNode *getRootNode() {
+    return DT.getRootNode();
+  }
+
+  /// Compares two dominator trees.
+  /// \returns false if the other dominator tree matches this dominator tree,
+  /// false otherwise.
+  bool compare(CFGDominatorTreeImpl &Other) const {
+    DomTreeNode *R = getRootNode();
+    DomTreeNode *OtherR = Other.getRootNode();
+
+    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
+      return true;
+
+    if (DT.compare(Other.getBase()))
+      return true;
+
+    return false;
+  }
+
+  /// Builds the dominator tree for a given CFG.
+  void buildDominatorTree(CFG *cfg) {
+    assert(cfg);
+    this->cfg = cfg;
+    DT.recalculate(*cfg);
+  }
+
+  /// Dumps immediate dominators for each block.
+  void dump() {
+    llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")
+                 << "dominance tree (Node#,IDom#):\n";
+    for (CFG::const_iterator I = cfg->begin(),
+        E = cfg->end(); I != E; ++I) {
+
+      assert(*I &&
+             "LLVM's Dominator tree builder uses nullpointers to signify the "
+             "virtual root!");
+
+      DomTreeNode *IDom = DT.getNode(*I)->getIDom();
+      if (IDom && IDom->getBlock())
+        llvm::errs() << "(" << (*I)->getBlockID()
+                     << ","
+                     << IDom->getBlock()->getBlockID()
+                     << ")\n";
+      else {
+        bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
+        bool IsExitBlock = *I == &(*I)->getParent()->getExit();
+
+        bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock;
+        bool IsPostDomTreeRoot =
+            IDom && !IDom->getBlock() && IsPostDom && IsExitBlock;
+
+        assert((IsDomTreeRoot || IsPostDomTreeRoot) &&
+               "If the immediate dominator node is nullptr, the CFG block "
+               "should be the exit point (since it's the root of the dominator "
+               "tree), or if the CFG block it refers to is a nullpointer, it "
+               "must be the entry block (since it's the root of the post "
+               "dominator tree)");
+
+        (void)IsDomTreeRoot;
+        (void)IsPostDomTreeRoot;
+
+        llvm::errs() << "(" << (*I)->getBlockID()
+                     << "," << (*I)->getBlockID() << ")\n";
+      }
+    }
+  }
+
+  /// Tests whether \p A dominates \p B.
+  /// Note a block always dominates itself.
+  bool dominates(const CFGBlock *A, const CFGBlock *B) const {
+    return DT.dominates(A, B);
+  }
+
+  /// Tests whether \p A properly dominates \p B.
+  /// \returns false if \p A is the same block as \p B, otherwise whether A
+  /// dominates B.
+  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
+    return DT.properlyDominates(A, B);
+  }
+
+  /// \returns the nearest common dominator CFG block for CFG block \p A and \p
+  /// B. If there is no such block then return NULL.
+  CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
+    return DT.findNearestCommonDominator(A, B);
+  }
+
+  const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
+                                             const CFGBlock *B) {
+    return DT.findNearestCommonDominator(A, B);
+  }
+
+  /// Update the dominator tree information when a node's immediate dominator
+  /// changes.
+  void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
+    DT.changeImmediateDominator(N, NewIDom);
+  }
+
+  /// Tests whether \p A is reachable from the entry block.
+  bool isReachableFromEntry(const CFGBlock *A) {
+    return DT.isReachableFromEntry(A);
+  }
+
+  /// Releases the memory held by the dominator tree.
+  virtual void releaseMemory() { DT.reset(); }
+
+  /// Converts the dominator tree to human readable form.
+  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
+    DT.print(OS);
+  }
+
+private:
+  CFG *cfg;
+  DominatorTreeBase DT;
+};
+
+using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
+using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
+
+template<> void CFGDominatorTreeImpl<true>::anchor();
+template<> void CFGDominatorTreeImpl<false>::anchor();
+
+} // end of namespace clang
+
+namespace llvm {
+namespace IDFCalculatorDetail {
+
+/// Specialize ChildrenGetterTy to skip nullpointer successors.
+template <bool IsPostDom>
+struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
+  using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef;
+  using ChildrenTy = SmallVector<NodeRef, 8>;
+
+  ChildrenTy get(const NodeRef &N) {
+    using OrderedNodeTy =
+        typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
+
+    auto Children = children<OrderedNodeTy>(N);
+    ChildrenTy Ret{Children.begin(), Children.end()};
+    llvm::erase_value(Ret, nullptr);
+    return Ret;
+  }
+};
+
+} // end of namespace IDFCalculatorDetail
+} // end of namespace llvm
+
+namespace clang {
+
+class ControlDependencyCalculator : public ManagedAnalysis {
+  using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
+  using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;
+  using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
+
+  CFGPostDomTree PostDomTree;
+  IDFCalculator IDFCalc;
+
+  llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
+
+public:
+  ControlDependencyCalculator(CFG *cfg)
+    : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
+
+  const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
+
+  // Lazily retrieves the set of control dependencies to \p A.
+  const CFGBlockVector &getControlDependencies(CFGBlock *A) {
+    auto It = ControlDepenencyMap.find(A);
+    if (It == ControlDepenencyMap.end()) {
+      CFGBlockSet DefiningBlock = {A};
+      IDFCalc.setDefiningBlocks(DefiningBlock);
+
+      CFGBlockVector ControlDependencies;
+      IDFCalc.calculate(ControlDependencies);
+
+      It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
+    }
+
+    assert(It != ControlDepenencyMap.end());
+    return It->second;
+  }
+
+  /// Whether \p A is control dependent on \p B.
+  bool isControlDependent(CFGBlock *A, CFGBlock *B) {
+    return llvm::is_contained(getControlDependencies(A), B);
+  }
+
+  // Dumps immediate control dependencies for each block.
+  LLVM_DUMP_METHOD void dump() {
+    CFG *cfg = PostDomTree.getCFG();
+    llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
+    for (CFGBlock *BB : *cfg) {
+
+      assert(BB &&
+             "LLVM's Dominator tree builder uses nullpointers to signify the "
+             "virtual root!");
+
+      for (CFGBlock *isControlDependency : getControlDependencies(BB))
+        llvm::errs() << "(" << BB->getBlockID()
+                     << ","
+                     << isControlDependency->getBlockID()
+                     << ")\n";
+    }
+  }
+};
+
+} // namespace clang
+
+namespace llvm {
+
+//===-------------------------------------
+/// DominatorTree GraphTraits specialization so the DominatorTree can be
+/// iterable by generic graph iterators.
+///
+template <> struct GraphTraits<clang::DomTreeNode *> {
+  using NodeRef = ::clang::DomTreeNode *;
+  using ChildIteratorType = ::clang::DomTreeNode::const_iterator;
+
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
+
+  using nodes_iterator =
+      llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
+
+  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
+    return nodes_iterator(df_begin(getEntryNode(N)));
+  }
+
+  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
+    return nodes_iterator(df_end(getEntryNode(N)));
+  }
+};
+
+template <> struct GraphTraits<clang::CFGDomTree *>
+    : public GraphTraits<clang::DomTreeNode *> {
+  static NodeRef getEntryNode(clang::CFGDomTree *DT) {
+    return DT->getRootNode();
+  }
+
+  static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
+    return nodes_iterator(df_begin(getEntryNode(N)));
+  }
+
+  static nodes_iterator nodes_end(clang::CFGDomTree *N) {
+    return nodes_iterator(df_end(getEntryNode(N)));
+  }
+};
+
+} // namespace llvm
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h
new file mode 100644
index 0000000000..5771fcc526
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h
@@ -0,0 +1,108 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===---------- ExprMutationAnalyzer.h ------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_EXPRMUTATIONANALYZER_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_EXPRMUTATIONANALYZER_H
+
+#include <type_traits>
+
+#include "clang/AST/AST.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace clang {
+
+class FunctionParmMutationAnalyzer;
+
+/// Analyzes whether any mutative operations are applied to an expression within
+/// a given statement.
+class ExprMutationAnalyzer {
+public:
+  ExprMutationAnalyzer(const Stmt &Stm, ASTContext &Context)
+      : Stm(Stm), Context(Context) {}
+
+  bool isMutated(const Expr *Exp) { return findMutation(Exp) != nullptr; }
+  bool isMutated(const Decl *Dec) { return findMutation(Dec) != nullptr; }
+  const Stmt *findMutation(const Expr *Exp);
+  const Stmt *findMutation(const Decl *Dec);
+
+  bool isPointeeMutated(const Expr *Exp) {
+    return findPointeeMutation(Exp) != nullptr;
+  }
+  bool isPointeeMutated(const Decl *Dec) {
+    return findPointeeMutation(Dec) != nullptr;
+  }
+  const Stmt *findPointeeMutation(const Expr *Exp);
+  const Stmt *findPointeeMutation(const Decl *Dec);
+  static bool isUnevaluated(const Stmt *Smt, const Stmt &Stm,
+                            ASTContext &Context);
+
+private:
+  using MutationFinder = const Stmt *(ExprMutationAnalyzer::*)(const Expr *);
+  using ResultMap = llvm::DenseMap<const Expr *, const Stmt *>;
+
+  const Stmt *findMutationMemoized(const Expr *Exp,
+                                   llvm::ArrayRef<MutationFinder> Finders,
+                                   ResultMap &MemoizedResults);
+  const Stmt *tryEachDeclRef(const Decl *Dec, MutationFinder Finder);
+
+  bool isUnevaluated(const Expr *Exp);
+
+  const Stmt *findExprMutation(ArrayRef<ast_matchers::BoundNodes> Matches);
+  const Stmt *findDeclMutation(ArrayRef<ast_matchers::BoundNodes> Matches);
+  const Stmt *
+  findExprPointeeMutation(ArrayRef<ast_matchers::BoundNodes> Matches);
+  const Stmt *
+  findDeclPointeeMutation(ArrayRef<ast_matchers::BoundNodes> Matches);
+
+  const Stmt *findDirectMutation(const Expr *Exp);
+  const Stmt *findMemberMutation(const Expr *Exp);
+  const Stmt *findArrayElementMutation(const Expr *Exp);
+  const Stmt *findCastMutation(const Expr *Exp);
+  const Stmt *findRangeLoopMutation(const Expr *Exp);
+  const Stmt *findReferenceMutation(const Expr *Exp);
+  const Stmt *findFunctionArgMutation(const Expr *Exp);
+
+  const Stmt &Stm;
+  ASTContext &Context;
+  llvm::DenseMap<const FunctionDecl *,
+                 std::unique_ptr<FunctionParmMutationAnalyzer>>
+      FuncParmAnalyzer;
+  ResultMap Results;
+  ResultMap PointeeResults;
+};
+
+// A convenient wrapper around ExprMutationAnalyzer for analyzing function
+// params.
+class FunctionParmMutationAnalyzer {
+public:
+  FunctionParmMutationAnalyzer(const FunctionDecl &Func, ASTContext &Context);
+
+  bool isMutated(const ParmVarDecl *Parm) {
+    return findMutation(Parm) != nullptr;
+  }
+  const Stmt *findMutation(const ParmVarDecl *Parm);
+
+private:
+  ExprMutationAnalyzer BodyAnalyzer;
+  llvm::DenseMap<const ParmVarDecl *, const Stmt *> Results;
+};
+
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_EXPRMUTATIONANALYZER_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/LiveVariables.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/LiveVariables.h
new file mode 100644
index 0000000000..e44a95ccf5
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/LiveVariables.h
@@ -0,0 +1,135 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements Live Variables analysis for source-level CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "llvm/ADT/ImmutableSet.h"
+
+namespace clang {
+
+class CFG;
+class CFGBlock;
+class Stmt;
+class DeclRefExpr;
+class SourceManager;
+
+class LiveVariables : public ManagedAnalysis {
+public:
+  class LivenessValues {
+  public:
+
+    llvm::ImmutableSet<const Expr *> liveExprs;
+    llvm::ImmutableSet<const VarDecl *> liveDecls;
+    llvm::ImmutableSet<const BindingDecl *> liveBindings;
+
+    bool equals(const LivenessValues &V) const;
+
+    LivenessValues()
+      : liveExprs(nullptr), liveDecls(nullptr), liveBindings(nullptr) {}
+
+    LivenessValues(llvm::ImmutableSet<const Expr *> liveExprs,
+                   llvm::ImmutableSet<const VarDecl *> LiveDecls,
+                   llvm::ImmutableSet<const BindingDecl *> LiveBindings)
+        : liveExprs(liveExprs), liveDecls(LiveDecls),
+          liveBindings(LiveBindings) {}
+
+    bool isLive(const Expr *E) const;
+    bool isLive(const VarDecl *D) const;
+
+    friend class LiveVariables;
+  };
+
+  class Observer {
+    virtual void anchor();
+  public:
+    virtual ~Observer() {}
+
+    /// A callback invoked right before invoking the
+    ///  liveness transfer function on the given statement.
+    virtual void observeStmt(const Stmt *S,
+                             const CFGBlock *currentBlock,
+                             const LivenessValues& V) {}
+
+    /// Called when the live variables analysis registers
+    /// that a variable is killed.
+    virtual void observerKill(const DeclRefExpr *DR) {}
+  };
+
+  ~LiveVariables() override;
+
+  /// Compute the liveness information for a given CFG.
+  static std::unique_ptr<LiveVariables>
+  computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign);
+
+  /// Return true if a variable is live at the end of a
+  /// specified block.
+  bool isLive(const CFGBlock *B, const VarDecl *D);
+
+  /// Returns true if a variable is live at the beginning of the
+  ///  the statement.  This query only works if liveness information
+  ///  has been recorded at the statement level (see runOnAllBlocks), and
+  ///  only returns liveness information for block-level expressions.
+  bool isLive(const Stmt *S, const VarDecl *D);
+
+  /// Returns true the block-level expression value is live
+  ///  before the given block-level expression (see runOnAllBlocks).
+  bool isLive(const Stmt *Loc, const Expr *Val);
+
+  /// Print to stderr the variable liveness information associated with
+  /// each basic block.
+  void dumpBlockLiveness(const SourceManager &M);
+
+  /// Print to stderr the expression liveness information associated with
+  /// each basic block.
+  void dumpExprLiveness(const SourceManager &M);
+
+  void runOnAllBlocks(Observer &obs);
+
+  static std::unique_ptr<LiveVariables>
+  create(AnalysisDeclContext &analysisContext) {
+    return computeLiveness(analysisContext, true);
+  }
+
+  static const void *getTag();
+
+private:
+  LiveVariables(void *impl);
+  void *impl;
+};
+
+class RelaxedLiveVariables : public LiveVariables {
+public:
+  static std::unique_ptr<LiveVariables>
+  create(AnalysisDeclContext &analysisContext) {
+    return computeLiveness(analysisContext, false);
+  }
+
+  static const void *getTag();
+};
+
+} // end namespace clang
+
+#endif
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/PostOrderCFGView.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/PostOrderCFGView.h
new file mode 100644
index 0000000000..75885c3654
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/PostOrderCFGView.h
@@ -0,0 +1,128 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- PostOrderCFGView.h - Post order view of CFG blocks -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements post order view of the blocks in a CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
+
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include <utility>
+#include <vector>
+
+namespace clang {
+
+class PostOrderCFGView : public ManagedAnalysis {
+  virtual void anchor();
+
+public:
+  /// Implements a set of CFGBlocks using a BitVector.
+  ///
+  /// This class contains a minimal interface, primarily dictated by the SetType
+  /// template parameter of the llvm::po_iterator template, as used with
+  /// external storage. We also use this set to keep track of which CFGBlocks we
+  /// visit during the analysis.
+  class CFGBlockSet {
+    llvm::BitVector VisitedBlockIDs;
+
+  public:
+    // po_iterator requires this iterator, but the only interface needed is the
+    // value_type type.
+    struct iterator { using value_type = const CFGBlock *; };
+
+    CFGBlockSet() = default;
+    CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {}
+
+    /// Set the bit associated with a particular CFGBlock.
+    /// This is the important method for the SetType template parameter.
+    std::pair<std::nullopt_t, bool> insert(const CFGBlock *Block) {
+      // Note that insert() is called by po_iterator, which doesn't check to
+      // make sure that Block is non-null.  Moreover, the CFGBlock iterator will
+      // occasionally hand out null pointers for pruned edges, so we catch those
+      // here.
+      if (!Block)
+        return std::make_pair(std::nullopt,
+                              false); // if an edge is trivially false.
+      if (VisitedBlockIDs.test(Block->getBlockID()))
+        return std::make_pair(std::nullopt, false);
+      VisitedBlockIDs.set(Block->getBlockID());
+      return std::make_pair(std::nullopt, true);
+    }
+
+    /// Check if the bit for a CFGBlock has been already set.
+    /// This method is for tracking visited blocks in the main threadsafety
+    /// loop. Block must not be null.
+    bool alreadySet(const CFGBlock *Block) {
+      return VisitedBlockIDs.test(Block->getBlockID());
+    }
+  };
+
+private:
+  using po_iterator = llvm::po_iterator<const CFG *, CFGBlockSet, true>;
+  std::vector<const CFGBlock *> Blocks;
+
+  using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>;
+  BlockOrderTy BlockOrder;
+
+public:
+  friend struct BlockOrderCompare;
+
+  using iterator = std::vector<const CFGBlock *>::reverse_iterator;
+  using const_iterator = std::vector<const CFGBlock *>::const_reverse_iterator;
+
+  PostOrderCFGView(const CFG *cfg);
+
+  iterator begin() { return Blocks.rbegin(); }
+  iterator end() { return Blocks.rend(); }
+
+  const_iterator begin() const { return Blocks.rbegin(); }
+  const_iterator end() const { return Blocks.rend(); }
+
+  bool empty() const { return begin() == end(); }
+
+  struct BlockOrderCompare {
+    const PostOrderCFGView &POV;
+
+  public:
+    BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {}
+
+    bool operator()(const CFGBlock *b1, const CFGBlock *b2) const;
+  };
+
+  BlockOrderCompare getComparator() const {
+    return BlockOrderCompare(*this);
+  }
+
+  // Used by AnalyisContext to construct this object.
+  static const void *getTag();
+
+  static std::unique_ptr<PostOrderCFGView>
+  create(AnalysisDeclContext &analysisContext);
+};
+
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ReachableCode.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/ReachableCode.h
new file mode 100644
index 0000000000..9a622bfac4
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ReachableCode.h
@@ -0,0 +1,79 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- ReachableCode.h -----------------------------------------*- C++ --*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// A flow-sensitive, path-insensitive analysis of unreachable code.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLECODE_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLECODE_H
+
+#include "clang/Basic/SourceLocation.h"
+
+//===----------------------------------------------------------------------===//
+// Forward declarations.
+//===----------------------------------------------------------------------===//
+
+namespace llvm {
+  class BitVector;
+}
+
+namespace clang {
+  class AnalysisDeclContext;
+  class CFGBlock;
+  class Preprocessor;
+}
+
+//===----------------------------------------------------------------------===//
+// API.
+//===----------------------------------------------------------------------===//
+
+namespace clang {
+namespace reachable_code {
+
+/// Classifications of unreachable code.
+enum UnreachableKind {
+  UK_Return,
+  UK_Break,
+  UK_Loop_Increment,
+  UK_Other
+};
+
+class Callback {
+  virtual void anchor();
+public:
+  virtual ~Callback() {}
+  virtual void HandleUnreachable(UnreachableKind UK,
+                                 SourceLocation L,
+                                 SourceRange ConditionVal,
+                                 SourceRange R1,
+                                 SourceRange R2) = 0;
+};
+
+/// ScanReachableFromBlock - Mark all blocks reachable from Start.
+/// Returns the total number of blocks that were marked reachable.
+unsigned ScanReachableFromBlock(const CFGBlock *Start,
+                                llvm::BitVector &Reachable);
+
+void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP,
+                         Callback &CB);
+
+}} // end namespace clang::reachable_code
+
+#endif
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafety.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafety.h
new file mode 100644
index 0000000000..b5785fc5e7
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafety.h
@@ -0,0 +1,270 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- ThreadSafety.h -------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//
+// A intra-procedural analysis for thread safety (e.g. deadlocks and race
+// conditions), based off of an annotation system.
+//
+// See http://clang.llvm.org/docs/LanguageExtensions.html#thread-safety-annotation-checking
+// for more information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETY_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETY_H
+
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+
+class AnalysisDeclContext;
+class FunctionDecl;
+class NamedDecl;
+
+namespace threadSafety {
+
+class BeforeSet;
+
+/// This enum distinguishes between different kinds of operations that may
+/// need to be protected by locks. We use this enum in error handling.
+enum ProtectedOperationKind {
+  /// Dereferencing a variable (e.g. p in *p = 5;)
+  POK_VarDereference,
+
+  /// Reading or writing a variable (e.g. x in x = 5;)
+  POK_VarAccess,
+
+  /// Making a function call (e.g. fool())
+  POK_FunctionCall,
+
+  /// Passing a guarded variable by reference.
+  POK_PassByRef,
+
+  /// Passing a pt-guarded variable by reference.
+  POK_PtPassByRef
+};
+
+/// This enum distinguishes between different kinds of lock actions. For
+/// example, it is an error to write a variable protected by shared version of a
+/// mutex.
+enum LockKind {
+  /// Shared/reader lock of a mutex.
+  LK_Shared,
+
+  /// Exclusive/writer lock of a mutex.
+  LK_Exclusive,
+
+  /// Can be either Shared or Exclusive.
+  LK_Generic
+};
+
+/// This enum distinguishes between different ways to access (read or write) a
+/// variable.
+enum AccessKind {
+  /// Reading a variable.
+  AK_Read,
+
+  /// Writing a variable.
+  AK_Written
+};
+
+/// This enum distinguishes between different situations where we warn due to
+/// inconsistent locking.
+/// \enum SK_LockedSomeLoopIterations -- a mutex is locked for some but not all
+/// loop iterations.
+/// \enum SK_LockedSomePredecessors -- a mutex is locked in some but not all
+/// predecessors of a CFGBlock.
+/// \enum SK_LockedAtEndOfFunction -- a mutex is still locked at the end of a
+/// function.
+enum LockErrorKind {
+  LEK_LockedSomeLoopIterations,
+  LEK_LockedSomePredecessors,
+  LEK_LockedAtEndOfFunction,
+  LEK_NotLockedAtEndOfFunction
+};
+
+/// Handler class for thread safety warnings.
+class ThreadSafetyHandler {
+public:
+  using Name = StringRef;
+
+  ThreadSafetyHandler() = default;
+  virtual ~ThreadSafetyHandler();
+
+  /// Warn about lock expressions which fail to resolve to lockable objects.
+  /// \param Loc -- the SourceLocation of the unresolved expression.
+  virtual void handleInvalidLockExp(SourceLocation Loc) {}
+
+  /// Warn about unlock function calls that do not have a prior matching lock
+  /// expression.
+  /// \param Kind -- the capability's name parameter (role, mutex, etc).
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param Loc -- The SourceLocation of the Unlock
+  /// \param LocPreviousUnlock -- If valid, the location of a previous Unlock.
+  virtual void handleUnmatchedUnlock(StringRef Kind, Name LockName,
+                                     SourceLocation Loc,
+                                     SourceLocation LocPreviousUnlock) {}
+
+  /// Warn about an unlock function call that attempts to unlock a lock with
+  /// the incorrect lock kind. For instance, a shared lock being unlocked
+  /// exclusively, or vice versa.
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param Kind -- the capability's name parameter (role, mutex, etc).
+  /// \param Expected -- the kind of lock expected.
+  /// \param Received -- the kind of lock received.
+  /// \param LocLocked -- The SourceLocation of the Lock.
+  /// \param LocUnlock -- The SourceLocation of the Unlock.
+  virtual void handleIncorrectUnlockKind(StringRef Kind, Name LockName,
+                                         LockKind Expected, LockKind Received,
+                                         SourceLocation LocLocked,
+                                         SourceLocation LocUnlock) {}
+
+  /// Warn about lock function calls for locks which are already held.
+  /// \param Kind -- the capability's name parameter (role, mutex, etc).
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param LocLocked -- The location of the first lock expression.
+  /// \param LocDoubleLock -- The location of the second lock expression.
+  virtual void handleDoubleLock(StringRef Kind, Name LockName,
+                                SourceLocation LocLocked,
+                                SourceLocation LocDoubleLock) {}
+
+  /// Warn about situations where a mutex is sometimes held and sometimes not.
+  /// The three situations are:
+  /// 1. a mutex is locked on an "if" branch but not the "else" branch,
+  /// 2, or a mutex is only held at the start of some loop iterations,
+  /// 3. or when a mutex is locked but not unlocked inside a function.
+  /// \param Kind -- the capability's name parameter (role, mutex, etc).
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param LocLocked -- The location of the lock expression where the mutex is
+  ///               locked
+  /// \param LocEndOfScope -- The location of the end of the scope where the
+  ///               mutex is no longer held
+  /// \param LEK -- which of the three above cases we should warn for
+  virtual void handleMutexHeldEndOfScope(StringRef Kind, Name LockName,
+                                         SourceLocation LocLocked,
+                                         SourceLocation LocEndOfScope,
+                                         LockErrorKind LEK) {}
+
+  /// Warn when a mutex is held exclusively and shared at the same point. For
+  /// example, if a mutex is locked exclusively during an if branch and shared
+  /// during the else branch.
+  /// \param Kind -- the capability's name parameter (role, mutex, etc).
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param Loc1 -- The location of the first lock expression.
+  /// \param Loc2 -- The location of the second lock expression.
+  virtual void handleExclusiveAndShared(StringRef Kind, Name LockName,
+                                        SourceLocation Loc1,
+                                        SourceLocation Loc2) {}
+
+  /// Warn when a protected operation occurs while no locks are held.
+  /// \param D -- The decl for the protected variable or function
+  /// \param POK -- The kind of protected operation (e.g. variable access)
+  /// \param AK -- The kind of access (i.e. read or write) that occurred
+  /// \param Loc -- The location of the protected operation.
+  virtual void handleNoMutexHeld(const NamedDecl *D, ProtectedOperationKind POK,
+                                 AccessKind AK, SourceLocation Loc) {}
+
+  /// Warn when a protected operation occurs while the specific mutex protecting
+  /// the operation is not locked.
+  /// \param Kind -- the capability's name parameter (role, mutex, etc).
+  /// \param D -- The decl for the protected variable or function
+  /// \param POK -- The kind of protected operation (e.g. variable access)
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param LK -- The kind of access (i.e. read or write) that occurred
+  /// \param Loc -- The location of the protected operation.
+  virtual void handleMutexNotHeld(StringRef Kind, const NamedDecl *D,
+                                  ProtectedOperationKind POK, Name LockName,
+                                  LockKind LK, SourceLocation Loc,
+                                  Name *PossibleMatch = nullptr) {}
+
+  /// Warn when acquiring a lock that the negative capability is not held.
+  /// \param Kind -- the capability's name parameter (role, mutex, etc).
+  /// \param LockName -- The name for the lock expression, to be printed in the
+  /// diagnostic.
+  /// \param Neg -- The name of the negative capability to be printed in the
+  /// diagnostic.
+  /// \param Loc -- The location of the protected operation.
+  virtual void handleNegativeNotHeld(StringRef Kind, Name LockName, Name Neg,
+                                     SourceLocation Loc) {}
+
+  /// Warn when calling a function that a negative capability is not held.
+  /// \param D -- The decl for the function requiring the negative capability.
+  /// \param LockName -- The name for the lock expression, to be printed in the
+  /// diagnostic.
+  /// \param Loc -- The location of the protected operation.
+  virtual void handleNegativeNotHeld(const NamedDecl *D, Name LockName,
+                                     SourceLocation Loc) {}
+
+  /// Warn when a function is called while an excluded mutex is locked. For
+  /// example, the mutex may be locked inside the function.
+  /// \param Kind -- the capability's name parameter (role, mutex, etc).
+  /// \param FunName -- The name of the function
+  /// \param LockName -- A StringRef name for the lock expression, to be printed
+  /// in the error message.
+  /// \param Loc -- The location of the function call.
+  virtual void handleFunExcludesLock(StringRef Kind, Name FunName,
+                                     Name LockName, SourceLocation Loc) {}
+
+  /// Warn that L1 cannot be acquired before L2.
+  virtual void handleLockAcquiredBefore(StringRef Kind, Name L1Name,
+                                        Name L2Name, SourceLocation Loc) {}
+
+  /// Warn that there is a cycle in acquired_before/after dependencies.
+  virtual void handleBeforeAfterCycle(Name L1Name, SourceLocation Loc) {}
+
+  /// Called by the analysis when starting analysis of a function.
+  /// Used to issue suggestions for changes to annotations.
+  virtual void enterFunction(const FunctionDecl *FD) {}
+
+  /// Called by the analysis when finishing analysis of a function.
+  virtual void leaveFunction(const FunctionDecl *FD) {}
+
+  bool issueBetaWarnings() { return IssueBetaWarnings; }
+  void setIssueBetaWarnings(bool b) { IssueBetaWarnings = b; }
+
+private:
+  bool IssueBetaWarnings = false;
+};
+
+/// Check a function's CFG for thread-safety violations.
+///
+/// We traverse the blocks in the CFG, compute the set of mutexes that are held
+/// at the end of each block, and issue warnings for thread safety violations.
+/// Each block in the CFG is traversed exactly once.
+void runThreadSafetyAnalysis(AnalysisDeclContext &AC,
+                             ThreadSafetyHandler &Handler,
+                             BeforeSet **Bset);
+
+void threadSafetyCleanup(BeforeSet *Cache);
+
+/// Helper function that returns a LockKind required for the given level
+/// of access.
+LockKind getLockKindFromAccessKind(AccessKind AK);
+
+} // namespace threadSafety
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETY_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyCommon.h
new file mode 100644
index 0000000000..b77a7ba0d9
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyCommon.h
@@ -0,0 +1,549 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- ThreadSafetyCommon.h -------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Parts of thread safety analysis that are not specific to thread safety
+// itself have been factored into classes here, where they can be potentially
+// used by other analyses.  Currently these include:
+//
+// * Generalize clang CFG visitors.
+// * Conversion of the clang CFG to SSA form.
+// * Translation of clang Exprs to TIL SExprs
+//
+// UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
+#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
+#include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Casting.h"
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace clang {
+
+class AbstractConditionalOperator;
+class ArraySubscriptExpr;
+class BinaryOperator;
+class CallExpr;
+class CastExpr;
+class CXXDestructorDecl;
+class CXXMemberCallExpr;
+class CXXOperatorCallExpr;
+class CXXThisExpr;
+class DeclRefExpr;
+class DeclStmt;
+class Expr;
+class MemberExpr;
+class Stmt;
+class UnaryOperator;
+
+namespace threadSafety {
+
+// Various helper functions on til::SExpr
+namespace sx {
+
+inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
+  return til::EqualsComparator::compareExprs(E1, E2);
+}
+
+inline bool matches(const til::SExpr *E1, const til::SExpr *E2) {
+  // We treat a top-level wildcard as the "univsersal" lock.
+  // It matches everything for the purpose of checking locks, but not
+  // for unlocking them.
+  if (isa<til::Wildcard>(E1))
+    return isa<til::Wildcard>(E2);
+  if (isa<til::Wildcard>(E2))
+    return isa<til::Wildcard>(E1);
+
+  return til::MatchComparator::compareExprs(E1, E2);
+}
+
+inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) {
+  const auto *PE1 = dyn_cast_or_null<til::Project>(E1);
+  if (!PE1)
+    return false;
+  const auto *PE2 = dyn_cast_or_null<til::Project>(E2);
+  if (!PE2)
+    return false;
+  return PE1->clangDecl() == PE2->clangDecl();
+}
+
+inline std::string toString(const til::SExpr *E) {
+  std::stringstream ss;
+  til::StdPrinter::print(E, ss);
+  return ss.str();
+}
+
+}  // namespace sx
+
+// This class defines the interface of a clang CFG Visitor.
+// CFGWalker will invoke the following methods.
+// Note that methods are not virtual; the visitor is templatized.
+class CFGVisitor {
+  // Enter the CFG for Decl D, and perform any initial setup operations.
+  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
+
+  // Enter a CFGBlock.
+  void enterCFGBlock(const CFGBlock *B) {}
+
+  // Returns true if this visitor implements handlePredecessor
+  bool visitPredecessors() { return true; }
+
+  // Process a predecessor edge.
+  void handlePredecessor(const CFGBlock *Pred) {}
+
+  // Process a successor back edge to a previously visited block.
+  void handlePredecessorBackEdge(const CFGBlock *Pred) {}
+
+  // Called just before processing statements.
+  void enterCFGBlockBody(const CFGBlock *B) {}
+
+  // Process an ordinary statement.
+  void handleStatement(const Stmt *S) {}
+
+  // Process a destructor call
+  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
+
+  // Called after all statements have been handled.
+  void exitCFGBlockBody(const CFGBlock *B) {}
+
+  // Return true
+  bool visitSuccessors() { return true; }
+
+  // Process a successor edge.
+  void handleSuccessor(const CFGBlock *Succ) {}
+
+  // Process a successor back edge to a previously visited block.
+  void handleSuccessorBackEdge(const CFGBlock *Succ) {}
+
+  // Leave a CFGBlock.
+  void exitCFGBlock(const CFGBlock *B) {}
+
+  // Leave the CFG, and perform any final cleanup operations.
+  void exitCFG(const CFGBlock *Last) {}
+};
+
+// Walks the clang CFG, and invokes methods on a given CFGVisitor.
+class CFGWalker {
+public:
+  CFGWalker() = default;
+
+  // Initialize the CFGWalker.  This setup only needs to be done once, even
+  // if there are multiple passes over the CFG.
+  bool init(AnalysisDeclContext &AC) {
+    ACtx = &AC;
+    CFGraph = AC.getCFG();
+    if (!CFGraph)
+      return false;
+
+    // Ignore anonymous functions.
+    if (!isa_and_nonnull<NamedDecl>(AC.getDecl()))
+      return false;
+
+    SortedGraph = AC.getAnalysis<PostOrderCFGView>();
+    if (!SortedGraph)
+      return false;
+
+    return true;
+  }
+
+  // Traverse the CFG, calling methods on V as appropriate.
+  template <class Visitor>
+  void walk(Visitor &V) {
+    PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
+
+    V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry());
+
+    for (const auto *CurrBlock : *SortedGraph) {
+      VisitedBlocks.insert(CurrBlock);
+
+      V.enterCFGBlock(CurrBlock);
+
+      // Process predecessors, handling back edges last
+      if (V.visitPredecessors()) {
+        SmallVector<CFGBlock*, 4> BackEdges;
+        // Process successors
+        for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(),
+                                           SE = CurrBlock->pred_end();
+             SI != SE; ++SI) {
+          if (*SI == nullptr)
+            continue;
+
+          if (!VisitedBlocks.alreadySet(*SI)) {
+            BackEdges.push_back(*SI);
+            continue;
+          }
+          V.handlePredecessor(*SI);
+        }
+
+        for (auto *Blk : BackEdges)
+          V.handlePredecessorBackEdge(Blk);
+      }
+
+      V.enterCFGBlockBody(CurrBlock);
+
+      // Process statements
+      for (const auto &BI : *CurrBlock) {
+        switch (BI.getKind()) {
+        case CFGElement::Statement:
+          V.handleStatement(BI.castAs<CFGStmt>().getStmt());
+          break;
+
+        case CFGElement::AutomaticObjectDtor: {
+          CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();
+          auto *DD = const_cast<CXXDestructorDecl *>(
+              AD.getDestructorDecl(ACtx->getASTContext()));
+          auto *VD = const_cast<VarDecl *>(AD.getVarDecl());
+          V.handleDestructorCall(VD, DD);
+          break;
+        }
+        default:
+          break;
+        }
+      }
+
+      V.exitCFGBlockBody(CurrBlock);
+
+      // Process successors, handling back edges first.
+      if (V.visitSuccessors()) {
+        SmallVector<CFGBlock*, 8> ForwardEdges;
+
+        // Process successors
+        for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
+                                           SE = CurrBlock->succ_end();
+             SI != SE; ++SI) {
+          if (*SI == nullptr)
+            continue;
+
+          if (!VisitedBlocks.alreadySet(*SI)) {
+            ForwardEdges.push_back(*SI);
+            continue;
+          }
+          V.handleSuccessorBackEdge(*SI);
+        }
+
+        for (auto *Blk : ForwardEdges)
+          V.handleSuccessor(Blk);
+      }
+
+      V.exitCFGBlock(CurrBlock);
+    }
+    V.exitCFG(&CFGraph->getExit());
+  }
+
+  const CFG *getGraph() const { return CFGraph; }
+  CFG *getGraph() { return CFGraph; }
+
+  const NamedDecl *getDecl() const {
+    return dyn_cast<NamedDecl>(ACtx->getDecl());
+  }
+
+  const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }
+
+private:
+  CFG *CFGraph = nullptr;
+  AnalysisDeclContext *ACtx = nullptr;
+  PostOrderCFGView *SortedGraph = nullptr;
+};
+
+// TODO: move this back into ThreadSafety.cpp
+// This is specific to thread safety.  It is here because
+// translateAttrExpr needs it, but that should be moved too.
+class CapabilityExpr {
+private:
+  /// The capability expression and whether it's negated.
+  llvm::PointerIntPair<const til::SExpr *, 1, bool> CapExpr;
+
+  /// The kind of capability as specified by @ref CapabilityAttr::getName.
+  StringRef CapKind;
+
+public:
+  CapabilityExpr() : CapExpr(nullptr, false) {}
+  CapabilityExpr(const til::SExpr *E, StringRef Kind, bool Neg)
+      : CapExpr(E, Neg), CapKind(Kind) {}
+
+  // Don't allow implicitly-constructed StringRefs since we'll capture them.
+  template <typename T> CapabilityExpr(const til::SExpr *, T, bool) = delete;
+
+  const til::SExpr *sexpr() const { return CapExpr.getPointer(); }
+  StringRef getKind() const { return CapKind; }
+  bool negative() const { return CapExpr.getInt(); }
+
+  CapabilityExpr operator!() const {
+    return CapabilityExpr(CapExpr.getPointer(), CapKind, !CapExpr.getInt());
+  }
+
+  bool equals(const CapabilityExpr &other) const {
+    return (negative() == other.negative()) &&
+           sx::equals(sexpr(), other.sexpr());
+  }
+
+  bool matches(const CapabilityExpr &other) const {
+    return (negative() == other.negative()) &&
+           sx::matches(sexpr(), other.sexpr());
+  }
+
+  bool matchesUniv(const CapabilityExpr &CapE) const {
+    return isUniversal() || matches(CapE);
+  }
+
+  bool partiallyMatches(const CapabilityExpr &other) const {
+    return (negative() == other.negative()) &&
+           sx::partiallyMatches(sexpr(), other.sexpr());
+  }
+
+  const ValueDecl* valueDecl() const {
+    if (negative() || sexpr() == nullptr)
+      return nullptr;
+    if (const auto *P = dyn_cast<til::Project>(sexpr()))
+      return P->clangDecl();
+    if (const auto *P = dyn_cast<til::LiteralPtr>(sexpr()))
+      return P->clangDecl();
+    return nullptr;
+  }
+
+  std::string toString() const {
+    if (negative())
+      return "!" + sx::toString(sexpr());
+    return sx::toString(sexpr());
+  }
+
+  bool shouldIgnore() const { return sexpr() == nullptr; }
+
+  bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
+
+  bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
+};
+
+// Translate clang::Expr to til::SExpr.
+class SExprBuilder {
+public:
+  /// Encapsulates the lexical context of a function call.  The lexical
+  /// context includes the arguments to the call, including the implicit object
+  /// argument.  When an attribute containing a mutex expression is attached to
+  /// a method, the expression may refer to formal parameters of the method.
+  /// Actual arguments must be substituted for formal parameters to derive
+  /// the appropriate mutex expression in the lexical context where the function
+  /// is called.  PrevCtx holds the context in which the arguments themselves
+  /// should be evaluated; multiple calling contexts can be chained together
+  /// by the lock_returned attribute.
+  struct CallingContext {
+    // The previous context; or 0 if none.
+    CallingContext  *Prev;
+
+    // The decl to which the attr is attached.
+    const NamedDecl *AttrDecl;
+
+    // Implicit object argument -- e.g. 'this'
+    llvm::PointerUnion<const Expr *, til::SExpr *> SelfArg = nullptr;
+
+    // Number of funArgs
+    unsigned NumArgs = 0;
+
+    // Function arguments
+    const Expr *const *FunArgs = nullptr;
+
+    // is Self referred to with -> or .?
+    bool SelfArrow = false;
+
+    CallingContext(CallingContext *P, const NamedDecl *D = nullptr)
+        : Prev(P), AttrDecl(D) {}
+  };
+
+  SExprBuilder(til::MemRegionRef A) : Arena(A) {
+    // FIXME: we don't always have a self-variable.
+    SelfVar = new (Arena) til::Variable(nullptr);
+    SelfVar->setKind(til::Variable::VK_SFun);
+  }
+
+  // Translate a clang expression in an attribute to a til::SExpr.
+  // Constructs the context from D, DeclExp, and SelfDecl.
+  CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,
+                                   const Expr *DeclExp,
+                                   til::SExpr *Self = nullptr);
+
+  CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);
+
+  // Translate a variable reference.
+  til::LiteralPtr *createVariable(const VarDecl *VD);
+
+  // Create placeholder for this: we don't know the VarDecl on construction yet.
+  std::pair<til::LiteralPtr *, StringRef>
+  createThisPlaceholder(const Expr *Exp);
+
+  // Translate a clang statement or expression to a TIL expression.
+  // Also performs substitution of variables; Ctx provides the context.
+  // Dispatches on the type of S.
+  til::SExpr *translate(const Stmt *S, CallingContext *Ctx);
+  til::SCFG  *buildCFG(CFGWalker &Walker);
+
+  til::SExpr *lookupStmt(const Stmt *S);
+
+  til::BasicBlock *lookupBlock(const CFGBlock *B) {
+    return BlockMap[B->getBlockID()];
+  }
+
+  const til::SCFG *getCFG() const { return Scfg; }
+  til::SCFG *getCFG() { return Scfg; }
+
+private:
+  // We implement the CFGVisitor API
+  friend class CFGWalker;
+
+  til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,
+                                   CallingContext *Ctx) ;
+  til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);
+  til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);
+  til::SExpr *translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE,
+                                       CallingContext *Ctx);
+  til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx,
+                                const Expr *SelfE = nullptr);
+  til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,
+                                         CallingContext *Ctx);
+  til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,
+                                           CallingContext *Ctx);
+  til::SExpr *translateUnaryOperator(const UnaryOperator *UO,
+                                     CallingContext *Ctx);
+  til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,
+                             const BinaryOperator *BO,
+                             CallingContext *Ctx, bool Reverse = false);
+  til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,
+                                 const BinaryOperator *BO,
+                                 CallingContext *Ctx, bool Assign = false);
+  til::SExpr *translateBinaryOperator(const BinaryOperator *BO,
+                                      CallingContext *Ctx);
+  til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);
+  til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,
+                                          CallingContext *Ctx);
+  til::SExpr *translateAbstractConditionalOperator(
+      const AbstractConditionalOperator *C, CallingContext *Ctx);
+
+  til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);
+
+  // Map from statements in the clang CFG to SExprs in the til::SCFG.
+  using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>;
+
+  // Map from clang local variables to indices in a LVarDefinitionMap.
+  using LVarIndexMap = llvm::DenseMap<const ValueDecl *, unsigned>;
+
+  // Map from local variable indices to SSA variables (or constants).
+  using NameVarPair = std::pair<const ValueDecl *, til::SExpr *>;
+  using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>;
+
+  struct BlockInfo {
+    LVarDefinitionMap ExitMap;
+    bool HasBackEdges = false;
+
+    // Successors yet to be processed
+    unsigned UnprocessedSuccessors = 0;
+
+    // Predecessors already processed
+    unsigned ProcessedPredecessors = 0;
+
+    BlockInfo() = default;
+    BlockInfo(BlockInfo &&) = default;
+    BlockInfo &operator=(BlockInfo &&) = default;
+  };
+
+  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
+  void enterCFGBlock(const CFGBlock *B);
+  bool visitPredecessors() { return true; }
+  void handlePredecessor(const CFGBlock *Pred);
+  void handlePredecessorBackEdge(const CFGBlock *Pred);
+  void enterCFGBlockBody(const CFGBlock *B);
+  void handleStatement(const Stmt *S);
+  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
+  void exitCFGBlockBody(const CFGBlock *B);
+  bool visitSuccessors() { return true; }
+  void handleSuccessor(const CFGBlock *Succ);
+  void handleSuccessorBackEdge(const CFGBlock *Succ);
+  void exitCFGBlock(const CFGBlock *B);
+  void exitCFG(const CFGBlock *Last);
+
+  void insertStmt(const Stmt *S, til::SExpr *E) {
+    SMap.insert(std::make_pair(S, E));
+  }
+
+  til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
+
+  til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
+                           const ValueDecl *VD = nullptr);
+  til::SExpr *lookupVarDecl(const ValueDecl *VD);
+  til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
+  til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
+
+  void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
+  void mergeEntryMap(LVarDefinitionMap Map);
+  void mergeEntryMapBackEdge();
+  void mergePhiNodesBackEdge(const CFGBlock *Blk);
+
+private:
+  // Set to true when parsing capability expressions, which get translated
+  // inaccurately in order to hack around smart pointers etc.
+  static const bool CapabilityExprMode = true;
+
+  til::MemRegionRef Arena;
+
+  // Variable to use for 'this'.  May be null.
+  til::Variable *SelfVar = nullptr;
+
+  til::SCFG *Scfg = nullptr;
+
+  // Map from Stmt to TIL Variables
+  StatementMap SMap;
+
+  // Indices of clang local vars.
+  LVarIndexMap LVarIdxMap;
+
+  // Map from clang to til BBs.
+  std::vector<til::BasicBlock *> BlockMap;
+
+  // Extra information per BB. Indexed by clang BlockID.
+  std::vector<BlockInfo> BBInfo;
+
+  LVarDefinitionMap CurrentLVarMap;
+  std::vector<til::Phi *> CurrentArguments;
+  std::vector<til::SExpr *> CurrentInstructions;
+  std::vector<til::Phi *> IncompleteArgs;
+  til::BasicBlock *CurrentBB = nullptr;
+  BlockInfo *CurrentBlockInfo = nullptr;
+};
+
+// Dump an SCFG to llvm::errs().
+void printSCFG(CFGWalker &Walker);
+
+} // namespace threadSafety
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyLogical.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyLogical.h
new file mode 100644
index 0000000000..b5765172a1
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyLogical.h
@@ -0,0 +1,118 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- ThreadSafetyLogical.h -----------------------------------*- C++ --*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// This file defines a representation for logical expressions with SExpr leaves
+// that are used as part of fact-checking capability expressions.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYLOGICAL_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYLOGICAL_H
+
+#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
+
+namespace clang {
+namespace threadSafety {
+namespace lexpr {
+
+class LExpr {
+public:
+  enum Opcode {
+    Terminal,
+    And,
+    Or,
+    Not
+  };
+  Opcode kind() const { return Kind; }
+
+  /// Logical implication. Returns true if the LExpr implies RHS, i.e. if
+  /// the LExpr holds, then RHS must hold. For example, (A & B) implies A.
+  inline bool implies(const LExpr *RHS) const;
+
+protected:
+  LExpr(Opcode Kind) : Kind(Kind) {}
+
+private:
+  Opcode Kind;
+};
+
+class Terminal : public LExpr {
+  til::SExpr *Expr;
+
+public:
+  Terminal(til::SExpr *Expr) : LExpr(LExpr::Terminal), Expr(Expr) {}
+
+  const til::SExpr *expr() const { return Expr; }
+  til::SExpr *expr() { return Expr; }
+
+  static bool classof(const LExpr *E) { return E->kind() == LExpr::Terminal; }
+};
+
+class BinOp : public LExpr {
+  LExpr *LHS, *RHS;
+
+protected:
+  BinOp(LExpr *LHS, LExpr *RHS, Opcode Code) : LExpr(Code), LHS(LHS), RHS(RHS) {}
+
+public:
+  const LExpr *left() const { return LHS; }
+  LExpr *left() { return LHS; }
+
+  const LExpr *right() const { return RHS; }
+  LExpr *right() { return RHS; }
+};
+
+class And : public BinOp {
+public:
+  And(LExpr *LHS, LExpr *RHS) : BinOp(LHS, RHS, LExpr::And) {}
+
+  static bool classof(const LExpr *E) { return E->kind() == LExpr::And; }
+};
+
+class Or : public BinOp {
+public:
+  Or(LExpr *LHS, LExpr *RHS) : BinOp(LHS, RHS, LExpr::Or) {}
+
+  static bool classof(const LExpr *E) { return E->kind() == LExpr::Or; }
+};
+
+class Not : public LExpr {
+  LExpr *Exp;
+
+public:
+  Not(LExpr *Exp) : LExpr(LExpr::Not), Exp(Exp) {}
+
+  const LExpr *exp() const { return Exp; }
+  LExpr *exp() { return Exp; }
+
+  static bool classof(const LExpr *E) { return E->kind() == LExpr::Not; }
+};
+
+/// Logical implication. Returns true if LHS implies RHS, i.e. if LHS
+/// holds, then RHS must hold. For example, (A & B) implies A.
+bool implies(const LExpr *LHS, const LExpr *RHS);
+
+bool LExpr::implies(const LExpr *RHS) const {
+  return lexpr::implies(this, RHS);
+}
+
+}
+}
+}
+
+#endif
+
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyOps.def b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyOps.def
new file mode 100644
index 0000000000..fc4881a7f0
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyOps.def
@@ -0,0 +1,56 @@
+//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the list of core opcodes for the Thread Safety
+// Typed Intermediate language.  Please see ThreadSafetyTIL.h for more
+// information.
+//
+//===----------------------------------------------------------------------===//
+
+
+TIL_OPCODE_DEF(Future)
+TIL_OPCODE_DEF(Undefined)
+TIL_OPCODE_DEF(Wildcard)
+
+TIL_OPCODE_DEF(Literal)
+TIL_OPCODE_DEF(LiteralPtr)
+TIL_OPCODE_DEF(Variable)
+TIL_OPCODE_DEF(Function)
+TIL_OPCODE_DEF(SFunction)
+TIL_OPCODE_DEF(Code)
+TIL_OPCODE_DEF(Field)
+
+TIL_OPCODE_DEF(Apply)
+TIL_OPCODE_DEF(SApply)
+TIL_OPCODE_DEF(Project)
+
+TIL_OPCODE_DEF(Call)
+TIL_OPCODE_DEF(Alloc)
+TIL_OPCODE_DEF(Load)
+TIL_OPCODE_DEF(Store)
+TIL_OPCODE_DEF(ArrayIndex)
+TIL_OPCODE_DEF(ArrayAdd)
+
+TIL_OPCODE_DEF(UnaryOp)
+TIL_OPCODE_DEF(BinaryOp)
+TIL_OPCODE_DEF(Cast)
+
+TIL_OPCODE_DEF(SCFG)
+TIL_OPCODE_DEF(BasicBlock)
+TIL_OPCODE_DEF(Phi)
+
+// Terminator instructions
+TIL_OPCODE_DEF(Goto)
+TIL_OPCODE_DEF(Branch)
+TIL_OPCODE_DEF(Return)
+
+// pseudo-terms
+TIL_OPCODE_DEF(Identifier)
+TIL_OPCODE_DEF(IfThenElse)
+TIL_OPCODE_DEF(Let)
+
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyTIL.h
new file mode 100644
index 0000000000..4575a4dc61
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyTIL.h
@@ -0,0 +1,1921 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- ThreadSafetyTIL.h ----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a simple Typed Intermediate Language, or TIL, that is used
+// by the thread safety analysis (See ThreadSafety.cpp).  The TIL is intended
+// to be largely independent of clang, in the hope that the analysis can be
+// reused for other non-C++ languages.  All dependencies on clang/llvm should
+// go in ThreadSafetyUtil.h.
+//
+// Thread safety analysis works by comparing mutex expressions, e.g.
+//
+// class A { Mutex mu; int dat GUARDED_BY(this->mu); }
+// class B { A a; }
+//
+// void foo(B* b) {
+//   (*b).a.mu.lock();     // locks (*b).a.mu
+//   b->a.dat = 0;         // substitute &b->a for 'this';
+//                         // requires lock on (&b->a)->mu
+//   (b->a.mu).unlock();   // unlocks (b->a.mu)
+// }
+//
+// As illustrated by the above example, clang Exprs are not well-suited to
+// represent mutex expressions directly, since there is no easy way to compare
+// Exprs for equivalence.  The thread safety analysis thus lowers clang Exprs
+// into a simple intermediate language (IL).  The IL supports:
+//
+// (1) comparisons for semantic equality of expressions
+// (2) SSA renaming of variables
+// (3) wildcards and pattern matching over expressions
+// (4) hash-based expression lookup
+//
+// The TIL is currently very experimental, is intended only for use within
+// the thread safety analysis, and is subject to change without notice.
+// After the API stabilizes and matures, it may be appropriate to make this
+// more generally available to other analyses.
+//
+// UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <iterator>
+#include <optional>
+#include <string>
+#include <utility>
+
+namespace clang {
+
+class CallExpr;
+class Expr;
+class Stmt;
+
+namespace threadSafety {
+namespace til {
+
+class BasicBlock;
+
+/// Enum for the different distinct classes of SExpr
+enum TIL_Opcode : unsigned char {
+#define TIL_OPCODE_DEF(X) COP_##X,
+#include "ThreadSafetyOps.def"
+#undef TIL_OPCODE_DEF
+};
+
+/// Opcode for unary arithmetic operations.
+enum TIL_UnaryOpcode : unsigned char {
+  UOP_Minus,        //  -
+  UOP_BitNot,       //  ~
+  UOP_LogicNot      //  !
+};
+
+/// Opcode for binary arithmetic operations.
+enum TIL_BinaryOpcode : unsigned char {
+  BOP_Add,          //  +
+  BOP_Sub,          //  -
+  BOP_Mul,          //  *
+  BOP_Div,          //  /
+  BOP_Rem,          //  %
+  BOP_Shl,          //  <<
+  BOP_Shr,          //  >>
+  BOP_BitAnd,       //  &
+  BOP_BitXor,       //  ^
+  BOP_BitOr,        //  |
+  BOP_Eq,           //  ==
+  BOP_Neq,          //  !=
+  BOP_Lt,           //  <
+  BOP_Leq,          //  <=
+  BOP_Cmp,          //  <=>
+  BOP_LogicAnd,     //  &&  (no short-circuit)
+  BOP_LogicOr       //  ||  (no short-circuit)
+};
+
+/// Opcode for cast operations.
+enum TIL_CastOpcode : unsigned char {
+  CAST_none = 0,
+
+  // Extend precision of numeric type
+  CAST_extendNum,
+
+  // Truncate precision of numeric type
+  CAST_truncNum,
+
+  // Convert to floating point type
+  CAST_toFloat,
+
+  // Convert to integer type
+  CAST_toInt,
+
+  // Convert smart pointer to pointer (C++ only)
+  CAST_objToPtr
+};
+
+const TIL_Opcode       COP_Min  = COP_Future;
+const TIL_Opcode       COP_Max  = COP_Branch;
+const TIL_UnaryOpcode  UOP_Min  = UOP_Minus;
+const TIL_UnaryOpcode  UOP_Max  = UOP_LogicNot;
+const TIL_BinaryOpcode BOP_Min  = BOP_Add;
+const TIL_BinaryOpcode BOP_Max  = BOP_LogicOr;
+const TIL_CastOpcode   CAST_Min = CAST_none;
+const TIL_CastOpcode   CAST_Max = CAST_toInt;
+
+/// Return the name of a unary opcode.
+StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
+
+/// Return the name of a binary opcode.
+StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
+
+/// ValueTypes are data types that can actually be held in registers.
+/// All variables and expressions must have a value type.
+/// Pointer types are further subdivided into the various heap-allocated
+/// types, such as functions, records, etc.
+/// Structured types that are passed by value (e.g. complex numbers)
+/// require special handling; they use BT_ValueRef, and size ST_0.
+struct ValueType {
+  enum BaseType : unsigned char {
+    BT_Void = 0,
+    BT_Bool,
+    BT_Int,
+    BT_Float,
+    BT_String,    // String literals
+    BT_Pointer,
+    BT_ValueRef
+  };
+
+  enum SizeType : unsigned char {
+    ST_0 = 0,
+    ST_1,
+    ST_8,
+    ST_16,
+    ST_32,
+    ST_64,
+    ST_128
+  };
+
+  ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
+      : Base(B), Size(Sz), Signed(S), VectSize(VS) {}
+
+  inline static SizeType getSizeType(unsigned nbytes);
+
+  template <class T>
+  inline static ValueType getValueType();
+
+  BaseType Base;
+  SizeType Size;
+  bool Signed;
+
+  // 0 for scalar, otherwise num elements in vector
+  unsigned char VectSize;
+};
+
+inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
+  switch (nbytes) {
+    case 1: return ST_8;
+    case 2: return ST_16;
+    case 4: return ST_32;
+    case 8: return ST_64;
+    case 16: return ST_128;
+    default: return ST_0;
+  }
+}
+
+template<>
+inline ValueType ValueType::getValueType<void>() {
+  return ValueType(BT_Void, ST_0, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<bool>() {
+  return ValueType(BT_Bool, ST_1, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<int8_t>() {
+  return ValueType(BT_Int, ST_8, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<uint8_t>() {
+  return ValueType(BT_Int, ST_8, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<int16_t>() {
+  return ValueType(BT_Int, ST_16, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<uint16_t>() {
+  return ValueType(BT_Int, ST_16, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<int32_t>() {
+  return ValueType(BT_Int, ST_32, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<uint32_t>() {
+  return ValueType(BT_Int, ST_32, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<int64_t>() {
+  return ValueType(BT_Int, ST_64, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<uint64_t>() {
+  return ValueType(BT_Int, ST_64, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<float>() {
+  return ValueType(BT_Float, ST_32, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<double>() {
+  return ValueType(BT_Float, ST_64, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<long double>() {
+  return ValueType(BT_Float, ST_128, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<StringRef>() {
+  return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<void*>() {
+  return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
+}
+
+/// Base class for AST nodes in the typed intermediate language.
+class SExpr {
+public:
+  SExpr() = delete;
+
+  TIL_Opcode opcode() const { return Opcode; }
+
+  // Subclasses of SExpr must define the following:
+  //
+  // This(const This& E, ...) {
+  //   copy constructor: construct copy of E, with some additional arguments.
+  // }
+  //
+  // template <class V>
+  // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+  //   traverse all subexpressions, following the traversal/rewriter interface.
+  // }
+  //
+  // template <class C> typename C::CType compare(CType* E, C& Cmp) {
+  //   compare all subexpressions, following the comparator interface
+  // }
+  void *operator new(size_t S, MemRegionRef &R) {
+    return ::operator new(S, R);
+  }
+
+  /// SExpr objects must be created in an arena.
+  void *operator new(size_t) = delete;
+
+  /// SExpr objects cannot be deleted.
+  // This declaration is public to workaround a gcc bug that breaks building
+  // with REQUIRES_EH=1.
+  void operator delete(void *) = delete;
+
+  /// Returns the instruction ID for this expression.
+  /// All basic block instructions have a unique ID (i.e. virtual register).
+  unsigned id() const { return SExprID; }
+
+  /// Returns the block, if this is an instruction in a basic block,
+  /// otherwise returns null.
+  BasicBlock *block() const { return Block; }
+
+  /// Set the basic block and instruction ID for this expression.
+  void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
+
+protected:
+  SExpr(TIL_Opcode Op) : Opcode(Op) {}
+  SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {}
+
+  const TIL_Opcode Opcode;
+  unsigned char Reserved = 0;
+  unsigned short Flags = 0;
+  unsigned SExprID = 0;
+  BasicBlock *Block = nullptr;
+};
+
+// Contains various helper functions for SExprs.
+namespace ThreadSafetyTIL {
+
+inline bool isTrivial(const SExpr *E) {
+  TIL_Opcode Op = E->opcode();
+  return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
+}
+
+} // namespace ThreadSafetyTIL
+
+// Nodes which declare variables
+
+/// A named variable, e.g. "x".
+///
+/// There are two distinct places in which a Variable can appear in the AST.
+/// A variable declaration introduces a new variable, and can occur in 3 places:
+///   Let-expressions:           (Let (x = t) u)
+///   Functions:                 (Function (x : t) u)
+///   Self-applicable functions  (SFunction (x) t)
+///
+/// If a variable occurs in any other location, it is a reference to an existing
+/// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
+/// allocate a separate AST node for variable references; a reference is just a
+/// pointer to the original declaration.
+class Variable : public SExpr {
+public:
+  enum VariableKind {
+    /// Let-variable
+    VK_Let,
+
+    /// Function parameter
+    VK_Fun,
+
+    /// SFunction (self) parameter
+    VK_SFun
+  };
+
+  Variable(StringRef s, SExpr *D = nullptr)
+      : SExpr(COP_Variable), Name(s), Definition(D) {
+    Flags = VK_Let;
+  }
+
+  Variable(SExpr *D, const ValueDecl *Cvd = nullptr)
+      : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
+        Definition(D), Cvdecl(Cvd) {
+    Flags = VK_Let;
+  }
+
+  Variable(const Variable &Vd, SExpr *D)  // rewrite constructor
+      : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
+    Flags = Vd.kind();
+  }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
+
+  /// Return the kind of variable (let, function param, or self)
+  VariableKind kind() const { return static_cast<VariableKind>(Flags); }
+
+  /// Return the name of the variable, if any.
+  StringRef name() const { return Name; }
+
+  /// Return the clang declaration for this variable, if any.
+  const ValueDecl *clangDecl() const { return Cvdecl; }
+
+  /// Return the definition of the variable.
+  /// For let-vars, this is the setting expression.
+  /// For function and self parameters, it is the type of the variable.
+  SExpr *definition() { return Definition; }
+  const SExpr *definition() const { return Definition; }
+
+  void setName(StringRef S)    { Name = S;  }
+  void setKind(VariableKind K) { Flags = K; }
+  void setDefinition(SExpr *E) { Definition = E; }
+  void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    // This routine is only called for variable references.
+    return Vs.reduceVariableRef(this);
+  }
+
+  template <class C>
+  typename C::CType compare(const Variable* E, C& Cmp) const {
+    return Cmp.compareVariableRefs(this, E);
+  }
+
+private:
+  friend class BasicBlock;
+  friend class Function;
+  friend class Let;
+  friend class SFunction;
+
+  // The name of the variable.
+  StringRef Name;
+
+  // The TIL type or definition.
+  SExpr *Definition;
+
+  // The clang declaration for this variable.
+  const ValueDecl *Cvdecl = nullptr;
+};
+
+/// Placeholder for an expression that has not yet been created.
+/// Used to implement lazy copy and rewriting strategies.
+class Future : public SExpr {
+public:
+  enum FutureStatus {
+    FS_pending,
+    FS_evaluating,
+    FS_done
+  };
+
+  Future() : SExpr(COP_Future) {}
+  virtual ~Future() = delete;
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
+
+  // A lazy rewriting strategy should subclass Future and override this method.
+  virtual SExpr *compute() { return nullptr; }
+
+  // Return the result of this future if it exists, otherwise return null.
+  SExpr *maybeGetResult() const { return Result; }
+
+  // Return the result of this future; forcing it if necessary.
+  SExpr *result() {
+    switch (Status) {
+    case FS_pending:
+      return force();
+    case FS_evaluating:
+      return nullptr; // infinite loop; illegal recursion.
+    case FS_done:
+      return Result;
+    }
+  }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    assert(Result && "Cannot traverse Future that has not been forced.");
+    return Vs.traverse(Result, Ctx);
+  }
+
+  template <class C>
+  typename C::CType compare(const Future* E, C& Cmp) const {
+    if (!Result || !E->Result)
+      return Cmp.comparePointers(this, E);
+    return Cmp.compare(Result, E->Result);
+  }
+
+private:
+  SExpr* force();
+
+  FutureStatus Status = FS_pending;
+  SExpr *Result = nullptr;
+};
+
+/// Placeholder for expressions that cannot be represented in the TIL.
+class Undefined : public SExpr {
+public:
+  Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
+  Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    return Vs.reduceUndefined(*this);
+  }
+
+  template <class C>
+  typename C::CType compare(const Undefined* E, C& Cmp) const {
+    return Cmp.trueResult();
+  }
+
+private:
+  const Stmt *Cstmt;
+};
+
+/// Placeholder for a wildcard that matches any other expression.
+class Wildcard : public SExpr {
+public:
+  Wildcard() : SExpr(COP_Wildcard) {}
+  Wildcard(const Wildcard &) = default;
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
+
+  template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    return Vs.reduceWildcard(*this);
+  }
+
+  template <class C>
+  typename C::CType compare(const Wildcard* E, C& Cmp) const {
+    return Cmp.trueResult();
+  }
+};
+
+template <class T> class LiteralT;
+
+// Base class for literal values.
+class Literal : public SExpr {
+public:
+  Literal(const Expr *C)
+     : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {}
+  Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {}
+  Literal(const Literal &) = default;
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
+
+  // The clang expression for this literal.
+  const Expr *clangExpr() const { return Cexpr; }
+
+  ValueType valueType() const { return ValType; }
+
+  template<class T> const LiteralT<T>& as() const {
+    return *static_cast<const LiteralT<T>*>(this);
+  }
+  template<class T> LiteralT<T>& as() {
+    return *static_cast<LiteralT<T>*>(this);
+  }
+
+  template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
+
+  template <class C>
+  typename C::CType compare(const Literal* E, C& Cmp) const {
+    // TODO: defer actual comparison to LiteralT
+    return Cmp.trueResult();
+  }
+
+private:
+  const ValueType ValType;
+  const Expr *Cexpr = nullptr;
+};
+
+// Derived class for literal values, which stores the actual value.
+template<class T>
+class LiteralT : public Literal {
+public:
+  LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {}
+  LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {}
+
+  T value() const { return Val;}
+  T& value() { return Val; }
+
+private:
+  T Val;
+};
+
+template <class V>
+typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
+  if (Cexpr)
+    return Vs.reduceLiteral(*this);
+
+  switch (ValType.Base) {
+  case ValueType::BT_Void:
+    break;
+  case ValueType::BT_Bool:
+    return Vs.reduceLiteralT(as<bool>());
+  case ValueType::BT_Int: {
+    switch (ValType.Size) {
+    case ValueType::ST_8:
+      if (ValType.Signed)
+        return Vs.reduceLiteralT(as<int8_t>());
+      else
+        return Vs.reduceLiteralT(as<uint8_t>());
+    case ValueType::ST_16:
+      if (ValType.Signed)
+        return Vs.reduceLiteralT(as<int16_t>());
+      else
+        return Vs.reduceLiteralT(as<uint16_t>());
+    case ValueType::ST_32:
+      if (ValType.Signed)
+        return Vs.reduceLiteralT(as<int32_t>());
+      else
+        return Vs.reduceLiteralT(as<uint32_t>());
+    case ValueType::ST_64:
+      if (ValType.Signed)
+        return Vs.reduceLiteralT(as<int64_t>());
+      else
+        return Vs.reduceLiteralT(as<uint64_t>());
+    default:
+      break;
+    }
+  }
+  case ValueType::BT_Float: {
+    switch (ValType.Size) {
+    case ValueType::ST_32:
+      return Vs.reduceLiteralT(as<float>());
+    case ValueType::ST_64:
+      return Vs.reduceLiteralT(as<double>());
+    default:
+      break;
+    }
+  }
+  case ValueType::BT_String:
+    return Vs.reduceLiteralT(as<StringRef>());
+  case ValueType::BT_Pointer:
+    return Vs.reduceLiteralT(as<void*>());
+  case ValueType::BT_ValueRef:
+    break;
+  }
+  return Vs.reduceLiteral(*this);
+}
+
+/// A Literal pointer to an object allocated in memory.
+/// At compile time, pointer literals are represented by symbolic names.
+class LiteralPtr : public SExpr {
+public:
+  LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
+  LiteralPtr(const LiteralPtr &) = default;
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
+
+  // The clang declaration for the value that this pointer points to.
+  const ValueDecl *clangDecl() const { return Cvdecl; }
+  void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    return Vs.reduceLiteralPtr(*this);
+  }
+
+  template <class C>
+  typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
+    if (!Cvdecl || !E->Cvdecl)
+      return Cmp.comparePointers(this, E);
+    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
+  }
+
+private:
+  const ValueDecl *Cvdecl;
+};
+
+/// A function -- a.k.a. lambda abstraction.
+/// Functions with multiple arguments are created by currying,
+/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y })))
+class Function : public SExpr {
+public:
+  Function(Variable *Vd, SExpr *Bd)
+      : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
+    Vd->setKind(Variable::VK_Fun);
+  }
+
+  Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
+      : SExpr(F), VarDecl(Vd), Body(Bd) {
+    Vd->setKind(Variable::VK_Fun);
+  }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
+
+  Variable *variableDecl()  { return VarDecl; }
+  const Variable *variableDecl() const { return VarDecl; }
+
+  SExpr *body() { return Body; }
+  const SExpr *body() const { return Body; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    // This is a variable declaration, so traverse the definition.
+    auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
+    // Tell the rewriter to enter the scope of the function.
+    Variable *Nvd = Vs.enterScope(*VarDecl, E0);
+    auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
+    Vs.exitScope(*VarDecl);
+    return Vs.reduceFunction(*this, Nvd, E1);
+  }
+
+  template <class C>
+  typename C::CType compare(const Function* E, C& Cmp) const {
+    typename C::CType Ct =
+      Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    Cmp.enterScope(variableDecl(), E->variableDecl());
+    Ct = Cmp.compare(body(), E->body());
+    Cmp.leaveScope();
+    return Ct;
+  }
+
+private:
+  Variable *VarDecl;
+  SExpr* Body;
+};
+
+/// A self-applicable function.
+/// A self-applicable function can be applied to itself.  It's useful for
+/// implementing objects and late binding.
+class SFunction : public SExpr {
+public:
+  SFunction(Variable *Vd, SExpr *B)
+      : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
+    assert(Vd->Definition == nullptr);
+    Vd->setKind(Variable::VK_SFun);
+    Vd->Definition = this;
+  }
+
+  SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
+      : SExpr(F), VarDecl(Vd), Body(B) {
+    assert(Vd->Definition == nullptr);
+    Vd->setKind(Variable::VK_SFun);
+    Vd->Definition = this;
+  }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
+
+  Variable *variableDecl() { return VarDecl; }
+  const Variable *variableDecl() const { return VarDecl; }
+
+  SExpr *body() { return Body; }
+  const SExpr *body() const { return Body; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    // A self-variable points to the SFunction itself.
+    // A rewrite must introduce the variable with a null definition, and update
+    // it after 'this' has been rewritten.
+    Variable *Nvd = Vs.enterScope(*VarDecl, nullptr);
+    auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
+    Vs.exitScope(*VarDecl);
+    // A rewrite operation will call SFun constructor to set Vvd->Definition.
+    return Vs.reduceSFunction(*this, Nvd, E1);
+  }
+
+  template <class C>
+  typename C::CType compare(const SFunction* E, C& Cmp) const {
+    Cmp.enterScope(variableDecl(), E->variableDecl());
+    typename C::CType Ct = Cmp.compare(body(), E->body());
+    Cmp.leaveScope();
+    return Ct;
+  }
+
+private:
+  Variable *VarDecl;
+  SExpr* Body;
+};
+
+/// A block of code -- e.g. the body of a function.
+class Code : public SExpr {
+public:
+  Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
+  Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
+      : SExpr(C), ReturnType(T), Body(B) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
+
+  SExpr *returnType() { return ReturnType; }
+  const SExpr *returnType() const { return ReturnType; }
+
+  SExpr *body() { return Body; }
+  const SExpr *body() const { return Body; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
+    auto Nb = Vs.traverse(Body,       Vs.lazyCtx(Ctx));
+    return Vs.reduceCode(*this, Nt, Nb);
+  }
+
+  template <class C>
+  typename C::CType compare(const Code* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(body(), E->body());
+  }
+
+private:
+  SExpr* ReturnType;
+  SExpr* Body;
+};
+
+/// A typed, writable location in memory
+class Field : public SExpr {
+public:
+  Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
+  Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
+      : SExpr(C), Range(R), Body(B) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
+
+  SExpr *range() { return Range; }
+  const SExpr *range() const { return Range; }
+
+  SExpr *body() { return Body; }
+  const SExpr *body() const { return Body; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
+    auto Nb = Vs.traverse(Body,  Vs.lazyCtx(Ctx));
+    return Vs.reduceField(*this, Nr, Nb);
+  }
+
+  template <class C>
+  typename C::CType compare(const Field* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(range(), E->range());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(body(), E->body());
+  }
+
+private:
+  SExpr* Range;
+  SExpr* Body;
+};
+
+/// Apply an argument to a function.
+/// Note that this does not actually call the function.  Functions are curried,
+/// so this returns a closure in which the first parameter has been applied.
+/// Once all parameters have been applied, Call can be used to invoke the
+/// function.
+class Apply : public SExpr {
+public:
+  Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
+  Apply(const Apply &A, SExpr *F, SExpr *Ar)  // rewrite constructor
+      : SExpr(A), Fun(F), Arg(Ar) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
+
+  SExpr *fun() { return Fun; }
+  const SExpr *fun() const { return Fun; }
+
+  SExpr *arg() { return Arg; }
+  const SExpr *arg() const { return Arg; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
+    auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
+    return Vs.reduceApply(*this, Nf, Na);
+  }
+
+  template <class C>
+  typename C::CType compare(const Apply* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(fun(), E->fun());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(arg(), E->arg());
+  }
+
+private:
+  SExpr* Fun;
+  SExpr* Arg;
+};
+
+/// Apply a self-argument to a self-applicable function.
+class SApply : public SExpr {
+public:
+  SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
+  SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
+      : SExpr(A), Sfun(Sf), Arg(Ar) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
+
+  SExpr *sfun() { return Sfun; }
+  const SExpr *sfun() const { return Sfun; }
+
+  SExpr *arg() { return Arg ? Arg : Sfun; }
+  const SExpr *arg() const { return Arg ? Arg : Sfun; }
+
+  bool isDelegation() const { return Arg != nullptr; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
+    typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
+                                       : nullptr;
+    return Vs.reduceSApply(*this, Nf, Na);
+  }
+
+  template <class C>
+  typename C::CType compare(const SApply* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
+    if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
+      return Ct;
+    return Cmp.compare(arg(), E->arg());
+  }
+
+private:
+  SExpr* Sfun;
+  SExpr* Arg;
+};
+
+/// Project a named slot from a C++ struct or class.
+class Project : public SExpr {
+public:
+  Project(SExpr *R, const ValueDecl *Cvd)
+      : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {
+    assert(Cvd && "ValueDecl must not be null");
+  }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
+
+  SExpr *record() { return Rec; }
+  const SExpr *record() const { return Rec; }
+
+  const ValueDecl *clangDecl() const { return Cvdecl; }
+
+  bool isArrow() const { return (Flags & 0x01) != 0; }
+
+  void setArrow(bool b) {
+    if (b) Flags |= 0x01;
+    else Flags &= 0xFFFE;
+  }
+
+  StringRef slotName() const {
+    if (Cvdecl->getDeclName().isIdentifier())
+      return Cvdecl->getName();
+    if (!SlotName) {
+      SlotName = "";
+      llvm::raw_string_ostream OS(*SlotName);
+      Cvdecl->printName(OS);
+    }
+    return *SlotName;
+  }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
+    return Vs.reduceProject(*this, Nr);
+  }
+
+  template <class C>
+  typename C::CType compare(const Project* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(record(), E->record());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
+  }
+
+private:
+  SExpr* Rec;
+  mutable std::optional<std::string> SlotName;
+  const ValueDecl *Cvdecl;
+};
+
+/// Call a function (after all arguments have been applied).
+class Call : public SExpr {
+public:
+  Call(SExpr *T, const CallExpr *Ce = nullptr)
+      : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
+  Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
+
+  SExpr *target() { return Target; }
+  const SExpr *target() const { return Target; }
+
+  const CallExpr *clangCallExpr() const { return Cexpr; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
+    return Vs.reduceCall(*this, Nt);
+  }
+
+  template <class C>
+  typename C::CType compare(const Call* E, C& Cmp) const {
+    return Cmp.compare(target(), E->target());
+  }
+
+private:
+  SExpr* Target;
+  const CallExpr *Cexpr;
+};
+
+/// Allocate memory for a new value on the heap or stack.
+class Alloc : public SExpr {
+public:
+  enum AllocKind {
+    AK_Stack,
+    AK_Heap
+  };
+
+  Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
+  Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
+
+  AllocKind kind() const { return static_cast<AllocKind>(Flags); }
+
+  SExpr *dataType() { return Dtype; }
+  const SExpr *dataType() const { return Dtype; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
+    return Vs.reduceAlloc(*this, Nd);
+  }
+
+  template <class C>
+  typename C::CType compare(const Alloc* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(dataType(), E->dataType());
+  }
+
+private:
+  SExpr* Dtype;
+};
+
+/// Load a value from memory.
+class Load : public SExpr {
+public:
+  Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
+  Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
+
+  SExpr *pointer() { return Ptr; }
+  const SExpr *pointer() const { return Ptr; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
+    return Vs.reduceLoad(*this, Np);
+  }
+
+  template <class C>
+  typename C::CType compare(const Load* E, C& Cmp) const {
+    return Cmp.compare(pointer(), E->pointer());
+  }
+
+private:
+  SExpr* Ptr;
+};
+
+/// Store a value to memory.
+/// The destination is a pointer to a field, the source is the value to store.
+class Store : public SExpr {
+public:
+  Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
+  Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
+
+  SExpr *destination() { return Dest; }  // Address to store to
+  const SExpr *destination() const { return Dest; }
+
+  SExpr *source() { return Source; }     // Value to store
+  const SExpr *source() const { return Source; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Np = Vs.traverse(Dest,   Vs.subExprCtx(Ctx));
+    auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
+    return Vs.reduceStore(*this, Np, Nv);
+  }
+
+  template <class C>
+  typename C::CType compare(const Store* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(destination(), E->destination());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(source(), E->source());
+  }
+
+private:
+  SExpr* Dest;
+  SExpr* Source;
+};
+
+/// If p is a reference to an array, then p[i] is a reference to the i'th
+/// element of the array.
+class ArrayIndex : public SExpr {
+public:
+  ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
+  ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
+      : SExpr(E), Array(A), Index(N) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
+
+  SExpr *array() { return Array; }
+  const SExpr *array() const { return Array; }
+
+  SExpr *index() { return Index; }
+  const SExpr *index() const { return Index; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
+    auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
+    return Vs.reduceArrayIndex(*this, Na, Ni);
+  }
+
+  template <class C>
+  typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(array(), E->array());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(index(), E->index());
+  }
+
+private:
+  SExpr* Array;
+  SExpr* Index;
+};
+
+/// Pointer arithmetic, restricted to arrays only.
+/// If p is a reference to an array, then p + n, where n is an integer, is
+/// a reference to a subarray.
+class ArrayAdd : public SExpr {
+public:
+  ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
+  ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
+      : SExpr(E), Array(A), Index(N) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
+
+  SExpr *array() { return Array; }
+  const SExpr *array() const { return Array; }
+
+  SExpr *index() { return Index; }
+  const SExpr *index() const { return Index; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
+    auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
+    return Vs.reduceArrayAdd(*this, Na, Ni);
+  }
+
+  template <class C>
+  typename C::CType compare(const ArrayAdd* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(array(), E->array());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(index(), E->index());
+  }
+
+private:
+  SExpr* Array;
+  SExpr* Index;
+};
+
+/// Simple arithmetic unary operations, e.g. negate and not.
+/// These operations have no side-effects.
+class UnaryOp : public SExpr {
+public:
+  UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
+    Flags = Op;
+  }
+
+  UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
+
+  TIL_UnaryOpcode unaryOpcode() const {
+    return static_cast<TIL_UnaryOpcode>(Flags);
+  }
+
+  SExpr *expr() { return Expr0; }
+  const SExpr *expr() const { return Expr0; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
+    return Vs.reduceUnaryOp(*this, Ne);
+  }
+
+  template <class C>
+  typename C::CType compare(const UnaryOp* E, C& Cmp) const {
+    typename C::CType Ct =
+      Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(expr(), E->expr());
+  }
+
+private:
+  SExpr* Expr0;
+};
+
+/// Simple arithmetic binary operations, e.g. +, -, etc.
+/// These operations have no side effects.
+class BinaryOp : public SExpr {
+public:
+  BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
+      : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
+    Flags = Op;
+  }
+
+  BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
+      : SExpr(B), Expr0(E0), Expr1(E1) {
+    Flags = B.Flags;
+  }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
+
+  TIL_BinaryOpcode binaryOpcode() const {
+    return static_cast<TIL_BinaryOpcode>(Flags);
+  }
+
+  SExpr *expr0() { return Expr0; }
+  const SExpr *expr0() const { return Expr0; }
+
+  SExpr *expr1() { return Expr1; }
+  const SExpr *expr1() const { return Expr1; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
+    auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
+    return Vs.reduceBinaryOp(*this, Ne0, Ne1);
+  }
+
+  template <class C>
+  typename C::CType compare(const BinaryOp* E, C& Cmp) const {
+    typename C::CType Ct =
+      Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    Ct = Cmp.compare(expr0(), E->expr0());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(expr1(), E->expr1());
+  }
+
+private:
+  SExpr* Expr0;
+  SExpr* Expr1;
+};
+
+/// Cast expressions.
+/// Cast expressions are essentially unary operations, but we treat them
+/// as a distinct AST node because they only change the type of the result.
+class Cast : public SExpr {
+public:
+  Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
+  Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
+
+  TIL_CastOpcode castOpcode() const {
+    return static_cast<TIL_CastOpcode>(Flags);
+  }
+
+  SExpr *expr() { return Expr0; }
+  const SExpr *expr() const { return Expr0; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
+    return Vs.reduceCast(*this, Ne);
+  }
+
+  template <class C>
+  typename C::CType compare(const Cast* E, C& Cmp) const {
+    typename C::CType Ct =
+      Cmp.compareIntegers(castOpcode(), E->castOpcode());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(expr(), E->expr());
+  }
+
+private:
+  SExpr* Expr0;
+};
+
+class SCFG;
+
+/// Phi Node, for code in SSA form.
+/// Each Phi node has an array of possible values that it can take,
+/// depending on where control flow comes from.
+class Phi : public SExpr {
+public:
+  using ValArray = SimpleArray<SExpr *>;
+
+  // In minimal SSA form, all Phi nodes are MultiVal.
+  // During conversion to SSA, incomplete Phi nodes may be introduced, which
+  // are later determined to be SingleVal, and are thus redundant.
+  enum Status {
+    PH_MultiVal = 0, // Phi node has multiple distinct values.  (Normal)
+    PH_SingleVal,    // Phi node has one distinct value, and can be eliminated
+    PH_Incomplete    // Phi node is incomplete
+  };
+
+  Phi() : SExpr(COP_Phi) {}
+  Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals)  {}
+  Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
+
+  const ValArray &values() const { return Values; }
+  ValArray &values() { return Values; }
+
+  Status status() const { return static_cast<Status>(Flags); }
+  void setStatus(Status s) { Flags = s; }
+
+  /// Return the clang declaration of the variable for this Phi node, if any.
+  const ValueDecl *clangDecl() const { return Cvdecl; }
+
+  /// Set the clang variable associated with this Phi node.
+  void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    typename V::template Container<typename V::R_SExpr>
+      Nvs(Vs, Values.size());
+
+    for (const auto *Val : Values)
+      Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
+    return Vs.reducePhi(*this, Nvs);
+  }
+
+  template <class C>
+  typename C::CType compare(const Phi *E, C &Cmp) const {
+    // TODO: implement CFG comparisons
+    return Cmp.comparePointers(this, E);
+  }
+
+private:
+  ValArray Values;
+  const ValueDecl* Cvdecl = nullptr;
+};
+
+/// Base class for basic block terminators:  Branch, Goto, and Return.
+class Terminator : public SExpr {
+protected:
+  Terminator(TIL_Opcode Op) : SExpr(Op) {}
+  Terminator(const SExpr &E) : SExpr(E) {}
+
+public:
+  static bool classof(const SExpr *E) {
+    return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
+  }
+
+  /// Return the list of basic blocks that this terminator can branch to.
+  ArrayRef<BasicBlock *> successors();
+
+  ArrayRef<BasicBlock *> successors() const {
+    return const_cast<Terminator*>(this)->successors();
+  }
+};
+
+/// Jump to another basic block.
+/// A goto instruction is essentially a tail-recursive call into another
+/// block.  In addition to the block pointer, it specifies an index into the
+/// phi nodes of that block.  The index can be used to retrieve the "arguments"
+/// of the call.
+class Goto : public Terminator {
+public:
+  Goto(BasicBlock *B, unsigned I)
+      : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
+  Goto(const Goto &G, BasicBlock *B, unsigned I)
+      : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
+
+  const BasicBlock *targetBlock() const { return TargetBlock; }
+  BasicBlock *targetBlock() { return TargetBlock; }
+
+  /// Returns the index into the
+  unsigned index() const { return Index; }
+
+  /// Return the list of basic blocks that this terminator can branch to.
+  ArrayRef<BasicBlock *> successors() { return TargetBlock; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
+    return Vs.reduceGoto(*this, Ntb);
+  }
+
+  template <class C>
+  typename C::CType compare(const Goto *E, C &Cmp) const {
+    // TODO: implement CFG comparisons
+    return Cmp.comparePointers(this, E);
+  }
+
+private:
+  BasicBlock *TargetBlock;
+  unsigned Index;
+};
+
+/// A conditional branch to two other blocks.
+/// Note that unlike Goto, Branch does not have an index.  The target blocks
+/// must be child-blocks, and cannot have Phi nodes.
+class Branch : public Terminator {
+public:
+  Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
+      : Terminator(COP_Branch), Condition(C) {
+    Branches[0] = T;
+    Branches[1] = E;
+  }
+
+  Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
+      : Terminator(Br), Condition(C) {
+    Branches[0] = T;
+    Branches[1] = E;
+  }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
+
+  const SExpr *condition() const { return Condition; }
+  SExpr *condition() { return Condition; }
+
+  const BasicBlock *thenBlock() const { return Branches[0]; }
+  BasicBlock *thenBlock() { return Branches[0]; }
+
+  const BasicBlock *elseBlock() const { return Branches[1]; }
+  BasicBlock *elseBlock() { return Branches[1]; }
+
+  /// Return the list of basic blocks that this terminator can branch to.
+  ArrayRef<BasicBlock *> successors() { return llvm::ArrayRef(Branches); }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
+    BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]);
+    BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]);
+    return Vs.reduceBranch(*this, Nc, Ntb, Nte);
+  }
+
+  template <class C>
+  typename C::CType compare(const Branch *E, C &Cmp) const {
+    // TODO: implement CFG comparisons
+    return Cmp.comparePointers(this, E);
+  }
+
+private:
+  SExpr *Condition;
+  BasicBlock *Branches[2];
+};
+
+/// Return from the enclosing function, passing the return value to the caller.
+/// Only the exit block should end with a return statement.
+class Return : public Terminator {
+public:
+  Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
+  Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
+
+  /// Return an empty list.
+  ArrayRef<BasicBlock *> successors() { return std::nullopt; }
+
+  SExpr *returnValue() { return Retval; }
+  const SExpr *returnValue() const { return Retval; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx));
+    return Vs.reduceReturn(*this, Ne);
+  }
+
+  template <class C>
+  typename C::CType compare(const Return *E, C &Cmp) const {
+    return Cmp.compare(Retval, E->Retval);
+  }
+
+private:
+  SExpr* Retval;
+};
+
+inline ArrayRef<BasicBlock*> Terminator::successors() {
+  switch (opcode()) {
+    case COP_Goto:   return cast<Goto>(this)->successors();
+    case COP_Branch: return cast<Branch>(this)->successors();
+    case COP_Return: return cast<Return>(this)->successors();
+    default:
+      return std::nullopt;
+  }
+}
+
+/// A basic block is part of an SCFG.  It can be treated as a function in
+/// continuation passing style.  A block consists of a sequence of phi nodes,
+/// which are "arguments" to the function, followed by a sequence of
+/// instructions.  It ends with a Terminator, which is a Branch or Goto to
+/// another basic block in the same SCFG.
+class BasicBlock : public SExpr {
+public:
+  using InstrArray = SimpleArray<SExpr *>;
+  using BlockArray = SimpleArray<BasicBlock *>;
+
+  // TopologyNodes are used to overlay tree structures on top of the CFG,
+  // such as dominator and postdominator trees.  Each block is assigned an
+  // ID in the tree according to a depth-first search.  Tree traversals are
+  // always up, towards the parents.
+  struct TopologyNode {
+    int NodeID = 0;
+
+    // Includes this node, so must be > 1.
+    int SizeOfSubTree = 0;
+
+    // Pointer to parent.
+    BasicBlock *Parent = nullptr;
+
+    TopologyNode() = default;
+
+    bool isParentOf(const TopologyNode& OtherNode) {
+      return OtherNode.NodeID > NodeID &&
+             OtherNode.NodeID < NodeID + SizeOfSubTree;
+    }
+
+    bool isParentOfOrEqual(const TopologyNode& OtherNode) {
+      return OtherNode.NodeID >= NodeID &&
+             OtherNode.NodeID < NodeID + SizeOfSubTree;
+    }
+  };
+
+  explicit BasicBlock(MemRegionRef A)
+      : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {}
+  BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is,
+             Terminator *T)
+      : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false),
+        Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
+
+  /// Returns the block ID.  Every block has a unique ID in the CFG.
+  int blockID() const { return BlockID; }
+
+  /// Returns the number of predecessors.
+  size_t numPredecessors() const { return Predecessors.size(); }
+  size_t numSuccessors() const { return successors().size(); }
+
+  const SCFG* cfg() const { return CFGPtr; }
+  SCFG* cfg() { return CFGPtr; }
+
+  const BasicBlock *parent() const { return DominatorNode.Parent; }
+  BasicBlock *parent() { return DominatorNode.Parent; }
+
+  const InstrArray &arguments() const { return Args; }
+  InstrArray &arguments() { return Args; }
+
+  InstrArray &instructions() { return Instrs; }
+  const InstrArray &instructions() const { return Instrs; }
+
+  /// Returns a list of predecessors.
+  /// The order of predecessors in the list is important; each phi node has
+  /// exactly one argument for each precessor, in the same order.
+  BlockArray &predecessors() { return Predecessors; }
+  const BlockArray &predecessors() const { return Predecessors; }
+
+  ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
+  ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
+
+  const Terminator *terminator() const { return TermInstr; }
+  Terminator *terminator() { return TermInstr; }
+
+  void setTerminator(Terminator *E) { TermInstr = E; }
+
+  bool Dominates(const BasicBlock &Other) {
+    return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
+  }
+
+  bool PostDominates(const BasicBlock &Other) {
+    return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
+  }
+
+  /// Add a new argument.
+  void addArgument(Phi *V) {
+    Args.reserveCheck(1, Arena);
+    Args.push_back(V);
+  }
+
+  /// Add a new instruction.
+  void addInstruction(SExpr *V) {
+    Instrs.reserveCheck(1, Arena);
+    Instrs.push_back(V);
+  }
+
+  // Add a new predecessor, and return the phi-node index for it.
+  // Will add an argument to all phi-nodes, initialized to nullptr.
+  unsigned addPredecessor(BasicBlock *Pred);
+
+  // Reserve space for Nargs arguments.
+  void reserveArguments(unsigned Nargs)   { Args.reserve(Nargs, Arena); }
+
+  // Reserve space for Nins instructions.
+  void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
+
+  // Reserve space for NumPreds predecessors, including space in phi nodes.
+  void reservePredecessors(unsigned NumPreds);
+
+  /// Return the index of BB, or Predecessors.size if BB is not a predecessor.
+  unsigned findPredecessorIndex(const BasicBlock *BB) const {
+    auto I = llvm::find(Predecessors, BB);
+    return std::distance(Predecessors.cbegin(), I);
+  }
+
+  template <class V>
+  typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
+    typename V::template Container<SExpr*> Nas(Vs, Args.size());
+    typename V::template Container<SExpr*> Nis(Vs, Instrs.size());
+
+    // Entering the basic block should do any scope initialization.
+    Vs.enterBasicBlock(*this);
+
+    for (const auto *E : Args) {
+      auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
+      Nas.push_back(Ne);
+    }
+    for (const auto *E : Instrs) {
+      auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
+      Nis.push_back(Ne);
+    }
+    auto Nt = Vs.traverse(TermInstr, Ctx);
+
+    // Exiting the basic block should handle any scope cleanup.
+    Vs.exitBasicBlock(*this);
+
+    return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
+  }
+
+  template <class C>
+  typename C::CType compare(const BasicBlock *E, C &Cmp) const {
+    // TODO: implement CFG comparisons
+    return Cmp.comparePointers(this, E);
+  }
+
+private:
+  friend class SCFG;
+
+  // assign unique ids to all instructions
+  unsigned renumberInstrs(unsigned id);
+
+  unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
+  unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
+  void computeDominator();
+  void computePostDominator();
+
+  // The arena used to allocate this block.
+  MemRegionRef Arena;
+
+  // The CFG that contains this block.
+  SCFG *CFGPtr = nullptr;
+
+  // Unique ID for this BB in the containing CFG. IDs are in topological order.
+  unsigned BlockID : 31;
+
+  // Bit to determine if a block has been visited during a traversal.
+  bool Visited : 1;
+
+  // Predecessor blocks in the CFG.
+  BlockArray Predecessors;
+
+  // Phi nodes. One argument per predecessor.
+  InstrArray Args;
+
+  // Instructions.
+  InstrArray Instrs;
+
+  // Terminating instruction.
+  Terminator *TermInstr = nullptr;
+
+  // The dominator tree.
+  TopologyNode DominatorNode;
+
+  // The post-dominator tree.
+  TopologyNode PostDominatorNode;
+};
+
+/// An SCFG is a control-flow graph.  It consists of a set of basic blocks,
+/// each of which terminates in a branch to another basic block.  There is one
+/// entry point, and one exit point.
+class SCFG : public SExpr {
+public:
+  using BlockArray = SimpleArray<BasicBlock *>;
+  using iterator = BlockArray::iterator;
+  using const_iterator = BlockArray::const_iterator;
+
+  SCFG(MemRegionRef A, unsigned Nblocks)
+      : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) {
+    Entry = new (A) BasicBlock(A);
+    Exit  = new (A) BasicBlock(A);
+    auto *V = new (A) Phi();
+    Exit->addArgument(V);
+    Exit->setTerminator(new (A) Return(V));
+    add(Entry);
+    add(Exit);
+  }
+
+  SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
+      : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) {
+    // TODO: set entry and exit!
+  }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
+
+  /// Return true if this CFG is valid.
+  bool valid() const { return Entry && Exit && Blocks.size() > 0; }
+
+  /// Return true if this CFG has been normalized.
+  /// After normalization, blocks are in topological order, and block and
+  /// instruction IDs have been assigned.
+  bool normal() const { return Normal; }
+
+  iterator begin() { return Blocks.begin(); }
+  iterator end() { return Blocks.end(); }
+
+  const_iterator begin() const { return cbegin(); }
+  const_iterator end() const { return cend(); }
+
+  const_iterator cbegin() const { return Blocks.cbegin(); }
+  const_iterator cend() const { return Blocks.cend(); }
+
+  const BasicBlock *entry() const { return Entry; }
+  BasicBlock *entry() { return Entry; }
+  const BasicBlock *exit() const { return Exit; }
+  BasicBlock *exit() { return Exit; }
+
+  /// Return the number of blocks in the CFG.
+  /// Block::blockID() will return a number less than numBlocks();
+  size_t numBlocks() const { return Blocks.size(); }
+
+  /// Return the total number of instructions in the CFG.
+  /// This is useful for building instruction side-tables;
+  /// A call to SExpr::id() will return a number less than numInstructions().
+  unsigned numInstructions() { return NumInstructions; }
+
+  inline void add(BasicBlock *BB) {
+    assert(BB->CFGPtr == nullptr);
+    BB->CFGPtr = this;
+    Blocks.reserveCheck(1, Arena);
+    Blocks.push_back(BB);
+  }
+
+  void setEntry(BasicBlock *BB) { Entry = BB; }
+  void setExit(BasicBlock *BB)  { Exit = BB;  }
+
+  void computeNormalForm();
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    Vs.enterCFG(*this);
+    typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
+
+    for (const auto *B : Blocks) {
+      Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
+    }
+    Vs.exitCFG(*this);
+    return Vs.reduceSCFG(*this, Bbs);
+  }
+
+  template <class C>
+  typename C::CType compare(const SCFG *E, C &Cmp) const {
+    // TODO: implement CFG comparisons
+    return Cmp.comparePointers(this, E);
+  }
+
+private:
+  // assign unique ids to all instructions
+  void renumberInstrs();
+
+  MemRegionRef Arena;
+  BlockArray Blocks;
+  BasicBlock *Entry = nullptr;
+  BasicBlock *Exit = nullptr;
+  unsigned NumInstructions = 0;
+  bool Normal = false;
+};
+
+/// An identifier, e.g. 'foo' or 'x'.
+/// This is a pseduo-term; it will be lowered to a variable or projection.
+class Identifier : public SExpr {
+public:
+  Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {}
+  Identifier(const Identifier &) = default;
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
+
+  StringRef name() const { return Name; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    return Vs.reduceIdentifier(*this);
+  }
+
+  template <class C>
+  typename C::CType compare(const Identifier* E, C& Cmp) const {
+    return Cmp.compareStrings(name(), E->name());
+  }
+
+private:
+  StringRef Name;
+};
+
+/// An if-then-else expression.
+/// This is a pseduo-term; it will be lowered to a branch in a CFG.
+class IfThenElse : public SExpr {
+public:
+  IfThenElse(SExpr *C, SExpr *T, SExpr *E)
+      : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {}
+  IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
+      : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {}
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
+
+  SExpr *condition() { return Condition; }   // Address to store to
+  const SExpr *condition() const { return Condition; }
+
+  SExpr *thenExpr() { return ThenExpr; }     // Value to store
+  const SExpr *thenExpr() const { return ThenExpr; }
+
+  SExpr *elseExpr() { return ElseExpr; }     // Value to store
+  const SExpr *elseExpr() const { return ElseExpr; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
+    auto Nt = Vs.traverse(ThenExpr,  Vs.subExprCtx(Ctx));
+    auto Ne = Vs.traverse(ElseExpr,  Vs.subExprCtx(Ctx));
+    return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
+  }
+
+  template <class C>
+  typename C::CType compare(const IfThenElse* E, C& Cmp) const {
+    typename C::CType Ct = Cmp.compare(condition(), E->condition());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    Ct = Cmp.compare(thenExpr(), E->thenExpr());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    return Cmp.compare(elseExpr(), E->elseExpr());
+  }
+
+private:
+  SExpr* Condition;
+  SExpr* ThenExpr;
+  SExpr* ElseExpr;
+};
+
+/// A let-expression,  e.g.  let x=t; u.
+/// This is a pseduo-term; it will be lowered to instructions in a CFG.
+class Let : public SExpr {
+public:
+  Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
+    Vd->setKind(Variable::VK_Let);
+  }
+
+  Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
+    Vd->setKind(Variable::VK_Let);
+  }
+
+  static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
+
+  Variable *variableDecl()  { return VarDecl; }
+  const Variable *variableDecl() const { return VarDecl; }
+
+  SExpr *body() { return Body; }
+  const SExpr *body() const { return Body; }
+
+  template <class V>
+  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+    // This is a variable declaration, so traverse the definition.
+    auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
+    // Tell the rewriter to enter the scope of the let variable.
+    Variable *Nvd = Vs.enterScope(*VarDecl, E0);
+    auto E1 = Vs.traverse(Body, Ctx);
+    Vs.exitScope(*VarDecl);
+    return Vs.reduceLet(*this, Nvd, E1);
+  }
+
+  template <class C>
+  typename C::CType compare(const Let* E, C& Cmp) const {
+    typename C::CType Ct =
+      Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
+    if (Cmp.notTrue(Ct))
+      return Ct;
+    Cmp.enterScope(variableDecl(), E->variableDecl());
+    Ct = Cmp.compare(body(), E->body());
+    Cmp.leaveScope();
+    return Ct;
+  }
+
+private:
+  Variable *VarDecl;
+  SExpr* Body;
+};
+
+const SExpr *getCanonicalVal(const SExpr *E);
+SExpr* simplifyToCanonicalVal(SExpr *E);
+void simplifyIncompleteArg(til::Phi *Ph);
+
+} // namespace til
+} // namespace threadSafety
+
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h
new file mode 100644
index 0000000000..76d1701c56
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h
@@ -0,0 +1,945 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- ThreadSafetyTraverse.h -----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a framework for doing generic traversals and rewriting
+// operations over the Thread Safety TIL.
+//
+// UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
+#include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include <cstdint>
+#include <ostream>
+
+namespace clang {
+namespace threadSafety {
+namespace til {
+
+// Defines an interface used to traverse SExprs.  Traversals have been made as
+// generic as possible, and are intended to handle any kind of pass over the
+// AST, e.g. visitors, copying, non-destructive rewriting, destructive
+// (in-place) rewriting, hashing, typing, etc.
+//
+// Traversals implement the functional notion of a "fold" operation on SExprs.
+// Each SExpr class provides a traverse method, which does the following:
+//   * e->traverse(v):
+//       // compute a result r_i for each subexpression e_i
+//       for (i = 1..n)  r_i = v.traverse(e_i);
+//       // combine results into a result for e,  where X is the class of e
+//       return v.reduceX(*e, r_1, .. r_n).
+//
+// A visitor can control the traversal by overriding the following methods:
+//   * v.traverse(e):
+//       return v.traverseByCase(e), which returns v.traverseX(e)
+//   * v.traverseX(e):   (X is the class of e)
+//       return e->traverse(v).
+//   * v.reduceX(*e, r_1, .. r_n):
+//       compute a result for a node of type X
+//
+// The reduceX methods control the kind of traversal (visitor, copy, etc.).
+// They are defined in derived classes.
+//
+// Class R defines the basic interface types (R_SExpr).
+template <class Self, class R>
+class Traversal {
+public:
+  Self *self() { return static_cast<Self *>(this); }
+
+  // Traverse an expression -- returning a result of type R_SExpr.
+  // Override this method to do something for every expression, regardless
+  // of which kind it is.
+  // E is a reference, so this can be use for in-place updates.
+  // The type T must be a subclass of SExpr.
+  template <class T>
+  typename R::R_SExpr traverse(T* &E, typename R::R_Ctx Ctx) {
+    return traverseSExpr(E, Ctx);
+  }
+
+  // Override this method to do something for every expression.
+  // Does not allow in-place updates.
+  typename R::R_SExpr traverseSExpr(SExpr *E, typename R::R_Ctx Ctx) {
+    return traverseByCase(E, Ctx);
+  }
+
+  // Helper method to call traverseX(e) on the appropriate type.
+  typename R::R_SExpr traverseByCase(SExpr *E, typename R::R_Ctx Ctx) {
+    switch (E->opcode()) {
+#define TIL_OPCODE_DEF(X)                                                   \
+    case COP_##X:                                                           \
+      return self()->traverse##X(cast<X>(E), Ctx);
+#include "ThreadSafetyOps.def"
+#undef TIL_OPCODE_DEF
+    }
+    return self()->reduceNull();
+  }
+
+// Traverse e, by static dispatch on the type "X" of e.
+// Override these methods to do something for a particular kind of term.
+#define TIL_OPCODE_DEF(X)                                                   \
+  typename R::R_SExpr traverse##X(X *e, typename R::R_Ctx Ctx) {            \
+    return e->traverse(*self(), Ctx);                                       \
+  }
+#include "ThreadSafetyOps.def"
+#undef TIL_OPCODE_DEF
+};
+
+// Base class for simple reducers that don't much care about the context.
+class SimpleReducerBase {
+public:
+  enum TraversalKind {
+    // Ordinary subexpressions.
+    TRV_Normal,
+
+    // Declarations (e.g. function bodies).
+    TRV_Decl,
+
+    // Expressions that require lazy evaluation.
+    TRV_Lazy,
+
+    // Type expressions.
+    TRV_Type
+  };
+
+  // R_Ctx defines a "context" for the traversal, which encodes information
+  // about where a term appears.  This can be used to encoding the
+  // "current continuation" for CPS transforms, or other information.
+  using R_Ctx = TraversalKind;
+
+  // Create context for an ordinary subexpression.
+  R_Ctx subExprCtx(R_Ctx Ctx) { return TRV_Normal; }
+
+  // Create context for a subexpression that occurs in a declaration position
+  // (e.g. function body).
+  R_Ctx declCtx(R_Ctx Ctx) { return TRV_Decl; }
+
+  // Create context for a subexpression that occurs in a position that
+  // should be reduced lazily.  (e.g. code body).
+  R_Ctx lazyCtx(R_Ctx Ctx) { return TRV_Lazy; }
+
+  // Create context for a subexpression that occurs in a type position.
+  R_Ctx typeCtx(R_Ctx Ctx) { return TRV_Type; }
+};
+
+// Base class for traversals that rewrite an SExpr to another SExpr.
+class CopyReducerBase : public SimpleReducerBase {
+public:
+  // R_SExpr is the result type for a traversal.
+  // A copy or non-destructive rewrite returns a newly allocated term.
+  using R_SExpr = SExpr *;
+  using R_BasicBlock = BasicBlock *;
+
+  // Container is a minimal interface used to store results when traversing
+  // SExprs of variable arity, such as Phi, Goto, and SCFG.
+  template <class T> class Container {
+  public:
+    // Allocate a new container with a capacity for n elements.
+    Container(CopyReducerBase &S, unsigned N) : Elems(S.Arena, N) {}
+
+    // Push a new element onto the container.
+    void push_back(T E) { Elems.push_back(E); }
+
+    SimpleArray<T> Elems;
+  };
+
+  CopyReducerBase(MemRegionRef A) : Arena(A) {}
+
+protected:
+  MemRegionRef Arena;
+};
+
+// Base class for visit traversals.
+class VisitReducerBase : public SimpleReducerBase {
+public:
+  // A visitor returns a bool, representing success or failure.
+  using R_SExpr = bool;
+  using R_BasicBlock = bool;
+
+  // A visitor "container" is a single bool, which accumulates success.
+  template <class T> class Container {
+  public:
+    bool Success = true;
+
+    Container(VisitReducerBase &S, unsigned N) {}
+
+    void push_back(bool E) { Success = Success && E; }
+  };
+};
+
+// Implements a traversal that visits each subexpression, and returns either
+// true or false.
+template <class Self>
+class VisitReducer : public Traversal<Self, VisitReducerBase>,
+                     public VisitReducerBase {
+public:
+  VisitReducer() = default;
+
+public:
+  R_SExpr reduceNull() { return true; }
+  R_SExpr reduceUndefined(Undefined &Orig) { return true; }
+  R_SExpr reduceWildcard(Wildcard &Orig) { return true; }
+
+  R_SExpr reduceLiteral(Literal &Orig) { return true; }
+  template<class T>
+  R_SExpr reduceLiteralT(LiteralT<T> &Orig) { return true; }
+  R_SExpr reduceLiteralPtr(Literal &Orig) { return true; }
+
+  R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) {
+    return Nvd && E0;
+  }
+
+  R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) {
+    return Nvd && E0;
+  }
+
+  R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) {
+    return E0 && E1;
+  }
+
+  R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) {
+    return E0 && E1;
+  }
+
+  R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) {
+    return E0 && E1;
+  }
+
+  R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) {
+    return E0 && E1;
+  }
+
+  R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; }
+  R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; }
+  R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; }
+  R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; }
+  R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; }
+
+  R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1) {
+    return E0 && E1;
+  }
+
+  R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1) {
+    return E0 && E1;
+  }
+
+  R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; }
+
+  R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) {
+    return E0 && E1;
+  }
+
+  R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; }
+
+  R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) {
+    return Bbs.Success;
+  }
+
+  R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<R_SExpr> &As,
+                                Container<R_SExpr> &Is, R_SExpr T) {
+    return (As.Success && Is.Success && T);
+  }
+
+  R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) {
+    return As.Success;
+  }
+
+  R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) {
+    return true;
+  }
+
+  R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) {
+    return C;
+  }
+
+  R_SExpr reduceReturn(Return &O, R_SExpr E) {
+    return E;
+  }
+
+  R_SExpr reduceIdentifier(Identifier &Orig) {
+    return true;
+  }
+
+  R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) {
+    return C && T && E;
+  }
+
+  R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) {
+    return Nvd && B;
+  }
+
+  Variable *enterScope(Variable &Orig, R_SExpr E0) { return &Orig; }
+  void exitScope(const Variable &Orig) {}
+  void enterCFG(SCFG &Cfg) {}
+  void exitCFG(SCFG &Cfg) {}
+  void enterBasicBlock(BasicBlock &BB) {}
+  void exitBasicBlock(BasicBlock &BB) {}
+
+  Variable *reduceVariableRef(Variable *Ovd) { return Ovd; }
+  BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; }
+
+public:
+  bool traverse(SExpr *E, TraversalKind K = TRV_Normal) {
+    Success = Success && this->traverseByCase(E);
+    return Success;
+  }
+
+  static bool visit(SExpr *E) {
+    Self Visitor;
+    return Visitor.traverse(E, TRV_Normal);
+  }
+
+private:
+  bool Success;
+};
+
+// Basic class for comparison operations over expressions.
+template <typename Self>
+class Comparator {
+protected:
+  Self *self() { return reinterpret_cast<Self *>(this); }
+
+public:
+  bool compareByCase(const SExpr *E1, const SExpr* E2) {
+    switch (E1->opcode()) {
+#define TIL_OPCODE_DEF(X)                                                     \
+    case COP_##X:                                                             \
+      return cast<X>(E1)->compare(cast<X>(E2), *self());
+#include "ThreadSafetyOps.def"
+#undef TIL_OPCODE_DEF
+    }
+    return false;
+  }
+};
+
+class EqualsComparator : public Comparator<EqualsComparator> {
+public:
+  // Result type for the comparison, e.g. bool for simple equality,
+  // or int for lexigraphic comparison (-1, 0, 1).  Must have one value which
+  // denotes "true".
+  using CType = bool;
+
+  CType trueResult() { return true; }
+  bool notTrue(CType ct) { return !ct; }
+
+  bool compareIntegers(unsigned i, unsigned j) { return i == j; }
+  bool compareStrings (StringRef s, StringRef r) { return s == r; }
+  bool comparePointers(const void* P, const void* Q) { return P == Q; }
+
+  bool compare(const SExpr *E1, const SExpr* E2) {
+    if (E1->opcode() != E2->opcode())
+      return false;
+    return compareByCase(E1, E2);
+  }
+
+  // TODO -- handle alpha-renaming of variables
+  void enterScope(const Variable *V1, const Variable *V2) {}
+  void leaveScope() {}
+
+  bool compareVariableRefs(const Variable *V1, const Variable *V2) {
+    return V1 == V2;
+  }
+
+  static bool compareExprs(const SExpr *E1, const SExpr* E2) {
+    EqualsComparator Eq;
+    return Eq.compare(E1, E2);
+  }
+};
+
+class MatchComparator : public Comparator<MatchComparator> {
+public:
+  // Result type for the comparison, e.g. bool for simple equality,
+  // or int for lexigraphic comparison (-1, 0, 1).  Must have one value which
+  // denotes "true".
+  using CType = bool;
+
+  CType trueResult() { return true; }
+  bool notTrue(CType ct) { return !ct; }
+
+  bool compareIntegers(unsigned i, unsigned j) { return i == j; }
+  bool compareStrings (StringRef s, StringRef r) { return s == r; }
+  bool comparePointers(const void *P, const void *Q) { return P == Q; }
+
+  bool compare(const SExpr *E1, const SExpr *E2) {
+    // Wildcards match anything.
+    if (E1->opcode() == COP_Wildcard || E2->opcode() == COP_Wildcard)
+      return true;
+    // otherwise normal equality.
+    if (E1->opcode() != E2->opcode())
+      return false;
+    return compareByCase(E1, E2);
+  }
+
+  // TODO -- handle alpha-renaming of variables
+  void enterScope(const Variable* V1, const Variable* V2) {}
+  void leaveScope() {}
+
+  bool compareVariableRefs(const Variable* V1, const Variable* V2) {
+    return V1 == V2;
+  }
+
+  static bool compareExprs(const SExpr *E1, const SExpr* E2) {
+    MatchComparator Matcher;
+    return Matcher.compare(E1, E2);
+  }
+};
+
+// inline std::ostream& operator<<(std::ostream& SS, StringRef R) {
+//   return SS.write(R.data(), R.size());
+// }
+
+// Pretty printer for TIL expressions
+template <typename Self, typename StreamType>
+class PrettyPrinter {
+private:
+  // Print out additional information.
+  bool Verbose;
+
+  // Omit redundant decls.
+  bool Cleanup;
+
+  // Print exprs in C-like syntax.
+  bool CStyle;
+
+public:
+  PrettyPrinter(bool V = false, bool C = true, bool CS = true)
+      : Verbose(V), Cleanup(C), CStyle(CS) {}
+
+  static void print(const SExpr *E, StreamType &SS) {
+    Self printer;
+    printer.printSExpr(E, SS, Prec_MAX);
+  }
+
+protected:
+  Self *self() { return reinterpret_cast<Self *>(this); }
+
+  void newline(StreamType &SS) {
+    SS << "\n";
+  }
+
+  // TODO: further distinguish between binary operations.
+  static const unsigned Prec_Atom = 0;
+  static const unsigned Prec_Postfix = 1;
+  static const unsigned Prec_Unary = 2;
+  static const unsigned Prec_Binary = 3;
+  static const unsigned Prec_Other = 4;
+  static const unsigned Prec_Decl = 5;
+  static const unsigned Prec_MAX = 6;
+
+  // Return the precedence of a given node, for use in pretty printing.
+  unsigned precedence(const SExpr *E) {
+    switch (E->opcode()) {
+      case COP_Future:     return Prec_Atom;
+      case COP_Undefined:  return Prec_Atom;
+      case COP_Wildcard:   return Prec_Atom;
+
+      case COP_Literal:    return Prec_Atom;
+      case COP_LiteralPtr: return Prec_Atom;
+      case COP_Variable:   return Prec_Atom;
+      case COP_Function:   return Prec_Decl;
+      case COP_SFunction:  return Prec_Decl;
+      case COP_Code:       return Prec_Decl;
+      case COP_Field:      return Prec_Decl;
+
+      case COP_Apply:      return Prec_Postfix;
+      case COP_SApply:     return Prec_Postfix;
+      case COP_Project:    return Prec_Postfix;
+
+      case COP_Call:       return Prec_Postfix;
+      case COP_Alloc:      return Prec_Other;
+      case COP_Load:       return Prec_Postfix;
+      case COP_Store:      return Prec_Other;
+      case COP_ArrayIndex: return Prec_Postfix;
+      case COP_ArrayAdd:   return Prec_Postfix;
+
+      case COP_UnaryOp:    return Prec_Unary;
+      case COP_BinaryOp:   return Prec_Binary;
+      case COP_Cast:       return Prec_Atom;
+
+      case COP_SCFG:       return Prec_Decl;
+      case COP_BasicBlock: return Prec_MAX;
+      case COP_Phi:        return Prec_Atom;
+      case COP_Goto:       return Prec_Atom;
+      case COP_Branch:     return Prec_Atom;
+      case COP_Return:     return Prec_Other;
+
+      case COP_Identifier: return Prec_Atom;
+      case COP_IfThenElse: return Prec_Other;
+      case COP_Let:        return Prec_Decl;
+    }
+    return Prec_MAX;
+  }
+
+  void printBlockLabel(StreamType & SS, const BasicBlock *BB, int index) {
+    if (!BB) {
+      SS << "BB_null";
+      return;
+    }
+    SS << "BB_";
+    SS << BB->blockID();
+    if (index >= 0) {
+      SS << ":";
+      SS << index;
+    }
+  }
+
+  void printSExpr(const SExpr *E, StreamType &SS, unsigned P, bool Sub=true) {
+    if (!E) {
+      self()->printNull(SS);
+      return;
+    }
+    if (Sub && E->block() && E->opcode() != COP_Variable) {
+      SS << "_x" << E->id();
+      return;
+    }
+    if (self()->precedence(E) > P) {
+      // Wrap expr in () if necessary.
+      SS << "(";
+      self()->printSExpr(E, SS, Prec_MAX);
+      SS << ")";
+      return;
+    }
+
+    switch (E->opcode()) {
+#define TIL_OPCODE_DEF(X)                                                  \
+    case COP_##X:                                                          \
+      self()->print##X(cast<X>(E), SS);                                    \
+      return;
+#include "ThreadSafetyOps.def"
+#undef TIL_OPCODE_DEF
+    }
+  }
+
+  void printNull(StreamType &SS) {
+    SS << "#null";
+  }
+
+  void printFuture(const Future *E, StreamType &SS) {
+    self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom);
+  }
+
+  void printUndefined(const Undefined *E, StreamType &SS) {
+    SS << "#undefined";
+  }
+
+  void printWildcard(const Wildcard *E, StreamType &SS) {
+    SS << "*";
+  }
+
+  template<class T>
+  void printLiteralT(const LiteralT<T> *E, StreamType &SS) {
+    SS << E->value();
+  }
+
+  void printLiteralT(const LiteralT<uint8_t> *E, StreamType &SS) {
+    SS << "'" << E->value() << "'";
+  }
+
+  void printLiteral(const Literal *E, StreamType &SS) {
+    if (E->clangExpr()) {
+      SS << getSourceLiteralString(E->clangExpr());
+      return;
+    }
+    else {
+      ValueType VT = E->valueType();
+      switch (VT.Base) {
+      case ValueType::BT_Void:
+        SS << "void";
+        return;
+      case ValueType::BT_Bool:
+        if (E->as<bool>().value())
+          SS << "true";
+        else
+          SS << "false";
+        return;
+      case ValueType::BT_Int:
+        switch (VT.Size) {
+        case ValueType::ST_8:
+          if (VT.Signed)
+            printLiteralT(&E->as<int8_t>(), SS);
+          else
+            printLiteralT(&E->as<uint8_t>(), SS);
+          return;
+        case ValueType::ST_16:
+          if (VT.Signed)
+            printLiteralT(&E->as<int16_t>(), SS);
+          else
+            printLiteralT(&E->as<uint16_t>(), SS);
+          return;
+        case ValueType::ST_32:
+          if (VT.Signed)
+            printLiteralT(&E->as<int32_t>(), SS);
+          else
+            printLiteralT(&E->as<uint32_t>(), SS);
+          return;
+        case ValueType::ST_64:
+          if (VT.Signed)
+            printLiteralT(&E->as<int64_t>(), SS);
+          else
+            printLiteralT(&E->as<uint64_t>(), SS);
+          return;
+        default:
+          break;
+        }
+        break;
+      case ValueType::BT_Float:
+        switch (VT.Size) {
+        case ValueType::ST_32:
+          printLiteralT(&E->as<float>(), SS);
+          return;
+        case ValueType::ST_64:
+          printLiteralT(&E->as<double>(), SS);
+          return;
+        default:
+          break;
+        }
+        break;
+      case ValueType::BT_String:
+        SS << "\"";
+        printLiteralT(&E->as<StringRef>(), SS);
+        SS << "\"";
+        return;
+      case ValueType::BT_Pointer:
+        SS << "#ptr";
+        return;
+      case ValueType::BT_ValueRef:
+        SS << "#vref";
+        return;
+      }
+    }
+    SS << "#lit";
+  }
+
+  void printLiteralPtr(const LiteralPtr *E, StreamType &SS) {
+    if (const NamedDecl *D = E->clangDecl())
+      SS << D->getNameAsString();
+    else
+      SS << "<temporary>";
+  }
+
+  void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false) {
+    if (CStyle && V->kind() == Variable::VK_SFun)
+      SS << "this";
+    else
+      SS << V->name() << V->id();
+  }
+
+  void printFunction(const Function *E, StreamType &SS, unsigned sugared = 0) {
+    switch (sugared) {
+      default:
+        SS << "\\(";   // Lambda
+        break;
+      case 1:
+        SS << "(";     // Slot declarations
+        break;
+      case 2:
+        SS << ", ";    // Curried functions
+        break;
+    }
+    self()->printVariable(E->variableDecl(), SS, true);
+    SS << ": ";
+    self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX);
+
+    const SExpr *B = E->body();
+    if (B && B->opcode() == COP_Function)
+      self()->printFunction(cast<Function>(B), SS, 2);
+    else {
+      SS << ")";
+      self()->printSExpr(B, SS, Prec_Decl);
+    }
+  }
+
+  void printSFunction(const SFunction *E, StreamType &SS) {
+    SS << "@";
+    self()->printVariable(E->variableDecl(), SS, true);
+    SS << " ";
+    self()->printSExpr(E->body(), SS, Prec_Decl);
+  }
+
+  void printCode(const Code *E, StreamType &SS) {
+    SS << ": ";
+    self()->printSExpr(E->returnType(), SS, Prec_Decl-1);
+    SS << " -> ";
+    self()->printSExpr(E->body(), SS, Prec_Decl);
+  }
+
+  void printField(const Field *E, StreamType &SS) {
+    SS << ": ";
+    self()->printSExpr(E->range(), SS, Prec_Decl-1);
+    SS << " = ";
+    self()->printSExpr(E->body(), SS, Prec_Decl);
+  }
+
+  void printApply(const Apply *E, StreamType &SS, bool sugared = false) {
+    const SExpr *F = E->fun();
+    if (F->opcode() == COP_Apply) {
+      printApply(cast<Apply>(F), SS, true);
+      SS << ", ";
+    } else {
+      self()->printSExpr(F, SS, Prec_Postfix);
+      SS << "(";
+    }
+    self()->printSExpr(E->arg(), SS, Prec_MAX);
+    if (!sugared)
+      SS << ")$";
+  }
+
+  void printSApply(const SApply *E, StreamType &SS) {
+    self()->printSExpr(E->sfun(), SS, Prec_Postfix);
+    if (E->isDelegation()) {
+      SS << "@(";
+      self()->printSExpr(E->arg(), SS, Prec_MAX);
+      SS << ")";
+    }
+  }
+
+  void printProject(const Project *E, StreamType &SS) {
+    if (CStyle) {
+      // Omit the  this->
+      if (const auto *SAP = dyn_cast<SApply>(E->record())) {
+        if (const auto *V = dyn_cast<Variable>(SAP->sfun())) {
+          if (!SAP->isDelegation() && V->kind() == Variable::VK_SFun) {
+            SS << E->slotName();
+            return;
+          }
+        }
+      }
+      if (isa<Wildcard>(E->record())) {
+        // handle existentials
+        SS << "&";
+        SS << E->clangDecl()->getQualifiedNameAsString();
+        return;
+      }
+    }
+    self()->printSExpr(E->record(), SS, Prec_Postfix);
+    if (CStyle && E->isArrow())
+      SS << "->";
+    else
+      SS << ".";
+    SS << E->slotName();
+  }
+
+  void printCall(const Call *E, StreamType &SS) {
+    const SExpr *T = E->target();
+    if (T->opcode() == COP_Apply) {
+      self()->printApply(cast<Apply>(T), SS, true);
+      SS << ")";
+    }
+    else {
+      self()->printSExpr(T, SS, Prec_Postfix);
+      SS << "()";
+    }
+  }
+
+  void printAlloc(const Alloc *E, StreamType &SS) {
+    SS << "new ";
+    self()->printSExpr(E->dataType(), SS, Prec_Other-1);
+  }
+
+  void printLoad(const Load *E, StreamType &SS) {
+    self()->printSExpr(E->pointer(), SS, Prec_Postfix);
+    if (!CStyle)
+      SS << "^";
+  }
+
+  void printStore(const Store *E, StreamType &SS) {
+    self()->printSExpr(E->destination(), SS, Prec_Other-1);
+    SS << " := ";
+    self()->printSExpr(E->source(), SS, Prec_Other-1);
+  }
+
+  void printArrayIndex(const ArrayIndex *E, StreamType &SS) {
+    self()->printSExpr(E->array(), SS, Prec_Postfix);
+    SS << "[";
+    self()->printSExpr(E->index(), SS, Prec_MAX);
+    SS << "]";
+  }
+
+  void printArrayAdd(const ArrayAdd *E, StreamType &SS) {
+    self()->printSExpr(E->array(), SS, Prec_Postfix);
+    SS << " + ";
+    self()->printSExpr(E->index(), SS, Prec_Atom);
+  }
+
+  void printUnaryOp(const UnaryOp *E, StreamType &SS) {
+    SS << getUnaryOpcodeString(E->unaryOpcode());
+    self()->printSExpr(E->expr(), SS, Prec_Unary);
+  }
+
+  void printBinaryOp(const BinaryOp *E, StreamType &SS) {
+    self()->printSExpr(E->expr0(), SS, Prec_Binary-1);
+    SS << " " << getBinaryOpcodeString(E->binaryOpcode()) << " ";
+    self()->printSExpr(E->expr1(), SS, Prec_Binary-1);
+  }
+
+  void printCast(const Cast *E, StreamType &SS) {
+    if (!CStyle) {
+      SS << "cast[";
+      switch (E->castOpcode()) {
+      case CAST_none:
+        SS << "none";
+        break;
+      case CAST_extendNum:
+        SS << "extendNum";
+        break;
+      case CAST_truncNum:
+        SS << "truncNum";
+        break;
+      case CAST_toFloat:
+        SS << "toFloat";
+        break;
+      case CAST_toInt:
+        SS << "toInt";
+        break;
+      case CAST_objToPtr:
+        SS << "objToPtr";
+        break;
+      }
+      SS << "](";
+      self()->printSExpr(E->expr(), SS, Prec_Unary);
+      SS << ")";
+      return;
+    }
+    self()->printSExpr(E->expr(), SS, Prec_Unary);
+  }
+
+  void printSCFG(const SCFG *E, StreamType &SS) {
+    SS << "CFG {\n";
+    for (const auto *BBI : *E)
+      printBasicBlock(BBI, SS);
+    SS << "}";
+    newline(SS);
+  }
+
+  void printBBInstr(const SExpr *E, StreamType &SS) {
+    bool Sub = false;
+    if (E->opcode() == COP_Variable) {
+      const auto *V = cast<Variable>(E);
+      SS << "let " << V->name() << V->id() << " = ";
+      E = V->definition();
+      Sub = true;
+    }
+    else if (E->opcode() != COP_Store) {
+      SS << "let _x" << E->id() << " = ";
+    }
+    self()->printSExpr(E, SS, Prec_MAX, Sub);
+    SS << ";";
+    newline(SS);
+  }
+
+  void printBasicBlock(const BasicBlock *E, StreamType &SS) {
+    SS << "BB_" << E->blockID() << ":";
+    if (E->parent())
+      SS << " BB_" << E->parent()->blockID();
+    newline(SS);
+
+    for (const auto *A : E->arguments())
+      printBBInstr(A, SS);
+
+    for (const auto *I : E->instructions())
+      printBBInstr(I, SS);
+
+    const SExpr *T = E->terminator();
+    if (T) {
+      self()->printSExpr(T, SS, Prec_MAX, false);
+      SS << ";";
+      newline(SS);
+    }
+    newline(SS);
+  }
+
+  void printPhi(const Phi *E, StreamType &SS) {
+    SS << "phi(";
+    if (E->status() == Phi::PH_SingleVal)
+      self()->printSExpr(E->values()[0], SS, Prec_MAX);
+    else {
+      unsigned i = 0;
+      for (const auto *V : E->values()) {
+        if (i++ > 0)
+          SS << ", ";
+        self()->printSExpr(V, SS, Prec_MAX);
+      }
+    }
+    SS << ")";
+  }
+
+  void printGoto(const Goto *E, StreamType &SS) {
+    SS << "goto ";
+    printBlockLabel(SS, E->targetBlock(), E->index());
+  }
+
+  void printBranch(const Branch *E, StreamType &SS) {
+    SS << "branch (";
+    self()->printSExpr(E->condition(), SS, Prec_MAX);
+    SS << ") ";
+    printBlockLabel(SS, E->thenBlock(), -1);
+    SS << " ";
+    printBlockLabel(SS, E->elseBlock(), -1);
+  }
+
+  void printReturn(const Return *E, StreamType &SS) {
+    SS << "return ";
+    self()->printSExpr(E->returnValue(), SS, Prec_Other);
+  }
+
+  void printIdentifier(const Identifier *E, StreamType &SS) {
+    SS << E->name();
+  }
+
+  void printIfThenElse(const IfThenElse *E, StreamType &SS) {
+    if (CStyle) {
+      printSExpr(E->condition(), SS, Prec_Unary);
+      SS << " ? ";
+      printSExpr(E->thenExpr(), SS, Prec_Unary);
+      SS << " : ";
+      printSExpr(E->elseExpr(), SS, Prec_Unary);
+      return;
+    }
+    SS << "if (";
+    printSExpr(E->condition(), SS, Prec_MAX);
+    SS << ") then ";
+    printSExpr(E->thenExpr(), SS, Prec_Other);
+    SS << " else ";
+    printSExpr(E->elseExpr(), SS, Prec_Other);
+  }
+
+  void printLet(const Let *E, StreamType &SS) {
+    SS << "let ";
+    printVariable(E->variableDecl(), SS, true);
+    SS << " = ";
+    printSExpr(E->variableDecl()->definition(), SS, Prec_Decl-1);
+    SS << "; ";
+    printSExpr(E->body(), SS, Prec_Decl-1);
+  }
+};
+
+class StdPrinter : public PrettyPrinter<StdPrinter, std::ostream> {};
+
+} // namespace til
+} // namespace threadSafety
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyUtil.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyUtil.h
new file mode 100644
index 0000000000..a3ad8a30c0
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/ThreadSafetyUtil.h
@@ -0,0 +1,368 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- ThreadSafetyUtil.h ---------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines some basic utility classes for use by ThreadSafetyTIL.h
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Support/Allocator.h"
+#include <cassert>
+#include <cstddef>
+#include <cstring>
+#include <iterator>
+#include <ostream>
+#include <string>
+#include <vector>
+
+namespace clang {
+
+class Expr;
+
+namespace threadSafety {
+namespace til {
+
+// Simple wrapper class to abstract away from the details of memory management.
+// SExprs are allocated in pools, and deallocated all at once.
+class MemRegionRef {
+private:
+  union AlignmentType {
+    double d;
+    void *p;
+    long double dd;
+    long long ii;
+  };
+
+public:
+  MemRegionRef() = default;
+  MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
+
+  void *allocate(size_t Sz) {
+    return Allocator->Allocate(Sz, alignof(AlignmentType));
+  }
+
+  template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
+
+  template <typename T> T *allocateT(size_t NumElems) {
+    return Allocator->Allocate<T>(NumElems);
+  }
+
+private:
+  llvm::BumpPtrAllocator *Allocator = nullptr;
+};
+
+} // namespace til
+} // namespace threadSafety
+
+} // namespace clang
+
+inline void *operator new(size_t Sz,
+                          clang::threadSafety::til::MemRegionRef &R) {
+  return R.allocate(Sz);
+}
+
+namespace clang {
+namespace threadSafety {
+
+std::string getSourceLiteralString(const Expr *CE);
+
+namespace til {
+
+// A simple fixed size array class that does not manage its own memory,
+// suitable for use with bump pointer allocation.
+template <class T> class SimpleArray {
+public:
+  SimpleArray() = default;
+  SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
+      : Data(Dat), Size(Sz), Capacity(Cp) {}
+  SimpleArray(MemRegionRef A, size_t Cp)
+      : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {}
+  SimpleArray(const SimpleArray<T> &A) = delete;
+
+  SimpleArray(SimpleArray<T> &&A)
+      : Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
+    A.Data = nullptr;
+    A.Size = 0;
+    A.Capacity = 0;
+  }
+
+  SimpleArray &operator=(SimpleArray &&RHS) {
+    if (this != &RHS) {
+      Data = RHS.Data;
+      Size = RHS.Size;
+      Capacity = RHS.Capacity;
+
+      RHS.Data = nullptr;
+      RHS.Size = RHS.Capacity = 0;
+    }
+    return *this;
+  }
+
+  // Reserve space for at least Ncp items, reallocating if necessary.
+  void reserve(size_t Ncp, MemRegionRef A) {
+    if (Ncp <= Capacity)
+      return;
+    T *Odata = Data;
+    Data = A.allocateT<T>(Ncp);
+    Capacity = Ncp;
+    memcpy(Data, Odata, sizeof(T) * Size);
+  }
+
+  // Reserve space for at least N more items.
+  void reserveCheck(size_t N, MemRegionRef A) {
+    if (Capacity == 0)
+      reserve(u_max(InitialCapacity, N), A);
+    else if (Size + N < Capacity)
+      reserve(u_max(Size + N, Capacity * 2), A);
+  }
+
+  using iterator = T *;
+  using const_iterator = const T *;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+  size_t size() const { return Size; }
+  size_t capacity() const { return Capacity; }
+
+  T &operator[](unsigned i) {
+    assert(i < Size && "Array index out of bounds.");
+    return Data[i];
+  }
+
+  const T &operator[](unsigned i) const {
+    assert(i < Size && "Array index out of bounds.");
+    return Data[i];
+  }
+
+  T &back() {
+    assert(Size && "No elements in the array.");
+    return Data[Size - 1];
+  }
+
+  const T &back() const {
+    assert(Size && "No elements in the array.");
+    return Data[Size - 1];
+  }
+
+  iterator begin() { return Data; }
+  iterator end() { return Data + Size; }
+
+  const_iterator begin() const { return Data; }
+  const_iterator end() const { return Data + Size; }
+
+  const_iterator cbegin() const { return Data; }
+  const_iterator cend() const { return Data + Size; }
+
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(end());
+  }
+
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(begin());
+  }
+
+  void push_back(const T &Elem) {
+    assert(Size < Capacity);
+    Data[Size++] = Elem;
+  }
+
+  // drop last n elements from array
+  void drop(unsigned n = 0) {
+    assert(Size > n);
+    Size -= n;
+  }
+
+  void setValues(unsigned Sz, const T& C) {
+    assert(Sz <= Capacity);
+    Size = Sz;
+    for (unsigned i = 0; i < Sz; ++i) {
+      Data[i] = C;
+    }
+  }
+
+  template <class Iter> unsigned append(Iter I, Iter E) {
+    size_t Osz = Size;
+    size_t J = Osz;
+    for (; J < Capacity && I != E; ++J, ++I)
+      Data[J] = *I;
+    Size = J;
+    return J - Osz;
+  }
+
+  llvm::iterator_range<reverse_iterator> reverse() {
+    return llvm::reverse(*this);
+  }
+
+  llvm::iterator_range<const_reverse_iterator> reverse() const {
+    return llvm::reverse(*this);
+  }
+
+private:
+  // std::max is annoying here, because it requires a reference,
+  // thus forcing InitialCapacity to be initialized outside the .h file.
+  size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; }
+
+  static const size_t InitialCapacity = 4;
+
+  T *Data = nullptr;
+  size_t Size = 0;
+  size_t Capacity = 0;
+};
+
+}  // namespace til
+
+// A copy on write vector.
+// The vector can be in one of three states:
+// * invalid -- no operations are permitted.
+// * read-only -- read operations are permitted.
+// * writable -- read and write operations are permitted.
+// The init(), destroy(), and makeWritable() methods will change state.
+template<typename T>
+class CopyOnWriteVector {
+  class VectorData {
+  public:
+    unsigned NumRefs = 1;
+    std::vector<T> Vect;
+
+    VectorData() = default;
+    VectorData(const VectorData &VD) : Vect(VD.Vect) {}
+  };
+
+public:
+  CopyOnWriteVector() = default;
+  CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
+
+  CopyOnWriteVector &operator=(CopyOnWriteVector &&V) {
+    destroy();
+    Data = V.Data;
+    V.Data = nullptr;
+    return *this;
+  }
+
+  // No copy constructor or copy assignment.  Use clone() with move assignment.
+  CopyOnWriteVector(const CopyOnWriteVector &) = delete;
+  CopyOnWriteVector &operator=(const CopyOnWriteVector &) = delete;
+
+  ~CopyOnWriteVector() { destroy(); }
+
+  // Returns true if this holds a valid vector.
+  bool valid() const  { return Data; }
+
+  // Returns true if this vector is writable.
+  bool writable() const { return Data && Data->NumRefs == 1; }
+
+  // If this vector is not valid, initialize it to a valid vector.
+  void init() {
+    if (!Data) {
+      Data = new VectorData();
+    }
+  }
+
+  // Destroy this vector; thus making it invalid.
+  void destroy() {
+    if (!Data)
+      return;
+    if (Data->NumRefs <= 1)
+      delete Data;
+    else
+      --Data->NumRefs;
+    Data = nullptr;
+  }
+
+  // Make this vector writable, creating a copy if needed.
+  void makeWritable() {
+    if (!Data) {
+      Data = new VectorData();
+      return;
+    }
+    if (Data->NumRefs == 1)
+      return;   // already writeable.
+    --Data->NumRefs;
+    Data = new VectorData(*Data);
+  }
+
+  // Create a lazy copy of this vector.
+  CopyOnWriteVector clone() { return CopyOnWriteVector(Data); }
+
+  using const_iterator = typename std::vector<T>::const_iterator;
+
+  const std::vector<T> &elements() const { return Data->Vect; }
+
+  const_iterator begin() const { return elements().cbegin(); }
+  const_iterator end() const { return elements().cend(); }
+
+  const T& operator[](unsigned i) const { return elements()[i]; }
+
+  unsigned size() const { return Data ? elements().size() : 0; }
+
+  // Return true if V and this vector refer to the same data.
+  bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
+
+  // Clear vector.  The vector must be writable.
+  void clear() {
+    assert(writable() && "Vector is not writable!");
+    Data->Vect.clear();
+  }
+
+  // Push a new element onto the end.  The vector must be writable.
+  void push_back(const T &Elem) {
+    assert(writable() && "Vector is not writable!");
+    Data->Vect.push_back(Elem);
+  }
+
+  // Gets a mutable reference to the element at index(i).
+  // The vector must be writable.
+  T& elem(unsigned i) {
+    assert(writable() && "Vector is not writable!");
+    return Data->Vect[i];
+  }
+
+  // Drops elements from the back until the vector has size i.
+  void downsize(unsigned i) {
+    assert(writable() && "Vector is not writable!");
+    Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end());
+  }
+
+private:
+  CopyOnWriteVector(VectorData *D) : Data(D) {
+    if (!Data)
+      return;
+    ++Data->NumRefs;
+  }
+
+  VectorData *Data = nullptr;
+};
+
+inline std::ostream& operator<<(std::ostream& ss, const StringRef str) {
+  return ss.write(str.data(), str.size());
+}
+
+} // namespace threadSafety
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/UninitializedValues.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/UninitializedValues.h
new file mode 100644
index 0000000000..9f383069a2
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/UninitializedValues.h
@@ -0,0 +1,146 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//=- UninitializedValues.h - Finding uses of uninitialized values -*- C++ -*-=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines APIs for invoking and reported uninitialized values
+// warnings.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H
+
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace clang {
+
+class AnalysisDeclContext;
+class CFG;
+class DeclContext;
+class Expr;
+class Stmt;
+class VarDecl;
+
+/// A use of a variable, which might be uninitialized.
+class UninitUse {
+public:
+  struct Branch {
+    const Stmt *Terminator;
+    unsigned Output;
+  };
+
+private:
+  /// The expression which uses this variable.
+  const Expr *User;
+
+  /// Is this use uninitialized whenever the function is called?
+  bool UninitAfterCall = false;
+
+  /// Is this use uninitialized whenever the variable declaration is reached?
+  bool UninitAfterDecl = false;
+
+  /// Does this use always see an uninitialized value?
+  bool AlwaysUninit;
+
+  /// This use is always uninitialized if it occurs after any of these branches
+  /// is taken.
+  SmallVector<Branch, 2> UninitBranches;
+
+public:
+  UninitUse(const Expr *User, bool AlwaysUninit)
+      : User(User), AlwaysUninit(AlwaysUninit) {}
+
+  void addUninitBranch(Branch B) {
+    UninitBranches.push_back(B);
+  }
+
+  void setUninitAfterCall() { UninitAfterCall = true; }
+  void setUninitAfterDecl() { UninitAfterDecl = true; }
+
+  /// Get the expression containing the uninitialized use.
+  const Expr *getUser() const { return User; }
+
+  /// The kind of uninitialized use.
+  enum Kind {
+    /// The use might be uninitialized.
+    Maybe,
+
+    /// The use is uninitialized whenever a certain branch is taken.
+    Sometimes,
+
+    /// The use is uninitialized the first time it is reached after we reach
+    /// the variable's declaration.
+    AfterDecl,
+
+    /// The use is uninitialized the first time it is reached after the function
+    /// is called.
+    AfterCall,
+
+    /// The use is always uninitialized.
+    Always
+  };
+
+  /// Get the kind of uninitialized use.
+  Kind getKind() const {
+    return AlwaysUninit ? Always :
+           UninitAfterCall ? AfterCall :
+           UninitAfterDecl ? AfterDecl :
+           !branch_empty() ? Sometimes : Maybe;
+  }
+
+  using branch_iterator = SmallVectorImpl<Branch>::const_iterator;
+
+  /// Branches which inevitably result in the variable being used uninitialized.
+  branch_iterator branch_begin() const { return UninitBranches.begin(); }
+  branch_iterator branch_end() const { return UninitBranches.end(); }
+  bool branch_empty() const { return UninitBranches.empty(); }
+};
+
+class UninitVariablesHandler {
+public:
+  UninitVariablesHandler() = default;
+  virtual ~UninitVariablesHandler();
+
+  /// Called when the uninitialized variable is used at the given expression.
+  virtual void handleUseOfUninitVariable(const VarDecl *vd,
+                                         const UninitUse &use) {}
+
+  /// Called when the uninitialized variable is used as const refernce argument.
+  virtual void handleConstRefUseOfUninitVariable(const VarDecl *vd,
+                                                 const UninitUse &use) {}
+
+  /// Called when the uninitialized variable analysis detects the
+  /// idiom 'int x = x'.  All other uses of 'x' within the initializer
+  /// are handled by handleUseOfUninitVariable.
+  virtual void handleSelfInit(const VarDecl *vd) {}
+};
+
+struct UninitVariablesAnalysisStats {
+  unsigned NumVariablesAnalyzed;
+  unsigned NumBlockVisits;
+};
+
+void runUninitializedVariablesAnalysis(const DeclContext &dc, const CFG &cfg,
+                                       AnalysisDeclContext &ac,
+                                       UninitVariablesHandler &handler,
+                                       UninitVariablesAnalysisStats &stats);
+
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/UnsafeBufferUsage.h b/contrib/libs/clang16/include/clang/Analysis/Analyses/UnsafeBufferUsage.h
new file mode 100644
index 0000000000..5cf3a0946b
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/UnsafeBufferUsage.h
@@ -0,0 +1,59 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- UnsafeBufferUsage.h - Replace pointers with modern C++ ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines an analysis that aids replacing buffer accesses through
+//  raw pointers with safer C++ abstractions such as containers and views/spans.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Stmt.h"
+
+namespace clang {
+
+/// The interface that lets the caller handle unsafe buffer usage analysis
+/// results by overriding this class's handle... methods.
+class UnsafeBufferUsageHandler {
+public:
+  UnsafeBufferUsageHandler() = default;
+  virtual ~UnsafeBufferUsageHandler() = default;
+
+  /// This analyses produces large fixits that are organized into lists
+  /// of primitive fixits (individual insertions/removals/replacements).
+  using FixItList = llvm::SmallVectorImpl<FixItHint>;
+
+  /// Invoked when an unsafe operation over raw pointers is found.
+  virtual void handleUnsafeOperation(const Stmt *Operation,
+                                     bool IsRelatedToDecl) = 0;
+
+  /// Invoked when a fix is suggested against a variable.
+  virtual void handleFixableVariable(const VarDecl *Variable,
+                                     FixItList &&List) = 0;
+};
+
+// This function invokes the analysis and allows the caller to react to it
+// through the handler class.
+void checkUnsafeBufferUsage(const Decl *D, UnsafeBufferUsageHandler &Handler);
+
+} // end namespace clang
+
+#endif /* LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H */
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif
diff --git a/contrib/libs/clang16/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def b/contrib/libs/clang16/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def
new file mode 100644
index 0000000000..d10d95e5b1
--- /dev/null
+++ b/contrib/libs/clang16/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def
@@ -0,0 +1,35 @@
+//=- UnsafeBufferUsageGadgets.def - List of ways to use a buffer --*- C++ -*-=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+/// A gadget is an individual operation in the code that may be of interest to
+/// the UnsafeBufferUsage analysis.
+#ifndef GADGET
+#define GADGET(name)
+#endif
+
+/// Unsafe gadgets correspond to unsafe code patterns that warrant
+/// an immediate warning.
+#ifndef WARNING_GADGET
+#define WARNING_GADGET(name) GADGET(name)
+#endif
+
+/// Safe gadgets correspond to code patterns that aren't unsafe but need to be
+/// properly recognized in order to emit correct warnings and fixes over unsafe
+/// gadgets.
+#ifndef FIXABLE_GADGET
+#define FIXABLE_GADGET(name) GADGET(name)
+#endif
+
+WARNING_GADGET(Increment)
+WARNING_GADGET(Decrement)
+WARNING_GADGET(ArraySubscript)
+WARNING_GADGET(PointerArithmetic)
+
+#undef FIXABLE_GADGET
+#undef WARNING_GADGET
+#undef GADGET