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