Making usage of `RTLIL::IdString` more efficient

Developers
1

Looking at the code generated for users of IdString reveals some issues. For example, here’s a disassembly of OptMergeWorker::hash_cell_inputs (x86-64):

Every ID() macro call site has a C++ static variable associated with it. For each of those, there’s a hidden “initialized” flag that has to be checked using a load and conditional branch. It’s cheaper to use global IdString variables in the ID:: namespace. The ID:: constants don’t support IdStrings starting with $, but it’s easy enough to add something similar. There are still thousands of calls to the ID() macro but I think it would be good to eventually eliminate them. Please let me know if people agree or disagree…

Every ID() macro call invokes a lambda that returns the IdString. The inferred return type for that lambda is IdString (not a reference), so we create a temporary IdString, which requires incrementing (and eventually decrementing) a refcount. Similarly, CellTypes::output() and other methods take IdString by value, leading to refcount churn. So do IdString::in() and hashlib::hash_ops::hash(). I have created a PR that fixes all these. There are a lot more places that should be converted to take IdString by reference, but that PR is a good start.

Large in() expressions compile to a long chain of comparisons. In this case, clang compiles them as a chain of cmp/sete/or, which avoids branch mispredictions within a single in()… but it’s still a lot of instructions, and as many branches as if cases. The underlying problem is that even for the ID:: constants, theirIdString indices are not known at compile time. Fixing this is a little tricky but not a lot of code. With that fixed, clang turnshash_cell_inputs’s chain of ifs andin()s into a jump table. It’s beautiful.

  8db5d7:       8b 46 48                mov    0x48(%rsi),%eax // load 'cell->type'
...
  8db607:       05 de fe ff ff          add    $0xfffffede,%eax
  8db60c:       83 f8 1c                cmp    $0x1c,%eax
  8db60f:       0f 87 a0 08 00 00       ja     8dbeb5 <_ZZN12_GLOBAL__N_114OptMergeWorkerC1EPN5Yosys5RTLIL6DesignEPNS2_6ModuleEbbbENK11CellPtrHashclEPKNS2_4CellE+0x8f5>
  8db615:       48 8d 0d 40 9e a3 00    lea    0xa39e40(%rip),%rcx        # 131545c <_ZTSN12_GLOBAL__N_17OptPassE+0x90>
  8db61c:       48 63 04 81             movslq (%rcx,%rax,4),%rax
  8db620:       48 01 c8                add    %rcx,%rax
  8db623:       ff e0                   jmp    *%rax

Making the well-known IdString indices compile-time constants seems like a clear win to me. I’ve made this into a PR.

If this sounds good and we want to keep pushing in this direction then future steps would be to convert more code to take IdString by reference, and remove those ID() macro calls.

2

That sounds really great, and I’m all for it, but …

I’d prefer to keep the current ID(...) macro syntax, not only to avoid churn, which would be a one-time cost, but more importantly I think there’s value in having the ID literals correspond to the IdStrings without having to consider C++ keyword collisions or avoiding $.

Luckily, I think with C++17 (which we already require), we can get all the advantages of your approach while keeping the syntax backwards compatible. The idea is to have a constexpr function that takes a string literal as argument and returns the corresponding fixed id or -1 if the literal isn’t listed in the .inc file. This can be done like this:

	template<size_t NL, size_t NR>
	constexpr bool strlit_eq(const char (&l)[NL], const char (&r)[NR]) {
		if constexpr (NL != NR) {
			return false;
		}
		for (size_t i = 0; i != NL; ++i) {
			if (l[i] != r[i])
				return false;
		}
		return true;
	}

	template<size_t N>
	constexpr int fixed_idstring_id(const char (&name)[N]) {
		int fixed_id = 0;
#define X(_id) if (strlit_eq(name, #_id)) { return fixed_id; } fixed_id++;
#include "kernel/constids.inc"
#undef X
		return -1;
	}

If evaluating fixed_idstring_id at compile time becomes to slow (because this version performs a linear pass over all symbols, interpreted by the compiler’s constexpr machinery), we could e.g. preprocess constids.inc using a python script to generate the code for an optimal decision tree instead.

The ID macro could then use constexpr fixed_id = RTLIL::fixed_idstring_id(#_id) and dispatch using if constexpr (fixed_id >= 0) .... I haven’t looked at all the implementation details of your PR, but I’m assuming it can be adapted to work with the fixed id provided this way.

For IDs that are not listed in the .inc file, we could opt for either a fallback that dynamically allocates them, which is nice because it avoids a full recompile during development of a pass that introduces new IDs, or for a compilation error. Another option would be to fail for default builds, but have a development-mode build time option that downgrades the compilation error to a warning emitted once.

3

If evaluating fixed_idstring_id at compile time becomes to slow (because this version performs a linear pass over all symbols, interpreted by the compiler’s constexpr machinery), we could e.g. preprocess constids.inc using a python script to generate the code for an optimal decision tree instead.

That sounds a little bit scary… apart from compile times, without consteval (C++20) there’s a danger that with the wrong compiler options, runtime performance falls off a cliff. Generating a decision tree would help a bit but cost additional complexity.

There is another option: just use $ in our identifiers. Technically C++ does not require $ to be valid in identifiers but clang, gcc and VC++ all support it, so it seems unlikely to be a problem in practice. That also conveniently avoids the problem of and/or/xor being keywords, because $and/$or/$xor are not keywords. I think this is by far the best option if you’re not too squeamish about using something technically non-standard. What do you think?

4

Note that what I’m proposing will only ever invoke fixed_idstring_id to initialize a constexpr int fixed_id. My understanding, and what I’m seeing with clang and gcc, is that failure to evaluate that at compile time will result in a compilation failure even in C++17. Of course a compiler could first const-evaluate constexpr fixed_id but then still emit a call when its value is required at runtime, this seems like such a bad idea and easy enough to avoid, that I’d expect compilers to treat such behavior as a bug, even if the standard would allow it. Let me know if I’m missing something here.

If it turns out to be necessary for compile times, I’m not concerned about the complexity of generating a decision tree since how the fixed id is computed doesn’t make a difference for any users of fixed_idstring_id, so the complexity is well contained.

I think we can safely use $ in identifiers. As far as I understand it, we already depend on the preprocessor considering $ to be allowed in identifiers, otherwise tokenization of the ID arguments would fail. I’d also assume you get matching implementation-defined behavior between the preprocessor and compiler, so I really don’t expect any surprises here.

This is also what I would have suggested if my conclusion was that C++17 doesn’t allow us to assign fixed IDs at compile time while keeping the ID macro.

I still think the constexpr approach has some advantages, though, since it would remain fully compatible with the current ID macro, so we avoid breaking plugins. I also often use custom one-off IDs to emit debug data as attributes while debugging a pass, and certainly don’t want to do a full recompile in that situation, but for that I could adapt and use the dynamic IdString constructor instead.

Overall, I’d still prefer keeping ID macro syntax, but I’m not inherently opposed to using $ identifiers. If it turns out I’m mistaken about how reliably the approach I suggested forces compile time evaluation, I think we should go with that and I might also be swayed by other arguments I haven’t considered so far.

5

Ok, I’ve followed your suggestions and updated the PR. It was tricky to work out the details because we have to make the ID() macro return a value whose type depends on whether the ID is well-known or not… but I eventually was able to win the battle.

6

Also I was able to avoid any noticeable regression in compile time, without introducing an extra build step, by having the constexpr lookup function do a binary search over the sorted ID table.

7

For anyone following along here, we did merge the updated version that keeps the support for the existing ID macro syntax.