//===- 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.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "cee"
#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/DerivedTypes.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Assembly/Writer.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>
using namespace llvm;
STATISTIC(NumCmpRemoved, "Number of cmp instruction eliminated");
STATISTIC(NumOperandsCann, "Number of operands canonicalized");
STATISTIC(BranchRevectors, "Number of branches revectored");
namespace {
class ValueInfo;
class Relation {
Value *Val; // Relation to what value?
unsigned<