-
+//===- Reassociate.cpp - Reassociate binary expressions -------------------===//
//
// The LLVM Compiler Infrastructure
//
#define DEBUG_TYPE "reassociate"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Transforms/Utils/Local.h"
-#include "llvm/Constants.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Function.h"
-#include "llvm/IRBuilder.h"
-#include "llvm/Instructions.h"
-#include "llvm/IntrinsicInst.h"
-#include "llvm/Pass.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Assembly/Writer.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/Pass.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
-#include <deque>
-#include <set>
using namespace llvm;
STATISTIC(NumChanged, "Number of insts reassociated");
}
namespace {
-
- class Reassociate;
-
- class isInstDeadFunc {
- public:
- bool operator() (Instruction* I) {
- return isInstructionTriviallyDead(I);
- }
- };
-
- class RmInstCallBackFunc {
- Reassociate *reassoc_;
- public:
- RmInstCallBackFunc(Reassociate* ra): reassoc_(ra) {}
- inline void operator() (Instruction*);
- };
-
- // The worklist has following traits:
- // - it is pretty much a dequeue.
- // - has "set" semantic, meaning all elements in the worklist are distinct.
- // - efficient in-place element removal (by replacing the element with
- // invalid value 0).
- //
- class RedoWorklist {
- public:
- typedef AssertingVH<Instruction> value_type;
- typedef std::set<value_type> set_type;
- typedef std::deque<value_type> deque_type;
- // caller cannot modify element via iterator, hence constant.
- typedef deque_type::const_iterator iterator;
- typedef deque_type::const_iterator const_iterator;
- typedef deque_type::size_type size_type;
-
- RedoWorklist() {}
-
- bool empty() const {
- return deque_.empty();
- }
-
- size_type size() const {
- return deque_.size();
- }
-
- // return true iff X is in the worklist
- bool found(const value_type &X) {
- return set_.find(X) != set_.end();
- }
-
- iterator begin() {
- return deque_.begin();
- }
-
- const_iterator begin() const {
- return deque_.begin();
- }
-
- iterator end() {
- return deque_.end();
- }
-
- const_iterator end() const {
- return deque_.end();
- }
-
- const value_type &back() const {
- assert(!empty() && "worklist is empty");
- return deque_.back();
- }
-
- // If element X is already in the worklist, do nothing but return false;
- // otherwise, append X to the worklist and return true.
- //
- bool push_back(const value_type &X) {
- bool result = set_.insert(X).second;
- if (result)
- deque_.push_back(X);
- return result;
- }
-
- // insert() is the alias of push_back()
- bool insert(const value_type &X) {
- return push_back(X);
- }
-
- void clear() {
- set_.clear();
- deque_.clear();
- }
-
- void pop_back() {
- assert(!empty() && "worklist is empty");
- set_.erase(back());
- deque_.pop_back();
- }
-
- value_type pop_back_val() {
- value_type Ret = back();
- pop_back();
- return Ret;
- }
-
- const value_type &front() const {
- assert(!empty() && "worklist is empty");
- return deque_.front();
- }
-
- void pop_front() {
- assert(!empty() && "worklist is empty");
- set_.erase(front());
- deque_.pop_front();
- }
-
- value_type pop_front_val() {
- value_type Ret = front();
- pop_front();
- return Ret;
- }
-
- // Remove an element from the worklist. Return true iff the element was
- // in the worklist.
- bool remove(const value_type& X);
-
- template <typename pred, typename call_back_func>
- int inplace_remove(pred p, call_back_func cb);
-
- template <typename pred, typename call_back_func>
- int inplace_rremove(pred p, call_back_func cb);
-
- void append(RedoWorklist&);
-
- private:
- set_type set_;
- deque_type deque_;
- };
-
class Reassociate : public FunctionPass {
- friend class RmInstCallBackFunc;
-
DenseMap<BasicBlock*, unsigned> RankMap;
DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
- RedoWorklist RedoInsts;
- RedoWorklist TmpRedoInsts;
+ SetVector<AssertingVH<Instruction> > RedoInsts;
bool MadeChange;
public:
static char ID; // Pass identification, replacement for typeid
SmallVectorImpl<Factor> &Factors);
Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
SmallVectorImpl<Factor> &Factors);
- void removeNegFromMulOps(SmallVectorImpl<ValueEntry> &Ops);
Value *OptimizeMul(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
Value *RemoveFactorFromExpression(Value *V, Value *Factor);
void EraseInst(Instruction *I);
- void EraseInstCallBack(Instruction *I);
- void EraseAllDeadInst();
void OptimizeInst(Instruction *I);
};
}
return false;
}
-inline void RmInstCallBackFunc::operator() (Instruction* I) {
- reassoc_->EraseInstCallBack(I);
-}
-
-// Remove an item from the worklist. Return true iff the element was
-// in the worklist.
-bool RedoWorklist::remove(const value_type& X) {
- if (set_.erase(X)) {
- deque_type::iterator I = std::find(deque_.begin(), deque_.end(), X);
- assert(I != deque_.end() && "Can not find element");
- deque_.erase(I);
- return true;
- }
- return false;
-}
-
-// Forward go through each element e, calling p(e) to tell if e should be
-// removed or not; if p(e) = true, then e will be replaced with NULL to
-// indicate it is removed from the worklist, and functor cb will be
-// called for further processing on e. The functors should not invalidate
-// the iterator by inserting or deleteing element to and from the worklist.
-//
-// Returns the number of instruction being deleted.
-template <typename pred, typename call_back_func>
-int RedoWorklist::inplace_remove(pred p, call_back_func cb) {
- int cnt = 0;
- for (typename deque_type::iterator iter = deque_.begin(),
- iter_e = deque_.end(); iter != iter_e; iter++) {
- value_type &element = *iter;
- if (p(element) && set_.erase(element)) {
- Instruction* t = element;
- element.~value_type();
- new (&element) value_type(NULL);
- cb(t);
- cnt ++;
- }
- }
- return cnt;
-}
-
-// inplace_rremove() is the same as inplace_remove() except that elements
-// are visited in backward order.
-template <typename pred, typename call_back_func>
-int RedoWorklist::inplace_rremove(pred p, call_back_func cb) {
- int cnt = 0;
- for (typename deque_type::reverse_iterator iter = deque_.rbegin(),
- iter_e = deque_.rend(); iter != iter_e; iter++) {
- value_type &element = *iter;
- if (p(element) && set_.erase(element)) {
- Instruction* t = element;
- element.~value_type();
- new (&element) value_type(NULL);
- cb(t);
- cnt ++;
- }
- }
- return cnt;
-}
-
-void RedoWorklist::append(RedoWorklist& that) {
- deque_type &that_deque = that.deque_;
-
- while (!that_deque.empty()) {
- push_back(that_deque.front());
- that_deque.pop_front();
- }
- that.clear();
-}
-
void Reassociate::BuildRankMap(Function &F) {
unsigned i = 2;
}
}
-/// EvaluateRepeatedConstant - Compute C op C op ... op C where the constant C
-/// is repeated Weight times.
-static Constant *EvaluateRepeatedConstant(unsigned Opcode, Constant *C,
- APInt Weight) {
- // For addition the result can be efficiently computed as the product of the
- // constant and the weight.
- if (Opcode == Instruction::Add)
- return ConstantExpr::getMul(C, ConstantInt::get(C->getContext(), Weight));
-
- // The weight might be huge, so compute by repeated squaring to ensure that
- // compile time is proportional to the logarithm of the weight.
- Constant *Result = 0;
- Constant *Power = C; // Successively C, C op C, (C op C) op (C op C) etc.
- // Visit the bits in Weight.
- while (Weight != 0) {
- // If the current bit in Weight is non-zero do Result = Result op Power.
- if (Weight[0])
- Result = Result ? ConstantExpr::get(Opcode, Result, Power) : Power;
- // Move on to the next bit if any more are non-zero.
- Weight = Weight.lshr(1);
- if (Weight.isMinValue())
- break;
- // Square the power.
- Power = ConstantExpr::get(Opcode, Power, Power);
- }
-
- assert(Result && "Only positive weights supported!");
- return Result;
-}
-
typedef std::pair<Value*, APInt> RepeatedValue;
/// LinearizeExprTree - Given an associative binary expression, return the leaf
/// op
/// (Ops[N].first op Ops[N].first op ... Ops[N].first) <- Ops[N].second times
///
-/// Note that the values Ops[0].first, ..., Ops[N].first are all distinct, and
-/// they are all non-constant except possibly for the last one, which if it is
-/// constant will have weight one (Ops[N].second === 1).
+/// Note that the values Ops[0].first, ..., Ops[N].first are all distinct.
///
/// This routine may modify the function, in which case it returns 'true'. The
/// changes it makes may well be destructive, changing the value computed by 'I'
assert(Instruction::isAssociative(Opcode) &&
Instruction::isCommutative(Opcode) &&
"Expected an associative and commutative operation!");
- // If we see an absorbing element then the entire expression must be equal to
- // it. For example, if this is a multiplication expression and zero occurs as
- // an operand somewhere in it then the result of the expression must be zero.
- Constant *Absorber = ConstantExpr::getBinOpAbsorber(Opcode, I->getType());
// Visit all operands of the expression, keeping track of their weight (the
// number of paths from the expression root to the operand, or if you like
DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n");
assert(!Op->use_empty() && "No uses, so how did we get to it?!");
- // If the expression contains an absorbing element then there is no need
- // to analyze it further: it must evaluate to the absorbing element.
- if (Op == Absorber && !Weight.isMinValue()) {
- Ops.push_back(std::make_pair(Absorber, APInt(Bitwidth, 1)));
- return MadeChange;
- }
-
// If this is a binary operation of the right kind with only one use then
// add its operands to the expression.
if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
// The leaves, repeated according to their weights, represent the linearized
// form of the expression.
- Constant *Cst = 0; // Accumulate constants here.
for (unsigned i = 0, e = LeafOrder.size(); i != e; ++i) {
Value *V = LeafOrder[i];
LeafMap::iterator It = Leaves.find(V);
continue;
// Ensure the leaf is only output once.
It->second = 0;
- // Glob all constants together into Cst.
- if (Constant *C = dyn_cast<Constant>(V)) {
- C = EvaluateRepeatedConstant(Opcode, C, Weight);
- Cst = Cst ? ConstantExpr::get(Opcode, Cst, C) : C;
- continue;
- }
- // Add non-constant
Ops.push_back(std::make_pair(V, Weight));
}
- // Add any constants back into Ops, all globbed together and reduced to having
- // weight 1 for the convenience of users.
- Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, I->getType());
- if (Cst && Cst != Identity) {
- // If combining multiple constants resulted in the absorber then the entire
- // expression must evaluate to the absorber.
- if (Cst == Absorber)
- Ops.clear();
- Ops.push_back(std::make_pair(Cst, APInt(Bitwidth, 1)));
- }
-
// For nilpotent operations or addition there may be no operands, for example
// because the expression was "X xor X" or consisted of 2^Bitwidth additions:
// in both cases the weight reduces to 0 causing the value to be skipped.
if (Ops.empty()) {
+ Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, I->getType());
assert(Identity && "Associative operation without identity!");
Ops.push_back(std::make_pair(Identity, APInt(Bitwidth, 1)));
}
SmallVectorImpl<ValueEntry> &Ops) {
assert(Ops.size() > 1 && "Single values should be used directly!");
- // Since our optimizations never increase the number of operations, the new
- // expression can always be written by reusing the existing binary operators
+ // Since our optimizations should never increase the number of operations, the
+ // new expression can usually be written reusing the existing binary operators
// from the original expression tree, without creating any new instructions,
// though the rewritten expression may have a completely different topology.
// We take care to not change anything if the new expression will be the same
unsigned Opcode = I->getOpcode();
BinaryOperator *Op = I;
+ /// NotRewritable - The operands being written will be the leaves of the new
+ /// expression and must not be used as inner nodes (via NodesToRewrite) by
+ /// mistake. Inner nodes are always reassociable, and usually leaves are not
+ /// (if they were they would have been incorporated into the expression and so
+ /// would not be leaves), so most of the time there is no danger of this. But
+ /// in rare cases a leaf may become reassociable if an optimization kills uses
+ /// of it, or it may momentarily become reassociable during rewriting (below)
+ /// due it being removed as an operand of one of its uses. Ensure that misuse
+ /// of leaf nodes as inner nodes cannot occur by remembering all of the future
+ /// leaves and refusing to reuse any of them as inner nodes.
+ SmallPtrSet<Value*, 8> NotRewritable;
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+ NotRewritable.insert(Ops[i].Op);
+
// ExpressionChanged - Non-null if the rewritten expression differs from the
// original in some non-trivial way, requiring the clearing of optional flags.
// Flags are cleared from the operator in ExpressionChanged up to I inclusive.
// the old operands with the new ones.
DEBUG(dbgs() << "RA: " << *Op << '\n');
if (NewLHS != OldLHS) {
- if (BinaryOperator *BO = isReassociableOp(OldLHS, Opcode))
+ BinaryOperator *BO = isReassociableOp(OldLHS, Opcode);
+ if (BO && !NotRewritable.count(BO))
NodesToRewrite.push_back(BO);
Op->setOperand(0, NewLHS);
}
if (NewRHS != OldRHS) {
- if (BinaryOperator *BO = isReassociableOp(OldRHS, Opcode))
+ BinaryOperator *BO = isReassociableOp(OldRHS, Opcode);
+ if (BO && !NotRewritable.count(BO))
NodesToRewrite.push_back(BO);
Op->setOperand(1, NewRHS);
}
Op->swapOperands();
} else {
// Overwrite with the new right-hand side.
- if (BinaryOperator *BO = isReassociableOp(Op->getOperand(1), Opcode))
+ BinaryOperator *BO = isReassociableOp(Op->getOperand(1), Opcode);
+ if (BO && !NotRewritable.count(BO))
NodesToRewrite.push_back(BO);
Op->setOperand(1, NewRHS);
ExpressionChanged = Op;
// Now deal with the left-hand side. If this is already an operation node
// from the original expression then just rewrite the rest of the expression
// into it.
- if (BinaryOperator *BO = isReassociableOp(Op->getOperand(0), Opcode)) {
+ BinaryOperator *BO = isReassociableOp(Op->getOperand(0), Opcode);
+ if (BO && !NotRewritable.count(BO)) {
Op = BO;
continue;
}
return V;
}
-// Multiply Ops may have some negation operators. This situation arises
-// when the negation operators have multiple uses, and LinearizeExprTree() has
-// to treat them as leaf operands. Before multiplication optimization begins,
-// get rid of the negations wherever possible.
-void Reassociate::removeNegFromMulOps(SmallVectorImpl<ValueEntry> &Ops) {
- int32_t NegIdx = -1;
-
- // loop over all elements except the last one
- for (int32_t Idx = 0, IdxEnd = Ops.size() - 1; Idx < IdxEnd; Idx++) {
- ValueEntry &VE = Ops[Idx];
- if (!BinaryOperator::isNeg(VE.Op))
- continue;
-
- if (NegIdx < 0) {
- NegIdx = Idx;
- continue;
- }
-
- // Find a pair of negation operators, say -X and -Y, change them to
- // X and Y respectively.
- ValueEntry &VEX = Ops[NegIdx];
- Value *OpX = cast<BinaryOperator>(VEX.Op)->getOperand(1);
- VEX.Op = OpX;
- VEX.Rank = getRank(OpX);
-
- Value *OpY = cast<BinaryOperator>(VE.Op)->getOperand(1);
- VE.Op = OpY;
- VE.Rank = getRank(OpY);
- NegIdx = -1;
- }
-
- if (NegIdx >= 0) {
- // We have visited odd number of negation operators so far.
- // Check if the last element is negation as well.
- ValueEntry &Last = Ops.back();
- Value *LastOp = Last.Op;
- if (!isa<ConstantInt>(LastOp) && !BinaryOperator::isNeg(LastOp))
- return;
-
- ValueEntry& PrevNeg = Ops[NegIdx];
- Value *Op = cast<BinaryOperator>(PrevNeg.Op)->getOperand(1);
- PrevNeg.Op = Op;
- PrevNeg.Rank = getRank(Op);
-
- if (isa<ConstantInt>(LastOp))
- Last.Op = ConstantExpr::getNeg(cast<Constant>(LastOp));
- else {
- LastOp = cast<BinaryOperator>(PrevNeg.Op)->getOperand(1);
- Last.Op = LastOp;
- Last.Rank = getRank(LastOp);
- }
- }
-}
-
Value *Reassociate::OptimizeMul(BinaryOperator *I,
SmallVectorImpl<ValueEntry> &Ops) {
-
- // Simplify the operands: (-x)*(-y) -> x*y, and (-x)*c -> x*(-c)
- removeNegFromMulOps(Ops);
-
// We can only optimize the multiplies when there is a chain of more than
// three, such that a balanced tree might require fewer total multiplies.
if (Ops.size() < 4)
SmallVectorImpl<ValueEntry> &Ops) {
// Now that we have the linearized expression tree, try to optimize it.
// Start by folding any constants that we found.
- if (Ops.size() == 1) return Ops[0].Op;
-
+ Constant *Cst = 0;
unsigned Opcode = I->getOpcode();
+ while (!Ops.empty() && isa<Constant>(Ops.back().Op)) {
+ Constant *C = cast<Constant>(Ops.pop_back_val().Op);
+ Cst = Cst ? ConstantExpr::get(Opcode, C, Cst) : C;
+ }
+ // If there was nothing but constants then we are done.
+ if (Ops.empty())
+ return Cst;
+
+ // Put the combined constant back at the end of the operand list, except if
+ // there is no point. For example, an add of 0 gets dropped here, while a
+ // multiplication by zero turns the whole expression into zero.
+ if (Cst && Cst != ConstantExpr::getBinOpIdentity(Opcode, I->getType())) {
+ if (Cst == ConstantExpr::getBinOpAbsorber(Opcode, I->getType()))
+ return Cst;
+ Ops.push_back(ValueEntry(0, Cst));
+ }
+
+ if (Ops.size() == 1) return Ops[0].Op;
// Handle destructive annihilation due to identities between elements in the
// argument list here.
return 0;
}
-// EraseInstCallBack is a helper function of EraseInst which will be called to
-// delete an individual instruction, and it is also a callback funciton when
-// EraseAllDeadInst is called to delete all dead instruciton in the Redo
-// worklist (RedoInsts).
-//
-void Reassociate::EraseInstCallBack(Instruction *I) {
- DEBUG(dbgs() << "Erase instruction :" << *I << "\n");
+/// EraseInst - Zap the given instruction, adding interesting operands to the
+/// work list.
+void Reassociate::EraseInst(Instruction *I) {
assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
// Erase the dead instruction.
ValueRankMap.erase(I);
+ RedoInsts.remove(I);
I->eraseFromParent();
// Optimize its operands.
SmallPtrSet<Instruction *, 8> Visited; // Detect self-referential nodes.
while (Op->hasOneUse() && Op->use_back()->getOpcode() == Opcode &&
Visited.insert(Op))
Op = Op->use_back();
-
- // The caller may be itearating the RedoInsts. Inserting a new element to
- // RedoInsts will invaidate the iterator. Instead, we temporally place the
- // new candidate to TmpRedoInsts. It is up to caller to combine
- // TmpRedoInsts and RedoInsts together.
- //
- if (!RedoInsts.found(Op))
- TmpRedoInsts.insert(Op);
+ RedoInsts.insert(Op);
}
}
-/// EraseInst - Zap the given instruction, adding interesting operands to the
-/// work list.
-void Reassociate::EraseInst(Instruction *I) {
- RedoInsts.remove(I);
-
- // Since EraseInstCallBack() put new reassociation candidates to TmpRedoInsts
- // we need to copy the candidates back to RedoInsts.
- TmpRedoInsts.clear();
- EraseInstCallBack(I);
- RedoInsts.append(TmpRedoInsts);
-}
-
-/// EraseAllDeadInst - Remove all dead instructions from the worklist.
-void Reassociate::EraseAllDeadInst() {
- TmpRedoInsts.clear();
- RedoInsts.inplace_rremove(isInstDeadFunc(), RmInstCallBackFunc(this));
- RedoInsts.append(TmpRedoInsts);
-}
-
/// OptimizeInst - Inspect and optimize the given instruction. Note that erasing
/// instructions is not allowed.
void Reassociate::OptimizeInst(Instruction *I) {
if (!isa<BinaryOperator>(I))
return;
- DEBUG(dbgs() << "\n>Opt Instruction: " << *I << '\n');
-
if (I->getOpcode() == Instruction::Shl &&
isa<ConstantInt>(I->getOperand(1)))
// If an operand of this shift is a reassociable multiply, or if the shift
++II;
}
- DEBUG(dbgs() << "Process instructions in worklist\n");
- EraseAllDeadInst();
-
// If this produced extra instructions to optimize, handle them now.
while (!RedoInsts.empty()) {
- Instruction *I = RedoInsts.pop_front_val();
- if (!I)
- continue;
+ Instruction *I = RedoInsts.pop_back_val();
if (isInstructionTriviallyDead(I))
EraseInst(I);
else
projects / oota-llvm.git / blobdiff