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

//===------- ABCD.cpp - Removes redundant conditional branches ------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass removes redundant branch instructions. This algorithm was
// described by Rastislav Bodik, Rajiv Gupta and Vivek Sarkar in their paper
// "ABCD: Eliminating Array Bounds Checks on Demand (2000)". The original
// Algorithm was created to remove array bound checks for strongly typed
// languages. This implementation expands the idea and removes any conditional
// branches that can be proved redundant, not only those used in array bound
// checks. With the SSI representation, each variable has a
// constraint. By analyzing these constraints we can prove that a branch is
// redundant. When a branch is proved redundant it means that
// one direction will always be taken; thus, we can change this branch into an
// unconditional jump.
// It is advisable to run SimplifyCFG and Aggressive Dead Code Elimination
// after ABCD to clean up the code.
// This implementation was created based on the implementation of the ABCD
// algorithm implemented for the compiler Jitrino.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "abcd"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/OwningPtr.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/SSI.h"

using namespace llvm;

STATISTIC(NumBranchTested, "Number of conditional branches analyzed");
STATISTIC(NumBranchRemoved, "Number of conditional branches removed");

namespace {

class ABCD : public FunctionPass {
 public:
  static char ID;  // Pass identification, replacement for typeid.
  ABCD() : FunctionPass(&ID) {}

  void getAnalysisUsage(AnalysisUsage &AU) const {
    AU.addRequired<SSI>();
  }

  bool runOnFunction(Function &F);

 private:
  /// Keep track of whether we've modified the program yet.
  bool modified;

  enum ProveResult {
    False = 0,
    Reduced = 1,
    True = 2
  };

  typedef ProveResult (*meet_function)(ProveResult, ProveResult);
  static ProveResult max(ProveResult res1, ProveResult res2) {
    return (ProveResult) std::max(res1, res2);
  }
  static ProveResult min(ProveResult res1, ProveResult res2) {
    return (ProveResult) std::min(res1, res2);
  }

  class Bound {
   public:
    Bound(APInt v, bool upper) : value(v), upper_bound(upper) {}
    Bound(const Bound &b, int cnst)
      : value(b.value - cnst), upper_bound(b.upper_bound) {}
    Bound(const Bound &b, const APInt &cnst)
      : value(b.value - cnst), upper_bound(b.upper_bound) {}

    /// Test if Bound is an upper bound
    bool isUpperBound() const { return upper_bound; }

    /// Get the bitwidth of this bound
    int32_t getBitWidth() const { return value.getBitWidth(); }

    /// Creates a Bound incrementing the one received
    static Bound createIncrement(const Bound &b) {
      return Bound(b.isUpperBound() ? b.value+1 : b.value-1,
                   b.upper_bound);
    }

    /// Creates a Bound decrementing the one received
    static Bound createDecrement(const Bound &b) {
      return Bound(b.isUpperBound() ? b.value-1 : b.value+1,
                   b.upper_bound);
    }

    /// Test if two bounds are equal
    static bool eq(const Bound *a, const Bound *b) {
      if (!a || !b) return false;

      assert(a->isUpperBound() == b->