Add `isRelExprOneOf` helper (alternative to D27145).

[silvas]

Summary

Additionally, this uses a fast implementation to do the test, significantly reducing the amount of branching in this hot path of the relocation handling code.

Thanks to Joerg for suggesting this simple way to do this that should still retain most of the performance advantages of the approach in D27145.

[joerg]

Otherwise, LGTM.

ELF/Relocations.h

81 ↗

(On Diff #79366)

Small item, but please add a static assert that 0 <= Head < 64 here.

90 ↗

(On Diff #79366)

...and a run-time assert for for 0<=Expr < 64 here.

[ruiu]

Ah, so there's a new patch. This looks nice. LGTM.

Before submitting, please update the commit message so that you'll keep the message you wrote for https://reviews.llvm.org/D27145 in our commit history.

ELF/Relocations.h

78 ↗

(On Diff #79366)

nit: add a blank line.

90 ↗

(On Diff #79366)

Maybe we should instead define R_END at end of RelExpr and statically assert R_END < 64;

[joerg]

ELF/Relocations.h

90 ↗

(On Diff #79366)

One motivation for doing the asserts here is that there is a good chance it will get copied to other places. So getting it right the first time helps avoiding surprises in other places where the constraints are not that obvious.

[silvas]

Sadly, it seems like static_assert can't be used on constexpr function arguments, so I've had to rewrite this to pass the set of RelExprs as template arguments. Though the implementation of the mask construction becomes slightly larger, I actually like the template argument approach because the call sites of isRelExprOneOf have the the value to check in the runtime argument list separate from the set of values to check against (which are now in the template arguments).

Just posting this explicitly so that if one of you feels strongly I can go back to the original version with constexpr and use an R_END technique to static assert (that gives a bit less protection though), but the fact that I think the callsites are cleaner for the template version seems worth it to stick with the template. Please let me know if this is good or if I should go back to the original and use R_END.

[ruiu]

I agree that at the call side this looks better, but after reviewing the previous one again, I think I still prefer the previous one, because recursive templates are more complicated than the original simple-minded constexpr containing a for-loop. In practice, static_assert'ing on R_END would be enough as a protection.

[silvas]

In D27156#608816, @ruiu wrote:

I agree that at the call side this looks better, but after reviewing the previous one again, I think I still prefer the previous one, because recursive templates are more complicated than the original simple-minded constexpr containing a for-loop. In practice, static_assert'ing on R_END would be enough as a protection.

Unfortunately the R_END approach causes "unhandled case in switch" warnings in getSymVA. What do you think? I like the safety of these switch warnings.

ELF/Relocations.h

81 ↗

(On Diff #79366)

Sadly it seems like static_assert is not allowed inside constexpr functions :(

[silvas]

Somewhat simpler template version. Let me know what you think. I think the improved clarity at the call site is worth it.

[silvas]

the original simple-minded constexpr containing a for-loop

There wasn't a for loop. It was still recursive in the constexpr case.

Thinking about this for a little bit, I actually like the extra clarity at the use site for the template approach. If you don't mind, I would like to keep it that way.
The templates are not any more complicated (they are both a recursive approach). The templates are slightly more lines of code, but the conceptual complexity is still the same.

[silvas]

Small fixup (delete some code that I forgot to remove in the last patch).

[joerg]

This looks fine thanks.

[ruiu]

LGTM

lld/trunk/ELF/Relocations.h

enum RelExpr {
   R_TLSDESC_PAGE,
   R_TLSDESC_CALL,
   R_TLSGD,
   R_TLSGD_PC,
   R_TLSLD,
   R_TLSLD_PC,
 };
 
+// Build a bitmask with one bit set for each RelExpr.
+//
+// Constexpr function arguments can't be used in static asserts, so we
+// use template arguments to build the mask.
+// But function template partial specializations don't exist (needed
+// for base case of the recursion), so we need a dummy struct.
+template <RelExpr... Exprs> struct RelExprMaskBuilder {
+  static inline uint64_t build() { return 0; }
+};
+
+// Specialization for recursive case.
+template <RelExpr Head, RelExpr... Tail>
+struct RelExprMaskBuilder<Head, Tail...> {
+  static inline uint64_t build() {
+    static_assert(0 <= Head && Head < 64,
+                  "RelExpr is too large for 64-bit mask!");
+    return (uint64_t(1) << Head) | RelExprMaskBuilder<Tail...>::build();
+  }
+};
+
+// Return true if `Expr` is one of `Exprs`.
+// There are fewer than 64 RelExpr's, so we can represent any set of
+// RelExpr's as a constant bit mask and test for membership with a
+// couple cheap bitwise operations.
+template <RelExpr... Exprs> bool isRelExprOneOf(RelExpr Expr) {
+  assert(0 <= Expr && Expr < 64 && "RelExpr is too large for 64-bit mask!");
+  return (uint64_t(1) << Expr) & RelExprMaskBuilder<Exprs...>::build();
+}
+
 // Architecture-neutral representation of relocation.
 struct Relocation {
   RelExpr Expr;
   uint32_t Type;
   uint64_t Offset;
   uint64_t Addend;
   SymbolBody *Sym;
 };

lld/trunk/ELF/Relocations.cpp

 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 namespace lld {
 namespace elf {
 
 static bool refersToGotEntry(RelExpr Expr) {
-  return Expr == R_GOT || Expr == R_GOT_OFF || Expr == R_MIPS_GOT_LOCAL_PAGE ||
-         Expr == R_MIPS_GOT_OFF || Expr == R_MIPS_GOT_OFF32 ||
-         Expr == R_MIPS_TLSGD || Expr == R_MIPS_TLSLD ||
-         Expr == R_GOT_PAGE_PC || Expr == R_GOT_PC || Expr == R_GOT_FROM_END ||
-         Expr == R_TLSGD || Expr == R_TLSGD_PC || Expr == R_TLSDESC ||
-         Expr == R_TLSDESC_PAGE;
+  return isRelExprOneOf<R_GOT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOT_OFF,
+                        R_MIPS_GOT_OFF32, R_MIPS_TLSGD, R_MIPS_TLSLD,
+                        R_GOT_PAGE_PC, R_GOT_PC, R_GOT_FROM_END, R_TLSGD,
+                        R_TLSGD_PC, R_TLSDESC, R_TLSDESC_PAGE>(Expr);
 }
 
 static bool isPreemptible(const SymbolBody &Body, uint32_t Type) {
   // In case of MIPS GP-relative relocations always resolve to a definition
   // in a regular input file, ignoring the one-definition rule. So we,
   // for example, should not attempt to create a dynamic relocation even
   // if the target symbol is preemptible. There are two two MIPS GP-relative
   // relocations R_MIPS_GPREL16 and R_MIPS_GPREL32. But only R_MIPS_GPREL16
template <class ELFT> static bool isAbsolute(const SymbolBody &Body) {
   return false;
 }
 
 template <class ELFT> static bool isAbsoluteValue(const SymbolBody &Body) {
   return isAbsolute<ELFT>(Body) || Body.isTls();
 }
 
 static bool needsPlt(RelExpr Expr) {
-  return Expr == R_PLT_PC || Expr == R_PPC_PLT_OPD || Expr == R_PLT ||
-         Expr == R_PLT_PAGE_PC || Expr == R_THUNK_PLT_PC;
+  return isRelExprOneOf<R_PLT_PC, R_PPC_PLT_OPD, R_PLT, R_PLT_PAGE_PC,
+                        R_THUNK_PLT_PC>(Expr);
 }
 
 // True if this expression is of the form Sym - X, where X is a position in the
 // file (PC, or GOT for example).
 static bool isRelExpr(RelExpr Expr) {
-  return Expr == R_PC || Expr == R_GOTREL || Expr == R_GOTREL_FROM_END ||
-         Expr == R_MIPS_GOTREL || Expr == R_PAGE_PC || Expr == R_RELAX_GOT_PC ||
-         Expr == R_THUNK_PC || Expr == R_THUNK_PLT_PC;
+  return isRelExprOneOf<R_PC, R_GOTREL, R_GOTREL_FROM_END, R_MIPS_GOTREL,
+                        R_PAGE_PC, R_RELAX_GOT_PC, R_THUNK_PC, R_THUNK_PLT_PC>(
+      Expr);
 }
 
 template <class ELFT>
 static bool isStaticLinkTimeConstant(RelExpr E, uint32_t Type,
                                      const SymbolBody &Body,
                                      InputSectionBase<ELFT> &S,
                                      typename ELFT::uint RelOff) {
   // These expressions always compute a constant
-  if (E == R_SIZE || E == R_GOT_FROM_END || E == R_GOT_OFF ||
-      E == R_MIPS_GOT_LOCAL_PAGE || E == R_MIPS_GOT_OFF ||
-      E == R_MIPS_GOT_OFF32 || E == R_MIPS_TLSGD || E == R_GOT_PAGE_PC ||
-      E == R_GOT_PC || E == R_PLT_PC || E == R_TLSGD_PC || E == R_TLSGD ||
-      E == R_PPC_PLT_OPD || E == R_TLSDESC_CALL || E == R_TLSDESC_PAGE ||
-      E == R_HINT || E == R_THUNK_PC || E == R_THUNK_PLT_PC)
+  if (isRelExprOneOf<R_SIZE, R_GOT_FROM_END, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE,
+                     R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_MIPS_TLSGD,
+                     R_GOT_PAGE_PC, R_GOT_PC, R_PLT_PC, R_TLSGD_PC, R_TLSGD,
+                     R_PPC_PLT_OPD, R_TLSDESC_CALL, R_TLSDESC_PAGE, R_HINT,
+                     R_THUNK_PC, R_THUNK_PLT_PC>(E))
     return true;
 
   // These never do, except if the entire file is position dependent or if
   // only the low bits are used.
   if (E == R_GOT || E == R_PLT || E == R_TLSDESC)
     return Target->usesOnlyLowPageBits(Type) || !Config->Pic;
 
   if (isPreemptible(Body, Type))
for (auto I = Rels.begin(), E = Rels.end(); I != E; ++I) {
     if (unsigned Processed =
             handleTlsRelocation<ELFT>(Type, Body, C, Offset, Addend, Expr)) {
       I += (Processed - 1);
       continue;
     }
 
     // Ignore "hint" and TLS Descriptor call relocation because they are
     // only markers for relaxation.
-    if (Expr == R_HINT || Expr == R_TLSDESC_CALL)
+    if (isRelExprOneOf<R_HINT, R_TLSDESC_CALL>(Expr))
       continue;
 
-    if (needsPlt(Expr) || Expr == R_THUNK_ABS || Expr == R_THUNK_PC ||
-        Expr == R_THUNK_PLT_PC || refersToGotEntry(Expr) ||
-        !isPreemptible(Body, Type)) {
+    if (needsPlt(Expr) ||
+        isRelExprOneOf<R_THUNK_ABS, R_THUNK_PC, R_THUNK_PLT_PC>(Expr) ||
+        refersToGotEntry(Expr) || !isPreemptible(Body, Type)) {
       // If the relocation points to something in the file, we can process it.
       bool Constant =
           isStaticLinkTimeConstant<ELFT>(Expr, Type, Body, C, RI.r_offset);
 
       // If the output being produced is position independent, the final value
       // is still not known. In that case we still need some help from the
       // dynamic linker. We can however do better than just copying the incoming
       // relocation. We can process some of it and and just ask the dynamic