path: root/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

//===-- DAGCombiner.cpp - Implement a trivial DAG combiner ----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by Nate Begeman and is distributed under the
// University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass combines dag nodes to form fewer, simpler DAG nodes.  It can be run
// both before and after the DAG is legalized.
//
// FIXME: Missing folds
// sdiv, udiv, srem, urem (X, const) where X is an integer can be expanded into
//  a sequence of multiplies, shifts, and adds.  This should be controlled by
//  some kind of hint from the target that int div is expensive.
// various folds of mulh[s,u] by constants such as -1, powers of 2, etc.
//
// FIXME: Should add a corresponding version of fold AND with
// ZERO_EXTEND/SIGN_EXTEND by converting them to an ANY_EXTEND node which
// we don't have yet.
//
// FIXME: mul (x, const) -> shifts + adds
//
// FIXME: undef values
//
// FIXME: zero extend when top bits are 0 -> drop it ?
// 
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "dagcombine"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Target/TargetLowering.h"
#include <cmath>
using namespace llvm;

namespace {
  Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined");

  class DAGCombiner {
    SelectionDAG &DAG;
    TargetLowering &TLI;

    // Worklist of all of the nodes that need to be simplified.
    std::vector<SDNode*> WorkList;

    /// AddUsersToWorkList - When an instruction is simplified, add all users of
    /// the instruction to the work lists because they might get more simplified
    /// now.
    ///
    void AddUsersToWorkList(SDNode *N) {
      for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
           UI != UE; ++UI) {
        SDNode *U = *UI;
        for (unsigned i = 0, e = U->getNumOperands(); i != e; ++i)
          WorkList.push_back(U->getOperand(i).Val);
      }
    }

    /// removeFromWorkList - remove all instances of N from the worklist.
    void removeFromWorkList(SDNode *N) {
      WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
                     WorkList.end());
    }
    
    /// visit - call the node-specific routine that knows how to fold each
    /// particular type of node.
    SDNode *visit(SDNode *N);

    // Visitation implementation - Implement dag node combining for different
    // node types.  The semantics are as follows:
    // Return Value:
    //    null        - No change was made
    //   otherwise    - Node N should be replaced by the returned node.
    //
    SDNode *visitTokenFactor(SDNode *N);
    SDNode *visitAdd(SDNode *N);
    SDNode *visitSub(SDNode *N);
    SDNode *visitMul(SDNode *N);
    SDNode *visitSdiv(SDNode *N);
    SDNode *visitUdiv(SDNode *N);
    SDNode *visitSrem(SDNode *N);
    SDNode *visitUrem(SDNode *N);
    SDNode *visitMulHiU(SDNode *N);
    SDNode *visitMulHiS(SDNode *N);
    SDNode *visitAnd(SDNode *N);
    SDNode *visitOr(SDNode *N);
    SDNode *visitXor(SDNode *N);
    SDNode *visitShl(SDNode *N);
    SDNode *visitSra(SDNode *N);
    SDNode *visitSrl(SDNode *N);
    SDNode *visitCtlz(SDNode *N);
    SDNode *visitCttz(SDNode *N);
    SDNode *visitCtpop(SDNode *N);
    // select
    // select_cc
    // setcc
    SDNode *visitSignExtend(SDNode *N);
    SDNode *visitZeroExtend(SDNode *N);
    SDNode *visitSignExtendInReg(SDNode *N);
    SDNode *visitTruncate(SDNode *N);
    SDNode *visitSintToFP(SDNode *N);
    SDNode *visitUintToFP(SDNode *N);
    SDNode *visitFPToSint(SDNode *N);
    SDNode *visitFPToUint(SDNode *N);
    SDNode *visitFPRound(SDNode *N);
    SDNode *visitFPRoundInReg(SDNode *N);
    SDNode *visitFPExtend(SDNode *N);
    SDNode *visitFneg(SDNode *N);
    SDNode *visitFabs(SDNode *N);