1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This pass reassociates commutative expressions in an order that is designed 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// to promote better constant propagation, GCSE, LICM, PRE, etc. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// For example: 4 + (x + 5) -> x + (4 + 5) 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// In the implementation of this algorithm, constants are assigned rank = 0, 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// function arguments are rank = 1, and other values are assigned ranks 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// corresponding to the reverse post order traversal of current function 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// (starting at 2), which effectively gives values in deep loops higher rank 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// than values not in loops. 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define DEBUG_TYPE "reassociate" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Scalar.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Transforms/Utils/Local.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Constants.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/DerivedTypes.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Function.h" 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instructions.h" 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/IntrinsicInst.h" 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Pass.h" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Assembly/Writer.h" 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/CFG.h" 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/ValueHandle.h" 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/PostOrderIterator.h" 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/Statistic.h" 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMap.h" 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <algorithm> 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumLinear , "Number of insts linearized"); 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumChanged, "Number of insts reassociated"); 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumAnnihil, "Number of expr tree annihilated"); 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumFactor , "Number of multiplies factored"); 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct ValueEntry { 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Rank; 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Op; 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// PrintOps - Print out the expression identified in the Ops list. 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) { 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Module *M = I->getParent()->getParent()->getParent(); 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << Instruction::getOpcodeName(I->getOpcode()) << " " 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << *Ops[0].Op->getType() << '\t'; 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "[ "; 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WriteAsOperand(dbgs(), Ops[i].Op, false, M); 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << ", #" << Ops[i].Rank << "] "; 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class Reassociate : public FunctionPass { 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<BasicBlock*, unsigned> RankMap; 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<AssertingVH<>, unsigned> ValueRankMap; 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<WeakVH, 8> RedoInsts; 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<WeakVH, 8> DeadInsts; 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange; 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification, replacement for typeid 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Reassociate() : FunctionPass(ID) { 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeReassociatePass(*PassRegistry::getPassRegistry()); 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool runOnFunction(Function &F); 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.setPreservesCFG(); 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void BuildRankMap(Function &F); 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getRank(Value *V); 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *ReassociateExpression(BinaryOperator *I); 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops, 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Idx = 0); 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *OptimizeExpression(BinaryOperator *I, 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<ValueEntry> &Ops); 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops); 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void LinearizeExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void LinearizeExpr(BinaryOperator *I); 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *RemoveFactorFromExpression(Value *V, Value *Factor); 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void ReassociateInst(BasicBlock::iterator &BBI); 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void RemoveDeadBinaryOp(Value *V); 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar Reassociate::ID = 0; 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanINITIALIZE_PASS(Reassociate, "reassociate", 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Reassociate expressions", false, false) 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Public interface to the Reassociate pass 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanFunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid Reassociate::RemoveDeadBinaryOp(Value *V) { 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *Op = dyn_cast<Instruction>(V); 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Op || !isa<BinaryOperator>(Op)) 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1); 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueRankMap.erase(Op); 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DeadInsts.push_back(Op); 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemoveDeadBinaryOp(LHS); 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemoveDeadBinaryOp(RHS); 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool isUnmovableInstruction(Instruction *I) { 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getOpcode() == Instruction::PHI || 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() == Instruction::Alloca || 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() == Instruction::Load || 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I->getOpcode() == Instruction::Invoke || 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (I->getOpcode() == Instruction::Call && 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !isa<DbgInfoIntrinsic>(I)) || 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() == Instruction::UDiv || 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() == Instruction::SDiv || 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() == Instruction::FDiv || 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() == Instruction::URem || 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() == Instruction::SRem || 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOpcode() == Instruction::FRem) 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid Reassociate::BuildRankMap(Function &F) { 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned i = 2; 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Assign distinct ranks to function arguments 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueRankMap[&*I] = ++i; 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ReversePostOrderTraversal<Function*> RPOT(&F); 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = RPOT.end(); I != E; ++I) { 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *BB = *I; 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned BBRank = RankMap[BB] = ++i << 16; 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Walk the basic block, adding precomputed ranks for any instructions that 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // we cannot move. This ensures that the ranks for these instructions are 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // all different in the block. 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isUnmovableInstruction(I)) 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueRankMap[&*I] = ++BBRank; 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanunsigned Reassociate::getRank(Value *V) { 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *I = dyn_cast<Instruction>(V); 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I == 0) { 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument. 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; // Otherwise it's a global or constant, rank 0. 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (unsigned Rank = ValueRankMap[I]) 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Rank; // Rank already known? 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // we can reassociate expressions for code motion! Since we do not recurse 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // for PHI nodes, we cannot have infinite recursion here, because there 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // cannot be loops in the value graph that do not go through PHI nodes. 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = I->getNumOperands(); 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman i != e && Rank != MaxRank; ++i) 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Rank = std::max(Rank, getRank(I->getOperand(i))); 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a not or neg instruction, do not count it for rank. This 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // assures us that X and ~X will have the same rank. 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!I->getType()->isIntegerTy() || 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Rank; 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = " 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // << Rank << "\n"); 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return ValueRankMap[I] = Rank; 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// isReassociableOp - Return true if V is an instruction of the specified 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// opcode and if it only has one use. 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((V->hasOneUse() || V->use_empty()) && isa<Instruction>(V) && 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<Instruction>(V)->getOpcode() == Opcode) 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return cast<BinaryOperator>(V); 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// LowerNegateToMultiply - Replace 0-X with X*-1. 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic Instruction *LowerNegateToMultiply(Instruction *Neg, 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<AssertingVH<>, unsigned> &ValueRankMap) { 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Constant *Cst = Constant::getAllOnesValue(Neg->getType()); 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *Res = BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg); 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueRankMap.erase(Neg); 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Res->takeName(Neg); 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Neg->replaceAllUsesWith(Res); 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Res->setDebugLoc(Neg->getDebugLoc()); 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Neg->eraseFromParent(); 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Res; 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Note that if D is also part of the expression tree that we recurse to 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// linearize it as well. Besides that case, this does not recurse into A,B, or 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// C. 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid Reassociate::LinearizeExpr(BinaryOperator *I) { 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1)); 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(isReassociableOp(LHS, I->getOpcode()) && 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isReassociableOp(RHS, I->getOpcode()) && 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Not an expression that needs linearization?"); 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Linear" << *LHS << '\n' << *RHS << '\n' << *I << '\n'); 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Move the RHS instruction to live immediately before I, avoiding breaking 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // dominator properties. 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHS->moveBefore(I); 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Move operands around to do the linearization. 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(1, RHS->getOperand(0)); 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHS->setOperand(0, LHS); 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(0, RHS); 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Conservatively clear all the optional flags, which may not hold 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // after the reassociation. 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I->clearSubclassOptionalData(); 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHS->clearSubclassOptionalData(); 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RHS->clearSubclassOptionalData(); 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumLinear; 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Linearized: " << *I << '\n'); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If D is part of this expression tree, tail recurse. 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isReassociableOp(I->getOperand(1), I->getOpcode())) 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LinearizeExpr(I); 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// LinearizeExprTree - Given an associative binary expression tree, traverse 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// all of the uses putting it into canonical form. This forces a left-linear 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// form of the expression (((a+b)+c)+d), and collects information about the 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// rank of the non-tree operands. 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// NOTE: These intentionally destroys the expression tree operands (turning 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// them into undef values) to reduce #uses of the values. This means that the 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// caller MUST use something like RewriteExprTree to put the values back in. 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid Reassociate::LinearizeExprTree(BinaryOperator *I, 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<ValueEntry> &Ops) { 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Opcode = I->getOpcode(); 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // First step, linearize the expression if it is in ((A+B)+(C+D)) form. 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a multiply expression tree and it contains internal negations, 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // transform them into multiplies by -1 so they can be reassociated. 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getOpcode() == Instruction::Mul) { 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!LHSBO && LHS->hasOneUse() && BinaryOperator::isNeg(LHS)) { 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LHS = LowerNegateToMultiply(cast<Instruction>(LHS), ValueRankMap); 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LHSBO = isReassociableOp(LHS, Opcode); 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!RHSBO && RHS->hasOneUse() && BinaryOperator::isNeg(RHS)) { 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHS = LowerNegateToMultiply(cast<Instruction>(RHS), ValueRankMap); 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHSBO = isReassociableOp(RHS, Opcode); 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!LHSBO) { 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!RHSBO) { 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Neither the LHS or RHS as part of the tree, thus this is a leaf. As 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // such, just remember these operands and their rank. 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.push_back(ValueEntry(getRank(LHS), LHS)); 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.push_back(ValueEntry(getRank(RHS), RHS)); 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Clear the leaves out. 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(0, UndefValue::get(I->getType())); 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(1, UndefValue::get(I->getType())); 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Turn X+(Y+Z) -> (Y+Z)+X 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(LHSBO, RHSBO); 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(LHS, RHS); 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Success = !I->swapOperands(); 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Success && "swapOperands failed"); 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)Success; 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (RHSBO) { 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the RHS is not 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // part of the expression tree. 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LinearizeExpr(I); 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0)); 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHS = I->getOperand(1); 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHSBO = 0; 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, now we know that the LHS is a nested expression and that the RHS is 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not. Perform reassociation. 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Move LHS right before I to make sure that the tree expression dominates all 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // values. 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LHSBO->moveBefore(I); 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Linearize the expression tree on the LHS. 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LinearizeExprTree(LHSBO, Ops); 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember the RHS operand and its rank. 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.push_back(ValueEntry(getRank(RHS), RHS)); 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Clear the RHS leaf out. 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(1, UndefValue::get(I->getType())); 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// RewriteExprTree - Now that the operands for this expression tree are 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// linearized and optimized, emit them in-order. This function is written to be 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// tail recursive. 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid Reassociate::RewriteExprTree(BinaryOperator *I, 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<ValueEntry> &Ops, 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned i) { 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i+2 == Ops.size()) { 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getOperand(0) != Ops[i].Op || 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->getOperand(1) != Ops[i+1].Op) { 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *OldLHS = I->getOperand(0); 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "RA: " << *I << '\n'); 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(0, Ops[i].Op); 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(1, Ops[i+1].Op); 35419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Clear all the optional flags, which may not hold after the 35619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // reassociation if the expression involved more than just this operation. 35719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Ops.size() != 2) 35819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I->clearSubclassOptionalData(); 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "TO: " << *I << '\n'); 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumChanged; 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we reassociated a tree to fewer operands (e.g. (1+a+2) -> (a+3) 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // delete the extra, now dead, nodes. 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemoveDeadBinaryOp(OldLHS); 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(i+2 < Ops.size() && "Ops index out of range!"); 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getOperand(1) != Ops[i].Op) { 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "RA: " << *I << '\n'); 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(1, Ops[i].Op); 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Conservatively clear all the optional flags, which may not hold 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // after the reassociation. 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I->clearSubclassOptionalData(); 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "TO: " << *I << '\n'); 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumChanged; 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(LHS->getOpcode() == I->getOpcode() && 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Improper expression tree!"); 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compactify the tree instructions together with each other to guarantee 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // that the expression tree is dominated by all of Ops. 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LHS->moveBefore(I); 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RewriteExprTree(LHS, Ops, i+1); 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// NegateValue - Insert instructions before the instruction pointed to by BI, 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// that computes the negative version of the value specified. The negative 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// version of the value is returned, and BI is left pointing at the instruction 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// that should be processed next by the reassociation pass. 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic Value *NegateValue(Value *V, Instruction *BI) { 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Constant *C = dyn_cast<Constant>(V)) 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return ConstantExpr::getNeg(C); 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We are trying to expose opportunity for reassociation. One of the things 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // that we want to do to achieve this is to push a negation as deep into an 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // expression chain as possible, to expose the add instructions. In practice, 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this means that we turn this: 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the constants. We assume that instcombine will clean up the mess later if 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // we introduce tons of unnecessary negation instructions. 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Instruction *I = dyn_cast<Instruction>(V)) 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Push the negates through the add. 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(0, NegateValue(I->getOperand(0), BI)); 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(1, NegateValue(I->getOperand(1), BI)); 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We must move the add instruction here, because the neg instructions do 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not dominate the old add instruction in general. By moving it, we are 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // assured that the neg instructions we just inserted dominate the 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instruction we are about to insert after them. 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->moveBefore(BI); 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setName(I->getName()+".neg"); 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return I; 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, we need to materialize a negated version of V with an instruction. 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan the use lists of V to see if we have one already. 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){ 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman User *U = *UI; 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!BinaryOperator::isNeg(U)) continue; 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We found one! Now we have to make sure that the definition dominates 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this use. We do this by moving it to the entry block (if it is a 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // non-instruction value) or right after the definition. These negates will 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // be zapped by reassociate later, so we don't need much finesse here. 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *TheNeg = cast<BinaryOperator>(U); 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Verify that the negate is in this function, V might be a constant expr. 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TheNeg->getParent()->getParent() != BI->getParent()->getParent()) 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock::iterator InsertPt; 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Instruction *InstInput = dyn_cast<Instruction>(V)) { 44919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) { 45019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InsertPt = II->getNormalDest()->begin(); 45119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertPt = InstInput; 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++InsertPt; 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (isa<PHINode>(InsertPt)) ++InsertPt; 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin(); 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheNeg->moveBefore(InsertPt); 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return TheNeg; 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert a 'neg' instruction that subtracts the value from zero to get the 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // negation. 46519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return BinaryOperator::CreateNeg(V, V->getName() + ".neg", BI); 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ShouldBreakUpSubtract - Return true if we should break up this subtract of 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// X-Y into (X + -Y). 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool ShouldBreakUpSubtract(Instruction *Sub) { 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a negation, we can't split it up! 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BinaryOperator::isNeg(Sub)) 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Don't bother to break this up unless either the LHS is an associable add or 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // subtract or if this is only used by one. 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isReassociableOp(Sub->getOperand(0), Instruction::Add) || 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isReassociableOp(Sub->getOperand(0), Instruction::Sub)) 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isReassociableOp(Sub->getOperand(1), Instruction::Add) || 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isReassociableOp(Sub->getOperand(1), Instruction::Sub)) 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Sub->hasOneUse() && 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (isReassociableOp(Sub->use_back(), Instruction::Add) || 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isReassociableOp(Sub->use_back(), Instruction::Sub))) 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// only used by an add, transform this into (X+(0-Y)) to promote better 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// reassociation. 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic Instruction *BreakUpSubtract(Instruction *Sub, 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<AssertingVH<>, unsigned> &ValueRankMap) { 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Convert a subtract into an add and a neg instruction. This allows sub 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instructions to be commuted with other add instructions. 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Calculate the negative value of Operand 1 of the sub instruction, 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and set it as the RHS of the add instruction we just made. 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *New = 50419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub); 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman New->takeName(Sub); 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Everyone now refers to the add instruction. 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueRankMap.erase(Sub); 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Sub->replaceAllUsesWith(New); 51019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman New->setDebugLoc(Sub->getDebugLoc()); 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Sub->eraseFromParent(); 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Negated: " << *New << '\n'); 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return New; 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// by one, change this into a multiply by a constant to assist with further 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// reassociation. 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic Instruction *ConvertShiftToMul(Instruction *Shl, 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<AssertingVH<>, unsigned> &ValueRankMap) { 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If an operand of this shift is a reassociable multiply, or if the shift 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // is used by a reassociable multiply or add, turn into a multiply. 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isReassociableOp(Shl->getOperand(0), Instruction::Mul) || 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (Shl->hasOneUse() && 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (isReassociableOp(Shl->use_back(), Instruction::Mul) || 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isReassociableOp(Shl->use_back(), Instruction::Add)))) { 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *Mul = 53219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl); 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueRankMap.erase(Shl); 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mul->takeName(Shl); 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Shl->replaceAllUsesWith(Mul); 53619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Mul->setDebugLoc(Shl->getDebugLoc()); 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Shl->eraseFromParent(); 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Mul; 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Scan backwards and forwards among values with the same rank as element i to 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// see if X exists. If X does not exist, return i. This is useful when 545894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// scanning for 'x' when we see '-x' because they both get the same rank. 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic unsigned FindInOperandList(SmallVectorImpl<ValueEntry> &Ops, unsigned i, 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *X) { 548894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned XRank = Ops[i].Rank; 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned e = Ops.size(); 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops[j].Op == X) 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return j; 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan backwards. 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops[j].Op == X) 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return j; 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return i; 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// and returning the result. Insert the tree before I. 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic Value *EmitAddTreeOfValues(Instruction *I, SmallVectorImpl<Value*> &Ops){ 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops.size() == 1) return Ops.back(); 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V1 = Ops.back(); 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.pop_back(); 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V2 = EmitAddTreeOfValues(I, Ops); 56819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return BinaryOperator::CreateAdd(V2, V1, "tmp", I); 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RemoveFactorFromExpression - If V is an expression tree that is a 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// multiplication sequence, and if this sequence contains a multiply by Factor, 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// remove Factor from the tree and return the new tree. 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanValue *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *BO = isReassociableOp(V, Instruction::Mul); 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!BO) return 0; 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<ValueEntry, 8> Factors; 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LinearizeExprTree(BO, Factors); 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool FoundFactor = false; 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool NeedsNegate = false; 583894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Factors[i].Op == Factor) { 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundFactor = true; 586894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Factors.erase(Factors.begin()+i); 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 588894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 590894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a negative version of this factor, remove it. 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *FC1 = dyn_cast<ConstantInt>(Factor)) 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op)) 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FC1->getValue() == -FC2->getValue()) { 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundFactor = NeedsNegate = true; 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Factors.erase(Factors.begin()+i); 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!FoundFactor) { 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make sure to restore the operands to the expression tree. 602894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RewriteExprTree(BO, Factors); 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock::iterator InsertPt = BO; ++InsertPt; 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this was just a single multiply, remove the multiply and return the only 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // remaining operand. 610894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Factors.size() == 1) { 611894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueRankMap.erase(BO); 61219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DeadInsts.push_back(BO); 613894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V = Factors[0].Op; 614894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 615894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RewriteExprTree(BO, Factors); 616894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V = BO; 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 618894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NeedsNegate) 62019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = BinaryOperator::CreateNeg(V, "neg", InsertPt); 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V; 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 625894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// add its operands as factors, otherwise add V to the list of factors. 627894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Ops is the top-level list of add operands we're trying to factor. 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic void FindSingleUseMultiplyFactors(Value *V, 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<Value*> &Factors, 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SmallVectorImpl<ValueEntry> &Ops, 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool IsRoot) { 633894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *BO; 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!(V->hasOneUse() || V->use_empty()) || // More than one use. 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !(BO = dyn_cast<BinaryOperator>(V)) || 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BO->getOpcode() != Instruction::Mul) { 637894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Factors.push_back(V); 638894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 639894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this value has a single use because it is another input to the add 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // tree we're reassociating and we dropped its use, it actually has two 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // uses and we can't factor it. 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!IsRoot) { 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Ops.size(); i != e; ++i) 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops[i].Op == V) { 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Factors.push_back(V); 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 649894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, add the LHS and RHS to the list of factors. 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FindSingleUseMultiplyFactors(BO->getOperand(1), Factors, Ops, false); 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops, false); 656894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 657894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 658894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor' 659894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// instruction. This optimizes based on identities. If it can be reduced to 660894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// a single Value, it is returned, otherwise the Ops list is mutated as 661894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// necessary. 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic Value *OptimizeAndOrXor(unsigned Opcode, 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<ValueEntry> &Ops) { 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 665894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 666894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // First, check for X and ~X in the operand list. 668894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(i < Ops.size()); 669894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 670894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 671894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned FoundX = FindInOperandList(Ops, i, X); 672894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FoundX != i) { 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Opcode == Instruction::And) // ...&X&~X = 0 674894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Constant::getNullValue(X->getType()); 675894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 676894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Opcode == Instruction::Or) // ...|X|~X = -1 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Constant::getAllOnesValue(X->getType()); 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 680894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 681894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Next, check for duplicate pairs of values, which we assume are next to 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // each other, due to our sorting criteria. 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(i < Ops.size()); 684894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Opcode == Instruction::And || Opcode == Instruction::Or) { 686894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Drop duplicate values for And and Or. 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.erase(Ops.begin()+i); 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --i; --e; 689894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumAnnihil; 690894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 691894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 692894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 693894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Drop pairs of values for Xor. 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Opcode == Instruction::Xor); 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (e == 2) 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Constant::getNullValue(Ops[0].Op->getType()); 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Y ^ X^X -> Y 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman i -= 1; e -= 2; 701894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumAnnihil; 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 705894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 706894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 707894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OptimizeAdd - Optimize a series of operands to an 'add' instruction. This 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// optimizes based on identities. If it can be reduced to a single Value, it 709894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// is returned, otherwise the Ops list is mutated as necessary. 710894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanValue *Reassociate::OptimizeAdd(Instruction *I, 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<ValueEntry> &Ops) { 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan the operand lists looking for X and -X pairs. If we find any, we 713894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // can simplify the expression. X+-X == 0. While we're at it, scan for any 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // duplicates. We want to canonicalize Y+Y+Y+Z -> 3*Y+Z. 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 716894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: We could handle "X + ~X" -> "-1" if we wanted, since "-X = ~X+1". 717894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 718894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 719894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *TheOp = Ops[i].Op; 720894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if we've seen this operand before. If so, we factor all 721894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instances of the operand together. Due to our sorting criteria, we know 722894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // that these need to be next to each other in the vector. 723894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) { 724894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Rescan the list, remove all instances of this operand from the expr. 725894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumFound = 0; 726894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 727894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.erase(Ops.begin()+i); 728894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumFound; 729894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (i != Ops.size() && Ops[i].Op == TheOp); 730894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 731894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(errs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n'); 732894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumFactor; 733894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 734894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert a new multiply. 735894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Mul = ConstantInt::get(cast<IntegerType>(I->getType()), NumFound); 73619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Mul = BinaryOperator::CreateMul(TheOp, Mul, "factor", I); 737894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 738894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we have inserted a multiply, optimize it. This allows us to 739894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // handle cases that require multiple factoring steps, such as this: 740894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6 74119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RedoInsts.push_back(Mul); 742894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 743894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If every add operand was a duplicate, return the multiply. 744894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops.empty()) 745894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Mul; 746894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 747894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, we had some input that didn't have the dupe, such as 748894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // "A + A + B" -> "A*2 + B". Add the new multiply to the list of 749894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // things being added by this operation. 750894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul)); 751894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 752894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --i; 753894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman e = Ops.size(); 754894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 755894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 756894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 757894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check for X and -X in the operand list. 758894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!BinaryOperator::isNeg(TheOp)) 759894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 760894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 761894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *X = BinaryOperator::getNegArgument(TheOp); 762894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned FoundX = FindInOperandList(Ops, i, X); 763894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FoundX == i) 764894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 765894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 766894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove X and -X from the operand list. 767894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops.size() == 2) 768894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Constant::getNullValue(X->getType()); 769894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 770894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.erase(Ops.begin()+i); 771894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i < FoundX) 772894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --FoundX; 773894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 774894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --i; // Need to back up an extra one. 775894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.erase(Ops.begin()+FoundX); 776894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumAnnihil; 777894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --i; // Revisit element. 778894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman e -= 2; // Removed two elements. 779894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 780894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 781894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan the operand list, checking to see if there are any common factors 782894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // between operands. Consider something like A*A+A*B*C+D. We would like to 783894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies. 784894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // To efficiently find this, we count the number of times a factor occurs 785894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // for any ADD operands that are MULs. 786894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<Value*, unsigned> FactorOccurrences; 787894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 788894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4) 789894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // where they are actually the same multiply. 790894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned MaxOcc = 0; 791894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *MaxOccVal = 0; 792894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 793894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op); 794894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty()) 795894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 796894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 797894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute all of the factors of this added value. 798894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<Value*, 8> Factors; 799894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FindSingleUseMultiplyFactors(BOp, Factors, Ops, true); 800894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Factors.size() > 1 && "Bad linearize!"); 801894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 802894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add one to FactorOccurrences for each unique factor in this op. 803894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<Value*, 8> Duplicates; 804894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 805894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Factor = Factors[i]; 806894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Duplicates.insert(Factor)) continue; 807894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 808894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Occ = ++FactorOccurrences[Factor]; 809894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } 810894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 811894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If Factor is a negative constant, add the negated value as a factor 812894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // because we can percolate the negate out. Watch for minint, which 813894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // cannot be positivified. 814894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) 81519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CI->isNegative() && !CI->isMinValue(true)) { 816894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Factor = ConstantInt::get(CI->getContext(), -CI->getValue()); 817894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!Duplicates.count(Factor) && 818894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Shouldn't have two constant factors, missed a canonicalize"); 819894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 820894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Occ = ++FactorOccurrences[Factor]; 821894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } 822894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 823894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 824894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 825894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 826894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If any factor occurred more than one time, we can pull it out. 827894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MaxOcc > 1) { 828894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(errs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n'); 829894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumFactor; 830894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 831894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create a new instruction that uses the MaxOccVal twice. If we don't do 832894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this, we could otherwise run into situations where removing a factor 833894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // from an expression will drop a use of maxocc, and this can cause 834894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // RemoveFactorFromExpression on successive values to behave differently. 835894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal); 836894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<Value*, 4> NewMulOps; 83719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0; i != Ops.size(); ++i) { 838894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Only try to remove factors from expressions we're allowed to. 839894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op); 840894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty()) 841894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 842894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 843894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { 84419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The factorized operand may occur several times. Convert them all in 84519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // one fell swoop. 84619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned j = Ops.size(); j != i;) { 84719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman --j; 84819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Ops[j].Op == Ops[i].Op) { 84919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewMulOps.push_back(V); 85019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Ops.erase(Ops.begin()+j); 85119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 85219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 85319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman --i; 854894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 855894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 856894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 857894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // No need for extra uses anymore. 858894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman delete DummyInst; 859894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 860894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumAddedValues = NewMulOps.size(); 861894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V = EmitAddTreeOfValues(I, NewMulOps); 862894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 863894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we have inserted the add tree, optimize it. This allows us to 864894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // handle cases that require multiple factoring steps, such as this: 865894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C)) 866894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(NumAddedValues > 1 && "Each occurrence should contribute a value"); 867894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (void)NumAddedValues; 868894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V = ReassociateExpression(cast<BinaryOperator>(V)); 869894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 870894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create the multiply. 87119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I); 872894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 873894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Rerun associate on the multiply in case the inner expression turned into 874894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // a multiply. We want to make sure that we keep things in canonical form. 875894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V2 = ReassociateExpression(cast<BinaryOperator>(V2)); 876894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 877894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If every add operand included the factor (e.g. "A*B + A*C"), then the 878894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // entire result expression is just the multiply "A*(B+C)". 879894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops.empty()) 880894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V2; 881894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 882894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, we had some input that didn't have the factor, such as 883894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // "A*B + A*C + D" -> "A*(B+C) + D". Add the new multiply to the list of 884894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // things being added by this operation. 885894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); 886894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 887894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 888894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 889894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 890894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 891894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanValue *Reassociate::OptimizeExpression(BinaryOperator *I, 892894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<ValueEntry> &Ops) { 893894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we have the linearized expression tree, try to optimize it. 894894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Start by folding any constants that we found. 895894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool IterateOptimization = false; 896894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops.size() == 1) return Ops[0].Op; 897894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 898894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Opcode = I->getOpcode(); 899894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 900894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 901894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 902894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.pop_back(); 903894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 904894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return OptimizeExpression(I, Ops); 905894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 906894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 907894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check for destructive annihilation due to a constant being used. 908894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op)) 909894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (Opcode) { 910894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: break; 911894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::And: 912894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CstVal->isZero()) // X & 0 -> 0 913894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return CstVal; 914894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CstVal->isAllOnesValue()) // X & -1 -> X 915894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.pop_back(); 916894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 917894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Mul: 918894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CstVal->isZero()) { // X * 0 -> 0 919894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumAnnihil; 920894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return CstVal; 921894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 922894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 923894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (cast<ConstantInt>(CstVal)->isOne()) 924894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.pop_back(); // X * 1 -> X 925894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 926894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Or: 927894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CstVal->isAllOnesValue()) // X | -1 -> -1 928894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return CstVal; 929894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FALLTHROUGH! 930894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Add: 931894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Xor: 932894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CstVal->isZero()) // X [|^+] 0 -> X 933894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.pop_back(); 934894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 935894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 936894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops.size() == 1) return Ops[0].Op; 937894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 938894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Handle destructive annihilation due to identities between elements in the 939894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // argument list here. 940894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (Opcode) { 941894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: break; 942894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::And: 943894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Or: 944894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Xor: { 945894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumOps = Ops.size(); 946894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Value *Result = OptimizeAndOrXor(Opcode, Ops)) 947894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Result; 948894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IterateOptimization |= Ops.size() != NumOps; 949894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 950894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 951894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 952894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Add: { 953894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumOps = Ops.size(); 954894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Value *Result = OptimizeAdd(I, Ops)) 955894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Result; 956894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IterateOptimization |= Ops.size() != NumOps; 957894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 958894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 959894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 960894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //case Instruction::Mul: 961894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 962894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 963894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IterateOptimization) 964894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return OptimizeExpression(I, Ops); 965894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 966894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 967894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 968894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 96919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ReassociateInst - Inspect and reassociate the instruction at the 97019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// given position, post-incrementing the position. 97119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid Reassociate::ReassociateInst(BasicBlock::iterator &BBI) { 97219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *BI = BBI++; 97319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BI->getOpcode() == Instruction::Shl && 97419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<ConstantInt>(BI->getOperand(1))) 97519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Instruction *NI = ConvertShiftToMul(BI, ValueRankMap)) { 97619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MadeChange = true; 97719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BI = NI; 97819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 979894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 98019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Reject cases where it is pointless to do this. 98119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPointTy() || 98219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BI->getType()->isVectorTy()) 98319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; // Floating point ops are not associative. 98419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 98519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Do not reassociate boolean (i1) expressions. We want to preserve the 98619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // original order of evaluation for short-circuited comparisons that 98719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // SimplifyCFG has folded to AND/OR expressions. If the expression 98819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // is not further optimized, it is likely to be transformed back to a 98919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // short-circuited form for code gen, and the source order may have been 99019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // optimized for the most likely conditions. 99119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BI->getType()->isIntegerTy(1)) 99219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 993894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 99419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this is a subtract instruction which is not already in negate form, 99519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // see if we can convert it to X+-Y. 99619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BI->getOpcode() == Instruction::Sub) { 99719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ShouldBreakUpSubtract(BI)) { 99819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BI = BreakUpSubtract(BI, ValueRankMap); 99919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Reset the BBI iterator in case BreakUpSubtract changed the 100019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // instruction it points to. 100119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BBI = BI; 100219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++BBI; 100319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MadeChange = true; 100419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (BinaryOperator::isNeg(BI)) { 100519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, this is a negation. See if the operand is a multiply tree 100619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // and if this is not an inner node of a multiply tree. 100719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isReassociableOp(BI->getOperand(1), Instruction::Mul) && 100819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (!BI->hasOneUse() || 100919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !isReassociableOp(BI->use_back(), Instruction::Mul))) { 101019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BI = LowerNegateToMultiply(BI, ValueRankMap); 1011894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 1012894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1013894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 101419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 1015894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 101619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this instruction is a commutative binary operator, process it. 101719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!BI->isAssociative()) return; 101819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BinaryOperator *I = cast<BinaryOperator>(BI); 1019894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 102019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this is an interior node of a reassociable tree, ignore it until we 102119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // get to the root of the tree, to avoid N^2 analysis. 102219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode())) 102319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 1024894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 102519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this is an add tree that is used by a sub instruction, ignore it 102619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // until we process the subtract. 102719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->hasOneUse() && I->getOpcode() == Instruction::Add && 102819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub) 102919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 1030894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 103119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReassociateExpression(I); 1032894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1033894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1034894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanValue *Reassociate::ReassociateExpression(BinaryOperator *I) { 1035894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1036894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // First, walk the expression tree, linearizing the tree, collecting the 1037894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // operand information. 1038894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<ValueEntry, 8> Ops; 1039894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LinearizeExprTree(I, Ops); 1040894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1041894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n'); 1042894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1043894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we have linearized the tree to a list and have gathered all of 1044894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the operands and their ranks, sort the operands by their rank. Use a 1045894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // stable_sort so that values with equal ranks will have their relative 1046894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // positions maintained (and so the compiler is deterministic). Note that 1047894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this sorts so that the highest ranking values end up at the beginning of 1048894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the vector. 1049894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::stable_sort(Ops.begin(), Ops.end()); 1050894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1051894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // OptimizeExpression - Now that we have the expression tree in a convenient 1052894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // sorted form, optimize it globally if possible. 1053894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Value *V = OptimizeExpression(I, Ops)) { 1054894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This expression tree simplified to something that isn't a tree, 1055894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // eliminate it. 1056894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n'); 1057894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->replaceAllUsesWith(V); 105819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Instruction *VI = dyn_cast<Instruction>(V)) 105919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VI->setDebugLoc(I->getDebugLoc()); 1060894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemoveDeadBinaryOp(I); 1061894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumAnnihil; 1062894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V; 1063894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1064894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1065894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We want to sink immediates as deeply as possible except in the case where 1066894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this is a multiply tree used only by an add, and the immediate is a -1. 1067894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // In this case we reassociate to put the negation on the outside so that we 1068894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y 1069894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getOpcode() == Instruction::Mul && I->hasOneUse() && 1070894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add && 1071894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isa<ConstantInt>(Ops.back().Op) && 1072894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) { 1073894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueEntry Tmp = Ops.pop_back_val(); 1074894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops.insert(Ops.begin(), Tmp); 1075894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1076894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1077894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n'); 1078894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1079894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Ops.size() == 1) { 1080894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This expression tree simplified to something that isn't a tree, 1081894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // eliminate it. 1082894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->replaceAllUsesWith(Ops[0].Op); 108319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op)) 108419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OI->setDebugLoc(I->getDebugLoc()); 1085894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemoveDeadBinaryOp(I); 1086894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Ops[0].Op; 1087894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1088894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1089894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we ordered and optimized the expressions, splat them back into 1090894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the expression tree, removing any unneeded nodes. 1091894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RewriteExprTree(I, Ops); 1092894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return I; 1093894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1094894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1095894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1096894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool Reassociate::runOnFunction(Function &F) { 1097894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Recalculate the rank map for F 1098894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BuildRankMap(F); 1099894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = false; 1101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 110219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator BBI = FI->begin(); BBI != FI->end(); ) 110319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReassociateInst(BBI); 110419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 110519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Now that we're done, revisit any instructions which are likely to 110619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // have secondary reassociation opportunities. 110719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!RedoInsts.empty()) 110819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Value *V = RedoInsts.pop_back_val()) { 110919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator BBI = cast<Instruction>(V); 111019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReassociateInst(BBI); 111119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 111219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 111319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Now that we're done, delete any instructions which are no longer used. 111419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!DeadInsts.empty()) 111519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Value *V = DeadInsts.pop_back_val()) 111619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RecursivelyDeleteTriviallyDeadInstructions(V); 1117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We are done with the rank map. 1119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RankMap.clear(); 1120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueRankMap.clear(); 1121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MadeChange; 1122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1124