静态分析

LibToolin

include/clang/Tooling/Tooling.h

入口: ClangTool::run(…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int run(ToolAction *Action) {
	...

	bool ProcessingFailed = false;
	bool FileSkipped = false;

	for (const auto &SourcePath : SourcePaths) {
		std::string File(getAbsolutePath(SourcePath));

		std::vector<CompileCommand> CompileCommandsForFile = 
			Compilations.getCompileCommands(File);
		if (CompileCommandsForFile.empty()) {
			FileSkipped = true;
			continue;
		}

		for (CompileCommand &CompileCommand : CompileCommandsForFile) {
			std::vector<std::string> CommandLine = CompileCommand.CommandLine;

			ToolInvocation Invocation(std::move(CommandLine), Action, 
										Files.get(), PCHContainerOps);
			Invocation.setDiagnosticConsumer(DiagConsumer);

			// 核心, ToolInvocation::tun()
			if (!Invocation.run()) {
				...
				ProcessingFailed = true;
			}
		}
	}
	return ProcessingFailed ? 1 : (FileSkipped ? 2 : 0);
}

ToolInvocation

::run()

如果分析中没有错误出现，则返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool ToolInvocation::run() {
	std::vector<const char*> Argv;
	for (const std::string &Str : CommandLine) {
		Argv.push_back(Str.c_str());
	}
	const char *const BinaryName = Argv[0];

	unsigned MissingArgIndex, MissingArgCount;
	std::unique_ptr<llvm::opt::OptTable> Opts = driver::createDriverOptTable();
	llvm::opt::InputArgList ParseArgs = Opts->ParseArgs(
			ArrayRef<const char *>(Argv).slice(1), MissingArgIndex, MissingArgCount);

	IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
	ParseDiagnosticArgs(*DiagOpts, ParseArgs);

	TextDiagnosticPrinter DiagnosticPrinter(llvm::errs(), &*DiagOpts);
	DiagnosticEngine Diagnostics(IntrusiveRefCntPrt<DiagnosticIDs>(new DiagnosticIDs()), 
			&*DiagOpts, DiagConsumer ? DiagConsumer : &DiagnosticPrinter, false);

	...

	// 核心
	return runInvocation(BinaryName, Compilation.get(), std::move(Invocation),
						std::move(PCHContainerOpts));
}

::runInvocation()

执行用户指定的Action：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool ToolInvocation::runInvocation(
    const char *BinaryName, driver::Compilation *Compilation,
    std::shared_ptr<CompilerInvocation> Invocation,
    std::shared_ptr<PCHContainerOperations> PCHContainerOps) {
  // 显示调用的命令（参数-v）
  if (Invocation->getHeaderSearchOpts().Verbose) {
    llvm::errs() << "clang Invocation:\n";
    Compilation->getJobs().Print(llvm::errs(), "\n", true);
    llvm::errs() << "\n";
  }

  // 核心，这里的Action是Tool生成ToolInvocation的时候给它赋值的，也就是用户指定的Action
  return Action->runInvocation(std::move(Invocation), Files,
                               std::move(PCHContainerOps), DiagConsumer);
}

ToolAction

1
2
3
4
5
6
7
	ToolAction
		^
		|
FrontendActionFactory
		^
		|
其他子类：SimpleFrontendActionFactory...

::runInvocation(…)

ToolAction只有一个虚方法：

1
2
3
4
5
virtual bool
runInvocation(std::shared_ptr<CompilerInvocation> Invocation,
                FileManager *Files,
                std::shared_ptr<PCHContainerOperations> PCHContainerOps,
                DiagnosticConsumer *DiagConsumer) = 0;

FrontendActionFactory

FrontendActionFactory继承ToolAction，重写了runInvocation方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool FrontendActionFactory::runInvocation(
    std::shared_ptr<CompilerInvocation> Invocation, FileManager *Files,
    std::shared_ptr<PCHContainerOperations> PCHContainerOps,
    DiagnosticConsumer *DiagConsumer) {

  // 生成一个CompilerInstance来处理任务
  CompilerInstance Compiler(std::move(PCHContainerOps));
  Compiler.setInvocation(std::move(Invocation));
  Compiler.setFileManager(Files);

  std::unique_ptr<FrontendAction> ScopedToolAction(create());

  // 创建compiler的实际engine
  Compiler.createDiagnostics(DiagConsumer, /*ShouldOwnClient=*/false);
  if (!Compiler.hasDiagnostics())
    return false;

  // 创建SourceFManager
  Compiler.createSourceManager(*Files);

  // 核心，这个Action是FrontendAction了，而不是传入的ToolAction
  const bool Success = Compiler.ExecuteAction(*ScopedToolAction);

  Files->clearStatCaches();
  return Success;
}

提供了一个生成FrontendAction的虚函数：create()

1
virtual FrontendAction *create() = 0;

CompilerInstance

ExecuteAction(…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool CompilerInstance::ExecuteAction(FrontendAction &Act) {
	...
	for (const FrontendInputFile &FIF : getFrontendOpts().Inputs) {
		// Reset the ID tables if we are reusing the SourceManager and parsing
		// regular files.
		if (hasSourceManager() && !Act.isModelParsingAction())
			getSourceManager().clearIDTables();

		// 核心
		if (Act.BeginSourceFile(*this, FIF)) {
			Act.Execute();
			Act.EndSourceFile();
		}
	}
	...

	return !getDiagnostics().getClient()->getNumErrors();
}

setASTConsumer(…)

在ExcuteAction(Frontend &Act)方法中，Act.BeginSourceFile(*this, FIF)将设置环境信息，其中就会给*this设置ASTConsumer。
在设置的同时，CompilerInstance将ASTContext给ASTConsumer设置回去：

1
2
3
4
5
6
void CompilerInstance::setASTConsumer(std::unique_ptr<ASTConsumer> Value) {
  Consumer = std::move(Value);

  if (Context && Consumer)
    getASTConsumer().Initialize(getASTContext());
}

FrontendAction

include/clang/Frontend/FrontendAction.h
include/clang/StaticAnalyzer/FrontendActions.h

继承

1
2
3
4
5
6
7
	FrontendAction
		  ^
		  |
	ASTFrontendAction
		  ^
		  |
其他子类：AnalysisAction、ASTDumpAction、ASTViewAction...

环境设置

1
2
3
4
5
6
7
8
9
FrontendAction::BeginSourceFile(CompilerInstance &CI,
		const FrontendInputFile &RealInput) {

	...
	// 生成ASTConsumer，设置到CI中
	// 同时该ASTConsumer从CompilerInstance中获取ASTContext
    CI.setASTConsumer(CreateWrappedASTConsumer(CI, InputFile));
	...
}
1
2
3
void FrontendAction::EndSourceFile() {
	...
}

::Execute()

在FrontendAction::BeginSourceFile(...) & EndSourceFile(...)中间执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool FrontendAction::Execute() {
  CompilerInstance &CI = getCompilerInstance();

  if (CI.hasFrontendTimer())
    llvm::TimeRegion Timer(CI.getFrontendTimer());
  
  // 核心，虚函数，子类重写
  ExecuteAction();

  // If we are supposed to rebuild the global module index, do so now unless
  // there were any module-build failures.
  if (CI.shouldBuildGlobalModuleIndex() && CI.hasFileManager() &&
      CI.hasPreprocessor()) {
    StringRef Cache =
        CI.getPreprocessor().getHeaderSearchInfo().getModuleCachePath();
    if (!Cache.empty())
      GlobalModuleIndex::writeIndex(CI.getFileManager(),
                                    CI.getPCHContainerReader(), Cache);
  }

  return true;
}

::CreateWrappedASTConsumer(…)

私有函数，调用虚方法FrontendAction::CreateASTConsumer(...)来实现功能，该虚方法在子类中实现。

1
2
3
4
5
6
7
8
9
std::unique_ptr<ASTConsumer> 
FrontendAction::CreateWrappedASTConsumer(CompilerInstance &CI,
                                         StringRef InFile) {
	std::unique_ptr<ASTConsumer> Consumer = CreateASTConsumer(CI, InFile);
	if (!Consumer)
		return nullptr;

	...
}

ASTFrontendAction

::ExecuteAction()

虚函数的重写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ASTFrontendAction::ExecuteAction() {
  CompilerInstance &CI = getCompilerInstance();
  if (!CI.hasPreprocessor())
    return;

  if (hasCodeCompletionSupport() &&
      !CI.getFrontendOpts().CodeCompletionAt.FileName.empty())
    CI.createCodeCompletionConsumer();

  CodeCompleteConsumer *CompletionConsumer = nullptr;
  if (CI.hasCodeCompletionConsumer())
    CompletionConsumer = &CI.getCodeCompletionConsumer();

  if (!CI.hasSema())
    CI.createSema(getTranslationUnitKind(), CompletionConsumer);

  // 核心
  ParseAST(CI.getSema(), CI.getFrontendOpts().ShowStats,
           CI.getFrontendOpts().SkipFunctionBodies);
}

AnalysisAction

::CreateASTConsumer(…)

重写FrontendAction的虚方法：

1
2
3
4
5
6
std::unique_ptr<ASTConsumer>
AnalysisAction::CreateASTConsumer(CompilerInstance &CI, StringRef InFile) {
	// CreateAnalysisConsumer(...)是 AnalysisConsumer.h 中的静态函数，
	// 通过获取已有的全局信息，生成 AnalysisConsumer ，返回
	return CreateAnalysisConsumer(CI);
}

ParseAST(…)

include/clang/Parse/ParseAST.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void clang::ParseAST(Sema &S, bool PrintStats, bool SkipFunctionBodies) {
	...

	// Initialize the template instantiation observer chain.
	initialize(S.TemplateInstCallbacks, S);

	// 重要: 
	// S = CI.getSema(), 
	// ASTConsumer在FrontendAction::BeginSourceFile()中，
	// 通过FrontendAction::CreateWrappedASTConsumer()方法设置到CI上
	ASTConsumer *Consumer = &S.getASTConsumer();

	std::unique_ptr<Parser> ParseOP(
		new Parser(S.getPreprocessor(), S, SkipFunctionBodies));
	// 重要
	Parser &P = *ParseOP.get();
	...
	P.Initialize();

	...

	Parser::DeclGroupPtrTy ADecl;
	ExternalASTSource *External = S.getASTContext().getExternalSource();
	if (External)
		External->StartTranslationUnit(Consumer);

	for (bool AtEOF = P.ParseFirstTopLevelDecl(ADecl); !AtEOF;
		AtEOF = P.ParseTopLevelDecl(ADecl)) {
		// 核心
		if (ADecl && !Consumer->HandleTopLevelDecl(ADecl.get()))
			return;
	}
	...

	// 核心
	Consumer->HandleTranslationUnit(S.getASTContext());
	
	...
}

ASTConsumer

include/clang/AST/ASTConsumer.h
include/clang/StaticAnalyzer/Frontend/AnalysisConsumer.h

继承

1
2
3
4
5
6
7
	ASTConsumer
		^
		|
AnalysisASTConsumer
		^
		|
 AnalysisConsumer

AnalysisASTConsumer

只是在ASTConsumer的基础上，又继承了RecursiveASTVisitor<T>,方便AST遍历。

AnalysisConsumer

::HandleTopLevelDecl(…)

先将所有的顶层函数都处理一遍：

1
2
3
4
bool AnalysisConsumer::HandleTopLevelDecl(DeclGroupRef DG) {
  storeTopLevelDecls(DG);
  return true;
}

::HandleTranslationUnit(…)

再对整个TU处理一遍：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void AnalysisConsumer::HandleTranslationUnit(ASTContext &C) {

	// Don't run the actions if an error has occurred with parsing the file.
	DiagnosticsEngine &Diags = PP.getDiagnostics();
	if (Diags.hasErrorOccurred() || Diags.hasFatalErrorOccurred())
		return;

	if (TUTotalTimer) TUTotalTimer->startTimer();

	if (isBisonFile(C)) {
		reportAnalyzerProgress("Skipping bison-generated file\n");
	} 
	else if (Opts->DisableAllChecks) {

		// Don't analyze if the user explicitly asked for no checks to be performed
		// on this file.
		reportAnalyzerProgress("All checks are disabled using a supplied option\n");
	}	
	else {
		// Otherwise, just run the analysis.
		// 核心
		runAnalysisOnTranslationUnit(C);
	}

	if (TUTotalTimer) TUTotalTimer->stopTimer();

	// Count how many basic blocks we have not covered.
	NumBlocksInAnalyzedFunctions = FunctionSummaries.getTotalNumBasicBlocks();
	NumVisitedBlocksInAnalyzedFunctions =
		FunctionSummaries.getTotalNumVisitedBasicBlocks();
	if (NumBlocksInAnalyzedFunctions > 0)
		PercentReachableBlocks =
			(FunctionSummaries.getTotalNumVisitedBasicBlocks() * 100) /
				NumBlocksInAnalyzedFunctions;

    Mgr.reset();
}

::runAnalysisOnTranslationUnit(…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void AnalysisConsumer::runAnalysisOnTranslationUnit(ASTContext &C) {
	BugReporter BR(*Mgr);
	TranslationUnitDecl *TU = C.getTranslationUnitDecl();
	checkerMgr->runCheckersOnASTDecl(TU, *Mgr, BR);

	// 递归访问Decls的模式
	// 如果设置了AnalyzerOptions.IPAMode = AM_None
	// 那么就执行函数内的语法分析和路径敏感分析
	// 但是不会做CallGraph的过程间分析
	RecVisitorMode = AM_Syntax;
	if (!Mgr->shouldInlineCall())
		RecVisitorMode |= AM_Path;
	RecVisitorBR = &BR;

	const unsigned LocalTUDeclsSize = LocalTUDecls.size();
	for (unsigned i = 0 ; i < LocalTUDeclsSize ; ++i) {
		TraverseDecl(LocalTUDecls[i]); // RecursiveASTVisitor中的方法
	}

	// 如果设置了AnalyzerOptions.IPAMode = AM_None，那么将不会进行过程间分析
	if (Mgr->shouldInlineCall())
		HandleDeclsCallGraph(LocalTUDeclsSize);

	// 处理完所有Decls后，在整个TranslationUnitDecl上执行checks
	checkerMgr->runCheckersOnEndOfTranslationUnit(TU, *Mgr, BR);

	RecVisitorBR = nullptr;
}

::HandleDeclsCallGraph(…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void AnalysisConsumer::HandleDeclsCallGraph(const unsigned LocalTUDeclsSize) {
    // 构建函数调用图
    // 思想：遍历函数体，定位到Call Site，然后向外传播
    CallGraph CG;
    for (unsigned i = 0 ; i < LocalTUDeclsSize ; ++i) {
        CG.addToCallGraph(LocalTUDecls[i]);
    }

    SetOfConstDecls Visited;
    SetOfConstDecls VisitedAsTopLevel;
    llvm::ReversePostOrderTraversal<clang::CallGraph*> RPOT(&CG);
    for (llvm::ReversePostOrderTraversal<clang::CallGraph*>::rpo_iterator
                 I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
        NumFunctionTopLevel++;

        CallGraphNode *N = *I;
        Decl *D = N->getDecl();

        // Skip the abstract root node.
        if (!D)
            continue;

        // Skip the functions which have been processed already or previously
        // inlined.
        if (shouldSkipFunction(D, Visited, VisitedAsTopLevel))
            continue;

        // Analyze the function.
        SetOfConstDecls VisitedCallees;
        HandleCode(D, AM_Path, getInliningModeForFunction(D, Visited),
                   (Mgr->options.InliningMode == All ? nullptr : &VisitedCallees));

        // Add the visited callees to the global visited set.
        for (const Decl *Callee : VisitedCallees)
            // Decls from CallGraph are already canonical. But Decls coming from
            // CallExprs may be not. We should canonicalize them manually.
            Visited.insert(isa<ObjCMethodDecl>(Callee) ? Callee
                                                       : Callee->getCanonicalDecl());
        VisitedAsTopLevel.insert(D);
    }
}

::HandleCode(…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void AnalysisConsumer::HandleCode(Decl *D, AnalysisMode Mode,
                                  ExprEngine::InliningModes IMode,
                                  SetOfConstDecls *VisitedCallees) {
    if (!D->hasBody())
        return;
    Mode = getModeForDecl(D, Mode);
    if (Mode == AM_None)
        return;

    // Clear the AnalysisManager of old AnalysisDeclContexts.
    Mgr->ClearContexts();
    // Ignore autosynthesized code.
    if (Mgr->getAnalysisDeclContext(D)->isBodyAutosynthesized())
        return;

    DisplayFunction(D, Mode, IMode);
    CFG *DeclCFG = Mgr->getCFG(D);
    if (DeclCFG)
        MaxCFGSize.updateMax(DeclCFG->size());

    BugReporter BR(*Mgr);

    if (Mode & AM_Syntax)
        checkerMgr->runCheckersOnASTBody(D, *Mgr, BR);
    if ((Mode & AM_Path) && checkerMgr->hasPathSensitiveCheckers()) {
        RunPathSensitiveChecks(D, IMode, VisitedCallees);
        if (IMode != ExprEngine::Inline_Minimal)
            NumFunctionsAnalyzed++;
    }
}