Index: llvm/trunk/lib/TableGen/Record.cpp
===================================================================
--- llvm/trunk/lib/TableGen/Record.cpp
+++ llvm/trunk/lib/TableGen/Record.cpp
@@ -919,26 +919,22 @@
   ProfileTernOpInit(ID, getOpcode(), getLHS(), getMHS(), getRHS(), getType());
 }
 
-static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
-                           Record *CurRec, MultiClass *CurMultiClass);
+static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, Record *CurRec,
+                           MultiClass *CurMultiClass);
 
+// Evaluates operation RHSo after replacing all operands matching LHS with Arg.
 static Init *EvaluateOperation(OpInit *RHSo, Init *LHS, Init *Arg,
-                               RecTy *Type, Record *CurRec,
-                               MultiClass *CurMultiClass) {
-  // If this is a dag, recurse
-  if (auto *TArg = dyn_cast<TypedInit>(Arg))
-    if (isa<DagRecTy>(TArg->getType()))
-      return ForeachHelper(LHS, Arg, RHSo, Type, CurRec, CurMultiClass);
+                               Record *CurRec, MultiClass *CurMultiClass) {
 
   SmallVector<Init *, 8> NewOperands;
   NewOperands.reserve(RHSo->getNumOperands());
   for (unsigned i = 0, e = RHSo->getNumOperands(); i < e; ++i) {
     if (auto *RHSoo = dyn_cast<OpInit>(RHSo->getOperand(i))) {
-      if (Init *Result = EvaluateOperation(RHSoo, LHS, Arg,
-                                           Type, CurRec, CurMultiClass))
+      if (Init *Result =
+              EvaluateOperation(RHSoo, LHS, Arg, CurRec, CurMultiClass))
         NewOperands.push_back(Result);
       else
-        NewOperands.push_back(Arg);
+        NewOperands.push_back(RHSoo);
     } else if (LHS->getAsString() == RHSo->getOperand(i)->getAsString()) {
       NewOperands.push_back(Arg);
     } else {
@@ -952,8 +948,9 @@
   return (NewVal != NewOp) ? NewVal : nullptr;
 }
 
-static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
-                           Record *CurRec, MultiClass *CurMultiClass) {
+// Applies RHS to all elements of MHS, using LHS as a temp variable.
+static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, Record *CurRec,
+                           MultiClass *CurMultiClass) {
   OpInit *RHSo = dyn_cast<OpInit>(RHS);
 
   if (!RHSo)
@@ -965,21 +962,23 @@
     PrintFatalError(CurRec->getLoc(), "!foreach requires typed variable\n");
 
   DagInit *MHSd = dyn_cast<DagInit>(MHS);
-  if (MHSd && isa<DagRecTy>(Type)) {
+  if (MHSd) {
     Init *Val = MHSd->getOperator();
-    if (Init *Result = EvaluateOperation(RHSo, LHS, Val,
-                                         Type, CurRec, CurMultiClass))
+    if (Init *Result = EvaluateOperation(RHSo, LHS, Val, CurRec, CurMultiClass))
       Val = Result;
 
-    SmallVector<std::pair<Init *, StringInit*>, 8> args;
+    SmallVector<std::pair<Init *, StringInit *>, 8> args;
     for (unsigned int i = 0; i < MHSd->getNumArgs(); ++i) {
       Init *Arg = MHSd->getArg(i);
       StringInit *ArgName = MHSd->getArgName(i);
-
-      // Process args
-      if (Init *Result = EvaluateOperation(RHSo, LHS, Arg, Type,
-                                           CurRec, CurMultiClass))
+      // If this is a dag, recurse
+      if (isa<DagInit>(Arg)) {
+        if (Init *Result = ForeachHelper(LHS, Arg, RHSo, CurRec, CurMultiClass))
+          Arg = Result;
+      } else if (Init *Result =
+                     EvaluateOperation(RHSo, LHS, Arg, CurRec, CurMultiClass)) {
         Arg = Result;
+      }
 
       // TODO: Process arg names
       args.push_back(std::make_pair(Arg, ArgName));
@@ -989,25 +988,12 @@
   }
 
   ListInit *MHSl = dyn_cast<ListInit>(MHS);
-  if (MHSl && isa<ListRecTy>(Type)) {
-    SmallVector<Init *, 8> NewOperands;
+  if (MHSl) {
     SmallVector<Init *, 8> NewList(MHSl->begin(), MHSl->end());
-
-    for (Init *&Item : NewList) {
-      NewOperands.clear();
-      for(unsigned i = 0; i < RHSo->getNumOperands(); ++i) {
-        // First, replace the foreach variable with the list item
-        if (LHS->getAsString() == RHSo->getOperand(i)->getAsString())
-          NewOperands.push_back(Item);
-        else
-          NewOperands.push_back(RHSo->getOperand(i));
-      }
-
-      // Now run the operator and use its result as the new list item
-      const OpInit *NewOp = RHSo->clone(NewOperands);
-      Init *NewItem = NewOp->Fold(CurRec, CurMultiClass);
-      if (NewItem != NewOp)
-        Item = NewItem;
+    for (Init *&Arg : NewList) {
+      if (Init *Result =
+              EvaluateOperation(RHSo, LHS, Arg, CurRec, CurMultiClass))
+        Arg = Result;
     }
     return ListInit::get(NewList, MHSl->getType());
   }
@@ -1060,8 +1046,7 @@
   }
 
   case FOREACH: {
-    if (Init *Result = ForeachHelper(LHS, MHS, RHS, getType(),
-                                     CurRec, CurMultiClass))
+    if (Init *Result = ForeachHelper(LHS, MHS, RHS, CurRec, CurMultiClass))
       return Result;
     break;
   }
Index: llvm/trunk/test/TableGen/foreach-eval.td
===================================================================
--- llvm/trunk/test/TableGen/foreach-eval.td
+++ llvm/trunk/test/TableGen/foreach-eval.td
@@ -0,0 +1,72 @@
+// RUN: llvm-tblgen %s | FileCheck %s
+// XFAIL: vg_leak
+
+// Tests evaluation of !foreach operator.
+
+def d0;
+def d1;
+def d2;
+def d3;
+def d4;
+
+class D<dag d> {
+  int tmp;
+  dag r1 = !foreach(tmp, d, !subst(d1, d0, !subst(d2, d0,
+                                           !subst(d3, d0,
+                                           !subst(d4, d0, tmp)))));
+  dag tmp2;
+  list<dag> dl = [d];
+  list<dag> r2 = !foreach(tmp2, dl,
+                          !foreach(tmp, tmp2, !subst(d1, d0,
+                                              !subst(d2, d0,
+                                              !subst(d3, d0,
+                                              !subst(d4, d0, tmp))))));
+}
+
+// CHECK-LABEL: def d
+// CHECK: dag r1 = (d0 d0, d0, d0, d0);
+// CHECK: list<dag> r2 = [(d0 d0, d0, d0, d0)];
+def d : D <(d0 d1, d2, d3, d4)>;
+
+class I<list<int> i> {
+  int tmp;
+  list<int> r1 = !foreach(tmp, i, !add(3, !add(4, tmp)));
+
+  list<int> tmp2;
+  list<list<int>> li = [i];
+  list<list<int>> r2 = !foreach(tmp2, li,
+                                !foreach(tmp, tmp2, !add(3, !add(4, tmp))));
+}
+
+// CHECK-LABEL: def i
+// CHECK: list<int> r1 = [8, 9, 10];
+// CHECK: list<list<int>> r2 = [{{[[]}}8, 9, 10]];
+def i : I<[1,2,3]>;
+
+class Tmp {
+  dag t0;
+  int t1;
+}
+def tmp: Tmp;
+
+class J0<list<dag> pattern> {
+  list<dag> Pattern = pattern;
+}
+class J1<dag pattern>
+      : J0<[!foreach(tmp.t1, pattern, !subst(d1, d0,
+                                      !subst(d2, d0,
+                                      !subst(d3, d0,
+                                      !subst(d4, d0, tmp.t1)))))]>;
+class J2<list<dag> patterns>
+      : J0<!foreach(tmp.t0, patterns,
+                    !foreach(tmp.t1, tmp.t0, !subst(d1, d0,
+                                             !subst(d2, d0,
+                                             !subst(d3, d0,
+                                             !subst(d4, d0, tmp.t1))))))>;
+// CHECK-LABEL: def j1
+// CHECK: list<dag> Pattern = [(d0 d0:$dst, (d0 d0:$src1))];
+def j1 : J1< (d1 d2:$dst, (d3 d4:$src1))>;
+// CHECK-LABEL: def j2
+// CHECK: list<dag> Pattern = [(d0 d0:$dst, (d0 d0:$src1))];
+def j2 : J2< [(d1 d2:$dst, (d3 d4:$src1))]>;
+