Index: clang/include/clang/Analysis/Analyses/ReachingDefinitions.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/Analyses/ReachingDefinitions.h @@ -0,0 +1,247 @@ +//===--- ReachingDefinitions.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 +// +//===----------------------------------------------------------------------===// +// +// Calculates reaching definitions for a CFG. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLE_DEFINITIONS_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLE_DEFINITIONS_H + +#include "clang/AST/Decl.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/Analysis/AnalysisDeclContext.h" +#include "clang/Analysis/CFG.h" +#include "llvm/ADT/SmallVector.h" +#include + +namespace clang { + +//===----------------------------------------------------------------------===// +// Since reaching definitions was implemented for instructions, it isn't well +// thought out what a definition of a variable is in C/C++, nor what we really +// mean under the term variable. +//===----------------------------------------------------------------------===// + +namespace ReachingDefinitionsDetail { + +//===----------------------------------------------------------------------===// +// What a 'variable' is: +// We define a variable as a VarDecl. +// TODO: How about records? Add support for fields. +// TODO: How do we describe the implicit this parameter for methods? +//===----------------------------------------------------------------------===// + +struct Variable { + const VarDecl *Var; + + Variable(const VarDecl *Var) : Var(Var) {} +}; + +struct VariableLess { + // TODO: const ref? but what if we change this to immutablelist? + bool operator()(Variable Lhs, Variable Rhs) { + return Lhs.Var < Rhs.Var; + } +}; + +//===----------------------------------------------------------------------===// +// What a 'definition of a variable' is: +// Whatever statement that writes a 'variable', or may write a 'variable'. +// TODO: What about global variables on function calls? We should introduce +// invalidations as well. +//===----------------------------------------------------------------------===// + +class Definition : public Variable { +public: + enum DefinitionKind { Write }; + + CFGBlock::ConstCFGElementRef E; + DefinitionKind Kind; + +public: + + Definition(const VarDecl *Var, CFGBlock::ConstCFGElementRef E, + DefinitionKind Kind) + : Variable(Var), E(E), Kind(Kind) {} + + const CFGBlock *getCFGBlock() const { return E.getParent(); } + + // (varname [blockid, elementid]) (reason) + void dump() const; +}; + +struct VarAndCFGElementLess { + bool operator()(Definition Lhs, Definition Rhs) const { + return std::tie(Lhs.Var, Lhs.E) < + std::tie(Rhs.Var, Rhs.E); + } +}; + +/// A set of definitions sorted only by the variable, so that each basic block +/// may only emit a single definition for any single variable. +// TODO: We need to track more then a single definition to a variable for a +// block's GEN set. Say, the static analyzer manages to prove that a potential +// invalidation definition (like a function call) didn't write the variable, we +// need to retrieve the definitions up to that point in the block. +// TODO: This is ridiculously espensive, change to ImmutableSet. +using GenSet = std::set; + +/// A set of definitions sorted by the variable and the location of the +/// definition. For KILL, IN and OUT sets this is correct, because a CFGBlock +/// may kill several definitions of the same variables from different locations. +using DefinitionSet = std::set; + +//===----------------------------------------------------------------------===// +// Determining whether a statement modifies a variable is a challanging, and +// requires using expensive-to-create matchers, and an easily extensible +// interface, hence the use of a builder class outside of the main calculator. +//===----------------------------------------------------------------------===// + +class GenSetBuilder; + +class GenSetMatcherCallback : public ast_matchers::MatchFinder::MatchCallback { +protected: + GenSetBuilder &GSBuilder; + + GenSetMatcherCallback(GenSetBuilder &GSBuilder) : GSBuilder(GSBuilder) {} +}; + +/// Responsible for building the GEN sets for each basic block. +/// +/// Since pointer escapes or function calls in general require us to generate +/// definitions that are invalidations, we need to gather all variables relevant +/// for this analysis, like parameters, locals and globals. We refer to this +/// stage as 'variable finding': +/// * Collect all non-local, visible variables +/// * Collect all local variables within the function that is used +/// +/// The actual building of GEN sets has two stages: +/// 1. For each CFGStmt in the CFGBlock, look for a statement that may be a +/// definition of an expression. ('definition finding') +/// 2. Search expressions for variables recursively. ('expression finding') +class GenSetBuilder { + using DefinitionKind = Definition::DefinitionKind; + + // Fields that shouldn't change after the construction of the builder object. + + llvm::SmallVector, 8> Callbacks; + + ast_matchers::MatchFinder VariableFinder; + ast_matchers::MatchFinder DefinitionFinder; + ast_matchers::MatchFinder ExpressionFinder; + + const Decl *D; + ASTContext *Context = nullptr; + + // TODO: This does not contain non-local visible variables. + std::set AllVariables; + + // Fields that are changed at and during each GEN set construction. + + GenSet *CurrentGenSet; + Optional CurrentCFGElem; + + // This field is used for definition finder matchers to communicate with + // expression finder matchers what kind of a definition we need to note. This + // isn't too pretty, but the interaction in between matcher callbacks are + // inherently awkward. + DefinitionKind CurrentKind = Definition::Write; + +private: + // TODO: Make this public and allow custom matchers to be added? + template + void addMatcher() { + Callbacks.emplace_back(std::make_unique(*this)); + (this->*Finder) + .addMatcher(GenSetMatcherCallbackTy::getMatcher(), + Callbacks.back().get()); + } + +public: + GenSetBuilder(const Decl *D); + + //===--------------------------------------------------------------------===// + // Methods for retrieving a GEN set. + //===--------------------------------------------------------------------===// + + void getGenSetForCFGBlock(const CFGBlock *B, GenSet &Gen); + + //===--------------------------------------------------------------------===// + // Utility methods for building a GEN set. These are public because the + // callback objects will need to call them. + //===--------------------------------------------------------------------===// + + /// When we find a definition to an *expression*, we need to see if that + /// expression is a variable, or some other expression that needs further + /// processing, like in this case: + /// (a, b) = 10; + void handleExpr(const Expr *E, DefinitionKind Kind); + + /// Insert a new defintion of a variable into the current GEN set. + void insertToGenSet(const VarDecl *Var, DefinitionKind Kind); + + void insertToGenSet(const VarDecl *Var) { insertToGenSet(Var, CurrentKind); } + + /// Called during the variable finding stage. + void addVariable(const VarDecl *Var); +}; + +} // end of namespace ReachingDefinitionsDetail + +/// Calculates reaching definitions for each basic block. This calculation +/// doesn't try to argue about aliasing, meaning that some definitions are +/// definite write (we know that the variable it written), and some are a result +/// of invalidation, like passing a variable as a non-const reference to a +/// function. +class ReachingDefinitionsCalculator : public ManagedAnalysis { + using GenSetBuilder = ReachingDefinitionsDetail::GenSetBuilder; + +public: + using GenSet = ReachingDefinitionsDetail::GenSet; + using DefinitionKind = ReachingDefinitionsDetail::Definition::DefinitionKind; + using DefinitionSet = ReachingDefinitionsDetail::DefinitionSet; + + void calculate(); + + void dumpKillSet() const; + void dumpGenSet() const; + void dumpReachingDefinitions() const; + + static ReachingDefinitionsCalculator *create(AnalysisDeclContext &Ctx) { + return new ReachingDefinitionsCalculator(Ctx.getDecl(), Ctx.getCFG()); + } + + static const void *getTag() { + static int x; + return &x; + } + +private: + ReachingDefinitionsCalculator(const Decl *D, const CFG *cfg); + + void init(); + + const CFG *cfg; + GenSetBuilder GSBuilder; + + // TODO: Make the GEN set public to allow clients to remove definitions, or + // possibly mark an invalidation as write. + // TODO: Should we change to ImmutableMap? Does this matter that much? + std::map Gen; + std::map Kill; + +public: + std::map In; + std::map Out; +}; + +} // end of namespace clang + +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLE_DEFINITIONS_H Index: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ clang/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -1415,8 +1415,19 @@ Dependencies<[DebugContainerModeling, IteratorModeling]>, Documentation; -} // end "debug" +def GenSetDumper : Checker<"DumpGenSets">, + HelpText<"Dump the GEN sets for each block in a function">, + Documentation; + +def KillSetDumper : Checker<"DumpKillSets">, + HelpText<"Dump the KILL sets for each block in a function">, + Documentation; +def ReachingDefinitionsDumper : Checker<"DumpReachingDefinitions">, + HelpText<"Dump the reaching definitions for each block in a function">, + Documentation; + +} // end "debug" //===----------------------------------------------------------------------===// // Clone Detection Index: clang/lib/Analysis/CMakeLists.txt =================================================================== --- clang/lib/Analysis/CMakeLists.txt +++ clang/lib/Analysis/CMakeLists.txt @@ -22,6 +22,7 @@ PostOrderCFGView.cpp ProgramPoint.cpp ReachableCode.cpp + ReachingDefinitions.cpp RetainSummaryManager.cpp ThreadSafety.cpp ThreadSafetyCommon.cpp Index: clang/lib/Analysis/ReachingDefinitions.cpp =================================================================== --- /dev/null +++ clang/lib/Analysis/ReachingDefinitions.cpp @@ -0,0 +1,319 @@ +//===--- ReachableDefinitions.cpp -------------------------------*- 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 +// +//===----------------------------------------------------------------------===// +// +// Calculates reachable definitions for a variable. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/ReachingDefinitions.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/DeclLookups.h" +#include "clang/AST/Expr.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/ASTMatchers/ASTMatchersInternal.h" +#include "clang/Analysis/CFG.h" +#include "clang/Basic/LLVM.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetOperations.h" +#include "llvm/Support/ErrorHandling.h" +#include + +using namespace clang; +using namespace ReachingDefinitionsDetail; +using namespace ast_matchers; + +using DefinitionKind = Definition::DefinitionKind; + +//===----------------------------------------------------------------------===// +// Utility functions. +//===----------------------------------------------------------------------===// + +static bool killsVar(const Definition &Victim, const GenSet &Set) { + for (const Definition &Perpetrator : Set) + if (Victim.Var == Perpetrator.Var) + return true; + return false; +} + +static StringRef describeDefinitionKind(DefinitionKind K) { + switch (K) { + case Definition::Write: + return "write"; + } +} + +//===----------------------------------------------------------------------===// +// Methods of Definition. +//===----------------------------------------------------------------------===// + +void Definition::dump() const { + llvm::errs() << "(" << Var->getNameAsString(); + + llvm::errs() << ", [" << getCFGBlock()->getIndexInCFG() << ", " + << E.getIndexInBlock() << "])" + << " <" << (describeDefinitionKind(Kind)) << ">"; +} + +//===----------------------------------------------------------------------===// +// Matcher callbacks for constructing GEN sets for the variable finding stage. +//===----------------------------------------------------------------------===// + +class VariableCollectorCB : public GenSetMatcherCallback { +public: + VariableCollectorCB(GenSetBuilder &GSBuilder) + : GenSetMatcherCallback(GSBuilder) {} + + static internal::Matcher getMatcher() { + return stmt(forEachDescendant(declRefExpr().bind("var"))); + } + + virtual void run(const MatchFinder::MatchResult &Result) override { + const auto *E = Result.Nodes.getNodeAs("var"); + assert(E); + if (const VarDecl *Var = dyn_cast(E->getDecl())) + GSBuilder.addVariable(Var); + } +}; + +//===----------------------------------------------------------------------===// +// Matcher callbacks for constructing GEN sets for the definition finding stage. +//===----------------------------------------------------------------------===// + +class AssignmentOperatorCB : public GenSetMatcherCallback { +public: + AssignmentOperatorCB(GenSetBuilder &GSBuilder) + : GenSetMatcherCallback(GSBuilder) {} + + static internal::Matcher getMatcher() { + return binaryOperator(isAssignmentOperator()).bind("assign"); + } + + virtual void run(const MatchFinder::MatchResult &Result) override { + const auto *BO = Result.Nodes.getNodeAs("assign"); + assert(BO); + GSBuilder.handleExpr(BO->getLHS(), DefinitionKind::Write); + } +}; + +class DeclarationCB : public GenSetMatcherCallback { +public: + DeclarationCB(GenSetBuilder &GSBuilder) : GenSetMatcherCallback(GSBuilder) {} + + static internal::Matcher getMatcher() { + return declStmt().bind("decls"); + } + + virtual void run(const MatchFinder::MatchResult &Result) override { + const auto *DS = Result.Nodes.getNodeAs("decls"); + assert(DS); + + for (const Decl *D : DS->decls()) { + const auto *Var = dyn_cast(D); + if (!Var) + continue; + + GSBuilder.insertToGenSet(Var, DefinitionKind::Write); + } + } +}; + +//===----------------------------------------------------------------------===// +// Matcher callbacks for constructing GEN sets for the expression finding stage. +//===----------------------------------------------------------------------===// + +class DeclRefExprCB : public GenSetMatcherCallback { +public: + DeclRefExprCB(GenSetBuilder &GSBuilder) : GenSetMatcherCallback(GSBuilder) {} + + static internal::Matcher getMatcher() { + return declRefExpr(to(varDecl().bind("var"))); + } + + virtual void run(const MatchFinder::MatchResult &Result) override { + const auto *Var = Result.Nodes.getNodeAs("var"); + assert(Var); + GSBuilder.insertToGenSet(Var); + } +}; + +//===----------------------------------------------------------------------===// +// Methods of GenSetBuilder. +//===----------------------------------------------------------------------===// + +GenSetBuilder::GenSetBuilder(const Decl *D) + : D(D), Context(&D->getASTContext()) { + + // TODO: Should we match the entire TU for nested static variables? + addMatcher<&GenSetBuilder::VariableFinder, VariableCollectorCB>(); + + // TODO: Elvis operator (?:). + // TODO: C++ MemberExpr? + // TODO: ParenExpr? (((a))) = 3; + addMatcher<&GenSetBuilder::ExpressionFinder, DeclRefExprCB>(); + + // TODO: Destructor calls? Should we be THAT conservative? + // TODO: Regular function calls? + // TODO: Moving an object? + // TODO: Method calls? + // TODO: Analyzing a method? + // TODO: What do you do with Objective.*? + // TODO: Exceptions? + addMatcher<&GenSetBuilder::DefinitionFinder, AssignmentOperatorCB>(); + addMatcher<&GenSetBuilder::DefinitionFinder, DeclarationCB>(); + + // Collect all used variables. + if (const auto *FD = dyn_cast(D)) { + VariableFinder.match(*FD, FD->getASTContext()); + for (const ParmVarDecl *Param : FD->parameters()) + addVariable(Param); + } + + // TODO: Collect all visible, non-local variables as well. +} + +void GenSetBuilder::getGenSetForCFGBlock(const CFGBlock *B, GenSet &Gen) { + if (B->empty()) + return; + + VariableFinder.match(*D, D->getASTContext()); + + CurrentGenSet = &Gen; + + for (CFGBlock::ConstCFGElementRef E : B->rrefs()) { + if (E->getKind() != CFGElement::Kind::Statement) + continue; + CurrentCFGElem = E; + + const Stmt *S = E->castAs().getStmt(); + assert(S); + DefinitionFinder.match(*S, D->getASTContext()); + } + + CurrentGenSet = nullptr; +} + +void GenSetBuilder::handleExpr(const Expr *E, DefinitionKind Kind) { + CurrentKind = Kind; + ExpressionFinder.match(*E, *Context); +} + +void GenSetBuilder::insertToGenSet(const VarDecl *Var, + DefinitionKind Kind) { + CurrentGenSet->emplace(Var, *CurrentCFGElem, Kind); +} + +void GenSetBuilder::addVariable(const VarDecl *Var) { + AllVariables.emplace(Var); +} + +//===----------------------------------------------------------------------===// +// Methods of ReachingDefinitionsCalculator. +//===----------------------------------------------------------------------===// + +ReachingDefinitionsCalculator::ReachingDefinitionsCalculator(const Decl *D, + const CFG *cfg) + : cfg(cfg), GSBuilder(D) { + + for (const CFGBlock *B : *cfg) + GSBuilder.getGenSetForCFGBlock(B, Gen[B]); + // TODO: We ignore parameters! We should collect them as definitions as well. + + calculate(); +} + +void ReachingDefinitionsCalculator::init() { + llvm::SmallVector AllDefinitions; + for (const std::pair G : Gen) + for (const Definition &Def : G.second) + AllDefinitions.push_back(Def); + + for (const std::pair G : Gen) + for (const Definition &Def : AllDefinitions) + if (G.first != Def.getCFGBlock() && killsVar(Def, G.second)) + Kill[G.first].insert(Def); +} + +using WorklistTy = llvm::SmallVector; + +void ReachingDefinitionsCalculator::calculate() { + init(); + + // TODO: Use ForwardDataflowWorklist. + for (const std::pair G : Gen) + Out[G.first] = {G.second.begin(), G.second.end()}; + + WorklistTy Worklist({cfg->begin(), cfg->end()}); + + while (!Worklist.empty()) { + const CFGBlock *N = Worklist.pop_back_val(); + + for (const CFGBlock *Pred : N->preds()) + llvm::set_union(In[N], Out[Pred]); + + bool HasChanged = + llvm::set_union(Out[N], llvm::set_difference(In[N], Kill[N])); + + if (llvm::set_union(Out[N], Gen[N])) + HasChanged = true; + + if (HasChanged) { + for (const CFGBlock *Succ : N->succs()) + Worklist.push_back(Succ); + } + } +} + +void ReachingDefinitionsCalculator::dumpGenSet() const { + llvm::errs() << "GEN sets: blockid (varname [blockid, elementid])\n"; + for (const std::pair D : Gen) { + size_t BlockID = llvm::find(*cfg, D.first) - cfg->begin(); + for (const Definition &Def : D.second) { + llvm::errs() << BlockID << ' '; + Def.dump(); + llvm::errs() << '\n'; + } + } +} + +void ReachingDefinitionsCalculator::dumpKillSet() const { + llvm::errs() << "KILL sets: blockid (varname [blockid, elementid])\n"; + for (const std::pair D : Kill) { + size_t BlockID = llvm::find(*cfg, D.first) - cfg->begin(); + for (const Definition &Def : D.second) { + llvm::errs() << BlockID << ' '; + Def.dump(); + llvm::errs() << '\n'; + } + } +} + +void ReachingDefinitionsCalculator::dumpReachingDefinitions() const { + llvm::errs() << "Reaching definition sets: " + "blockid IN/OUT (varname [blockid, elementid])\n"; + for (const CFGBlock *B : *cfg) { + size_t BlockID = llvm::find(*cfg, B) - cfg->begin(); + if (In.count(B)) { + for (const Definition &Def : In.find(B)->second) { + llvm::errs() << BlockID << " IN "; + Def.dump(); + llvm::errs() << '\n'; + } + } + + if (Out.count(B)) { + for (const Definition &Def : Out.find(B)->second) { + llvm::errs() << BlockID << " OUT "; + Def.dump(); + llvm::errs() << '\n'; + } + } + } +} Index: clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp +++ clang/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp @@ -10,12 +10,13 @@ // //===----------------------------------------------------------------------===// -#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" #include "clang/Analysis/Analyses/Dominators.h" #include "clang/Analysis/Analyses/LiveVariables.h" +#include "clang/Analysis/Analyses/ReachingDefinitions.h" #include "clang/Analysis/CallGraph.h" -#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" @@ -102,6 +103,72 @@ return true; } +//===----------------------------------------------------------------------===// +// GenSetDumper +//===----------------------------------------------------------------------===// + +namespace { +class GenSetDumper : public Checker { +public: + void checkASTCodeBody(const Decl *D, AnalysisManager &mgr, + BugReporter &BR) const { + if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) + AC->getAnalysis()->dumpGenSet(); + } +}; +} // namespace + +void ento::registerGenSetDumper(CheckerManager &mgr) { + mgr.registerChecker(); +} + +bool ento::shouldRegisterGenSetDumper(const LangOptions &LO) { return true; } + +//===----------------------------------------------------------------------===// +// KillSetDumper +//===----------------------------------------------------------------------===// + +namespace { +class KillSetDumper : public Checker { +public: + void checkASTCodeBody(const Decl *D, AnalysisManager &mgr, + BugReporter &BR) const { + if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) + AC->getAnalysis()->dumpKillSet(); + } +}; +} // namespace + +void ento::registerKillSetDumper(CheckerManager &mgr) { + mgr.registerChecker(); +} + +bool ento::shouldRegisterKillSetDumper(const LangOptions &LO) { return true; } + +//===----------------------------------------------------------------------===// +// ReachingDefinitionsDumper +//===----------------------------------------------------------------------===// + +namespace { +class ReachingDefinitionsDumper : public Checker { +public: + void checkASTCodeBody(const Decl *D, AnalysisManager &mgr, + BugReporter &BR) const { + if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) + AC->getAnalysis() + ->dumpReachingDefinitions(); + } +}; +} // namespace + +void ento::registerReachingDefinitionsDumper(CheckerManager &mgr) { + mgr.registerChecker(); +} + +bool ento::shouldRegisterReachingDefinitionsDumper(const LangOptions &LO) { + return true; +} + //===----------------------------------------------------------------------===// // LiveVariablesDumper //===----------------------------------------------------------------------===// Index: clang/test/Analysis/dump-definitions.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/dump-definitions.cpp @@ -0,0 +1,153 @@ +// RUN: %clang_analyze_cc1 %s \ +// RUN: -analyzer-checker=debug.DumpCFG \ +// RUN: -analyzer-checker=debug.DumpGenSets \ +// RUN: -analyzer-checker=debug.DumpKillSets \ +// RUN: -analyzer-checker=debug.DumpReachingDefinitions \ +// RUN: 2>&1 | FileCheck %s + +int getInt(); +int *getIntPtr(); +bool coin(); + +void single_vardecl_in_declstmt() { + int *ptr = getIntPtr(); +} +// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (ptr, [1, 3]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (ptr, [1, 3]) +// CHECK-NEXT: 0 OUT (ptr, [1, 3]) +// CHECK-NEXT: 1 OUT (ptr, [1, 3]) + +void multiple_vardecl_in_declstmt() { + int *ptr = getIntPtr(), i; +} +// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (ptr, [1, 3]) +// CHECK-NEXT: 1 (i, [1, 4]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (ptr, [1, 3]) +// CHECK-NEXT: 0 IN (i, [1, 4]) +// CHECK-NEXT: 0 OUT (ptr, [1, 3]) +// CHECK-NEXT: 0 OUT (i, [1, 4]) +// CHECK-NEXT: 1 OUT (ptr, [1, 3]) +// CHECK-NEXT: 1 OUT (i, [1, 4]) + +void function_and_vardecl_in_declstmt() { + int *ptr = getIntPtr(), a(); +} +// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (ptr, [1, 3]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (ptr, [1, 3]) +// CHECK-NEXT: 0 OUT (ptr, [1, 3]) +// CHECK-NEXT: 1 OUT (ptr, [1, 3]) + +void single_def_in_same_block() { + int *ptr = getIntPtr(); + + if (coin()) + ptr = 0; + + if (!ptr) + *ptr = 5; +} +// -> [B3] -> -> [B1] -> +// / \ / \ +// [B5 (ENTRY)] -> [B4] ------> [B2] ---> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 3 (ptr, [3, 3]) +// CHECK-NEXT: 4 (ptr, [4, 3]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 3 (ptr, [4, 3]) +// CHECK-NEXT: 4 (ptr, [3, 3]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (ptr, [3, 3]) +// CHECK-NEXT: 0 IN (ptr, [4, 3]) +// CHECK-NEXT: 0 OUT (ptr, [3, 3]) +// CHECK-NEXT: 0 OUT (ptr, [4, 3]) +// CHECK-NEXT: 1 IN (ptr, [3, 3]) +// CHECK-NEXT: 1 IN (ptr, [4, 3]) +// CHECK-NEXT: 1 OUT (ptr, [3, 3]) +// CHECK-NEXT: 1 OUT (ptr, [4, 3]) +// CHECK-NEXT: 2 IN (ptr, [3, 3]) +// CHECK-NEXT: 2 IN (ptr, [4, 3]) +// CHECK-NEXT: 2 OUT (ptr, [3, 3]) +// CHECK-NEXT: 2 OUT (ptr, [4, 3]) +// CHECK-NEXT: 3 IN (ptr, [4, 3]) +// CHECK-NEXT: 3 OUT (ptr, [3, 3]) +// CHECK-NEXT: 4 OUT (ptr, [4, 3]) + +void different_assignments() { + int i = getInt(); + + if (coin()) + i = 0; + + i += 3; + + if (!coin()) + i -= 2; + + i *= 9; + + if (i = 0) + ; +} +// -> [B5] -> -> [B3] -> -> [B1] -> +// / \ / \ / \ +// [B7 (ENTRY)] -> [B6] ------> [B4] -------> [B2] ---> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 2 (i, [2, 5]) +// CHECK-NEXT: 3 (i, [3, 2]) +// CHECK-NEXT: 4 (i, [4, 2]) +// CHECK-NEXT: 5 (i, [5, 2]) +// CHECK-NEXT: 6 (i, [6, 3]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 2 (i, [3, 2]) +// CHECK-NEXT: 2 (i, [4, 2]) +// CHECK-NEXT: 2 (i, [5, 2]) +// CHECK-NEXT: 2 (i, [6, 3]) +// CHECK-NEXT: 3 (i, [2, 5]) +// CHECK-NEXT: 3 (i, [4, 2]) +// CHECK-NEXT: 3 (i, [5, 2]) +// CHECK-NEXT: 3 (i, [6, 3]) +// CHECK-NEXT: 4 (i, [2, 5]) +// CHECK-NEXT: 4 (i, [3, 2]) +// CHECK-NEXT: 4 (i, [5, 2]) +// CHECK-NEXT: 4 (i, [6, 3]) +// CHECK-NEXT: 5 (i, [2, 5]) +// CHECK-NEXT: 5 (i, [3, 2]) +// CHECK-NEXT: 5 (i, [4, 2]) +// CHECK-NEXT: 5 (i, [6, 3]) +// CHECK-NEXT: 6 (i, [2, 5]) +// CHECK-NEXT: 6 (i, [3, 2]) +// CHECK-NEXT: 6 (i, [4, 2]) +// CHECK-NEXT: 6 (i, [5, 2]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (i, [2, 5]) +// CHECK-NEXT: 0 OUT (i, [2, 5]) +// CHECK-NEXT: 1 IN (i, [2, 5]) +// CHECK-NEXT: 1 OUT (i, [2, 5]) +// CHECK-NEXT: 2 IN (i, [3, 2]) +// CHECK-NEXT: 2 IN (i, [4, 2]) +// CHECK-NEXT: 2 OUT (i, [2, 5]) +// CHECK-NEXT: 3 IN (i, [4, 2]) +// CHECK-NEXT: 3 OUT (i, [3, 2]) +// CHECK-NEXT: 4 IN (i, [5, 2]) +// CHECK-NEXT: 4 IN (i, [6, 3]) +// CHECK-NEXT: 4 OUT (i, [4, 2]) +// CHECK-NEXT: 5 IN (i, [6, 3]) +// CHECK-NEXT: 5 OUT (i, [5, 2]) +// CHECK-NEXT: 6 OUT (i, [6, 3])