[DomTree] Use SmallVector<DomTreeNodeBase *, 4> instead of std::vector.

[fhahn]

Summary

Currentl DomTreeNodeBase is using std::vectot to store it's children.
Using SmallVector should be more efficient in terms of compile-time.

A size of 4 seems to be the sweet-spot in terms of compile-time,
according to

http://llvm-compile-time-tracker.com/compare.php?from=9933188c90615c9c264ebb69117f09726e909a25&to=d7a801d027648877b20f0e00e822a7a64c58d976&stat=instructions

This results in the following geomean improvements

                       geomean insts     max rss
O3                          -0.31 %       +0.02 %
ReleaseThinLTO              -0.35 %       -0.12 %
ReleaseLTO                  -0.28 %       -0.12 %
O0                          -0.06 %       -0.02 %
NewPM O3                    -0.36 %       +0.05 %
ReleaseThinLTO (link only)  -0.44 %       -0.10 %
ReleaseLTO-g (link only):   -0.32 %       -0.03 %

I am not sure if there's any other benefits of using std::vector over
SmallVector.

[asbirlea]

LGTM.

[kuhar]

Thanks for the numbers. LGTM.

llvm/include/llvm/Support/GenericDomTree.h

 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 #include <utility>
-#include <vector>
 
 namespace llvm {
 
 template <typename NodeT, bool IsPostDom>
 class DominatorTreeBase;
 
 namespace DomTreeBuilder {
 template <typename DomTreeT>
 struct SemiNCAInfo;
 }  // namespace DomTreeBuilder
 
 /// Base class for the actual dominator tree node.
 template <class NodeT> class DomTreeNodeBase {
   friend class PostDominatorTree;
   friend class DominatorTreeBase<NodeT, false>;
   friend class DominatorTreeBase<NodeT, true>;
   friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
   friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
 
   NodeT *TheBB;
   DomTreeNodeBase *IDom;
   unsigned Level;
-  std::vector<DomTreeNodeBase *> Children;
+  SmallVector<DomTreeNodeBase *, 4> Children;
   mutable unsigned DFSNumIn = ~0;
   mutable unsigned DFSNumOut = ~0;
 
  public:
   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
       : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
 
-  using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
+  using iterator = typename SmallVector<DomTreeNodeBase *, 4>::iterator;
   using const_iterator =
-      typename std::vector<DomTreeNodeBase *>::const_iterator;
+      typename SmallVector<DomTreeNodeBase *, 4>::const_iterator;
 
   iterator begin() { return Children.begin(); }
   iterator end() { return Children.end(); }
   const_iterator begin() const { return Children.begin(); }
   const_iterator end() const { return Children.end(); }
 
   DomTreeNodeBase *const &back() const { return Children.back(); }
   DomTreeNodeBase *&back() { return Children.back(); }
protected:
   void Split(typename GraphTraits<N>::NodeRef NewBB) {
     using GraphT = GraphTraits<N>;
     using NodeRef = typename GraphT::NodeRef;
     assert(std::distance(GraphT::child_begin(NewBB),
                          GraphT::child_end(NewBB)) == 1 &&
            "NewBB should have a single successor!");
     NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
 
-    std::vector<NodeRef> PredBlocks;
+    SmallVector<NodeRef, 4> PredBlocks;
     for (auto Pred : children<Inverse<N>>(NewBB))
       PredBlocks.push_back(Pred);
 
     assert(!PredBlocks.empty() && "No predblocks?");
 
     bool NewBBDominatesNewBBSucc = true;
     for (auto Pred : children<Inverse<N>>(NewBBSucc)) {
       if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&