path: root/include/llvm/CodeGen/SelectionDAG.h

//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file declares the SelectionDAG class, and transitively defines the
// SDNode class and subclasses.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_SELECTIONDAG_H
#define LLVM_CODEGEN_SELECTIONDAG_H

#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/ilist.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"

#include <list>
#include <vector>
#include <map>
#include <string>

namespace llvm {
  class AliasAnalysis;
  class TargetLowering;
  class TargetMachine;
  class MachineModuleInfo;
  class MachineFunction;
  class MachineConstantPoolValue;
  class FunctionLoweringInfo;

/// SelectionDAG class - This is used to represent a portion of an LLVM function
/// in a low-level Data Dependence DAG representation suitable for instruction
/// selection.  This DAG is constructed as the first step of instruction
/// selection in order to allow implementation of machine specific optimizations
/// and code simplifications.
///
/// The representation used by the SelectionDAG is a target-independent
/// representation, which has some similarities to the GCC RTL representation,
/// but is significantly more simple, powerful, and is a graph form instead of a
/// linear form.
///
class SelectionDAG {
  TargetLowering &TLI;
  MachineFunction &MF;
  FunctionLoweringInfo &FLI;
  MachineModuleInfo *MMI;

  /// Root - The root of the entire DAG.  EntryNode - The starting token.
  SDOperand Root, EntryNode;

  /// AllNodes - A linked list of nodes in the current DAG.
  ilist<SDNode> AllNodes;

  /// CSEMap - This structure is used to memoize nodes, automatically performing
  /// CSE with existing nodes with a duplicate is requested.
  FoldingSet<SDNode> CSEMap;

public:
  SelectionDAG(TargetLowering &tli, MachineFunction &mf, 
               FunctionLoweringInfo &fli, MachineModuleInfo *mmi)
  : TLI(tli), MF(mf), FLI(fli), MMI(mmi) {
    EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
  }
  ~SelectionDAG();

  MachineFunction &getMachineFunction() const { return MF; }
  const TargetMachine &getTarget() const;
  TargetLowering &getTargetLoweringInfo() const { return TLI; }
  FunctionLoweringInfo &getFunctionLoweringInfo() const { return FLI; }
  MachineModuleInfo *getMachineModuleInfo() const { return MMI; }

  /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
  ///
  void viewGraph();
  
#ifndef NDEBUG
  std::map<const SDNode *, std::string> NodeGraphAttrs;
#endif

  /// clearGraphAttrs - Clear all previously defined node graph attributes.
  /// Intended to be used from a debugging tool (eg. gdb).
  void clearGraphAttrs();
  
  /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
  ///
  void setGraphAttrs(const SDNode *N, const char *Attrs);
  
  /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
  /// Used from getNodeAttributes.
  const std::string getGraphAttrs(const SDNode *N) const;
  
  /// setGraphColor - Convenience for setting node color attribute.
  ///
  void setGraphColor(const SDNode *N, const char *Color);

  typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
  allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
  allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
  typedef ilist<SDNode>::iterator allnodes_iterator;
  allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
  allnodes_iterator allnodes_end() { return AllNodes.end(); }
  ilist<SDNode>::size_type allnodes_size() const { return AllNodes.size(); }
  
  /// getRoot - Return the root tag of the SelectionDAG.
  ///
  const SDOperand &getRoot() const { return Root; }

  /// getEntryNode - Return the token chain corresponding to the entry of the
  /// function.
  const SDOperand &getEntryNode() const { return EntryNode; }

  /// setRoot - Set the current root tag of the SelectionDAG.
  ///
  const SDOperand &setRoot(SDOperand N) { return Root = N; }

  /// Combine - This iterates over the nodes in the SelectionDAG, folding
  /// certain types of nodes together, or eliminating superfluous nodes.  When
  /// the AfterLegalize argument is set to 'true', Combine takes care not to
  /// generate any nodes that will be illegal on the target.
  void Combine(bool AfterLegalize, AliasAnalysis &AA);
  
  /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
  /// only uses types natively supported by the target.
  ///
  /// Note that this is an involved process that may invalidate pointers into
  /// the graph.
  void LegalizeTypes();
  
  /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
  /// compatible with the target instruction selector, as indicated by the
  /// TargetLowering object.
  ///
  /// Note that this is an involved process that may invalidate pointers into
  /// the graph.
  void Legalize();

  /// RemoveDeadNodes - This method deletes all unreachable nodes in the
  /// SelectionDAG.
  void RemoveDeadNodes();

  /// DeleteNode - Remove the specified node from the system.  This node must
  /// have no referrers.
  void DeleteNode(SDNode *N);

  /// getVTList - Return an SDVTList that represents the list of values
  /// specified.
  SDVTList getVTList(MVT VT);
  SDVTList getVTList(MVT VT1, MVT VT2);
  SDVTList getVTList(MVT VT1, MVT VT2, MVT VT3);
  SDVTList getVTList(const MVT *VTs, unsigned NumVTs);
  
  /// getNodeValueTypes - These are obsolete, use getVTList instead.
  const MVT *getNodeValueTypes(MVT VT) {
    return getVTList(VT).VTs;
  }
  const MVT *getNodeValueTypes(MVT VT1, MVT VT2) {
    return getVTList(VT1, VT2).VTs;
  }
  const MVT *getNodeValueTypes(MVT VT1, MVT VT2, MVT VT3) {
    return getVTList(VT1, VT2, VT3).VTs;
  }
  const MVT *getNodeValueTypes(std::vector<MVT> &vtList) {
    return getVTList(&vtList[0], (unsigned)vtList.size()).VTs;
  }
  
  
  //===--------------------------------------------------------------------===//
  // Node creation methods.
  //
  SDOperand getConstant(uint64_t Val, MVT VT, bool isTarget = false);
  SDOperand getConstant(const APInt &Val, MVT VT, bool isTarget = false);
  SDOperand getIntPtrConstant(uint64_t Val, bool isTarget = false);
  SDOperand getTargetConstant(uint64_t Val, MVT VT) {
    return getConstant(Val, VT, true);
  }
  SDOperand getTargetConstant(const APInt &Val, MVT VT) {
    return getConstant(Val, VT, true);
  }
  SDOperand getConstantFP(double Val, MVT VT, bool isTarget = false);
  SDOperand getConstantFP(const APFloat& Val, MVT VT, bool isTarget = false);
  SDOperand getTargetConstantFP(double Val, MVT VT) {
    return getConstantFP(Val, VT, true);
  }
  SDOperand getTargetConstantFP(const APFloat& Val, MVT VT) {
    return getConstantFP(Val, VT, true);
  }