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/ilist.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/Support/RecyclingAllocator.h"
#include "llvm/Target/TargetMachine.h"
#include <cassert>
#include <vector>
#include <map>
#include <string>

namespace llvm {

class AliasAnalysis;
class MachineConstantPoolValue;
class MachineFunction;
class MDNode;
class SDNodeOrdering;
class SDDbgValue;
class TargetLowering;
class TargetSelectionDAGInfo;

template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
private:
  mutable ilist_half_node<SDNode> Sentinel;
public:
  SDNode *createSentinel() const {
    return static_cast<SDNode*>(&Sentinel);
  }
  static void destroySentinel(SDNode *) {}

  SDNode *provideInitialHead() const { return createSentinel(); }
  SDNode *ensureHead(SDNode*) const { return createSentinel(); }
  static void noteHead(SDNode*, SDNode*) {}

  static void deleteNode(SDNode *) {
    assert(0 && "ilist_traits<SDNode> shouldn't see a deleteNode call!");
  }
private:
  static void createNode(const SDNode &);
};

/// SDDbgInfo - Keeps track of dbg_value information through SDISel.  We do
/// not build SDNodes for these so as not to perturb the generated code;
/// instead the info is kept off to the side in this structure. Each SDNode may
/// have one or more associated dbg_value entries. This information is kept in
/// DbgValMap.
/// Byval parameters are handled separately because they don't use alloca's,
/// which busts the normal mechanism.  There is good reason for handling all
/// parameters separately:  they may not have code generated for them, they
/// should always go at the beginning of the function regardless of other code
/// motion, and debug info for them is potentially useful even if the parameter
/// is unused.  Right now only byval parameters are handled separately.
class SDDbgInfo {
  SmallVector<SDDbgValue*, 32> DbgValues;
  SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
  DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMap;

  void operator=(const SDDbgInfo&);   // Do not implement.
  SDDbgInfo(const SDDbgInfo&);   // Do not implement.
public:
  SDDbgInfo() {}

  void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
    if (isParameter) {
      ByvalParmDbgValues.push_back(V);
    } else     DbgValues.push_back(V);
    if (Node)
      DbgValMap[Node].push_back(V);
  }

  void clear() {
    DbgValMap.clear();
    DbgValues.clear();
    ByvalParmDbgValues.clear();
  }

  bool empty() const {
    return DbgValues.empty() && ByvalParmDbgValues.empty();
  }

  SmallVector<SDDbgValue*,2> &getSDDbgValues(const SDNode *Node) {
    return DbgValMap[Node];
  }

  void removeSDDbgValues(const SDNode *Node) {
    DbgValMap.erase(Node);
  }

  typedef SmallVector<SDDbgValue*,32>::iterator DbgIterator;
  DbgIterator DbgBegin() { return DbgValues.begin(); }
  DbgIterator DbgEnd()   { return DbgValues.end(); }
  DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
  DbgIterator ByvalParmDbgEnd()   { return ByvalParmDbgValues.end(); }
};

enum CombineLevel {
  Unrestricted,   // Combine may create illegal operations and illegal types.
  NoIllegalTypes, // Combine may create illegal operations but no illegal types.
  NoIllegalOperations // Combine may only create legal operations and types.
};

class SelectionDAG;
void checkForCycles(const SDNode *N);
void checkForCycles(const SelectionDAG *DAG);

/// 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 {
  const TargetMachine &TM;
  const TargetLowering &TLI;
  const TargetSelectionDAGInfo &TSI;
  MachineFunction *MF;
  LLVMContext *Context;

  /// EntryNode - The