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

//===- Reassociate.cpp - Reassociate binary expressions -------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass reassociates commutative expressions in an order that is designed
// to promote better constant propagation, GCSE, LICM, PRE...
//
// For example: 4 + (x + 5) -> x + (4 + 5)
//
// In the implementation of this algorithm, constants are assigned rank = 0,
// function arguments are rank = 1, and other values are assigned ranks
// corresponding to the reverse post order traversal of current function
// (starting at 2), which effectively gives values in deep loops higher rank
// than values not in loops.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "reassociate"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include <algorithm>
#include <map>
using namespace llvm;

STATISTIC(NumLinear , "Number of insts linearized");
STATISTIC(NumChanged, "Number of insts reassociated");
STATISTIC(NumAnnihil, "Number of expr tree annihilated");
STATISTIC(NumFactor , "Number of multiplies factored");

namespace {
  struct ValueEntry {
    unsigned Rank;
    Value *Op;
    ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
  };
  inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
    return LHS.Rank > RHS.Rank;   // Sort so that highest rank goes to start.
  }
}

#ifndef NDEBUG
/// PrintOps - Print out the expression identified in the Ops list.
///
static void PrintOps(Instruction *I, const std::vector<ValueEntry> &Ops) {
  Module *M = I->getParent()->getParent()->getParent();
  errs() << Instruction::getOpcodeName(I->getOpcode()) << " "
       << *Ops[0].Op->getType();
  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
    WriteAsOperand(errs() << " ", Ops[i].Op, false, M);
    errs() << "," << Ops[i].Rank;
  }
}
#endif
  
namespace {
  class Reassociate : public FunctionPass {
    std::map<BasicBlock*, unsigned> RankMap;
    std::map<AssertingVH<>, unsigned> ValueRankMap;
    bool MadeChange;
  public:
    static char ID; // Pass identification, replacement for typeid
    Reassociate() : FunctionPass(&ID) {}

    bool runOnFunction(Function &F);

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
    }
  private:
    void BuildRankMap(Function &F);
    unsigned getRank(Value *V);
    void ReassociateExpression(BinaryOperator *I);
    void RewriteExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops,
                         unsigned Idx = 0);
    Value *OptimizeExpression(BinaryOperator *I, std::vector<ValueEntry> &Ops);
    void LinearizeExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops);
    void LinearizeExpr(BinaryOperator *I);
    Value *RemoveFactorFromExpression(Value *V, Value *Factor);
    void ReassociateBB(BasicBlock *BB);
    
    void RemoveDeadBinaryOp(Value *V);
  };
}

char Reassociate::ID = 0;
static RegisterPass<Reassociate> X("reassociate", "Reassociate expressions");

// Public interface to the Reassociate pass
FunctionPass *llvm::createReassociatePass() { return new Reassociate(); }

void Reassociate::RemoveDeadBinaryOp(Value *V) {
  Instruction *Op = dyn_cast<Instruction>(V);
  if (!Op || !isa<BinaryOperator>(Op) || !isa<CmpInst>(Op) || !Op->use_empty())
    return;
  
  Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1);
  RemoveDeadBinaryOp(LHS);
  RemoveDeadBinaryOp(RHS);
}


static bool isUnmovableInstruction(Instruction *I) {
  if (I->getOpcode() == Instruction::PHI ||
      I->getOpcode() == Instruction::Alloca ||
      I->getOpcode() == Instruction::Load ||
      I->getOpcode() == Instruction::Malloc ||
      I->getOpcode() == Instruction::Invoke ||
      (I->getOpcode() == Instruction::Call &&
       !isa<DbgInfoIntrinsic>(I)) ||
      I->getOpcode() == Instruction::UDiv || 
      I->getOpcode() == Instruction::SDiv ||
      I->getOpcode() == Instruction::FDiv ||
      I->getOpcode()</