Reassociate.cpp revision 841f42617531ff947b2d957e7b0cb367a290aae4
1//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass reassociates commutative expressions in an order that is designed 11// to promote better constant propagation, GCSE, LICM, PRE, etc. 12// 13// For example: 4 + (x + 5) -> x + (4 + 5) 14// 15// In the implementation of this algorithm, constants are assigned rank = 0, 16// function arguments are rank = 1, and other values are assigned ranks 17// corresponding to the reverse post order traversal of current function 18// (starting at 2), which effectively gives values in deep loops higher rank 19// than values not in loops. 20// 21//===----------------------------------------------------------------------===// 22 23#define DEBUG_TYPE "reassociate" 24#include "llvm/Transforms/Scalar.h" 25#include "llvm/Transforms/Utils/Local.h" 26#include "llvm/Constants.h" 27#include "llvm/DerivedTypes.h" 28#include "llvm/Function.h" 29#include "llvm/Instructions.h" 30#include "llvm/IntrinsicInst.h" 31#include "llvm/Pass.h" 32#include "llvm/Assembly/Writer.h" 33#include "llvm/Support/CFG.h" 34#include "llvm/Support/IRBuilder.h" 35#include "llvm/Support/Debug.h" 36#include "llvm/Support/ValueHandle.h" 37#include "llvm/Support/raw_ostream.h" 38#include "llvm/ADT/DenseMap.h" 39#include "llvm/ADT/PostOrderIterator.h" 40#include "llvm/ADT/SetVector.h" 41#include "llvm/ADT/SmallMap.h" 42#include "llvm/ADT/STLExtras.h" 43#include "llvm/ADT/Statistic.h" 44#include <algorithm> 45using namespace llvm; 46 47STATISTIC(NumChanged, "Number of insts reassociated"); 48STATISTIC(NumAnnihil, "Number of expr tree annihilated"); 49STATISTIC(NumFactor , "Number of multiplies factored"); 50 51namespace { 52 struct ValueEntry { 53 unsigned Rank; 54 Value *Op; 55 ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 56 }; 57 inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 58 return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 59 } 60} 61 62#ifndef NDEBUG 63/// PrintOps - Print out the expression identified in the Ops list. 64/// 65static void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) { 66 Module *M = I->getParent()->getParent()->getParent(); 67 dbgs() << Instruction::getOpcodeName(I->getOpcode()) << " " 68 << *Ops[0].Op->getType() << '\t'; 69 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 70 dbgs() << "[ "; 71 WriteAsOperand(dbgs(), Ops[i].Op, false, M); 72 dbgs() << ", #" << Ops[i].Rank << "] "; 73 } 74} 75#endif 76 77namespace { 78 /// \brief Utility class representing a base and exponent pair which form one 79 /// factor of some product. 80 struct Factor { 81 Value *Base; 82 unsigned Power; 83 84 Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {} 85 86 /// \brief Sort factors by their Base. 87 struct BaseSorter { 88 bool operator()(const Factor &LHS, const Factor &RHS) { 89 return LHS.Base < RHS.Base; 90 } 91 }; 92 93 /// \brief Compare factors for equal bases. 94 struct BaseEqual { 95 bool operator()(const Factor &LHS, const Factor &RHS) { 96 return LHS.Base == RHS.Base; 97 } 98 }; 99 100 /// \brief Sort factors in descending order by their power. 101 struct PowerDescendingSorter { 102 bool operator()(const Factor &LHS, const Factor &RHS) { 103 return LHS.Power > RHS.Power; 104 } 105 }; 106 107 /// \brief Compare factors for equal powers. 108 struct PowerEqual { 109 bool operator()(const Factor &LHS, const Factor &RHS) { 110 return LHS.Power == RHS.Power; 111 } 112 }; 113 }; 114} 115 116namespace { 117 class Reassociate : public FunctionPass { 118 DenseMap<BasicBlock*, unsigned> RankMap; 119 DenseMap<AssertingVH<Value>, unsigned> ValueRankMap; 120 SetVector<AssertingVH<Instruction> > RedoInsts; 121 bool MadeChange; 122 public: 123 static char ID; // Pass identification, replacement for typeid 124 Reassociate() : FunctionPass(ID) { 125 initializeReassociatePass(*PassRegistry::getPassRegistry()); 126 } 127 128 bool runOnFunction(Function &F); 129 130 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 131 AU.setPreservesCFG(); 132 } 133 private: 134 void BuildRankMap(Function &F); 135 unsigned getRank(Value *V); 136 Value *ReassociateExpression(BinaryOperator *I); 137 void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 138 Value *OptimizeExpression(BinaryOperator *I, 139 SmallVectorImpl<ValueEntry> &Ops); 140 Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops); 141 bool collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops, 142 SmallVectorImpl<Factor> &Factors); 143 Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder, 144 SmallVectorImpl<Factor> &Factors); 145 Value *OptimizeMul(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 146 void LinearizeExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 147 Value *RemoveFactorFromExpression(Value *V, Value *Factor); 148 void EraseInst(Instruction *I); 149 void OptimizeInst(Instruction *I); 150 }; 151} 152 153char Reassociate::ID = 0; 154INITIALIZE_PASS(Reassociate, "reassociate", 155 "Reassociate expressions", false, false) 156 157// Public interface to the Reassociate pass 158FunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 159 160/// isReassociableOp - Return true if V is an instruction of the specified 161/// opcode and if it only has one use. 162static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 163 if (V->hasOneUse() && isa<Instruction>(V) && 164 cast<Instruction>(V)->getOpcode() == Opcode) 165 return cast<BinaryOperator>(V); 166 return 0; 167} 168 169static bool isUnmovableInstruction(Instruction *I) { 170 if (I->getOpcode() == Instruction::PHI || 171 I->getOpcode() == Instruction::LandingPad || 172 I->getOpcode() == Instruction::Alloca || 173 I->getOpcode() == Instruction::Load || 174 I->getOpcode() == Instruction::Invoke || 175 (I->getOpcode() == Instruction::Call && 176 !isa<DbgInfoIntrinsic>(I)) || 177 I->getOpcode() == Instruction::UDiv || 178 I->getOpcode() == Instruction::SDiv || 179 I->getOpcode() == Instruction::FDiv || 180 I->getOpcode() == Instruction::URem || 181 I->getOpcode() == Instruction::SRem || 182 I->getOpcode() == Instruction::FRem) 183 return true; 184 return false; 185} 186 187void Reassociate::BuildRankMap(Function &F) { 188 unsigned i = 2; 189 190 // Assign distinct ranks to function arguments 191 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 192 ValueRankMap[&*I] = ++i; 193 194 ReversePostOrderTraversal<Function*> RPOT(&F); 195 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 196 E = RPOT.end(); I != E; ++I) { 197 BasicBlock *BB = *I; 198 unsigned BBRank = RankMap[BB] = ++i << 16; 199 200 // Walk the basic block, adding precomputed ranks for any instructions that 201 // we cannot move. This ensures that the ranks for these instructions are 202 // all different in the block. 203 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 204 if (isUnmovableInstruction(I)) 205 ValueRankMap[&*I] = ++BBRank; 206 } 207} 208 209unsigned Reassociate::getRank(Value *V) { 210 Instruction *I = dyn_cast<Instruction>(V); 211 if (I == 0) { 212 if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument. 213 return 0; // Otherwise it's a global or constant, rank 0. 214 } 215 216 if (unsigned Rank = ValueRankMap[I]) 217 return Rank; // Rank already known? 218 219 // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 220 // we can reassociate expressions for code motion! Since we do not recurse 221 // for PHI nodes, we cannot have infinite recursion here, because there 222 // cannot be loops in the value graph that do not go through PHI nodes. 223 unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 224 for (unsigned i = 0, e = I->getNumOperands(); 225 i != e && Rank != MaxRank; ++i) 226 Rank = std::max(Rank, getRank(I->getOperand(i))); 227 228 // If this is a not or neg instruction, do not count it for rank. This 229 // assures us that X and ~X will have the same rank. 230 if (!I->getType()->isIntegerTy() || 231 (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 232 ++Rank; 233 234 //DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = " 235 // << Rank << "\n"); 236 237 return ValueRankMap[I] = Rank; 238} 239 240/// LowerNegateToMultiply - Replace 0-X with X*-1. 241/// 242static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) { 243 Constant *Cst = Constant::getAllOnesValue(Neg->getType()); 244 245 BinaryOperator *Res = 246 BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg); 247 Neg->setOperand(1, Constant::getNullValue(Neg->getType())); // Drop use of op. 248 Res->takeName(Neg); 249 Neg->replaceAllUsesWith(Res); 250 Res->setDebugLoc(Neg->getDebugLoc()); 251 return Res; 252} 253 254/// LinearizeExprTree - Given an associative binary expression, return the leaf 255/// nodes in Ops. The original expression is the same as Ops[0] op ... Ops[N]. 256/// Note that a node may occur multiple times in Ops, but if so all occurrences 257/// are consecutive in the vector. 258/// 259/// A leaf node is either not a binary operation of the same kind as the root 260/// node 'I' (i.e. is not a binary operator at all, or is, but with a different 261/// opcode), or is the same kind of binary operator but has a use which either 262/// does not belong to the expression, or does belong to the expression but is 263/// a leaf node. Every leaf node has at least one use that is a non-leaf node 264/// of the expression, while for non-leaf nodes (except for the root 'I') every 265/// use is a non-leaf node of the expression. 266/// 267/// For example: 268/// expression graph node names 269/// 270/// + | I 271/// / \ | 272/// + + | A, B 273/// / \ / \ | 274/// * + * | C, D, E 275/// / \ / \ / \ | 276/// + * | F, G 277/// 278/// The leaf nodes are C, E, F and G. The Ops array will contain (maybe not in 279/// that order) C, E, F, F, G, G. 280/// 281/// The expression is maximal: if some instruction is a binary operator of the 282/// same kind as 'I', and all of its uses are non-leaf nodes of the expression, 283/// then the instruction also belongs to the expression, is not a leaf node of 284/// it, and its operands also belong to the expression (but may be leaf nodes). 285/// 286/// NOTE: This routine will set operands of non-leaf non-root nodes to undef in 287/// order to ensure that every non-root node in the expression has *exactly one* 288/// use by a non-leaf node of the expression. This destruction means that the 289/// caller MUST either replace 'I' with a new expression or use something like 290/// RewriteExprTree to put the values back in. 291/// 292/// In the above example either the right operand of A or the left operand of B 293/// will be replaced by undef. If it is B's operand then this gives: 294/// 295/// + | I 296/// / \ | 297/// + + | A, B - operand of B replaced with undef 298/// / \ \ | 299/// * + * | C, D, E 300/// / \ / \ / \ | 301/// + * | F, G 302/// 303/// Note that such undef operands can only be reached by passing through 'I'. 304/// For example, if you visit operands recursively starting from a leaf node 305/// then you will never see such an undef operand unless you get back to 'I', 306/// which requires passing through a phi node. 307/// 308/// Note that this routine may also mutate binary operators of the wrong type 309/// that have all uses inside the expression (i.e. only used by non-leaf nodes 310/// of the expression) if it can turn them into binary operators of the right 311/// type and thus make the expression bigger. 312 313void Reassociate::LinearizeExprTree(BinaryOperator *I, 314 SmallVectorImpl<ValueEntry> &Ops) { 315 DEBUG(dbgs() << "LINEARIZE: " << *I << '\n'); 316 317 // Visit all operands of the expression, keeping track of their weight (the 318 // number of paths from the expression root to the operand, or if you like 319 // the number of times that operand occurs in the linearized expression). 320 // For example, if I = X + A, where X = A + B, then I, X and B have weight 1 321 // while A has weight two. 322 323 // Worklist of non-leaf nodes (their operands are in the expression too) along 324 // with their weights, representing a certain number of paths to the operator. 325 // If an operator occurs in the worklist multiple times then we found multiple 326 // ways to get to it. 327 SmallVector<std::pair<BinaryOperator*, unsigned>, 8> Worklist; // (Op, Weight) 328 Worklist.push_back(std::make_pair(I, 1)); 329 unsigned Opcode = I->getOpcode(); 330 331 // Leaves of the expression are values that either aren't the right kind of 332 // operation (eg: a constant, or a multiply in an add tree), or are, but have 333 // some uses that are not inside the expression. For example, in I = X + X, 334 // X = A + B, the value X has two uses (by I) that are in the expression. If 335 // X has any other uses, for example in a return instruction, then we consider 336 // X to be a leaf, and won't analyze it further. When we first visit a value, 337 // if it has more than one use then at first we conservatively consider it to 338 // be a leaf. Later, as the expression is explored, we may discover some more 339 // uses of the value from inside the expression. If all uses turn out to be 340 // from within the expression (and the value is a binary operator of the right 341 // kind) then the value is no longer considered to be a leaf, and its operands 342 // are explored. 343 344 // Leaves - Keeps track of the set of putative leaves as well as the number of 345 // paths to each leaf seen so far. 346 typedef SmallMap<Value*, unsigned, 8> LeafMap; 347 LeafMap Leaves; // Leaf -> Total weight so far. 348 SmallVector<Value*, 8> LeafOrder; // Ensure deterministic leaf output order. 349 350#ifndef NDEBUG 351 SmallPtrSet<Value*, 8> Visited; // For sanity checking the iteration scheme. 352#endif 353 while (!Worklist.empty()) { 354 std::pair<BinaryOperator*, unsigned> P = Worklist.pop_back_val(); 355 I = P.first; // We examine the operands of this binary operator. 356 assert(P.second >= 1 && "No paths to here, so how did we get here?!"); 357 358 for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) { // Visit operands. 359 Value *Op = I->getOperand(OpIdx); 360 unsigned Weight = P.second; // Number of paths to this operand. 361 DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n"); 362 assert(!Op->use_empty() && "No uses, so how did we get to it?!"); 363 364 // If this is a binary operation of the right kind with only one use then 365 // add its operands to the expression. 366 if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) { 367 assert(Visited.insert(Op) && "Not first visit!"); 368 DEBUG(dbgs() << "DIRECT ADD: " << *Op << " (" << Weight << ")\n"); 369 Worklist.push_back(std::make_pair(BO, Weight)); 370 continue; 371 } 372 373 // Appears to be a leaf. Is the operand already in the set of leaves? 374 LeafMap::iterator It = Leaves.find(Op); 375 if (It == Leaves.end()) { 376 // Not in the leaf map. Must be the first time we saw this operand. 377 assert(Visited.insert(Op) && "Not first visit!"); 378 if (!Op->hasOneUse()) { 379 // This value has uses not accounted for by the expression, so it is 380 // not safe to modify. Mark it as being a leaf. 381 DEBUG(dbgs() << "ADD USES LEAF: " << *Op << " (" << Weight << ")\n"); 382 LeafOrder.push_back(Op); 383 Leaves[Op] = Weight; 384 continue; 385 } 386 // No uses outside the expression, try morphing it. 387 } else if (It != Leaves.end()) { 388 // Already in the leaf map. 389 assert(Visited.count(Op) && "In leaf map but not visited!"); 390 391 // Update the number of paths to the leaf. 392 It->second += Weight; 393 394 // The leaf already has one use from inside the expression. As we want 395 // exactly one such use, drop this new use of the leaf. 396 assert(!Op->hasOneUse() && "Only one use, but we got here twice!"); 397 I->setOperand(OpIdx, UndefValue::get(I->getType())); 398 MadeChange = true; 399 400 // If the leaf is a binary operation of the right kind and we now see 401 // that its multiple original uses were in fact all by nodes belonging 402 // to the expression, then no longer consider it to be a leaf and add 403 // its operands to the expression. 404 if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) { 405 DEBUG(dbgs() << "UNLEAF: " << *Op << " (" << It->second << ")\n"); 406 Worklist.push_back(std::make_pair(BO, It->second)); 407 Leaves.erase(It); 408 continue; 409 } 410 411 // If we still have uses that are not accounted for by the expression 412 // then it is not safe to modify the value. 413 if (!Op->hasOneUse()) 414 continue; 415 416 // No uses outside the expression, try morphing it. 417 Weight = It->second; 418 Leaves.erase(It); // Since the value may be morphed below. 419 } 420 421 // At this point we have a value which, first of all, is not a binary 422 // expression of the right kind, and secondly, is only used inside the 423 // expression. This means that it can safely be modified. See if we 424 // can usefully morph it into an expression of the right kind. 425 assert((!isa<Instruction>(Op) || 426 cast<Instruction>(Op)->getOpcode() != Opcode) && 427 "Should have been handled above!"); 428 assert(Op->hasOneUse() && "Has uses outside the expression tree!"); 429 430 // If this is a multiply expression, turn any internal negations into 431 // multiplies by -1 so they can be reassociated. 432 BinaryOperator *BO = dyn_cast<BinaryOperator>(Op); 433 if (Opcode == Instruction::Mul && BO && BinaryOperator::isNeg(BO)) { 434 DEBUG(dbgs() << "MORPH LEAF: " << *Op << " (" << Weight << ") TO "); 435 BO = LowerNegateToMultiply(BO); 436 DEBUG(dbgs() << *BO << 'n'); 437 Worklist.push_back(std::make_pair(BO, Weight)); 438 MadeChange = true; 439 continue; 440 } 441 442 // Failed to morph into an expression of the right type. This really is 443 // a leaf. 444 DEBUG(dbgs() << "ADD LEAF: " << *Op << " (" << Weight << ")\n"); 445 assert(!isReassociableOp(Op, Opcode) && "Value was morphed?"); 446 LeafOrder.push_back(Op); 447 Leaves[Op] = Weight; 448 } 449 } 450 451 // The leaves, repeated according to their weights, represent the linearized 452 // form of the expression. 453 for (unsigned i = 0, e = LeafOrder.size(); i != e; ++i) { 454 Value *V = LeafOrder[i]; 455 LeafMap::iterator It = Leaves.find(V); 456 if (It == Leaves.end()) 457 // Leaf already output, or node initially thought to be a leaf wasn't. 458 continue; 459 assert(!isReassociableOp(V, Opcode) && "Shouldn't be a leaf!"); 460 unsigned Weight = It->second; 461 assert(Weight > 0 && "No paths to this value!"); 462 // FIXME: Rather than repeating values Weight times, use a vector of 463 // (ValueEntry, multiplicity) pairs. 464 Ops.append(Weight, ValueEntry(getRank(V), V)); 465 // Ensure the leaf is only output once. 466 Leaves.erase(It); 467 } 468} 469 470// RewriteExprTree - Now that the operands for this expression tree are 471// linearized and optimized, emit them in-order. 472void Reassociate::RewriteExprTree(BinaryOperator *I, 473 SmallVectorImpl<ValueEntry> &Ops) { 474 assert(Ops.size() > 1 && "Single values should be used directly!"); 475 476 // Since our optimizations never increase the number of operations, the new 477 // expression can always be written by reusing the existing binary operators 478 // from the original expression tree, without creating any new instructions, 479 // though the rewritten expression may have a completely different topology. 480 // We take care to not change anything if the new expression will be the same 481 // as the original. If more than trivial changes (like commuting operands) 482 // were made then we are obliged to clear out any optional subclass data like 483 // nsw flags. 484 485 /// NodesToRewrite - Nodes from the original expression available for writing 486 /// the new expression into. 487 SmallVector<BinaryOperator*, 8> NodesToRewrite; 488 unsigned Opcode = I->getOpcode(); 489 NodesToRewrite.push_back(I); 490 491 // ExpressionChanged - Non-null if the rewritten expression differs from the 492 // original in some non-trivial way, requiring the clearing of optional flags. 493 // Flags are cleared from the operator in ExpressionChanged up to I inclusive. 494 BinaryOperator *ExpressionChanged = 0; 495 BinaryOperator *Previous; 496 BinaryOperator *Op = 0; 497 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 498 assert(!NodesToRewrite.empty() && 499 "Optimized expressions has more nodes than original!"); 500 Previous = Op; Op = NodesToRewrite.pop_back_val(); 501 if (ExpressionChanged) 502 // Compactify the tree instructions together with each other to guarantee 503 // that the expression tree is dominated by all of Ops. 504 Op->moveBefore(Previous); 505 506 // The last operation (which comes earliest in the IR) is special as both 507 // operands will come from Ops, rather than just one with the other being 508 // a subexpression. 509 if (i+2 == Ops.size()) { 510 Value *NewLHS = Ops[i].Op; 511 Value *NewRHS = Ops[i+1].Op; 512 Value *OldLHS = Op->getOperand(0); 513 Value *OldRHS = Op->getOperand(1); 514 515 if (NewLHS == OldLHS && NewRHS == OldRHS) 516 // Nothing changed, leave it alone. 517 break; 518 519 if (NewLHS == OldRHS && NewRHS == OldLHS) { 520 // The order of the operands was reversed. Swap them. 521 DEBUG(dbgs() << "RA: " << *Op << '\n'); 522 Op->swapOperands(); 523 DEBUG(dbgs() << "TO: " << *Op << '\n'); 524 MadeChange = true; 525 ++NumChanged; 526 break; 527 } 528 529 // The new operation differs non-trivially from the original. Overwrite 530 // the old operands with the new ones. 531 DEBUG(dbgs() << "RA: " << *Op << '\n'); 532 if (NewLHS != OldLHS) { 533 if (BinaryOperator *BO = isReassociableOp(OldLHS, Opcode)) 534 NodesToRewrite.push_back(BO); 535 Op->setOperand(0, NewLHS); 536 } 537 if (NewRHS != OldRHS) { 538 if (BinaryOperator *BO = isReassociableOp(OldRHS, Opcode)) 539 NodesToRewrite.push_back(BO); 540 Op->setOperand(1, NewRHS); 541 } 542 DEBUG(dbgs() << "TO: " << *Op << '\n'); 543 544 ExpressionChanged = Op; 545 MadeChange = true; 546 ++NumChanged; 547 548 break; 549 } 550 551 // Not the last operation. The left-hand side will be a sub-expression 552 // while the right-hand side will be the current element of Ops. 553 Value *NewRHS = Ops[i].Op; 554 if (NewRHS != Op->getOperand(1)) { 555 DEBUG(dbgs() << "RA: " << *Op << '\n'); 556 if (NewRHS == Op->getOperand(0)) { 557 // The new right-hand side was already present as the left operand. If 558 // we are lucky then swapping the operands will sort out both of them. 559 Op->swapOperands(); 560 } else { 561 // Overwrite with the new right-hand side. 562 if (BinaryOperator *BO = isReassociableOp(Op->getOperand(1), Opcode)) 563 NodesToRewrite.push_back(BO); 564 Op->setOperand(1, NewRHS); 565 ExpressionChanged = Op; 566 } 567 DEBUG(dbgs() << "TO: " << *Op << '\n'); 568 MadeChange = true; 569 ++NumChanged; 570 } 571 572 // Now deal with the left-hand side. If this is already an operation node 573 // from the original expression then just rewrite the rest of the expression 574 // into it. 575 if (BinaryOperator *BO = isReassociableOp(Op->getOperand(0), Opcode)) { 576 NodesToRewrite.push_back(BO); 577 continue; 578 } 579 580 // Otherwise, grab a spare node from the original expression and use that as 581 // the left-hand side. 582 assert(!NodesToRewrite.empty() && 583 "Optimized expressions has more nodes than original!"); 584 DEBUG(dbgs() << "RA: " << *Op << '\n'); 585 Op->setOperand(0, NodesToRewrite.back()); 586 DEBUG(dbgs() << "TO: " << *Op << '\n'); 587 ExpressionChanged = Op; 588 MadeChange = true; 589 ++NumChanged; 590 } 591 592 // If the expression changed non-trivially then clear out all subclass data 593 // starting from the operator specified in ExpressionChanged. 594 if (ExpressionChanged) { 595 do { 596 ExpressionChanged->clearSubclassOptionalData(); 597 if (ExpressionChanged == I) 598 break; 599 ExpressionChanged = cast<BinaryOperator>(*ExpressionChanged->use_begin()); 600 } while (1); 601 } 602 603 // Throw away any left over nodes from the original expression. 604 for (unsigned i = 0, e = NodesToRewrite.size(); i != e; ++i) 605 RedoInsts.insert(NodesToRewrite[i]); 606} 607 608/// NegateValue - Insert instructions before the instruction pointed to by BI, 609/// that computes the negative version of the value specified. The negative 610/// version of the value is returned, and BI is left pointing at the instruction 611/// that should be processed next by the reassociation pass. 612static Value *NegateValue(Value *V, Instruction *BI) { 613 if (Constant *C = dyn_cast<Constant>(V)) 614 return ConstantExpr::getNeg(C); 615 616 // We are trying to expose opportunity for reassociation. One of the things 617 // that we want to do to achieve this is to push a negation as deep into an 618 // expression chain as possible, to expose the add instructions. In practice, 619 // this means that we turn this: 620 // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 621 // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 622 // the constants. We assume that instcombine will clean up the mess later if 623 // we introduce tons of unnecessary negation instructions. 624 // 625 if (BinaryOperator *I = isReassociableOp(V, Instruction::Add)) { 626 // Push the negates through the add. 627 I->setOperand(0, NegateValue(I->getOperand(0), BI)); 628 I->setOperand(1, NegateValue(I->getOperand(1), BI)); 629 630 // We must move the add instruction here, because the neg instructions do 631 // not dominate the old add instruction in general. By moving it, we are 632 // assured that the neg instructions we just inserted dominate the 633 // instruction we are about to insert after them. 634 // 635 I->moveBefore(BI); 636 I->setName(I->getName()+".neg"); 637 return I; 638 } 639 640 // Okay, we need to materialize a negated version of V with an instruction. 641 // Scan the use lists of V to see if we have one already. 642 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){ 643 User *U = *UI; 644 if (!BinaryOperator::isNeg(U)) continue; 645 646 // We found one! Now we have to make sure that the definition dominates 647 // this use. We do this by moving it to the entry block (if it is a 648 // non-instruction value) or right after the definition. These negates will 649 // be zapped by reassociate later, so we don't need much finesse here. 650 BinaryOperator *TheNeg = cast<BinaryOperator>(U); 651 652 // Verify that the negate is in this function, V might be a constant expr. 653 if (TheNeg->getParent()->getParent() != BI->getParent()->getParent()) 654 continue; 655 656 BasicBlock::iterator InsertPt; 657 if (Instruction *InstInput = dyn_cast<Instruction>(V)) { 658 if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) { 659 InsertPt = II->getNormalDest()->begin(); 660 } else { 661 InsertPt = InstInput; 662 ++InsertPt; 663 } 664 while (isa<PHINode>(InsertPt)) ++InsertPt; 665 } else { 666 InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin(); 667 } 668 TheNeg->moveBefore(InsertPt); 669 return TheNeg; 670 } 671 672 // Insert a 'neg' instruction that subtracts the value from zero to get the 673 // negation. 674 return BinaryOperator::CreateNeg(V, V->getName() + ".neg", BI); 675} 676 677/// ShouldBreakUpSubtract - Return true if we should break up this subtract of 678/// X-Y into (X + -Y). 679static bool ShouldBreakUpSubtract(Instruction *Sub) { 680 // If this is a negation, we can't split it up! 681 if (BinaryOperator::isNeg(Sub)) 682 return false; 683 684 // Don't bother to break this up unless either the LHS is an associable add or 685 // subtract or if this is only used by one. 686 if (isReassociableOp(Sub->getOperand(0), Instruction::Add) || 687 isReassociableOp(Sub->getOperand(0), Instruction::Sub)) 688 return true; 689 if (isReassociableOp(Sub->getOperand(1), Instruction::Add) || 690 isReassociableOp(Sub->getOperand(1), Instruction::Sub)) 691 return true; 692 if (Sub->hasOneUse() && 693 (isReassociableOp(Sub->use_back(), Instruction::Add) || 694 isReassociableOp(Sub->use_back(), Instruction::Sub))) 695 return true; 696 697 return false; 698} 699 700/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 701/// only used by an add, transform this into (X+(0-Y)) to promote better 702/// reassociation. 703static BinaryOperator *BreakUpSubtract(Instruction *Sub) { 704 // Convert a subtract into an add and a neg instruction. This allows sub 705 // instructions to be commuted with other add instructions. 706 // 707 // Calculate the negative value of Operand 1 of the sub instruction, 708 // and set it as the RHS of the add instruction we just made. 709 // 710 Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 711 BinaryOperator *New = 712 BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub); 713 Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op. 714 Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op. 715 New->takeName(Sub); 716 717 // Everyone now refers to the add instruction. 718 Sub->replaceAllUsesWith(New); 719 New->setDebugLoc(Sub->getDebugLoc()); 720 721 DEBUG(dbgs() << "Negated: " << *New << '\n'); 722 return New; 723} 724 725/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 726/// by one, change this into a multiply by a constant to assist with further 727/// reassociation. 728static BinaryOperator *ConvertShiftToMul(Instruction *Shl) { 729 Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 730 MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 731 732 BinaryOperator *Mul = 733 BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl); 734 Shl->setOperand(0, UndefValue::get(Shl->getType())); // Drop use of op. 735 Mul->takeName(Shl); 736 Shl->replaceAllUsesWith(Mul); 737 Mul->setDebugLoc(Shl->getDebugLoc()); 738 return Mul; 739} 740 741/// FindInOperandList - Scan backwards and forwards among values with the same 742/// rank as element i to see if X exists. If X does not exist, return i. This 743/// is useful when scanning for 'x' when we see '-x' because they both get the 744/// same rank. 745static unsigned FindInOperandList(SmallVectorImpl<ValueEntry> &Ops, unsigned i, 746 Value *X) { 747 unsigned XRank = Ops[i].Rank; 748 unsigned e = Ops.size(); 749 for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) 750 if (Ops[j].Op == X) 751 return j; 752 // Scan backwards. 753 for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) 754 if (Ops[j].Op == X) 755 return j; 756 return i; 757} 758 759/// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together 760/// and returning the result. Insert the tree before I. 761static Value *EmitAddTreeOfValues(Instruction *I, 762 SmallVectorImpl<WeakVH> &Ops){ 763 if (Ops.size() == 1) return Ops.back(); 764 765 Value *V1 = Ops.back(); 766 Ops.pop_back(); 767 Value *V2 = EmitAddTreeOfValues(I, Ops); 768 return BinaryOperator::CreateAdd(V2, V1, "tmp", I); 769} 770 771/// RemoveFactorFromExpression - If V is an expression tree that is a 772/// multiplication sequence, and if this sequence contains a multiply by Factor, 773/// remove Factor from the tree and return the new tree. 774Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { 775 BinaryOperator *BO = isReassociableOp(V, Instruction::Mul); 776 if (!BO) return 0; 777 778 SmallVector<ValueEntry, 8> Factors; 779 LinearizeExprTree(BO, Factors); 780 781 bool FoundFactor = false; 782 bool NeedsNegate = false; 783 for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 784 if (Factors[i].Op == Factor) { 785 FoundFactor = true; 786 Factors.erase(Factors.begin()+i); 787 break; 788 } 789 790 // If this is a negative version of this factor, remove it. 791 if (ConstantInt *FC1 = dyn_cast<ConstantInt>(Factor)) 792 if (ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op)) 793 if (FC1->getValue() == -FC2->getValue()) { 794 FoundFactor = NeedsNegate = true; 795 Factors.erase(Factors.begin()+i); 796 break; 797 } 798 } 799 800 if (!FoundFactor) { 801 // Make sure to restore the operands to the expression tree. 802 RewriteExprTree(BO, Factors); 803 return 0; 804 } 805 806 BasicBlock::iterator InsertPt = BO; ++InsertPt; 807 808 // If this was just a single multiply, remove the multiply and return the only 809 // remaining operand. 810 if (Factors.size() == 1) { 811 RedoInsts.insert(BO); 812 V = Factors[0].Op; 813 } else { 814 RewriteExprTree(BO, Factors); 815 V = BO; 816 } 817 818 if (NeedsNegate) 819 V = BinaryOperator::CreateNeg(V, "neg", InsertPt); 820 821 return V; 822} 823 824/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively 825/// add its operands as factors, otherwise add V to the list of factors. 826/// 827/// Ops is the top-level list of add operands we're trying to factor. 828static void FindSingleUseMultiplyFactors(Value *V, 829 SmallVectorImpl<Value*> &Factors, 830 const SmallVectorImpl<ValueEntry> &Ops) { 831 BinaryOperator *BO = isReassociableOp(V, Instruction::Mul); 832 if (!BO) { 833 Factors.push_back(V); 834 return; 835 } 836 837 // Otherwise, add the LHS and RHS to the list of factors. 838 FindSingleUseMultiplyFactors(BO->getOperand(1), Factors, Ops); 839 FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops); 840} 841 842/// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor' 843/// instruction. This optimizes based on identities. If it can be reduced to 844/// a single Value, it is returned, otherwise the Ops list is mutated as 845/// necessary. 846static Value *OptimizeAndOrXor(unsigned Opcode, 847 SmallVectorImpl<ValueEntry> &Ops) { 848 // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 849 // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 850 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 851 // First, check for X and ~X in the operand list. 852 assert(i < Ops.size()); 853 if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 854 Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 855 unsigned FoundX = FindInOperandList(Ops, i, X); 856 if (FoundX != i) { 857 if (Opcode == Instruction::And) // ...&X&~X = 0 858 return Constant::getNullValue(X->getType()); 859 860 if (Opcode == Instruction::Or) // ...|X|~X = -1 861 return Constant::getAllOnesValue(X->getType()); 862 } 863 } 864 865 // Next, check for duplicate pairs of values, which we assume are next to 866 // each other, due to our sorting criteria. 867 assert(i < Ops.size()); 868 if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 869 if (Opcode == Instruction::And || Opcode == Instruction::Or) { 870 // Drop duplicate values for And and Or. 871 Ops.erase(Ops.begin()+i); 872 --i; --e; 873 ++NumAnnihil; 874 continue; 875 } 876 877 // Drop pairs of values for Xor. 878 assert(Opcode == Instruction::Xor); 879 if (e == 2) 880 return Constant::getNullValue(Ops[0].Op->getType()); 881 882 // Y ^ X^X -> Y 883 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 884 i -= 1; e -= 2; 885 ++NumAnnihil; 886 } 887 } 888 return 0; 889} 890 891/// OptimizeAdd - Optimize a series of operands to an 'add' instruction. This 892/// optimizes based on identities. If it can be reduced to a single Value, it 893/// is returned, otherwise the Ops list is mutated as necessary. 894Value *Reassociate::OptimizeAdd(Instruction *I, 895 SmallVectorImpl<ValueEntry> &Ops) { 896 // Scan the operand lists looking for X and -X pairs. If we find any, we 897 // can simplify the expression. X+-X == 0. While we're at it, scan for any 898 // duplicates. We want to canonicalize Y+Y+Y+Z -> 3*Y+Z. 899 // 900 // TODO: We could handle "X + ~X" -> "-1" if we wanted, since "-X = ~X+1". 901 // 902 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 903 Value *TheOp = Ops[i].Op; 904 // Check to see if we've seen this operand before. If so, we factor all 905 // instances of the operand together. Due to our sorting criteria, we know 906 // that these need to be next to each other in the vector. 907 if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) { 908 // Rescan the list, remove all instances of this operand from the expr. 909 unsigned NumFound = 0; 910 do { 911 Ops.erase(Ops.begin()+i); 912 ++NumFound; 913 } while (i != Ops.size() && Ops[i].Op == TheOp); 914 915 DEBUG(errs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n'); 916 ++NumFactor; 917 918 // Insert a new multiply. 919 Value *Mul = ConstantInt::get(cast<IntegerType>(I->getType()), NumFound); 920 Mul = BinaryOperator::CreateMul(TheOp, Mul, "factor", I); 921 922 // Now that we have inserted a multiply, optimize it. This allows us to 923 // handle cases that require multiple factoring steps, such as this: 924 // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6 925 RedoInsts.insert(cast<Instruction>(Mul)); 926 927 // If every add operand was a duplicate, return the multiply. 928 if (Ops.empty()) 929 return Mul; 930 931 // Otherwise, we had some input that didn't have the dupe, such as 932 // "A + A + B" -> "A*2 + B". Add the new multiply to the list of 933 // things being added by this operation. 934 Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul)); 935 936 --i; 937 e = Ops.size(); 938 continue; 939 } 940 941 // Check for X and -X in the operand list. 942 if (!BinaryOperator::isNeg(TheOp)) 943 continue; 944 945 Value *X = BinaryOperator::getNegArgument(TheOp); 946 unsigned FoundX = FindInOperandList(Ops, i, X); 947 if (FoundX == i) 948 continue; 949 950 // Remove X and -X from the operand list. 951 if (Ops.size() == 2) 952 return Constant::getNullValue(X->getType()); 953 954 Ops.erase(Ops.begin()+i); 955 if (i < FoundX) 956 --FoundX; 957 else 958 --i; // Need to back up an extra one. 959 Ops.erase(Ops.begin()+FoundX); 960 ++NumAnnihil; 961 --i; // Revisit element. 962 e -= 2; // Removed two elements. 963 } 964 965 // Scan the operand list, checking to see if there are any common factors 966 // between operands. Consider something like A*A+A*B*C+D. We would like to 967 // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies. 968 // To efficiently find this, we count the number of times a factor occurs 969 // for any ADD operands that are MULs. 970 DenseMap<Value*, unsigned> FactorOccurrences; 971 972 // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4) 973 // where they are actually the same multiply. 974 unsigned MaxOcc = 0; 975 Value *MaxOccVal = 0; 976 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 977 BinaryOperator *BOp = isReassociableOp(Ops[i].Op, Instruction::Mul); 978 if (!BOp) 979 continue; 980 981 // Compute all of the factors of this added value. 982 SmallVector<Value*, 8> Factors; 983 FindSingleUseMultiplyFactors(BOp, Factors, Ops); 984 assert(Factors.size() > 1 && "Bad linearize!"); 985 986 // Add one to FactorOccurrences for each unique factor in this op. 987 SmallPtrSet<Value*, 8> Duplicates; 988 for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 989 Value *Factor = Factors[i]; 990 if (!Duplicates.insert(Factor)) continue; 991 992 unsigned Occ = ++FactorOccurrences[Factor]; 993 if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } 994 995 // If Factor is a negative constant, add the negated value as a factor 996 // because we can percolate the negate out. Watch for minint, which 997 // cannot be positivified. 998 if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) 999 if (CI->isNegative() && !CI->isMinValue(true)) { 1000 Factor = ConstantInt::get(CI->getContext(), -CI->getValue()); 1001 assert(!Duplicates.count(Factor) && 1002 "Shouldn't have two constant factors, missed a canonicalize"); 1003 1004 unsigned Occ = ++FactorOccurrences[Factor]; 1005 if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } 1006 } 1007 } 1008 } 1009 1010 // If any factor occurred more than one time, we can pull it out. 1011 if (MaxOcc > 1) { 1012 DEBUG(errs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n'); 1013 ++NumFactor; 1014 1015 // Create a new instruction that uses the MaxOccVal twice. If we don't do 1016 // this, we could otherwise run into situations where removing a factor 1017 // from an expression will drop a use of maxocc, and this can cause 1018 // RemoveFactorFromExpression on successive values to behave differently. 1019 Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal); 1020 SmallVector<WeakVH, 4> NewMulOps; 1021 for (unsigned i = 0; i != Ops.size(); ++i) { 1022 // Only try to remove factors from expressions we're allowed to. 1023 BinaryOperator *BOp = isReassociableOp(Ops[i].Op, Instruction::Mul); 1024 if (!BOp) 1025 continue; 1026 1027 if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { 1028 // The factorized operand may occur several times. Convert them all in 1029 // one fell swoop. 1030 for (unsigned j = Ops.size(); j != i;) { 1031 --j; 1032 if (Ops[j].Op == Ops[i].Op) { 1033 NewMulOps.push_back(V); 1034 Ops.erase(Ops.begin()+j); 1035 } 1036 } 1037 --i; 1038 } 1039 } 1040 1041 // No need for extra uses anymore. 1042 delete DummyInst; 1043 1044 unsigned NumAddedValues = NewMulOps.size(); 1045 Value *V = EmitAddTreeOfValues(I, NewMulOps); 1046 1047 // Now that we have inserted the add tree, optimize it. This allows us to 1048 // handle cases that require multiple factoring steps, such as this: 1049 // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C)) 1050 assert(NumAddedValues > 1 && "Each occurrence should contribute a value"); 1051 (void)NumAddedValues; 1052 if (Instruction *VI = dyn_cast<Instruction>(V)) 1053 RedoInsts.insert(VI); 1054 1055 // Create the multiply. 1056 Instruction *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I); 1057 1058 // Rerun associate on the multiply in case the inner expression turned into 1059 // a multiply. We want to make sure that we keep things in canonical form. 1060 RedoInsts.insert(V2); 1061 1062 // If every add operand included the factor (e.g. "A*B + A*C"), then the 1063 // entire result expression is just the multiply "A*(B+C)". 1064 if (Ops.empty()) 1065 return V2; 1066 1067 // Otherwise, we had some input that didn't have the factor, such as 1068 // "A*B + A*C + D" -> "A*(B+C) + D". Add the new multiply to the list of 1069 // things being added by this operation. 1070 Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); 1071 } 1072 1073 return 0; 1074} 1075 1076namespace { 1077 /// \brief Predicate tests whether a ValueEntry's op is in a map. 1078 struct IsValueInMap { 1079 const DenseMap<Value *, unsigned> ⤅ 1080 1081 IsValueInMap(const DenseMap<Value *, unsigned> &Map) : Map(Map) {} 1082 1083 bool operator()(const ValueEntry &Entry) { 1084 return Map.find(Entry.Op) != Map.end(); 1085 } 1086 }; 1087} 1088 1089/// \brief Build up a vector of value/power pairs factoring a product. 1090/// 1091/// Given a series of multiplication operands, build a vector of factors and 1092/// the powers each is raised to when forming the final product. Sort them in 1093/// the order of descending power. 1094/// 1095/// (x*x) -> [(x, 2)] 1096/// ((x*x)*x) -> [(x, 3)] 1097/// ((((x*y)*x)*y)*x) -> [(x, 3), (y, 2)] 1098/// 1099/// \returns Whether any factors have a power greater than one. 1100bool Reassociate::collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops, 1101 SmallVectorImpl<Factor> &Factors) { 1102 // FIXME: Have Ops be (ValueEntry, Multiplicity) pairs, simplifying this. 1103 // Compute the sum of powers of simplifiable factors. 1104 unsigned FactorPowerSum = 0; 1105 for (unsigned Idx = 1, Size = Ops.size(); Idx < Size; ++Idx) { 1106 Value *Op = Ops[Idx-1].Op; 1107 1108 // Count the number of occurrences of this value. 1109 unsigned Count = 1; 1110 for (; Idx < Size && Ops[Idx].Op == Op; ++Idx) 1111 ++Count; 1112 // Track for simplification all factors which occur 2 or more times. 1113 if (Count > 1) 1114 FactorPowerSum += Count; 1115 } 1116 1117 // We can only simplify factors if the sum of the powers of our simplifiable 1118 // factors is 4 or higher. When that is the case, we will *always* have 1119 // a simplification. This is an important invariant to prevent cyclicly 1120 // trying to simplify already minimal formations. 1121 if (FactorPowerSum < 4) 1122 return false; 1123 1124 // Now gather the simplifiable factors, removing them from Ops. 1125 FactorPowerSum = 0; 1126 for (unsigned Idx = 1; Idx < Ops.size(); ++Idx) { 1127 Value *Op = Ops[Idx-1].Op; 1128 1129 // Count the number of occurrences of this value. 1130 unsigned Count = 1; 1131 for (; Idx < Ops.size() && Ops[Idx].Op == Op; ++Idx) 1132 ++Count; 1133 if (Count == 1) 1134 continue; 1135 // Move an even number of occurrences to Factors. 1136 Count &= ~1U; 1137 Idx -= Count; 1138 FactorPowerSum += Count; 1139 Factors.push_back(Factor(Op, Count)); 1140 Ops.erase(Ops.begin()+Idx, Ops.begin()+Idx+Count); 1141 } 1142 1143 // None of the adjustments above should have reduced the sum of factor powers 1144 // below our mininum of '4'. 1145 assert(FactorPowerSum >= 4); 1146 1147 std::sort(Factors.begin(), Factors.end(), Factor::PowerDescendingSorter()); 1148 return true; 1149} 1150 1151/// \brief Build a tree of multiplies, computing the product of Ops. 1152static Value *buildMultiplyTree(IRBuilder<> &Builder, 1153 SmallVectorImpl<Value*> &Ops) { 1154 if (Ops.size() == 1) 1155 return Ops.back(); 1156 1157 Value *LHS = Ops.pop_back_val(); 1158 do { 1159 LHS = Builder.CreateMul(LHS, Ops.pop_back_val()); 1160 } while (!Ops.empty()); 1161 1162 return LHS; 1163} 1164 1165/// \brief Build a minimal multiplication DAG for (a^x)*(b^y)*(c^z)*... 1166/// 1167/// Given a vector of values raised to various powers, where no two values are 1168/// equal and the powers are sorted in decreasing order, compute the minimal 1169/// DAG of multiplies to compute the final product, and return that product 1170/// value. 1171Value *Reassociate::buildMinimalMultiplyDAG(IRBuilder<> &Builder, 1172 SmallVectorImpl<Factor> &Factors) { 1173 assert(Factors[0].Power); 1174 SmallVector<Value *, 4> OuterProduct; 1175 for (unsigned LastIdx = 0, Idx = 1, Size = Factors.size(); 1176 Idx < Size && Factors[Idx].Power > 0; ++Idx) { 1177 if (Factors[Idx].Power != Factors[LastIdx].Power) { 1178 LastIdx = Idx; 1179 continue; 1180 } 1181 1182 // We want to multiply across all the factors with the same power so that 1183 // we can raise them to that power as a single entity. Build a mini tree 1184 // for that. 1185 SmallVector<Value *, 4> InnerProduct; 1186 InnerProduct.push_back(Factors[LastIdx].Base); 1187 do { 1188 InnerProduct.push_back(Factors[Idx].Base); 1189 ++Idx; 1190 } while (Idx < Size && Factors[Idx].Power == Factors[LastIdx].Power); 1191 1192 // Reset the base value of the first factor to the new expression tree. 1193 // We'll remove all the factors with the same power in a second pass. 1194 Value *M = Factors[LastIdx].Base = buildMultiplyTree(Builder, InnerProduct); 1195 if (Instruction *MI = dyn_cast<Instruction>(M)) 1196 RedoInsts.insert(MI); 1197 1198 LastIdx = Idx; 1199 } 1200 // Unique factors with equal powers -- we've folded them into the first one's 1201 // base. 1202 Factors.erase(std::unique(Factors.begin(), Factors.end(), 1203 Factor::PowerEqual()), 1204 Factors.end()); 1205 1206 // Iteratively collect the base of each factor with an add power into the 1207 // outer product, and halve each power in preparation for squaring the 1208 // expression. 1209 for (unsigned Idx = 0, Size = Factors.size(); Idx != Size; ++Idx) { 1210 if (Factors[Idx].Power & 1) 1211 OuterProduct.push_back(Factors[Idx].Base); 1212 Factors[Idx].Power >>= 1; 1213 } 1214 if (Factors[0].Power) { 1215 Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors); 1216 OuterProduct.push_back(SquareRoot); 1217 OuterProduct.push_back(SquareRoot); 1218 } 1219 if (OuterProduct.size() == 1) 1220 return OuterProduct.front(); 1221 1222 Value *V = buildMultiplyTree(Builder, OuterProduct); 1223 return V; 1224} 1225 1226Value *Reassociate::OptimizeMul(BinaryOperator *I, 1227 SmallVectorImpl<ValueEntry> &Ops) { 1228 // We can only optimize the multiplies when there is a chain of more than 1229 // three, such that a balanced tree might require fewer total multiplies. 1230 if (Ops.size() < 4) 1231 return 0; 1232 1233 // Try to turn linear trees of multiplies without other uses of the 1234 // intermediate stages into minimal multiply DAGs with perfect sub-expression 1235 // re-use. 1236 SmallVector<Factor, 4> Factors; 1237 if (!collectMultiplyFactors(Ops, Factors)) 1238 return 0; // All distinct factors, so nothing left for us to do. 1239 1240 IRBuilder<> Builder(I); 1241 Value *V = buildMinimalMultiplyDAG(Builder, Factors); 1242 if (Ops.empty()) 1243 return V; 1244 1245 ValueEntry NewEntry = ValueEntry(getRank(V), V); 1246 Ops.insert(std::lower_bound(Ops.begin(), Ops.end(), NewEntry), NewEntry); 1247 return 0; 1248} 1249 1250Value *Reassociate::OptimizeExpression(BinaryOperator *I, 1251 SmallVectorImpl<ValueEntry> &Ops) { 1252 // Now that we have the linearized expression tree, try to optimize it. 1253 // Start by folding any constants that we found. 1254 if (Ops.size() == 1) return Ops[0].Op; 1255 1256 unsigned Opcode = I->getOpcode(); 1257 1258 if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 1259 if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 1260 Ops.pop_back(); 1261 Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 1262 return OptimizeExpression(I, Ops); 1263 } 1264 1265 // Check for destructive annihilation due to a constant being used. 1266 if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op)) 1267 switch (Opcode) { 1268 default: break; 1269 case Instruction::And: 1270 if (CstVal->isZero()) // X & 0 -> 0 1271 return CstVal; 1272 if (CstVal->isAllOnesValue()) // X & -1 -> X 1273 Ops.pop_back(); 1274 break; 1275 case Instruction::Mul: 1276 if (CstVal->isZero()) { // X * 0 -> 0 1277 ++NumAnnihil; 1278 return CstVal; 1279 } 1280 1281 if (cast<ConstantInt>(CstVal)->isOne()) 1282 Ops.pop_back(); // X * 1 -> X 1283 break; 1284 case Instruction::Or: 1285 if (CstVal->isAllOnesValue()) // X | -1 -> -1 1286 return CstVal; 1287 // FALLTHROUGH! 1288 case Instruction::Add: 1289 case Instruction::Xor: 1290 if (CstVal->isZero()) // X [|^+] 0 -> X 1291 Ops.pop_back(); 1292 break; 1293 } 1294 if (Ops.size() == 1) return Ops[0].Op; 1295 1296 // Handle destructive annihilation due to identities between elements in the 1297 // argument list here. 1298 unsigned NumOps = Ops.size(); 1299 switch (Opcode) { 1300 default: break; 1301 case Instruction::And: 1302 case Instruction::Or: 1303 case Instruction::Xor: 1304 if (Value *Result = OptimizeAndOrXor(Opcode, Ops)) 1305 return Result; 1306 break; 1307 1308 case Instruction::Add: 1309 if (Value *Result = OptimizeAdd(I, Ops)) 1310 return Result; 1311 break; 1312 1313 case Instruction::Mul: 1314 if (Value *Result = OptimizeMul(I, Ops)) 1315 return Result; 1316 break; 1317 } 1318 1319 if (Ops.size() != NumOps) 1320 return OptimizeExpression(I, Ops); 1321 return 0; 1322} 1323 1324/// EraseInst - Zap the given instruction, adding interesting operands to the 1325/// work list. 1326void Reassociate::EraseInst(Instruction *I) { 1327 assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!"); 1328 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 1329 // Erase the dead instruction. 1330 ValueRankMap.erase(I); 1331 I->eraseFromParent(); 1332 // Optimize its operands. 1333 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 1334 if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) { 1335 // If this is a node in an expression tree, climb to the expression root 1336 // and add that since that's where optimization actually happens. 1337 unsigned Opcode = Op->getOpcode(); 1338 while (Op->hasOneUse() && Op->use_back()->getOpcode() == Opcode) 1339 Op = Op->use_back(); 1340 RedoInsts.insert(Op); 1341 } 1342} 1343 1344/// OptimizeInst - Inspect and optimize the given instruction. Note that erasing 1345/// instructions is not allowed. 1346void Reassociate::OptimizeInst(Instruction *I) { 1347 // Only consider operations that we understand. 1348 if (!isa<BinaryOperator>(I)) 1349 return; 1350 1351 if (I->getOpcode() == Instruction::Shl && 1352 isa<ConstantInt>(I->getOperand(1))) 1353 // If an operand of this shift is a reassociable multiply, or if the shift 1354 // is used by a reassociable multiply or add, turn into a multiply. 1355 if (isReassociableOp(I->getOperand(0), Instruction::Mul) || 1356 (I->hasOneUse() && 1357 (isReassociableOp(I->use_back(), Instruction::Mul) || 1358 isReassociableOp(I->use_back(), Instruction::Add)))) { 1359 Instruction *NI = ConvertShiftToMul(I); 1360 RedoInsts.insert(I); 1361 MadeChange = true; 1362 I = NI; 1363 } 1364 1365 // Floating point binary operators are not associative, but we can still 1366 // commute (some) of them, to canonicalize the order of their operands. 1367 // This can potentially expose more CSE opportunities, and makes writing 1368 // other transformations simpler. 1369 if ((I->getType()->isFloatingPointTy() || I->getType()->isVectorTy())) { 1370 // FAdd and FMul can be commuted. 1371 if (I->getOpcode() != Instruction::FMul && 1372 I->getOpcode() != Instruction::FAdd) 1373 return; 1374 1375 Value *LHS = I->getOperand(0); 1376 Value *RHS = I->getOperand(1); 1377 unsigned LHSRank = getRank(LHS); 1378 unsigned RHSRank = getRank(RHS); 1379 1380 // Sort the operands by rank. 1381 if (RHSRank < LHSRank) { 1382 I->setOperand(0, RHS); 1383 I->setOperand(1, LHS); 1384 } 1385 1386 return; 1387 } 1388 1389 // Do not reassociate boolean (i1) expressions. We want to preserve the 1390 // original order of evaluation for short-circuited comparisons that 1391 // SimplifyCFG has folded to AND/OR expressions. If the expression 1392 // is not further optimized, it is likely to be transformed back to a 1393 // short-circuited form for code gen, and the source order may have been 1394 // optimized for the most likely conditions. 1395 if (I->getType()->isIntegerTy(1)) 1396 return; 1397 1398 // If this is a subtract instruction which is not already in negate form, 1399 // see if we can convert it to X+-Y. 1400 if (I->getOpcode() == Instruction::Sub) { 1401 if (ShouldBreakUpSubtract(I)) { 1402 Instruction *NI = BreakUpSubtract(I); 1403 RedoInsts.insert(I); 1404 MadeChange = true; 1405 I = NI; 1406 } else if (BinaryOperator::isNeg(I)) { 1407 // Otherwise, this is a negation. See if the operand is a multiply tree 1408 // and if this is not an inner node of a multiply tree. 1409 if (isReassociableOp(I->getOperand(1), Instruction::Mul) && 1410 (!I->hasOneUse() || 1411 !isReassociableOp(I->use_back(), Instruction::Mul))) { 1412 Instruction *NI = LowerNegateToMultiply(I); 1413 RedoInsts.insert(I); 1414 MadeChange = true; 1415 I = NI; 1416 } 1417 } 1418 } 1419 1420 // If this instruction is an associative binary operator, process it. 1421 if (!I->isAssociative()) return; 1422 BinaryOperator *BO = cast<BinaryOperator>(I); 1423 1424 // If this is an interior node of a reassociable tree, ignore it until we 1425 // get to the root of the tree, to avoid N^2 analysis. 1426 if (BO->hasOneUse() && BO->use_back()->getOpcode() == BO->getOpcode()) 1427 return; 1428 1429 // If this is an add tree that is used by a sub instruction, ignore it 1430 // until we process the subtract. 1431 if (BO->hasOneUse() && BO->getOpcode() == Instruction::Add && 1432 cast<Instruction>(BO->use_back())->getOpcode() == Instruction::Sub) 1433 return; 1434 1435 ReassociateExpression(BO); 1436} 1437 1438Value *Reassociate::ReassociateExpression(BinaryOperator *I) { 1439 1440 // First, walk the expression tree, linearizing the tree, collecting the 1441 // operand information. 1442 SmallVector<ValueEntry, 8> Ops; 1443 LinearizeExprTree(I, Ops); 1444 1445 DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n'); 1446 1447 // Now that we have linearized the tree to a list and have gathered all of 1448 // the operands and their ranks, sort the operands by their rank. Use a 1449 // stable_sort so that values with equal ranks will have their relative 1450 // positions maintained (and so the compiler is deterministic). Note that 1451 // this sorts so that the highest ranking values end up at the beginning of 1452 // the vector. 1453 std::stable_sort(Ops.begin(), Ops.end()); 1454 1455 // OptimizeExpression - Now that we have the expression tree in a convenient 1456 // sorted form, optimize it globally if possible. 1457 if (Value *V = OptimizeExpression(I, Ops)) { 1458 // This expression tree simplified to something that isn't a tree, 1459 // eliminate it. 1460 DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n'); 1461 I->replaceAllUsesWith(V); 1462 if (Instruction *VI = dyn_cast<Instruction>(V)) 1463 VI->setDebugLoc(I->getDebugLoc()); 1464 RedoInsts.insert(I); 1465 ++NumAnnihil; 1466 return V; 1467 } 1468 1469 // We want to sink immediates as deeply as possible except in the case where 1470 // this is a multiply tree used only by an add, and the immediate is a -1. 1471 // In this case we reassociate to put the negation on the outside so that we 1472 // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y 1473 if (I->getOpcode() == Instruction::Mul && I->hasOneUse() && 1474 cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add && 1475 isa<ConstantInt>(Ops.back().Op) && 1476 cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) { 1477 ValueEntry Tmp = Ops.pop_back_val(); 1478 Ops.insert(Ops.begin(), Tmp); 1479 } 1480 1481 DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n'); 1482 1483 if (Ops.size() == 1) { 1484 // This expression tree simplified to something that isn't a tree, 1485 // eliminate it. 1486 I->replaceAllUsesWith(Ops[0].Op); 1487 if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op)) 1488 OI->setDebugLoc(I->getDebugLoc()); 1489 RedoInsts.insert(I); 1490 return Ops[0].Op; 1491 } 1492 1493 // Now that we ordered and optimized the expressions, splat them back into 1494 // the expression tree, removing any unneeded nodes. 1495 RewriteExprTree(I, Ops); 1496 return I; 1497} 1498 1499bool Reassociate::runOnFunction(Function &F) { 1500 // Calculate the rank map for F 1501 BuildRankMap(F); 1502 1503 MadeChange = false; 1504 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { 1505 // Optimize every instruction in the basic block. 1506 for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; ) 1507 if (isInstructionTriviallyDead(II)) { 1508 EraseInst(II++); 1509 } else { 1510 OptimizeInst(II); 1511 assert(II->getParent() == BI && "Moved to a different block!"); 1512 ++II; 1513 } 1514 1515 // If this produced extra instructions to optimize, handle them now. 1516 while (!RedoInsts.empty()) { 1517 Instruction *I = RedoInsts.pop_back_val(); 1518 if (isInstructionTriviallyDead(I)) 1519 EraseInst(I); 1520 else 1521 OptimizeInst(I); 1522 } 1523 } 1524 1525 // We are done with the rank map. 1526 RankMap.clear(); 1527 ValueRankMap.clear(); 1528 1529 return MadeChange; 1530} 1531