Clang
I am impressed by clang, so I had a desire to learn more about its libTooling. I figured it would be valuable to learn how to exploit this toolkit and it would make me a more effective promoter.
scan-build is a static analysis utility from the clang suite. It comes with a large set of pre-defined checks for catching various errors. There is a plugin interface for scan-build that doesn't look too difficult to take advantage of. That way teams can design their own checkers to suit their needs. In fact, the llvm dev team has done just that -- created a llvm.Conventions checker for their team to verify that submissions conform to their development conventions.
I've worked on large teams that span several countries. Even with relatively well-described standards for coding, human code reviews don't always catch some classic errors that the standards are designed to catch.
The output of scan-build can be simple text at the command line or a handy HTML report. The latter is easier to navigate for large code bases or reports that follow a tortuous path to the offending code.
If you're not interested in this article, you can skip the prose and go straight to the code.
Sample Problem
For CPU-bound performance critical code, a classic source of suboptimal code is when floating-point literals end up promoting some computation to use double-precision.
Here's the difference between the code generated for x * 100. vs x * 100.f:
:::asm
float.o: file format elf64-x86-64 | double.o: file format elf64-x86-64
Disassembly of section .text: Disassembly of section .text:
0000000000000000 <transformInput>: 0000000000000000 <transformInput>:
>
float transformInput(float x) float transformInput(float x)
{ {
0: 55 push %rbp 0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp 1: 48 89 e5 mov %rsp,%rbp
4: 48 b8 64 00 00 00 00 movabs $0x64,%rax 4: 48 b8 64 00 00 00 00 movabs $0x64,%rax
b: 00 00 00 b: 00 00 00
e: f3 48 0f 2a c8 cvtsi2ss %rax,%xmm1 | e: f2 48 0f 2a c8 cvtsi2sd %rax,%xmm1
13: f3 0f 11 45 fc movss %xmm0,-0x4(%rbp) 13: f3 0f 11 45 fc movss %xmm0,-0x4(%rbp)
return x * 100.f; | return x * 100.;
18: f3 0f 10 45 fc movss -0x4(%rbp),%xmm0 | 18: f3 0f 5a 45 fc cvtss2sd -0x4(%rbp),%xmm0
1d: f3 0f 59 c1 mulss %xmm1,%xmm0 | 1d: f2 0f 59 c1 mulsd %xmm1,%xmm0
21: 5d pop %rbp | 21: f2 0f 5a c0 cvtsd2ss %xmm0,%xmm0
22: c3 retq | 25: 5d pop %rbp
Those extra cvtsx2sx instructions are required to promote the arithmetic to use double-precision. For the most part, that work is useless because we convert back to single-precision for the return value. This can cost us dearly if this code ends up in an inner loop. So that pesky literal is very pernicious.
This problem is well known, so gcc already has a warning (-Wdouble-promotion) designed to be on the lookout for this. Also, -fsingle-precision-constant exists to force the single-precision behavior.
Regardless of the existing features, this seems like a simple enough use case to get my feet wet with writing a Clang Checker.
Building the checker library
I started off with Ubuntu 14.04.1 (trusty) and clang-3.5. Ubuntu's popularity practically guarantees me that someone else has tried this before me. That said, I've also had some luck building from source on older platforms like SLES11 SP3. I'll focus on ubuntu now because the process is significantly simpler.
After encountering compilation errors with 3.5, I backed off to 3.4 and everything worked well. Start with:
sudo apt-get install llvm-3.4-dev clang-3.4 libclang-3.4-dev
I created a mostly-empty Checker that would emit a bug at almost any code I threw at it as a "Hello World." I tried to start with cmake for building the Checker but I ran into challenges there. Since this was pretty much my first experience building something myself with cmake I decided that it wasn't critical. I know GNU make, so I just shifted gears and created a Makefile. If you need features only present on newer releases, I'd recommend just building from source where you likely won't encounter any of these problems. You're also in a better position in getting support from the community than you are when you use Canonical's packages. Note that you may find subtle incompatibilities among releases.
:::make
LLVM_VER:=3.4
LLVM_CXXFLAGS:=$(shell llvm-config-$(LLVM_VER) --cxxflags)
LLVM_LDFLAGS:=$(shell llvm-config-$(LLVM_VER) --ldflags --libs )
CLANG_LIBS:= \
-Wl,--start-group \
-lclangAST \
-lclangAnalysis \
-lclangBasic \
-lclangDriver \
-lclangEdit \
-lclangFrontend \
-lclangFrontendTool \
-lclangLex \
-lclangParse \
-lclangSema \
-lclangEdit \
-lclangASTMatchers \
-lclangRewriteFrontend \
-lclangStaticAnalyzerFrontend \
-lclangStaticAnalyzerCheckers \
-lclangStaticAnalyzerCore \
-lclangSerialization \
-lclangTooling \
-Wl,--end-group \
$()
CXXFLAGS=-fno-rtti -Wall -g -std=c++11
CXXFLAGS+=$(LLVM_CXXFLAGS)
LDFLAGS+=$(LLVM_LDFLAGS) -shared
LOADLIBES+=-lstdc++
LOADLIBES+=$(CLANG_LIBS)
libfloatcheck.so: float-check.o
$(CXX) $(LDFLAGS) $^ $(LOADLIBES) $(LDLIBS) -o $@
Here's our simple checker to test the build:
:::c++
namespace {
class FloatExcessPrecisionChecker: public Checker <check::Bind,
>
{
mutable std::unique_ptr<BugType> bugType;
public:
FloatExcessPrecisionChecker()
: bugType(new BugType("Excess floating-point precision", "androm3da analyzer"))
{
}
void checkBind(SVal Loc,
SVal Val,
const Stmt *Statement,
CheckerContext &ctxt
) const;
};
}
void FloatExcessPrecisionChecker::checkBind(SVal Loc,
SVal Val,
const Stmt *Statement,
CheckerContext &ctxt
) const
{
ExplodedNode *loc = ctxt.generateSink();
BugReport *bug = new BugReport(*this->bugType, "all bugs all the time", loc);
ctxt.emitReport(bug);
}
extern "C"
const char clang_analyzerAPIVersionString[] = CLANG_ANALYZER_API_VERSION_STRING;
extern "C"
void clang_registerCheckers(CheckerRegistry ®istry) {
registry.addChecker<FloatExcessPrecisionChecker>("performance.crit.ExcessPrecision", "float ...");
}
The most interesting part so far is the checkBind() method inherited from clang::ento::Checker<>. Our Checker's flow is primarily dictated by the specialization of the Checker we're inheriting from. check::Bind hooks "binding of a value to a location." In my experience with vanilla test code, this is typically assignments. The CheckerDocumentation is an excellent basis for understanding how your Checker is integrated with the overall ecosystem.
ctxt.generateSink() tells the analyzer not to consider anything else in this path for this checker.
Taking a test drive
We can invoke our checker using scan-build or clang:
scan-build -load-plugin ~/src/floatcheck/libfloatcheck.so -enable-checker performance.crit.ExcessPrecision make -C test/ --always-make
Running this one yields the following output:
:::text
scan-build: Using '/usr/bin/clang' for static analysis
make[1]: Entering directory `/home/androm3da/src/floatcheck/test'
/usr/share/clang/scan-build/c++-analyzer -c -o test_one.o test_one.cpp
test_one.cpp:28:2: warning: all bugs all the time
int j = i + 33.f;
^~~~~
test_one.cpp:35:2: warning: all bugs all the time
int j = i + 100;
^~~~~
scan-build works similarly to some commercial static analysis tools in that it watches your build and deduces how to get the analysis in the correct context. This is necessary for C/C++ because you can't even create the AST for a translation unit without the defines, includes and other compiler arguments. It's valuable because scan-build might generate false positives or false negatives if it were used with a different context.
Designing a useful checker
checkBind was a good sanity-check, perhaps useful if we wanted to look at all assignments. But it's probably simpler to just zoom in on any floating point literals that we come across. So we'll ditch the check::Bind and add a check::PostStmt<FloatingLiteral>. This will invoke checkPostStmt(), so let's override that method to match:
:::C++
void FloatExcessPrecisionChecker::checkPostStmt(const FloatingLiteral *fl, CheckerContext &ctxt) const
{
const bool is_double = &fl->getSemantics() == &APFloat::IEEEdouble;
const bool foundbug = is_double;
if (foundbug)
{
ExplodedNode *loc = ctxt.generateSink();
BugReport *bug = new BugReport(*this->bugType,
"literal w/double precision, may impact performance", loc);
ctxt.emitReport(bug);
}
}
Let 'er rip on the test code:
:::text
scan-build: Using '/usr/bin/clang' for static analysis
make[1]: Entering directory `/home/androm3da/src/floatcheck/test'
/usr/share/clang/scan-build/c++-analyzer -c -o test_one.o test_one.cpp
test_one.cpp:12:14: warning: literal w/double precision, may impact performance
int j = i + 100.;
^~~~
Ok, so we're in business. But so far, we're not really exploiting the power of the checker. Let's see if we can find a way to let folks intentionally use a double-precision literal without setting off our checker. C++ has a pretty good mechanism of letting coders signify their intent for a type. We'll (ab)use the explicit cast to suggest that this use of higher-precision literals is by design.
:::C++
void FloatExcessPrecisionChecker::checkPostStmt(const FloatingLiteral *fl, CheckerContext &ctxt) const
{
auto parents = ctxt.getASTContext().getParents(*fl);
const bool is_intentional = !parents.empty()
&& parents[0].get<CXXStaticCastExpr>() != nullptr
&& parents[0].get<CXXStaticCastExpr>()->getTypeAsWritten().getAsString() == "double";
const bool is_double = &fl->getSemantics() == &APFloat::IEEEdouble;
const bool foundbug = !is_intentional && is_double;
if (foundbug)
{
ExplodedNode *loc = ctxt.generateSink();
BugReport *bug = new BugReport(*this->bugType,
"literal w/double precision, may impact performance", loc);
ctxt.emitReport(bug);
}
}
A FloatingLiteral is-a Stmt, we look at its parents to determine whether the immediate parent is a static_cast<>.
Here's our test case with an explicit cast:
:::C++
int some_intentional_dbl_func(int i) {
int j = i + static_cast<double>(100.);
return j - 12;
}
But it doesn't trigger our warning, just as we'd like:
scan-build: Using '/usr/bin/clang' for static analysis
make[1]: Entering directory `/home/brian/src/floatcheck/test'
/usr/share/clang/scan-build/c++-analyzer -c -o test_one.o test_one.cpp
test_one.cpp:12:14: warning: literal w/double precision, may impact performance
int j = i + 100.;
^~~~
1 warning generated.
Follow up, other notes
I was able to whip up this example by doing a great deal of wandering around clang's API documentation. It's an excellent resource. The llvm, clang projects move really fast, sometimes without regard to backwards compatibility of these interfaces. Although I didn't notice any incompatibilities between what's documented at http://clang.llvm.org/doxygen/ and the llvm-3.4 install that I used for this article.
This is still a pretty low complexity checker that you could probably get from AST analysis alone. But it's a great starting point for further work. We could expand our search to any high-precision operands or pass/return values. Also, it would be useful to further narrow our search domain to only what the user considers performance critical code. I'd like to only consider methods which are declared in classes which have a class with the name "PerfCritical" among its ancestors. That way, builders could apply this checker globally and users can opt-in to the checker only where appropriate.
In searching for ancestors, I know I should probably try to get the FunctionDecl associated with this code. But I couldn't find a way to get the associated FunctionDecl from the Stmt, ASTContext, etc values that I get at checkPostStmt or similar intercepts. Assuming that there's no way to get there from here, an alternative is to build a list of violations found via checkPostStmt and use CheckASTDecl to find FunctionDecls with a body and walk their children to match against Stmts in our violation list.
Those generateSink() calls are a handy way to get the appropriate location to highlight (necessary for the BugReport). But their side-effect is to force the analyzer to stop searching this code path. For this particular checker we'd probably prefer to continue our search. I'll bet ASTContext or something similar has a way to get the ExplodedNode we need for BugReport without halting the search.
Appendix
[^1] fatal error: 'llvm/ADT/iterator_range.h' file not found when including StaticAnalyzer/Core/Checker.h