[tblgen] Track CodeInit origins when possible

[dsanders]

Summary

Add an SMLoc to CodeInit that records the source line it originated from.
This allows tablegen to point precisely at portions of code when reporting
errors within the CodeInit. For example, in the upcoming GlobalISel
combiner, it can report undefined expansions and point at the instance of
the expansion. This is achieved using something like:

SMLoc::getFromPointer(SMLoc::getPointer() +
                      (StringRef - CodeInit::getValue()))

The location is lost when producing a CodeInit by string concatenation so
a fallback SMLoc is required (e.g. the Record::getLoc()) but that's pretty
rare for CodeInits.

There's a reasonable case for extending tracking of a couple other Init
objects, for example StringInit's are often parsed and it would be good to
point inside the string when reporting errors about that. However, location
tracking also harms de-duplication. This is fine for CodeInit where there's
only a few hundred of them (~160 for X86) and it may be worth it for
StringInit (~86k up to ~1.9M for roughly 15MB increase for X86).
However the origin tracking would be a _terrible_ idea for IntInit, BitInit,
and UnsetInit. I haven't measured either of those three but BitInit would
most likely be on the order of increasing the current 2 BitInit values up
to billions.

[paquette]

Better error-reporting sounds like a net win to me. LGTM aside from spelling nit.

lib/TableGen/Record.cpp

525

s/CodeInit's/CodeInits/

include/llvm/ADT/StringSet.h

class StringSet : public StringMap<char, AllocatorTy> {
     using base = StringMap<char, AllocatorTy>;
 
   public:
     StringSet() = default;
     StringSet(std::initializer_list<StringRef> S) {
       for (StringRef X : S)
         insert(X);
     }
+    explicit StringSet(AllocatorTy A) : base(A) {}
 
     std::pair<typename base::iterator, bool> insert(StringRef Key) {
       assert(!Key.empty());
       return base::insert(std::make_pair(Key, '\0'));
     }
 
     template <typename InputIt>
     void insert(const InputIt &Begin, const InputIt &End) {
       for (auto It = Begin; It != End; ++It)
         base::insert(std::make_pair(*It, '\0'));
     }
   };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_STRINGSET_H

include/llvm/TableGen/Record.h

public:
 
   Init *getBit(unsigned Bit) const override {
     llvm_unreachable("Illegal bit reference off string");
   }
 };
 
 class CodeInit : public TypedInit {
   StringRef Value;
+  SMLoc Loc;
 
-  explicit CodeInit(StringRef V)
+  explicit CodeInit(StringRef V, const SMLoc &Loc)
       : TypedInit(IK_CodeInit, static_cast<RecTy *>(CodeRecTy::get())),
-        Value(V) {}
+        Value(V), Loc(Loc) {}
 
 public:
   CodeInit(const StringInit &) = delete;
   CodeInit &operator=(const StringInit &) = delete;
 
   static bool classof(const Init *I) {
     return I->getKind() == IK_CodeInit;
   }
 
-  static CodeInit *get(StringRef);
+  static CodeInit *get(StringRef, const SMLoc &Loc);
 
   StringRef getValue() const { return Value; }
+  const SMLoc &getLoc() const { return Loc; }
 
   Init *convertInitializerTo(RecTy *Ty) const override;
 
   bool isConcrete() const override { return true; }
   std::string getAsString() const override {
     return "[{" + Value.str() + "}]";
   }
 

lib/TableGen/Record.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/SMLoc.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include <cassert>
 #include <cstdint>
 #include <memory>
 #include <string>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
+#define DEBUG_TYPE "tblgen-records"
+
 static BumpPtrAllocator Allocator;
 
+STATISTIC(CodeInitsConstructed,
+          "The total number of unique CodeInits constructed");
+
 //===----------------------------------------------------------------------===//
 //    Type implementations
 //===----------------------------------------------------------------------===//
 
 BitRecTy BitRecTy::Shared;
 CodeRecTy CodeRecTy::Shared;
 IntRecTy IntRecTy::Shared;
 StringRecTy StringRecTy::Shared;
for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
     if (Bits[i] >= 64)
       return nullptr;
 
     NewBits[i] = BitInit::get(Value & (INT64_C(1) << Bits[i]));
   }
   return BitsInit::get(NewBits);
 }
 
-CodeInit *CodeInit::get(StringRef V) {
-  static StringMap<CodeInit*, BumpPtrAllocator &> ThePool(Allocator);
+CodeInit *CodeInit::get(StringRef V, const SMLoc &Loc) {
+  static StringSet<BumpPtrAllocator &> ThePool(Allocator);
 
-  auto &Entry = *ThePool.insert(std::make_pair(V, nullptr)).first;
-  if (!Entry.second)
-    Entry.second = new(Allocator) CodeInit(Entry.getKey());
-  return Entry.second;
+  CodeInitsConstructed++;
+
+  // Unlike StringMap, StringSet doesn't accept empty keys.
+  if (V.empty())
+    return new (Allocator) CodeInit("", Loc);
+
+  // Location tracking prevents us from de-duping CodeInit's as we're never
+  // called with the same string and same location twice. However, we can at
+  // least de-dupe the strings for a modest saving.
+  auto &Entry = *ThePool.insert(V).first;
+  return new(Allocator) CodeInit(Entry.getKey(), Loc);
 }
 
 StringInit *StringInit::get(StringRef V) {
   static StringMap<StringInit*, BumpPtrAllocator &> ThePool(Allocator);
 
   auto &Entry = *ThePool.insert(std::make_pair(V, nullptr)).first;
   if (!Entry.second)
     Entry.second = new(Allocator) StringInit(Entry.getKey());
   return Entry.second;
 }
 
 Init *StringInit::convertInitializerTo(RecTy *Ty) const {
   if (isa<StringRecTy>(Ty))
     return const_cast<StringInit *>(this);
   if (isa<CodeRecTy>(Ty))
-    return CodeInit::get(getValue());
+    return CodeInit::get(getValue(), SMLoc());
 
   return nullptr;
 }
 
 Init *CodeInit::convertInitializerTo(RecTy *Ty) const {
   if (isa<CodeRecTy>(Ty))
     return const_cast<CodeInit *>(this);
   if (isa<StringRecTy>(Ty))

lib/TableGen/TGParser.cpp

while (Lex.getCode() == tgtok::StrVal) {
       Val += Lex.getCurStrVal();
       Lex.Lex();
     }
 
     R = StringInit::get(Val);
     break;
   }
   case tgtok::CodeFragment:
-    R = CodeInit::get(Lex.getCurStrVal());
+    R = CodeInit::get(Lex.getCurStrVal(), Lex.getLoc());
     Lex.Lex();
     break;
   case tgtok::question:
     R = UnsetInit::get();
     Lex.Lex();
     break;
   case tgtok::Id: {
     SMLoc NameLoc = Lex.getLoc();