LLVM integrated assembler: Improving expressions and relocations

In my previous post, LLVM integrated assembler: Improving MCExpr and MCValue, I explored improvements to the internal representation MCExpr and MCValue. This post dives into recent improvements I’ve made to refine that system.

Symbol equating

In GNU Assembler, the following directives are called symbol equating. I have re-read its documentation https://sourceware.org/binutils/docs/as.html. Yes, it uses "equating" instead of "assignment" or "definition".

  • symbol = expression (multiple = on the same symbol is allowed)
  • .set symbol, expression (equivalent to =)
  • .equ symbol, expression (equivalent to =)
  • .equiv symbol, expression (redefinition leads to errors)
  • .eqv symbol, expression (lazy evaluation, not implemented in LLVM integrated assembler)

Cycle detection

Equated symbols may form a cycle, which is not allowed.

1
2
3
4
5
6
7
8
9
# CHECK: [[#@LINE+2]]:7: error: cyclic dependency detected for symbol 'a'
# CHECK: [[#@LINE+1]]:7: error: expression could not be evaluated
a = a + 1

# CHECK: [[#@LINE+3]]:6: error: cyclic dependency detected for symbol 'b1'
# CHECK: [[#@LINE+1]]:6: error: expression could not be evaluated
b0 = b1
b1 = b2
b2 = b0

Previously, the LLVM integrated assembler detected cycles by having an occurs check when a symbol was equated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool parseAssignmentExpression(StringRef Name, bool allow_redef,
                               MCAsmParser &Parser, MCSymbol *&Sym,
                               const MCExpr *&Value) {
  ...
  // Validate that the LHS is allowed to be a variable (either it has not been
  // used as a symbol, or it is an absolute symbol).
  Sym = Parser.getContext().lookupSymbol(Name);
  if (Sym) {
    // Diagnose assignment to a label.
    //
    // FIXME: Diagnostics. Note the location of the definition as a label.
    // FIXME: Diagnose assignment to protected identifier (e.g., register name).
    if (Value->isSymbolUsedInExpression(Sym))
      return Parser.Error(EqualLoc, "Recursive use of '" + Name + "'");
    ...
  }

The occurs check function isSymbolUsedInExpression was defined as a tree traversal (DAG traveral more precisely, as subexpressions can be reused, but it very rarely happens in LLVM).

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
bool MCExpr::isSymbolUsedInExpression(const MCSymbol *Sym) const {
  switch (getKind()) {
  case MCExpr::Binary: {
    const MCBinaryExpr *BE = static_cast<const MCBinaryExpr *>(this);
    return BE->getLHS()->isSymbolUsedInExpression(Sym) ||
           BE->getRHS()->isSymbolUsedInExpression(Sym);
  }
  case MCExpr::Target: {
    const MCTargetExpr *TE = static_cast<const MCTargetExpr *>(this);
    return TE->isSymbolUsedInExpression(Sym);
  }
  case MCExpr::Constant:
    return false;
  case MCExpr::SymbolRef: {
    const MCSymbol &S = static_cast<const MCSymbolRefExpr *>(this)->getSymbol();
    if (S.isVariable() && !S.isWeakExternal())
      return S.getVariableValue()->isSymbolUsedInExpression(Sym);
    return &S == Sym;
  }
  case MCExpr::Unary: {
    const MCExpr *SubExpr =
        static_cast<const MCUnaryExpr *>(this)->getSubExpr();
    return SubExpr->isSymbolUsedInExpression(Sym);
  }
  }

  llvm_unreachable("Unknown expr kind!");
}

The problem was that this assignment routine was not used by all symbol equating. For instance, .weakref and many target-specific AsmParsers might define variables without doing the occurs check.

This can be implemented as the classic 3-color depth-first search algorithm for graph, or 2-color for tree. If we apply the 2-color algorithm to a DAG, some vertexes (symbols) might be visited multiple times. This is OK, as shared subexpressions are very uncommon.

I settled on using a 2-color depth-first search.

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
@@ -497,13 +498,25 @@ bool MCExpr::evaluateAsRelocatableImpl(MCValue &Res, const MCAssembler *Asm,

   case SymbolRef: {
     const MCSymbolRefExpr *SRE = cast<MCSymbolRefExpr>(this);
-    const MCSymbol &Sym = SRE->getSymbol();
+    MCSymbol &Sym = const_cast<MCSymbol &>(SRE->getSymbol());
     const auto Kind = SRE->getKind();
     bool Layout = Asm && Asm->hasLayout();

     // Evaluate recursively if this is a variable.
+    if (Sym.isResolving()) {
+      if (Asm && Asm->hasFinalLayout()) {
+        Asm->getContext().reportError(
+            Sym.getVariableValue()->getLoc(),
+            "cyclic dependency detected for symbol '" + Sym.getName() + "'");
+        Sym.IsUsed = false;
+        Sym.setVariableValue(MCConstantExpr::create(0, Asm->getContext()));
+      }
+      return false;
+    }
     if (Sym.isVariable() && (Kind == MCSymbolRefExpr::VK_None || Layout) &&
         canExpand(Sym, InSet)) {
+      Sym.setIsResolving(true);
+      auto _ = make_scope_exit([&] { Sym.setIsResolving(false); });
       bool IsMachO =
           Asm && Asm->getContext().getAsmInfo()->hasSubsectionsViaSymbols();
       if (Sym.getVariableValue()->evaluateAsRelocatableImpl(Res, Asm,

Expression resolving

= and the equivalent .set and equ allow a symbol to be equated multiple times.

1
2
3
4
5
6
7
.data
.set x, 0
.long x         // reference the first instance
x = .-.data
.long x         // reference the second instance
.set x,.-.data
.long x         // reference the third instance

When such a symbol is referenced, its current value is snapshoted and used. Future reassignments do not change previous references.

In general, the LLVM integrated assembler did not allow equating a symbol whose value was not a MCConstExpr (a parse-time integer constant). 

1
2
3
4
% clang -c g.s
g.s:6:8: error: invalid reassignment of non-absolute variable 'x'
.set x,.-.data
       ^

This was probably to reject potentially unsafe reassignments. When a symbol is being reassigned, its old value might still be referenced by an instruction operand or another symbol that has not been resolved yet.

In the past few years when we worked on porting Clang to Linux kernel ports, we worked around the limitation by updating the assembly code.

Relocation generation

You might want to read Relocation generation in assemblers first for the concept.

The linker relaxation framework created redundant relocations (which could be resolved instead) in a few scenarios, including

1
2
3
4
5
6
7
8
9
10
11
12
.option norelax
j label
// For assembly input, RISCVAsmParser::ParseInstruction sets ForceRelocs (https://reviews.llvm.org/D46423).
// For direct object emission, RISCVELFStreamer sets ForceRelocs (#77436)
.option relax
call foo  // linker-relaxable

.option norelax
j label   // redundant relocation due to ForceRelocs
.option relax

label:

and

1
2
3
4
5
6
7
8
9
10
11
call foo

.section .text1,"ax"
# No linker-relaxable instruction. Label differences should be resolved.
w1:
  nop
w2:

.data
# Redundant R_RISCV_SET32 and R_RISCV_SUB32
.long w2-w1

The issues are resolved with quite a few patches. The target-neutral relocation generation framework has been largely revamped to make this possible.