Reassociate.cpp revision 24d6da5fedcf39891f7d8c5b031c01324b3db545
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" 26ae74f555522298bef3be8a173163bf778d59adf9Chris Lattner#include "llvm/DerivedTypes.h" 274fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Function.h" 28d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 294fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Pass.h" 30c9fd097a01383323f166c14c17d3984620cad766Chris Lattner#include "llvm/Assembly/Writer.h" 314fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Support/CFG.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/PostOrderIterator.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 35c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner#include <algorithm> 36d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 380e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumLinear , "Number of insts linearized"); 390e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumChanged, "Number of insts reassociated"); 400e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumAnnihil, "Number of expr tree annihilated"); 410e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumFactor , "Number of multiplies factored"); 42a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 430e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 44c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner struct ValueEntry { 45c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner unsigned Rank; 46c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Value *Op; 47c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 48c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner }; 49c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 50c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 51c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 52e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 53c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 54e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// PrintOps - Print out the expression identified in the Ops list. 55e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// 56e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattnerstatic void PrintOps(Instruction *I, const std::vector<ValueEntry> &Ops) { 57e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Module *M = I->getParent()->getParent()->getParent(); 58832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling cerr << Instruction::getOpcodeName(I->getOpcode()) << " " 59e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner << *Ops[0].Op->getType(); 60e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) 61832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling WriteAsOperand(*cerr.stream() << " ", Ops[i].Op, false, M) 62e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner << "," << Ops[i].Rank; 63e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 64e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 65e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattnernamespace { 664fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner class Reassociate : public FunctionPass { 670c0edf8afc35a42b15a24ebb5fa5f3fc674290aeChris Lattner std::map<BasicBlock*, unsigned> RankMap; 68fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner std::map<Value*, unsigned> ValueRankMap; 69c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner bool MadeChange; 704fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner public: 717e70829632f82de15db187845666aaca6e04b792Chris Lattner bool runOnFunction(Function &F); 724fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 734fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 74cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 754fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 764fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner private: 777e70829632f82de15db187845666aaca6e04b792Chris Lattner void BuildRankMap(Function &F); 784fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned getRank(Value *V); 79895b392269cad07c34d59110d68dc86708c53adbChris Lattner void ReassociateExpression(BinaryOperator *I); 80e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner void RewriteExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops, 81e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner unsigned Idx = 0); 82e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *OptimizeExpression(BinaryOperator *I, std::vector<ValueEntry> &Ops); 83c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void LinearizeExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops); 84c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void LinearizeExpr(BinaryOperator *I); 85e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *RemoveFactorFromExpression(Value *V, Value *Factor); 86c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void ReassociateBB(BasicBlock *BB); 87e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 88e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner void RemoveDeadBinaryOp(Value *V); 894fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner }; 90f629309f74cf1a64aa7fd1cd5784fd7db9a8f59eChris Lattner 917f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<Reassociate> X("reassociate", "Reassociate expressions"); 924fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 934fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 94d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the Reassociate pass 95d7456026629fc1760a45e6e955e9834246493147Chris LattnerFunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 964fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 97e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattnervoid Reassociate::RemoveDeadBinaryOp(Value *V) { 98e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Instruction *Op = dyn_cast<Instruction>(V); 99e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (!Op || !isa<BinaryOperator>(Op) || !isa<CmpInst>(Op) || !Op->use_empty()) 100e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer return; 101e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 102e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1); 103e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(LHS); 104e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(RHS); 105e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 106e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 1079c723199384b16899831937e2800d52f4f953569Chris Lattner 1089c723199384b16899831937e2800d52f4f953569Chris Lattnerstatic bool isUnmovableInstruction(Instruction *I) { 1099c723199384b16899831937e2800d52f4f953569Chris Lattner if (I->getOpcode() == Instruction::PHI || 1109c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Alloca || 1119c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Load || 1129c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Malloc || 1139c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Invoke || 1149c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Call || 1151628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::UDiv || 1161628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::SDiv || 1171628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::FDiv || 1180a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::URem || 1190a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::SRem || 1200a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::FRem) 1219c723199384b16899831937e2800d52f4f953569Chris Lattner return true; 1229c723199384b16899831937e2800d52f4f953569Chris Lattner return false; 1239c723199384b16899831937e2800d52f4f953569Chris Lattner} 1249c723199384b16899831937e2800d52f4f953569Chris Lattner 1257e70829632f82de15db187845666aaca6e04b792Chris Lattnervoid Reassociate::BuildRankMap(Function &F) { 1266007cb6c4d923e2dee4a1133fb6d1bb00a37062dChris Lattner unsigned i = 2; 127fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 128fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner // Assign distinct ranks to function arguments 129e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 130fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner ValueRankMap[I] = ++i; 131fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 1327e70829632f82de15db187845666aaca6e04b792Chris Lattner ReversePostOrderTraversal<Function*> RPOT(&F); 1334fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 1349c723199384b16899831937e2800d52f4f953569Chris Lattner E = RPOT.end(); I != E; ++I) { 1359c723199384b16899831937e2800d52f4f953569Chris Lattner BasicBlock *BB = *I; 1369c723199384b16899831937e2800d52f4f953569Chris Lattner unsigned BBRank = RankMap[BB] = ++i << 16; 1379c723199384b16899831937e2800d52f4f953569Chris Lattner 1389c723199384b16899831937e2800d52f4f953569Chris Lattner // Walk the basic block, adding precomputed ranks for any instructions that 1399c723199384b16899831937e2800d52f4f953569Chris Lattner // we cannot move. This ensures that the ranks for these instructions are 1409c723199384b16899831937e2800d52f4f953569Chris Lattner // all different in the block. 1419c723199384b16899831937e2800d52f4f953569Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 1429c723199384b16899831937e2800d52f4f953569Chris Lattner if (isUnmovableInstruction(I)) 1439c723199384b16899831937e2800d52f4f953569Chris Lattner ValueRankMap[I] = ++BBRank; 1449c723199384b16899831937e2800d52f4f953569Chris Lattner } 1454fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1464fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1474fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnerunsigned Reassociate::getRank(Value *V) { 148fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument... 149fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 15008b43921e18f314c4fd38049291d323830934c36Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 15108b43921e18f314c4fd38049291d323830934c36Chris Lattner if (I == 0) return 0; // Otherwise it's a global or constant, rank 0. 1524fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 15308b43921e18f314c4fd38049291d323830934c36Chris Lattner unsigned &CachedRank = ValueRankMap[I]; 15408b43921e18f314c4fd38049291d323830934c36Chris Lattner if (CachedRank) return CachedRank; // Rank already known? 15500b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 15608b43921e18f314c4fd38049291d323830934c36Chris Lattner // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 15708b43921e18f314c4fd38049291d323830934c36Chris Lattner // we can reassociate expressions for code motion! Since we do not recurse 15808b43921e18f314c4fd38049291d323830934c36Chris Lattner // for PHI nodes, we cannot have infinite recursion here, because there 15908b43921e18f314c4fd38049291d323830934c36Chris Lattner // cannot be loops in the value graph that do not go through PHI nodes. 16008b43921e18f314c4fd38049291d323830934c36Chris Lattner unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 16108b43921e18f314c4fd38049291d323830934c36Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); 16208b43921e18f314c4fd38049291d323830934c36Chris Lattner i != e && Rank != MaxRank; ++i) 16308b43921e18f314c4fd38049291d323830934c36Chris Lattner Rank = std::max(Rank, getRank(I->getOperand(i))); 16400b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 165cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner // If this is a not or neg instruction, do not count it for rank. This 166cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner // assures us that X and ~X will have the same rank. 16742a75517250017a52afb03a0ade03cbd49559fe5Chris Lattner if (!I->getType()->isInteger() || 168cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 169cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner ++Rank; 170cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner 171832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling //DOUT << "Calculated Rank[" << V->getName() << "] = " 172832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling // << Rank << "\n"; 17300b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 174cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner return CachedRank = Rank; 1754fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1764fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 177c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// isReassociableOp - Return true if V is an instruction of the specified 178c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// opcode and if it only has one use. 179c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnerstatic BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 180e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if ((V->hasOneUse() || V->use_empty()) && isa<Instruction>(V) && 181c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner cast<Instruction>(V)->getOpcode() == Opcode) 182c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return cast<BinaryOperator>(V); 183c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return 0; 184c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 1854fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 186f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner/// LowerNegateToMultiply - Replace 0-X with X*-1. 187f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner/// 188f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattnerstatic Instruction *LowerNegateToMultiply(Instruction *Neg) { 18924d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer Constant *Cst = ConstantInt::getAllOnesValue(Neg->getType()); 190f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 191f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner std::string NegName = Neg->getName(); Neg->setName(""); 192f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner Instruction *Res = BinaryOperator::createMul(Neg->getOperand(1), Cst, NegName, 193f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner Neg); 194f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner Neg->replaceAllUsesWith(Res); 195f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner Neg->eraseFromParent(); 196f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner return Res; 197f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner} 198f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 199c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. 200c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// Note that if D is also part of the expression tree that we recurse to 201c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// linearize it as well. Besides that case, this does not recurse into A,B, or 202c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// C. 203c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::LinearizeExpr(BinaryOperator *I) { 204c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 205c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1)); 20600b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen assert(isReassociableOp(LHS, I->getOpcode()) && 207c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner isReassociableOp(RHS, I->getOpcode()) && 208c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner "Not an expression that needs linearization?"); 209c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 210832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "Linear" << *LHS << *RHS << *I; 211c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 212c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move the RHS instruction to live immediately before I, avoiding breaking 213c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // dominator properties. 2144bc5f8071a28b6fc4f4c2207dd03a5f747d0d84bChris Lattner RHS->moveBefore(I); 215c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 216c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move operands around to do the linearization. 217c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, RHS->getOperand(0)); 218c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHS->setOperand(0, LHS); 219c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(0, RHS); 22000b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 221c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumLinear; 222c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 223832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "Linearized: " << *I; 224fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 225c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If D is part of this expression tree, tail recurse. 226c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (isReassociableOp(I->getOperand(1), I->getOpcode())) 227c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExpr(I); 228c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 2294fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 230e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 231c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// LinearizeExprTree - Given an associative binary expression tree, traverse 232c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// all of the uses putting it into canonical form. This forces a left-linear 233c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// form of the the expression (((a+b)+c)+d), and collects information about the 234c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// rank of the non-tree operands. 235c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// 236e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// NOTE: These intentionally destroys the expression tree operands (turning 237e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// them into undef values) to reduce #uses of the values. This means that the 238e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// caller MUST use something like RewriteExprTree to put the values back in. 239e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// 240c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::LinearizeExprTree(BinaryOperator *I, 241c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::vector<ValueEntry> &Ops) { 242c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); 243c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner unsigned Opcode = I->getOpcode(); 244c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 245c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // First step, linearize the expression if it is in ((A+B)+(C+D)) form. 246c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); 247c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); 248c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 249f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // If this is a multiply expression tree and it contains internal negations, 250f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // transform them into multiplies by -1 so they can be reassociated. 251f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (I->getOpcode() == Instruction::Mul) { 252f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (!LHSBO && LHS->hasOneUse() && BinaryOperator::isNeg(LHS)) { 253f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner LHS = LowerNegateToMultiply(cast<Instruction>(LHS)); 254f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner LHSBO = isReassociableOp(LHS, Opcode); 255f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 256f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (!RHSBO && RHS->hasOneUse() && BinaryOperator::isNeg(RHS)) { 257f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner RHS = LowerNegateToMultiply(cast<Instruction>(RHS)); 258f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner RHSBO = isReassociableOp(RHS, Opcode); 259f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 260f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 261f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 262c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!LHSBO) { 263c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!RHSBO) { 264c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Neither the LHS or RHS as part of the tree, thus this is a leaf. As 265c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // such, just remember these operands and their rank. 266c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(LHS), LHS)); 267c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(RHS), RHS)); 268e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 269e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Clear the leaves out. 270e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner I->setOperand(0, UndefValue::get(I->getType())); 271e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner I->setOperand(1, UndefValue::get(I->getType())); 272c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return; 273c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } else { 274c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Turn X+(Y+Z) -> (Y+Z)+X 275c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::swap(LHSBO, RHSBO); 276c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner std::swap(LHS, RHS); 277c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner bool Success = !I->swapOperands(); 278c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(Success && "swapOperands failed"); 279c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 280c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 281c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } else if (RHSBO) { 282c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the the RHS is not 283c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // part of the expression tree. 284c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExpr(I); 285c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0)); 286c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHS = I->getOperand(1); 287c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHSBO = 0; 2884fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 289fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 290c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Okay, now we know that the LHS is a nested expression and that the RHS is 291c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // not. Perform reassociation. 292c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); 2934fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 294c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move LHS right before I to make sure that the tree expression dominates all 295c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // values. 2964bc5f8071a28b6fc4f4c2207dd03a5f747d0d84bChris Lattner LHSBO->moveBefore(I); 297c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 298c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Linearize the expression tree on the LHS. 299c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExprTree(LHSBO, Ops); 300c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 301c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Remember the RHS operand and its rank. 302c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(RHS), RHS)); 303e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 304e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Clear the RHS leaf out. 305e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner I->setOperand(1, UndefValue::get(I->getType())); 306c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 307c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 308c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// RewriteExprTree - Now that the operands for this expression tree are 309c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// linearized and optimized, emit them in-order. This function is written to be 310c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// tail recursive. 311e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattnervoid Reassociate::RewriteExprTree(BinaryOperator *I, 312e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner std::vector<ValueEntry> &Ops, 313e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner unsigned i) { 314c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (i+2 == Ops.size()) { 315c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->getOperand(0) != Ops[i].Op || 316c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->getOperand(1) != Ops[i+1].Op) { 317e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *OldLHS = I->getOperand(0); 318832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "RA: " << *I; 319c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(0, Ops[i].Op); 320c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, Ops[i+1].Op); 321832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "TO: " << *I; 322c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 323c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumChanged; 324e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 325e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // If we reassociated a tree to fewer operands (e.g. (1+a+2) -> (a+3) 326e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // delete the extra, now dead, nodes. 327e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(OldLHS); 328c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 329c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return; 330c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 331c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(i+2 < Ops.size() && "Ops index out of range!"); 332c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 333c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->getOperand(1) != Ops[i].Op) { 334832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "RA: " << *I; 335c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, Ops[i].Op); 336832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "TO: " << *I; 337c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 338c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumChanged; 339c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 340e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 341e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 342e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner assert(LHS->getOpcode() == I->getOpcode() && 343e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner "Improper expression tree!"); 344e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 345e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // Compactify the tree instructions together with each other to guarantee 346e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // that the expression tree is dominated by all of Ops. 347e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner LHS->moveBefore(I); 348e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(LHS, Ops, i+1); 3494fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 3504fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 3514fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 352c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 353a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// NegateValue - Insert instructions before the instruction pointed to by BI, 354a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that computes the negative version of the value specified. The negative 355a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// version of the value is returned, and BI is left pointing at the instruction 356a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that should be processed next by the reassociation pass. 357a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// 35808b43921e18f314c4fd38049291d323830934c36Chris Lattnerstatic Value *NegateValue(Value *V, Instruction *BI) { 359a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // We are trying to expose opportunity for reassociation. One of the things 360a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // that we want to do to achieve this is to push a negation as deep into an 361a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // expression chain as possible, to expose the add instructions. In practice, 362a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // this means that we turn this: 363a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 364a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 365a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // the constants. We assume that instcombine will clean up the mess later if 3665560c9d49ccae132cabf1155f18aa0480dce3edaMisha Brukman // we introduce tons of unnecessary negation instructions... 367a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 368a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 369fd05924946ebfcfb3409b21996cfd0836e4ddb31Chris Lattner if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 3702cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // Push the negates through the add. 3712cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner I->setOperand(0, NegateValue(I->getOperand(0), BI)); 3722cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner I->setOperand(1, NegateValue(I->getOperand(1), BI)); 3732cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner 3742cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // We must move the add instruction here, because the neg instructions do 3752cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // not dominate the old add instruction in general. By moving it, we are 3762cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // assured that the neg instructions we just inserted dominate the 3772cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // instruction we are about to insert after them. 378a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 3792cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner I->moveBefore(BI); 3802cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner I->setName(I->getName()+".neg"); 3812cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner return I; 382a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner } 383a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 384a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Insert a 'neg' instruction that subtracts the value from zero to get the 385a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // negation. 386a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 38708b43921e18f314c4fd38049291d323830934c36Chris Lattner return BinaryOperator::createNeg(V, V->getName() + ".neg", BI); 388a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner} 389a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 39008b43921e18f314c4fd38049291d323830934c36Chris Lattner/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 39108b43921e18f314c4fd38049291d323830934c36Chris Lattner/// only used by an add, transform this into (X+(0-Y)) to promote better 39208b43921e18f314c4fd38049291d323830934c36Chris Lattner/// reassociation. 39308b43921e18f314c4fd38049291d323830934c36Chris Lattnerstatic Instruction *BreakUpSubtract(Instruction *Sub) { 39408b43921e18f314c4fd38049291d323830934c36Chris Lattner // Don't bother to break this up unless either the LHS is an associable add or 39508b43921e18f314c4fd38049291d323830934c36Chris Lattner // if this is only used by one. 39608b43921e18f314c4fd38049291d323830934c36Chris Lattner if (!isReassociableOp(Sub->getOperand(0), Instruction::Add) && 39708b43921e18f314c4fd38049291d323830934c36Chris Lattner !isReassociableOp(Sub->getOperand(1), Instruction::Add) && 39808b43921e18f314c4fd38049291d323830934c36Chris Lattner !(Sub->hasOneUse() &&isReassociableOp(Sub->use_back(), Instruction::Add))) 39908b43921e18f314c4fd38049291d323830934c36Chris Lattner return 0; 40008b43921e18f314c4fd38049291d323830934c36Chris Lattner 40108b43921e18f314c4fd38049291d323830934c36Chris Lattner // Convert a subtract into an add and a neg instruction... so that sub 40208b43921e18f314c4fd38049291d323830934c36Chris Lattner // instructions can be commuted with other add instructions... 40308b43921e18f314c4fd38049291d323830934c36Chris Lattner // 40408b43921e18f314c4fd38049291d323830934c36Chris Lattner // Calculate the negative value of Operand 1 of the sub instruction... 40508b43921e18f314c4fd38049291d323830934c36Chris Lattner // and set it as the RHS of the add instruction we just made... 40608b43921e18f314c4fd38049291d323830934c36Chris Lattner // 40708b43921e18f314c4fd38049291d323830934c36Chris Lattner std::string Name = Sub->getName(); 40808b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->setName(""); 40908b43921e18f314c4fd38049291d323830934c36Chris Lattner Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 41008b43921e18f314c4fd38049291d323830934c36Chris Lattner Instruction *New = 41108b43921e18f314c4fd38049291d323830934c36Chris Lattner BinaryOperator::createAdd(Sub->getOperand(0), NegVal, Name, Sub); 41208b43921e18f314c4fd38049291d323830934c36Chris Lattner 41308b43921e18f314c4fd38049291d323830934c36Chris Lattner // Everyone now refers to the add instruction. 41408b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->replaceAllUsesWith(New); 41508b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->eraseFromParent(); 41600b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 417832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "Negated: " << *New; 41808b43921e18f314c4fd38049291d323830934c36Chris Lattner return New; 41908b43921e18f314c4fd38049291d323830934c36Chris Lattner} 42008b43921e18f314c4fd38049291d323830934c36Chris Lattner 4210975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 4220975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// by one, change this into a multiply by a constant to assist with further 4230975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// reassociation. 4240975ed5f4ef7264b45995241717055f8a116bb27Chris Lattnerstatic Instruction *ConvertShiftToMul(Instruction *Shl) { 42522a66c41f3ab42c15437033851395b0b8288681bChris Lattner // If an operand of this shift is a reassociable multiply, or if the shift 42622a66c41f3ab42c15437033851395b0b8288681bChris Lattner // is used by a reassociable multiply or add, turn into a multiply. 42722a66c41f3ab42c15437033851395b0b8288681bChris Lattner if (isReassociableOp(Shl->getOperand(0), Instruction::Mul) || 42822a66c41f3ab42c15437033851395b0b8288681bChris Lattner (Shl->hasOneUse() && 42922a66c41f3ab42c15437033851395b0b8288681bChris Lattner (isReassociableOp(Shl->use_back(), Instruction::Mul) || 43022a66c41f3ab42c15437033851395b0b8288681bChris Lattner isReassociableOp(Shl->use_back(), Instruction::Add)))) { 43122a66c41f3ab42c15437033851395b0b8288681bChris Lattner Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 43222a66c41f3ab42c15437033851395b0b8288681bChris Lattner MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 43322a66c41f3ab42c15437033851395b0b8288681bChris Lattner 43422a66c41f3ab42c15437033851395b0b8288681bChris Lattner std::string Name = Shl->getName(); Shl->setName(""); 43522a66c41f3ab42c15437033851395b0b8288681bChris Lattner Instruction *Mul = BinaryOperator::createMul(Shl->getOperand(0), MulCst, 43622a66c41f3ab42c15437033851395b0b8288681bChris Lattner Name, Shl); 43722a66c41f3ab42c15437033851395b0b8288681bChris Lattner Shl->replaceAllUsesWith(Mul); 43822a66c41f3ab42c15437033851395b0b8288681bChris Lattner Shl->eraseFromParent(); 43922a66c41f3ab42c15437033851395b0b8288681bChris Lattner return Mul; 44022a66c41f3ab42c15437033851395b0b8288681bChris Lattner } 44122a66c41f3ab42c15437033851395b0b8288681bChris Lattner return 0; 4420975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner} 4430975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner 444109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner// Scan backwards and forwards among values with the same rank as element i to 445109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner// see if X exists. If X does not exist, return i. 446109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattnerstatic unsigned FindInOperandList(std::vector<ValueEntry> &Ops, unsigned i, 447109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Value *X) { 448109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner unsigned XRank = Ops[i].Rank; 449109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner unsigned e = Ops.size(); 450109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) 451109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Ops[j].Op == X) 452109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return j; 453109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // Scan backwards 454109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) 455109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Ops[j].Op == X) 456109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return j; 457109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return i; 458109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner} 459109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 460e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together 461e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// and returning the result. Insert the tree before I. 462e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattnerstatic Value *EmitAddTreeOfValues(Instruction *I, std::vector<Value*> &Ops) { 463e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops.back(); 464e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 465e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *V1 = Ops.back(); 466e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Ops.pop_back(); 467e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *V2 = EmitAddTreeOfValues(I, Ops); 468e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return BinaryOperator::createAdd(V2, V1, "tmp", I); 469e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 470e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 471e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// RemoveFactorFromExpression - If V is an expression tree that is a 472e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// multiplication sequence, and if this sequence contains a multiply by Factor, 473e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// remove Factor from the tree and return the new tree. 474e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris LattnerValue *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { 475e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner BinaryOperator *BO = isReassociableOp(V, Instruction::Mul); 476e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (!BO) return 0; 477e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 478e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner std::vector<ValueEntry> Factors; 479e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner LinearizeExprTree(BO, Factors); 480e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 481e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner bool FoundFactor = false; 482e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner for (unsigned i = 0, e = Factors.size(); i != e; ++i) 483e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Factors[i].Op == Factor) { 484e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner FoundFactor = true; 485e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Factors.erase(Factors.begin()+i); 486e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner break; 487e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 488e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if (!FoundFactor) { 489e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Make sure to restore the operands to the expression tree. 490e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(BO, Factors); 491e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner return 0; 492e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner } 493e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 494e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Factors.size() == 1) return Factors[0].Op; 495e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 496e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(BO, Factors); 497e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return BO; 498e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 499e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 500e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively 501e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// add its operands as factors, otherwise add V to the list of factors. 502e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattnerstatic void FindSingleUseMultiplyFactors(Value *V, 503e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner std::vector<Value*> &Factors) { 504e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner BinaryOperator *BO; 505e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if ((!V->hasOneUse() && !V->use_empty()) || 506e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner !(BO = dyn_cast<BinaryOperator>(V)) || 507e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner BO->getOpcode() != Instruction::Mul) { 508e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner Factors.push_back(V); 509e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner return; 510e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner } 511e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 512e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Otherwise, add the LHS and RHS to the list of factors. 513e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner FindSingleUseMultiplyFactors(BO->getOperand(1), Factors); 514e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner FindSingleUseMultiplyFactors(BO->getOperand(0), Factors); 515e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner} 516e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 517e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 518e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 519e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris LattnerValue *Reassociate::OptimizeExpression(BinaryOperator *I, 520e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner std::vector<ValueEntry> &Ops) { 521469001000620df176decd093a300db84a06cc78bChris Lattner // Now that we have the linearized expression tree, try to optimize it. 522469001000620df176decd093a300db84a06cc78bChris Lattner // Start by folding any constants that we found. 523109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner bool IterateOptimization = false; 524e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops[0].Op; 525469001000620df176decd093a300db84a06cc78bChris Lattner 526e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner unsigned Opcode = I->getOpcode(); 527e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 528469001000620df176decd093a300db84a06cc78bChris Lattner if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 529469001000620df176decd093a300db84a06cc78bChris Lattner if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 530469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 531469001000620df176decd093a300db84a06cc78bChris Lattner Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 532e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return OptimizeExpression(I, Ops); 533469001000620df176decd093a300db84a06cc78bChris Lattner } 534469001000620df176decd093a300db84a06cc78bChris Lattner 535469001000620df176decd093a300db84a06cc78bChris Lattner // Check for destructive annihilation due to a constant being used. 5366b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op)) 537469001000620df176decd093a300db84a06cc78bChris Lattner switch (Opcode) { 538469001000620df176decd093a300db84a06cc78bChris Lattner default: break; 539469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::And: 540469001000620df176decd093a300db84a06cc78bChris Lattner if (CstVal->isNullValue()) { // ... & 0 -> 0 541109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 542e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 543469001000620df176decd093a300db84a06cc78bChris Lattner } else if (CstVal->isAllOnesValue()) { // ... & -1 -> ... 544469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 545469001000620df176decd093a300db84a06cc78bChris Lattner } 546469001000620df176decd093a300db84a06cc78bChris Lattner break; 547469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Mul: 548469001000620df176decd093a300db84a06cc78bChris Lattner if (CstVal->isNullValue()) { // ... * 0 -> 0 549109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 550e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 551b83eb6447ba155342598f0fabe1f08f5baa9164aReid Spencer } else if (cast<ConstantInt>(CstVal)->getZExtValue() == 1) { 552469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); // ... * 1 -> ... 553469001000620df176decd093a300db84a06cc78bChris Lattner } 554469001000620df176decd093a300db84a06cc78bChris Lattner break; 555469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Or: 556469001000620df176decd093a300db84a06cc78bChris Lattner if (CstVal->isAllOnesValue()) { // ... | -1 -> -1 557109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 558e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 559469001000620df176decd093a300db84a06cc78bChris Lattner } 560469001000620df176decd093a300db84a06cc78bChris Lattner // FALLTHROUGH! 561469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Add: 562469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Xor: 563469001000620df176decd093a300db84a06cc78bChris Lattner if (CstVal->isNullValue()) // ... [|^+] 0 -> ... 564469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 565469001000620df176decd093a300db84a06cc78bChris Lattner break; 566469001000620df176decd093a300db84a06cc78bChris Lattner } 567e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops[0].Op; 568469001000620df176decd093a300db84a06cc78bChris Lattner 569469001000620df176decd093a300db84a06cc78bChris Lattner // Handle destructive annihilation do to identities between elements in the 570469001000620df176decd093a300db84a06cc78bChris Lattner // argument list here. 571109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner switch (Opcode) { 572109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner default: break; 573109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner case Instruction::And: 574109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner case Instruction::Or: 575109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner case Instruction::Xor: 576109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 577109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 578109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 579109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // First, check for X and ~X in the operand list. 580368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner assert(i < Ops.size()); 581109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 582109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 583109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner unsigned FoundX = FindInOperandList(Ops, i, X); 584109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (FoundX != i) { 585109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Opcode == Instruction::And) { // ...&X&~X = 0 586109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 587e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return Constant::getNullValue(X->getType()); 588109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } else if (Opcode == Instruction::Or) { // ...|X|~X = -1 589109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 5906b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng return ConstantInt::getAllOnesValue(X->getType()); 591109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 592109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 593109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 594109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 595109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // Next, check for duplicate pairs of values, which we assume are next to 596109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // each other, due to our sorting criteria. 597368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner assert(i < Ops.size()); 598109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 599109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Opcode == Instruction::And || Opcode == Instruction::Or) { 600109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // Drop duplicate values. 601109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Ops.erase(Ops.begin()+i); 602109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner --i; --e; 603109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner IterateOptimization = true; 604109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 605109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } else { 606109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner assert(Opcode == Instruction::Xor); 607ac83b0301ea5ce0e1092fad8f294fe7f046832ffChris Lattner if (e == 2) { 608ac83b0301ea5ce0e1092fad8f294fe7f046832ffChris Lattner ++NumAnnihil; 609e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return Constant::getNullValue(Ops[0].Op->getType()); 610ac83b0301ea5ce0e1092fad8f294fe7f046832ffChris Lattner } 611109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // ... X^X -> ... 612109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 613ac83b0301ea5ce0e1092fad8f294fe7f046832ffChris Lattner i -= 1; e -= 2; 614109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner IterateOptimization = true; 615109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 616109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 617109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 618109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 619109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner break; 620109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 621109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner case Instruction::Add: 622109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // Scan the operand lists looking for X and -X pairs. If we find any, we 623e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // can simplify the expression. X+-X == 0. 624109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 625368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner assert(i < Ops.size()); 626109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // Check for X and -X in the operand list. 627109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (BinaryOperator::isNeg(Ops[i].Op)) { 628109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Value *X = BinaryOperator::getNegArgument(Ops[i].Op); 629109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner unsigned FoundX = FindInOperandList(Ops, i, X); 630109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (FoundX != i) { 631109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // Remove X and -X from the operand list. 632109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Ops.size() == 2) { 633109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 634e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return Constant::getNullValue(X->getType()); 635109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } else { 636109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Ops.erase(Ops.begin()+i); 637368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner if (i < FoundX) 638368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner --FoundX; 639368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner else 640368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner --i; // Need to back up an extra one. 641109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Ops.erase(Ops.begin()+FoundX); 642109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner IterateOptimization = true; 643109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 644368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner --i; // Revisit element. 645368a3aabb2b48ad6e39d23d1c6cbdfe0c5857483Chris Lattner e -= 2; // Removed two elements. 646109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 647109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 648109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 649109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 650e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 651e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 652e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // Scan the operand list, checking to see if there are any common factors 653e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // between operands. Consider something like A*A+A*B*C+D. We would like to 654e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies. 655e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // To efficiently find this, we count the number of times a factor occurs 656e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // for any ADD operands that are MULs. 657e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner std::map<Value*, unsigned> FactorOccurrences; 658e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner unsigned MaxOcc = 0; 659e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *MaxOccVal = 0; 66024d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 66124d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op)) { 66224d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer if (BOp->getOpcode() == Instruction::Mul && BOp->use_empty()) { 66324d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer // Compute all of the factors of this added value. 66424d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer std::vector<Value*> Factors; 66524d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer FindSingleUseMultiplyFactors(BOp, Factors); 66624d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer assert(Factors.size() > 1 && "Bad linearize!"); 66724d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer 66824d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer // Add one to FactorOccurrences for each unique factor in this op. 66924d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer if (Factors.size() == 2) { 67024d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer unsigned Occ = ++FactorOccurrences[Factors[0]]; 67124d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[0]; } 67224d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer if (Factors[0] != Factors[1]) { // Don't double count A*A. 67324d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer Occ = ++FactorOccurrences[Factors[1]]; 67424d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[1]; } 67524d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer } 67624d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer } else { 67724d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer std::set<Value*> Duplicates; 67824d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 67924d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer if (Duplicates.insert(Factors[i]).second) { 68024d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer unsigned Occ = ++FactorOccurrences[Factors[i]]; 68124d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[i]; } 682e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 683e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 684e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 68524d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer } 686e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 687e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 688e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 689e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // If any factor occurred more than one time, we can pull it out. 690e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (MaxOcc > 1) { 691832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << "\n"; 692e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 693e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // Create a new instruction that uses the MaxOccVal twice. If we don't do 694e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // this, we could otherwise run into situations where removing a factor 695e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // from an expression will drop a use of maxocc, and this can cause 696e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // RemoveFactorFromExpression on successive values to behave differently. 697e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Instruction *DummyInst = BinaryOperator::createAdd(MaxOccVal, MaxOccVal); 698e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner std::vector<Value*> NewMulOps; 699e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 700e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { 701e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner NewMulOps.push_back(V); 702e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Ops.erase(Ops.begin()+i); 703e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner --i; --e; 704e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 705e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 706e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 707e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // No need for extra uses anymore. 708e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner delete DummyInst; 709e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 710e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner unsigned NumAddedValues = NewMulOps.size(); 711e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *V = EmitAddTreeOfValues(I, NewMulOps); 712e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner Value *V2 = BinaryOperator::createMul(V, MaxOccVal, "tmp", I); 713e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 714e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Now that we have inserted V and its sole use, optimize it. This allows 715e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // us to handle cases that require multiple factoring steps, such as this: 716e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C)) 717e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if (NumAddedValues > 1) 718e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner ReassociateExpression(cast<BinaryOperator>(V)); 719e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 720e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner ++NumFactor; 721e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 722e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 0) 723e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner return V2; 724e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 725e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // Add the new value to the list of things being added. 726e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); 727e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 728e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // Rewrite the tree so that there is now a use of V. 729e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(I, Ops); 730e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return OptimizeExpression(I, Ops); 731e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 732109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner break; 733109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner //case Instruction::Mul: 734109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 735109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 73600b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen if (IterateOptimization) 737e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return OptimizeExpression(I, Ops); 738e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return 0; 739469001000620df176decd093a300db84a06cc78bChris Lattner} 740469001000620df176decd093a300db84a06cc78bChris Lattner 74108b43921e18f314c4fd38049291d323830934c36Chris Lattner 74208b43921e18f314c4fd38049291d323830934c36Chris Lattner/// ReassociateBB - Inspect all of the instructions in this basic block, 74308b43921e18f314c4fd38049291d323830934c36Chris Lattner/// reassociating them as we go. 744c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::ReassociateBB(BasicBlock *BB) { 745e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner for (BasicBlock::iterator BBI = BB->begin(); BBI != BB->end(); ) { 746e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Instruction *BI = BBI++; 747641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner if (BI->getOpcode() == Instruction::Shl && 748641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner isa<ConstantInt>(BI->getOperand(1))) 749641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner if (Instruction *NI = ConvertShiftToMul(BI)) { 750641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner MadeChange = true; 751641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner BI = NI; 752641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner } 753641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner 7546f156856ca23394122f39d92fe74eec40a1f7c27Chris Lattner // Reject cases where it is pointless to do this. 755e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPoint() || 756ae74f555522298bef3be8a173163bf778d59adf9Chris Lattner isa<PackedType>(BI->getType())) 7576f156856ca23394122f39d92fe74eec40a1f7c27Chris Lattner continue; // Floating point ops are not associative. 7586f156856ca23394122f39d92fe74eec40a1f7c27Chris Lattner 75908b43921e18f314c4fd38049291d323830934c36Chris Lattner // If this is a subtract instruction which is not already in negate form, 76008b43921e18f314c4fd38049291d323830934c36Chris Lattner // see if we can convert it to X+-Y. 761f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (BI->getOpcode() == Instruction::Sub) { 762f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (!BinaryOperator::isNeg(BI)) { 763f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (Instruction *NI = BreakUpSubtract(BI)) { 764f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner MadeChange = true; 765f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner BI = NI; 766f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 767f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } else { 768f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // Otherwise, this is a negation. See if the operand is a multiply tree 769f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // and if this is not an inner node of a multiply tree. 770f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (isReassociableOp(BI->getOperand(1), Instruction::Mul) && 771f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner (!BI->hasOneUse() || 772f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner !isReassociableOp(BI->use_back(), Instruction::Mul))) { 773f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner BI = LowerNegateToMultiply(BI); 774f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner MadeChange = true; 775f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 77608b43921e18f314c4fd38049291d323830934c36Chris Lattner } 777f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 778e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 779c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If this instruction is a commutative binary operator, process it. 780c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!BI->isAssociative()) continue; 781c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *I = cast<BinaryOperator>(BI); 78200b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 783c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If this is an interior node of a reassociable tree, ignore it until we 784c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // get to the root of the tree, to avoid N^2 analysis. 785c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode())) 786c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner continue; 787c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 7887b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner // If this is an add tree that is used by a sub instruction, ignore it 7897b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner // until we process the subtract. 7907b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner if (I->hasOneUse() && I->getOpcode() == Instruction::Add && 7917b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub) 7927b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner continue; 7937b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner 794895b392269cad07c34d59110d68dc86708c53adbChris Lattner ReassociateExpression(I); 795895b392269cad07c34d59110d68dc86708c53adbChris Lattner } 796895b392269cad07c34d59110d68dc86708c53adbChris Lattner} 797c9fd097a01383323f166c14c17d3984620cad766Chris Lattner 798895b392269cad07c34d59110d68dc86708c53adbChris Lattnervoid Reassociate::ReassociateExpression(BinaryOperator *I) { 799895b392269cad07c34d59110d68dc86708c53adbChris Lattner 800895b392269cad07c34d59110d68dc86708c53adbChris Lattner // First, walk the expression tree, linearizing the tree, collecting 801895b392269cad07c34d59110d68dc86708c53adbChris Lattner std::vector<ValueEntry> Ops; 802895b392269cad07c34d59110d68dc86708c53adbChris Lattner LinearizeExprTree(I, Ops); 803895b392269cad07c34d59110d68dc86708c53adbChris Lattner 804832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "RAIn:\t"; DEBUG(PrintOps(I, Ops)); DOUT << "\n"; 805895b392269cad07c34d59110d68dc86708c53adbChris Lattner 806895b392269cad07c34d59110d68dc86708c53adbChris Lattner // Now that we have linearized the tree to a list and have gathered all of 807895b392269cad07c34d59110d68dc86708c53adbChris Lattner // the operands and their ranks, sort the operands by their rank. Use a 808895b392269cad07c34d59110d68dc86708c53adbChris Lattner // stable_sort so that values with equal ranks will have their relative 809895b392269cad07c34d59110d68dc86708c53adbChris Lattner // positions maintained (and so the compiler is deterministic). Note that 810895b392269cad07c34d59110d68dc86708c53adbChris Lattner // this sorts so that the highest ranking values end up at the beginning of 811895b392269cad07c34d59110d68dc86708c53adbChris Lattner // the vector. 812895b392269cad07c34d59110d68dc86708c53adbChris Lattner std::stable_sort(Ops.begin(), Ops.end()); 813895b392269cad07c34d59110d68dc86708c53adbChris Lattner 814895b392269cad07c34d59110d68dc86708c53adbChris Lattner // OptimizeExpression - Now that we have the expression tree in a convenient 815895b392269cad07c34d59110d68dc86708c53adbChris Lattner // sorted form, optimize it globally if possible. 816895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (Value *V = OptimizeExpression(I, Ops)) { 817895b392269cad07c34d59110d68dc86708c53adbChris Lattner // This expression tree simplified to something that isn't a tree, 818895b392269cad07c34d59110d68dc86708c53adbChris Lattner // eliminate it. 819832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "Reassoc to scalar: " << *V << "\n"; 820895b392269cad07c34d59110d68dc86708c53adbChris Lattner I->replaceAllUsesWith(V); 821895b392269cad07c34d59110d68dc86708c53adbChris Lattner RemoveDeadBinaryOp(I); 822895b392269cad07c34d59110d68dc86708c53adbChris Lattner return; 823895b392269cad07c34d59110d68dc86708c53adbChris Lattner } 824895b392269cad07c34d59110d68dc86708c53adbChris Lattner 825895b392269cad07c34d59110d68dc86708c53adbChris Lattner // We want to sink immediates as deeply as possible except in the case where 826895b392269cad07c34d59110d68dc86708c53adbChris Lattner // this is a multiply tree used only by an add, and the immediate is a -1. 827895b392269cad07c34d59110d68dc86708c53adbChris Lattner // In this case we reassociate to put the negation on the outside so that we 828895b392269cad07c34d59110d68dc86708c53adbChris Lattner // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y 829895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (I->getOpcode() == Instruction::Mul && I->hasOneUse() && 830895b392269cad07c34d59110d68dc86708c53adbChris Lattner cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add && 831895b392269cad07c34d59110d68dc86708c53adbChris Lattner isa<ConstantInt>(Ops.back().Op) && 832895b392269cad07c34d59110d68dc86708c53adbChris Lattner cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) { 833895b392269cad07c34d59110d68dc86708c53adbChris Lattner Ops.insert(Ops.begin(), Ops.back()); 834895b392269cad07c34d59110d68dc86708c53adbChris Lattner Ops.pop_back(); 835895b392269cad07c34d59110d68dc86708c53adbChris Lattner } 836895b392269cad07c34d59110d68dc86708c53adbChris Lattner 837832171cb9724d2d31c8dfb73172e2be8f6dd13eeBill Wendling DOUT << "RAOut:\t"; DEBUG(PrintOps(I, Ops)); DOUT << "\n"; 838895b392269cad07c34d59110d68dc86708c53adbChris Lattner 839895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (Ops.size() == 1) { 840895b392269cad07c34d59110d68dc86708c53adbChris Lattner // This expression tree simplified to something that isn't a tree, 841895b392269cad07c34d59110d68dc86708c53adbChris Lattner // eliminate it. 842895b392269cad07c34d59110d68dc86708c53adbChris Lattner I->replaceAllUsesWith(Ops[0].Op); 843895b392269cad07c34d59110d68dc86708c53adbChris Lattner RemoveDeadBinaryOp(I); 844895b392269cad07c34d59110d68dc86708c53adbChris Lattner } else { 845895b392269cad07c34d59110d68dc86708c53adbChris Lattner // Now that we ordered and optimized the expressions, splat them back into 846895b392269cad07c34d59110d68dc86708c53adbChris Lattner // the expression tree, removing any unneeded nodes. 847e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(I, Ops); 8484fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 8494fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 8504fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 8514fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 8527e70829632f82de15db187845666aaca6e04b792Chris Lattnerbool Reassociate::runOnFunction(Function &F) { 8534fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Recalculate the rank map for F 8544fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner BuildRankMap(F); 8554fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 856c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = false; 8577e70829632f82de15db187845666aaca6e04b792Chris Lattner for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 858c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ReassociateBB(FI); 8594fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 8604fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // We are done with the rank map... 8614fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner RankMap.clear(); 862fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner ValueRankMap.clear(); 863c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return MadeChange; 8644fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 865d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 866