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

//===-- PredicateSimplifier.cpp - Path Sensitive Simplifier ---------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by Nick Lewycky and is distributed under the
// University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Path-sensitive optimizer. In a branch where x == y, replace uses of
// x with y. Permits further optimization, such as the elimination of
// the unreachable call:
//
// void test(int *p, int *q)
// {
//   if (p != q)
//     return;
// 
//   if (*p != *q)
//     foo(); // unreachable
// }
//
//===----------------------------------------------------------------------===//
//
// This pass focusses on four properties; equals, not equals, less-than
// and less-than-or-equals-to. The greater-than forms are also held just
// to allow walking from a lesser node to a greater one. These properties
// are stored in a lattice; LE can become LT or EQ, NE can become LT or GT.
//
// These relationships define a graph between values of the same type. Each
// Value is stored in a map table that retrieves the associated Node. This
// is how EQ relationships are stored; the map contains pointers to the
// same node. The node contains a most canonical Value* form and the list of
// known relationships.
//
// If two nodes are known to be inequal, then they will contain pointers to
// each other with an "NE" relationship. If node getNode(%x) is less than
// getNode(%y), then the %x node will contain <%y, GT> and %y will contain
// <%x, LT>. This allows us to tie nodes together into a graph like this:
//
//   %a < %b < %c < %d
//
// with four nodes representing the properties. The InequalityGraph provides
// queries (such as "isEqual") and mutators (such as "addEqual"). To implement
// "isLess(%a, %c)", we start with getNode(%c) and walk downwards until
// we reach %a or the leaf node. Note that the graph is directed and acyclic,
// but may contain joins, meaning that this walk is not a linear time
// algorithm.
//
// To create these properties, we wait until a branch or switch instruction
// implies that a particular value is true (or false). The VRPSolver is
// responsible for analyzing the variable and seeing what new inferences
// can be made from each property. For example:
//
//   %P = seteq int* %ptr, null
//   %a = or bool %P, %Q
//   br bool %a label %cond_true, label %cond_false
//
// For the true branch, the VRPSolver will start with %a EQ true and look at
// the definition of %a and find that it can infer that %P and %Q are both
// true. From %P being true, it can infer that %ptr NE null. For the false
// branch it can't infer anything from the "or" instruction.
//
// Besides branches, we can also infer properties from instruction that may
// have undefined behaviour in certain cases. For example, the dividend of
// a division may never be zero. After the division instruction, we may assume
// that the dividend is not equal to zero.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "predsimplify"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ET-Forest.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <deque>
#include <iostream>
#include <sstream>
#include <map>
using namespace llvm;

namespace {
  Statistic<>
  NumVarsReplaced("predsimplify", "Number of argument substitutions");
  Statistic<>
  NumInstruction("predsimplify", "Number of instructions removed");
  Statistic<>
  NumSimple("predsimplify", "Number of simple replacements");

  /// The InequalityGraph stores the relationships between values.
  /// Each Value in the graph is assigned to a Node. Nodes are pointer
  /// comparable for equality. The caller is expected to maintain the logical
  /// consistency of the system.
  ///
  /// The InequalityGraph class may invalidate Node*s after any mutator call.