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

//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- C++ -*-===//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
// 
// This file declares the SelectionDAG class, which is used to represent an LLVM
// function in a low-level 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 is loosly modeled after the GCC RTL representation, but
// is significantly simpler.
//   
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_SELECTIONDAG_H
#define LLVM_CODEGEN_SELECTIONDAG_H

#include "llvm/CodeGen/ValueTypes.h"
#include "Support/DataTypes.h"
#include <map>
#include <vector>
#include <cassert>

namespace llvm {

class Value;
class Type;
class Instruction;
class CallInst;
class BasicBlock;
class MachineBasicBlock;
class MachineFunction;
class TargetMachine;
class SelectionDAGNode;
class SelectionDAGBlock;
class SelectionDAGBuilder;
class SelectionDAGTargetBuilder;

/// ISD namespace - This namespace contains an enum which represents all of the
/// SelectionDAG node types and value types.
///
namespace ISD {
  enum NodeType {
    // ChainNode nodes are used to sequence operations within a basic block
    // which cannot be reordered (such as loads, stores, calls, etc).
    // BlockChainNodes are used to connect the DAG's for different basic blocks
    // into one big DAG.
    ChainNode, BlockChainNode,

    // ProtoNodes are nodes that are only half way constructed.
    ProtoNode,

    // Leaf nodes
    Constant, FrameIndex, BasicBlock,

    // Simple binary arithmetic operators
    Plus, Minus, Times, SDiv, UDiv, SRem, URem,

    // Bitwise operators
    And, Or, Xor,

    // Comparisons
    SetEQ, SetNE, SetLT, SetLE, SetGT, SetGE,

    // Control flow instructions
    Br, BrCond, Switch, Ret, RetVoid,

    // Other operators
    Load, Store, PHI, Call,

    // Unknown operators, of a specified arity
    Unspec1, Unspec2
  };
}

class SelectionDAG {
  friend class SelectionDAGBuilder;
  MachineFunction &F;
  const TargetMachine &TM;
  MVT::ValueType PointerType;    // The ValueType the target uses for pointers

  // ValueMap - The SelectionDAGNode for each LLVM value in the function.
  std::map<const Value*, SelectionDAGNode*> ValueMap;

  // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock
  std::map<const BasicBlock*, MachineBasicBlock*> BlockMap;

  // Root - The root of the entire DAG
  SelectionDAGNode *Root;

  // AllNodes - All of the nodes in the DAG
  std::vector<SelectionDAGNode*> AllNodes;
public:
  /// SelectionDAG constructor - Build a SelectionDAG for the specified
  /// function.  Implemented in DAGBuilder.cpp
  ///
  SelectionDAG(MachineFunction &F, const TargetMachine &TM,
               SelectionDAGTargetBuilder &SDTB);
  ~SelectionDAG();

  /// getValueType - Return the ValueType for the specified LLVM type.  This
  /// method works on all scalar LLVM types.
  ///
  MVT::ValueType getValueType(const Type *Ty) const;

  /// getRoot - Return the root of the current SelectionDAG.
  ///
  SelectionDAGNode *getRoot() const { return Root; }

  /// getMachineFunction - Return the MachineFunction object that this
  /// SelectionDAG corresponds to.
  ///
  MachineFunction &getMachineFunction() const { return F; }

  //===--------------------------------------------------------------------===//
  // Addition and updating methods
  //

  /// addNode - Add the specified node to the SelectionDAG so that it will be
  /// deleted when the DAG is...
  ///
  SelectionDAGNode *addNode(SelectionDAGNode *N) {
    AllNodes.push_back(N);
    return N;
  }

  /// addNodeForValue - Add the specified node to the SelectionDAG so that it
  /// will be deleted when the DAG is... and update the value map to indicate
  /// that the specified DAG node computes the value.  Note that it is an error
  /// to specify multiple DAG nodes that compute the same value.
  ///
  SelectionDAGNode *addNodeForValue(SelectionDAGNode *N, const Value *V) {
    assert(ValueMap.count(V) == 0 && "Value already has a DAG node!");
    return addNode(ValueMap[V] = N);
  }

  void dump() const;
private:
  void addInstructionToDAG(const Instruction &I, const BasicBlock &BB);
};


/// SelectionDAGReducedValue - During the reducer pass we need the ability to
/// add an arbitrary (but usually 1 or 0) number of arbitrarily sized values to
/// the selection DAG.  Because of this, we represent these values as a singly
/// linked list of values attached to the DAGNode.  We end up putting the
/// arbitrary state for the value in subclasses of this node.
///
/// Note that this class does not have a virtual dtor, this is because we know
/// that the subclasses will not hold state that needs to be destroyed.
///
class SelectionDAGReducedValue {
  unsigned Code;
  SelectionDAGReducedValue *Next;
public:
  SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {}

  /// getValueCode - Return the code for this reducer value...
  ///
  unsigned getValueCode() const { return Code; }
  
  /// getNext - Return the next value in the list
  ///
  const SelectionDAGReducedValue *getNext() const { return Next; }
  void setNext(SelectionDAGReducedValue *N) { Next = N; }

  SelectionDAGReducedValue *getNext() { return Next; }
};



/// SelectionDAGNode - Represents one node in the selection DAG.
///
class SelectionDAGNode {
  std::vector<SelectionDAGNode*> Uses;
  ISD::NodeType  NodeType;
  MVT::ValueType ValueType;
  MachineBasicBlock *BB;
  SelectionDAGReducedValue *ValList;

  /// Costs - Each pair of elements of 'Costs' contains the cost of producing
  /// the value with the target specific slot number and the production number
  /// to use to produce it.  A zero value for the production number indicates
  /// that the cost has not yet been computed.
  unsigned *Costs;
public:
  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT,
                   MachineBasicBlock *bb = 0) 
    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {}

  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
                   SelectionDAGNode *N)
    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
    Uses.reserve(1); Uses.push_back(N);
  }
  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
                   SelectionDAGNode *N1, SelectionDAGNode *N2)
    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
    Uses.reserve(2); Uses.push_back(N1); Uses.push_back(N2);
  }
  SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb,
                   SelectionDAGNode *N1, SelectionDAGNode *N2,
                   SelectionDAGNode *N3)
    : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {
    assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!");
    Uses.reserve(3); Uses.push_back(N1); Uses.push_back(N2); Uses.push_back(N3);
  }

  ~SelectionDAGNode() { delete [] Costs; delete ValList; }

  void setNode(ISD::NodeType NT, MachineBasicBlock *bb) {
    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
    NodeType = NT; BB = bb;
  }
  void setNode(ISD::NodeType NT, MachineBasicBlock *bb, SelectionDAGNode *N) {
    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
    NodeType = NT; BB = bb; Uses.reserve(1); Uses.push_back(N);
  }
  void setNode(ISD::NodeType NT, MachineBasicBlock *bb, 
               SelectionDAGNode *N1, SelectionDAGNode *N2) {
    assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode);
    NodeType = NT; BB = bb;
    Uses.reserve(1); Uses.push_back(N1); Uses.push_back(N2);
  }

  //===--------------------------------------------------------------------===//
  //  Accessors
  //
  ISD::NodeType  getNodeType()  const { return NodeType; }
  MVT::ValueType getValueType() const { return ValueType; }
  MachineBasicBlock *getBB() const { return BB; }

  SelectionDAGNode *getUse(unsigned Num) {
    assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!");
    return Uses[Num];
  }

  template<class Type>
  Type *getValue(unsigned Code) const {
    SelectionDAGReducedValue *Vals = ValList;
    while (1) {
      assert(Vals && "Code does not exist in this list!");
      if (Vals->getValueCode() == Code)
        return (Type*)Vals;
      Vals = Vals->getNext();
    }
  }