path: root/lib/Transforms/Scalar/CorrelatedExprs.cpp

//===- CorrelatedExprs.cpp - Pass to detect and eliminated c.e.'s ---------===//
//
//                     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.
//
//===----------------------------------------------------------------------===//
//
// Correlated Expression Elimination propagates information from conditional
// branches to blocks dominated by destinations of the branch.  It propagates
// information from the condition check itself into the body of the branch,
// allowing transformations like these for example:
//
//  if (i == 7)
//    ... 4*i;  // constant propagation
//
//  M = i+1; N = j+1;
//  if (i == j)
//    X = M-N;  // = M-M == 0;
//
// This is called Correlated Expression Elimination because we eliminate or
// simplify expressions that are correlated with the direction of a branch.  In
// this way we use static information to give us some information about the
// dynamic value of a variable.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Pass.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include <algorithm>
#include <iostream>
using namespace llvm;

namespace {
  Statistic<> NumSetCCRemoved("cee", "Number of setcc instruction eliminated");
  Statistic<> NumOperandsCann("cee", "Number of operands canonicalized");
  Statistic<> BranchRevectors("cee", "Number of branches revectored");

  class ValueInfo;
  class Relation {
    Value *Val;                 // Relation to what value?
    Instruction::BinaryOps Rel; // SetCC relation, or Add if no information
  public:
    Relation(Value *V) : Val(V), Rel(Instruction::Add) {}
    bool operator<(const Relation &R) const { return Val < R.Val; }
    Value *getValue() const { return Val; }
    Instruction::BinaryOps getRelation() const { return Rel; }

    // contradicts - Return true if the relationship specified by the operand
    // contradicts already known information.
    //
    bool contradicts(Instruction::BinaryOps Rel, const ValueInfo &VI) const;

    // incorporate - Incorporate information in the argument into this relation
    // entry.  This assumes that the information doesn't contradict itself.  If
    // any new information is gained, true is returned, otherwise false is
    // returned to indicate that nothing was updated.
    //
    bool incorporate(Instruction::BinaryOps Rel, ValueInfo &VI);

    // KnownResult - Whether or not this condition determines the result of a
    // setcc in the program.  False & True are intentionally 0 & 1 so we can
    // convert to bool by casting after checking for unknown.
    //
    enum