Natural loops

A dominator tree can be used to compute natural loops.

  • For every node H in a post-order traversal of the dominator tree (or the original CFG), find all predecessors that are dominated by H. This identifies all back edges.
  • Each back edge T->H identifies a natural loop with H as the header.
    • Perform a flood fill starting from T in the reversed dominator tree (from exiting block to header)
    • All visited nodes reachable from the root belong to the natural loop associated with the back edge. These nodes are guaranteed to be reachable from H due to the dominator property.
    • Visited nodes unreachable from the root should be ignored.
    • Loops associated with visited nodes are considered subloops.

Read More

Understanding and improving Clang -ftime-report

Clang provides a few options to generate timing report. Among them, -ftime-report and -ftime-trace can be used to analyze the performance of Clang's internal passes.

  • -fproc-stat-report records time and memory on spawned processes (ld, and gas if -fno-integrated-as).
  • -ftime-trace, introduced in 2019, generates Clang timing information in the Chrome Trace Event format (JSON). The format supports nested events, providing a rich view of the front end.
  • -ftime-report: The option name is borrowed from GCC.

This post focuses on the traditional -ftime-report, which uses a line-based textual format.

Understanding -ftime-report output

The output consists of information about multiple timer groups. The last group spans the largest interval and encompasses timing data from other groups.

Up to Clang 19, the last group is called "Clang front-end time report". You would see something like the following.

Read More

Skipping boring functions in debuggers

In debuggers, stepping into a function with arguments that involve function calls may step into the nested function calls, even if they are simple and uninteresting, such as those found in the C++ STL.

GDB

Consider the following example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <memory>
#include <vector>
using namespace std;

void foo(int i, int j) {
  printf("%d %d\n", i, j);
}

int main() {
  auto i = make_unique<int>(3);
  vector v{1,2};
  foo(*i, v.back()); // step into
}

When GDB stops at the foo call, the step (s) command will step into std::vector::back and std::unique_ptr::operator*. While you can execute finish (fin) and then execute s again, it's time-consuming and distracting, especially when dealing with complex argument expressions.

Read More

Exporting Tweets

On https://x.com/settings/, click More -> Settings and privacy -> Download an archive of your data. Wait for a message from x.com: "@XXX your X data is ready" Download the archive.

1
cp data/tweets.js tweets.ts

Change the first line from window.YTD.tweets.part0 = [ to let part0 = [, and append

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
import { unescape } from "@std/html/entities";

let out = part0.map(tw => [new Date(tw.tweet.created_at), tw.tweet.full_text])
out.sort((a,b) => a[0] - b[0])

let yy0 = 0, mm0 = 0, str = ''
for (let i=0, j=0; i<=out.length; i++) {
  let d = i<out.length ? out[i][0] : new Date('9999-12-31')
  let yy = d.getYear()+1900, mm = d.getMonth()+1
  if (yy0 != yy) {
    if (str.length) {
      try {
        Deno.mkdirSync(String(yy0))
      } catch (e) {
      }
      Deno.writeTextFileSync(`${yy0}/index.md`, str)
    }
    yy0 = yy
    mm0 = 0
    str = `# ${yy0}\n`
    if (i == out.length) break
  }
  if (mm0 != mm) {
    str += `\n## ${yy}-${String(mm).padStart(2,'0')}\n`
    mm0 = mm
  }
  str += `\n${unescape(out[i][1]).replace(/(http(s)?:[-/.\w]+)/, "<$1>")}\n`
}

Then run deno run --allow-write=. tweets.ts

1
2
3
4
5
6
7
8
9
10
11
12
% cat 2022/index.md
# 2022

## 2022-01

tweet0

tweet1

## 2022-02

...

tweet0

tweet1

Simplifying disassembly with LLVM tools

Both compiler developers and security researchers have built disassemblers. They often prioritize different aspects. Compiler toolchains, benefiting from direct contributions from CPU vendors, tend to offer more accurate and robust decoding. Security-focused tools, on the other hand, often excel in user interface design.

For quick disassembly tasks, rizin provides a convenient command-line interface.

Read More

clang-format and single-line statements

The Google C++ Style is widely adopted by projects. It contains a brace omission guideline in Looping and branching statements:

For historical reasons, we allow one exception to the above rules: the curly braces for the controlled statement or the line breaks inside the curly braces may be omitted if as a result the entire statement appears on either a single line (in which case there is a space between the closing parenthesis and the controlled statement) or on two lines (in which case there is a line break after the closing parenthesis and there are no braces).

Read More

Removing global state from LLD

LLD, the LLVM linker, is a mature and fast linker supporting multiple binary formats (ELF, Mach-O, PE/COFF, WebAssembly). Designed as a standalone program, the code base relies heavily on global state, making it less than ideal for library integration. As outlined in RFC: Revisiting LLD-as-a-library design, two main hurdles exist:

  • Fatal errors: they exit the process without returning control to the caller. This was actually addressed for most scenarios in 2020 by utilizing llvm::sys::Process::Exit(val, /*NoCleanup=*/true) and CrashRecoveryContext (longjmp under the hood).
  • Global variable conflicts: shared global variables do not allow two concurrent invocation.

I understand that calling a linker API could be convenient, especially when you want to avoid shipping another executable (which can be large when you link against LLVM statically). However, I believe that invoking LLD as a separate process remains the recommended approach. There are several advantages:

  • Build system control: Build systems gain greater control over scheduling and resource allocation for LLD. In an edit-compile-link cycle, the link could need more resources and threading is more useful.
  • Better parallelism management
  • Global state isolation: LLVM's global state (primarily cl::opt and ManagedStatic) is isolated.

Read More

Keeping pace with LLVM: compatibility strategies

LLVM's C++ API doesn't offer a stability guarantee. This means function signatures can change or be removed between versions, forcing projects to adapt.

On the other hand, LLVM has an extensive API surface. When a library like llvm/lib/Y relies functionality from another library, the API is often exported in header files under llvm/include/llvm/X/, even if it is not intended to be user-facing.

To be compatible with multiple LLVM versions, many projects rely on #if directives based on the LLVM_VERSION_MAJOR macro. This post explores the specific techniques used by ccls to ensure compatibility with LLVM versions 7 to 19. For the latest release (ccls 0.20241108), support for LLVM versions 7 to 9 has been discontinued.

Given the tight coupling between LLVM and Clang, the LLVM_VERSION_MAJOR macro can be used for both version detection. There's no need to check CLANG_VERSION_MAJOR.

Read More