TableGen: Allow foreach in multiclass to depend on template args

[nhaehnle]

Summary

This also allows inner foreach loops to have a list that depends on
the iteration variable of an outer foreach loop. The test cases show
some very simple examples of how this can be used.

This was perhaps the last remaining major non-orthogonality in the
TableGen frontend.

Change-Id: I79b92d41a5c0e7c03cc8af4000c5e1bda5ef464d

[nhaehnle]

Ping.

[simon_tatham]

test/TableGen/foreach-multiclass.td

20

Hmm, this is generating -print-records output that's not legal tablegen input – the minus sign isn't a valid character in identifier names as far as the lexer's concerned. Is that a problem? I think in this situation I'd have expected a complaint from tablegen ("this concatenation would generate an illegal record name"), rather than silently generating this kind of unexpected output which I could imagine causing knock-on confusion in an unwary backend.

[simon_tatham]

lib/TableGen/TGParser.cpp

2917

While you're looking at this code, should this be tracking whether the DefmName you're adding to Substs here was explicitly given by the user, or made up anonymously on line 2861?

I feel as if the end-product record that comes out of the whole chain of defms and foreaches ought to have its 'anonymous' flag set if any defm or def on the way to it was anonymous, because in that case some part of the final name will include something TableGen made up.

[nhaehnle]

lib/TableGen/TGParser.cpp

2917

I'd agree if we were recreating TableGen from scratch.

However, there are some existing TableGen files (e.g. something in X86 about condition codes) that rely on being able to substitute NAME reliably in a multiclass that is instantiated by a defm without a name. I did ponder changing those TableGen files accordingly while I did the earlier change (about streamlining NAME resolution), but ultimately decided against it to reduce the churn in existing .td files.

While I also think the behavior with the made-up "anonymous_NNNN" part in names is a bit weird, it's a comparatively minor wart that doesn't really hurt anything as far as I can tell.

test/TableGen/foreach-multiclass.td

20

Fair point. I'll at least change the test case to remove this. I don't know if we can or should actually add such a check.

[nhaehnle]

Address a review comment

[simon_tatham]

In that case, LGTM – though I must admit that this is probably the part of tablegen I understand least well, so I can't guarantee not to have missed anything subtle!

lib/TableGen/TGParser.cpp

2917

Fair enough -- I suppose if the backend just needs a set of unique string identifiers and doesn't necessarily care exactly what they are, then that's enough.

In that case I should probably revert the tweak in that area I just made to my JSON backend (when I started exporting the anonymous flag). Fortunately you're about to cause a merge conflict that will remind me to do that :-)

[tra]

Few nits. LGTM overall.

lib/TableGen/TGParser.cpp

390–391

I think for (auto &E: LI) should work.

1266–1276

This may warrant a comment explaining why we need a temp record here.
AFAICT, it's supposed to provide a scope for the names used in top-level foreach.

1528–1540

Same here.

lib/TableGen/TGParser.h

45–48

Are Rec and Loop expected to be mutually exclusive?
It would be good to have some asserts enforcing the invariant.

test/TableGen/NestedForeach.td

20–22

Here and below I'd make all nested constructs indented, possibly with braces -- like it's done in the nested foreach above.

[nhaehnle]

lib/TableGen/TGParser.cpp

390–391

Right you are, changed it (to *LI actually, but that's a detail).

1266–1276

Right, added a comment here and below.

lib/TableGen/TGParser.h

45–48

Good point, done.

test/TableGen/NestedForeach.td

20–22

I'm putting the indent, but keeping it without braces (to make sure that path of the parser is covered as well).

[nhaehnle]

Address review comments. Going to submit later today.

include/llvm/TableGen/Record.h

public:
   /// This method looks up the specified field and returns its
   /// value as an Dag, throwing an exception if the field does not exist or if
   /// the value is not the right type.
   DagInit *getValueAsDag(StringRef FieldName) const;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const Record &R);
 
-struct MultiClass {
-  Record Rec;  // Placeholder for template args and Name.
-  using RecordVector = std::vector<std::unique_ptr<Record>>;
-  RecordVector DefPrototypes;
-
-  void dump() const;
-
-  MultiClass(StringRef Name, SMLoc Loc, RecordKeeper &Records) :
-    Rec(Name, Loc, Records) {}
-};
-
 class RecordKeeper {
   friend class RecordRecTy;
   using RecordMap = std::map<std::string, std::unique_ptr<Record>>;
   RecordMap Classes, Defs;
   FoldingSet<RecordRecTy> RecordTypePool;
   std::map<std::string, Init *> ExtraGlobals;
   unsigned AnonCounter = 0;
 
for (size_t I = 1, E = LHSNumParts; I < E; I+=2) {
         return LHSVal < RHSVal;
     }
     return LHSNumParts < RHSNumParts;
   }
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const RecordKeeper &RK);
 
-/// Return an Init with a qualifier prefix referring
-/// to CurRec's name.
-Init *QualifyName(Record &CurRec, MultiClass *CurMultiClass,
-                  Init *Name, StringRef Scoper);
-
 //===----------------------------------------------------------------------===//
 //  Resolvers
 //===----------------------------------------------------------------------===//
 
 /// Interface for looking up the initializer for a variable name, used by
 /// Init::resolveReferences.
 class Resolver {
   Record *CurRec;

lib/TableGen/Record.cpp

DagInit *Record::getValueAsDag(StringRef FieldName) const {
 
   if (DagInit *DI = dyn_cast<DagInit>(R->getValue()))
     return DI;
   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
     FieldName + "' does not have a dag initializer!");
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-LLVM_DUMP_METHOD void MultiClass::dump() const {
-  errs() << "Record:\n";
-  Rec.dump();
-
-  errs() << "Defs:\n";
-  for (const auto &Proto : DefPrototypes)
-    Proto->dump();
-}
-
 LLVM_DUMP_METHOD void RecordKeeper::dump() const { errs() << *this; }
 #endif
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const RecordKeeper &RK) {
   OS << "------------- Classes -----------------\n";
   for (const auto &C : RK.getClasses())
     OS << "class " << *C.second;
 
RecordKeeper::getAllDerivedDefinitions(StringRef ClassName) const {
   std::vector<Record*> Defs;
   for (const auto &D : getDefs())
     if (D.second->isSubClassOf(Class))
       Defs.push_back(D.second.get());
 
   return Defs;
 }
 
-Init *llvm::QualifyName(Record &CurRec, MultiClass *CurMultiClass,
-                        Init *Name, StringRef Scoper) {
-  Init *NewName =
-      BinOpInit::getStrConcat(CurRec.getNameInit(), StringInit::get(Scoper));
-  NewName = BinOpInit::getStrConcat(NewName, Name);
-  if (CurMultiClass && Scoper != "::") {
-    Init *Prefix = BinOpInit::getStrConcat(CurMultiClass->Rec.getNameInit(),
-                                           StringInit::get("::"));
-    NewName = BinOpInit::getStrConcat(Prefix, NewName);
-  }
-
-  if (BinOpInit *BinOp = dyn_cast<BinOpInit>(NewName))
-    NewName = BinOp->Fold(&CurRec);
-  return NewName;
-}
-
 Init *MapResolver::resolve(Init *VarName) {
   auto It = Map.find(VarName);
   if (It == Map.end())
     return nullptr;
 
   Init *I = It->second.V;
 
   if (!It->second.Resolved && Map.size() > 1) {

lib/TableGen/TGParser.h

 #include <map>
 
 namespace llvm {
   class Record;
   class RecordVal;
   class RecordKeeper;
   class RecTy;
   class Init;
+  struct ForeachLoop;
   struct MultiClass;
   struct SubClassReference;
   struct SubMultiClassReference;
 
   struct LetRecord {
     StringInit *Name;
     std::vector<unsigned> Bits;
     Init *Value;
     SMLoc Loc;
     LetRecord(StringInit *N, ArrayRef<unsigned> B, Init *V, SMLoc L)
       : Name(N), Bits(B), Value(V), Loc(L) {
     }
   };
 
+  /// RecordsEntry - Can be either a record or a foreach loop.
+  struct RecordsEntry {
+    std::unique_ptr<Record> Rec;
+    std::unique_ptr<ForeachLoop> Loop;
+
+    void dump() const;
+
+    RecordsEntry() {}
+    RecordsEntry(std::unique_ptr<Record> Rec) : Rec(std::move(Rec)) {}
+    RecordsEntry(std::unique_ptr<ForeachLoop> Loop)
+      : Loop(std::move(Loop)) {}
+  };
+
   /// ForeachLoop - Record the iteration state associated with a for loop.
   /// This is used to instantiate items in the loop body.
   struct ForeachLoop {
+    SMLoc Loc;
     VarInit *IterVar;
-    ListInit *ListValue;
+    Init *ListValue;
+    std::vector<RecordsEntry> Entries;
 
-    ForeachLoop(VarInit *IVar, ListInit *LValue)
-      : IterVar(IVar), ListValue(LValue) {}
+    void dump() const;
+
+    ForeachLoop(SMLoc Loc, VarInit *IVar, Init *LValue)
+      : Loc(Loc), IterVar(IVar), ListValue(LValue) {}
   };
 
   struct DefsetRecord {
     SMLoc Loc;
     RecTy *EltTy;
     SmallVector<Init *, 16> Elements;
   };
 
+struct MultiClass {
+  Record Rec;  // Placeholder for template args and Name.
+  std::vector<RecordsEntry> Entries;
+
+  void dump() const;
+
+  MultiClass(StringRef Name, SMLoc Loc, RecordKeeper &Records) :
+    Rec(Name, Loc, Records) {}
+};
+
 class TGParser {
   TGLexer Lex;
   std::vector<SmallVector<LetRecord, 4>> LetStack;
   std::map<std::string, std::unique_ptr<MultiClass>> MultiClasses;
 
   /// Loops - Keep track of any foreach loops we are within.
   ///
-  typedef std::vector<ForeachLoop> LoopVector;
-  LoopVector Loops;
+  std::vector<std::unique_ptr<ForeachLoop>> Loops;
 
   SmallVector<DefsetRecord *, 2> Defsets;
 
   /// CurMultiClass - If we are parsing a 'multiclass' definition, this is the
   /// current value.
   MultiClass *CurMultiClass;
 
   // Record tracker
public:
   }
 
 private:  // Semantic analysis methods.
   bool AddValue(Record *TheRec, SMLoc Loc, const RecordVal &RV);
   bool SetValue(Record *TheRec, SMLoc Loc, Init *ValName,
                 ArrayRef<unsigned> BitList, Init *V,
                 bool AllowSelfAssignment = false);
   bool AddSubClass(Record *Rec, SubClassReference &SubClass);
+  bool AddSubClass(RecordsEntry &Entry, SubClassReference &SubClass);
   bool AddSubMultiClass(MultiClass *CurMC,
                         SubMultiClassReference &SubMultiClass);
 
-  // IterRecord: Map an iterator name to a value.
-  struct IterRecord {
-    VarInit *IterVar;
-    Init *IterValue;
-    IterRecord(VarInit *Var, Init *Val) : IterVar(Var), IterValue(Val) {}
-  };
-
-  // IterSet: The set of all iterator values at some point in the
-  // iteration space.
-  typedef std::vector<IterRecord> IterSet;
+  using SubstStack = SmallVector<std::pair<Init *, Init *>, 8>;
 
-  bool addDefOne(std::unique_ptr<Record> Rec, IterSet &IterVals);
-  bool addDefForeach(Record *Rec, IterSet &IterVals);
-  bool addDef(std::unique_ptr<Record> Rec);
+  bool addEntry(RecordsEntry E);
+  bool resolve(const ForeachLoop &Loop, SubstStack &Stack, bool Final,
+               std::vector<RecordsEntry> *Dest, SMLoc *Loc = nullptr);
+  bool resolve(const std::vector<RecordsEntry> &Source, SubstStack &Substs,
+               bool Final, std::vector<RecordsEntry> *Dest,
+               SMLoc *Loc = nullptr);
+  bool addDefOne(std::unique_ptr<Record> Rec);
 
 private:  // Parser methods.
   bool ParseObjectList(MultiClass *MC = nullptr);
   bool ParseObject(MultiClass *MC);
   bool ParseClass();
   bool ParseMultiClass();
   bool ParseDefm(MultiClass *CurMultiClass);
   bool ParseDef(MultiClass *CurMultiClass);
   bool ParseDefset();
   bool ParseForeach(MultiClass *CurMultiClass);
   bool ParseTopLevelLet(MultiClass *CurMultiClass);
   void ParseLetList(SmallVectorImpl<LetRecord> &Result);
 
   bool ParseObjectBody(Record *CurRec);
   bool ParseBody(Record *CurRec);
   bool ParseBodyItem(Record *CurRec);
 
   bool ParseTemplateArgList(Record *CurRec);
   Init *ParseDeclaration(Record *CurRec, bool ParsingTemplateArgs);
-  VarInit *ParseForeachDeclaration(ListInit *&ForeachListValue);
+  VarInit *ParseForeachDeclaration(Init *&ForeachListValue);
 
   SubClassReference ParseSubClassReference(Record *CurRec, bool isDefm);
   SubMultiClassReference ParseSubMultiClassReference(MultiClass *CurMC);
 
   Init *ParseIDValue(Record *CurRec, StringInit *Name, SMLoc NameLoc,
                      IDParseMode Mode = ParseValueMode);
   Init *ParseSimpleValue(Record *CurRec, RecTy *ItemType = nullptr,
                          IDParseMode Mode = ParseValueMode);
private:  // Parser methods.
   bool ParseRangePiece(SmallVectorImpl<unsigned> &Ranges);
   RecTy *ParseType();
   Init *ParseOperation(Record *CurRec, RecTy *ItemType);
   RecTy *ParseOperatorType();
   Init *ParseObjectName(MultiClass *CurMultiClass);
   Record *ParseClassID();
   MultiClass *ParseMultiClassID();
   bool ApplyLetStack(Record *CurRec);
+  bool ApplyLetStack(RecordsEntry &Entry);
 };
 
 } // end namespace llvm
 
 #endif

lib/TableGen/TGParser.cpp

if (Init *V = RV.getValue()) {
                    "' in '" + R.getNameInitAsString() +
                    "' could not be fully resolved: " +
                    RV.getValue()->getAsString());
       }
     }
   }
 }
 
+/// Return an Init with a qualifier prefix referring
+/// to CurRec's name.
+static Init *QualifyName(Record &CurRec, MultiClass *CurMultiClass,
+                        Init *Name, StringRef Scoper) {
+  Init *NewName =
+      BinOpInit::getStrConcat(CurRec.getNameInit(), StringInit::get(Scoper));
+  NewName = BinOpInit::getStrConcat(NewName, Name);
+  if (CurMultiClass && Scoper != "::") {
+    Init *Prefix = BinOpInit::getStrConcat(CurMultiClass->Rec.getNameInit(),
+                                           StringInit::get("::"));
+    NewName = BinOpInit::getStrConcat(Prefix, NewName);
+  }
+
+  if (BinOpInit *BinOp = dyn_cast<BinOpInit>(NewName))
+    NewName = BinOp->Fold(&CurRec);
+  return NewName;
+}
+
 /// Return the qualified version of the implicit 'NAME' template argument.
 static Init *QualifiedNameOfImplicitName(Record &Rec,
                                          MultiClass *MC = nullptr) {
   return QualifyName(Rec, MC, StringInit::get("NAME"), MC ? "::" : ":");
 }
 
 static Init *QualifiedNameOfImplicitName(MultiClass *MC) {
   return QualifiedNameOfImplicitName(MC->Rec, MC);
bool TGParser::AddSubClass(Record *CurRec, SubClassReference &SubClass) {
 
   if (CurRec->isSubClassOf(SC))
     return Error(SubClass.RefRange.Start,
                  "Already subclass of '" + SC->getName() + "'!\n");
   CurRec->addSuperClass(SC, SubClass.RefRange);
   return false;
 }
 
+bool TGParser::AddSubClass(RecordsEntry &Entry, SubClassReference &SubClass) {
+  if (Entry.Rec)
+    return AddSubClass(Entry.Rec.get(), SubClass);
+
+  for (auto &E : Entry.Loop->Entries) {
+    if (AddSubClass(E, SubClass))
+      return true;
+  }
+
+  return false;
+}
+
 /// AddSubMultiClass - Add SubMultiClass as a subclass to
 /// CurMC, resolving its template args as SubMultiClass's
 /// template arguments.
 bool TGParser::AddSubMultiClass(MultiClass *CurMC,
                                 SubMultiClassReference &SubMultiClass) {
   MultiClass *SMC = SubMultiClass.MC;
 
   ArrayRef<Init *> SMCTArgs = SMC->Rec.getTemplateArgs();
   if (SMCTArgs.size() < SubMultiClass.TemplateArgs.size())
     return Error(SubMultiClass.RefRange.Start,
                  "More template args specified than expected");
 
-  SmallVector<std::pair<Init *, Init *>, 8> TemplateArgs;
+  SubstStack TemplateArgs;
   for (unsigned i = 0, e = SMCTArgs.size(); i != e; ++i) {
     if (i < SubMultiClass.TemplateArgs.size()) {
       TemplateArgs.emplace_back(SMCTArgs[i], SubMultiClass.TemplateArgs[i]);
     } else {
       Init *Default = SMC->Rec.getValue(SMCTArgs[i])->getValue();
       if (!Default->isComplete()) {
         return Error(SubMultiClass.RefRange.Start,
                      "value not specified for template argument #" + Twine(i) +
                          " (" + SMCTArgs[i]->getAsUnquotedString() +
                          ") of multiclass '" + SMC->Rec.getNameInitAsString() +
                          "'");
       }
       TemplateArgs.emplace_back(SMCTArgs[i], Default);
     }
   }
 
   TemplateArgs.emplace_back(
       QualifiedNameOfImplicitName(SMC),
       VarInit::get(QualifiedNameOfImplicitName(CurMC), StringRecTy::get()));
 
   // Add all of the defs in the subclass into the current multiclass.
-  for (const std::unique_ptr<Record> &Rec : SMC->DefPrototypes) {
-    auto NewDef = make_unique<Record>(*Rec);
-
-    MapResolver R(NewDef.get());
-    for (const auto &TArg : TemplateArgs)
-      R.set(TArg.first, TArg.second);
-    NewDef->resolveReferences(R);
-
-    CurMC->DefPrototypes.push_back(std::move(NewDef));
-  }
+  return resolve(SMC->Entries, TemplateArgs, false, &CurMC->Entries);
 
+/// Add a record or foreach loop to the current context (global record keeper,
+/// current inner-most foreach loop, or multiclass).
+bool TGParser::addEntry(RecordsEntry E) {
+  if (!Loops.empty()) {
+    Loops.back()->Entries.push_back(std::move(E));
     return false;
   }
 
-/// Add a record that results from 'def' or 'defm', after template arguments
-/// and the external let stack have been resolved.
-///
-/// Apply foreach loops, resolve internal variable references, and add to the
-/// current multi class or the global record keeper as appropriate.
-bool TGParser::addDef(std::unique_ptr<Record> Rec) {
-  IterSet IterVals;
+  if (E.Loop) {
+    SubstStack Stack;
+    return resolve(*E.Loop, Stack, CurMultiClass == nullptr,
+                   CurMultiClass ? &CurMultiClass->Entries : nullptr);
+  }
 
-  if (Loops.empty())
-    return addDefOne(std::move(Rec), IterVals);
+  if (CurMultiClass) {
+    CurMultiClass->Entries.push_back(std::move(E));
+    return false;
+  }
 
-  return addDefForeach(Rec.get(), IterVals);
+  return addDefOne(std::move(E.Rec));
 }
 
-/// Recursive helper function for addDef/addDefOne to resolve references to
-/// foreach variables.
-bool TGParser::addDefForeach(Record *Rec, IterSet &IterVals) {
-  if (IterVals.size() != Loops.size()) {
-    assert(IterVals.size() < Loops.size());
-    ForeachLoop &CurLoop = Loops[IterVals.size()];
-    ListInit *List = CurLoop.ListValue;
+/// Resolve the entries in \p Loop, going over inner loops recursively
+/// and making the given subsitutions of (name, value) pairs.
+///
+/// The resulting records are stored in \p Dest if non-null. Otherwise, they
+/// are added to the global record keeper.
+bool TGParser::resolve(const ForeachLoop &Loop, SubstStack &Substs,
+                       bool Final, std::vector<RecordsEntry> *Dest,
+                       SMLoc *Loc) {
+  MapResolver R;
+  for (const auto &S : Substs)
+    R.set(S.first, S.second);
+  Init *List = Loop.ListValue->resolveReferences(R);
+  auto LI = dyn_cast<ListInit>(List);
+  if (!LI) {
+    if (!Final) {
+      Dest->emplace_back(make_unique<ForeachLoop>(Loop.Loc, Loop.IterVar,
+                                                  List));
+      return resolve(Loop.Entries, Substs, Final, &Dest->back().Loop->Entries,
+                     Loc);
+    }
 
-    // Process each value.
-    for (unsigned i = 0; i < List->size(); ++i) {
-      IterVals.push_back(IterRecord(CurLoop.IterVar, List->getElement(i)));
-      if (addDefForeach(Rec, IterVals))
-        return true;
-      IterVals.pop_back();
-    }
-    return false;
+    PrintError(Loop.Loc, Twine("attempting to loop over '") +
+                              List->getAsString() + "', expected a list");
   }
 
-  // This is the bottom of the recursion. We have all of the iterator values
-  // for this point in the iteration space.  Instantiate a new record to
-  // reflect this combination of values.
-  auto IterRec = make_unique<Record>(*Rec);
-  return addDefOne(std::move(IterRec), IterVals);
+  bool Error = false;
+  for (unsigned i = 0; i < LI->size(); ++i) {
+    Substs.emplace_back(Loop.IterVar->getNameInit(), LI->getElement(i));
+    Error = resolve(Loop.Entries, Substs, Final, Dest);
+    Substs.pop_back();
+    if (Error)
+      break;
+  }
+  return Error;
 }
 
-/// After resolving foreach loops, add the record as a prototype to the
-/// current multiclass, or resolve fully and add to the record keeper.
-bool TGParser::addDefOne(std::unique_ptr<Record> Rec, IterSet &IterVals) {
-  MapResolver R(Rec.get());
-
-  for (IterRecord &IR : IterVals)
-    R.set(IR.IterVar->getNameInit(), IR.IterValue);
+/// Resolve the entries in \p Source, going over loops recursively and
+/// making the given substitutions of (name, value) pairs.
+///
+/// The resulting records are stored in \p Dest if non-null. Otherwise, they
+/// are added to the global record keeper.
+bool TGParser::resolve(const std::vector<RecordsEntry> &Source,
+                       SubstStack &Substs, bool Final,
+                       std::vector<RecordsEntry> *Dest, SMLoc *Loc) {
+  bool Error = false;
+  for (auto &E : Source) {
+    if (E.Loop) {
+      Error = resolve(*E.Loop, Substs, Final, Dest);
+    } else {
+      auto Rec = make_unique<Record>(*E.Rec);
+      if (Loc)
+        Rec->appendLoc(*Loc);
 
+      MapResolver R(Rec.get());
+      for (const auto &S : Substs)
+        R.set(S.first, S.second);
       Rec->resolveReferences(R);
 
-  if (CurMultiClass) {
-    if (!Rec->isAnonymous()) {
-      for (const auto &Proto : CurMultiClass->DefPrototypes) {
-        if (Proto->getNameInit() == Rec->getNameInit()) {
-          PrintError(Rec->getLoc(),
-                    Twine("def '") + Rec->getNameInitAsString() +
-                        "' already defined in this multiclass!");
-          PrintNote(Proto->getLoc(), "location of previous definition");
-          return true;
-        }
-      }
-    }
-    CurMultiClass->DefPrototypes.emplace_back(std::move(Rec));
-    return false;
-  }
+      if (Dest)
+        Dest->push_back(std::move(Rec));
+      else
+        Error = addDefOne(std::move(Rec));
+    if (Error)
+      break;
+  return Error;
 
+/// Resolve the record fully and add it to the record keeper.
+bool TGParser::addDefOne(std::unique_ptr<Record> Rec) {
   if (Record *Prev = Records.getDef(Rec->getNameInitAsString())) {
     if (!Rec->isAnonymous()) {
       PrintError(Rec->getLoc(),
                  "def already exists: " + Rec->getNameInitAsString());
       PrintNote(Prev->getLoc(), "location of previous definition");
       return true;
     }
     Rec->setName(Records.getNewAnonymousName());
if (TemplateRec->isTemplateArg(TemplateArgName)) {
       return VarInit::get(TemplateArgName, RV->getType());
     } else if (Name->getValue() == "NAME") {
       return VarInit::get(TemplateArgName, StringRecTy::get());
     }
   }
 
   // If this is in a foreach loop, make sure it's not a loop iterator
   for (const auto &L : Loops) {
-    VarInit *IterVar = dyn_cast<VarInit>(L.IterVar);
+    VarInit *IterVar = dyn_cast<VarInit>(L->IterVar);
     if (IterVar && IterVar->getNameInit() == Name)
       return IterVar;
   }
 
   if (Mode == ParseNameMode)
     return Name;
 
   if (Init *I = Records.getGlobal(Name->getValue()))
case tgtok::XForEach: { // Value ::= !foreach '(' Id ',' Value ',' Value ')'
 
     if (Lex.Lex() != tgtok::Id) { // eat the '('
       TokError("first argument of !foreach must be an identifier");
       return nullptr;
     }
 
     Init *LHS = StringInit::get(Lex.getCurStrVal());
 
-    if (CurRec->getValue(LHS)) {
+    if (CurRec && CurRec->getValue(LHS)) {
       TokError((Twine("iteration variable '") + LHS->getAsString() +
                 "' already defined")
                    .str());
       return nullptr;
     }
 
     if (Lex.Lex() != tgtok::comma) { // eat the id
       TokError("expected ',' in ternary operator");
if (ListRecTy *InListTy = dyn_cast<ListRecTy>(MHSt->getType())) {
         return nullptr;
       }
       IsDAG = true;
     } else {
       TokError("!foreach must have list or dag input");
       return nullptr;
     }
 
-    CurRec->addValue(RecordVal(LHS, InEltType, false));
-    Init *RHS = ParseValue(CurRec, OutEltType);
-    CurRec->removeValue(LHS);
+    std::unique_ptr<Record> ParseRecTmp;
+    Record *ParseRec = CurRec;
+    if (!ParseRec) {
+      ParseRecTmp = make_unique<Record>(".parse", ArrayRef<SMLoc>{}, Records);
+      ParseRec = ParseRecTmp.get();
+    }
+
+    ParseRec->addValue(RecordVal(LHS, InEltType, false));
+    Init *RHS = ParseValue(ParseRec, OutEltType);
+    ParseRec->removeValue(LHS);
     if (!RHS)
       return nullptr;
 
     if (Lex.getCode() != tgtok::r_paren) {
       TokError("expected ')' in binary operator");
       return nullptr;
     }
     Lex.Lex();  // eat the ')'
 
case tgtok::XFoldl: {
     }
 
     if (Lex.Lex() != tgtok::Id) { // eat the ','
       TokError("third argument of !foldl must be an identifier");
       return nullptr;
     }
 
     Init *A = StringInit::get(Lex.getCurStrVal());
-    if (CurRec->getValue(A)) {
+    if (CurRec && CurRec->getValue(A)) {
       TokError((Twine("left !foldl variable '") + A->getAsString() +
                 "' already defined")
                    .str());
       return nullptr;
     }
 
     if (Lex.Lex() != tgtok::comma) { // eat the id
       TokError("expected ',' in !foldl");
       return nullptr;
     }
 
     if (Lex.Lex() != tgtok::Id) { // eat the ','
       TokError("fourth argument of !foldl must be an identifier");
       return nullptr;
     }
 
     Init *B = StringInit::get(Lex.getCurStrVal());
-    if (CurRec->getValue(B)) {
+    if (CurRec && CurRec->getValue(B)) {
       TokError((Twine("right !foldl variable '") + B->getAsString() +
                 "' already defined")
                    .str());
       return nullptr;
     }
 
     if (Lex.Lex() != tgtok::comma) { // eat the id
       TokError("expected ',' in !foldl");
       return nullptr;
     }
     Lex.Lex(); // eat the ','
 
-    CurRec->addValue(RecordVal(A, Start->getType(), false));
-    CurRec->addValue(RecordVal(B, ListType->getElementType(), false));
-    Init *ExprUntyped = ParseValue(CurRec);
-    CurRec->removeValue(A);
-    CurRec->removeValue(B);
+    std::unique_ptr<Record> ParseRecTmp;
+    Record *ParseRec = CurRec;
+    if (!ParseRec) {
+      ParseRecTmp = make_unique<Record>(".parse", ArrayRef<SMLoc>{}, Records);
+      ParseRec = ParseRecTmp.get();
+    }
+
+    ParseRec->addValue(RecordVal(A, Start->getType(), false));
+    ParseRec->addValue(RecordVal(B, ListType->getElementType(), false));
+    Init *ExprUntyped = ParseValue(ParseRec);
+    ParseRec->removeValue(A);
+    ParseRec->removeValue(B);
     if (!ExprUntyped)
       return nullptr;
 
     TypedInit *Expr = dyn_cast<TypedInit>(ExprUntyped);
     if (!Expr) {
       TokError("could not get type of !foldl expression");
       return nullptr;
     }
 

 /// ParseForeachDeclaration - Read a foreach declaration, returning
 /// the name of the declared object or a NULL Init on error.  Return
 /// the name of the parsed initializer list through ForeachListName.
 ///
 ///  ForeachDeclaration ::= ID '=' '{' RangeList '}'
 ///  ForeachDeclaration ::= ID '=' RangePiece
 ///  ForeachDeclaration ::= ID '=' Value
 ///
-VarInit *TGParser::ParseForeachDeclaration(ListInit *&ForeachListValue) {
+VarInit *TGParser::ParseForeachDeclaration(Init *&ForeachListValue) {
   if (Lex.getCode() != tgtok::Id) {
     TokError("Expected identifier in foreach declaration");
     return nullptr;
   }
 
   Init *DeclName = StringInit::get(Lex.getCurStrVal());
   Lex.Lex();
 
case tgtok::l_brace: { // '{' RangeList '}'
     }
     Lex.Lex();
     break;
   }
 
   default: {
     SMLoc ValueLoc = Lex.getLoc();
     Init *I = ParseValue(nullptr);
-    if (!isa<ListInit>(I)) {
+    TypedInit *TI = dyn_cast<TypedInit>(I);
+    if (!TI || !isa<ListRecTy>(TI->getType())) {
       std::string Type;
-      if (TypedInit *TI = dyn_cast<TypedInit>(I))
+      if (TI)
         Type = (Twine("' of type '") + TI->getType()->getAsString()).str();
       Error(ValueLoc, "expected a list, got '" + I->getAsString() + Type + "'");
       if (CurMultiClass)
         PrintNote({}, "references to multiclass template arguments cannot be "
                       "resolved at this time");
       return nullptr;
     }
-    ForeachListValue = dyn_cast<ListInit>(I);
-    IterType = ForeachListValue->getElementType();
+    ForeachListValue = I;
+    IterType = cast<ListRecTy>(TI->getType())->getElementType();
     break;
   }
   }
 
   if (!Ranges.empty()) {
     assert(!IterType && "Type already initialized?");
     IterType = IntRecTy::get();
     std::vector<Init*> Values;

 bool TGParser::ApplyLetStack(Record *CurRec) {
   for (SmallVectorImpl<LetRecord> &LetInfo : LetStack)
     for (LetRecord &LR : LetInfo)
       if (SetValue(CurRec, LR.Loc, LR.Name, LR.Bits, LR.Value))
         return true;
   return false;
 }
 
+bool TGParser::ApplyLetStack(RecordsEntry &Entry) {
+  if (Entry.Rec)
+    return ApplyLetStack(Entry.Rec.get());
+
+  for (auto &E : Entry.Loop->Entries) {
+    if (ApplyLetStack(E))
+      return true;
+  }
+
+  return false;
+}
+
 /// ParseObjectBody - Parse the body of a def or class.  This consists of an
 /// optional ClassList followed by a Body.  CurRec is the current def or class
 /// that is being parsed.
 ///
 ///   ObjectBody      ::= BaseClassList Body
 ///   BaseClassList   ::= /*empty*/
 ///   BaseClassList   ::= ':' BaseClassListNE
 ///   BaseClassListNE ::= SubClassRef (',' SubClassRef)*
if (isa<UnsetInit>(Name))
     CurRec = make_unique<Record>(Records.getNewAnonymousName(), DefLoc, Records,
                                  /*Anonymous=*/true);
   else
     CurRec = make_unique<Record>(Name, DefLoc, Records);
 
   if (ParseObjectBody(CurRec.get()))
     return true;
 
-  return addDef(std::move(CurRec));
+  return addEntry(std::move(CurRec));
 }
 
 /// ParseDefset - Parse a defset statement.
 ///
 ///   Defset ::= DEFSET Type Id '=' '{' ObjectList '}'
 ///
 bool TGParser::ParseDefset() {
   assert(Lex.getCode() == tgtok::Defset);

 
 /// ParseForeach - Parse a for statement.  Return the record corresponding
 /// to it.  This returns true on error.
 ///
 ///   Foreach ::= FOREACH Declaration IN '{ ObjectList '}'
 ///   Foreach ::= FOREACH Declaration IN Object
 ///
 bool TGParser::ParseForeach(MultiClass *CurMultiClass) {
+  SMLoc Loc = Lex.getLoc();
   assert(Lex.getCode() == tgtok::Foreach && "Unknown tok");
   Lex.Lex();  // Eat the 'for' token.
 
   // Make a temporary object to record items associated with the for
   // loop.
-  ListInit *ListValue = nullptr;
+  Init *ListValue = nullptr;
   VarInit *IterName = ParseForeachDeclaration(ListValue);
   if (!IterName)
     return TokError("expected declaration in for");
 
   if (Lex.getCode() != tgtok::In)
     return TokError("Unknown tok");
   Lex.Lex();  // Eat the in
 
   // Create a loop object and remember it.
-  Loops.push_back(ForeachLoop(IterName, ListValue));
+  Loops.push_back(llvm::make_unique<ForeachLoop>(Loc, IterName, ListValue));
 
   if (Lex.getCode() != tgtok::l_brace) {
     // FOREACH Declaration IN Object
     if (ParseObject(CurMultiClass))
       return true;
   } else {
     SMLoc BraceLoc = Lex.getLoc();
     // Otherwise, this is a group foreach.
     Lex.Lex();  // eat the '{'.
 
     // Parse the object list.
     if (ParseObjectList(CurMultiClass))
       return true;
 
     if (Lex.getCode() != tgtok::r_brace) {
       TokError("expected '}' at end of foreach command");
       return Error(BraceLoc, "to match this '{'");
     }
     Lex.Lex();  // Eat the }
   }
 
-  // We've processed everything in this loop.
+  // Resolve the loop or store it for later resolution.
+  std::unique_ptr<ForeachLoop> Loop = std::move(Loops.back());
   Loops.pop_back();
 
-  return false;
+  return addEntry(std::move(Loop));
 }
 
 /// ParseClass - Parse a tblgen class definition.
 ///
 ///   ClassInst ::= CLASS ID TemplateArgList? ObjectBody
 ///
 bool TGParser::ParseClass() {
   assert(Lex.getCode() == tgtok::Class && "Unexpected token!");
if (CurMultiClass)
                        StringRecTy::get()),
           DefmName);
   }
 
   if (Lex.getCode() != tgtok::colon)
     return TokError("expected ':' after defm identifier");
 
   // Keep track of the new generated record definitions.
-  SmallVector<std::unique_ptr<Record>, 8> NewRecDefs;
+  std::vector<RecordsEntry> NewEntries;
 
   // This record also inherits from a regular class (non-multiclass)?
   bool InheritFromClass = false;
 
   // eat the colon.
   Lex.Lex();
 
   SMLoc SubClassLoc = Lex.getLoc();
while (true) {
     ArrayRef<Init*> TemplateVals = Ref.TemplateArgs;
 
     // Verify that the correct number of template arguments were specified.
     ArrayRef<Init *> TArgs = MC->Rec.getTemplateArgs();
     if (TArgs.size() < TemplateVals.size())
       return Error(SubClassLoc,
                    "more template args specified than multiclass expects");
 
-    SmallVector<std::pair<Init *, Init *>, 8> TemplateArgs;
+    SubstStack Substs;
     for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
       if (i < TemplateVals.size()) {
-        TemplateArgs.emplace_back(TArgs[i], TemplateVals[i]);
+        Substs.emplace_back(TArgs[i], TemplateVals[i]);
       } else {
         Init *Default = MC->Rec.getValue(TArgs[i])->getValue();
         if (!Default->isComplete()) {
           return Error(SubClassLoc,
                        "value not specified for template argument #" +
                            Twine(i) + " (" + TArgs[i]->getAsUnquotedString() +
                            ") of multiclass '" + MC->Rec.getNameInitAsString() +
                            "'");
         }
-        TemplateArgs.emplace_back(TArgs[i], Default);
+        Substs.emplace_back(TArgs[i], Default);
       }
     }
 
-    TemplateArgs.emplace_back(QualifiedNameOfImplicitName(MC), DefmName);
+    Substs.emplace_back(QualifiedNameOfImplicitName(MC), DefmName);
 
-    // Loop over all the def's in the multiclass, instantiating each one.
-    for (const std::unique_ptr<Record> &DefProto : MC->DefPrototypes) {
-      auto CurRec = make_unique<Record>(*DefProto);
-      CurRec->appendLoc(SubClassLoc);
-
-      MapResolver R(CurRec.get());
-      for (const auto &TArg : TemplateArgs)
-        R.set(TArg.first, TArg.second);
-      CurRec->resolveReferences(R);
-
-      NewRecDefs.emplace_back(std::move(CurRec));
-    }
+    if (resolve(MC->Entries, Substs, CurMultiClass == nullptr, &NewEntries,
+                &SubClassLoc))
+      return true;
 
     if (Lex.getCode() != tgtok::comma) break;
     Lex.Lex(); // eat ','.
 
     if (Lex.getCode() != tgtok::Id)
       return TokError("expected identifier");
 
     SubClassLoc = Lex.getLoc();
if (InheritFromClass) {
     // regular 'def' and inherit all record values.
     SubClassReference SubClass = ParseSubClassReference(nullptr, false);
     while (true) {
       // Check for error.
       if (!SubClass.Rec) return true;
 
       // Get the expanded definition prototypes and teach them about
       // the record values the current class to inherit has
-      for (const auto &CurRec : NewRecDefs) {
+      for (auto &E : NewEntries) {
         // Add it.
-        if (AddSubClass(CurRec.get(), SubClass))
+        if (AddSubClass(E, SubClass))
           return true;
       }
 
       if (Lex.getCode() != tgtok::comma) break;
       Lex.Lex(); // eat ','.
       SubClass = ParseSubClassReference(nullptr, false);
     }
   }
 
-  for (auto &CurRec : NewRecDefs) {
-    if (ApplyLetStack(CurRec.get()))
+  for (auto &E : NewEntries) {
+    if (ApplyLetStack(E))
       return true;
 
-    addDef(std::move(CurRec));
+    addEntry(std::move(E));
   }
 
   if (Lex.getCode() != tgtok::semi)
     return TokError("expected ';' at end of defm");
   Lex.Lex();
 
   return false;
 }
bool TGParser::ParseFile() {
   if (ParseObjectList()) return true;
 
   // If we have unread input at the end of the file, report it.
   if (Lex.getCode() == tgtok::Eof)
     return false;
 
   return TokError("Unexpected input at top level");
 }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void RecordsEntry::dump() const {
+  if (Loop)
+    Loop->dump();
+  if (Rec)
+    Rec->dump();
+}
+
+LLVM_DUMP_METHOD void ForeachLoop::dump() const {
+  errs() << "foreach " << IterVar->getAsString() << " = "
+         << ListValue->getAsString() << " in {\n";
+
+  for (const auto &E : Entries)
+    E.dump();
+
+  errs() << "}\n";
+}
+
+LLVM_DUMP_METHOD void MultiClass::dump() const {
+  errs() << "Record:\n";
+  Rec.dump();
+
+  errs() << "Defs:\n";
+  for (const auto &E : Entries)
+    E.dump();
+}
+#endif

test/TableGen/NestedForeach.td

foreach R = [2, 3, 4] in {
     foreach M = ["D", "P", "Q"] in {
       foreach P = [0, 2, 4] in {
         def S#R#M#P : Droid<S, R, M, P>;
       }
     }
   }
 }
 
+foreach i = [0, 1] in
+foreach j = !foreach(x, [0, 2], !add(i, x)) in
+def Z#i#_#j;
+
 // CHECK: def C2D0
 // CHECK: def C2D2
 // CHECK: def C2D4
 // CHECK: def C2P0
 // CHECK: def C2P2
 // CHECK: def C2P4
 // CHECK: def C2Q0
 // CHECK: def C2Q2

 // CHECK: def R4D2
 // CHECK: def R4D4
 // CHECK: def R4P0
 // CHECK: def R4P2
 // CHECK: def R4P4
 // CHECK: def R4Q0
 // CHECK: def R4Q2
 // CHECK: def R4Q4
+
+// CHECK: def Z0_0
+// CHECK: def Z0_2
+// CHECK: def Z1_1
+// CHECK: def Z1_3

test/TableGen/foreach-multiclass.td

 // RUN: llvm-tblgen %s | FileCheck %s
 // XFAIL: vg_leak
 
 // CHECK: --- Defs ---
 
 // CHECK: def A00 {
 // CHECK:   int sum = 7;
 // CHECK: }
 
 // CHECK: def A01 {
 // CHECK:   int sum = 8;
 // CHECK: }
 
+// CHECK-NOT: def B0
+
+// CHECK: def B12 {
+// CHECK:   int val = 9;
+// CHECK: }
+
+// CHECK: def B2-1 {
+// CHECK:   int val = 6;
+// CHECK: }
+
+// CHECK: def B20 {
+// CHECK:   int val = 7;
+// CHECK: }
+
+// CHECK: def B24 {
+// CHECK:   int val = 11;
+// CHECK: }
+
+// CHECK: def C04
+// CHECK: def C05
+
+// CHECK: def D0A
+// CHECK-NOT: def D0B
+// CHECK: def D1A
+// CHECK: def D1B
+
+// CHECK: def E01
+// CHECK: def E02
+// CHECK-NOT: def E0C
+
+// CHECK: def E18
+// CHECK: def E19
+// CHECK: def E1C33
+// CHECK: def E1C34
+// CHECK: def E1C55
+// CHECK: def E1C56
+
+// CHECK-NOT: def F0
+// CHECK-NOT: def F1
+// CHECK-NOT: def F2_0_0
+// CHECK:     def F2_1_0
+// CHECK-NOT: def F2_1_2
+// CHECK:     def F2_2_0
+// CHECK:     def F2_2_1
+// CHECK-NOT: def F2_2_2
+
 multiclass A<int x> {
-  // Allow foreach in multiclass as long as the list does not depend on
-  // template args.
   foreach i = [0, 1] in {
     def NAME#i {
       int sum = !add(x, i);
     }
   }
 }
 
 defm A0 : A<7>;
+
+multiclass B<int x, list<int> lst> {
+  foreach i = lst in {
+    def NAME#i {
+      int val = !add(x, i);
+    }
+  }
+}
+
+defm B0 : B<7, []>;
+defm B1 : B<7, [2]>;
+defm B2 : B<7, [-1, 0, 4]>;
+
+multiclass C<int x> {
+  foreach i = [x, !add(x, 1)] in {
+    def NAME#i;
+  }
+}
+
+defm C0 : C<4>;
+
+multiclass D<bit b> {
+  def A;
+
+  foreach _ = !if(b, [0], []<int>) in
+  def B;
+}
+
+defm D0 : D<0>;
+defm D1 : D<1>;
+
+multiclass E<list<int> lst, int x>
+  : C<x> {
+  foreach i = lst in
+  defm C#i : C<i>;
+}
+
+defm E0 : E<[], 1>;
+defm E1 : E<[3, 5], 8>;
+
+multiclass F<list<int> lst> {
+  foreach i = lst in
+  foreach j = !foldl([]<int>, lst, lhs, x,
+                     !if(!lt(x, i), !listconcat(lhs, [x]), lhs)) in
+  def _#i#_#j;
+}
+
+defm F0 : F<[]>;
+defm F1 : F<[0]>;
+defm F2 : F<[0, 1, 2]>;