Understanding the source of a correctness, performance regression or behaviour changes is valuable information for developers. The process of going backwards and looking for a specific code change that caused a given issue is called bisection, see also https://en.wikipedia.org/wiki/Bisection(softwareengineering).

Even though the algorithmic complexity of bisection is O(log N), the constants involved are sometimes very large, leading to a very long run time. It can be very simple when an obvious local change causes something to start malfunctioning. On the flip side, it can become very costly in case the behaviour change is actually a side effect of a supposedly unrelated commit.

In projects with large code bases, lots of commits per day and requiring more than few minutes to be built - like LLVM and clang -, manually bisecting issues can be a painful and time-consuming process. That is why many tools are available to automate this process, with probably "git bisect" and "svn bisect" amongst the best known ones.

llvmlab bisect is a tool introduced in 2015 by Chris Matthews and Daniel Dunbar, to address challenges when bisecting behavioural changes in LLVM. Especially, it sharply reduces bisection time by not needing to rebuild LLVM on every bisection step, resulting in often many order of magnitude improvements in bisection speed. For example, it is not uncommon for a bisection run to find the commit that changes behaviour in 1 day worth of LLVM commits, to be sped up from hours to minutes.

The bisection process with llvmlab bisect relies on a publicly available build cache. This build cache saves time by avoiding the need to build a toolchain for every commit, by every developer. We have been using a build cache internally at Arm to be able to keep on top of correctness and performance regressions. Without this tool, the bisection runs would take too long to be able to feedback regressions introduced in recent commits in a timely fashion to external developers.

We have recently created two new public bots as part of the Works on Arm project (https://www.worksonarm.com/) to build LLVM and clang, and populate the LLVM build cache with Arm binaries, so they can be used with upstream llvmlab bisect.

In this talk, I’m going to present a practical introduction to automated LLVM/clang bisecting using llvmlab bisect, and following the recent addition of armv7 and aarch64 support on llvmlab bisect, examples will be demonstrated on a Raspberry Pi 3B+ board.