Reassociate.cpp revision 469001000620df176decd093a300db84a06cc78b
14fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 94fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 104fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// This pass reassociates commutative expressions in an order that is designed 11e96fda3002dd0769d3dd758ac5008ba8cda92349Chris Lattner// to promote better constant propagation, GCSE, LICM, PRE... 124fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 134fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// For example: 4 + (x + 5) -> x + (4 + 5) 144fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 154fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// In the implementation of this algorithm, constants are assigned rank = 0, 164fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// function arguments are rank = 1, and other values are assigned ranks 174fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// corresponding to the reverse post order traversal of current function 184fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// (starting at 2), which effectively gives values in deep loops higher rank 194fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// than values not in loops. 204fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 214fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner//===----------------------------------------------------------------------===// 224fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 2308b43921e18f314c4fd38049291d323830934c36Chris Lattner#define DEBUG_TYPE "reassociate" 244fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Transforms/Scalar.h" 250975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner#include "llvm/Constants.h" 264fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Function.h" 27d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 284fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Pass.h" 290975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner#include "llvm/Type.h" 304fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Support/CFG.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/PostOrderIterator.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 34c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner#include <algorithm> 35d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 36d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 374fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnernamespace { 38a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumLinear ("reassociate","Number of insts linearized"); 39a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumChanged("reassociate","Number of insts reassociated"); 40a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumSwapped("reassociate","Number of insts with operands swapped"); 41a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 42c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner struct ValueEntry { 43c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner unsigned Rank; 44c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Value *Op; 45c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 46c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner }; 47c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 48c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 49c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 50c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 514fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner class Reassociate : public FunctionPass { 520c0edf8afc35a42b15a24ebb5fa5f3fc674290aeChris Lattner std::map<BasicBlock*, unsigned> RankMap; 53fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner std::map<Value*, unsigned> ValueRankMap; 54c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner bool MadeChange; 554fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner public: 567e70829632f82de15db187845666aaca6e04b792Chris Lattner bool runOnFunction(Function &F); 574fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 584fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 59cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 604fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 614fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner private: 627e70829632f82de15db187845666aaca6e04b792Chris Lattner void BuildRankMap(Function &F); 634fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned getRank(Value *V); 64c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void RewriteExprTree(BinaryOperator *I, unsigned Idx, 65c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::vector<ValueEntry> &Ops); 66469001000620df176decd093a300db84a06cc78bChris Lattner void OptimizeExpression(unsigned Opcode, std::vector<ValueEntry> &Ops); 67c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void LinearizeExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops); 68c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void LinearizeExpr(BinaryOperator *I); 69c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void ReassociateBB(BasicBlock *BB); 704fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner }; 71f629309f74cf1a64aa7fd1cd5784fd7db9a8f59eChris Lattner 72a6275ccdf5e1aa208afde56c498e2b13e16442f0Chris Lattner RegisterOpt<Reassociate> X("reassociate", "Reassociate expressions"); 734fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 744fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 75d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the Reassociate pass 76d7456026629fc1760a45e6e955e9834246493147Chris LattnerFunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 774fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 787e70829632f82de15db187845666aaca6e04b792Chris Lattnervoid Reassociate::BuildRankMap(Function &F) { 796007cb6c4d923e2dee4a1133fb6d1bb00a37062dChris Lattner unsigned i = 2; 80fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 81fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner // Assign distinct ranks to function arguments 82e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 83fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner ValueRankMap[I] = ++i; 84fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 857e70829632f82de15db187845666aaca6e04b792Chris Lattner ReversePostOrderTraversal<Function*> RPOT(&F); 864fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 874fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner E = RPOT.end(); I != E; ++I) 886007cb6c4d923e2dee4a1133fb6d1bb00a37062dChris Lattner RankMap[*I] = ++i << 16; 894fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 904fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 914fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnerunsigned Reassociate::getRank(Value *V) { 92fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument... 93fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 9408b43921e18f314c4fd38049291d323830934c36Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 9508b43921e18f314c4fd38049291d323830934c36Chris Lattner if (I == 0) return 0; // Otherwise it's a global or constant, rank 0. 964fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 9708b43921e18f314c4fd38049291d323830934c36Chris Lattner unsigned &CachedRank = ValueRankMap[I]; 9808b43921e18f314c4fd38049291d323830934c36Chris Lattner if (CachedRank) return CachedRank; // Rank already known? 9908b43921e18f314c4fd38049291d323830934c36Chris Lattner 10008b43921e18f314c4fd38049291d323830934c36Chris Lattner // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 10108b43921e18f314c4fd38049291d323830934c36Chris Lattner // we can reassociate expressions for code motion! Since we do not recurse 10208b43921e18f314c4fd38049291d323830934c36Chris Lattner // for PHI nodes, we cannot have infinite recursion here, because there 10308b43921e18f314c4fd38049291d323830934c36Chris Lattner // cannot be loops in the value graph that do not go through PHI nodes. 10408b43921e18f314c4fd38049291d323830934c36Chris Lattner // 10508b43921e18f314c4fd38049291d323830934c36Chris Lattner if (I->getOpcode() == Instruction::PHI || 10608b43921e18f314c4fd38049291d323830934c36Chris Lattner I->getOpcode() == Instruction::Alloca || 10708b43921e18f314c4fd38049291d323830934c36Chris Lattner I->getOpcode() == Instruction::Malloc || isa<TerminatorInst>(I) || 10808b43921e18f314c4fd38049291d323830934c36Chris Lattner I->mayWriteToMemory()) // Cannot move inst if it writes to memory! 10908b43921e18f314c4fd38049291d323830934c36Chris Lattner return RankMap[I->getParent()]; 11008b43921e18f314c4fd38049291d323830934c36Chris Lattner 11108b43921e18f314c4fd38049291d323830934c36Chris Lattner // If not, compute it! 11208b43921e18f314c4fd38049291d323830934c36Chris Lattner unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 11308b43921e18f314c4fd38049291d323830934c36Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); 11408b43921e18f314c4fd38049291d323830934c36Chris Lattner i != e && Rank != MaxRank; ++i) 11508b43921e18f314c4fd38049291d323830934c36Chris Lattner Rank = std::max(Rank, getRank(I->getOperand(i))); 11608b43921e18f314c4fd38049291d323830934c36Chris Lattner 117cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner // If this is a not or neg instruction, do not count it for rank. This 118cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner // assures us that X and ~X will have the same rank. 119cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner if (!I->getType()->isIntegral() || 120cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 121cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner ++Rank; 122cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner 12308b43921e18f314c4fd38049291d323830934c36Chris Lattner DEBUG(std::cerr << "Calculated Rank[" << V->getName() << "] = " 124cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner << Rank << "\n"); 12508b43921e18f314c4fd38049291d323830934c36Chris Lattner 126cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner return CachedRank = Rank; 1274fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1284fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 129c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// isReassociableOp - Return true if V is an instruction of the specified 130c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// opcode and if it only has one use. 131c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnerstatic BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 132c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (V->hasOneUse() && isa<Instruction>(V) && 133c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner cast<Instruction>(V)->getOpcode() == Opcode) 134c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return cast<BinaryOperator>(V); 135c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return 0; 136c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 1374fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 138c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. 139c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// Note that if D is also part of the expression tree that we recurse to 140c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// linearize it as well. Besides that case, this does not recurse into A,B, or 141c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// C. 142c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::LinearizeExpr(BinaryOperator *I) { 143c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 144c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1)); 145c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(isReassociableOp(LHS, I->getOpcode()) && 146c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner isReassociableOp(RHS, I->getOpcode()) && 147c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner "Not an expression that needs linearization?"); 148c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 149c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner DEBUG(std::cerr << "Linear" << *LHS << *RHS << *I); 150c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 151c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move the RHS instruction to live immediately before I, avoiding breaking 152c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // dominator properties. 153c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->getParent()->getInstList().splice(I, RHS->getParent()->getInstList(), RHS); 154c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 155c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move operands around to do the linearization. 156c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, RHS->getOperand(0)); 157c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHS->setOperand(0, LHS); 158c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(0, RHS); 159c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 160c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumLinear; 161c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 162c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner DEBUG(std::cerr << "Linearized: " << *I); 163fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 164c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If D is part of this expression tree, tail recurse. 165c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (isReassociableOp(I->getOperand(1), I->getOpcode())) 166c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExpr(I); 167c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 1684fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 169e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 170c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// LinearizeExprTree - Given an associative binary expression tree, traverse 171c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// all of the uses putting it into canonical form. This forces a left-linear 172c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// form of the the expression (((a+b)+c)+d), and collects information about the 173c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// rank of the non-tree operands. 174c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// 175c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// This returns the rank of the RHS operand, which is known to be the highest 176c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// rank value in the expression tree. 177c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// 178c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::LinearizeExprTree(BinaryOperator *I, 179c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::vector<ValueEntry> &Ops) { 180c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); 181c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner unsigned Opcode = I->getOpcode(); 182c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 183c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // First step, linearize the expression if it is in ((A+B)+(C+D)) form. 184c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); 185c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); 186c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 187c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!LHSBO) { 188c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!RHSBO) { 189c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Neither the LHS or RHS as part of the tree, thus this is a leaf. As 190c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // such, just remember these operands and their rank. 191c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(LHS), LHS)); 192c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(RHS), RHS)); 193c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return; 194c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } else { 195c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Turn X+(Y+Z) -> (Y+Z)+X 196c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::swap(LHSBO, RHSBO); 197c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::swap(LHS, RHS); 198c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner bool Success = !I->swapOperands(); 199c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(Success && "swapOperands failed"); 200c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 201c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 202c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } else if (RHSBO) { 203c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the the RHS is not 204c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // part of the expression tree. 205c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExpr(I); 206c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0)); 207c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHS = I->getOperand(1); 208c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHSBO = 0; 2094fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 210fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 211c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Okay, now we know that the LHS is a nested expression and that the RHS is 212c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // not. Perform reassociation. 213c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); 2144fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 215c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move LHS right before I to make sure that the tree expression dominates all 216c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // values. 217c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->getParent()->getInstList().splice(I, 218c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LHSBO->getParent()->getInstList(), LHSBO); 219c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 220c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Linearize the expression tree on the LHS. 221c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExprTree(LHSBO, Ops); 222c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 223c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Remember the RHS operand and its rank. 224c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(RHS), RHS)); 225c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 226c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 227c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// RewriteExprTree - Now that the operands for this expression tree are 228c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// linearized and optimized, emit them in-order. This function is written to be 229c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// tail recursive. 230c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::RewriteExprTree(BinaryOperator *I, unsigned i, 231c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::vector<ValueEntry> &Ops) { 232c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (i+2 == Ops.size()) { 233c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->getOperand(0) != Ops[i].Op || 234c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->getOperand(1) != Ops[i+1].Op) { 235c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner DEBUG(std::cerr << "RA: " << *I); 236c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(0, Ops[i].Op); 237c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, Ops[i+1].Op); 238c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner DEBUG(std::cerr << "TO: " << *I); 239c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 240c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumChanged; 241c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 242c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return; 243c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 244c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(i+2 < Ops.size() && "Ops index out of range!"); 245c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 246c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->getOperand(1) != Ops[i].Op) { 247c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner DEBUG(std::cerr << "RA: " << *I); 248c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, Ops[i].Op); 249c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner DEBUG(std::cerr << "TO: " << *I); 250c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 251c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumChanged; 252c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 253c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RewriteExprTree(cast<BinaryOperator>(I->getOperand(0)), i+1, Ops); 2544fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 2554fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 2564fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 257c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 258a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// NegateValue - Insert instructions before the instruction pointed to by BI, 259a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that computes the negative version of the value specified. The negative 260a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// version of the value is returned, and BI is left pointing at the instruction 261a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that should be processed next by the reassociation pass. 262a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// 26308b43921e18f314c4fd38049291d323830934c36Chris Lattnerstatic Value *NegateValue(Value *V, Instruction *BI) { 264a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // We are trying to expose opportunity for reassociation. One of the things 265a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // that we want to do to achieve this is to push a negation as deep into an 266a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // expression chain as possible, to expose the add instructions. In practice, 267a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // this means that we turn this: 268a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 269a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 270a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // the constants. We assume that instcombine will clean up the mess later if 2715560c9d49ccae132cabf1155f18aa0480dce3edaMisha Brukman // we introduce tons of unnecessary negation instructions... 272a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 273a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 274fd05924946ebfcfb3409b21996cfd0836e4ddb31Chris Lattner if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 275e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner Value *RHS = NegateValue(I->getOperand(1), BI); 276e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner Value *LHS = NegateValue(I->getOperand(0), BI); 277a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 278a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // We must actually insert a new add instruction here, because the neg 279a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // instructions do not dominate the old add instruction in general. By 280a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // adding it now, we are assured that the neg instructions we just 281a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // inserted dominate the instruction we are about to insert after them. 282a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 2832a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner return BinaryOperator::create(Instruction::Add, LHS, RHS, 28408b43921e18f314c4fd38049291d323830934c36Chris Lattner I->getName()+".neg", BI); 285a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner } 286a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 287a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Insert a 'neg' instruction that subtracts the value from zero to get the 288a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // negation. 289a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 29008b43921e18f314c4fd38049291d323830934c36Chris Lattner return BinaryOperator::createNeg(V, V->getName() + ".neg", BI); 291a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner} 292a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 29308b43921e18f314c4fd38049291d323830934c36Chris Lattner/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 29408b43921e18f314c4fd38049291d323830934c36Chris Lattner/// only used by an add, transform this into (X+(0-Y)) to promote better 29508b43921e18f314c4fd38049291d323830934c36Chris Lattner/// reassociation. 29608b43921e18f314c4fd38049291d323830934c36Chris Lattnerstatic Instruction *BreakUpSubtract(Instruction *Sub) { 29708b43921e18f314c4fd38049291d323830934c36Chris Lattner // Reject cases where it is pointless to do this. 29808b43921e18f314c4fd38049291d323830934c36Chris Lattner if (Sub->getType()->isFloatingPoint()) 29908b43921e18f314c4fd38049291d323830934c36Chris Lattner return 0; // Floating point adds are not associative. 30008b43921e18f314c4fd38049291d323830934c36Chris Lattner 30108b43921e18f314c4fd38049291d323830934c36Chris Lattner // Don't bother to break this up unless either the LHS is an associable add or 30208b43921e18f314c4fd38049291d323830934c36Chris Lattner // if this is only used by one. 30308b43921e18f314c4fd38049291d323830934c36Chris Lattner if (!isReassociableOp(Sub->getOperand(0), Instruction::Add) && 30408b43921e18f314c4fd38049291d323830934c36Chris Lattner !isReassociableOp(Sub->getOperand(1), Instruction::Add) && 30508b43921e18f314c4fd38049291d323830934c36Chris Lattner !(Sub->hasOneUse() &&isReassociableOp(Sub->use_back(), Instruction::Add))) 30608b43921e18f314c4fd38049291d323830934c36Chris Lattner return 0; 30708b43921e18f314c4fd38049291d323830934c36Chris Lattner 30808b43921e18f314c4fd38049291d323830934c36Chris Lattner // Convert a subtract into an add and a neg instruction... so that sub 30908b43921e18f314c4fd38049291d323830934c36Chris Lattner // instructions can be commuted with other add instructions... 31008b43921e18f314c4fd38049291d323830934c36Chris Lattner // 31108b43921e18f314c4fd38049291d323830934c36Chris Lattner // Calculate the negative value of Operand 1 of the sub instruction... 31208b43921e18f314c4fd38049291d323830934c36Chris Lattner // and set it as the RHS of the add instruction we just made... 31308b43921e18f314c4fd38049291d323830934c36Chris Lattner // 31408b43921e18f314c4fd38049291d323830934c36Chris Lattner std::string Name = Sub->getName(); 31508b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->setName(""); 31608b43921e18f314c4fd38049291d323830934c36Chris Lattner Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 31708b43921e18f314c4fd38049291d323830934c36Chris Lattner Instruction *New = 31808b43921e18f314c4fd38049291d323830934c36Chris Lattner BinaryOperator::createAdd(Sub->getOperand(0), NegVal, Name, Sub); 31908b43921e18f314c4fd38049291d323830934c36Chris Lattner 32008b43921e18f314c4fd38049291d323830934c36Chris Lattner // Everyone now refers to the add instruction. 32108b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->replaceAllUsesWith(New); 32208b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->eraseFromParent(); 32308b43921e18f314c4fd38049291d323830934c36Chris Lattner 32408b43921e18f314c4fd38049291d323830934c36Chris Lattner DEBUG(std::cerr << "Negated: " << *New); 32508b43921e18f314c4fd38049291d323830934c36Chris Lattner return New; 32608b43921e18f314c4fd38049291d323830934c36Chris Lattner} 32708b43921e18f314c4fd38049291d323830934c36Chris Lattner 3280975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 3290975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// by one, change this into a multiply by a constant to assist with further 3300975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// reassociation. 3310975ed5f4ef7264b45995241717055f8a116bb27Chris Lattnerstatic Instruction *ConvertShiftToMul(Instruction *Shl) { 3320975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner if (!isReassociableOp(Shl->getOperand(0), Instruction::Mul) && 3330975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner !(Shl->hasOneUse() && isReassociableOp(Shl->use_back(),Instruction::Mul))) 3340975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner return 0; 3350975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner 3360975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 3370975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 3380975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner 3390975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner std::string Name = Shl->getName(); Shl->setName(""); 3400975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner Instruction *Mul = BinaryOperator::createMul(Shl->getOperand(0), MulCst, 3410975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner Name, Shl); 3420975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner Shl->replaceAllUsesWith(Mul); 3430975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner Shl->eraseFromParent(); 3440975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner return Mul; 3450975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner} 3460975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner 347469001000620df176decd093a300db84a06cc78bChris Lattnervoid Reassociate::OptimizeExpression(unsigned Opcode, 348469001000620df176decd093a300db84a06cc78bChris Lattner std::vector<ValueEntry> &Ops) { 349469001000620df176decd093a300db84a06cc78bChris Lattner // Now that we have the linearized expression tree, try to optimize it. 350469001000620df176decd093a300db84a06cc78bChris Lattner // Start by folding any constants that we found. 351469001000620df176decd093a300db84a06cc78bChris Lattner FoldConstants: 352469001000620df176decd093a300db84a06cc78bChris Lattner if (Ops.size() == 1) return; 353469001000620df176decd093a300db84a06cc78bChris Lattner 354469001000620df176decd093a300db84a06cc78bChris Lattner if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 355469001000620df176decd093a300db84a06cc78bChris Lattner if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 356469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 357469001000620df176decd093a300db84a06cc78bChris Lattner Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 358469001000620df176decd093a300db84a06cc78bChris Lattner goto FoldConstants; 359469001000620df176decd093a300db84a06cc78bChris Lattner } 360469001000620df176decd093a300db84a06cc78bChris Lattner 361469001000620df176decd093a300db84a06cc78bChris Lattner // Check for destructive annihilation due to a constant being used. 362469001000620df176decd093a300db84a06cc78bChris Lattner if (ConstantIntegral *CstVal = dyn_cast<ConstantIntegral>(Ops.back().Op)) 363469001000620df176decd093a300db84a06cc78bChris Lattner switch (Opcode) { 364469001000620df176decd093a300db84a06cc78bChris Lattner default: break; 365469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::And: 366469001000620df176decd093a300db84a06cc78bChris Lattner if (CstVal->isNullValue()) { // ... & 0 -> 0 367469001000620df176decd093a300db84a06cc78bChris Lattner Ops[0].Op = CstVal; 368469001000620df176decd093a300db84a06cc78bChris Lattner Ops.erase(Ops.begin()+1, Ops.end()); 369469001000620df176decd093a300db84a06cc78bChris Lattner } else if (CstVal->isAllOnesValue()) { // ... & -1 -> ... 370469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 371469001000620df176decd093a300db84a06cc78bChris Lattner } 372469001000620df176decd093a300db84a06cc78bChris Lattner break; 373469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Mul: 374469001000620df176decd093a300db84a06cc78bChris Lattner if (CstVal->isNullValue()) { // ... * 0 -> 0 375469001000620df176decd093a300db84a06cc78bChris Lattner Ops[0].Op = CstVal; 376469001000620df176decd093a300db84a06cc78bChris Lattner Ops.erase(Ops.begin()+1, Ops.end()); 377469001000620df176decd093a300db84a06cc78bChris Lattner } else if (cast<ConstantInt>(CstVal)->getRawValue() == 1) { 378469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); // ... * 1 -> ... 379469001000620df176decd093a300db84a06cc78bChris Lattner } 380469001000620df176decd093a300db84a06cc78bChris Lattner break; 381469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Or: 382469001000620df176decd093a300db84a06cc78bChris Lattner if (CstVal->isAllOnesValue()) { // ... | -1 -> -1 383469001000620df176decd093a300db84a06cc78bChris Lattner Ops[0].Op = CstVal; 384469001000620df176decd093a300db84a06cc78bChris Lattner Ops.erase(Ops.begin()+1, Ops.end()); 385469001000620df176decd093a300db84a06cc78bChris Lattner } 386469001000620df176decd093a300db84a06cc78bChris Lattner // FALLTHROUGH! 387469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Add: 388469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Xor: 389469001000620df176decd093a300db84a06cc78bChris Lattner if (CstVal->isNullValue()) // ... [|^+] 0 -> ... 390469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 391469001000620df176decd093a300db84a06cc78bChris Lattner break; 392469001000620df176decd093a300db84a06cc78bChris Lattner } 393469001000620df176decd093a300db84a06cc78bChris Lattner 394469001000620df176decd093a300db84a06cc78bChris Lattner // Handle destructive annihilation do to identities between elements in the 395469001000620df176decd093a300db84a06cc78bChris Lattner // argument list here. 396469001000620df176decd093a300db84a06cc78bChris Lattner} 397469001000620df176decd093a300db84a06cc78bChris Lattner 39808b43921e18f314c4fd38049291d323830934c36Chris Lattner 39908b43921e18f314c4fd38049291d323830934c36Chris Lattner/// ReassociateBB - Inspect all of the instructions in this basic block, 40008b43921e18f314c4fd38049291d323830934c36Chris Lattner/// reassociating them as we go. 401c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::ReassociateBB(BasicBlock *BB) { 4024fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) { 40308b43921e18f314c4fd38049291d323830934c36Chris Lattner // If this is a subtract instruction which is not already in negate form, 40408b43921e18f314c4fd38049291d323830934c36Chris Lattner // see if we can convert it to X+-Y. 40508b43921e18f314c4fd38049291d323830934c36Chris Lattner if (BI->getOpcode() == Instruction::Sub && !BinaryOperator::isNeg(BI)) 40608b43921e18f314c4fd38049291d323830934c36Chris Lattner if (Instruction *NI = BreakUpSubtract(BI)) { 407c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 40808b43921e18f314c4fd38049291d323830934c36Chris Lattner BI = NI; 40908b43921e18f314c4fd38049291d323830934c36Chris Lattner } 4100975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner if (BI->getOpcode() == Instruction::Shl && 4110975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner isa<ConstantInt>(BI->getOperand(1))) 4120975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner if (Instruction *NI = ConvertShiftToMul(BI)) { 413c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 4140975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner BI = NI; 4150975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner } 416e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 417c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If this instruction is a commutative binary operator, process it. 418c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!BI->isAssociative()) continue; 419c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *I = cast<BinaryOperator>(BI); 420c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 421c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If this is an interior node of a reassociable tree, ignore it until we 422c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // get to the root of the tree, to avoid N^2 analysis. 423c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode())) 424c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner continue; 425c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 426c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // First, walk the expression tree, linearizing the tree, collecting 427c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::vector<ValueEntry> Ops; 428c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExprTree(I, Ops); 429c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 430c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Now that we have linearized the tree to a list and have gathered all of 431c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // the operands and their ranks, sort the operands by their rank. Use a 432c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // stable_sort so that values with equal ranks will have their relative 433c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // positions maintained (and so the compiler is deterministic). Note that 434c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // this sorts so that the highest ranking values end up at the beginning of 435c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // the vector. 436c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::stable_sort(Ops.begin(), Ops.end()); 437c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 438469001000620df176decd093a300db84a06cc78bChris Lattner // OptimizeExpression - Now that we have the expression tree in a convenient 439469001000620df176decd093a300db84a06cc78bChris Lattner // sorted form, optimize it globally if possible. 440469001000620df176decd093a300db84a06cc78bChris Lattner OptimizeExpression(I->getOpcode(), Ops); 441c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 442c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (Ops.size() == 1) { 443c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // This expression tree simplified to something that isn't a tree, 444c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // eliminate it. 445c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->replaceAllUsesWith(Ops[0].Op); 446c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } else { 447c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Now that we ordered and optimized the expressions, splat them back into 448c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // the expression tree, removing any unneeded nodes. 449c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RewriteExprTree(I, 0, Ops); 4504fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 4514fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 4524fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 4534fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 4544fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 4557e70829632f82de15db187845666aaca6e04b792Chris Lattnerbool Reassociate::runOnFunction(Function &F) { 4564fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Recalculate the rank map for F 4574fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner BuildRankMap(F); 4584fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 459c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = false; 4607e70829632f82de15db187845666aaca6e04b792Chris Lattner for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 461c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ReassociateBB(FI); 4624fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 4634fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // We are done with the rank map... 4644fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner RankMap.clear(); 465fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner ValueRankMap.clear(); 466c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return MadeChange; 4674fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 468d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 469