Index: clang/include/clang/Analysis/Analyses/ReachingDefinitions.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/Analyses/ReachingDefinitions.h @@ -0,0 +1,101 @@ +//===--- 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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLE_DEFINITIONS_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLE_DEFINITIONS_H + +#include "clang/Analysis/AnalysisDeclContext.h" +#include "clang/Analysis/CFG.h" +#include +#include + +namespace clang { + +namespace ReachingDefinitionsDetail { + +struct Definition { + enum DefinitionKind { + Write, + Invalidation + }; + const VarDecl *Var; + CFGBlock::ConstCFGElementRef E; + DefinitionKind Kind; + + const CFGBlock *getCFGBlock() const { return E.getParent(); } + + // (varname [blockid, elementid]) + void dump() const { + llvm::errs() << "(" << Var->getNameAsString() << ", [" + << getCFGBlock()->getIndexInCFG() << ", " + << E.getIndexInBlock() << "])"; + } + + Definition(const VarDecl *Var, CFGBlock::ConstCFGElementRef E, + DefinitionKind Kind) + : Var(Var), E(E), Kind(Kind) {} +}; + +struct VarLess { + bool operator()(Definition Lhs, Definition Rhs) { + return Lhs.Var < Rhs.Var; + } +}; + +struct VarAndCFGElementLess { + bool operator()(Definition Lhs, Definition Rhs) const { + if (Lhs.Var == Rhs.Var) + return Lhs.E < Rhs.E; + return Lhs.Var < Rhs.Var; + } +}; + +using DefinitionSet = std::set; +using DefinitionKillSet = std::set; + +} // end of namespace ReachingDefinitionsDetail + +class ReachingDefinitionsCalculator : public ManagedAnalysis { + virtual void anchor(); + +public: + using DefinitionSet = ReachingDefinitionsDetail::DefinitionSet; + using DefinitionKillSet = ReachingDefinitionsDetail::DefinitionKillSet; + + ReachingDefinitionsCalculator(const Decl *D, const CFG *cfg, + ASTContext *Context) + : cfg(cfg), Context(Context), D(D) { + init(); + } + + void init(); + void calculate(); + + void dumpKillSet() const; + void dumpGenSet() const; + void dumpReachingDefinitions() const; + +private: + const CFG *cfg; + ASTContext *Context; + const Decl *D; + + std::map Gen; + std::map Kill; + + 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 @@ -1297,8 +1297,19 @@ HelpText<"Emits a warning for every statement.">, 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 @@ -21,6 +21,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,212 @@ +//===--- 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/DeclLookups.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/Analysis/CFG.h" +#include "llvm/ADT/SetOperations.h" + +using namespace clang; +using namespace ReachingDefinitionsDetail; + +void ReachingDefinitionsCalculator::anchor() {} + +using VarSet = llvm::SmallPtrSet; + +LLVM_NODISCARD +static VarSet getAllGlobalVariable(const Decl *D) { + VarSet Ret; + const DeclContext *DC = D->getDeclContext(); + while (DC) { + DC = DC->getPrimaryContext(); + for (const Decl *Res : DC->decls()) + if (const VarDecl *VD = dyn_cast(Res)) + Ret.insert(VD); + DC = DC->getParent(); + } + return Ret; +} + +LLVM_NODISCARD +static DefinitionSet +getGenSetForCFGBlock(const Decl *D, const CFGBlock *B, ASTContext *Context) { + if (B->size() == 0) { + return {}; + } + + using namespace ast_matchers; + using DefinitionKind = Definition::DefinitionKind; + + DefinitionSet Ret; + const VarSet GlobalVars = getAllGlobalVariable(D); + VarSet Vars; + + for (CFGBlock::ConstCFGElementRef E : B->rrefs()) { + if (E->getKind() != CFGElement::Kind::Statement) + continue; + + const Stmt *S = E->castAs().getStmt(); + assert(S); + + auto AssignmentM = + binaryOperator(isAssignmentOperator(), + hasLHS(declRefExpr(to(varDecl().bind("var"))))) + .bind("assign"); + + auto Assignments = + match(AssignmentM, *S, *Context); + if (!Assignments.empty()) { + for (const auto Assignment : Assignments) { + const auto *Var = Assignment.getNodeAs("var"); + assert(Var); + + if (Vars.insert(Var).second) + Ret.insert({Var, E, DefinitionKind::Write}); + } + } + + auto Declarations = match(declStmt().bind("decls"), *S, *Context); + if (!Declarations.empty()) { + assert(Declarations.size() == 1); + const auto *DS = Declarations[0].getNodeAs("decls"); + assert(DS); + + for (const Decl *D : DS->decls()) { + const auto *Var = dyn_cast(D); + if (!Var) + continue; + + if (Vars.insert(Var).second) + Ret.insert({Var, E, DefinitionKind::Write}); + } + } + + auto Calls = match(callExpr().bind("calls"), *S, *Context); + if (!Calls.empty()) { + assert(Calls.size() == 1); + const auto *Call = Calls[0].getNodeAs("calls"); + assert(Call); + + for (const VarDecl *GlobalVD : GlobalVars) + if (Vars.insert(GlobalVD).second) + Ret.insert({GlobalVD, E, DefinitionKind::Invalidation}); + } + } + + return Ret; +} + +bool killsVar(const VarDecl *VD, const DefinitionSet &Set) { + for (const Definition &Def : Set) + if (VD == Def.Var) + return true; + return false; +} + +void ReachingDefinitionsCalculator::init() { + llvm::SmallVector AllDefinitions; + + for (const CFGBlock *B : *cfg) { + for (const Definition &Def : getGenSetForCFGBlock(D, B, Context)) { + AllDefinitions.push_back(Def); + Gen[B].insert(Def); + } + } + + if (const auto *F = dyn_cast(D)) { + for (const ParmVarDecl *Param : F->parameters()) { + Definition ParamDef(Param, {&cfg->getEntry(), 0}, + Definition::DefinitionKind::Write); + AllDefinitions.push_back(ParamDef); + Gen[&cfg->getEntry()].insert(ParamDef); + } + } + + for (const std::pair &G : Gen) + for (const Definition &Def : AllDefinitions) + if (G.first != Def.getCFGBlock() && killsVar(Def.Var, G.second)) + Kill[G.first].insert(Def); +} + +using WorklistTy = llvm::SmallVector; + +void ReachingDefinitionsCalculator::calculate() { + Out = Gen; + + WorklistTy Worklist({cfg->begin(), cfg->end()}); + + while (!Worklist.empty()) { + const CFGBlock *N = Worklist.pop_back_val(); + + for (auto Pred = N->pred_begin(); Pred != N->pred_end(); ++Pred) + 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 (auto Succ = N->succ_begin(); Succ != N->succ_begin(); ++Succ) + 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 @@ -12,6 +12,7 @@ #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" #include "clang/Analysis/Analyses/Dominators.h" +#include "clang/Analysis/Analyses/ReachingDefinitions.h" #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/Analysis/CallGraph.h" #include "clang/StaticAnalyzer/Core/Checker.h" @@ -103,6 +104,82 @@ } //===----------------------------------------------------------------------===// +// GenSetDumper +//===----------------------------------------------------------------------===// + +namespace { +class GenSetDumper : public Checker { +public: + void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, + BugReporter &BR) const { + if (AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D)) { + ReachingDefinitionsCalculator R(D, AC->getCFG(), &AC->getASTContext()); + R.dumpGenSet(); + } + } +}; +} + +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)) { + ReachingDefinitionsCalculator R(D, AC->getCFG(), &AC->getASTContext()); + R.dumpKillSet(); + } + } +}; +} + +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)) { + ReachingDefinitionsCalculator R(D, AC->getCFG(), &AC->getASTContext()); + R.calculate(); + R.dumpReachingDefinitions(); + } + } +}; +} + +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,386 @@ +// 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 global_var; + +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 (global_var, [1, 2]) +// 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 (global_var, [1, 2]) +// CHECK-NEXT: 0 IN (ptr, [1, 3]) +// CHECK-NEXT: 0 OUT (global_var, [1, 2]) +// CHECK-NEXT: 0 OUT (ptr, [1, 3]) +// CHECK-NEXT: 1 OUT (global_var, [1, 2]) +// 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 (global_var, [1, 2]) +// 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 (global_var, [1, 2]) +// CHECK-NEXT: 0 IN (ptr, [1, 3]) +// CHECK-NEXT: 0 IN (i, [1, 4]) +// CHECK-NEXT: 0 OUT (global_var, [1, 2]) +// CHECK-NEXT: 0 OUT (ptr, [1, 3]) +// CHECK-NEXT: 0 OUT (i, [1, 4]) +// CHECK-NEXT: 1 OUT (global_var, [1, 2]) +// 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 (global_var, [1, 2]) +// 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 (global_var, [1, 2]) +// CHECK-NEXT: 0 IN (ptr, [1, 3]) +// CHECK-NEXT: 0 OUT (global_var, [1, 2]) +// CHECK-NEXT: 0 OUT (ptr, [1, 3]) +// CHECK-NEXT: 1 OUT (global_var, [1, 2]) +// 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 (global_var, [4, 6]) +// 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 (global_var, [4, 6]) +// CHECK-NEXT: 0 IN (ptr, [3, 3]) +// CHECK-NEXT: 0 OUT (global_var, [4, 6]) +// CHECK-NEXT: 0 OUT (ptr, [3, 3]) +// CHECK-NEXT: 1 IN (global_var, [4, 6]) +// CHECK-NEXT: 1 IN (ptr, [3, 3]) +// CHECK-NEXT: 1 OUT (global_var, [4, 6]) +// CHECK-NEXT: 1 OUT (ptr, [3, 3]) +// CHECK-NEXT: 2 IN (global_var, [4, 6]) +// CHECK-NEXT: 2 IN (ptr, [3, 3]) +// CHECK-NEXT: 2 OUT (global_var, [4, 6]) +// CHECK-NEXT: 2 OUT (ptr, [3, 3]) +// CHECK-NEXT: 3 IN (global_var, [4, 6]) +// CHECK-NEXT: 3 IN (ptr, [4, 3]) +// CHECK-NEXT: 3 OUT (global_var, [4, 6]) +// CHECK-NEXT: 3 OUT (ptr, [3, 3]) +// CHECK-NEXT: 4 OUT (global_var, [4, 6]) +// 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 (global_var, [4, 5]) +// CHECK-NEXT: 4 (i, [4, 2]) +// CHECK-NEXT: 5 (i, [5, 2]) +// CHECK-NEXT: 6 (global_var, [6, 6]) +// 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 (global_var, [6, 6]) +// 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 (global_var, [4, 5]) +// 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 (global_var, [4, 5]) +// CHECK-NEXT: 0 IN (i, [2, 5]) +// CHECK-NEXT: 0 OUT (global_var, [4, 5]) +// CHECK-NEXT: 0 OUT (i, [2, 5]) +// CHECK-NEXT: 1 IN (global_var, [4, 5]) +// CHECK-NEXT: 1 IN (i, [2, 5]) +// CHECK-NEXT: 1 OUT (global_var, [4, 5]) +// CHECK-NEXT: 1 OUT (i, [2, 5]) +// CHECK-NEXT: 2 IN (global_var, [4, 5]) +// CHECK-NEXT: 2 IN (i, [3, 2]) +// CHECK-NEXT: 2 OUT (global_var, [4, 5]) +// CHECK-NEXT: 2 OUT (i, [2, 5]) +// CHECK-NEXT: 3 IN (global_var, [4, 5]) +// CHECK-NEXT: 3 IN (i, [4, 2]) +// CHECK-NEXT: 3 OUT (global_var, [4, 5]) +// CHECK-NEXT: 3 OUT (i, [3, 2]) +// CHECK-NEXT: 4 IN (global_var, [6, 6]) +// CHECK-NEXT: 4 IN (i, [5, 2]) +// CHECK-NEXT: 4 OUT (global_var, [4, 5]) +// CHECK-NEXT: 4 OUT (i, [4, 2]) +// CHECK-NEXT: 5 IN (global_var, [6, 6]) +// CHECK-NEXT: 5 IN (i, [6, 3]) +// CHECK-NEXT: 5 OUT (global_var, [6, 6]) +// CHECK-NEXT: 5 OUT (i, [5, 2]) +// CHECK-NEXT: 6 OUT (global_var, [6, 6]) +// CHECK-NEXT: 6 OUT (i, [6, 3]) + +namespace example_1 { + +int flag; + +void foo() { + flag = coin(); +} +// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (global_var, [1, 2]) +// CHECK-NEXT: 1 (flag, [1, 5]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (global_var, [1, 2]) +// CHECK-NEXT: 0 IN (flag, [1, 5]) +// CHECK-NEXT: 0 OUT (global_var, [1, 2]) +// CHECK-NEXT: 0 OUT (flag, [1, 5]) +// CHECK-NEXT: 1 OUT (global_var, [1, 2]) +// CHECK-NEXT: 1 OUT (flag, [1, 5]) + +void f() { + int *x = nullptr; + flag = 1; + + foo(); + if (flag) + x = new int; + + foo(); + if (flag) + *x = 5; +} +// -> [B3] -> -> [B1] -> +// / \ / \ +// [B5 (ENTRY)] -> [B4] ------> [B2] ---> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 2 (global_var, [2, 2]) +// CHECK-NEXT: 2 (flag, [2, 2]) +// CHECK-NEXT: 3 (x, [3, 3]) +// CHECK-NEXT: 4 (global_var, [4, 8]) +// CHECK-NEXT: 4 (flag, [4, 8]) +// CHECK-NEXT: 4 (x, [4, 2]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 2 (global_var, [4, 8]) +// CHECK-NEXT: 2 (flag, [4, 8]) +// CHECK-NEXT: 3 (x, [4, 2]) +// CHECK-NEXT: 4 (global_var, [2, 2]) +// CHECK-NEXT: 4 (flag, [2, 2]) +// CHECK-NEXT: 4 (x, [3, 3]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (global_var, [2, 2]) +// CHECK-NEXT: 0 IN (flag, [2, 2]) +// CHECK-NEXT: 0 IN (x, [3, 3]) +// CHECK-NEXT: 0 OUT (global_var, [2, 2]) +// CHECK-NEXT: 0 OUT (flag, [2, 2]) +// CHECK-NEXT: 0 OUT (x, [3, 3]) +// CHECK-NEXT: 1 IN (global_var, [2, 2]) +// CHECK-NEXT: 1 IN (flag, [2, 2]) +// CHECK-NEXT: 1 IN (x, [3, 3]) +// CHECK-NEXT: 1 OUT (global_var, [2, 2]) +// CHECK-NEXT: 1 OUT (flag, [2, 2]) +// CHECK-NEXT: 1 OUT (x, [3, 3]) +// CHECK-NEXT: 2 IN (global_var, [4, 8]) +// CHECK-NEXT: 2 IN (flag, [4, 8]) +// CHECK-NEXT: 2 IN (x, [3, 3]) +// CHECK-NEXT: 2 OUT (global_var, [2, 2]) +// CHECK-NEXT: 2 OUT (flag, [2, 2]) +// CHECK-NEXT: 2 OUT (x, [3, 3]) +// CHECK-NEXT: 3 IN (global_var, [4, 8]) +// CHECK-NEXT: 3 IN (flag, [4, 8]) +// CHECK-NEXT: 3 IN (x, [4, 2]) +// CHECK-NEXT: 3 OUT (global_var, [4, 8]) +// CHECK-NEXT: 3 OUT (flag, [4, 8]) +// CHECK-NEXT: 3 OUT (x, [3, 3]) +// CHECK-NEXT: 4 OUT (global_var, [4, 8]) +// CHECK-NEXT: 4 OUT (flag, [4, 8]) +// CHECK-NEXT: 4 OUT (x, [4, 2]) + +} // end of namespace example_1 + +void assignment_buried_beneath_parentheses() { + int *ptr = getIntPtr(); + if (coin()) + (((((((((((((((ptr))))))) = getIntPtr())))))))); +} +// -> [B1] -> +// / \ +// [B3 (ENTRY)] -> [B2] ---> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (global_var, [1, 2]) +// CHECK-NEXT: 2 (global_var, [2, 6]) +// CHECK-NEXT: 2 (ptr, [2, 3]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (global_var, [2, 6]) +// CHECK-NEXT: 2 (global_var, [1, 2]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (global_var, [1, 2]) +// CHECK-NEXT: 0 IN (ptr, [2, 3]) +// CHECK-NEXT: 0 OUT (global_var, [1, 2]) +// CHECK-NEXT: 0 OUT (ptr, [2, 3]) +// CHECK-NEXT: 1 IN (global_var, [2, 6]) +// CHECK-NEXT: 1 IN (ptr, [2, 3]) +// CHECK-NEXT: 1 OUT (global_var, [1, 2]) +// CHECK-NEXT: 1 OUT (ptr, [2, 3]) +// CHECK-NEXT: 2 OUT (global_var, [2, 6]) +// CHECK-NEXT: 2 OUT (ptr, [2, 3]) + +void single_parameter(int i) { + int *ptr = getIntPtr(); +} +// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (global_var, [1, 2]) +// CHECK-NEXT: 1 (ptr, [1, 3]) +// CHECK-NEXT: 2 (i, [2, 0]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (global_var, [1, 2]) +// CHECK-NEXT: 0 IN (i, [2, 0]) +// CHECK-NEXT: 0 IN (ptr, [1, 3]) +// CHECK-NEXT: 0 OUT (global_var, [1, 2]) +// CHECK-NEXT: 0 OUT (i, [2, 0]) +// CHECK-NEXT: 0 OUT (ptr, [1, 3]) +// CHECK-NEXT: 1 IN (i, [2, 0]) +// CHECK-NEXT: 1 OUT (global_var, [1, 2]) +// CHECK-NEXT: 1 OUT (i, [2, 0]) +// CHECK-NEXT: 1 OUT (ptr, [1, 3]) +// CHECK-NEXT: 2 OUT (i, [2, 0]) + +void multiple_parameters(int i, int j, int k) { + int *ptr = getIntPtr(); +} +// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (global_var, [1, 2]) +// CHECK-NEXT: 1 (ptr, [1, 3]) +// CHECK-NEXT: 2 (i, [2, 0]) +// CHECK-NEXT: 2 (j, [2, 0]) +// CHECK-NEXT: 2 (k, [2, 0]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (global_var, [1, 2]) +// CHECK-NEXT: 0 IN (i, [2, 0]) +// CHECK-NEXT: 0 IN (j, [2, 0]) +// CHECK-NEXT: 0 IN (k, [2, 0]) +// CHECK-NEXT: 0 IN (ptr, [1, 3]) +// CHECK-NEXT: 0 OUT (global_var, [1, 2]) +// CHECK-NEXT: 0 OUT (i, [2, 0]) +// CHECK-NEXT: 0 OUT (j, [2, 0]) +// CHECK-NEXT: 0 OUT (k, [2, 0]) +// CHECK-NEXT: 0 OUT (ptr, [1, 3]) +// CHECK-NEXT: 1 IN (i, [2, 0]) +// CHECK-NEXT: 1 IN (j, [2, 0]) +// CHECK-NEXT: 1 IN (k, [2, 0]) +// CHECK-NEXT: 1 OUT (global_var, [1, 2]) +// CHECK-NEXT: 1 OUT (i, [2, 0]) +// CHECK-NEXT: 1 OUT (j, [2, 0]) +// CHECK-NEXT: 1 OUT (k, [2, 0]) +// CHECK-NEXT: 1 OUT (ptr, [1, 3]) +// CHECK-NEXT: 2 OUT (i, [2, 0]) +// CHECK-NEXT: 2 OUT (j, [2, 0]) +// CHECK-NEXT: 2 OUT (k, [2, 0]) + +void assignment_and_declaration_on_same_line(int i, int j) { + int k = i = j = 0; +} +// [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)] + +// CHECK: GEN sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (i, [1, 5]) +// CHECK-NEXT: 1 (j, [1, 2]) +// CHECK-NEXT: 1 (k, [1, 7]) +// CHECK-NEXT: 2 (i, [2, 0]) +// CHECK-NEXT: 2 (j, [2, 0]) +// CHECK-NEXT: KILL sets: blockid (varname [blockid, elementid]) +// CHECK-NEXT: 1 (i, [2, 0]) +// CHECK-NEXT: 1 (j, [2, 0]) +// CHECK-NEXT: 2 (i, [1, 5]) +// CHECK-NEXT: 2 (j, [1, 2]) +// CHECK-NEXT: Reaching definition sets: blockid IN/OUT (varname [blockid, elementid]) +// CHECK-NEXT: 0 IN (i, [1, 5]) +// CHECK-NEXT: 0 IN (j, [1, 2]) +// CHECK-NEXT: 0 IN (k, [1, 7]) +// CHECK-NEXT: 0 OUT (i, [1, 5]) +// CHECK-NEXT: 0 OUT (j, [1, 2]) +// CHECK-NEXT: 0 OUT (k, [1, 7]) +// CHECK-NEXT: 1 IN (i, [2, 0]) +// CHECK-NEXT: 1 IN (j, [2, 0]) +// CHECK-NEXT: 1 OUT (i, [1, 5]) +// CHECK-NEXT: 1 OUT (j, [1, 2]) +// CHECK-NEXT: 1 OUT (k, [1, 7]) +// CHECK-NEXT: 2 OUT (i, [2, 0]) +// CHECK-NEXT: 2 OUT (j, [2, 0])