Reassociate.cpp revision f8a447de162a2896a8a044931fb63de713dbc6b9
14fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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" 2903afd02ca2486aebb3b29edd2f77920d4e5020fdDale Johannesen#include "llvm/IntrinsicInst.h" 304fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Pass.h" 31c9fd097a01383323f166c14c17d3984620cad766Chris Lattner#include "llvm/Assembly/Writer.h" 324fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Support/CFG.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 34d3c7b7359d4992b9ab9f8e12ccd0a9b7d2446566Chris Lattner#include "llvm/Support/ValueHandle.h" 35bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 36551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/PostOrderIterator.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 38ec531233a16605756a84d175178e1ee0fac4791cChris Lattner#include "llvm/ADT/DenseMap.h" 39c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner#include <algorithm> 40c9235d2e855c56e9aa157969f8132a05f9ba89d8Dan Gohman#include <map> 41d7456026629fc1760a45e6e955e9834246493147Chris Lattnerusing namespace llvm; 42d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 430e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumLinear , "Number of insts linearized"); 440e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumChanged, "Number of insts reassociated"); 450e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumAnnihil, "Number of expr tree annihilated"); 460e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumFactor , "Number of multiplies factored"); 47a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 480e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 493e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct ValueEntry { 50c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner unsigned Rank; 51c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Value *Op; 52c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 53c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner }; 54c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 55c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 56c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 57e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 58c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 5950cacb2a520b93530e79220a307c907163b9e370Devang Patel#ifndef NDEBUG 60e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// PrintOps - Print out the expression identified in the Ops list. 61e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// 629f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattnerstatic void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) { 63e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Module *M = I->getParent()->getParent()->getParent(); 6479c5d3f9717756dc3ff56cfcaa3ae1a5930c457aChris Lattner errs() << Instruction::getOpcodeName(I->getOpcode()) << " " 651befe643b2a030f5e2433ce0034a27fb65b5f26bChris Lattner << *Ops[0].Op->getType() << '\t'; 667de3b5db26bb3c8dcca5348fb7c0be4f9bd1bcb7Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 671befe643b2a030f5e2433ce0034a27fb65b5f26bChris Lattner errs() << "[ "; 681befe643b2a030f5e2433ce0034a27fb65b5f26bChris Lattner WriteAsOperand(errs(), Ops[i].Op, false, M); 691befe643b2a030f5e2433ce0034a27fb65b5f26bChris Lattner errs() << ", #" << Ops[i].Rank << "] "; 707de3b5db26bb3c8dcca5348fb7c0be4f9bd1bcb7Chris Lattner } 71e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 7259500c8f9a76b3386329b6f837255c16f4e8b61bDevang Patel#endif 73e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 74844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 753e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class Reassociate : public FunctionPass { 760c0edf8afc35a42b15a24ebb5fa5f3fc674290aeChris Lattner std::map<BasicBlock*, unsigned> RankMap; 77d3c7b7359d4992b9ab9f8e12ccd0a9b7d2446566Chris Lattner std::map<AssertingVH<>, unsigned> ValueRankMap; 78c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner bool MadeChange; 794fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner public: 80ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 81ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman Reassociate() : FunctionPass(&ID) {} 82794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 837e70829632f82de15db187845666aaca6e04b792Chris Lattner bool runOnFunction(Function &F); 844fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 854fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 86cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 874fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 884fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner private: 897e70829632f82de15db187845666aaca6e04b792Chris Lattner void BuildRankMap(Function &F); 904fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned getRank(Value *V); 9169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *ReassociateExpression(BinaryOperator *I); 929f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops, 93e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner unsigned Idx = 0); 949f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner Value *OptimizeExpression(BinaryOperator *I, 959f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops); 969f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops); 979f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner void LinearizeExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 98c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void LinearizeExpr(BinaryOperator *I); 99e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *RemoveFactorFromExpression(Value *V, Value *Factor); 100c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void ReassociateBB(BasicBlock *BB); 101e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 102e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner void RemoveDeadBinaryOp(Value *V); 1034fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner }; 1044fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1054fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 106844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar Reassociate::ID = 0; 107844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<Reassociate> X("reassociate", "Reassociate expressions"); 108844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 109d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the Reassociate pass 110d7456026629fc1760a45e6e955e9834246493147Chris LattnerFunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 1114fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 112e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattnervoid Reassociate::RemoveDeadBinaryOp(Value *V) { 113e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Instruction *Op = dyn_cast<Instruction>(V); 11469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner if (!Op || !isa<BinaryOperator>(Op) || !Op->use_empty()) 115e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer return; 116e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 117e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1); 11869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 11969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner ValueRankMap.erase(Op); 12069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Op->eraseFromParent(); 121e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(LHS); 122e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(RHS); 123e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 124e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 1259c723199384b16899831937e2800d52f4f953569Chris Lattner 1269c723199384b16899831937e2800d52f4f953569Chris Lattnerstatic bool isUnmovableInstruction(Instruction *I) { 1279c723199384b16899831937e2800d52f4f953569Chris Lattner if (I->getOpcode() == Instruction::PHI || 1289c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Alloca || 1299c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Load || 1309c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Invoke || 13103afd02ca2486aebb3b29edd2f77920d4e5020fdDale Johannesen (I->getOpcode() == Instruction::Call && 13203afd02ca2486aebb3b29edd2f77920d4e5020fdDale Johannesen !isa<DbgInfoIntrinsic>(I)) || 1331628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::UDiv || 1341628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::SDiv || 1351628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::FDiv || 1360a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::URem || 1370a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::SRem || 1380a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::FRem) 1399c723199384b16899831937e2800d52f4f953569Chris Lattner return true; 1409c723199384b16899831937e2800d52f4f953569Chris Lattner return false; 1419c723199384b16899831937e2800d52f4f953569Chris Lattner} 1429c723199384b16899831937e2800d52f4f953569Chris Lattner 1437e70829632f82de15db187845666aaca6e04b792Chris Lattnervoid Reassociate::BuildRankMap(Function &F) { 1446007cb6c4d923e2dee4a1133fb6d1bb00a37062dChris Lattner unsigned i = 2; 145fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 146fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner // Assign distinct ranks to function arguments 147e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 148d3c7b7359d4992b9ab9f8e12ccd0a9b7d2446566Chris Lattner ValueRankMap[&*I] = ++i; 149fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 1507e70829632f82de15db187845666aaca6e04b792Chris Lattner ReversePostOrderTraversal<Function*> RPOT(&F); 1514fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 1529c723199384b16899831937e2800d52f4f953569Chris Lattner E = RPOT.end(); I != E; ++I) { 1539c723199384b16899831937e2800d52f4f953569Chris Lattner BasicBlock *BB = *I; 1549c723199384b16899831937e2800d52f4f953569Chris Lattner unsigned BBRank = RankMap[BB] = ++i << 16; 1559c723199384b16899831937e2800d52f4f953569Chris Lattner 1569c723199384b16899831937e2800d52f4f953569Chris Lattner // Walk the basic block, adding precomputed ranks for any instructions that 1579c723199384b16899831937e2800d52f4f953569Chris Lattner // we cannot move. This ensures that the ranks for these instructions are 1589c723199384b16899831937e2800d52f4f953569Chris Lattner // all different in the block. 1599c723199384b16899831937e2800d52f4f953569Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 1609c723199384b16899831937e2800d52f4f953569Chris Lattner if (isUnmovableInstruction(I)) 161d3c7b7359d4992b9ab9f8e12ccd0a9b7d2446566Chris Lattner ValueRankMap[&*I] = ++BBRank; 1629c723199384b16899831937e2800d52f4f953569Chris Lattner } 1634fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1644fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1654fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnerunsigned Reassociate::getRank(Value *V) { 166fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument... 167fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 16808b43921e18f314c4fd38049291d323830934c36Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 16908b43921e18f314c4fd38049291d323830934c36Chris Lattner if (I == 0) return 0; // Otherwise it's a global or constant, rank 0. 1704fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 17108b43921e18f314c4fd38049291d323830934c36Chris Lattner unsigned &CachedRank = ValueRankMap[I]; 17208b43921e18f314c4fd38049291d323830934c36Chris Lattner if (CachedRank) return CachedRank; // Rank already known? 17300b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 17408b43921e18f314c4fd38049291d323830934c36Chris Lattner // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 17508b43921e18f314c4fd38049291d323830934c36Chris Lattner // we can reassociate expressions for code motion! Since we do not recurse 17608b43921e18f314c4fd38049291d323830934c36Chris Lattner // for PHI nodes, we cannot have infinite recursion here, because there 17708b43921e18f314c4fd38049291d323830934c36Chris Lattner // cannot be loops in the value graph that do not go through PHI nodes. 17808b43921e18f314c4fd38049291d323830934c36Chris Lattner unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 17908b43921e18f314c4fd38049291d323830934c36Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); 18008b43921e18f314c4fd38049291d323830934c36Chris Lattner i != e && Rank != MaxRank; ++i) 18108b43921e18f314c4fd38049291d323830934c36Chris Lattner Rank = std::max(Rank, getRank(I->getOperand(i))); 18200b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 183cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner // If this is a not or neg instruction, do not count it for rank. This 184cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner // assures us that X and ~X will have the same rank. 18542a75517250017a52afb03a0ade03cbd49559fe5Chris Lattner if (!I->getType()->isInteger() || 186fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 187cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner ++Rank; 188cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner 189bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner //DEBUG(errs() << "Calculated Rank[" << V->getName() << "] = " 190bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner // << Rank << "\n"); 19100b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 192cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner return CachedRank = Rank; 1934fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1944fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 195c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// isReassociableOp - Return true if V is an instruction of the specified 196c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// opcode and if it only has one use. 197c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnerstatic BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 198e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if ((V->hasOneUse() || V->use_empty()) && isa<Instruction>(V) && 199c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner cast<Instruction>(V)->getOpcode() == Opcode) 200c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return cast<BinaryOperator>(V); 201c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return 0; 202c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 2034fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 204f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner/// LowerNegateToMultiply - Replace 0-X with X*-1. 205f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner/// 206f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesenstatic Instruction *LowerNegateToMultiply(Instruction *Neg, 207e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky std::map<AssertingVH<>, unsigned> &ValueRankMap) { 208a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Constant *Cst = Constant::getAllOnesValue(Neg->getType()); 209f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 2107cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction *Res = BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg); 211f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesen ValueRankMap.erase(Neg); 2126934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner Res->takeName(Neg); 213f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner Neg->replaceAllUsesWith(Res); 214f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner Neg->eraseFromParent(); 215f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner return Res; 216f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner} 217f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 218c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. 219c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// Note that if D is also part of the expression tree that we recurse to 220c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// linearize it as well. Besides that case, this does not recurse into A,B, or 221c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// C. 222c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::LinearizeExpr(BinaryOperator *I) { 223c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 224c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1)); 22500b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen assert(isReassociableOp(LHS, I->getOpcode()) && 226c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner isReassociableOp(RHS, I->getOpcode()) && 227c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner "Not an expression that needs linearization?"); 228c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 229bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "Linear" << *LHS << '\n' << *RHS << '\n' << *I << '\n'); 230c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 231c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move the RHS instruction to live immediately before I, avoiding breaking 232c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // dominator properties. 2334bc5f8071a28b6fc4f4c2207dd03a5f747d0d84bChris Lattner RHS->moveBefore(I); 234c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 235c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move operands around to do the linearization. 236c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, RHS->getOperand(0)); 237c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHS->setOperand(0, LHS); 238c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(0, RHS); 23900b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 240c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumLinear; 241c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 242bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "Linearized: " << *I << '\n'); 243fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 244c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If D is part of this expression tree, tail recurse. 245c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (isReassociableOp(I->getOperand(1), I->getOpcode())) 246c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExpr(I); 247c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 2484fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 249e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 250c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// LinearizeExprTree - Given an associative binary expression tree, traverse 251c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// all of the uses putting it into canonical form. This forces a left-linear 252c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// form of the the expression (((a+b)+c)+d), and collects information about the 253c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// rank of the non-tree operands. 254c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// 255e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// NOTE: These intentionally destroys the expression tree operands (turning 256e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// them into undef values) to reduce #uses of the values. This means that the 257e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// caller MUST use something like RewriteExprTree to put the values back in. 258e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// 259c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::LinearizeExprTree(BinaryOperator *I, 2609f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops) { 261c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); 262c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner unsigned Opcode = I->getOpcode(); 263c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 264c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // First step, linearize the expression if it is in ((A+B)+(C+D)) form. 265c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); 266c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); 267c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 268f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // If this is a multiply expression tree and it contains internal negations, 269f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // transform them into multiplies by -1 so they can be reassociated. 270f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (I->getOpcode() == Instruction::Mul) { 271fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson if (!LHSBO && LHS->hasOneUse() && BinaryOperator::isNeg(LHS)) { 272e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky LHS = LowerNegateToMultiply(cast<Instruction>(LHS), ValueRankMap); 273f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner LHSBO = isReassociableOp(LHS, Opcode); 274f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 275fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson if (!RHSBO && RHS->hasOneUse() && BinaryOperator::isNeg(RHS)) { 276e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky RHS = LowerNegateToMultiply(cast<Instruction>(RHS), ValueRankMap); 277f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner RHSBO = isReassociableOp(RHS, Opcode); 278f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 279f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 280f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 281c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!LHSBO) { 282c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!RHSBO) { 283c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Neither the LHS or RHS as part of the tree, thus this is a leaf. As 284c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // such, just remember these operands and their rank. 285c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(LHS), LHS)); 286c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(RHS), RHS)); 287e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 288e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Clear the leaves out. 2899e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I->setOperand(0, UndefValue::get(I->getType())); 2909e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I->setOperand(1, UndefValue::get(I->getType())); 291c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return; 292c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 293f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 294f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Turn X+(Y+Z) -> (Y+Z)+X 295f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner std::swap(LHSBO, RHSBO); 296f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner std::swap(LHS, RHS); 297f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner bool Success = !I->swapOperands(); 298f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner assert(Success && "swapOperands failed"); 299f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Success = false; 300f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner MadeChange = true; 301c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } else if (RHSBO) { 302c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the the RHS is not 303c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // part of the expression tree. 304c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExpr(I); 305c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0)); 306c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHS = I->getOperand(1); 307c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHSBO = 0; 3084fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 309fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 310c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Okay, now we know that the LHS is a nested expression and that the RHS is 311c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // not. Perform reassociation. 312c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); 3134fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 314c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move LHS right before I to make sure that the tree expression dominates all 315c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // values. 3164bc5f8071a28b6fc4f4c2207dd03a5f747d0d84bChris Lattner LHSBO->moveBefore(I); 317c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 318c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Linearize the expression tree on the LHS. 319c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExprTree(LHSBO, Ops); 320c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 321c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Remember the RHS operand and its rank. 322c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(RHS), RHS)); 323e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 324e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Clear the RHS leaf out. 3259e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I->setOperand(1, UndefValue::get(I->getType())); 326c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 327c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 328c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// RewriteExprTree - Now that the operands for this expression tree are 329c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// linearized and optimized, emit them in-order. This function is written to be 330c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// tail recursive. 331e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattnervoid Reassociate::RewriteExprTree(BinaryOperator *I, 3329f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops, 333e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner unsigned i) { 334c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (i+2 == Ops.size()) { 335c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->getOperand(0) != Ops[i].Op || 336c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->getOperand(1) != Ops[i+1].Op) { 337e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *OldLHS = I->getOperand(0); 338bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "RA: " << *I << '\n'); 339c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(0, Ops[i].Op); 340c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, Ops[i+1].Op); 341bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "TO: " << *I << '\n'); 342c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 343c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumChanged; 344e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 345e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // If we reassociated a tree to fewer operands (e.g. (1+a+2) -> (a+3) 346e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // delete the extra, now dead, nodes. 347e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(OldLHS); 348c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 349c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return; 350c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 351c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(i+2 < Ops.size() && "Ops index out of range!"); 352c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 353c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->getOperand(1) != Ops[i].Op) { 354bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "RA: " << *I << '\n'); 355c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, Ops[i].Op); 356bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "TO: " << *I << '\n'); 357c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 358c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumChanged; 359c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 360e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 361e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 362e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner assert(LHS->getOpcode() == I->getOpcode() && 363e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner "Improper expression tree!"); 364e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 365e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // Compactify the tree instructions together with each other to guarantee 366e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // that the expression tree is dominated by all of Ops. 367e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner LHS->moveBefore(I); 368e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(LHS, Ops, i+1); 3694fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 3704fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 3714fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 372c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 373a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// NegateValue - Insert instructions before the instruction pointed to by BI, 374a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that computes the negative version of the value specified. The negative 375a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// version of the value is returned, and BI is left pointing at the instruction 376a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that should be processed next by the reassociation pass. 377a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// 378e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewyckystatic Value *NegateValue(Value *V, Instruction *BI) { 379a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // We are trying to expose opportunity for reassociation. One of the things 380a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // that we want to do to achieve this is to push a negation as deep into an 381a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // expression chain as possible, to expose the add instructions. In practice, 382a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // this means that we turn this: 383a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 384a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 385a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // the constants. We assume that instcombine will clean up the mess later if 3865560c9d49ccae132cabf1155f18aa0480dce3edaMisha Brukman // we introduce tons of unnecessary negation instructions... 387a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 388a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 389fd05924946ebfcfb3409b21996cfd0836e4ddb31Chris Lattner if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 3902cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // Push the negates through the add. 391e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky I->setOperand(0, NegateValue(I->getOperand(0), BI)); 392e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky I->setOperand(1, NegateValue(I->getOperand(1), BI)); 3932cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner 3942cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // We must move the add instruction here, because the neg instructions do 3952cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // not dominate the old add instruction in general. By moving it, we are 3962cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // assured that the neg instructions we just inserted dominate the 3972cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // instruction we are about to insert after them. 398a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 3992cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner I->moveBefore(BI); 4002cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner I->setName(I->getName()+".neg"); 4012cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner return I; 402a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner } 403a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 404a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Insert a 'neg' instruction that subtracts the value from zero to get the 405a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // negation. 406a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 4074ae5126d041768ab9665cf2f11c024becd76c41fDan Gohman return BinaryOperator::CreateNeg(V, V->getName() + ".neg", BI); 408a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner} 409a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 4109bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner/// ShouldBreakUpSubtract - Return true if we should break up this subtract of 4119bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner/// X-Y into (X + -Y). 412e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewyckystatic bool ShouldBreakUpSubtract(Instruction *Sub) { 4139bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner // If this is a negation, we can't split it up! 414fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson if (BinaryOperator::isNeg(Sub)) 4159bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return false; 4169bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner 4179bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner // Don't bother to break this up unless either the LHS is an associable add or 4180b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner // subtract or if this is only used by one. 4190b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner if (isReassociableOp(Sub->getOperand(0), Instruction::Add) || 4200b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner isReassociableOp(Sub->getOperand(0), Instruction::Sub)) 4219bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return true; 4220b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner if (isReassociableOp(Sub->getOperand(1), Instruction::Add) || 4235329bb22e9b6374d62919981c1ef8775b42945ebChris Lattner isReassociableOp(Sub->getOperand(1), Instruction::Sub)) 4249bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return true; 4250b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner if (Sub->hasOneUse() && 4260b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner (isReassociableOp(Sub->use_back(), Instruction::Add) || 4270b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner isReassociableOp(Sub->use_back(), Instruction::Sub))) 4289bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return true; 4299bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner 4309bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return false; 4319bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner} 4329bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner 43308b43921e18f314c4fd38049291d323830934c36Chris Lattner/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 43408b43921e18f314c4fd38049291d323830934c36Chris Lattner/// only used by an add, transform this into (X+(0-Y)) to promote better 43508b43921e18f314c4fd38049291d323830934c36Chris Lattner/// reassociation. 436e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewyckystatic Instruction *BreakUpSubtract(Instruction *Sub, 437d3c7b7359d4992b9ab9f8e12ccd0a9b7d2446566Chris Lattner std::map<AssertingVH<>, unsigned> &ValueRankMap) { 43808b43921e18f314c4fd38049291d323830934c36Chris Lattner // Convert a subtract into an add and a neg instruction... so that sub 43908b43921e18f314c4fd38049291d323830934c36Chris Lattner // instructions can be commuted with other add instructions... 44008b43921e18f314c4fd38049291d323830934c36Chris Lattner // 44108b43921e18f314c4fd38049291d323830934c36Chris Lattner // Calculate the negative value of Operand 1 of the sub instruction... 44208b43921e18f314c4fd38049291d323830934c36Chris Lattner // and set it as the RHS of the add instruction we just made... 44308b43921e18f314c4fd38049291d323830934c36Chris Lattner // 444e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 44508b43921e18f314c4fd38049291d323830934c36Chris Lattner Instruction *New = 4467cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub); 4476934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner New->takeName(Sub); 44808b43921e18f314c4fd38049291d323830934c36Chris Lattner 44908b43921e18f314c4fd38049291d323830934c36Chris Lattner // Everyone now refers to the add instruction. 450f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesen ValueRankMap.erase(Sub); 45108b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->replaceAllUsesWith(New); 45208b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->eraseFromParent(); 45300b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 454bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "Negated: " << *New << '\n'); 45508b43921e18f314c4fd38049291d323830934c36Chris Lattner return New; 45608b43921e18f314c4fd38049291d323830934c36Chris Lattner} 45708b43921e18f314c4fd38049291d323830934c36Chris Lattner 4580975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 4590975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// by one, change this into a multiply by a constant to assist with further 4600975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// reassociation. 461f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesenstatic Instruction *ConvertShiftToMul(Instruction *Shl, 462e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky std::map<AssertingVH<>, unsigned> &ValueRankMap) { 46322a66c41f3ab42c15437033851395b0b8288681bChris Lattner // If an operand of this shift is a reassociable multiply, or if the shift 46422a66c41f3ab42c15437033851395b0b8288681bChris Lattner // is used by a reassociable multiply or add, turn into a multiply. 46522a66c41f3ab42c15437033851395b0b8288681bChris Lattner if (isReassociableOp(Shl->getOperand(0), Instruction::Mul) || 46622a66c41f3ab42c15437033851395b0b8288681bChris Lattner (Shl->hasOneUse() && 46722a66c41f3ab42c15437033851395b0b8288681bChris Lattner (isReassociableOp(Shl->use_back(), Instruction::Mul) || 46822a66c41f3ab42c15437033851395b0b8288681bChris Lattner isReassociableOp(Shl->use_back(), Instruction::Add)))) { 469eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 470f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 47122a66c41f3ab42c15437033851395b0b8288681bChris Lattner 472f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Instruction *Mul = 473f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl); 474f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesen ValueRankMap.erase(Shl); 4756934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner Mul->takeName(Shl); 47622a66c41f3ab42c15437033851395b0b8288681bChris Lattner Shl->replaceAllUsesWith(Mul); 47722a66c41f3ab42c15437033851395b0b8288681bChris Lattner Shl->eraseFromParent(); 47822a66c41f3ab42c15437033851395b0b8288681bChris Lattner return Mul; 47922a66c41f3ab42c15437033851395b0b8288681bChris Lattner } 48022a66c41f3ab42c15437033851395b0b8288681bChris Lattner return 0; 4810975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner} 4820975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner 483109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner// Scan backwards and forwards among values with the same rank as element i to 484109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner// see if X exists. If X does not exist, return i. 4859f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattnerstatic unsigned FindInOperandList(SmallVectorImpl<ValueEntry> &Ops, unsigned i, 486109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Value *X) { 487109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner unsigned XRank = Ops[i].Rank; 488109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner unsigned e = Ops.size(); 489109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) 490109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Ops[j].Op == X) 491109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return j; 492109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner // Scan backwards 493109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) 494109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Ops[j].Op == X) 495109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return j; 496109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return i; 497109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner} 498109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 499e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together 500e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// and returning the result. Insert the tree before I. 5018d93b259f6d6ece634df86d5df453efc0c918546Chris Lattnerstatic Value *EmitAddTreeOfValues(Instruction *I, SmallVectorImpl<Value*> &Ops){ 502e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops.back(); 503e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 504e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *V1 = Ops.back(); 505e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Ops.pop_back(); 506e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *V2 = EmitAddTreeOfValues(I, Ops); 5077cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif return BinaryOperator::CreateAdd(V2, V1, "tmp", I); 508e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 509e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 510e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// RemoveFactorFromExpression - If V is an expression tree that is a 511e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// multiplication sequence, and if this sequence contains a multiply by Factor, 512e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// remove Factor from the tree and return the new tree. 513e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris LattnerValue *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { 514e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner BinaryOperator *BO = isReassociableOp(V, Instruction::Mul); 515e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (!BO) return 0; 516e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 5179f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVector<ValueEntry, 8> Factors; 518e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner LinearizeExprTree(BO, Factors); 519e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 520e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner bool FoundFactor = false; 521e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner for (unsigned i = 0, e = Factors.size(); i != e; ++i) 522e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Factors[i].Op == Factor) { 523e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner FoundFactor = true; 524e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Factors.erase(Factors.begin()+i); 525e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner break; 526e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 527e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if (!FoundFactor) { 528e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Make sure to restore the operands to the expression tree. 529e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(BO, Factors); 530e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner return 0; 531e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner } 532e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 533e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Factors.size() == 1) return Factors[0].Op; 534e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 535e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(BO, Factors); 536e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return BO; 537e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 538e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 539e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively 540e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// add its operands as factors, otherwise add V to the list of factors. 541e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattnerstatic void FindSingleUseMultiplyFactors(Value *V, 5428d93b259f6d6ece634df86d5df453efc0c918546Chris Lattner SmallVectorImpl<Value*> &Factors) { 543e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner BinaryOperator *BO; 544e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if ((!V->hasOneUse() && !V->use_empty()) || 545e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner !(BO = dyn_cast<BinaryOperator>(V)) || 546e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner BO->getOpcode() != Instruction::Mul) { 547e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner Factors.push_back(V); 548e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner return; 549e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner } 550e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 551e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Otherwise, add the LHS and RHS to the list of factors. 552e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner FindSingleUseMultiplyFactors(BO->getOperand(1), Factors); 553e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner FindSingleUseMultiplyFactors(BO->getOperand(0), Factors); 554e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner} 555e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 556f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor' 557f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// instruction. This optimizes based on identities. If it can be reduced to 558f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// a single Value, it is returned, otherwise the Ops list is mutated as 559f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// necessary. 5609f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattnerstatic Value *OptimizeAndOrXor(unsigned Opcode, 5619f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops) { 562f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 563f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 564f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 565f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // First, check for X and ~X in the operand list. 566f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner assert(i < Ops.size()); 567f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 568f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 569f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner unsigned FoundX = FindInOperandList(Ops, i, X); 570f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (FoundX != i) { 5719fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (Opcode == Instruction::And) // ...&X&~X = 0 572f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Constant::getNullValue(X->getType()); 573f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 5749fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (Opcode == Instruction::Or) // ...|X|~X = -1 575f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Constant::getAllOnesValue(X->getType()); 576f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 577f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 578f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 579f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Next, check for duplicate pairs of values, which we assume are next to 580f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // each other, due to our sorting criteria. 581f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner assert(i < Ops.size()); 582f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 583f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (Opcode == Instruction::And || Opcode == Instruction::Or) { 584f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Drop duplicate values. 585f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Ops.erase(Ops.begin()+i); 586f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner --i; --e; 587f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner ++NumAnnihil; 588f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } else { 589f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner assert(Opcode == Instruction::Xor); 5909fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (e == 2) 591f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Constant::getNullValue(Ops[0].Op->getType()); 5929fdaefad580194353f34b6d72669591f8f9d811aChris Lattner 593f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // ... X^X -> ... 594f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 595f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner i -= 1; e -= 2; 596f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner ++NumAnnihil; 597f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 598f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 599f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 600f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return 0; 601f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner} 602e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 603f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// OptimizeAdd - Optimize a series of operands to an 'add' instruction. This 604f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// optimizes based on identities. If it can be reduced to a single Value, it 605f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// is returned, otherwise the Ops list is mutated as necessary. 6069f7b7089be854c323f8d9a4627d80e47adf496e6Chris LattnerValue *Reassociate::OptimizeAdd(Instruction *I, 6079f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops) { 60869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner SmallPtrSet<Value*, 8> OperandsSeen; 60969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 61069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris LattnerRestart: 61169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner OperandsSeen.clear(); 61269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 613f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Scan the operand lists looking for X and -X pairs. If we find any, we 61469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // can simplify the expression. X+-X == 0. While we're at it, scan for any 61569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // duplicates. We want to canonicalize Y+Y+Y+Z -> 3*Y+Z. 616f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 61769e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *TheOp = Ops[i].Op; 61869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Check to see if we've seen this operand before. If so, we factor all 61969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // instances of the operand together. 62069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner if (!OperandsSeen.insert(TheOp)) { 62169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Rescan the list, removing all instances of this operand from the expr. 62269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner unsigned NumFound = 0; 62369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner for (unsigned j = 0, je = Ops.size(); j != je; ++j) { 62469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner if (Ops[j].Op != TheOp) continue; 62569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner ++NumFound; 62669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Ops.erase(Ops.begin()+j); 62769e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner --j; --je; 62869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner } 62969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 630f8a447de162a2896a8a044931fb63de713dbc6b9Chris Lattner DEBUG(errs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n'); 63169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner ++NumFactor; 63269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 63369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 63469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Insert a new multiply. 63569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *Mul = ConstantInt::get(cast<IntegerType>(I->getType()), NumFound); 63669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Mul = BinaryOperator::CreateMul(TheOp, Mul, "factor", I); 63769e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 63869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Now that we have inserted a multiply, optimize it. This allows us to 63969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // handle cases that require multiple factoring steps, such as this: 64069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6 64169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Mul = ReassociateExpression(cast<BinaryOperator>(Mul)); 64269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 64369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // If every add operand was a duplicate, return the multiply. 64469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner if (Ops.empty()) 64569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner return Mul; 64669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 64769e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Otherwise, we had some input that didn't have the dupe, such as 64869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // "A + A + B" -> "A*2 + B". Add the new multiply to the list of 64969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // things being added by this operation. 65069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul)); 65169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner goto Restart; 65269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner } 65369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 654f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Check for X and -X in the operand list. 65569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner if (!BinaryOperator::isNeg(TheOp)) 656f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner continue; 657f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 65869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *X = BinaryOperator::getNegArgument(TheOp); 659f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner unsigned FoundX = FindInOperandList(Ops, i, X); 660f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (FoundX == i) 661f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner continue; 662f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 663f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Remove X and -X from the operand list. 6649fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (Ops.size() == 2) 665f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Constant::getNullValue(X->getType()); 666f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 667f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Ops.erase(Ops.begin()+i); 668f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (i < FoundX) 669f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner --FoundX; 670f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner else 671f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner --i; // Need to back up an extra one. 672f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Ops.erase(Ops.begin()+FoundX); 673f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner ++NumAnnihil; 674f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner --i; // Revisit element. 675f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner e -= 2; // Removed two elements. 676f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 67794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 67894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Scan the operand list, checking to see if there are any common factors 67994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // between operands. Consider something like A*A+A*B*C+D. We would like to 68094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies. 68194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // To efficiently find this, we count the number of times a factor occurs 68294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // for any ADD operands that are MULs. 68394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner DenseMap<Value*, unsigned> FactorOccurrences; 68494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 68594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4) 68694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // where they are actually the same multiply. 68794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner unsigned MaxOcc = 0; 68894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Value *MaxOccVal = 0; 68994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 69094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op); 69194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty()) 69294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner continue; 69394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 69494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Compute all of the factors of this added value. 69594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner SmallVector<Value*, 8> Factors; 69694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner FindSingleUseMultiplyFactors(BOp, Factors); 69794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner assert(Factors.size() > 1 && "Bad linearize!"); 69894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 69994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Add one to FactorOccurrences for each unique factor in this op. 70094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Factors.size() == 2) { 70194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner unsigned Occ = ++FactorOccurrences[Factors[0]]; 70294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[0]; } 70394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Factors[0] != Factors[1]) { // Don't double count A*A. 70494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Occ = ++FactorOccurrences[Factors[1]]; 70594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[1]; } 70694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 70794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } else { 70894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner SmallPtrSet<Value*, 4> Duplicates; 70994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 71094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (!Duplicates.insert(Factors[i])) continue; 71194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 71294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner unsigned Occ = ++FactorOccurrences[Factors[i]]; 71394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[i]; } 71494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 71594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 71694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 71794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 71894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // If any factor occurred more than one time, we can pull it out. 71994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (MaxOcc > 1) { 72069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner DEBUG(errs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n'); 72194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner ++NumFactor; 72294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 72394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Create a new instruction that uses the MaxOccVal twice. If we don't do 72494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // this, we could otherwise run into situations where removing a factor 72594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // from an expression will drop a use of maxocc, and this can cause 72694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // RemoveFactorFromExpression on successive values to behave differently. 72794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal); 72894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner SmallVector<Value*, 4> NewMulOps; 72994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 73094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { 73194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner NewMulOps.push_back(V); 73294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Ops.erase(Ops.begin()+i); 73394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner --i; --e; 73494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 73594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 73694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 73794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // No need for extra uses anymore. 73894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner delete DummyInst; 73994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 74094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner unsigned NumAddedValues = NewMulOps.size(); 74194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Value *V = EmitAddTreeOfValues(I, NewMulOps); 74294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 74369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Now that we have inserted the add tree, optimize it. This allows us to 74469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // handle cases that require multiple factoring steps, such as this: 74594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C)) 7469cd1bc4f8b3e98892a2b9856eccd2a2ec9afdf7fChris Lattner assert(NumAddedValues > 1 && "Each occurrence should contribute a value"); 74769e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner V = ReassociateExpression(cast<BinaryOperator>(V)); 74869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 74969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Create the multiply. 75069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I); 75169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 75269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // FIXME: Should rerun 'ReassociateExpression' on the mul too?? 75394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 75494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // If every add operand included the factor (e.g. "A*B + A*C"), then the 75594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // entire result expression is just the multiply "A*(B+C)". 75694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Ops.empty()) 75794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner return V2; 75894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 7599cd1bc4f8b3e98892a2b9856eccd2a2ec9afdf7fChris Lattner // Otherwise, we had some input that didn't have the factor, such as 76094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // "A*B + A*C + D" -> "A*(B+C) + D". Add the new multiply to the list of 7619cd1bc4f8b3e98892a2b9856eccd2a2ec9afdf7fChris Lattner // things being added by this operation. 76294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); 76394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 76494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 765f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return 0; 766f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner} 767e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 768e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris LattnerValue *Reassociate::OptimizeExpression(BinaryOperator *I, 7699f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops) { 770469001000620df176decd093a300db84a06cc78bChris Lattner // Now that we have the linearized expression tree, try to optimize it. 771469001000620df176decd093a300db84a06cc78bChris Lattner // Start by folding any constants that we found. 772109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner bool IterateOptimization = false; 773e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops[0].Op; 774469001000620df176decd093a300db84a06cc78bChris Lattner 775e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner unsigned Opcode = I->getOpcode(); 776e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 777469001000620df176decd093a300db84a06cc78bChris Lattner if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 778469001000620df176decd093a300db84a06cc78bChris Lattner if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 779469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 780baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 781e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return OptimizeExpression(I, Ops); 782469001000620df176decd093a300db84a06cc78bChris Lattner } 783469001000620df176decd093a300db84a06cc78bChris Lattner 784469001000620df176decd093a300db84a06cc78bChris Lattner // Check for destructive annihilation due to a constant being used. 7856b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op)) 786469001000620df176decd093a300db84a06cc78bChris Lattner switch (Opcode) { 787469001000620df176decd093a300db84a06cc78bChris Lattner default: break; 788469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::And: 7899fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (CstVal->isZero()) // ... & 0 -> 0 790e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 7919fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (CstVal->isAllOnesValue()) // ... & -1 -> ... 7928d93b259f6d6ece634df86d5df453efc0c918546Chris Lattner Ops.pop_back(); 793469001000620df176decd093a300db84a06cc78bChris Lattner break; 794469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Mul: 795cae5754619433aed7be74abbf1c0551a82d369cbReid Spencer if (CstVal->isZero()) { // ... * 0 -> 0 796109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 797e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 798469001000620df176decd093a300db84a06cc78bChris Lattner } 7998d93b259f6d6ece634df86d5df453efc0c918546Chris Lattner 8008d93b259f6d6ece634df86d5df453efc0c918546Chris Lattner if (cast<ConstantInt>(CstVal)->isOne()) 8018d93b259f6d6ece634df86d5df453efc0c918546Chris Lattner Ops.pop_back(); // ... * 1 -> ... 802469001000620df176decd093a300db84a06cc78bChris Lattner break; 803469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Or: 8049fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (CstVal->isAllOnesValue()) // ... | -1 -> -1 805e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 806469001000620df176decd093a300db84a06cc78bChris Lattner // FALLTHROUGH! 807469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Add: 808469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Xor: 809cae5754619433aed7be74abbf1c0551a82d369cbReid Spencer if (CstVal->isZero()) // ... [|^+] 0 -> ... 810469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 811469001000620df176decd093a300db84a06cc78bChris Lattner break; 812469001000620df176decd093a300db84a06cc78bChris Lattner } 813e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops[0].Op; 814469001000620df176decd093a300db84a06cc78bChris Lattner 815ec531233a16605756a84d175178e1ee0fac4791cChris Lattner // Handle destructive annihilation due to identities between elements in the 816469001000620df176decd093a300db84a06cc78bChris Lattner // argument list here. 817109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner switch (Opcode) { 818109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner default: break; 819109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner case Instruction::And: 820109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner case Instruction::Or: 821f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner case Instruction::Xor: { 822f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner unsigned NumOps = Ops.size(); 823f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (Value *Result = OptimizeAndOrXor(Opcode, Ops)) 824f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Result; 825f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner IterateOptimization |= Ops.size() != NumOps; 826109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner break; 827f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 828109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 829f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner case Instruction::Add: { 830f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner unsigned NumOps = Ops.size(); 83194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Value *Result = OptimizeAdd(I, Ops)) 832f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Result; 833f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner IterateOptimization |= Ops.size() != NumOps; 834f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 835e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 836109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner break; 837109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner //case Instruction::Mul: 838109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 839109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 84000b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen if (IterateOptimization) 841e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return OptimizeExpression(I, Ops); 842e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return 0; 843469001000620df176decd093a300db84a06cc78bChris Lattner} 844469001000620df176decd093a300db84a06cc78bChris Lattner 84508b43921e18f314c4fd38049291d323830934c36Chris Lattner 84608b43921e18f314c4fd38049291d323830934c36Chris Lattner/// ReassociateBB - Inspect all of the instructions in this basic block, 84708b43921e18f314c4fd38049291d323830934c36Chris Lattner/// reassociating them as we go. 848c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::ReassociateBB(BasicBlock *BB) { 849e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner for (BasicBlock::iterator BBI = BB->begin(); BBI != BB->end(); ) { 850e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Instruction *BI = BBI++; 851641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner if (BI->getOpcode() == Instruction::Shl && 852641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner isa<ConstantInt>(BI->getOperand(1))) 853e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky if (Instruction *NI = ConvertShiftToMul(BI, ValueRankMap)) { 854641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner MadeChange = true; 855641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner BI = NI; 856641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner } 857641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner 8586f156856ca23394122f39d92fe74eec40a1f7c27Chris Lattner // Reject cases where it is pointless to do this. 859e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPoint() || 8609d6565a5b1fbc4286d6ee638d8f47a3171a9ed7eReid Spencer isa<VectorType>(BI->getType())) 8616f156856ca23394122f39d92fe74eec40a1f7c27Chris Lattner continue; // Floating point ops are not associative. 8626f156856ca23394122f39d92fe74eec40a1f7c27Chris Lattner 86308b43921e18f314c4fd38049291d323830934c36Chris Lattner // If this is a subtract instruction which is not already in negate form, 86408b43921e18f314c4fd38049291d323830934c36Chris Lattner // see if we can convert it to X+-Y. 865f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (BI->getOpcode() == Instruction::Sub) { 866e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky if (ShouldBreakUpSubtract(BI)) { 867e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky BI = BreakUpSubtract(BI, ValueRankMap); 868d5b8d92b9f4dfb216e4f2a52b4e801d7559574baChris Lattner MadeChange = true; 869fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson } else if (BinaryOperator::isNeg(BI)) { 870f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // Otherwise, this is a negation. See if the operand is a multiply tree 871f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // and if this is not an inner node of a multiply tree. 872f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (isReassociableOp(BI->getOperand(1), Instruction::Mul) && 873f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner (!BI->hasOneUse() || 874f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner !isReassociableOp(BI->use_back(), Instruction::Mul))) { 875e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky BI = LowerNegateToMultiply(BI, ValueRankMap); 876f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner MadeChange = true; 877f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 87808b43921e18f314c4fd38049291d323830934c36Chris Lattner } 879f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 880e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 881c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If this instruction is a commutative binary operator, process it. 882c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!BI->isAssociative()) continue; 883c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *I = cast<BinaryOperator>(BI); 88400b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 885c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If this is an interior node of a reassociable tree, ignore it until we 886c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // get to the root of the tree, to avoid N^2 analysis. 887c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode())) 888c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner continue; 889c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 8907b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner // If this is an add tree that is used by a sub instruction, ignore it 8917b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner // until we process the subtract. 8927b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner if (I->hasOneUse() && I->getOpcode() == Instruction::Add && 8937b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub) 8947b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner continue; 8957b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner 896895b392269cad07c34d59110d68dc86708c53adbChris Lattner ReassociateExpression(I); 897895b392269cad07c34d59110d68dc86708c53adbChris Lattner } 898895b392269cad07c34d59110d68dc86708c53adbChris Lattner} 899c9fd097a01383323f166c14c17d3984620cad766Chris Lattner 90069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris LattnerValue *Reassociate::ReassociateExpression(BinaryOperator *I) { 901895b392269cad07c34d59110d68dc86708c53adbChris Lattner 90269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // First, walk the expression tree, linearizing the tree, collecting the 90369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // operand information. 9049f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVector<ValueEntry, 8> Ops; 905895b392269cad07c34d59110d68dc86708c53adbChris Lattner LinearizeExprTree(I, Ops); 906895b392269cad07c34d59110d68dc86708c53adbChris Lattner 90794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner DEBUG(errs() << "RAIn:\t"; PrintOps(I, Ops); errs() << '\n'); 908895b392269cad07c34d59110d68dc86708c53adbChris Lattner 909895b392269cad07c34d59110d68dc86708c53adbChris Lattner // Now that we have linearized the tree to a list and have gathered all of 910895b392269cad07c34d59110d68dc86708c53adbChris Lattner // the operands and their ranks, sort the operands by their rank. Use a 911895b392269cad07c34d59110d68dc86708c53adbChris Lattner // stable_sort so that values with equal ranks will have their relative 912895b392269cad07c34d59110d68dc86708c53adbChris Lattner // positions maintained (and so the compiler is deterministic). Note that 913895b392269cad07c34d59110d68dc86708c53adbChris Lattner // this sorts so that the highest ranking values end up at the beginning of 914895b392269cad07c34d59110d68dc86708c53adbChris Lattner // the vector. 915895b392269cad07c34d59110d68dc86708c53adbChris Lattner std::stable_sort(Ops.begin(), Ops.end()); 916895b392269cad07c34d59110d68dc86708c53adbChris Lattner 917895b392269cad07c34d59110d68dc86708c53adbChris Lattner // OptimizeExpression - Now that we have the expression tree in a convenient 918895b392269cad07c34d59110d68dc86708c53adbChris Lattner // sorted form, optimize it globally if possible. 919895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (Value *V = OptimizeExpression(I, Ops)) { 920895b392269cad07c34d59110d68dc86708c53adbChris Lattner // This expression tree simplified to something that isn't a tree, 921895b392269cad07c34d59110d68dc86708c53adbChris Lattner // eliminate it. 92294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner DEBUG(errs() << "Reassoc to scalar: " << *V << '\n'); 923895b392269cad07c34d59110d68dc86708c53adbChris Lattner I->replaceAllUsesWith(V); 924895b392269cad07c34d59110d68dc86708c53adbChris Lattner RemoveDeadBinaryOp(I); 9259fdaefad580194353f34b6d72669591f8f9d811aChris Lattner ++NumAnnihil; 92669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner return V; 927895b392269cad07c34d59110d68dc86708c53adbChris Lattner } 928895b392269cad07c34d59110d68dc86708c53adbChris Lattner 929895b392269cad07c34d59110d68dc86708c53adbChris Lattner // We want to sink immediates as deeply as possible except in the case where 930895b392269cad07c34d59110d68dc86708c53adbChris Lattner // this is a multiply tree used only by an add, and the immediate is a -1. 931895b392269cad07c34d59110d68dc86708c53adbChris Lattner // In this case we reassociate to put the negation on the outside so that we 932895b392269cad07c34d59110d68dc86708c53adbChris Lattner // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y 933895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (I->getOpcode() == Instruction::Mul && I->hasOneUse() && 934895b392269cad07c34d59110d68dc86708c53adbChris Lattner cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add && 935895b392269cad07c34d59110d68dc86708c53adbChris Lattner isa<ConstantInt>(Ops.back().Op) && 936895b392269cad07c34d59110d68dc86708c53adbChris Lattner cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) { 9379f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner ValueEntry Tmp = Ops.pop_back_val(); 9389f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner Ops.insert(Ops.begin(), Tmp); 939895b392269cad07c34d59110d68dc86708c53adbChris Lattner } 940895b392269cad07c34d59110d68dc86708c53adbChris Lattner 94194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner DEBUG(errs() << "RAOut:\t"; PrintOps(I, Ops); errs() << '\n'); 942895b392269cad07c34d59110d68dc86708c53adbChris Lattner 943895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (Ops.size() == 1) { 944895b392269cad07c34d59110d68dc86708c53adbChris Lattner // This expression tree simplified to something that isn't a tree, 945895b392269cad07c34d59110d68dc86708c53adbChris Lattner // eliminate it. 946895b392269cad07c34d59110d68dc86708c53adbChris Lattner I->replaceAllUsesWith(Ops[0].Op); 947895b392269cad07c34d59110d68dc86708c53adbChris Lattner RemoveDeadBinaryOp(I); 94869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner return Ops[0].Op; 9494fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 95069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 95169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Now that we ordered and optimized the expressions, splat them back into 95269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // the expression tree, removing any unneeded nodes. 95369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner RewriteExprTree(I, Ops); 95469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner return I; 9554fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 9564fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 9574fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 9587e70829632f82de15db187845666aaca6e04b792Chris Lattnerbool Reassociate::runOnFunction(Function &F) { 9594fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Recalculate the rank map for F 9604fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner BuildRankMap(F); 9614fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 962c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = false; 9637e70829632f82de15db187845666aaca6e04b792Chris Lattner for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 964c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ReassociateBB(FI); 9654fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 9664fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // We are done with the rank map... 9674fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner RankMap.clear(); 968fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner ValueRankMap.clear(); 969c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return MadeChange; 9704fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 971d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 972