Reassociate.cpp revision 59500c8f9a76b3386329b6f837255c16f4e8b61b
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... 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/Constants.h" 26#include "llvm/DerivedTypes.h" 27#include "llvm/Function.h" 28#include "llvm/Instructions.h" 29#include "llvm/Pass.h" 30#include "llvm/Assembly/Writer.h" 31#include "llvm/Support/CFG.h" 32#include "llvm/Support/Compiler.h" 33#include "llvm/Support/Debug.h" 34#include "llvm/ADT/PostOrderIterator.h" 35#include "llvm/ADT/Statistic.h" 36#include <algorithm> 37#include <map> 38using namespace llvm; 39 40STATISTIC(NumLinear , "Number of insts linearized"); 41STATISTIC(NumChanged, "Number of insts reassociated"); 42STATISTIC(NumAnnihil, "Number of expr tree annihilated"); 43STATISTIC(NumFactor , "Number of multiplies factored"); 44 45namespace { 46 struct VISIBILITY_HIDDEN ValueEntry { 47 unsigned Rank; 48 Value *Op; 49 ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 50 }; 51 inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 52 return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 53 } 54} 55 56#ifndef DEBUG 57/// PrintOps - Print out the expression identified in the Ops list. 58/// 59static void PrintOps(Instruction *I, const std::vector<ValueEntry> &Ops) { 60 Module *M = I->getParent()->getParent()->getParent(); 61 cerr << Instruction::getOpcodeName(I->getOpcode()) << " " 62 << *Ops[0].Op->getType(); 63 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 64 WriteAsOperand(*cerr.stream() << " ", Ops[i].Op, false, M); 65 cerr << "," << Ops[i].Rank; 66 } 67} 68#endif 69 70namespace { 71 class VISIBILITY_HIDDEN Reassociate : public FunctionPass { 72 std::map<BasicBlock*, unsigned> RankMap; 73 std::map<Value*, unsigned> ValueRankMap; 74 bool MadeChange; 75 public: 76 static char ID; // Pass identification, replacement for typeid 77 Reassociate() : FunctionPass(&ID) {} 78 79 bool runOnFunction(Function &F); 80 81 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 82 AU.setPreservesCFG(); 83 } 84 private: 85 void BuildRankMap(Function &F); 86 unsigned getRank(Value *V); 87 void ReassociateExpression(BinaryOperator *I); 88 void RewriteExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops, 89 unsigned Idx = 0); 90 Value *OptimizeExpression(BinaryOperator *I, std::vector<ValueEntry> &Ops); 91 void LinearizeExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops); 92 void LinearizeExpr(BinaryOperator *I); 93 Value *RemoveFactorFromExpression(Value *V, Value *Factor); 94 void ReassociateBB(BasicBlock *BB); 95 96 void RemoveDeadBinaryOp(Value *V); 97 }; 98} 99 100char Reassociate::ID = 0; 101static RegisterPass<Reassociate> X("reassociate", "Reassociate expressions"); 102 103// Public interface to the Reassociate pass 104FunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 105 106void Reassociate::RemoveDeadBinaryOp(Value *V) { 107 Instruction *Op = dyn_cast<Instruction>(V); 108 if (!Op || !isa<BinaryOperator>(Op) || !isa<CmpInst>(Op) || !Op->use_empty()) 109 return; 110 111 Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1); 112 RemoveDeadBinaryOp(LHS); 113 RemoveDeadBinaryOp(RHS); 114} 115 116 117static bool isUnmovableInstruction(Instruction *I) { 118 if (I->getOpcode() == Instruction::PHI || 119 I->getOpcode() == Instruction::Alloca || 120 I->getOpcode() == Instruction::Load || 121 I->getOpcode() == Instruction::Malloc || 122 I->getOpcode() == Instruction::Invoke || 123 I->getOpcode() == Instruction::Call || 124 I->getOpcode() == Instruction::UDiv || 125 I->getOpcode() == Instruction::SDiv || 126 I->getOpcode() == Instruction::FDiv || 127 I->getOpcode() == Instruction::URem || 128 I->getOpcode() == Instruction::SRem || 129 I->getOpcode() == Instruction::FRem) 130 return true; 131 return false; 132} 133 134void Reassociate::BuildRankMap(Function &F) { 135 unsigned i = 2; 136 137 // Assign distinct ranks to function arguments 138 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 139 ValueRankMap[I] = ++i; 140 141 ReversePostOrderTraversal<Function*> RPOT(&F); 142 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 143 E = RPOT.end(); I != E; ++I) { 144 BasicBlock *BB = *I; 145 unsigned BBRank = RankMap[BB] = ++i << 16; 146 147 // Walk the basic block, adding precomputed ranks for any instructions that 148 // we cannot move. This ensures that the ranks for these instructions are 149 // all different in the block. 150 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 151 if (isUnmovableInstruction(I)) 152 ValueRankMap[I] = ++BBRank; 153 } 154} 155 156unsigned Reassociate::getRank(Value *V) { 157 if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument... 158 159 Instruction *I = dyn_cast<Instruction>(V); 160 if (I == 0) return 0; // Otherwise it's a global or constant, rank 0. 161 162 unsigned &CachedRank = ValueRankMap[I]; 163 if (CachedRank) return CachedRank; // Rank already known? 164 165 // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 166 // we can reassociate expressions for code motion! Since we do not recurse 167 // for PHI nodes, we cannot have infinite recursion here, because there 168 // cannot be loops in the value graph that do not go through PHI nodes. 169 unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 170 for (unsigned i = 0, e = I->getNumOperands(); 171 i != e && Rank != MaxRank; ++i) 172 Rank = std::max(Rank, getRank(I->getOperand(i))); 173 174 // If this is a not or neg instruction, do not count it for rank. This 175 // assures us that X and ~X will have the same rank. 176 if (!I->getType()->isInteger() || 177 (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 178 ++Rank; 179 180 //DOUT << "Calculated Rank[" << V->getName() << "] = " 181 // << Rank << "\n"; 182 183 return CachedRank = Rank; 184} 185 186/// isReassociableOp - Return true if V is an instruction of the specified 187/// opcode and if it only has one use. 188static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 189 if ((V->hasOneUse() || V->use_empty()) && isa<Instruction>(V) && 190 cast<Instruction>(V)->getOpcode() == Opcode) 191 return cast<BinaryOperator>(V); 192 return 0; 193} 194 195/// LowerNegateToMultiply - Replace 0-X with X*-1. 196/// 197static Instruction *LowerNegateToMultiply(Instruction *Neg) { 198 Constant *Cst = ConstantInt::getAllOnesValue(Neg->getType()); 199 200 Instruction *Res = BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg); 201 Res->takeName(Neg); 202 Neg->replaceAllUsesWith(Res); 203 Neg->eraseFromParent(); 204 return Res; 205} 206 207// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. 208// Note that if D is also part of the expression tree that we recurse to 209// linearize it as well. Besides that case, this does not recurse into A,B, or 210// C. 211void Reassociate::LinearizeExpr(BinaryOperator *I) { 212 BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 213 BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1)); 214 assert(isReassociableOp(LHS, I->getOpcode()) && 215 isReassociableOp(RHS, I->getOpcode()) && 216 "Not an expression that needs linearization?"); 217 218 DOUT << "Linear" << *LHS << *RHS << *I; 219 220 // Move the RHS instruction to live immediately before I, avoiding breaking 221 // dominator properties. 222 RHS->moveBefore(I); 223 224 // Move operands around to do the linearization. 225 I->setOperand(1, RHS->getOperand(0)); 226 RHS->setOperand(0, LHS); 227 I->setOperand(0, RHS); 228 229 ++NumLinear; 230 MadeChange = true; 231 DOUT << "Linearized: " << *I; 232 233 // If D is part of this expression tree, tail recurse. 234 if (isReassociableOp(I->getOperand(1), I->getOpcode())) 235 LinearizeExpr(I); 236} 237 238 239/// LinearizeExprTree - Given an associative binary expression tree, traverse 240/// all of the uses putting it into canonical form. This forces a left-linear 241/// form of the the expression (((a+b)+c)+d), and collects information about the 242/// rank of the non-tree operands. 243/// 244/// NOTE: These intentionally destroys the expression tree operands (turning 245/// them into undef values) to reduce #uses of the values. This means that the 246/// caller MUST use something like RewriteExprTree to put the values back in. 247/// 248void Reassociate::LinearizeExprTree(BinaryOperator *I, 249 std::vector<ValueEntry> &Ops) { 250 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); 251 unsigned Opcode = I->getOpcode(); 252 253 // First step, linearize the expression if it is in ((A+B)+(C+D)) form. 254 BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); 255 BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); 256 257 // If this is a multiply expression tree and it contains internal negations, 258 // transform them into multiplies by -1 so they can be reassociated. 259 if (I->getOpcode() == Instruction::Mul) { 260 if (!LHSBO && LHS->hasOneUse() && BinaryOperator::isNeg(LHS)) { 261 LHS = LowerNegateToMultiply(cast<Instruction>(LHS)); 262 LHSBO = isReassociableOp(LHS, Opcode); 263 } 264 if (!RHSBO && RHS->hasOneUse() && BinaryOperator::isNeg(RHS)) { 265 RHS = LowerNegateToMultiply(cast<Instruction>(RHS)); 266 RHSBO = isReassociableOp(RHS, Opcode); 267 } 268 } 269 270 if (!LHSBO) { 271 if (!RHSBO) { 272 // Neither the LHS or RHS as part of the tree, thus this is a leaf. As 273 // such, just remember these operands and their rank. 274 Ops.push_back(ValueEntry(getRank(LHS), LHS)); 275 Ops.push_back(ValueEntry(getRank(RHS), RHS)); 276 277 // Clear the leaves out. 278 I->setOperand(0, UndefValue::get(I->getType())); 279 I->setOperand(1, UndefValue::get(I->getType())); 280 return; 281 } else { 282 // Turn X+(Y+Z) -> (Y+Z)+X 283 std::swap(LHSBO, RHSBO); 284 std::swap(LHS, RHS); 285 bool Success = !I->swapOperands(); 286 assert(Success && "swapOperands failed"); 287 Success = false; 288 MadeChange = true; 289 } 290 } else if (RHSBO) { 291 // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the the RHS is not 292 // part of the expression tree. 293 LinearizeExpr(I); 294 LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0)); 295 RHS = I->getOperand(1); 296 RHSBO = 0; 297 } 298 299 // Okay, now we know that the LHS is a nested expression and that the RHS is 300 // not. Perform reassociation. 301 assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); 302 303 // Move LHS right before I to make sure that the tree expression dominates all 304 // values. 305 LHSBO->moveBefore(I); 306 307 // Linearize the expression tree on the LHS. 308 LinearizeExprTree(LHSBO, Ops); 309 310 // Remember the RHS operand and its rank. 311 Ops.push_back(ValueEntry(getRank(RHS), RHS)); 312 313 // Clear the RHS leaf out. 314 I->setOperand(1, UndefValue::get(I->getType())); 315} 316 317// RewriteExprTree - Now that the operands for this expression tree are 318// linearized and optimized, emit them in-order. This function is written to be 319// tail recursive. 320void Reassociate::RewriteExprTree(BinaryOperator *I, 321 std::vector<ValueEntry> &Ops, 322 unsigned i) { 323 if (i+2 == Ops.size()) { 324 if (I->getOperand(0) != Ops[i].Op || 325 I->getOperand(1) != Ops[i+1].Op) { 326 Value *OldLHS = I->getOperand(0); 327 DOUT << "RA: " << *I; 328 I->setOperand(0, Ops[i].Op); 329 I->setOperand(1, Ops[i+1].Op); 330 DOUT << "TO: " << *I; 331 MadeChange = true; 332 ++NumChanged; 333 334 // If we reassociated a tree to fewer operands (e.g. (1+a+2) -> (a+3) 335 // delete the extra, now dead, nodes. 336 RemoveDeadBinaryOp(OldLHS); 337 } 338 return; 339 } 340 assert(i+2 < Ops.size() && "Ops index out of range!"); 341 342 if (I->getOperand(1) != Ops[i].Op) { 343 DOUT << "RA: " << *I; 344 I->setOperand(1, Ops[i].Op); 345 DOUT << "TO: " << *I; 346 MadeChange = true; 347 ++NumChanged; 348 } 349 350 BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 351 assert(LHS->getOpcode() == I->getOpcode() && 352 "Improper expression tree!"); 353 354 // Compactify the tree instructions together with each other to guarantee 355 // that the expression tree is dominated by all of Ops. 356 LHS->moveBefore(I); 357 RewriteExprTree(LHS, Ops, i+1); 358} 359 360 361 362// NegateValue - Insert instructions before the instruction pointed to by BI, 363// that computes the negative version of the value specified. The negative 364// version of the value is returned, and BI is left pointing at the instruction 365// that should be processed next by the reassociation pass. 366// 367static Value *NegateValue(Value *V, Instruction *BI) { 368 // We are trying to expose opportunity for reassociation. One of the things 369 // that we want to do to achieve this is to push a negation as deep into an 370 // expression chain as possible, to expose the add instructions. In practice, 371 // this means that we turn this: 372 // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 373 // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 374 // the constants. We assume that instcombine will clean up the mess later if 375 // we introduce tons of unnecessary negation instructions... 376 // 377 if (Instruction *I = dyn_cast<Instruction>(V)) 378 if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 379 // Push the negates through the add. 380 I->setOperand(0, NegateValue(I->getOperand(0), BI)); 381 I->setOperand(1, NegateValue(I->getOperand(1), BI)); 382 383 // We must move the add instruction here, because the neg instructions do 384 // not dominate the old add instruction in general. By moving it, we are 385 // assured that the neg instructions we just inserted dominate the 386 // instruction we are about to insert after them. 387 // 388 I->moveBefore(BI); 389 I->setName(I->getName()+".neg"); 390 return I; 391 } 392 393 // Insert a 'neg' instruction that subtracts the value from zero to get the 394 // negation. 395 // 396 return BinaryOperator::CreateNeg(V, V->getName() + ".neg", BI); 397} 398 399/// ShouldBreakUpSubtract - Return true if we should break up this subtract of 400/// X-Y into (X + -Y). 401static bool ShouldBreakUpSubtract(Instruction *Sub) { 402 // If this is a negation, we can't split it up! 403 if (BinaryOperator::isNeg(Sub)) 404 return false; 405 406 // Don't bother to break this up unless either the LHS is an associable add or 407 // subtract or if this is only used by one. 408 if (isReassociableOp(Sub->getOperand(0), Instruction::Add) || 409 isReassociableOp(Sub->getOperand(0), Instruction::Sub)) 410 return true; 411 if (isReassociableOp(Sub->getOperand(1), Instruction::Add) || 412 isReassociableOp(Sub->getOperand(1), Instruction::Sub)) 413 return true; 414 if (Sub->hasOneUse() && 415 (isReassociableOp(Sub->use_back(), Instruction::Add) || 416 isReassociableOp(Sub->use_back(), Instruction::Sub))) 417 return true; 418 419 return false; 420} 421 422/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 423/// only used by an add, transform this into (X+(0-Y)) to promote better 424/// reassociation. 425static Instruction *BreakUpSubtract(Instruction *Sub) { 426 // Convert a subtract into an add and a neg instruction... so that sub 427 // instructions can be commuted with other add instructions... 428 // 429 // Calculate the negative value of Operand 1 of the sub instruction... 430 // and set it as the RHS of the add instruction we just made... 431 // 432 Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 433 Instruction *New = 434 BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub); 435 New->takeName(Sub); 436 437 // Everyone now refers to the add instruction. 438 Sub->replaceAllUsesWith(New); 439 Sub->eraseFromParent(); 440 441 DOUT << "Negated: " << *New; 442 return New; 443} 444 445/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 446/// by one, change this into a multiply by a constant to assist with further 447/// reassociation. 448static Instruction *ConvertShiftToMul(Instruction *Shl) { 449 // If an operand of this shift is a reassociable multiply, or if the shift 450 // is used by a reassociable multiply or add, turn into a multiply. 451 if (isReassociableOp(Shl->getOperand(0), Instruction::Mul) || 452 (Shl->hasOneUse() && 453 (isReassociableOp(Shl->use_back(), Instruction::Mul) || 454 isReassociableOp(Shl->use_back(), Instruction::Add)))) { 455 Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 456 MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 457 458 Instruction *Mul = BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, 459 "", Shl); 460 Mul->takeName(Shl); 461 Shl->replaceAllUsesWith(Mul); 462 Shl->eraseFromParent(); 463 return Mul; 464 } 465 return 0; 466} 467 468// Scan backwards and forwards among values with the same rank as element i to 469// see if X exists. If X does not exist, return i. 470static unsigned FindInOperandList(std::vector<ValueEntry> &Ops, unsigned i, 471 Value *X) { 472 unsigned XRank = Ops[i].Rank; 473 unsigned e = Ops.size(); 474 for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) 475 if (Ops[j].Op == X) 476 return j; 477 // Scan backwards 478 for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) 479 if (Ops[j].Op == X) 480 return j; 481 return i; 482} 483 484/// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together 485/// and returning the result. Insert the tree before I. 486static Value *EmitAddTreeOfValues(Instruction *I, std::vector<Value*> &Ops) { 487 if (Ops.size() == 1) return Ops.back(); 488 489 Value *V1 = Ops.back(); 490 Ops.pop_back(); 491 Value *V2 = EmitAddTreeOfValues(I, Ops); 492 return BinaryOperator::CreateAdd(V2, V1, "tmp", I); 493} 494 495/// RemoveFactorFromExpression - If V is an expression tree that is a 496/// multiplication sequence, and if this sequence contains a multiply by Factor, 497/// remove Factor from the tree and return the new tree. 498Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { 499 BinaryOperator *BO = isReassociableOp(V, Instruction::Mul); 500 if (!BO) return 0; 501 502 std::vector<ValueEntry> Factors; 503 LinearizeExprTree(BO, Factors); 504 505 bool FoundFactor = false; 506 for (unsigned i = 0, e = Factors.size(); i != e; ++i) 507 if (Factors[i].Op == Factor) { 508 FoundFactor = true; 509 Factors.erase(Factors.begin()+i); 510 break; 511 } 512 if (!FoundFactor) { 513 // Make sure to restore the operands to the expression tree. 514 RewriteExprTree(BO, Factors); 515 return 0; 516 } 517 518 if (Factors.size() == 1) return Factors[0].Op; 519 520 RewriteExprTree(BO, Factors); 521 return BO; 522} 523 524/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively 525/// add its operands as factors, otherwise add V to the list of factors. 526static void FindSingleUseMultiplyFactors(Value *V, 527 std::vector<Value*> &Factors) { 528 BinaryOperator *BO; 529 if ((!V->hasOneUse() && !V->use_empty()) || 530 !(BO = dyn_cast<BinaryOperator>(V)) || 531 BO->getOpcode() != Instruction::Mul) { 532 Factors.push_back(V); 533 return; 534 } 535 536 // Otherwise, add the LHS and RHS to the list of factors. 537 FindSingleUseMultiplyFactors(BO->getOperand(1), Factors); 538 FindSingleUseMultiplyFactors(BO->getOperand(0), Factors); 539} 540 541 542 543Value *Reassociate::OptimizeExpression(BinaryOperator *I, 544 std::vector<ValueEntry> &Ops) { 545 // Now that we have the linearized expression tree, try to optimize it. 546 // Start by folding any constants that we found. 547 bool IterateOptimization = false; 548 if (Ops.size() == 1) return Ops[0].Op; 549 550 unsigned Opcode = I->getOpcode(); 551 552 if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 553 if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 554 Ops.pop_back(); 555 Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 556 return OptimizeExpression(I, Ops); 557 } 558 559 // Check for destructive annihilation due to a constant being used. 560 if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op)) 561 switch (Opcode) { 562 default: break; 563 case Instruction::And: 564 if (CstVal->isZero()) { // ... & 0 -> 0 565 ++NumAnnihil; 566 return CstVal; 567 } else if (CstVal->isAllOnesValue()) { // ... & -1 -> ... 568 Ops.pop_back(); 569 } 570 break; 571 case Instruction::Mul: 572 if (CstVal->isZero()) { // ... * 0 -> 0 573 ++NumAnnihil; 574 return CstVal; 575 } else if (cast<ConstantInt>(CstVal)->isOne()) { 576 Ops.pop_back(); // ... * 1 -> ... 577 } 578 break; 579 case Instruction::Or: 580 if (CstVal->isAllOnesValue()) { // ... | -1 -> -1 581 ++NumAnnihil; 582 return CstVal; 583 } 584 // FALLTHROUGH! 585 case Instruction::Add: 586 case Instruction::Xor: 587 if (CstVal->isZero()) // ... [|^+] 0 -> ... 588 Ops.pop_back(); 589 break; 590 } 591 if (Ops.size() == 1) return Ops[0].Op; 592 593 // Handle destructive annihilation do to identities between elements in the 594 // argument list here. 595 switch (Opcode) { 596 default: break; 597 case Instruction::And: 598 case Instruction::Or: 599 case Instruction::Xor: 600 // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 601 // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 602 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 603 // First, check for X and ~X in the operand list. 604 assert(i < Ops.size()); 605 if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 606 Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 607 unsigned FoundX = FindInOperandList(Ops, i, X); 608 if (FoundX != i) { 609 if (Opcode == Instruction::And) { // ...&X&~X = 0 610 ++NumAnnihil; 611 return Constant::getNullValue(X->getType()); 612 } else if (Opcode == Instruction::Or) { // ...|X|~X = -1 613 ++NumAnnihil; 614 return ConstantInt::getAllOnesValue(X->getType()); 615 } 616 } 617 } 618 619 // Next, check for duplicate pairs of values, which we assume are next to 620 // each other, due to our sorting criteria. 621 assert(i < Ops.size()); 622 if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 623 if (Opcode == Instruction::And || Opcode == Instruction::Or) { 624 // Drop duplicate values. 625 Ops.erase(Ops.begin()+i); 626 --i; --e; 627 IterateOptimization = true; 628 ++NumAnnihil; 629 } else { 630 assert(Opcode == Instruction::Xor); 631 if (e == 2) { 632 ++NumAnnihil; 633 return Constant::getNullValue(Ops[0].Op->getType()); 634 } 635 // ... X^X -> ... 636 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 637 i -= 1; e -= 2; 638 IterateOptimization = true; 639 ++NumAnnihil; 640 } 641 } 642 } 643 break; 644 645 case Instruction::Add: 646 // Scan the operand lists looking for X and -X pairs. If we find any, we 647 // can simplify the expression. X+-X == 0. 648 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 649 assert(i < Ops.size()); 650 // Check for X and -X in the operand list. 651 if (BinaryOperator::isNeg(Ops[i].Op)) { 652 Value *X = BinaryOperator::getNegArgument(Ops[i].Op); 653 unsigned FoundX = FindInOperandList(Ops, i, X); 654 if (FoundX != i) { 655 // Remove X and -X from the operand list. 656 if (Ops.size() == 2) { 657 ++NumAnnihil; 658 return Constant::getNullValue(X->getType()); 659 } else { 660 Ops.erase(Ops.begin()+i); 661 if (i < FoundX) 662 --FoundX; 663 else 664 --i; // Need to back up an extra one. 665 Ops.erase(Ops.begin()+FoundX); 666 IterateOptimization = true; 667 ++NumAnnihil; 668 --i; // Revisit element. 669 e -= 2; // Removed two elements. 670 } 671 } 672 } 673 } 674 675 676 // Scan the operand list, checking to see if there are any common factors 677 // between operands. Consider something like A*A+A*B*C+D. We would like to 678 // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies. 679 // To efficiently find this, we count the number of times a factor occurs 680 // for any ADD operands that are MULs. 681 std::map<Value*, unsigned> FactorOccurrences; 682 unsigned MaxOcc = 0; 683 Value *MaxOccVal = 0; 684 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 685 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op)) { 686 if (BOp->getOpcode() == Instruction::Mul && BOp->use_empty()) { 687 // Compute all of the factors of this added value. 688 std::vector<Value*> Factors; 689 FindSingleUseMultiplyFactors(BOp, Factors); 690 assert(Factors.size() > 1 && "Bad linearize!"); 691 692 // Add one to FactorOccurrences for each unique factor in this op. 693 if (Factors.size() == 2) { 694 unsigned Occ = ++FactorOccurrences[Factors[0]]; 695 if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[0]; } 696 if (Factors[0] != Factors[1]) { // Don't double count A*A. 697 Occ = ++FactorOccurrences[Factors[1]]; 698 if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[1]; } 699 } 700 } else { 701 std::set<Value*> Duplicates; 702 for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 703 if (Duplicates.insert(Factors[i]).second) { 704 unsigned Occ = ++FactorOccurrences[Factors[i]]; 705 if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[i]; } 706 } 707 } 708 } 709 } 710 } 711 } 712 713 // If any factor occurred more than one time, we can pull it out. 714 if (MaxOcc > 1) { 715 DOUT << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << "\n"; 716 717 // Create a new instruction that uses the MaxOccVal twice. If we don't do 718 // this, we could otherwise run into situations where removing a factor 719 // from an expression will drop a use of maxocc, and this can cause 720 // RemoveFactorFromExpression on successive values to behave differently. 721 Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal); 722 std::vector<Value*> NewMulOps; 723 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 724 if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { 725 NewMulOps.push_back(V); 726 Ops.erase(Ops.begin()+i); 727 --i; --e; 728 } 729 } 730 731 // No need for extra uses anymore. 732 delete DummyInst; 733 734 unsigned NumAddedValues = NewMulOps.size(); 735 Value *V = EmitAddTreeOfValues(I, NewMulOps); 736 Value *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I); 737 738 // Now that we have inserted V and its sole use, optimize it. This allows 739 // us to handle cases that require multiple factoring steps, such as this: 740 // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C)) 741 if (NumAddedValues > 1) 742 ReassociateExpression(cast<BinaryOperator>(V)); 743 744 ++NumFactor; 745 746 if (Ops.empty()) 747 return V2; 748 749 // Add the new value to the list of things being added. 750 Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); 751 752 // Rewrite the tree so that there is now a use of V. 753 RewriteExprTree(I, Ops); 754 return OptimizeExpression(I, Ops); 755 } 756 break; 757 //case Instruction::Mul: 758 } 759 760 if (IterateOptimization) 761 return OptimizeExpression(I, Ops); 762 return 0; 763} 764 765 766/// ReassociateBB - Inspect all of the instructions in this basic block, 767/// reassociating them as we go. 768void Reassociate::ReassociateBB(BasicBlock *BB) { 769 for (BasicBlock::iterator BBI = BB->begin(); BBI != BB->end(); ) { 770 Instruction *BI = BBI++; 771 if (BI->getOpcode() == Instruction::Shl && 772 isa<ConstantInt>(BI->getOperand(1))) 773 if (Instruction *NI = ConvertShiftToMul(BI)) { 774 MadeChange = true; 775 BI = NI; 776 } 777 778 // Reject cases where it is pointless to do this. 779 if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPoint() || 780 isa<VectorType>(BI->getType())) 781 continue; // Floating point ops are not associative. 782 783 // If this is a subtract instruction which is not already in negate form, 784 // see if we can convert it to X+-Y. 785 if (BI->getOpcode() == Instruction::Sub) { 786 if (ShouldBreakUpSubtract(BI)) { 787 BI = BreakUpSubtract(BI); 788 MadeChange = true; 789 } else if (BinaryOperator::isNeg(BI)) { 790 // Otherwise, this is a negation. See if the operand is a multiply tree 791 // and if this is not an inner node of a multiply tree. 792 if (isReassociableOp(BI->getOperand(1), Instruction::Mul) && 793 (!BI->hasOneUse() || 794 !isReassociableOp(BI->use_back(), Instruction::Mul))) { 795 BI = LowerNegateToMultiply(BI); 796 MadeChange = true; 797 } 798 } 799 } 800 801 // If this instruction is a commutative binary operator, process it. 802 if (!BI->isAssociative()) continue; 803 BinaryOperator *I = cast<BinaryOperator>(BI); 804 805 // If this is an interior node of a reassociable tree, ignore it until we 806 // get to the root of the tree, to avoid N^2 analysis. 807 if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode())) 808 continue; 809 810 // If this is an add tree that is used by a sub instruction, ignore it 811 // until we process the subtract. 812 if (I->hasOneUse() && I->getOpcode() == Instruction::Add && 813 cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub) 814 continue; 815 816 ReassociateExpression(I); 817 } 818} 819 820void Reassociate::ReassociateExpression(BinaryOperator *I) { 821 822 // First, walk the expression tree, linearizing the tree, collecting 823 std::vector<ValueEntry> Ops; 824 LinearizeExprTree(I, Ops); 825 826 DOUT << "RAIn:\t"; DEBUG(PrintOps(I, Ops)); DOUT << "\n"; 827 828 // Now that we have linearized the tree to a list and have gathered all of 829 // the operands and their ranks, sort the operands by their rank. Use a 830 // stable_sort so that values with equal ranks will have their relative 831 // positions maintained (and so the compiler is deterministic). Note that 832 // this sorts so that the highest ranking values end up at the beginning of 833 // the vector. 834 std::stable_sort(Ops.begin(), Ops.end()); 835 836 // OptimizeExpression - Now that we have the expression tree in a convenient 837 // sorted form, optimize it globally if possible. 838 if (Value *V = OptimizeExpression(I, Ops)) { 839 // This expression tree simplified to something that isn't a tree, 840 // eliminate it. 841 DOUT << "Reassoc to scalar: " << *V << "\n"; 842 I->replaceAllUsesWith(V); 843 RemoveDeadBinaryOp(I); 844 return; 845 } 846 847 // We want to sink immediates as deeply as possible except in the case where 848 // this is a multiply tree used only by an add, and the immediate is a -1. 849 // In this case we reassociate to put the negation on the outside so that we 850 // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y 851 if (I->getOpcode() == Instruction::Mul && I->hasOneUse() && 852 cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add && 853 isa<ConstantInt>(Ops.back().Op) && 854 cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) { 855 Ops.insert(Ops.begin(), Ops.back()); 856 Ops.pop_back(); 857 } 858 859 DOUT << "RAOut:\t"; DEBUG(PrintOps(I, Ops)); DOUT << "\n"; 860 861 if (Ops.size() == 1) { 862 // This expression tree simplified to something that isn't a tree, 863 // eliminate it. 864 I->replaceAllUsesWith(Ops[0].Op); 865 RemoveDeadBinaryOp(I); 866 } else { 867 // Now that we ordered and optimized the expressions, splat them back into 868 // the expression tree, removing any unneeded nodes. 869 RewriteExprTree(I, Ops); 870 } 871} 872 873 874bool Reassociate::runOnFunction(Function &F) { 875 // Recalculate the rank map for F 876 BuildRankMap(F); 877 878 MadeChange = false; 879 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 880 ReassociateBB(FI); 881 882 // We are done with the rank map... 883 RankMap.clear(); 884 ValueRankMap.clear(); 885 return MadeChange; 886} 887 888