[TableGen] Avoid leaking TreePatternNodes by using shared_ptr.

[fhahn]

Summary

By using std::shared_ptr for TreePatternNode, we can avoid leaking them.
Together with the other patches in linked to this one, ASAN shipped with
GCC8 is happy for TableGen.

I tried to keep the number of times we copy shared_ptrs around small,
but I probably missed a few places where there is no need to copy them.

[dsanders]

Generally LGTM. I have a couple questions on this one though

utils/TableGen/CodeGenDAGPatterns.h

923

Given that we build with -fno-exceptions, is the noexcept really needed?

939–942

Does this object really own Pattern? It looks like it probably does but it's a raw pointer. If it really does own it we should be using unique_ptr

[fhahn]

Thanks Daniel! I removed the changes related to leaking DAGInstruction::Pattern. I will add a separate patch for that, it should be easier to review that way.

[fhahn]

utils/TableGen/CodeGenDAGPatterns.h

939–942

Ah that change is unrelated to the shared_ptr changes. I will try to move it out, it should be clearer then.

[dsanders]

LGTM

[dblaikie]

Great to see these sort of improvements to memory ownership!

Just a few general pointers (I went through and gave specific feedback in some instances, but it was a bit repetitive):

• Some std::move opportunities
• Some opportunities to avoid copying smart pointers (avoid refcount increment/decrement)
• Some places where APIs could be change to take Nodes by ref or const ref (rather than pointer or smart pointer) that would simplify the callers (& incidentally make the callers identical between smart and plain pointers - "*X" in both cases)

Also, I think it may be better not to typedef the smart pointer type - it looks like it makes it easier to accidentally copy them when that may not be desirable. I'd keep it as an explicit feature of the type name (rather than behind a typedef) & try to reduce the number of places that need to name the shared_ptr type to only those that are really handling ownership transfer, etc.

llvm/trunk/utils/TableGen/CodeGenDAGPatterns.cpp

2522 ↗

(On Diff #149197)

Maybe ComputeNamedNodes could take by Node reference instead of by Node pointer? (then the call site would be "ComputeNamedNodes(*Tree);" - so it'd match/work fine with either plain pointers or smart pointers)

2674–2676 ↗

(On Diff #149197)

auto & std::move? Or maybe just inline it all together:

Children.insert(Children.begin(), std::make_shared<TreePatternNode>(IntInit::get(IID), 1));

2681 ↗

(On Diff #149197)

Node reference (eg: "auto &Child = *Children[i];") maybe? Doesn't look like this needs ownership?

2700 ↗

(On Diff #149197)

auto, maybe

2737 ↗

(On Diff #149197)

std::move?

3096 ↗

(On Diff #149197)

If this API continues to take Pat by value, this should std::move here - though if this move only happens in a relative minority of calls, perhaps it should take the parameter by const ref instead of incurring the ref count handling for every call?

3448 ↗

(On Diff #149197)

Node reference here, doesn't look like this needs any ownership?

3488 ↗

(On Diff #149197)

std::move? (after moving this down past the one other use of RNode)

3529 ↗

(On Diff #149197)

Reference rather than copy here? (& probably a reference to the node rather than a reference to the shared_ptr of node)

3550 ↗

(On Diff #149197)

maybe std::move here (though it'd mean needing to call getNumTypes above for the expression below)

3555 ↗

(On Diff #149197)

std::move

3562 ↗

(On Diff #149197)

Probably 'auto' here.

3986 ↗

(On Diff #149197)

Maybe another API that could take a node by reference instead of pointer?

4007 ↗

(On Diff #149197)

Does this need ownership (is Result being changed in such a way that it might cease owning the tree pattern node)? Doesn't look like it.

4079 ↗

(On Diff #149197)

std::move on NewSrc and NewDst?

4085 ↗

(On Diff #149197)

Do these need to be smart pointers? Looks like they don't need ownership between where they're set & where they're passed to collectModes?

4097 ↗

(On Diff #149197)

Other APIs that could be cleaned up with reference rather than pointer parameters, perhaps.

4209 ↗

(On Diff #149197)

could use "auto" here - since you've named the type on the RHS anyway.

4227 ↗

(On Diff #149197)

Whenever I'm moving to a smart pointer type I use cases like this as an opportunity to tidy up the code - for example this isIsomorphicTo function could take a const TreePatternNode& - then the callers could use op* to dereference - and then the code would be the same between smart and shared pointers (rather than having to move from X to X.get() it'd just be *X in both cases).

I don't remember/can't find right now if we have a dereferencing range adapter - which would be handy to use here if the API was changed as suggested.

llvm/trunk/utils/TableGen/CodeGenDAGPatterns.h

816 ↗

(On Diff #149197)

Missing std::move:

Trees[i] = Tree;

should be:

Trees[i] = std::move(Tree);

817 ↗

(On Diff #149197)

This should probably be const ref - so that users of this that don't need to take ownership don't cause a refcount increment/decrement caused by making the copy.

[fhahn]

Thanks you very much for looking at this carefully! I thought it was safer to start with a smaller diff, but that it's in now and I'll prepare a patch with your suggestions.

utils/TableGen/CodeGenDAGPatterns.h

 class ListInit;
 class DagInit;
 class SDNodeInfo;
 class TreePattern;
 class TreePatternNode;
 class CodeGenDAGPatterns;
 class ComplexPattern;
 
+/// Shared pointer for TreePatternNode.
+using TreePatternNodePtr = std::shared_ptr<TreePatternNode>;
+
 /// This represents a set of MVTs. Since the underlying type for the MVT
 /// is uint8_t, there are at most 256 values. To reduce the number of memory
 /// allocations and deallocations, represent the set as a sequence of bits.
 /// To reduce the allocations even further, make MachineValueTypeSet own
 /// the storage and use std::array as the bit container.
 struct MachineValueTypeSet {
   static_assert(std::is_same<std::underlying_type<MVT::SimpleValueType>::type,
                              uint8_t>::value,
private:
   std::string getImmCode() const;
   bool immCodeUsesAPInt() const;
   bool immCodeUsesAPFloat() const;
 
   bool isPredefinedPredicateEqualTo(StringRef Field, bool Value) const;
 };
 
 
-/// FIXME: TreePatternNode's can be shared in some cases (due to dag-shaped
-/// patterns), and as such should be ref counted.  We currently just leak all
-/// TreePatternNode objects!
 class TreePatternNode {
   /// The type of each node result.  Before and during type inference, each
   /// result may be a set of possible types.  After (successful) type inference,
   /// each is a single concrete type.
   std::vector<TypeSetByHwMode> Types;
 
   /// Operator - The Record for the operator if this is an interior node (not
   /// a leaf).
class TreePatternNode {
   /// PredicateFns - The predicate functions to execute on this node to check
   /// for a match.  If this list is empty, no predicate is involved.
   std::vector<TreePredicateFn> PredicateFns;
 
   /// TransformFn - The transformation function to execute on this node before
   /// it can be substituted into the resulting instruction on a pattern match.
   Record *TransformFn;
 
-  std::vector<TreePatternNode*> Children;
+  std::vector<TreePatternNodePtr> Children;
+
 public:
-  TreePatternNode(Record *Op, const std::vector<TreePatternNode*> &Ch,
+  TreePatternNode(Record *Op, std::vector<TreePatternNodePtr> &Ch,
                   unsigned NumResults)
       : Operator(Op), Val(nullptr), TransformFn(nullptr), Children(Ch) {
     Types.resize(NumResults);
   }
   TreePatternNode(Init *val, unsigned NumResults)    // leaf ctor
     : Operator(nullptr), Val(val), TransformFn(nullptr) {
     Types.resize(NumResults);
   }
-  ~TreePatternNode();
 
   bool hasName() const { return !Name.empty(); }
   const std::string &getName() const { return Name; }
   void setName(StringRef N) { Name.assign(N.begin(), N.end()); }
 
   bool isLeaf() const { return Val != nullptr; }
 
   // Type accessors.
public:
   bool isTypeCompletelyUnknown(unsigned ResNo, TreePattern &TP) const {
     return Types[ResNo].empty();
   }
 
   Init *getLeafValue() const { assert(isLeaf()); return Val; }
   Record *getOperator() const { assert(!isLeaf()); return Operator; }
 
   unsigned getNumChildren() const { return Children.size(); }
-  TreePatternNode *getChild(unsigned N) const { return Children[N]; }
-  void setChild(unsigned i, TreePatternNode *N) {
-    Children[i] = N;
+  TreePatternNode *getChild(unsigned N) const { return Children[N].get(); }
+  const TreePatternNodePtr &getChildShared(unsigned N) const {
+    return Children[N];
   }
+  void setChild(unsigned i, TreePatternNodePtr N) { Children[i] = N; }
 
   /// hasChild - Return true if N is any of our children.
   bool hasChild(const TreePatternNode *N) const {
     for (unsigned i = 0, e = Children.size(); i != e; ++i)
-      if (Children[i] == N) return true;
+      if (Children[i].get() == N)
+        return true;
     return false;
   }
 
   bool hasProperTypeByHwMode() const;
   bool hasPossibleType() const;
   bool setDefaultMode(unsigned Mode);
 
   bool hasAnyPredicate() const { return !PredicateFns.empty(); }
public:
 
   void print(raw_ostream &OS) const;
   void dump() const;
 
 public:   // Higher level manipulation routines.
 
   /// clone - Return a new copy of this tree.
   ///
-  TreePatternNode *clone() const;
+  TreePatternNodePtr clone() const;
 
   /// RemoveAllTypes - Recursively strip all the types of this tree.
   void RemoveAllTypes();
 
   /// isIsomorphicTo - Return true if this node is recursively isomorphic to
   /// the specified node.  For this comparison, all of the state of the node
   /// is considered, except for the assigned name.  Nodes with differing names
   /// that are otherwise identical are considered isomorphic.
   bool isIsomorphicTo(const TreePatternNode *N,
                       const MultipleUseVarSet &DepVars) const;
 
   /// SubstituteFormalArguments - Replace the formal arguments in this tree
   /// with actual values specified by ArgMap.
-  void SubstituteFormalArguments(std::map<std::string,
-                                          TreePatternNode*> &ArgMap);
+  void
+  SubstituteFormalArguments(std::map<std::string, TreePatternNodePtr> &ArgMap);
 
   /// InlinePatternFragments - If this pattern refers to any pattern
   /// fragments, inline them into place, giving us a pattern without any
   /// PatFrag references.
-  TreePatternNode *InlinePatternFragments(TreePattern &TP);
+  TreePatternNodePtr InlinePatternFragments(TreePatternNodePtr T,
+                                            TreePattern &TP);
 
   /// ApplyTypeConstraints - Apply all of the type constraints relevant to
   /// this node and its children in the tree.  This returns true if it makes a
   /// change, false otherwise.  If a type contradiction is found, flag an error.
   bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters);
 
   /// UpdateNodeType - Set the node type of N to VT if VT contains
   /// information.  If N already contains a conflicting type, then flag an

 
 /// TreePattern - Represent a pattern, used for instructions, pattern
 /// fragments, etc.
 ///
 class TreePattern {
   /// Trees - The list of pattern trees which corresponds to this pattern.
   /// Note that PatFrag's only have a single tree.
   ///
-  std::vector<TreePatternNode*> Trees;
+  std::vector<TreePatternNodePtr> Trees;
 
   /// NamedNodes - This is all of the nodes that have names in the trees in this
   /// pattern.
-  StringMap<SmallVector<TreePatternNode*,1> > NamedNodes;
+  StringMap<SmallVector<TreePatternNode *, 1>> NamedNodes;
 
   /// TheRecord - The actual TableGen record corresponding to this pattern.
   ///
   Record *TheRecord;
 
   /// Args - This is a list of all of the arguments to this pattern (for
   /// PatFrag patterns), which are the 'node' markers in this pattern.
   std::vector<std::string> Args;

 public:
 
   /// TreePattern constructor - Parse the specified DagInits into the
   /// current record.
   TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
               CodeGenDAGPatterns &ise);
   TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
               CodeGenDAGPatterns &ise);
-  TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput,
+  TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput,
               CodeGenDAGPatterns &ise);
 
   /// getTrees - Return the tree patterns which corresponds to this pattern.
   ///
-  const std::vector<TreePatternNode*> &getTrees() const { return Trees; }
+  const std::vector<TreePatternNodePtr> &getTrees() const { return Trees; }
   unsigned getNumTrees() const { return Trees.size(); }
-  TreePatternNode *getTree(unsigned i) const { return Trees[i]; }
-  void setTree(unsigned i, TreePatternNode *Tree) { Trees[i] = Tree; }
-  TreePatternNode *getOnlyTree() const {
+  const TreePatternNodePtr &getTree(unsigned i) const { return Trees[i]; }
+  void setTree(unsigned i, TreePatternNodePtr Tree) { Trees[i] = Tree; }
+  TreePatternNodePtr getOnlyTree() const {
     assert(Trees.size() == 1 && "Doesn't have exactly one pattern!");
     return Trees[0];
   }
 
-  const StringMap<SmallVector<TreePatternNode*,1> > &getNamedNodesMap() {
+  const StringMap<SmallVector<TreePatternNode *, 1>> &getNamedNodesMap() {
     if (NamedNodes.empty())
       ComputeNamedNodes();
     return NamedNodes;
   }
 
   /// getRecord - Return the actual TableGen record corresponding to this
   /// pattern.
   ///
   Record *getRecord() const { return TheRecord; }
 
   unsigned getNumArgs() const { return Args.size(); }
   const std::string &getArgName(unsigned i) const {
     assert(i < Args.size() && "Argument reference out of range!");
     return Args[i];
   }
   std::vector<std::string> &getArgList() { return Args; }
 
   CodeGenDAGPatterns &getDAGPatterns() const { return CDP; }
 
   /// InlinePatternFragments - If this pattern refers to any pattern
   /// fragments, inline them into place, giving us a pattern without any
   /// PatFrag references.
   void InlinePatternFragments() {
     for (unsigned i = 0, e = Trees.size(); i != e; ++i)
-      Trees[i] = Trees[i]->InlinePatternFragments(*this);
+      Trees[i] = Trees[i]->InlinePatternFragments(Trees[i], *this);
   }
 
   /// InferAllTypes - Infer/propagate as many types throughout the expression
   /// patterns as possible.  Return true if all types are inferred, false
   /// otherwise.  Bail out if a type contradiction is found.
-  bool InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> >
-                          *NamedTypes=nullptr);
+  bool InferAllTypes(
+      const StringMap<SmallVector<TreePatternNode *, 1>> *NamedTypes = nullptr);
 
   /// error - If this is the first error in the current resolution step,
   /// print it and set the error flag.  Otherwise, continue silently.
   void error(const Twine &Msg);
   bool hasError() const {
     return HasError;
   }
   void resetError() {
     HasError = false;
   }
 
   TypeInfer &getInfer() { return Infer; }
 
   void print(raw_ostream &OS) const;
   void dump() const;
 
 private:
-  TreePatternNode *ParseTreePattern(Init *DI, StringRef OpName);
+  TreePatternNodePtr ParseTreePattern(Init *DI, StringRef OpName);
   void ComputeNamedNodes();
   void ComputeNamedNodes(TreePatternNode *N);
 };
 
 
 inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
                                             const TypeSetByHwMode &InTy,
                                             TreePattern &TP) {
inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
   TP.getInfer().expandOverloads(VTS);
   return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
 }
 
 
 /// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps
 /// that has a set ExecuteAlways / DefaultOps field.
 struct DAGDefaultOperand {
-  std::vector<TreePatternNode*> DefaultOps;
+  std::vector<TreePatternNodePtr> DefaultOps;
 };
 
 class DAGInstruction {
   TreePattern *Pattern;
   std::vector<Record*> Results;
   std::vector<Record*> Operands;
   std::vector<Record*> ImpResults;
-  TreePatternNode *ResultPattern;
+  TreePatternNodePtr ResultPattern;
+
 public:
   DAGInstruction(TreePattern *TP,
                  const std::vector<Record*> &results,
                  const std::vector<Record*> &operands,
                  const std::vector<Record*> &impresults)
     : Pattern(TP), Results(results), Operands(operands),
       ImpResults(impresults), ResultPattern(nullptr) {}
+  DAGInstruction(DAGInstruction &&Other) noexcept
+      : Pattern(Other.Pattern), Results(std::move(Other.Results)),
+        Operands(std::move(Other.Operands)),
+        ImpResults(std::move(Other.ImpResults)),
+        ResultPattern(std::move(Other.ResultPattern)) {
+    Other.Pattern = nullptr;
+  }
 
   TreePattern *getPattern() const { return Pattern; }
   unsigned getNumResults() const { return Results.size(); }
   unsigned getNumOperands() const { return Operands.size(); }
   unsigned getNumImpResults() const { return ImpResults.size(); }
   const std::vector<Record*>& getImpResults() const { return ImpResults; }
 
-  void setResultPattern(TreePatternNode *R) { ResultPattern = R; }
+  void setResultPattern(TreePatternNodePtr R) { ResultPattern = R; }
+
+  ~DAGInstruction() {
+    if (Pattern)
+      delete Pattern;
+  }
 
   Record *getResult(unsigned RN) const {
     assert(RN < Results.size());
     return Results[RN];
   }
 
   Record *getOperand(unsigned ON) const {
     assert(ON < Operands.size());
     return Operands[ON];
   }
 
   Record *getImpResult(unsigned RN) const {
     assert(RN < ImpResults.size());
     return ImpResults[RN];
   }
 
-  TreePatternNode *getResultPattern() const { return ResultPattern; }
+  TreePatternNodePtr getResultPattern() const { return ResultPattern; }
 };
 
 /// This class represents a condition that has to be satisfied for a pattern
 /// to be tried. It is a generalization of a class "Pattern" from Target.td:
 /// in addition to the Target.td's predicates, this class can also represent
 /// conditions associated with HW modes. Both types will eventually become
 /// strings containing C++ code to be executed, the difference is in how
 /// these strings are generated.
public:
   bool IsHwMode;          ///< Does this predicate correspond to a HW mode?
 };
 
 /// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns
 /// processed to produce isel.
 class PatternToMatch {
 public:
   PatternToMatch(Record *srcrecord, const std::vector<Predicate> &preds,
-                 TreePatternNode *src, TreePatternNode *dst,
-                 const std::vector<Record*> &dstregs,
-                 int complexity, unsigned uid, unsigned setmode = 0)
+                 TreePatternNodePtr src, TreePatternNodePtr dst,
+                 const std::vector<Record *> &dstregs, int complexity,
+                 unsigned uid, unsigned setmode = 0)
       : SrcRecord(srcrecord), SrcPattern(src), DstPattern(dst),
         Predicates(preds), Dstregs(std::move(dstregs)),
         AddedComplexity(complexity), ID(uid), ForceMode(setmode) {}
 
   PatternToMatch(Record *srcrecord, std::vector<Predicate> &&preds,
-                 TreePatternNode *src, TreePatternNode *dst,
-                 std::vector<Record*> &&dstregs,
-                 int complexity, unsigned uid, unsigned setmode = 0)
+                 TreePatternNodePtr src, TreePatternNodePtr dst,
+                 std::vector<Record *> &&dstregs, int complexity, unsigned uid,
+                 unsigned setmode = 0)
       : SrcRecord(srcrecord), SrcPattern(src), DstPattern(dst),
         Predicates(preds), Dstregs(std::move(dstregs)),
         AddedComplexity(complexity), ID(uid), ForceMode(setmode) {}
 
   Record          *SrcRecord;   // Originating Record for the pattern.
-  TreePatternNode *SrcPattern;  // Source pattern to match.
-  TreePatternNode *DstPattern;  // Resulting pattern.
+  TreePatternNodePtr SrcPattern;      // Source pattern to match.
+  TreePatternNodePtr DstPattern;      // Resulting pattern.
   std::vector<Predicate> Predicates;  // Top level predicate conditions
                                       // to match.
   std::vector<Record*> Dstregs; // Physical register defs being matched.
   int              AddedComplexity; // Add to matching pattern complexity.
   unsigned         ID;          // Unique ID for the record.
   unsigned         ForceMode;   // Force this mode in type inference when set.
 
   Record          *getSrcRecord()  const { return SrcRecord; }
-  TreePatternNode *getSrcPattern() const { return SrcPattern; }
-  TreePatternNode *getDstPattern() const { return DstPattern; }
+  TreePatternNode *getSrcPattern() const { return SrcPattern.get(); }
+  TreePatternNodePtr getSrcPatternShared() const { return SrcPattern; }
+  TreePatternNode *getDstPattern() const { return DstPattern.get(); }
+  TreePatternNodePtr getDstPatternShared() const { return DstPattern; }
   const std::vector<Record*> &getDstRegs() const { return Dstregs; }
   int         getAddedComplexity() const { return AddedComplexity; }
   const std::vector<Predicate> &getPredicates() const { return Predicates; }
 
   std::string getPredicateCheck() const;
 
   /// Compute the complexity metric for the input pattern.  This roughly
   /// corresponds to the number of nodes that are covered.
private:
   void ExpandHwModeBasedTypes();
   void InferInstructionFlags();
   void GenerateVariants();
   void VerifyInstructionFlags();
 
   std::vector<Predicate> makePredList(ListInit *L);
 
   void AddPatternToMatch(TreePattern *Pattern, PatternToMatch &&PTM);
-  void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
-                                   std::map<std::string,
-                                   TreePatternNode*> &InstInputs,
-                                   std::map<std::string,
-                                   TreePatternNode*> &InstResults,
-                                   std::vector<Record*> &InstImpResults);
+  void FindPatternInputsAndOutputs(
+      TreePattern *I, TreePatternNodePtr Pat,
+      std::map<std::string, TreePatternNodePtr> &InstInputs,
+      std::map<std::string, TreePatternNodePtr> &InstResults,
+      std::vector<Record *> &InstImpResults);
 };
 
 
 inline bool SDNodeInfo::ApplyTypeConstraints(TreePatternNode *N,
                                              TreePattern &TP) const {
     bool MadeChange = false;
     for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i)
       MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP);
     return MadeChange;
   }
 
 } // end namespace llvm
 
 #endif

utils/TableGen/CodeGenDAGPatterns.cpp

if (getChild(i)->ContainsUnresolvedType(TP))
       return true;
   return false;
 }
 
 bool TreePatternNode::hasProperTypeByHwMode() const {
   for (const TypeSetByHwMode &S : Types)
     if (!S.isDefaultOnly())
       return true;
-  for (TreePatternNode *C : Children)
+  for (const TreePatternNodePtr &C : Children)
     if (C->hasProperTypeByHwMode())
       return true;
   return false;
 }
 
 bool TreePatternNode::hasPossibleType() const {
   for (const TypeSetByHwMode &S : Types)
     if (!S.isPossible())
       return false;
-  for (TreePatternNode *C : Children)
+  for (const TreePatternNodePtr &C : Children)
     if (!C->hasPossibleType())
       return false;
   return true;
 }
 
 bool TreePatternNode::setDefaultMode(unsigned Mode) {
   for (TypeSetByHwMode &S : Types) {
     S.makeSimple(Mode);
     // Check if the selected mode had a type conflict.
     if (S.get(DefaultMode).empty())
       return false;
   }
-  for (TreePatternNode *C : Children)
+  for (const TreePatternNodePtr &C : Children)
     if (!C->setDefaultMode(Mode))
       return false;
   return true;
 }
 
 //===----------------------------------------------------------------------===//
 // SDNodeInfo implementation
 //
MVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const {
   }
   return MVT::Other;
 }
 
 //===----------------------------------------------------------------------===//
 // TreePatternNode implementation
 //
 
-TreePatternNode::~TreePatternNode() {
-#if 0 // FIXME: implement refcounted tree nodes!
-  for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
-    delete getChild(i);
-#endif
-}
-
 static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) {
   if (Operator->getName() == "set" ||
       Operator->getName() == "implicit")
     return 0;  // All return nothing.
 
   if (Operator->isSubClassOf("Intrinsic"))
     return CDP.getIntrinsic(Operator).IS.RetVTs.size();
 
bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N,
   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
     if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars))
       return false;
   return true;
 }
 
 /// clone - Make a copy of this tree and all of its children.
 ///
-TreePatternNode *TreePatternNode::clone() const {
-  TreePatternNode *New;
+TreePatternNodePtr TreePatternNode::clone() const {
+  TreePatternNodePtr New;
   if (isLeaf()) {
-    New = new TreePatternNode(getLeafValue(), getNumTypes());
+    New = std::make_shared<TreePatternNode>(getLeafValue(), getNumTypes());
   } else {
-    std::vector<TreePatternNode*> CChildren;
+    std::vector<TreePatternNodePtr> CChildren;
     CChildren.reserve(Children.size());
     for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
       CChildren.push_back(getChild(i)->clone());
-    New = new TreePatternNode(getOperator(), CChildren, getNumTypes());
+    New = std::make_shared<TreePatternNode>(getOperator(), CChildren,
+                                            getNumTypes());
   }
   New->setName(getName());
   New->Types = Types;
   New->setPredicateFns(getPredicateFns());
   New->setTransformFn(getTransformFn());
   return New;
 }
 
 /// RemoveAllTypes - Recursively strip all the types of this tree.
 void TreePatternNode::RemoveAllTypes() {
   // Reset to unknown type.
   std::fill(Types.begin(), Types.end(), TypeSetByHwMode());
   if (isLeaf()) return;
   for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
     getChild(i)->RemoveAllTypes();
 }
 
 
 /// SubstituteFormalArguments - Replace the formal arguments in this tree
 /// with actual values specified by ArgMap.
-void TreePatternNode::
-SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) {
+void TreePatternNode::SubstituteFormalArguments(
+    std::map<std::string, TreePatternNodePtr> &ArgMap) {
   if (isLeaf()) return;
 
   for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
     TreePatternNode *Child = getChild(i);
     if (Child->isLeaf()) {
       Init *Val = Child->getLeafValue();
       // Note that, when substituting into an output pattern, Val might be an
       // UnsetInit.
       if (isa<UnsetInit>(Val) || (isa<DefInit>(Val) &&
           cast<DefInit>(Val)->getDef()->getName() == "node")) {
         // We found a use of a formal argument, replace it with its value.
-        TreePatternNode *NewChild = ArgMap[Child->getName()];
+        TreePatternNodePtr NewChild = ArgMap[Child->getName()];
         assert(NewChild && "Couldn't find formal argument!");
         assert((Child->getPredicateFns().empty() ||
                 NewChild->getPredicateFns() == Child->getPredicateFns()) &&
                "Non-empty child predicate clobbered!");
         setChild(i, NewChild);
       }
     } else {
       getChild(i)->SubstituteFormalArguments(ArgMap);
     }
   }
 }
 
 
 /// InlinePatternFragments - If this pattern refers to any pattern
 /// fragments, inline them into place, giving us a pattern without any
 /// PatFrag references.
-TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) {
+TreePatternNodePtr TreePatternNode::InlinePatternFragments(TreePatternNodePtr T,
+                                                           TreePattern &TP) {
   if (TP.hasError())
     return nullptr;
 
   if (isLeaf())
-     return this;  // nothing to do.
+    return T; // nothing to do.
   Record *Op = getOperator();
 
   if (!Op->isSubClassOf("PatFrag")) {
     // Just recursively inline children nodes.
     for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
-      TreePatternNode *Child = getChild(i);
-      TreePatternNode *NewChild = Child->InlinePatternFragments(TP);
+      TreePatternNodePtr Child = getChildShared(i);
+      TreePatternNodePtr NewChild = Child->InlinePatternFragments(Child, TP);
 
       assert((Child->getPredicateFns().empty() ||
               NewChild->getPredicateFns() == Child->getPredicateFns()) &&
              "Non-empty child predicate clobbered!");
 
       setChild(i, NewChild);
     }
-    return this;
+    return T;
   }
 
   // Otherwise, we found a reference to a fragment.  First, look up its
   // TreePattern record.
   TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);
 
   // Verify that we are passing the right number of operands.
   if (Frag->getNumArgs() != Children.size()) {
     TP.error("'" + Op->getName() + "' fragment requires " +
              Twine(Frag->getNumArgs()) + " operands!");
-    return nullptr;
+    return {nullptr};
   }
 
-  TreePatternNode *FragTree = Frag->getOnlyTree()->clone();
+  TreePatternNodePtr FragTree = Frag->getOnlyTree()->clone();
 
   TreePredicateFn PredFn(Frag);
   if (!PredFn.isAlwaysTrue())
     FragTree->addPredicateFn(PredFn);
 
   // Resolve formal arguments to their actual value.
   if (Frag->getNumArgs()) {
     // Compute the map of formal to actual arguments.
-    std::map<std::string, TreePatternNode*> ArgMap;
-    for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i)
-      ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP);
+    std::map<std::string, TreePatternNodePtr> ArgMap;
+    for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) {
+      TreePatternNodePtr Child = getChildShared(i);
+      ArgMap[Frag->getArgName(i)] = Child->InlinePatternFragments(Child, TP);
+    }
 
     FragTree->SubstituteFormalArguments(ArgMap);
   }
 
   FragTree->setName(getName());
   for (unsigned i = 0, e = Types.size(); i != e; ++i)
     FragTree->UpdateNodeType(i, getExtType(i), TP);
 
   // Transfer in the old predicates.
   for (const TreePredicateFn &Pred : getPredicateFns())
     FragTree->addPredicateFn(Pred);
 
-  // Get a new copy of this fragment to stitch into here.
-  //delete this;    // FIXME: implement refcounting!
-
   // The fragment we inlined could have recursive inlining that is needed.  See
   // if there are any pattern fragments in it and inline them as needed.
-  return FragTree->InlinePatternFragments(TP);
+  return FragTree->InlinePatternFragments(FragTree, TP);
 }
 
 /// getImplicitType - Check to see if the specified record has an implicit
 /// type which should be applied to it.  This will infer the type of register
 /// references from the register file information, for example.
 ///
 /// When Unnamed is set, return the type of a DAG operand with no name, such as
 /// the F8RC register class argument in:

 
 TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
                          CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp),
                          isInputPattern(isInput), HasError(false),
                          Infer(*this) {
   Trees.push_back(ParseTreePattern(Pat, ""));
 }
 
-TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput,
-                         CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp),
-                         isInputPattern(isInput), HasError(false),
-                         Infer(*this) {
+TreePattern::TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput,
+                         CodeGenDAGPatterns &cdp)
+    : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false),
   Trees.push_back(Pat);
 }
 
 void TreePattern::error(const Twine &Msg) {
   if (HasError)
     return;
   dump();
   PrintError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg);
   HasError = true;
 }
 
 void TreePattern::ComputeNamedNodes() {
-  for (TreePatternNode *Tree : Trees)
-    ComputeNamedNodes(Tree);
+  for (TreePatternNodePtr &Tree : Trees)
+    ComputeNamedNodes(Tree.get());
 }
 
 void TreePattern::ComputeNamedNodes(TreePatternNode *N) {
   if (!N->getName().empty())
     NamedNodes[N->getName()].push_back(N);
 
   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
     ComputeNamedNodes(N->getChild(i));
 }
 
-
-TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){
+TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit,
+                                                 StringRef OpName) {
   if (DefInit *DI = dyn_cast<DefInit>(TheInit)) {
     Record *R = DI->getDef();
 
     // Direct reference to a leaf DagNode or PatFrag?  Turn it into a
     // TreePatternNode of its own.  For example:
     ///   (foo GPR, imm) -> (foo GPR, (imm))
     if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag"))
       return ParseTreePattern(
         DagInit::get(DI, nullptr,
                      std::vector<std::pair<Init*, StringInit*> >()),
         OpName);
 
     // Input argument?
-    TreePatternNode *Res = new TreePatternNode(DI, 1);
+    TreePatternNodePtr Res = std::make_shared<TreePatternNode>(DI, 1);
     if (R->getName() == "node" && !OpName.empty()) {
       if (OpName.empty())
         error("'node' argument requires a name to match with operand list");
       Args.push_back(OpName);
     }
 
     Res->setName(OpName);
     return Res;
   }
 
   // ?:$name or just $name.
   if (isa<UnsetInit>(TheInit)) {
     if (OpName.empty())
       error("'?' argument requires a name to match with operand list");
-    TreePatternNode *Res = new TreePatternNode(TheInit, 1);
+    TreePatternNodePtr Res = std::make_shared<TreePatternNode>(TheInit, 1);
     Args.push_back(OpName);
     Res->setName(OpName);
     return Res;
   }
 
   if (IntInit *II = dyn_cast<IntInit>(TheInit)) {
     if (!OpName.empty())
       error("Constant int argument should not have a name!");
-    return new TreePatternNode(II, 1);
+    return std::make_shared<TreePatternNode>(II, 1);
   }
 
   if (BitsInit *BI = dyn_cast<BitsInit>(TheInit)) {
     // Turn this into an IntInit.
     Init *II = BI->convertInitializerTo(IntRecTy::get());
     if (!II || !isa<IntInit>(II))
       error("Bits value must be constants!");
     return ParseTreePattern(II, OpName);
TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit,
   Record *Operator = OpDef->getDef();
 
   if (Operator->isSubClassOf("ValueType")) {
     // If the operator is a ValueType, then this must be "type cast" of a leaf
     // node.
     if (Dag->getNumArgs() != 1)
       error("Type cast only takes one operand!");
 
-    TreePatternNode *New = ParseTreePattern(Dag->getArg(0),
-                                            Dag->getArgNameStr(0));
+    TreePatternNodePtr New =
+        ParseTreePattern(Dag->getArg(0), Dag->getArgNameStr(0));
 
     // Apply the type cast.
     assert(New->getNumTypes() == 1 && "FIXME: Unhandled");
     const CodeGenHwModes &CGH = getDAGPatterns().getTargetInfo().getHwModes();
     New->UpdateNodeType(0, getValueTypeByHwMode(Operator, CGH), *this);
 
     if (!OpName.empty())
       error("ValueType cast should not have a name!");
if (Operator->isSubClassOf("SDNode") &&
         Operator->getName() != "tblockaddress" &&
         Operator->getName() != "tglobaladdr" &&
         Operator->getName() != "bb" &&
         Operator->getName() != "vt" &&
         Operator->getName() != "mcsym")
       error("Cannot use '" + Operator->getName() + "' in an output pattern!");
   }
 
-  std::vector<TreePatternNode*> Children;
+  std::vector<TreePatternNodePtr> Children;
 
   // Parse all the operands.
   for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i)
     Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgNameStr(i)));
 
   // Get the actual number of results before Operator is converted to an intrinsic
   // node (which is hard-coded to have either zero or one result).
   unsigned NumResults = GetNumNodeResults(Operator, CDP);
if (Operator->isSubClassOf("Intrinsic")) {
     if (Int.IS.RetVTs.empty())
       Operator = getDAGPatterns().get_intrinsic_void_sdnode();
     else if (Int.ModRef != CodeGenIntrinsic::NoMem)
       // Has side-effects, requires chain.
       Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode();
     else // Otherwise, no chain.
       Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode();
 
-    TreePatternNode *IIDNode = new TreePatternNode(IntInit::get(IID), 1);
+    TreePatternNodePtr IIDNode =
+        std::make_shared<TreePatternNode>(IntInit::get(IID), 1);
     Children.insert(Children.begin(), IIDNode);
   }
 
   if (Operator->isSubClassOf("ComplexPattern")) {
     for (unsigned i = 0; i < Children.size(); ++i) {
-      TreePatternNode *Child = Children[i];
+      TreePatternNodePtr Child = Children[i];
 
       if (Child->getName().empty())
         error("All arguments to a ComplexPattern must be named");
 
       // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)"
       // and "(MY_PAT $b, $a)" should not be allowed in the same pattern;
       // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)".
       auto OperandId = std::make_pair(Operator, i);
       auto PrevOp = ComplexPatternOperands.find(Child->getName());
       if (PrevOp != ComplexPatternOperands.end()) {
         if (PrevOp->getValue() != OperandId)
           error("All ComplexPattern operands must appear consistently: "
                 "in the same order in just one ComplexPattern instance.");
       } else
         ComplexPatternOperands[Child->getName()] = OperandId;
     }
   }
 
-  TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults);
+  TreePatternNodePtr Result =
+      std::make_shared<TreePatternNode>(Operator, Children, NumResults);
   Result->setName(OpName);
 
   if (Dag->getName()) {
     assert(Result->getName().empty());
     Result->setName(Dag->getNameStr());
   }
   return Result;
 }
 
 /// SimplifyTree - See if we can simplify this tree to eliminate something that
 /// will never match in favor of something obvious that will.  This is here
 /// strictly as a convenience to target authors because it allows them to write
 /// more type generic things and have useless type casts fold away.
 ///
 /// This returns true if any change is made.
-static bool SimplifyTree(TreePatternNode *&N) {
+static bool SimplifyTree(TreePatternNodePtr &N) {
   if (N->isLeaf())
     return false;
 
   // If we have a bitconvert with a resolved type and if the source and
   // destination types are the same, then the bitconvert is useless, remove it.
   if (N->getOperator()->getName() == "bitconvert" &&
       N->getExtType(0).isValueTypeByHwMode(false) &&
       N->getExtType(0) == N->getChild(0)->getExtType(0) &&
       N->getName().empty()) {
-    N = N->getChild(0);
+    N = N->getChildShared(0);
     SimplifyTree(N);
     return true;
   }
 
   // Walk all children.
   bool MadeChange = false;
   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
-    TreePatternNode *Child = N->getChild(i);
+    TreePatternNodePtr Child = N->getChildShared(i);
     MadeChange |= SimplifyTree(Child);
     N->setChild(i, Child);
   }
   return MadeChange;
 }
 
 
 
 /// InferAllTypes - Infer/propagate as many types throughout the expression
 /// patterns as possible.  Return true if all types are inferred, false
 /// otherwise.  Flags an error if a type contradiction is found.
 bool TreePattern::
 InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) {
   if (NamedNodes.empty())
     ComputeNamedNodes();
 
   bool MadeChange = true;
   while (MadeChange) {
     MadeChange = false;
-    for (TreePatternNode *&Tree : Trees) {
+    for (TreePatternNodePtr &Tree : Trees) {
       MadeChange |= Tree->ApplyTypeConstraints(*this, false);
       MadeChange |= SimplifyTree(Tree);
     }
 
     // If there are constraints on our named nodes, apply them.
     for (auto &Entry : NamedNodes) {
       SmallVectorImpl<TreePatternNode*> &Nodes = Entry.second;
 
for (auto &Entry : NamedNodes) {
 
         // The input types should be fully resolved by now.
         for (TreePatternNode *Node : Nodes) {
           // If this node is a register class, and it is the root of the pattern
           // then we're mapping something onto an input register.  We allow
           // changing the type of the input register in this case.  This allows
           // us to match things like:
           //  def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>;
-          if (Node == Trees[0] && Node->isLeaf()) {
+          if (Node == Trees[0].get() && Node->isLeaf()) {
             DefInit *DI = dyn_cast<DefInit>(Node->getLeafValue());
             if (DI && (DI->getDef()->isSubClassOf("RegisterClass") ||
                        DI->getDef()->isSubClassOf("RegisterOperand")))
               continue;
           }
 
           assert(Node->getNumTypes() == 1 &&
                  InNodes[0]->getNumTypes() == 1 &&
for (auto &Entry : NamedNodes) {
           MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this);
           MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this);
         }
       }
     }
   }
 
   bool HasUnresolvedTypes = false;
-  for (const TreePatternNode *Tree : Trees)
+  for (const TreePatternNodePtr &Tree : Trees)
     HasUnresolvedTypes |= Tree->ContainsUnresolvedType(*this);
   return !HasUnresolvedTypes;
 }
 
 void TreePattern::print(raw_ostream &OS) const {
   OS << getRecord()->getName();
   if (!Args.empty()) {
     OS << "(" << Args[0];
     for (unsigned i = 1, e = Args.size(); i != e; ++i)
       OS << ", " << Args[i];
     OS << ")";
   }
   OS << ": ";
 
   if (Trees.size() > 1)
     OS << "[\n";
-  for (const TreePatternNode *Tree : Trees) {
+  for (const TreePatternNodePtr &Tree : Trees) {
     OS << "\t";
     Tree->print(OS);
     OS << "\n";
   }
 
   if (Trees.size() > 1)
     OS << "]\n";
 }
for (unsigned i = 0, e = DefaultOps.size(); i != e; ++i) {
 
     // Create a TreePattern to parse this.
     TreePattern P(DefaultOps[i], DI, false, *this);
     assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!");
 
     // Copy the operands over into a DAGDefaultOperand.
     DAGDefaultOperand DefaultOpInfo;
 
-    TreePatternNode *T = P.getTree(0);
+    const TreePatternNodePtr &T = P.getTree(0);
     for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) {
-      TreePatternNode *TPN = T->getChild(op);
+      TreePatternNodePtr TPN = T->getChildShared(op);
       while (TPN->ApplyTypeConstraints(P, false))
         /* Resolve all types */;
 
       if (TPN->ContainsUnresolvedType(P)) {
         PrintFatalError("Value #" + Twine(i) + " of OperandWithDefaultOps '" +
                         DefaultOps[i]->getName() +
                         "' doesn't have a concrete type!");
       }
       DefaultOpInfo.DefaultOps.push_back(TPN);
     }
 
     // Insert it into the DefaultOperands map so we can find it later.
     DefaultOperands[DefaultOps[i]] = DefaultOpInfo;
   }
 }
 
 /// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an
 /// instruction input.  Return true if this is a real use.
-static bool HandleUse(TreePattern *I, TreePatternNode *Pat,
-                      std::map<std::string, TreePatternNode*> &InstInputs) {
+static bool HandleUse(TreePattern *I, TreePatternNodePtr Pat,
+                      std::map<std::string, TreePatternNodePtr> &InstInputs) {
   // No name -> not interesting.
   if (Pat->getName().empty()) {
     if (Pat->isLeaf()) {
       DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue());
       if (DI && (DI->getDef()->isSubClassOf("RegisterClass") ||
                  DI->getDef()->isSubClassOf("RegisterOperand")))
         I->error("Input " + DI->getDef()->getName() + " must be named!");
     }
     return false;
   }
 
   Record *Rec;
   if (Pat->isLeaf()) {
     DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue());
     if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!");
     Rec = DI->getDef();
   } else {
     Rec = Pat->getOperator();
   }
 
   // SRCVALUE nodes are ignored.
   if (Rec->getName() == "srcvalue")
     return false;
 
-  TreePatternNode *&Slot = InstInputs[Pat->getName()];
+  TreePatternNodePtr &Slot = InstInputs[Pat->getName()];
   if (!Slot) {
     Slot = Pat;
     return true;
   }
   Record *SlotRec;
   if (Slot->isLeaf()) {
     SlotRec = cast<DefInit>(Slot->getLeafValue())->getDef();
   } else {
     assert(Slot->getNumChildren() == 0 && "can't be a use with children!");
     SlotRec = Slot->getOperator();
   }
 
   // Ensure that the inputs agree if we've already seen this input.
   if (Rec != SlotRec)
     I->error("All $" + Pat->getName() + " inputs must agree with each other");
   if (Slot->getExtTypes() != Pat->getExtTypes())
     I->error("All $" + Pat->getName() + " inputs must agree with each other");
   return true;
 }
 
 /// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
 /// part of "I", the instruction), computing the set of inputs and outputs of
 /// the pattern.  Report errors if we see anything naughty.
-void CodeGenDAGPatterns::
-FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
-                            std::map<std::string, TreePatternNode*> &InstInputs,
-                            std::map<std::string, TreePatternNode*>&InstResults,
-                            std::vector<Record*> &InstImpResults) {
+void CodeGenDAGPatterns::FindPatternInputsAndOutputs(
+    TreePattern *I, TreePatternNodePtr Pat,
+    std::map<std::string, TreePatternNodePtr> &InstInputs,
+    std::map<std::string, TreePatternNodePtr> &InstResults,
+    std::vector<Record *> &InstImpResults) {
   if (Pat->isLeaf()) {
     bool isUse = HandleUse(I, Pat, InstInputs);
     if (!isUse && Pat->getTransformFn())
       I->error("Cannot specify a transform function for a non-input value!");
     return;
   }
 
   if (Pat->getOperator()->getName() == "implicit") {
void CodeGenDAGPatterns::FindPatternInputsAndOutputs(
   }
 
   if (Pat->getOperator()->getName() != "set") {
     // If this is not a set, verify that the children nodes are not void typed,
     // and recurse.
     for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {
       if (Pat->getChild(i)->getNumTypes() == 0)
         I->error("Cannot have void nodes inside of patterns!");
-      FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults,
-                                  InstImpResults);
+      FindPatternInputsAndOutputs(I, Pat->getChildShared(i), InstInputs,
+                                  InstResults, InstImpResults);
     }
 
     // If this is a non-leaf node with no children, treat it basically as if
     // it were a leaf.  This handles nodes like (imm).
     bool isUse = HandleUse(I, Pat, InstInputs);
 
     if (!isUse && Pat->getTransformFn())
       I->error("Cannot specify a transform function for a non-input value!");
     return;
   }
 
   // Otherwise, this is a set, validate and collect instruction results.
   if (Pat->getNumChildren() == 0)
     I->error("set requires operands!");
 
   if (Pat->getTransformFn())
     I->error("Cannot specify a transform function on a set node!");
 
   // Check the set destinations.
   unsigned NumDests = Pat->getNumChildren()-1;
   for (unsigned i = 0; i != NumDests; ++i) {
-    TreePatternNode *Dest = Pat->getChild(i);
+    TreePatternNodePtr Dest = Pat->getChildShared(i);
     if (!Dest->isLeaf())
       I->error("set destination should be a register!");
 
     DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());
     if (!Val) {
       I->error("set destination should be a register!");
       continue;
     }
for (unsigned i = 0; i != NumDests; ++i) {
     } else if (Val->getDef()->isSubClassOf("Register")) {
       InstImpResults.push_back(Val->getDef());
     } else {
       I->error("set destination should be a register!");
     }
   }
 
   // Verify and collect info from the computation.
-  FindPatternInputsAndOutputs(I, Pat->getChild(NumDests),
-                              InstInputs, InstResults, InstImpResults);
+  FindPatternInputsAndOutputs(I, Pat->getChildShared(NumDests), InstInputs,
+                              InstResults, InstImpResults);
 }
 
 //===----------------------------------------------------------------------===//
 // Instruction Analysis
 //===----------------------------------------------------------------------===//
 
 class InstAnalyzer {
   const CodeGenDAGPatterns &CDP;
 public:
   bool hasSideEffects;
   bool mayStore;
   bool mayLoad;
   bool isBitcast;
   bool isVariadic;
 
   InstAnalyzer(const CodeGenDAGPatterns &cdp)
     : CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false),
       isBitcast(false), isVariadic(false) {}
 
   void Analyze(const TreePattern *Pat) {
     // Assume only the first tree is the pattern. The others are clobber nodes.
-    AnalyzeNode(Pat->getTree(0));
+    AnalyzeNode(Pat->getTree(0).get());
   }
 
   void Analyze(const PatternToMatch &Pat) {
     AnalyzeNode(Pat.getSrcPattern());
   }
 
 private:
   bool IsNodeBitcast(const TreePatternNode *N) const {
const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern(
 
   // Infer as many types as possible.  If we cannot infer all of them, we can
   // never do anything with this instruction pattern: report it to the user.
   if (!I->InferAllTypes())
     I->error("Could not infer all types in pattern!");
 
   // InstInputs - Keep track of all of the inputs of the instruction, along
   // with the record they are declared as.
-  std::map<std::string, TreePatternNode*> InstInputs;
+  std::map<std::string, TreePatternNodePtr> InstInputs;
 
   // InstResults - Keep track of all the virtual registers that are 'set'
   // in the instruction, including what reg class they are.
-  std::map<std::string, TreePatternNode*> InstResults;
+  std::map<std::string, TreePatternNodePtr> InstResults;
 
   std::vector<Record*> InstImpResults;
 
   // Verify that the top-level forms in the instruction are of void type, and
   // fill in the InstResults map.
   SmallString<32> TypesString;
   for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {
     TypesString.clear();
-    TreePatternNode *Pat = I->getTree(j);
+    TreePatternNodePtr Pat = I->getTree(j);
     if (Pat->getNumTypes() != 0) {
       raw_svector_ostream OS(TypesString);
       for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) {
         if (k > 0)
           OS << ", ";
         Pat->getExtType(k).writeToStream(OS);
       }
       I->error("Top-level forms in instruction pattern should have"
const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern(
   // added to the machine instruction the node corresponds to.
   unsigned NumResults = InstResults.size();
 
   // Parse the operands list from the (ops) list, validating it.
   assert(I->getArgList().empty() && "Args list should still be empty here!");
 
   // Check that all of the results occur first in the list.
   std::vector<Record*> Results;
-  SmallVector<TreePatternNode *, 2> ResNodes;
+  SmallVector<TreePatternNodePtr, 2> ResNodes;
   for (unsigned i = 0; i != NumResults; ++i) {
     if (i == CGI.Operands.size())
       I->error("'" + InstResults.begin()->first +
                "' set but does not appear in operand list!");
     const std::string &OpName = CGI.Operands[i].Name;
 
     // Check that it exists in InstResults.
-    TreePatternNode *RNode = InstResults[OpName];
+    TreePatternNodePtr RNode = InstResults[OpName];
     if (!RNode)
       I->error("Operand $" + OpName + " does not exist in operand list!");
 
     ResNodes.push_back(RNode);
 
     Record *R = cast<DefInit>(RNode->getLeafValue())->getDef();
     if (!R)
       I->error("Operand $" + OpName + " should be a set destination: all "
                "outputs must occur before inputs in operand list!");
 
     if (!checkOperandClass(CGI.Operands[i], R))
       I->error("Operand $" + OpName + " class mismatch!");
 
     // Remember the return type.
     Results.push_back(CGI.Operands[i].Rec);
 
     // Okay, this one checks out.
     InstResults.erase(OpName);
   }
 
   // Loop over the inputs next.  Make a copy of InstInputs so we can destroy
   // the copy while we're checking the inputs.
-  std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs);
+  std::map<std::string, TreePatternNodePtr> InstInputsCheck(InstInputs);
 
-  std::vector<TreePatternNode*> ResultNodeOperands;
+  std::vector<TreePatternNodePtr> ResultNodeOperands;
   std::vector<Record*> Operands;
   for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) {
     CGIOperandList::OperandInfo &Op = CGI.Operands[i];
     const std::string &OpName = Op.Name;
     if (OpName.empty())
       I->error("Operand #" + Twine(i) + " in operands list has no name!");
 
     if (!InstInputsCheck.count(OpName)) {
       // If this is an operand with a DefaultOps set filled in, we can ignore
       // this.  When we codegen it, we will do so as always executed.
       if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) {
         // Does it have a non-empty DefaultOps field?  If so, ignore this
         // operand.
         if (!getDefaultOperand(Op.Rec).DefaultOps.empty())
           continue;
       }
       I->error("Operand $" + OpName +
                " does not appear in the instruction pattern");
     }
-    TreePatternNode *InVal = InstInputsCheck[OpName];
+    TreePatternNodePtr InVal = InstInputsCheck[OpName];
     InstInputsCheck.erase(OpName);   // It occurred, remove from map.
 
     if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) {
       Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef();
       if (!checkOperandClass(Op, InRec))
         I->error("Operand $" + OpName + "'s register class disagrees"
                  " between the operand and pattern");
     }
     Operands.push_back(Op.Rec);
 
     // Construct the result for the dest-pattern operand list.
-    TreePatternNode *OpNode = InVal->clone();
+    TreePatternNodePtr OpNode = InVal->clone();
 
     // No predicate is useful on the result.
     OpNode->clearPredicateFns();
 
     // Promote the xform function to be an explicit node if set.
     if (Record *Xform = OpNode->getTransformFn()) {
       OpNode->setTransformFn(nullptr);
-      std::vector<TreePatternNode*> Children;
+      std::vector<TreePatternNodePtr> Children;
       Children.push_back(OpNode);
-      OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes());
+      OpNode = std::make_shared<TreePatternNode>(Xform, Children,
+                                                 OpNode->getNumTypes());
     }
 
     ResultNodeOperands.push_back(OpNode);
   }
 
   if (!InstInputsCheck.empty())
     I->error("Input operand $" + InstInputsCheck.begin()->first +
              " occurs in pattern but not in operands list!");
 
-  TreePatternNode *ResultPattern =
-    new TreePatternNode(I->getRecord(), ResultNodeOperands,
-                        GetNumNodeResults(I->getRecord(), *this));
+  TreePatternNodePtr ResultPattern = std::make_shared<TreePatternNode>(
+      I->getRecord(), ResultNodeOperands,
   // Copy fully inferred output node types to instruction result pattern.
   for (unsigned i = 0; i != NumResults; ++i) {
     assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled");
     ResultPattern->setType(i, ResNodes[i]->getExtType(0));
   }
 
   // Create and insert the instruction.
   // FIXME: InstImpResults should not be part of DAGInstruction.
   DAGInstruction TheInst(I, Results, Operands, InstImpResults);
-  DAGInsts.insert(std::make_pair(I->getRecord(), TheInst));
+  DAGInsts.emplace(std::make_pair(I->getRecord(), std::move(TheInst)));
 
   // Use a temporary tree pattern to infer all types and make sure that the
   // constructed result is correct.  This depends on the instruction already
   // being inserted into the DAGInsts map.
   TreePattern Temp(I->getRecord(), ResultPattern, false, *this);
   Temp.InferAllTypes(&I->getNamedNodesMap());
 
   DAGInstruction &TheInsertedInst = DAGInsts.find(I->getRecord())->second;
for (auto &Entry : Instructions) {
     DAGInstruction &TheInst = Entry.second;
     TreePattern *I = TheInst.getPattern();
     if (!I) continue;  // No pattern.
 
     if (PatternRewriter)
       PatternRewriter(I);
     // FIXME: Assume only the first tree is the pattern. The others are clobber
     // nodes.
-    TreePatternNode *Pattern = I->getTree(0);
-    TreePatternNode *SrcPattern;
+    TreePatternNodePtr Pattern = I->getTree(0);
+    TreePatternNodePtr SrcPattern;
     if (Pattern->getOperator()->getName() == "set") {
       SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone();
     } else{
       // Not a set (store or something?)
       SrcPattern = Pattern;
     }
 
     Record *Instr = Entry.first;
     ListInit *Preds = Instr->getValueAsListInit("Predicates");
     int Complexity = Instr->getValueAsInt("AddedComplexity");
     AddPatternToMatch(
         I,
         PatternToMatch(Instr, makePredList(Preds), SrcPattern,
                        TheInst.getResultPattern(), TheInst.getImpResults(),
                        Complexity, Instr->getID()));
   }
 }
 
+typedef std::pair<TreePatternNode *, unsigned> NameRecord;
 
-typedef std::pair<const TreePatternNode*, unsigned> NameRecord;
-
-static void FindNames(const TreePatternNode *P,
+static void FindNames(TreePatternNode *P,
                       std::map<std::string, NameRecord> &Names,
                       TreePattern *PatternTop) {
   if (!P->getName().empty()) {
     NameRecord &Rec = Names[P->getName()];
     // If this is the first instance of the name, remember the node.
     if (Rec.second++ == 0)
       Rec.first = P;
     else if (Rec.first->getExtTypes() != P->getExtTypes())
void CodeGenDAGPatterns::ParsePatterns() {
 
   for (Record *CurPattern : Patterns) {
     DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");
 
     // If the pattern references the null_frag, there's nothing to do.
     if (hasNullFragReference(Tree))
       continue;
 
-    TreePattern *Pattern = new TreePattern(CurPattern, Tree, true, *this);
+    TreePattern Pattern(CurPattern, Tree, true, *this);
 
     // Inline pattern fragments into it.
-    Pattern->InlinePatternFragments();
+    Pattern.InlinePatternFragments();
 
     ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
     if (LI->empty()) continue;  // no pattern.
 
     // Parse the instruction.
     TreePattern Result(CurPattern, LI, false, *this);
 
     // Inline pattern fragments into it.
     Result.InlinePatternFragments();
 
     if (Result.getNumTrees() != 1)
       Result.error("Cannot handle instructions producing instructions "
                    "with temporaries yet!");
 
     bool IterateInference;
     bool InferredAllPatternTypes, InferredAllResultTypes;
     do {
       // Infer as many types as possible.  If we cannot infer all of them, we
       // can never do anything with this pattern: report it to the user.
       InferredAllPatternTypes =
-        Pattern->InferAllTypes(&Pattern->getNamedNodesMap());
+          Pattern.InferAllTypes(&Pattern.getNamedNodesMap());
 
       // Infer as many types as possible.  If we cannot infer all of them, we
       // can never do anything with this pattern: report it to the user.
       InferredAllResultTypes =
-          Result.InferAllTypes(&Pattern->getNamedNodesMap());
+          Result.InferAllTypes(&Pattern.getNamedNodesMap());
 
       IterateInference = false;
 
       // Apply the type of the result to the source pattern.  This helps us
       // resolve cases where the input type is known to be a pointer type (which
       // is considered resolved), but the result knows it needs to be 32- or
       // 64-bits.  Infer the other way for good measure.
       for (unsigned i = 0, e = std::min(Result.getTree(0)->getNumTypes(),
-                                        Pattern->getTree(0)->getNumTypes());
+                                        Pattern.getTree(0)->getNumTypes());
            i != e; ++i) {
-        IterateInference = Pattern->getTree(0)->UpdateNodeType(
+        IterateInference = Pattern.getTree(0)->UpdateNodeType(
             i, Result.getTree(0)->getExtType(i), Result);
         IterateInference |= Result.getTree(0)->UpdateNodeType(
-            i, Pattern->getTree(0)->getExtType(i), Result);
+            i, Pattern.getTree(0)->getExtType(i), Result);
       }
 
       // If our iteration has converged and the input pattern's types are fully
       // resolved but the result pattern is not fully resolved, we may have a
       // situation where we have two instructions in the result pattern and
       // the instructions require a common register class, but don't care about
       // what actual MVT is used.  This is actually a bug in our modelling:
       // output patterns should have register classes, not MVTs.
       //
       // In any case, to handle this, we just go through and disambiguate some
       // arbitrary types to the result pattern's nodes.
       if (!IterateInference && InferredAllPatternTypes &&
           !InferredAllResultTypes)
         IterateInference =
-            ForceArbitraryInstResultType(Result.getTree(0), Result);
+            ForceArbitraryInstResultType(Result.getTree(0).get(), Result);
     } while (IterateInference);
 
     // Verify that we inferred enough types that we can do something with the
     // pattern and result.  If these fire the user has to add type casts.
     if (!InferredAllPatternTypes)
-      Pattern->error("Could not infer all types in pattern!");
+      Pattern.error("Could not infer all types in pattern!");
     if (!InferredAllResultTypes) {
-      Pattern->dump();
+      Pattern.dump();
       Result.error("Could not infer all types in pattern result!");
     }
 
     // Validate that the input pattern is correct.
-    std::map<std::string, TreePatternNode*> InstInputs;
-    std::map<std::string, TreePatternNode*> InstResults;
+    std::map<std::string, TreePatternNodePtr> InstInputs;
+    std::map<std::string, TreePatternNodePtr> InstResults;
     std::vector<Record*> InstImpResults;
-    for (unsigned j = 0, ee = Pattern->getNumTrees(); j != ee; ++j)
-      FindPatternInputsAndOutputs(Pattern, Pattern->getTree(j),
-                                  InstInputs, InstResults,
-                                  InstImpResults);
+    for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j)
+      FindPatternInputsAndOutputs(&Pattern, Pattern.getTree(j), InstInputs,
+                                  InstResults, InstImpResults);
 
     // Promote the xform function to be an explicit node if set.
-    TreePatternNode *DstPattern = Result.getOnlyTree();
-    std::vector<TreePatternNode*> ResultNodeOperands;
+    TreePatternNodePtr DstPattern = Result.getOnlyTree();
+    std::vector<TreePatternNodePtr> ResultNodeOperands;
     for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) {
-      TreePatternNode *OpNode = DstPattern->getChild(ii);
+      TreePatternNodePtr OpNode = DstPattern->getChildShared(ii);
       if (Record *Xform = OpNode->getTransformFn()) {
         OpNode->setTransformFn(nullptr);
-        std::vector<TreePatternNode*> Children;
+        std::vector<TreePatternNodePtr> Children;
         Children.push_back(OpNode);
-        OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes());
+        OpNode = std::make_shared<TreePatternNode>(Xform, Children,
+                                                   OpNode->getNumTypes());
       }
       ResultNodeOperands.push_back(OpNode);
     }
     DstPattern = Result.getOnlyTree();
     if (!DstPattern->isLeaf())
-      DstPattern = new TreePatternNode(DstPattern->getOperator(),
+      DstPattern = std::make_shared<TreePatternNode>(DstPattern->getOperator(),
                                                      ResultNodeOperands,
                                                      DstPattern->getNumTypes());
 
     for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i)
       DstPattern->setType(i, Result.getOnlyTree()->getExtType(i));
 
     TreePattern Temp(Result.getRecord(), DstPattern, false, *this);
     Temp.InferAllTypes();
 
     // A pattern may end up with an "impossible" type, i.e. a situation
     // where all types have been eliminated for some node in this pattern.
     // This could occur for intrinsics that only make sense for a specific
     // value type, and use a specific register class. If, for some mode,
     // that register class does not accept that type, the type inference
     // will lead to a contradiction, which is not an error however, but
     // a sign that this pattern will simply never match.
-    if (Pattern->getTree(0)->hasPossibleType() &&
+    if (Pattern.getTree(0)->hasPossibleType() &&
         Temp.getOnlyTree()->hasPossibleType()) {
       ListInit *Preds = CurPattern->getValueAsListInit("Predicates");
       int Complexity = CurPattern->getValueAsInt("AddedComplexity");
       if (PatternRewriter)
-        PatternRewriter(Pattern);
-      AddPatternToMatch(
-          Pattern,
-          PatternToMatch(
-              CurPattern, makePredList(Preds), Pattern->getTree(0),
-              Temp.getOnlyTree(), std::move(InstImpResults), Complexity,
+        PatternRewriter(&Pattern);
+      AddPatternToMatch(&Pattern,
+                        PatternToMatch(CurPattern, makePredList(Preds),
+                                       Pattern.getTree(0), Temp.getOnlyTree(),
+                                       std::move(InstImpResults), Complexity,
                                        CurPattern->getID()));
     }
   }
 }
 
 static void collectModes(std::set<unsigned> &Modes, const TreePatternNode *N) {
   for (const TypeSetByHwMode &VTS : N->getExtTypes())
     for (const auto &I : VTS)
       Modes.insert(I.first);
 
   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
     collectModes(Modes, N->getChild(i));
 }
 
 void CodeGenDAGPatterns::ExpandHwModeBasedTypes() {
   const CodeGenHwModes &CGH = getTargetInfo().getHwModes();
   std::map<unsigned,std::vector<Predicate>> ModeChecks;
   std::vector<PatternToMatch> Copy = PatternsToMatch;
   PatternsToMatch.clear();
 
-  auto AppendPattern = [this,&ModeChecks](PatternToMatch &P, unsigned Mode) {
-    TreePatternNode *NewSrc = P.SrcPattern->clone();
-    TreePatternNode *NewDst = P.DstPattern->clone();
+  auto AppendPattern = [this, &ModeChecks](PatternToMatch &P, unsigned Mode) {
+    TreePatternNodePtr NewSrc = P.SrcPattern->clone();
+    TreePatternNodePtr NewDst = P.DstPattern->clone();
     if (!NewSrc->setDefaultMode(Mode) || !NewDst->setDefaultMode(Mode)) {
-      delete NewSrc;
-      delete NewDst;
       return;
     }
 
     std::vector<Predicate> Preds = P.Predicates;
     const std::vector<Predicate> &MC = ModeChecks[Mode];
     Preds.insert(Preds.end(), MC.begin(), MC.end());
     PatternsToMatch.emplace_back(P.getSrcRecord(), Preds, NewSrc, NewDst,
                                  P.getDstRegs(), P.getAddedComplexity(),
                                  Record::getNewUID(), Mode);
   };
 
   for (PatternToMatch &P : Copy) {
-    TreePatternNode *SrcP = nullptr, *DstP = nullptr;
+    TreePatternNodePtr SrcP = nullptr, DstP = nullptr;
     if (P.SrcPattern->hasProperTypeByHwMode())
       SrcP = P.SrcPattern;
     if (P.DstPattern->hasProperTypeByHwMode())
       DstP = P.DstPattern;
     if (!SrcP && !DstP) {
       PatternsToMatch.push_back(P);
       continue;
     }
 
     std::set<unsigned> Modes;
     if (SrcP)
-      collectModes(Modes, SrcP);
+      collectModes(Modes, SrcP.get());
     if (DstP)
-      collectModes(Modes, DstP);
+      collectModes(Modes, DstP.get());
 
     // The predicate for the default mode needs to be constructed for each
     // pattern separately.
     // Since not all modes must be present in each pattern, if a mode m is
     // absent, then there is no point in constructing a check for m. If such
     // a check was created, it would be equivalent to checking the default
     // mode, except not all modes' predicates would be a part of the checking
     // code. The subsequently generated check for the default mode would then
if (DepVars.empty()) {
     LLVM_DEBUG(errs() << "]");
   }
 }
 #endif
 
 
 /// CombineChildVariants - Given a bunch of permutations of each child of the
 /// 'operator' node, put them together in all possible ways.
-static void CombineChildVariants(TreePatternNode *Orig,
-               const std::vector<std::vector<TreePatternNode*> > &ChildVariants,
-                                 std::vector<TreePatternNode*> &OutVariants,
-                                 CodeGenDAGPatterns &CDP,
-                                 const MultipleUseVarSet &DepVars) {
+static void CombineChildVariants(
+    TreePatternNodePtr Orig,
+    const std::vector<std::vector<TreePatternNodePtr>> &ChildVariants,
+    std::vector<TreePatternNodePtr> &OutVariants, CodeGenDAGPatterns &CDP,
   // Make sure that each operand has at least one variant to choose from.
   for (const auto &Variants : ChildVariants)
     if (Variants.empty())
       return;
 
   // The end result is an all-pairs construction of the resultant pattern.
   std::vector<unsigned> Idxs;
   Idxs.resize(ChildVariants.size());
   bool NotDone;
   do {
 #ifndef NDEBUG
     LLVM_DEBUG(if (!Idxs.empty()) {
       errs() << Orig->getOperator()->getName() << ": Idxs = [ ";
       for (unsigned Idx : Idxs) {
         errs() << Idx << " ";
       }
       errs() << "]\n";
     });
 #endif
     // Create the variant and add it to the output list.
-    std::vector<TreePatternNode*> NewChildren;
+    std::vector<TreePatternNodePtr> NewChildren;
     for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i)
       NewChildren.push_back(ChildVariants[i][Idxs[i]]);
-    auto R = llvm::make_unique<TreePatternNode>(
+    TreePatternNodePtr R = std::make_shared<TreePatternNode>(
         Orig->getOperator(), NewChildren, Orig->getNumTypes());
 
     // Copy over properties.
     R->setName(Orig->getName());
     R->setPredicateFns(Orig->getPredicateFns());
     R->setTransformFn(Orig->getTransformFn());
     for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i)
       R->setType(i, Orig->getExtType(i));
 
     // If this pattern cannot match, do not include it as a variant.
     std::string ErrString;
     // Scan to see if this pattern has already been emitted.  We can get
     // duplication due to things like commuting:
     //   (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a)
     // which are the same pattern.  Ignore the dups.
     if (R->canPatternMatch(ErrString, CDP) &&
-        none_of(OutVariants, [&](TreePatternNode *Variant) {
-          return R->isIsomorphicTo(Variant, DepVars);
+        none_of(OutVariants, [&](TreePatternNodePtr Variant) {
+          return R->isIsomorphicTo(Variant.get(), DepVars);
         }))
-      OutVariants.push_back(R.release());
+      OutVariants.push_back(R);
 
     // Increment indices to the next permutation by incrementing the
     // indices from last index backward, e.g., generate the sequence
     // [0, 0], [0, 1], [1, 0], [1, 1].
     int IdxsIdx;
     for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {
       if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size())
         Idxs[IdxsIdx] = 0;
       else
         break;
     }
     NotDone = (IdxsIdx >= 0);
   } while (NotDone);
 }
 
 /// CombineChildVariants - A helper function for binary operators.
 ///
-static void CombineChildVariants(TreePatternNode *Orig,
-                                 const std::vector<TreePatternNode*> &LHS,
-                                 const std::vector<TreePatternNode*> &RHS,
-                                 std::vector<TreePatternNode*> &OutVariants,
+static void CombineChildVariants(TreePatternNodePtr Orig,
+                                 const std::vector<TreePatternNodePtr> &LHS,
+                                 const std::vector<TreePatternNodePtr> &RHS,
+                                 std::vector<TreePatternNodePtr> &OutVariants,
                                  CodeGenDAGPatterns &CDP,
                                  const MultipleUseVarSet &DepVars) {
-  std::vector<std::vector<TreePatternNode*> > ChildVariants;
+  std::vector<std::vector<TreePatternNodePtr>> ChildVariants;
   ChildVariants.push_back(LHS);
   ChildVariants.push_back(RHS);
   CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars);
 }
 
-
-static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N,
-                                     std::vector<TreePatternNode *> &Children) {
+static void
+GatherChildrenOfAssociativeOpcode(TreePatternNodePtr N,
+                                  std::vector<TreePatternNodePtr> &Children) {
   assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!");
   Record *Operator = N->getOperator();
 
   // Only permit raw nodes.
   if (!N->getName().empty() || !N->getPredicateFns().empty() ||
       N->getTransformFn()) {
     Children.push_back(N);
     return;
   }
 
   if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator)
-    Children.push_back(N->getChild(0));
+    Children.push_back(N->getChildShared(0));
   else
-    GatherChildrenOfAssociativeOpcode(N->getChild(0), Children);
+    GatherChildrenOfAssociativeOpcode(N->getChildShared(0), Children);
 
   if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator)
-    Children.push_back(N->getChild(1));
+    Children.push_back(N->getChildShared(1));
   else
-    GatherChildrenOfAssociativeOpcode(N->getChild(1), Children);
+    GatherChildrenOfAssociativeOpcode(N->getChildShared(1), Children);
 }
 
 /// GenerateVariantsOf - Given a pattern N, generate all permutations we can of
 /// the (potentially recursive) pattern by using algebraic laws.
 ///
-static void GenerateVariantsOf(TreePatternNode *N,
-                               std::vector<TreePatternNode*> &OutVariants,
+static void GenerateVariantsOf(TreePatternNodePtr N,
+                               std::vector<TreePatternNodePtr> &OutVariants,
                                CodeGenDAGPatterns &CDP,
                                const MultipleUseVarSet &DepVars) {
   // We cannot permute leaves or ComplexPattern uses.
   if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) {
     OutVariants.push_back(N);
     return;
   }
 
   // Look up interesting info about the node.
   const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator());
 
   // If this node is associative, re-associate.
   if (NodeInfo.hasProperty(SDNPAssociative)) {
     // Re-associate by pulling together all of the linked operators
-    std::vector<TreePatternNode*> MaximalChildren;
+    std::vector<TreePatternNodePtr> MaximalChildren;
     GatherChildrenOfAssociativeOpcode(N, MaximalChildren);
 
     // Only handle child sizes of 3.  Otherwise we'll end up trying too many
     // permutations.
     if (MaximalChildren.size() == 3) {
       // Find the variants of all of our maximal children.
-      std::vector<TreePatternNode*> AVariants, BVariants, CVariants;
+      std::vector<TreePatternNodePtr> AVariants, BVariants, CVariants;
       GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars);
       GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars);
       GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars);
 
       // There are only two ways we can permute the tree:
       //   (A op B) op C    and    A op (B op C)
       // Within these forms, we can also permute A/B/C.
 
       // Generate legal pair permutations of A/B/C.
-      std::vector<TreePatternNode*> ABVariants;
-      std::vector<TreePatternNode*> BAVariants;
-      std::vector<TreePatternNode*> ACVariants;
-      std::vector<TreePatternNode*> CAVariants;
-      std::vector<TreePatternNode*> BCVariants;
-      std::vector<TreePatternNode*> CBVariants;
+      std::vector<TreePatternNodePtr> ABVariants;
+      std::vector<TreePatternNodePtr> BAVariants;
+      std::vector<TreePatternNodePtr> ACVariants;
+      std::vector<TreePatternNodePtr> CAVariants;
+      std::vector<TreePatternNodePtr> BCVariants;
+      std::vector<TreePatternNodePtr> CBVariants;
       CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars);
       CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars);
       CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars);
       CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars);
       CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars);
       CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars);
 
       // Combine those into the result: (x op x) op x
if (MaximalChildren.size() == 3) {
       CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars);
       CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars);
       CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars);
       return;
     }
   }
 
   // Compute permutations of all children.
-  std::vector<std::vector<TreePatternNode*> > ChildVariants;
+  std::vector<std::vector<TreePatternNodePtr>> ChildVariants;
   ChildVariants.resize(N->getNumChildren());
   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
-    GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP, DepVars);
+    GenerateVariantsOf(N->getChildShared(i), ChildVariants[i], CDP, DepVars);
 
   // Build all permutations based on how the children were formed.
   CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars);
 
   // If this node is commutative, consider the commuted order.
   bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP);
   if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
     assert((N->getNumChildren()>=2 || isCommIntrinsic) &&
if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
     }
     // Consider the commuted order.
     if (isCommIntrinsic) {
       // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd
       // operands are the commutative operands, and there might be more operands
       // after those.
       assert(NC >= 3 &&
              "Commutative intrinsic should have at least 3 children!");
-      std::vector<std::vector<TreePatternNode*> > Variants;
+      std::vector<std::vector<TreePatternNodePtr>> Variants;
       Variants.push_back(ChildVariants[0]); // Intrinsic id.
       Variants.push_back(ChildVariants[2]);
       Variants.push_back(ChildVariants[1]);
       for (unsigned i = 3; i != NC; ++i)
         Variants.push_back(ChildVariants[i]);
       CombineChildVariants(N, Variants, OutVariants, CDP, DepVars);
     } else if (NC == N->getNumChildren()) {
-      std::vector<std::vector<TreePatternNode*> > Variants;
+      std::vector<std::vector<TreePatternNodePtr>> Variants;
       Variants.push_back(ChildVariants[1]);
       Variants.push_back(ChildVariants[0]);
       for (unsigned i = 2; i != NC; ++i)
         Variants.push_back(ChildVariants[i]);
       CombineChildVariants(N, Variants, OutVariants, CDP, DepVars);
     }
   }
 }
void CodeGenDAGPatterns::GenerateVariants() {
   // the .td file having to contain tons of variants of instructions.
   //
   // Note that this loop adds new patterns to the PatternsToMatch list, but we
   // intentionally do not reconsider these.  Any variants of added patterns have
   // already been added.
   //
   for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {
     MultipleUseVarSet             DepVars;
-    std::vector<TreePatternNode*> Variants;
+    std::vector<TreePatternNodePtr> Variants;
     FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars);
     LLVM_DEBUG(errs() << "Dependent/multiply used variables: ");
     LLVM_DEBUG(DumpDepVars(DepVars));
     LLVM_DEBUG(errs() << "\n");
-    GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this,
-                       DepVars);
+    GenerateVariantsOf(PatternsToMatch[i].getSrcPatternShared(), Variants,
+                       *this, DepVars);
 
     assert(!Variants.empty() && "Must create at least original variant!");
     if (Variants.size() == 1)  // No additional variants for this pattern.
       continue;
 
     LLVM_DEBUG(errs() << "FOUND VARIANTS OF: ";
                PatternsToMatch[i].getSrcPattern()->dump(); errs() << "\n");
 
     for (unsigned v = 0, e = Variants.size(); v != e; ++v) {
-      TreePatternNode *Variant = Variants[v];
+      TreePatternNodePtr Variant = Variants[v];
 
       LLVM_DEBUG(errs() << "  VAR#" << v << ": "; Variant->dump();
                  errs() << "\n");
 
       // Scan to see if an instruction or explicit pattern already matches this.
       bool AlreadyExists = false;
       for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) {
         // Skip if the top level predicates do not match.
for (unsigned v = 0, e = Variants.size(); v != e; ++v) {
         }
       }
       // If we already have it, ignore the variant.
       if (AlreadyExists) continue;
 
       // Otherwise, add it to the list of patterns we have.
       PatternsToMatch.push_back(PatternToMatch(
           PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(),
-          Variant, PatternsToMatch[i].getDstPattern(),
+          Variant, PatternsToMatch[i].getDstPatternShared(),
           PatternsToMatch[i].getDstRegs(),
           PatternsToMatch[i].getAddedComplexity(), Record::getNewUID()));
     }
 
     LLVM_DEBUG(errs() << "\n");
   }
 }

utils/TableGen/DAGISelMatcherGen.cpp

 namespace {
   class MatcherGen {
     const PatternToMatch &Pattern;
     const CodeGenDAGPatterns &CGP;
 
     /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts
     /// out with all of the types removed.  This allows us to insert type checks
     /// as we scan the tree.
-    TreePatternNode *PatWithNoTypes;
+    TreePatternNodePtr PatWithNoTypes;
 
     /// VariableMap - A map from variable names ('$dst') to the recorded operand
     /// number that they were captured as.  These are biased by 1 to make
     /// insertion easier.
     StringMap<unsigned> VariableMap;
 
     /// This maintains the recorded operand number that OPC_CheckComplexPattern
     /// drops each sub-operand into. We don't want to insert these into
class MatcherGen {
     Matcher *TheMatcher;
 
     /// CurPredicate - As we emit matcher nodes, this points to the latest check
     /// which should have future checks stuck into its Next position.
     Matcher *CurPredicate;
   public:
     MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp);
 
-    ~MatcherGen() {
-      delete PatWithNoTypes;
-    }
-
     bool EmitMatcherCode(unsigned Variant);
     void EmitResultCode();
 
     Matcher *GetMatcher() const { return TheMatcher; }
   private:
     void AddMatcher(Matcher *NewNode);
     void InferPossibleTypes(unsigned ForceMode);
 
if (const ComplexPattern *CP =
     if (Variant >= OpNodes.size()) return true;
 
     AddMatcher(new CheckOpcodeMatcher(CGP.getSDNodeInfo(OpNodes[Variant])));
   } else {
     if (Variant != 0) return true;
   }
 
   // Emit the matcher for the pattern structure and types.
-  EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes, Pattern.ForceMode);
+  EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes.get(),
+                Pattern.ForceMode);
 
   // If the pattern has a predicate on it (e.g. only enabled when a subtarget
   // feature is around, do the check).
   if (!Pattern.getPredicateCheck().empty())
     AddMatcher(new CheckPatternPredicateMatcher(Pattern.getPredicateCheck()));
 
   // Now that we've completed the structural type match, emit any ComplexPattern
   // checks (e.g. addrmode matches).  We emit this after the structural match
   // because they are generally more expensive to evaluate and more difficult to
   // factor.
   for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) {
-    const TreePatternNode *N = MatchedComplexPatterns[i].first;
+    auto N = MatchedComplexPatterns[i].first;
 
     // Remember where the results of this match get stuck.
     if (N->isLeaf()) {
       NamedComplexPatternOperands[N->getName()] = NextRecordedOperandNo + 1;
     } else {
       unsigned CurOp = NextRecordedOperandNo;
       for (unsigned i = 0; i < N->getNumChildren(); ++i) {
         NamedComplexPatternOperands[N->getChild(i)->getName()] = CurOp + 1;

 ///
 const TreePatternNode *MatcherGen::
 GetInstPatternNode(const DAGInstruction &Inst, const TreePatternNode *N) {
   const TreePattern *InstPat = Inst.getPattern();
 
   // FIXME2?: Assume actual pattern comes before "implicit".
   TreePatternNode *InstPatNode;
   if (InstPat)
-    InstPatNode = InstPat->getTree(0);
+    InstPatNode = InstPat->getTree(0).get();
   else if (/*isRoot*/ N == Pattern.getDstPattern())
     InstPatNode = Pattern.getSrcPattern();
   else
     return nullptr;
 
   if (InstPatNode && !InstPatNode->isLeaf() &&
       InstPatNode->getOperator()->getName() == "set")
     InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1);
for (unsigned InstOpNo = NumResults, e = NumFixedOperands;
     Record *OperandNode = II.Operands[InstOpNo].Rec;
     if (OperandNode->isSubClassOf("OperandWithDefaultOps") &&
         !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) {
       // This is a predicate or optional def operand; emit the
       // 'default ops' operands.
       const DAGDefaultOperand &DefaultOp
         = CGP.getDefaultOperand(OperandNode);
       for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i)
-        EmitResultOperand(DefaultOp.DefaultOps[i], InstOps);
+        EmitResultOperand(DefaultOp.DefaultOps[i].get(), InstOps);
       continue;
     }
 
     // Otherwise this is a normal operand or a predicate operand without
     // 'execute always'; emit it.
 
     // For operands with multiple sub-operands we may need to emit
     // multiple child patterns to cover them all.  However, ComplexPattern