include/llvm/CodeGen/SelectionDAGCSEMap.h

   1 //===-- llvm/CodeGen/SelectionDAGCSEMap.h - CSE Map for SD ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file declares the SelectionDAG class, and transitively defines the
  11 // SDNode class and subclasses.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_SELECTIONDAGCSEMAP_H
  16 #define LLVM_CODEGEN_SELECTIONDAGCSEMAP_H
  17
  18 #include "llvm/ADT/SmallVector.h"
  19
  20 namespace llvm {
  21   class SDNode;
  22   class SDOperand;
  23   struct SDVTList;
  24
  25   /// SelectionDAGCSEMap - This class is used for two purposes:
  26   ///   1. Given information (e.g. opcode and operand info) about a node we want
  27   ///      to create, look up the unique instance of the node in the map.  If
  28   ///      the node already exists, return it, otherwise return the bucket it
  29   ///      should be inserted into.
  30   ///   2. Given a node that has already been created, remove it from the CSE
  31   ///      map.
  32   ///
  33   /// This class is implemented as a chained hash table, where the "buckets" are
  34   /// actually the SDNodes themselves (the next pointer is in the SDNode).
  35   ///
  36   class SelectionDAGCSEMap {
  37     void **Buckets;
  38     unsigned NumBuckets;  // Always a power of 2.
  39     unsigned NumNodes;
  40   public:
  41     class NodeID;
  42     SelectionDAGCSEMap();
  43     ~SelectionDAGCSEMap();
  44
  45     /// RemoveNode - Remove a node from the CSE map, returning true if one was
  46     /// removed or false if the node was not in the CSE map.
  47     bool RemoveNode(SDNode *N);
  48
  49     /// GetOrInsertSimpleNode - If there is an existing simple SDNode exactly
  50     /// equal to the specified node, return it.  Otherwise, insert 'N' and it
  51     /// instead.  This only works on *simple* SDNodes, not ConstantSDNode or any
  52     /// other classes derived from SDNode.
  53     SDNode *GetOrInsertNode(SDNode *N);
  54
  55     /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
  56     /// return it.  If not, return the insertion token that will make insertion
  57     /// faster.
  58     SDNode *FindNodeOrInsertPos(const NodeID &ID, void *&InsertPos);
  59
  60     /// InsertNode - Insert the specified node into the CSE Map, knowing that it
  61     /// is not already in the map.  InsertPos must be obtained from
  62     /// FindNodeOrInsertPos.
  63     void InsertNode(SDNode *N, void *InsertPos);
  64
  65     class NodeID {
  66       /// Use a SmallVector to avoid a heap allocation in the common case.
  67       ///
  68       SmallVector<unsigned, 32> Bits;
  69     public:
  70       NodeID() {}
  71       NodeID(SDNode *N);
  72       NodeID(unsigned short ID, SDVTList VTList);
  73       NodeID(unsigned short ID, SDVTList VTList, SDOperand Op);
  74       NodeID(unsigned short ID, SDVTList VTList,
  75              SDOperand Op1, SDOperand Op2);
  76       NodeID(unsigned short ID, SDVTList VTList,
  77              SDOperand Op1, SDOperand Op2, SDOperand Op3);
  78       NodeID(unsigned short ID, SDVTList VTList,
  79              const SDOperand *OpList, unsigned N);
  80
  81       void SetOpcode(unsigned short ID) {
  82         Bits.push_back(ID);
  83       }
  84
  85       /// getOpcode - Return the opcode that has been set for this NodeID.
  86       ///
  87       unsigned getOpcode() const {
  88         return Bits[0];
  89       }
  90
  91       void SetValueTypes(SDVTList VTList);
  92       void SetOperands() {}
  93       void SetOperands(SDOperand Op) { AddOperand(Op); }
  94       void SetOperands(SDOperand Op1, SDOperand Op2) {
  95         AddOperand(Op1); AddOperand(Op2);
  96       }
  97       void SetOperands(SDOperand Op1, SDOperand Op2, SDOperand Op3) {
  98         AddOperand(Op1); AddOperand(Op2); AddOperand(Op3);
  99       }
 100       void SetOperands(const SDOperand *Ops, unsigned NumOps);
 101       void AddOperand(SDOperand Op);
 102       void AddPointer(const void *Ptr);
 103       void AddInteger(signed I) {
 104         Bits.push_back(I);
 105       }
 106       void AddInteger(unsigned I) {
 107         Bits.push_back(I);
 108       }
 109       void AddInteger(uint64_t I) {
 110         Bits.push_back(unsigned(I));
 111         Bits.push_back(unsigned(I >> 32));
 112       }
 113
 114       unsigned ComputeHash() const;
 115
 116       bool operator==(const NodeID &RHS) const;
 117     };
 118
 119   private:
 120     SDNode *GetNextPtr(void *NextInBucketPtr);
 121     SDNode *GetNextPtr(void *NextInBucketPtr, void **Buckets, unsigned NumBuck);
 122     void **GetBucketPtr(void *NextInBucketPtr);
 123     void **GetBucketFor(const NodeID &ID) const;
 124     void GrowHashTable();
 125   };
 126 }  // end namespace llvm
 127
 128 #endif