Reassociate.cpp revision f1d0f7781e766df878bec4e7977fa3204374f394
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 119046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner// to promote better constant propagation, GCSE, LICM, PRE, etc. 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" 25fa0e6facc793d0a67e89f873e18cd35a9d7c02e0Dan Gohman#include "llvm/Transforms/Utils/Local.h" 260975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner#include "llvm/Constants.h" 27ae74f555522298bef3be8a173163bf778d59adf9Chris Lattner#include "llvm/DerivedTypes.h" 284fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Function.h" 29d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 3003afd02ca2486aebb3b29edd2f77920d4e5020fdDale Johannesen#include "llvm/IntrinsicInst.h" 314fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Pass.h" 32c9fd097a01383323f166c14c17d3984620cad766Chris Lattner#include "llvm/Assembly/Writer.h" 334fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Support/CFG.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 35d3c7b7359d4992b9ab9f8e12ccd0a9b7d2446566Chris Lattner#include "llvm/Support/ValueHandle.h" 36bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/PostOrderIterator.h" 38551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 39ec531233a16605756a84d175178e1ee0fac4791cChris Lattner#include "llvm/ADT/DenseMap.h" 40c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner#include <algorithm> 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(); 64a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene dbgs() << Instruction::getOpcodeName(I->getOpcode()) << " " 651befe643b2a030f5e2433ce0034a27fb65b5f26bChris Lattner << *Ops[0].Op->getType() << '\t'; 667de3b5db26bb3c8dcca5348fb7c0be4f9bd1bcb7Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 67a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene dbgs() << "[ "; 68a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene WriteAsOperand(dbgs(), Ops[i].Op, false, M); 69a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene dbgs() << ", #" << Ops[i].Rank << "] "; 707de3b5db26bb3c8dcca5348fb7c0be4f9bd1bcb7Chris Lattner } 71e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 7259500c8f9a76b3386329b6f837255c16f4e8b61bDevang Patel#endif 73e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 74844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 753e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class Reassociate : public FunctionPass { 76f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner DenseMap<BasicBlock*, unsigned> RankMap; 77f1d0f7781e766df878bec4e7977fa3204374f394Craig Topper DenseMap<AssertingVH<Value>, unsigned> ValueRankMap; 78dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman SmallVector<WeakVH, 8> RedoInsts; 79fa0e6facc793d0a67e89f873e18cd35a9d7c02e0Dan Gohman SmallVector<WeakVH, 8> DeadInsts; 80c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner bool MadeChange; 814fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner public: 82ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 83081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson Reassociate() : FunctionPass(ID) { 84081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeReassociatePass(*PassRegistry::getPassRegistry()); 85081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 86794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 877e70829632f82de15db187845666aaca6e04b792Chris Lattner bool runOnFunction(Function &F); 884fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 894fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 90cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 914fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 924fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner private: 937e70829632f82de15db187845666aaca6e04b792Chris Lattner void BuildRankMap(Function &F); 944fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned getRank(Value *V); 9569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *ReassociateExpression(BinaryOperator *I); 969f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops, 97e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner unsigned Idx = 0); 989f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner Value *OptimizeExpression(BinaryOperator *I, 999f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops); 1009f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops); 1019f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner void LinearizeExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 102c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner void LinearizeExpr(BinaryOperator *I); 103e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *RemoveFactorFromExpression(Value *V, Value *Factor); 104dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman void ReassociateInst(BasicBlock::iterator &BBI); 105e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 106e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner void RemoveDeadBinaryOp(Value *V); 1074fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner }; 1084fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1094fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 110844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar Reassociate::ID = 0; 111d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(Reassociate, "reassociate", 112ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Reassociate expressions", false, false) 113844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 114d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the Reassociate pass 115d7456026629fc1760a45e6e955e9834246493147Chris LattnerFunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 1164fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 117e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattnervoid Reassociate::RemoveDeadBinaryOp(Value *V) { 118e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Instruction *Op = dyn_cast<Instruction>(V); 119fa0e6facc793d0a67e89f873e18cd35a9d7c02e0Dan Gohman if (!Op || !isa<BinaryOperator>(Op)) 120e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer return; 121e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 122e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1); 12369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 12469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner ValueRankMap.erase(Op); 125fa0e6facc793d0a67e89f873e18cd35a9d7c02e0Dan Gohman DeadInsts.push_back(Op); 126e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(LHS); 127e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(RHS); 128e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 129e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 1309c723199384b16899831937e2800d52f4f953569Chris Lattner 1319c723199384b16899831937e2800d52f4f953569Chris Lattnerstatic bool isUnmovableInstruction(Instruction *I) { 1329c723199384b16899831937e2800d52f4f953569Chris Lattner if (I->getOpcode() == Instruction::PHI || 1339c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Alloca || 1349c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Load || 1359c723199384b16899831937e2800d52f4f953569Chris Lattner I->getOpcode() == Instruction::Invoke || 13603afd02ca2486aebb3b29edd2f77920d4e5020fdDale Johannesen (I->getOpcode() == Instruction::Call && 13703afd02ca2486aebb3b29edd2f77920d4e5020fdDale Johannesen !isa<DbgInfoIntrinsic>(I)) || 1381628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::UDiv || 1391628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::SDiv || 1401628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer I->getOpcode() == Instruction::FDiv || 1410a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::URem || 1420a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::SRem || 1430a783f783ca05c961234385f5b269d4cf03dbbdbReid Spencer I->getOpcode() == Instruction::FRem) 1449c723199384b16899831937e2800d52f4f953569Chris Lattner return true; 1459c723199384b16899831937e2800d52f4f953569Chris Lattner return false; 1469c723199384b16899831937e2800d52f4f953569Chris Lattner} 1479c723199384b16899831937e2800d52f4f953569Chris Lattner 1487e70829632f82de15db187845666aaca6e04b792Chris Lattnervoid Reassociate::BuildRankMap(Function &F) { 1496007cb6c4d923e2dee4a1133fb6d1bb00a37062dChris Lattner unsigned i = 2; 150fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 151fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner // Assign distinct ranks to function arguments 152e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 153d3c7b7359d4992b9ab9f8e12ccd0a9b7d2446566Chris Lattner ValueRankMap[&*I] = ++i; 154fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner 1557e70829632f82de15db187845666aaca6e04b792Chris Lattner ReversePostOrderTraversal<Function*> RPOT(&F); 1564fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 1579c723199384b16899831937e2800d52f4f953569Chris Lattner E = RPOT.end(); I != E; ++I) { 1589c723199384b16899831937e2800d52f4f953569Chris Lattner BasicBlock *BB = *I; 1599c723199384b16899831937e2800d52f4f953569Chris Lattner unsigned BBRank = RankMap[BB] = ++i << 16; 1609c723199384b16899831937e2800d52f4f953569Chris Lattner 1619c723199384b16899831937e2800d52f4f953569Chris Lattner // Walk the basic block, adding precomputed ranks for any instructions that 1629c723199384b16899831937e2800d52f4f953569Chris Lattner // we cannot move. This ensures that the ranks for these instructions are 1639c723199384b16899831937e2800d52f4f953569Chris Lattner // all different in the block. 1649c723199384b16899831937e2800d52f4f953569Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 1659c723199384b16899831937e2800d52f4f953569Chris Lattner if (isUnmovableInstruction(I)) 166d3c7b7359d4992b9ab9f8e12ccd0a9b7d2446566Chris Lattner ValueRankMap[&*I] = ++BBRank; 1679c723199384b16899831937e2800d52f4f953569Chris Lattner } 1684fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1694fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1704fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnerunsigned Reassociate::getRank(Value *V) { 17108b43921e18f314c4fd38049291d323830934c36Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 172f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner if (I == 0) { 173f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument. 174f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner return 0; // Otherwise it's a global or constant, rank 0. 175f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner } 1764fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 177f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner if (unsigned Rank = ValueRankMap[I]) 178f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner return Rank; // Rank already known? 17900b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 18008b43921e18f314c4fd38049291d323830934c36Chris Lattner // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 18108b43921e18f314c4fd38049291d323830934c36Chris Lattner // we can reassociate expressions for code motion! Since we do not recurse 18208b43921e18f314c4fd38049291d323830934c36Chris Lattner // for PHI nodes, we cannot have infinite recursion here, because there 18308b43921e18f314c4fd38049291d323830934c36Chris Lattner // cannot be loops in the value graph that do not go through PHI nodes. 18408b43921e18f314c4fd38049291d323830934c36Chris Lattner unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 18508b43921e18f314c4fd38049291d323830934c36Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); 18608b43921e18f314c4fd38049291d323830934c36Chris Lattner i != e && Rank != MaxRank; ++i) 18708b43921e18f314c4fd38049291d323830934c36Chris Lattner Rank = std::max(Rank, getRank(I->getOperand(i))); 18800b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 189cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner // If this is a not or neg instruction, do not count it for rank. This 190cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner // assures us that X and ~X will have the same rank. 191b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (!I->getType()->isIntegerTy() || 192fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 193cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner ++Rank; 194cc8a2b98f28c10d93f45489b8c6f0c8b8205bb3bChris Lattner 195a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene //DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = " 196bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner // << Rank << "\n"); 19700b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 198f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner return ValueRankMap[I] = Rank; 1994fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 2004fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 201c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// isReassociableOp - Return true if V is an instruction of the specified 202c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// opcode and if it only has one use. 203c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnerstatic BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 204e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if ((V->hasOneUse() || V->use_empty()) && isa<Instruction>(V) && 205c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner cast<Instruction>(V)->getOpcode() == Opcode) 206c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return cast<BinaryOperator>(V); 207c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return 0; 208c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 2094fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 210f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner/// LowerNegateToMultiply - Replace 0-X with X*-1. 211f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner/// 212f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesenstatic Instruction *LowerNegateToMultiply(Instruction *Neg, 213f1d0f7781e766df878bec4e7977fa3204374f394Craig Topper DenseMap<AssertingVH<Value>, unsigned> &ValueRankMap) { 214a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Constant *Cst = Constant::getAllOnesValue(Neg->getType()); 215f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 2167cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction *Res = BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg); 217f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesen ValueRankMap.erase(Neg); 2186934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner Res->takeName(Neg); 219f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner Neg->replaceAllUsesWith(Res); 2205367b23f76e75ebb680956575346fa8c3d56780fDevang Patel Res->setDebugLoc(Neg->getDebugLoc()); 221f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner Neg->eraseFromParent(); 222f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner return Res; 223f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner} 224f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 225c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. 226c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// Note that if D is also part of the expression tree that we recurse to 227c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// linearize it as well. Besides that case, this does not recurse into A,B, or 228c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// C. 229c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::LinearizeExpr(BinaryOperator *I) { 230c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 231c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1)); 23200b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen assert(isReassociableOp(LHS, I->getOpcode()) && 233c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner isReassociableOp(RHS, I->getOpcode()) && 234c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner "Not an expression that needs linearization?"); 235c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 236a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "Linear" << *LHS << '\n' << *RHS << '\n' << *I << '\n'); 237c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 238c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move the RHS instruction to live immediately before I, avoiding breaking 239c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // dominator properties. 2404bc5f8071a28b6fc4f4c2207dd03a5f747d0d84bChris Lattner RHS->moveBefore(I); 241c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 242c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move operands around to do the linearization. 243c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, RHS->getOperand(0)); 244c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHS->setOperand(0, LHS); 245c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(0, RHS); 24600b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 24746985a14409486293b689ca07dd07d7482734795Dan Gohman // Conservatively clear all the optional flags, which may not hold 24846985a14409486293b689ca07dd07d7482734795Dan Gohman // after the reassociation. 24946985a14409486293b689ca07dd07d7482734795Dan Gohman I->clearSubclassOptionalData(); 25046985a14409486293b689ca07dd07d7482734795Dan Gohman LHS->clearSubclassOptionalData(); 25146985a14409486293b689ca07dd07d7482734795Dan Gohman RHS->clearSubclassOptionalData(); 25246985a14409486293b689ca07dd07d7482734795Dan Gohman 253c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumLinear; 254c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 255a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "Linearized: " << *I << '\n'); 256fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 257c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // If D is part of this expression tree, tail recurse. 258c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (isReassociableOp(I->getOperand(1), I->getOpcode())) 259c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExpr(I); 260c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 2614fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 262e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 263c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// LinearizeExprTree - Given an associative binary expression tree, traverse 264c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// all of the uses putting it into canonical form. This forces a left-linear 265f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman/// form of the expression (((a+b)+c)+d), and collects information about the 266c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// rank of the non-tree operands. 267c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner/// 268e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// NOTE: These intentionally destroys the expression tree operands (turning 269e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// them into undef values) to reduce #uses of the values. This means that the 270e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// caller MUST use something like RewriteExprTree to put the values back in. 271e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// 272c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattnervoid Reassociate::LinearizeExprTree(BinaryOperator *I, 2739f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops) { 274c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); 275c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner unsigned Opcode = I->getOpcode(); 276c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 277c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // First step, linearize the expression if it is in ((A+B)+(C+D)) form. 278c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); 279c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); 280c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 281f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // If this is a multiply expression tree and it contains internal negations, 282f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner // transform them into multiplies by -1 so they can be reassociated. 283f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner if (I->getOpcode() == Instruction::Mul) { 284fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson if (!LHSBO && LHS->hasOneUse() && BinaryOperator::isNeg(LHS)) { 285e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky LHS = LowerNegateToMultiply(cast<Instruction>(LHS), ValueRankMap); 286f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner LHSBO = isReassociableOp(LHS, Opcode); 287f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 288fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson if (!RHSBO && RHS->hasOneUse() && BinaryOperator::isNeg(RHS)) { 289e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky RHS = LowerNegateToMultiply(cast<Instruction>(RHS), ValueRankMap); 290f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner RHSBO = isReassociableOp(RHS, Opcode); 291f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 292f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 293f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner 294c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!LHSBO) { 295c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (!RHSBO) { 296c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Neither the LHS or RHS as part of the tree, thus this is a leaf. As 297c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // such, just remember these operands and their rank. 298c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(LHS), LHS)); 299c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(RHS), RHS)); 300e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 301e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Clear the leaves out. 3029e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I->setOperand(0, UndefValue::get(I->getType())); 3039e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I->setOperand(1, UndefValue::get(I->getType())); 304c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return; 305c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 306f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 307f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Turn X+(Y+Z) -> (Y+Z)+X 308f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner std::swap(LHSBO, RHSBO); 309f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner std::swap(LHS, RHS); 310f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner bool Success = !I->swapOperands(); 311f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner assert(Success && "swapOperands failed"); 3121f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)Success; 313f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner MadeChange = true; 314c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } else if (RHSBO) { 315f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the RHS is not 316c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // part of the expression tree. 317c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExpr(I); 318c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0)); 319c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHS = I->getOperand(1); 320c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner RHSBO = 0; 3214fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 322fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 323c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Okay, now we know that the LHS is a nested expression and that the RHS is 324c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // not. Perform reassociation. 325c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); 3264fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 327c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Move LHS right before I to make sure that the tree expression dominates all 328c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // values. 3294bc5f8071a28b6fc4f4c2207dd03a5f747d0d84bChris Lattner LHSBO->moveBefore(I); 330c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 331c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Linearize the expression tree on the LHS. 332c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner LinearizeExprTree(LHSBO, Ops); 333c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 334c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner // Remember the RHS operand and its rank. 335c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner Ops.push_back(ValueEntry(getRank(RHS), RHS)); 336e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 337e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Clear the RHS leaf out. 3389e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I->setOperand(1, UndefValue::get(I->getType())); 339c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner} 340c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 341c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// RewriteExprTree - Now that the operands for this expression tree are 342c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// linearized and optimized, emit them in-order. This function is written to be 343c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner// tail recursive. 344e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattnervoid Reassociate::RewriteExprTree(BinaryOperator *I, 3459f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops, 346e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner unsigned i) { 347c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (i+2 == Ops.size()) { 348c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->getOperand(0) != Ops[i].Op || 349c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->getOperand(1) != Ops[i+1].Op) { 350e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *OldLHS = I->getOperand(0); 351a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "RA: " << *I << '\n'); 352c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(0, Ops[i].Op); 353c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, Ops[i+1].Op); 35446985a14409486293b689ca07dd07d7482734795Dan Gohman 355de1d8a544c1398cc34d4c865c5afa8b91f96316cChris Lattner // Clear all the optional flags, which may not hold after the 356de1d8a544c1398cc34d4c865c5afa8b91f96316cChris Lattner // reassociation if the expression involved more than just this operation. 357de1d8a544c1398cc34d4c865c5afa8b91f96316cChris Lattner if (Ops.size() != 2) 358de1d8a544c1398cc34d4c865c5afa8b91f96316cChris Lattner I->clearSubclassOptionalData(); 35946985a14409486293b689ca07dd07d7482734795Dan Gohman 360a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "TO: " << *I << '\n'); 361c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 362c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumChanged; 363e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 364e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // If we reassociated a tree to fewer operands (e.g. (1+a+2) -> (a+3) 365e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // delete the extra, now dead, nodes. 366e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner RemoveDeadBinaryOp(OldLHS); 367c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 368c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return; 369c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 370c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner assert(i+2 < Ops.size() && "Ops index out of range!"); 371c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 372c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner if (I->getOperand(1) != Ops[i].Op) { 373a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "RA: " << *I << '\n'); 374c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner I->setOperand(1, Ops[i].Op); 37546985a14409486293b689ca07dd07d7482734795Dan Gohman 37646985a14409486293b689ca07dd07d7482734795Dan Gohman // Conservatively clear all the optional flags, which may not hold 37746985a14409486293b689ca07dd07d7482734795Dan Gohman // after the reassociation. 37846985a14409486293b689ca07dd07d7482734795Dan Gohman I->clearSubclassOptionalData(); 37946985a14409486293b689ca07dd07d7482734795Dan Gohman 380a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "TO: " << *I << '\n'); 381c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = true; 382c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner ++NumChanged; 383c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner } 384e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 385e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 386e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner assert(LHS->getOpcode() == I->getOpcode() && 387e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner "Improper expression tree!"); 388e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 389e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // Compactify the tree instructions together with each other to guarantee 390e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner // that the expression tree is dominated by all of Ops. 391e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner LHS->moveBefore(I); 392e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(LHS, Ops, i+1); 3934fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 3944fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 3954fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 396c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 397a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// NegateValue - Insert instructions before the instruction pointed to by BI, 398a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that computes the negative version of the value specified. The negative 399a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// version of the value is returned, and BI is left pointing at the instruction 400a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that should be processed next by the reassociation pass. 401a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// 402e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewyckystatic Value *NegateValue(Value *V, Instruction *BI) { 40335239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner if (Constant *C = dyn_cast<Constant>(V)) 40435239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner return ConstantExpr::getNeg(C); 40535239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner 406a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // We are trying to expose opportunity for reassociation. One of the things 407a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // that we want to do to achieve this is to push a negation as deep into an 408a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // expression chain as possible, to expose the add instructions. In practice, 409a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // this means that we turn this: 410a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 411a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 412a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // the constants. We assume that instcombine will clean up the mess later if 4139046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner // we introduce tons of unnecessary negation instructions. 414a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 415a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 416fd05924946ebfcfb3409b21996cfd0836e4ddb31Chris Lattner if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 4172cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // Push the negates through the add. 418e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky I->setOperand(0, NegateValue(I->getOperand(0), BI)); 419e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky I->setOperand(1, NegateValue(I->getOperand(1), BI)); 4202cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner 4212cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // We must move the add instruction here, because the neg instructions do 4222cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // not dominate the old add instruction in general. By moving it, we are 4232cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // assured that the neg instructions we just inserted dominate the 4242cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner // instruction we are about to insert after them. 425a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 4262cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner I->moveBefore(BI); 4272cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner I->setName(I->getName()+".neg"); 4282cd85da3ed8e703729fb5adfe8cc2f9b1dd2f6a8Chris Lattner return I; 429a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner } 43035239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner 43135239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner // Okay, we need to materialize a negated version of V with an instruction. 43235239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner // Scan the use lists of V to see if we have one already. 43335239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){ 434110b75aa7572d3b59b308da7ec1d759e86788f97Gabor Greif User *U = *UI; 435110b75aa7572d3b59b308da7ec1d759e86788f97Gabor Greif if (!BinaryOperator::isNeg(U)) continue; 43635239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner 43735239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner // We found one! Now we have to make sure that the definition dominates 43835239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner // this use. We do this by moving it to the entry block (if it is a 43935239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner // non-instruction value) or right after the definition. These negates will 44035239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner // be zapped by reassociate later, so we don't need much finesse here. 441110b75aa7572d3b59b308da7ec1d759e86788f97Gabor Greif BinaryOperator *TheNeg = cast<BinaryOperator>(U); 4421c91fae649734abe6f8271862fe3ba917e191279Chris Lattner 4431c91fae649734abe6f8271862fe3ba917e191279Chris Lattner // Verify that the negate is in this function, V might be a constant expr. 4441c91fae649734abe6f8271862fe3ba917e191279Chris Lattner if (TheNeg->getParent()->getParent() != BI->getParent()->getParent()) 4451c91fae649734abe6f8271862fe3ba917e191279Chris Lattner continue; 44635239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner 44735239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner BasicBlock::iterator InsertPt; 44835239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner if (Instruction *InstInput = dyn_cast<Instruction>(V)) { 44935239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) { 45035239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner InsertPt = II->getNormalDest()->begin(); 45135239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner } else { 45235239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner InsertPt = InstInput; 45335239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner ++InsertPt; 45435239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner } 45535239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner while (isa<PHINode>(InsertPt)) ++InsertPt; 45635239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner } else { 45735239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin(); 45835239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner } 45935239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner TheNeg->moveBefore(InsertPt); 46035239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner return TheNeg; 46135239934517c6fcd52e3e965f40e03f74aa4d11dChris Lattner } 462a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 463a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Insert a 'neg' instruction that subtracts the value from zero to get the 464a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // negation. 4654ae5126d041768ab9665cf2f11c024becd76c41fDan Gohman return BinaryOperator::CreateNeg(V, V->getName() + ".neg", BI); 466a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner} 467a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 4689bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner/// ShouldBreakUpSubtract - Return true if we should break up this subtract of 4699bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner/// X-Y into (X + -Y). 470e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewyckystatic bool ShouldBreakUpSubtract(Instruction *Sub) { 4719bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner // If this is a negation, we can't split it up! 472fa82b6eba4e1584d7dba291c28fe908272e1e002Owen Anderson if (BinaryOperator::isNeg(Sub)) 4739bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return false; 4749bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner 4759bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner // Don't bother to break this up unless either the LHS is an associable add or 4760b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner // subtract or if this is only used by one. 4770b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner if (isReassociableOp(Sub->getOperand(0), Instruction::Add) || 4780b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner isReassociableOp(Sub->getOperand(0), Instruction::Sub)) 4799bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return true; 4800b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner if (isReassociableOp(Sub->getOperand(1), Instruction::Add) || 4815329bb22e9b6374d62919981c1ef8775b42945ebChris Lattner isReassociableOp(Sub->getOperand(1), Instruction::Sub)) 4829bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return true; 4830b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner if (Sub->hasOneUse() && 4840b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner (isReassociableOp(Sub->use_back(), Instruction::Add) || 4850b0803ae1508ff514dd7b471a2a3bcd1e83cb0efChris Lattner isReassociableOp(Sub->use_back(), Instruction::Sub))) 4869bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return true; 4879bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner 4889bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner return false; 4899bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner} 4909bc5ed78c860694ccb4ea63c96c2c9212a8b245bChris Lattner 49108b43921e18f314c4fd38049291d323830934c36Chris Lattner/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 49208b43921e18f314c4fd38049291d323830934c36Chris Lattner/// only used by an add, transform this into (X+(0-Y)) to promote better 49308b43921e18f314c4fd38049291d323830934c36Chris Lattner/// reassociation. 494e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewyckystatic Instruction *BreakUpSubtract(Instruction *Sub, 495f1d0f7781e766df878bec4e7977fa3204374f394Craig Topper DenseMap<AssertingVH<Value>, unsigned> &ValueRankMap) { 4969046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner // Convert a subtract into an add and a neg instruction. This allows sub 4979046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner // instructions to be commuted with other add instructions. 49808b43921e18f314c4fd38049291d323830934c36Chris Lattner // 4999046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner // Calculate the negative value of Operand 1 of the sub instruction, 5009046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner // and set it as the RHS of the add instruction we just made. 50108b43921e18f314c4fd38049291d323830934c36Chris Lattner // 502e79fddedcae1ee8fe7d8571db58447bc722f75dcNick Lewycky Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 50308b43921e18f314c4fd38049291d323830934c36Chris Lattner Instruction *New = 5047cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub); 5056934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner New->takeName(Sub); 50608b43921e18f314c4fd38049291d323830934c36Chris Lattner 50708b43921e18f314c4fd38049291d323830934c36Chris Lattner // Everyone now refers to the add instruction. 508f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesen ValueRankMap.erase(Sub); 50908b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->replaceAllUsesWith(New); 5105367b23f76e75ebb680956575346fa8c3d56780fDevang Patel New->setDebugLoc(Sub->getDebugLoc()); 51108b43921e18f314c4fd38049291d323830934c36Chris Lattner Sub->eraseFromParent(); 51200b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 513a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "Negated: " << *New << '\n'); 51408b43921e18f314c4fd38049291d323830934c36Chris Lattner return New; 51508b43921e18f314c4fd38049291d323830934c36Chris Lattner} 51608b43921e18f314c4fd38049291d323830934c36Chris Lattner 5170975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 5180975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// by one, change this into a multiply by a constant to assist with further 5190975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner/// reassociation. 520f1d0f7781e766df878bec4e7977fa3204374f394Craig Topperstatic Instruction *ConvertShiftToMul(Instruction *Shl, 521f1d0f7781e766df878bec4e7977fa3204374f394Craig Topper DenseMap<AssertingVH<Value>, unsigned> &ValueRankMap) { 52222a66c41f3ab42c15437033851395b0b8288681bChris Lattner // If an operand of this shift is a reassociable multiply, or if the shift 52322a66c41f3ab42c15437033851395b0b8288681bChris Lattner // is used by a reassociable multiply or add, turn into a multiply. 52422a66c41f3ab42c15437033851395b0b8288681bChris Lattner if (isReassociableOp(Shl->getOperand(0), Instruction::Mul) || 52522a66c41f3ab42c15437033851395b0b8288681bChris Lattner (Shl->hasOneUse() && 52622a66c41f3ab42c15437033851395b0b8288681bChris Lattner (isReassociableOp(Shl->use_back(), Instruction::Mul) || 52722a66c41f3ab42c15437033851395b0b8288681bChris Lattner isReassociableOp(Shl->use_back(), Instruction::Add)))) { 528eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 529f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 53022a66c41f3ab42c15437033851395b0b8288681bChris Lattner 531f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Instruction *Mul = 532f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl); 533f4978e2094a08760d4fa8a07052091cb7276eec7Dale Johannesen ValueRankMap.erase(Shl); 5346934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner Mul->takeName(Shl); 53522a66c41f3ab42c15437033851395b0b8288681bChris Lattner Shl->replaceAllUsesWith(Mul); 5365367b23f76e75ebb680956575346fa8c3d56780fDevang Patel Mul->setDebugLoc(Shl->getDebugLoc()); 53722a66c41f3ab42c15437033851395b0b8288681bChris Lattner Shl->eraseFromParent(); 53822a66c41f3ab42c15437033851395b0b8288681bChris Lattner return Mul; 53922a66c41f3ab42c15437033851395b0b8288681bChris Lattner } 54022a66c41f3ab42c15437033851395b0b8288681bChris Lattner return 0; 5410975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner} 5420975ed5f4ef7264b45995241717055f8a116bb27Chris Lattner 543109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner// Scan backwards and forwards among values with the same rank as element i to 5449506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner// see if X exists. If X does not exist, return i. This is useful when 5459506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner// scanning for 'x' when we see '-x' because they both get the same rank. 5469f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattnerstatic unsigned FindInOperandList(SmallVectorImpl<ValueEntry> &Ops, unsigned i, 547109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner Value *X) { 548109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner unsigned XRank = Ops[i].Rank; 549109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner unsigned e = Ops.size(); 550109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) 551109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Ops[j].Op == X) 552109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return j; 5539506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner // Scan backwards. 554109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) 555109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner if (Ops[j].Op == X) 556109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return j; 557109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner return i; 558109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner} 559109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 560e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together 561e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// and returning the result. Insert the tree before I. 5628d93b259f6d6ece634df86d5df453efc0c918546Chris Lattnerstatic Value *EmitAddTreeOfValues(Instruction *I, SmallVectorImpl<Value*> &Ops){ 563e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops.back(); 564e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 565e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *V1 = Ops.back(); 566e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Ops.pop_back(); 567e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Value *V2 = EmitAddTreeOfValues(I, Ops); 5687cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif return BinaryOperator::CreateAdd(V2, V1, "tmp", I); 569e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 570e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 571e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// RemoveFactorFromExpression - If V is an expression tree that is a 572e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// multiplication sequence, and if this sequence contains a multiply by Factor, 573e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner/// remove Factor from the tree and return the new tree. 574e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris LattnerValue *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { 575e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner BinaryOperator *BO = isReassociableOp(V, Instruction::Mul); 576e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (!BO) return 0; 577e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 5789f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVector<ValueEntry, 8> Factors; 579e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner LinearizeExprTree(BO, Factors); 580e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 581e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner bool FoundFactor = false; 5829506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner bool NeedsNegate = false; 5839506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 584e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Factors[i].Op == Factor) { 585e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner FoundFactor = true; 586e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner Factors.erase(Factors.begin()+i); 587e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner break; 588e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner } 5899506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner 5909506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner // If this is a negative version of this factor, remove it. 5919506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner if (ConstantInt *FC1 = dyn_cast<ConstantInt>(Factor)) 5929506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner if (ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op)) 5939506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner if (FC1->getValue() == -FC2->getValue()) { 5949506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner FoundFactor = NeedsNegate = true; 5959506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner Factors.erase(Factors.begin()+i); 5969506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner break; 5979506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner } 5989506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner } 5999506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner 600e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner if (!FoundFactor) { 601e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Make sure to restore the operands to the expression tree. 602e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner RewriteExprTree(BO, Factors); 603e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner return 0; 604e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner } 605e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 6069506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner BasicBlock::iterator InsertPt = BO; ++InsertPt; 6079506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner 6081e7558b65689999089f53ce40ff07564cf498c68Chris Lattner // If this was just a single multiply, remove the multiply and return the only 6091e7558b65689999089f53ce40ff07564cf498c68Chris Lattner // remaining operand. 6101e7558b65689999089f53ce40ff07564cf498c68Chris Lattner if (Factors.size() == 1) { 6111e7558b65689999089f53ce40ff07564cf498c68Chris Lattner ValueRankMap.erase(BO); 612fa0e6facc793d0a67e89f873e18cd35a9d7c02e0Dan Gohman DeadInsts.push_back(BO); 6139506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner V = Factors[0].Op; 6149506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner } else { 6159506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner RewriteExprTree(BO, Factors); 6169506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner V = BO; 6171e7558b65689999089f53ce40ff07564cf498c68Chris Lattner } 618e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 6199506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner if (NeedsNegate) 6209506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner V = BinaryOperator::CreateNeg(V, "neg", InsertPt); 6219506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner 6229506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner return V; 623e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner} 624e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 625e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively 626e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner/// add its operands as factors, otherwise add V to the list of factors. 627893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner/// 628893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner/// Ops is the top-level list of add operands we're trying to factor. 629e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattnerstatic void FindSingleUseMultiplyFactors(Value *V, 630893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner SmallVectorImpl<Value*> &Factors, 631893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner const SmallVectorImpl<ValueEntry> &Ops, 632893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner bool IsRoot) { 633e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner BinaryOperator *BO; 634893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner if (!(V->hasOneUse() || V->use_empty()) || // More than one use. 635e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner !(BO = dyn_cast<BinaryOperator>(V)) || 636e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner BO->getOpcode() != Instruction::Mul) { 637e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner Factors.push_back(V); 638e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner return; 639e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner } 640e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 641893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner // If this value has a single use because it is another input to the add 642893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner // tree we're reassociating and we dropped its use, it actually has two 643893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner // uses and we can't factor it. 644893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner if (!IsRoot) { 645893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) 646893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner if (Ops[i].Op == V) { 647893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner Factors.push_back(V); 648893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner return; 649893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner } 650893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner } 651893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner 652893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner 653e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner // Otherwise, add the LHS and RHS to the list of factors. 654893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner FindSingleUseMultiplyFactors(BO->getOperand(1), Factors, Ops, false); 655893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops, false); 656e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner} 657e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 658f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor' 659f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// instruction. This optimizes based on identities. If it can be reduced to 660f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// a single Value, it is returned, otherwise the Ops list is mutated as 661f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// necessary. 6629f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattnerstatic Value *OptimizeAndOrXor(unsigned Opcode, 6639f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops) { 664f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 665f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 666f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 667f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // First, check for X and ~X in the operand list. 668f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner assert(i < Ops.size()); 669f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 670f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 671f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner unsigned FoundX = FindInOperandList(Ops, i, X); 672f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (FoundX != i) { 6739fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (Opcode == Instruction::And) // ...&X&~X = 0 674f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Constant::getNullValue(X->getType()); 675f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 6769fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (Opcode == Instruction::Or) // ...|X|~X = -1 677f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Constant::getAllOnesValue(X->getType()); 678f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 679f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 680f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 681f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Next, check for duplicate pairs of values, which we assume are next to 682f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // each other, due to our sorting criteria. 683f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner assert(i < Ops.size()); 684f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 685f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (Opcode == Instruction::And || Opcode == Instruction::Or) { 686f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner // Drop duplicate values for And and Or. 687f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Ops.erase(Ops.begin()+i); 688f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner --i; --e; 689f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner ++NumAnnihil; 690f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner continue; 691f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 692f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner 693f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner // Drop pairs of values for Xor. 694f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner assert(Opcode == Instruction::Xor); 695f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner if (e == 2) 696f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner return Constant::getNullValue(Ops[0].Op->getType()); 697f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner 6989046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner // Y ^ X^X -> Y 699f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 700f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner i -= 1; e -= 2; 701f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner ++NumAnnihil; 702f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 703f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 704f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return 0; 705f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner} 706e9efecbf470100696355f32ea8b6ab942183ac6cChris Lattner 707f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// OptimizeAdd - Optimize a series of operands to an 'add' instruction. This 708f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// optimizes based on identities. If it can be reduced to a single Value, it 709f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner/// is returned, otherwise the Ops list is mutated as necessary. 7109f7b7089be854c323f8d9a4627d80e47adf496e6Chris LattnerValue *Reassociate::OptimizeAdd(Instruction *I, 7119f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops) { 712f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Scan the operand lists looking for X and -X pairs. If we find any, we 71369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // can simplify the expression. X+-X == 0. While we're at it, scan for any 71469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // duplicates. We want to canonicalize Y+Y+Y+Z -> 3*Y+Z. 7159506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner // 7169506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner // TODO: We could handle "X + ~X" -> "-1" if we wanted, since "-X = ~X+1". 7179506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner // 718f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 71969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *TheOp = Ops[i].Op; 72069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Check to see if we've seen this operand before. If so, we factor all 721f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner // instances of the operand together. Due to our sorting criteria, we know 722f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner // that these need to be next to each other in the vector. 723f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) { 724f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner // Rescan the list, remove all instances of this operand from the expr. 72569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner unsigned NumFound = 0; 726f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner do { 727f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner Ops.erase(Ops.begin()+i); 72869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner ++NumFound; 729f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner } while (i != Ops.size() && Ops[i].Op == TheOp); 730f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner 731f8a447de162a2896a8a044931fb63de713dbc6b9Chris Lattner DEBUG(errs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n'); 73269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner ++NumFactor; 73369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 73469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Insert a new multiply. 73569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *Mul = ConstantInt::get(cast<IntegerType>(I->getType()), NumFound); 73669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Mul = BinaryOperator::CreateMul(TheOp, Mul, "factor", I); 73769e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 73869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Now that we have inserted a multiply, optimize it. This allows us to 73969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // handle cases that require multiple factoring steps, such as this: 74069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6 741dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman RedoInsts.push_back(Mul); 74269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 74369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // If every add operand was a duplicate, return the multiply. 74469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner if (Ops.empty()) 74569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner return Mul; 74669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 74769e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Otherwise, we had some input that didn't have the dupe, such as 74869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // "A + A + B" -> "A*2 + B". Add the new multiply to the list of 74969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // things being added by this operation. 75069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul)); 751f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner 752f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner --i; 753f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner e = Ops.size(); 754f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner continue; 75569e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner } 75669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 757f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Check for X and -X in the operand list. 75869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner if (!BinaryOperator::isNeg(TheOp)) 759f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner continue; 760f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 76169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *X = BinaryOperator::getNegArgument(TheOp); 762f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner unsigned FoundX = FindInOperandList(Ops, i, X); 763f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (FoundX == i) 764f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner continue; 765f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 766f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner // Remove X and -X from the operand list. 7679fdaefad580194353f34b6d72669591f8f9d811aChris Lattner if (Ops.size() == 2) 768f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Constant::getNullValue(X->getType()); 769f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner 770f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Ops.erase(Ops.begin()+i); 771f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (i < FoundX) 772f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner --FoundX; 773f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner else 774f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner --i; // Need to back up an extra one. 775f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner Ops.erase(Ops.begin()+FoundX); 776f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner ++NumAnnihil; 777f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner --i; // Revisit element. 778f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner e -= 2; // Removed two elements. 779f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 78094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 78194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Scan the operand list, checking to see if there are any common factors 78294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // between operands. Consider something like A*A+A*B*C+D. We would like to 78394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies. 78494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // To efficiently find this, we count the number of times a factor occurs 78594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // for any ADD operands that are MULs. 78694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner DenseMap<Value*, unsigned> FactorOccurrences; 78794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 78894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4) 78994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // where they are actually the same multiply. 79094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner unsigned MaxOcc = 0; 79194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Value *MaxOccVal = 0; 79294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 79394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op); 79494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty()) 79594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner continue; 79694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 79794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Compute all of the factors of this added value. 79894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner SmallVector<Value*, 8> Factors; 799893075f46e9d07e3fe94e2b0e0f3ff8ae4061549Chris Lattner FindSingleUseMultiplyFactors(BOp, Factors, Ops, true); 80094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner assert(Factors.size() > 1 && "Bad linearize!"); 80194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 80294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Add one to FactorOccurrences for each unique factor in this op. 8039506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner SmallPtrSet<Value*, 8> Duplicates; 8049506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 8059506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner Value *Factor = Factors[i]; 8069506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner if (!Duplicates.insert(Factor)) continue; 8079506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner 8089506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner unsigned Occ = ++FactorOccurrences[Factor]; 8099506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } 8109506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner 8119506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner // If Factor is a negative constant, add the negated value as a factor 8129506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner // because we can percolate the negate out. Watch for minint, which 8139506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner // cannot be positivified. 8149506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) 815c73b24db5f6226ed44ebc44ce1c25bb357206623Chris Lattner if (CI->isNegative() && !CI->isMinValue(true)) { 8169506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner Factor = ConstantInt::get(CI->getContext(), -CI->getValue()); 8179506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner assert(!Duplicates.count(Factor) && 8189506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner "Shouldn't have two constant factors, missed a canonicalize"); 8199506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner 8209506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner unsigned Occ = ++FactorOccurrences[Factor]; 8219506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } 8229506c930aa1f7c5fbf1e0e1e6bfae71f4a61ee15Chris Lattner } 82394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 82494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 82594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 82694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // If any factor occurred more than one time, we can pull it out. 82794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (MaxOcc > 1) { 82869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner DEBUG(errs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n'); 82994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner ++NumFactor; 83094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 83194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // Create a new instruction that uses the MaxOccVal twice. If we don't do 83294285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // this, we could otherwise run into situations where removing a factor 83394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // from an expression will drop a use of maxocc, and this can cause 83494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // RemoveFactorFromExpression on successive values to behave differently. 83594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal); 83694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner SmallVector<Value*, 4> NewMulOps; 83737f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands for (unsigned i = 0; i != Ops.size(); ++i) { 838c2d1b6949c5141d21827cc94daea6ae4b1a9c750Chris Lattner // Only try to remove factors from expressions we're allowed to. 839c2d1b6949c5141d21827cc94daea6ae4b1a9c750Chris Lattner BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op); 840c2d1b6949c5141d21827cc94daea6ae4b1a9c750Chris Lattner if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty()) 841c2d1b6949c5141d21827cc94daea6ae4b1a9c750Chris Lattner continue; 842c2d1b6949c5141d21827cc94daea6ae4b1a9c750Chris Lattner 84394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { 84437f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands // The factorized operand may occur several times. Convert them all in 84537f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands // one fell swoop. 84637f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands for (unsigned j = Ops.size(); j != i;) { 84737f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands --j; 84837f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands if (Ops[j].Op == Ops[i].Op) { 84937f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands NewMulOps.push_back(V); 85037f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands Ops.erase(Ops.begin()+j); 85137f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands } 85237f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands } 85337f87c7aa914fba1362bb187ce5a386abfe94e39Duncan Sands --i; 85494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 85594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 85694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 85794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // No need for extra uses anymore. 85894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner delete DummyInst; 85954a57045ebcf8e31b1542098d1cd2bda9a718725Duncan Sands 86094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner unsigned NumAddedValues = NewMulOps.size(); 86194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Value *V = EmitAddTreeOfValues(I, NewMulOps); 86254a57045ebcf8e31b1542098d1cd2bda9a718725Duncan Sands 86369e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Now that we have inserted the add tree, optimize it. This allows us to 86469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // handle cases that require multiple factoring steps, such as this: 86594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C)) 8669cd1bc4f8b3e98892a2b9856eccd2a2ec9afdf7fChris Lattner assert(NumAddedValues > 1 && "Each occurrence should contribute a value"); 86754a57045ebcf8e31b1542098d1cd2bda9a718725Duncan Sands (void)NumAddedValues; 86869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner V = ReassociateExpression(cast<BinaryOperator>(V)); 86969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 87069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Create the multiply. 87169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner Value *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I); 87269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 873f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner // Rerun associate on the multiply in case the inner expression turned into 874f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner // a multiply. We want to make sure that we keep things in canonical form. 875f31e2e92a801c5053dc9b3b484cdec73ad89e567Chris Lattner V2 = ReassociateExpression(cast<BinaryOperator>(V2)); 87694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 87794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // If every add operand included the factor (e.g. "A*B + A*C"), then the 87894285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // entire result expression is just the multiply "A*(B+C)". 87994285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Ops.empty()) 88094285e620b845e09b18939e8d6448e01e692f3ceChris Lattner return V2; 88194285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 8829cd1bc4f8b3e98892a2b9856eccd2a2ec9afdf7fChris Lattner // Otherwise, we had some input that didn't have the factor, such as 88394285e620b845e09b18939e8d6448e01e692f3ceChris Lattner // "A*B + A*C + D" -> "A*(B+C) + D". Add the new multiply to the list of 8849cd1bc4f8b3e98892a2b9856eccd2a2ec9afdf7fChris Lattner // things being added by this operation. 88594285e620b845e09b18939e8d6448e01e692f3ceChris Lattner Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); 88694285e620b845e09b18939e8d6448e01e692f3ceChris Lattner } 88794285e620b845e09b18939e8d6448e01e692f3ceChris Lattner 888f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return 0; 889f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner} 890e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 891e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris LattnerValue *Reassociate::OptimizeExpression(BinaryOperator *I, 8929f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVectorImpl<ValueEntry> &Ops) { 893469001000620df176decd093a300db84a06cc78bChris Lattner // Now that we have the linearized expression tree, try to optimize it. 894469001000620df176decd093a300db84a06cc78bChris Lattner // Start by folding any constants that we found. 895109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner bool IterateOptimization = false; 896e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops[0].Op; 897469001000620df176decd093a300db84a06cc78bChris Lattner 898e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner unsigned Opcode = I->getOpcode(); 899e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 900469001000620df176decd093a300db84a06cc78bChris Lattner if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 901469001000620df176decd093a300db84a06cc78bChris Lattner if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 902469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 903baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 904e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return OptimizeExpression(I, Ops); 905469001000620df176decd093a300db84a06cc78bChris Lattner } 906469001000620df176decd093a300db84a06cc78bChris Lattner 907469001000620df176decd093a300db84a06cc78bChris Lattner // Check for destructive annihilation due to a constant being used. 9086b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op)) 909469001000620df176decd093a300db84a06cc78bChris Lattner switch (Opcode) { 910469001000620df176decd093a300db84a06cc78bChris Lattner default: break; 911469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::And: 9129046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner if (CstVal->isZero()) // X & 0 -> 0 913e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 9149046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner if (CstVal->isAllOnesValue()) // X & -1 -> X 9158d93b259f6d6ece634df86d5df453efc0c918546Chris Lattner Ops.pop_back(); 916469001000620df176decd093a300db84a06cc78bChris Lattner break; 917469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Mul: 9189046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner if (CstVal->isZero()) { // X * 0 -> 0 919109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner ++NumAnnihil; 920e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 921469001000620df176decd093a300db84a06cc78bChris Lattner } 9228d93b259f6d6ece634df86d5df453efc0c918546Chris Lattner 9238d93b259f6d6ece634df86d5df453efc0c918546Chris Lattner if (cast<ConstantInt>(CstVal)->isOne()) 9249046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner Ops.pop_back(); // X * 1 -> X 925469001000620df176decd093a300db84a06cc78bChris Lattner break; 926469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Or: 9279046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner if (CstVal->isAllOnesValue()) // X | -1 -> -1 928e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return CstVal; 929469001000620df176decd093a300db84a06cc78bChris Lattner // FALLTHROUGH! 930469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Add: 931469001000620df176decd093a300db84a06cc78bChris Lattner case Instruction::Xor: 9329046193e557d559f45dc50df5e20b1fccc90b2acChris Lattner if (CstVal->isZero()) // X [|^+] 0 -> X 933469001000620df176decd093a300db84a06cc78bChris Lattner Ops.pop_back(); 934469001000620df176decd093a300db84a06cc78bChris Lattner break; 935469001000620df176decd093a300db84a06cc78bChris Lattner } 936e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner if (Ops.size() == 1) return Ops[0].Op; 937469001000620df176decd093a300db84a06cc78bChris Lattner 938ec531233a16605756a84d175178e1ee0fac4791cChris Lattner // Handle destructive annihilation due to identities between elements in the 939469001000620df176decd093a300db84a06cc78bChris Lattner // argument list here. 940109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner switch (Opcode) { 941109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner default: break; 942109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner case Instruction::And: 943109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner case Instruction::Or: 944f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner case Instruction::Xor: { 945f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner unsigned NumOps = Ops.size(); 946f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner if (Value *Result = OptimizeAndOrXor(Opcode, Ops)) 947f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Result; 948f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner IterateOptimization |= Ops.size() != NumOps; 949109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner break; 950f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 951109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 952f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner case Instruction::Add: { 953f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner unsigned NumOps = Ops.size(); 95494285e620b845e09b18939e8d6448e01e692f3ceChris Lattner if (Value *Result = OptimizeAdd(I, Ops)) 955f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner return Result; 956f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner IterateOptimization |= Ops.size() != NumOps; 957f3f55a9bc1ce62fad7faecff7bd83565d569dee8Chris Lattner } 958e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner 959109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner break; 960109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner //case Instruction::Mul: 961109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner } 962109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3Chris Lattner 96300b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen if (IterateOptimization) 964e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return OptimizeExpression(I, Ops); 965e5022fe4cd83eef91f5c3a21c943ca9b65507ab8Chris Lattner return 0; 966469001000620df176decd093a300db84a06cc78bChris Lattner} 967469001000620df176decd093a300db84a06cc78bChris Lattner 96808b43921e18f314c4fd38049291d323830934c36Chris Lattner 969dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman/// ReassociateInst - Inspect and reassociate the instruction at the 970dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman/// given position, post-incrementing the position. 971dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohmanvoid Reassociate::ReassociateInst(BasicBlock::iterator &BBI) { 972dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman Instruction *BI = BBI++; 973dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (BI->getOpcode() == Instruction::Shl && 974dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman isa<ConstantInt>(BI->getOperand(1))) 975dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (Instruction *NI = ConvertShiftToMul(BI, ValueRankMap)) { 976dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman MadeChange = true; 977dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman BI = NI; 978dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman } 979641f02f10f08c9a9add651c6f0169f5441eaeb49Chris Lattner 980dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // Reject cases where it is pointless to do this. 981dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPointTy() || 982dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman BI->getType()->isVectorTy()) 983dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman return; // Floating point ops are not associative. 984dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman 985dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // Do not reassociate boolean (i1) expressions. We want to preserve the 986dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // original order of evaluation for short-circuited comparisons that 987dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // SimplifyCFG has folded to AND/OR expressions. If the expression 988dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // is not further optimized, it is likely to be transformed back to a 989dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // short-circuited form for code gen, and the source order may have been 990dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // optimized for the most likely conditions. 991dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (BI->getType()->isIntegerTy(1)) 992dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman return; 993fc375d22001d27ba6d22db67821da057e36f7f89Bob Wilson 994dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // If this is a subtract instruction which is not already in negate form, 995dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // see if we can convert it to X+-Y. 996dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (BI->getOpcode() == Instruction::Sub) { 997dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (ShouldBreakUpSubtract(BI)) { 998dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman BI = BreakUpSubtract(BI, ValueRankMap); 999dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // Reset the BBI iterator in case BreakUpSubtract changed the 1000dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // instruction it points to. 1001dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman BBI = BI; 1002dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman ++BBI; 1003dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman MadeChange = true; 1004dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman } else if (BinaryOperator::isNeg(BI)) { 1005dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // Otherwise, this is a negation. See if the operand is a multiply tree 1006dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // and if this is not an inner node of a multiply tree. 1007dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (isReassociableOp(BI->getOperand(1), Instruction::Mul) && 1008dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman (!BI->hasOneUse() || 1009dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman !isReassociableOp(BI->use_back(), Instruction::Mul))) { 1010dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman BI = LowerNegateToMultiply(BI, ValueRankMap); 1011d5b8d92b9f4dfb216e4f2a52b4e801d7559574baChris Lattner MadeChange = true; 101208b43921e18f314c4fd38049291d323830934c36Chris Lattner } 1013f33151aff008c40eec6435ddb7a5c9017b6acef9Chris Lattner } 1014dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman } 1015e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 1016dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // If this instruction is a commutative binary operator, process it. 1017dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (!BI->isAssociative()) return; 1018dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman BinaryOperator *I = cast<BinaryOperator>(BI); 101900b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 1020dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // If this is an interior node of a reassociable tree, ignore it until we 1021dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // get to the root of the tree, to avoid N^2 analysis. 1022dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode())) 1023dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman return; 1024c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner 1025dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // If this is an add tree that is used by a sub instruction, ignore it 1026dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // until we process the subtract. 1027dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (I->hasOneUse() && I->getOpcode() == Instruction::Add && 1028dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub) 1029dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman return; 10307b4ad94282b94e1827be29b4db73fdf6e241f748Chris Lattner 1031dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman ReassociateExpression(I); 1032895b392269cad07c34d59110d68dc86708c53adbChris Lattner} 1033c9fd097a01383323f166c14c17d3984620cad766Chris Lattner 103469e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris LattnerValue *Reassociate::ReassociateExpression(BinaryOperator *I) { 1035895b392269cad07c34d59110d68dc86708c53adbChris Lattner 103669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // First, walk the expression tree, linearizing the tree, collecting the 103769e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // operand information. 10389f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner SmallVector<ValueEntry, 8> Ops; 1039895b392269cad07c34d59110d68dc86708c53adbChris Lattner LinearizeExprTree(I, Ops); 1040895b392269cad07c34d59110d68dc86708c53adbChris Lattner 1041a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n'); 1042895b392269cad07c34d59110d68dc86708c53adbChris Lattner 1043895b392269cad07c34d59110d68dc86708c53adbChris Lattner // Now that we have linearized the tree to a list and have gathered all of 1044895b392269cad07c34d59110d68dc86708c53adbChris Lattner // the operands and their ranks, sort the operands by their rank. Use a 1045895b392269cad07c34d59110d68dc86708c53adbChris Lattner // stable_sort so that values with equal ranks will have their relative 1046895b392269cad07c34d59110d68dc86708c53adbChris Lattner // positions maintained (and so the compiler is deterministic). Note that 1047895b392269cad07c34d59110d68dc86708c53adbChris Lattner // this sorts so that the highest ranking values end up at the beginning of 1048895b392269cad07c34d59110d68dc86708c53adbChris Lattner // the vector. 1049895b392269cad07c34d59110d68dc86708c53adbChris Lattner std::stable_sort(Ops.begin(), Ops.end()); 1050895b392269cad07c34d59110d68dc86708c53adbChris Lattner 1051895b392269cad07c34d59110d68dc86708c53adbChris Lattner // OptimizeExpression - Now that we have the expression tree in a convenient 1052895b392269cad07c34d59110d68dc86708c53adbChris Lattner // sorted form, optimize it globally if possible. 1053895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (Value *V = OptimizeExpression(I, Ops)) { 1054895b392269cad07c34d59110d68dc86708c53adbChris Lattner // This expression tree simplified to something that isn't a tree, 1055895b392269cad07c34d59110d68dc86708c53adbChris Lattner // eliminate it. 1056a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n'); 1057895b392269cad07c34d59110d68dc86708c53adbChris Lattner I->replaceAllUsesWith(V); 10585367b23f76e75ebb680956575346fa8c3d56780fDevang Patel if (Instruction *VI = dyn_cast<Instruction>(V)) 10595367b23f76e75ebb680956575346fa8c3d56780fDevang Patel VI->setDebugLoc(I->getDebugLoc()); 1060895b392269cad07c34d59110d68dc86708c53adbChris Lattner RemoveDeadBinaryOp(I); 10619fdaefad580194353f34b6d72669591f8f9d811aChris Lattner ++NumAnnihil; 106269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner return V; 1063895b392269cad07c34d59110d68dc86708c53adbChris Lattner } 1064895b392269cad07c34d59110d68dc86708c53adbChris Lattner 1065895b392269cad07c34d59110d68dc86708c53adbChris Lattner // We want to sink immediates as deeply as possible except in the case where 1066895b392269cad07c34d59110d68dc86708c53adbChris Lattner // this is a multiply tree used only by an add, and the immediate is a -1. 1067895b392269cad07c34d59110d68dc86708c53adbChris Lattner // In this case we reassociate to put the negation on the outside so that we 1068895b392269cad07c34d59110d68dc86708c53adbChris Lattner // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y 1069895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (I->getOpcode() == Instruction::Mul && I->hasOneUse() && 1070895b392269cad07c34d59110d68dc86708c53adbChris Lattner cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add && 1071895b392269cad07c34d59110d68dc86708c53adbChris Lattner isa<ConstantInt>(Ops.back().Op) && 1072895b392269cad07c34d59110d68dc86708c53adbChris Lattner cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) { 10739f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner ValueEntry Tmp = Ops.pop_back_val(); 10749f7b7089be854c323f8d9a4627d80e47adf496e6Chris Lattner Ops.insert(Ops.begin(), Tmp); 1075895b392269cad07c34d59110d68dc86708c53adbChris Lattner } 1076895b392269cad07c34d59110d68dc86708c53adbChris Lattner 1077a1fa76cb5443e7b0fe7d36ee1118f80050e746f9David Greene DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n'); 1078895b392269cad07c34d59110d68dc86708c53adbChris Lattner 1079895b392269cad07c34d59110d68dc86708c53adbChris Lattner if (Ops.size() == 1) { 1080895b392269cad07c34d59110d68dc86708c53adbChris Lattner // This expression tree simplified to something that isn't a tree, 1081895b392269cad07c34d59110d68dc86708c53adbChris Lattner // eliminate it. 1082895b392269cad07c34d59110d68dc86708c53adbChris Lattner I->replaceAllUsesWith(Ops[0].Op); 10835367b23f76e75ebb680956575346fa8c3d56780fDevang Patel if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op)) 10845367b23f76e75ebb680956575346fa8c3d56780fDevang Patel OI->setDebugLoc(I->getDebugLoc()); 1085895b392269cad07c34d59110d68dc86708c53adbChris Lattner RemoveDeadBinaryOp(I); 108669e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner return Ops[0].Op; 10874fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 108869e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner 108969e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // Now that we ordered and optimized the expressions, splat them back into 109069e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner // the expression tree, removing any unneeded nodes. 109169e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner RewriteExprTree(I, Ops); 109269e98e2c0f7a1a1a8e3547b57e3e78e1142b8a64Chris Lattner return I; 10934fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 10944fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 10954fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 10967e70829632f82de15db187845666aaca6e04b792Chris Lattnerbool Reassociate::runOnFunction(Function &F) { 10974fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Recalculate the rank map for F 10984fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner BuildRankMap(F); 10994fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1100c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner MadeChange = false; 11017e70829632f82de15db187845666aaca6e04b792Chris Lattner for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 1102dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman for (BasicBlock::iterator BBI = FI->begin(); BBI != FI->end(); ) 1103dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman ReassociateInst(BBI); 1104dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman 1105dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // Now that we're done, revisit any instructions which are likely to 1106dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman // have secondary reassociation opportunities. 1107dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman while (!RedoInsts.empty()) 1108dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman if (Value *V = RedoInsts.pop_back_val()) { 1109dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman BasicBlock::iterator BBI = cast<Instruction>(V); 1110dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman ReassociateInst(BBI); 1111dac5dbadeb840ddded4665d144f31c5f88494d6eDan Gohman } 11124fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1113fa0e6facc793d0a67e89f873e18cd35a9d7c02e0Dan Gohman // Now that we're done, delete any instructions which are no longer used. 1114fa0e6facc793d0a67e89f873e18cd35a9d7c02e0Dan Gohman while (!DeadInsts.empty()) 1115c9f2f61d3426d30605b22ccbd112272d1d36cd28Dan Gohman if (Value *V = DeadInsts.pop_back_val()) 11169b7fdc7e8af26b65c9afdee45d4ec0b22c8a17c8Owen Anderson RecursivelyDeleteTriviallyDeadInstructions(V); 1117fa0e6facc793d0a67e89f873e18cd35a9d7c02e0Dan Gohman 1118f55e7f54b1877aa6a58b368084cc25acbaa30967Chris Lattner // We are done with the rank map. 11194fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner RankMap.clear(); 1120fb5be090f59997deb7a2e89c92bac19528ba6755Chris Lattner ValueRankMap.clear(); 1121c0649ac931d22b7118c1db292b887cd4eb52cd32Chris Lattner return MadeChange; 11224fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1123d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 1124