Reassociate.cpp revision 109d34d6ff51a0fdd39d7b3b373a83fcca6c67a3
1//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/Function.h" 27#include "llvm/Instructions.h" 28#include "llvm/Pass.h" 29#include "llvm/Type.h" 30#include "llvm/Support/CFG.h" 31#include "llvm/Support/Debug.h" 32#include "llvm/ADT/PostOrderIterator.h" 33#include "llvm/ADT/Statistic.h" 34#include <algorithm> 35using namespace llvm; 36 37namespace { 38 Statistic<> NumLinear ("reassociate","Number of insts linearized"); 39 Statistic<> NumChanged("reassociate","Number of insts reassociated"); 40 Statistic<> NumSwapped("reassociate","Number of insts with operands swapped"); 41 Statistic<> NumAnnihil("reassociate","Number of expr tree annihilated"); 42 43 struct ValueEntry { 44 unsigned Rank; 45 Value *Op; 46 ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 47 }; 48 inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 49 return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 50 } 51 52 class Reassociate : public FunctionPass { 53 std::map<BasicBlock*, unsigned> RankMap; 54 std::map<Value*, unsigned> ValueRankMap; 55 bool MadeChange; 56 public: 57 bool runOnFunction(Function &F); 58 59 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 60 AU.setPreservesCFG(); 61 } 62 private: 63 void BuildRankMap(Function &F); 64 unsigned getRank(Value *V); 65 void RewriteExprTree(BinaryOperator *I, unsigned Idx, 66 std::vector<ValueEntry> &Ops); 67 void OptimizeExpression(unsigned Opcode, std::vector<ValueEntry> &Ops); 68 void LinearizeExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops); 69 void LinearizeExpr(BinaryOperator *I); 70 void ReassociateBB(BasicBlock *BB); 71 }; 72 73 RegisterOpt<Reassociate> X("reassociate", "Reassociate expressions"); 74} 75 76// Public interface to the Reassociate pass 77FunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 78 79void Reassociate::BuildRankMap(Function &F) { 80 unsigned i = 2; 81 82 // Assign distinct ranks to function arguments 83 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 84 ValueRankMap[I] = ++i; 85 86 ReversePostOrderTraversal<Function*> RPOT(&F); 87 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 88 E = RPOT.end(); I != E; ++I) 89 RankMap[*I] = ++i << 16; 90} 91 92unsigned Reassociate::getRank(Value *V) { 93 if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument... 94 95 Instruction *I = dyn_cast<Instruction>(V); 96 if (I == 0) return 0; // Otherwise it's a global or constant, rank 0. 97 98 unsigned &CachedRank = ValueRankMap[I]; 99 if (CachedRank) return CachedRank; // Rank already known? 100 101 // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 102 // we can reassociate expressions for code motion! Since we do not recurse 103 // for PHI nodes, we cannot have infinite recursion here, because there 104 // cannot be loops in the value graph that do not go through PHI nodes. 105 // 106 if (I->getOpcode() == Instruction::PHI || 107 I->getOpcode() == Instruction::Alloca || 108 I->getOpcode() == Instruction::Malloc || isa<TerminatorInst>(I) || 109 I->mayWriteToMemory()) // Cannot move inst if it writes to memory! 110 return RankMap[I->getParent()]; 111 112 // If not, compute it! 113 unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 114 for (unsigned i = 0, e = I->getNumOperands(); 115 i != e && Rank != MaxRank; ++i) 116 Rank = std::max(Rank, getRank(I->getOperand(i))); 117 118 // If this is a not or neg instruction, do not count it for rank. This 119 // assures us that X and ~X will have the same rank. 120 if (!I->getType()->isIntegral() || 121 (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 122 ++Rank; 123 124 DEBUG(std::cerr << "Calculated Rank[" << V->getName() << "] = " 125 << Rank << "\n"); 126 127 return CachedRank = Rank; 128} 129 130/// isReassociableOp - Return true if V is an instruction of the specified 131/// opcode and if it only has one use. 132static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 133 if (V->hasOneUse() && isa<Instruction>(V) && 134 cast<Instruction>(V)->getOpcode() == Opcode) 135 return cast<BinaryOperator>(V); 136 return 0; 137} 138 139// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. 140// Note that if D is also part of the expression tree that we recurse to 141// linearize it as well. Besides that case, this does not recurse into A,B, or 142// C. 143void Reassociate::LinearizeExpr(BinaryOperator *I) { 144 BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 145 BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1)); 146 assert(isReassociableOp(LHS, I->getOpcode()) && 147 isReassociableOp(RHS, I->getOpcode()) && 148 "Not an expression that needs linearization?"); 149 150 DEBUG(std::cerr << "Linear" << *LHS << *RHS << *I); 151 152 // Move the RHS instruction to live immediately before I, avoiding breaking 153 // dominator properties. 154 I->getParent()->getInstList().splice(I, RHS->getParent()->getInstList(), RHS); 155 156 // Move operands around to do the linearization. 157 I->setOperand(1, RHS->getOperand(0)); 158 RHS->setOperand(0, LHS); 159 I->setOperand(0, RHS); 160 161 ++NumLinear; 162 MadeChange = true; 163 DEBUG(std::cerr << "Linearized: " << *I); 164 165 // If D is part of this expression tree, tail recurse. 166 if (isReassociableOp(I->getOperand(1), I->getOpcode())) 167 LinearizeExpr(I); 168} 169 170 171/// LinearizeExprTree - Given an associative binary expression tree, traverse 172/// all of the uses putting it into canonical form. This forces a left-linear 173/// form of the the expression (((a+b)+c)+d), and collects information about the 174/// rank of the non-tree operands. 175/// 176/// This returns the rank of the RHS operand, which is known to be the highest 177/// rank value in the expression tree. 178/// 179void Reassociate::LinearizeExprTree(BinaryOperator *I, 180 std::vector<ValueEntry> &Ops) { 181 Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); 182 unsigned Opcode = I->getOpcode(); 183 184 // First step, linearize the expression if it is in ((A+B)+(C+D)) form. 185 BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); 186 BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); 187 188 if (!LHSBO) { 189 if (!RHSBO) { 190 // Neither the LHS or RHS as part of the tree, thus this is a leaf. As 191 // such, just remember these operands and their rank. 192 Ops.push_back(ValueEntry(getRank(LHS), LHS)); 193 Ops.push_back(ValueEntry(getRank(RHS), RHS)); 194 return; 195 } else { 196 // Turn X+(Y+Z) -> (Y+Z)+X 197 std::swap(LHSBO, RHSBO); 198 std::swap(LHS, RHS); 199 bool Success = !I->swapOperands(); 200 assert(Success && "swapOperands failed"); 201 MadeChange = true; 202 } 203 } else if (RHSBO) { 204 // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the the RHS is not 205 // part of the expression tree. 206 LinearizeExpr(I); 207 LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0)); 208 RHS = I->getOperand(1); 209 RHSBO = 0; 210 } 211 212 // Okay, now we know that the LHS is a nested expression and that the RHS is 213 // not. Perform reassociation. 214 assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); 215 216 // Move LHS right before I to make sure that the tree expression dominates all 217 // values. 218 I->getParent()->getInstList().splice(I, 219 LHSBO->getParent()->getInstList(), LHSBO); 220 221 // Linearize the expression tree on the LHS. 222 LinearizeExprTree(LHSBO, Ops); 223 224 // Remember the RHS operand and its rank. 225 Ops.push_back(ValueEntry(getRank(RHS), RHS)); 226} 227 228// RewriteExprTree - Now that the operands for this expression tree are 229// linearized and optimized, emit them in-order. This function is written to be 230// tail recursive. 231void Reassociate::RewriteExprTree(BinaryOperator *I, unsigned i, 232 std::vector<ValueEntry> &Ops) { 233 if (i+2 == Ops.size()) { 234 if (I->getOperand(0) != Ops[i].Op || 235 I->getOperand(1) != Ops[i+1].Op) { 236 DEBUG(std::cerr << "RA: " << *I); 237 I->setOperand(0, Ops[i].Op); 238 I->setOperand(1, Ops[i+1].Op); 239 DEBUG(std::cerr << "TO: " << *I); 240 MadeChange = true; 241 ++NumChanged; 242 } 243 return; 244 } 245 assert(i+2 < Ops.size() && "Ops index out of range!"); 246 247 if (I->getOperand(1) != Ops[i].Op) { 248 DEBUG(std::cerr << "RA: " << *I); 249 I->setOperand(1, Ops[i].Op); 250 DEBUG(std::cerr << "TO: " << *I); 251 MadeChange = true; 252 ++NumChanged; 253 } 254 RewriteExprTree(cast<BinaryOperator>(I->getOperand(0)), i+1, Ops); 255} 256 257 258 259// NegateValue - Insert instructions before the instruction pointed to by BI, 260// that computes the negative version of the value specified. The negative 261// version of the value is returned, and BI is left pointing at the instruction 262// that should be processed next by the reassociation pass. 263// 264static Value *NegateValue(Value *V, Instruction *BI) { 265 // We are trying to expose opportunity for reassociation. One of the things 266 // that we want to do to achieve this is to push a negation as deep into an 267 // expression chain as possible, to expose the add instructions. In practice, 268 // this means that we turn this: 269 // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 270 // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 271 // the constants. We assume that instcombine will clean up the mess later if 272 // we introduce tons of unnecessary negation instructions... 273 // 274 if (Instruction *I = dyn_cast<Instruction>(V)) 275 if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 276 Value *RHS = NegateValue(I->getOperand(1), BI); 277 Value *LHS = NegateValue(I->getOperand(0), BI); 278 279 // We must actually insert a new add instruction here, because the neg 280 // instructions do not dominate the old add instruction in general. By 281 // adding it now, we are assured that the neg instructions we just 282 // inserted dominate the instruction we are about to insert after them. 283 // 284 return BinaryOperator::create(Instruction::Add, LHS, RHS, 285 I->getName()+".neg", BI); 286 } 287 288 // Insert a 'neg' instruction that subtracts the value from zero to get the 289 // negation. 290 // 291 return BinaryOperator::createNeg(V, V->getName() + ".neg", BI); 292} 293 294/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 295/// only used by an add, transform this into (X+(0-Y)) to promote better 296/// reassociation. 297static Instruction *BreakUpSubtract(Instruction *Sub) { 298 // Reject cases where it is pointless to do this. 299 if (Sub->getType()->isFloatingPoint()) 300 return 0; // Floating point adds are not associative. 301 302 // Don't bother to break this up unless either the LHS is an associable add or 303 // if this is only used by one. 304 if (!isReassociableOp(Sub->getOperand(0), Instruction::Add) && 305 !isReassociableOp(Sub->getOperand(1), Instruction::Add) && 306 !(Sub->hasOneUse() &&isReassociableOp(Sub->use_back(), Instruction::Add))) 307 return 0; 308 309 // Convert a subtract into an add and a neg instruction... so that sub 310 // instructions can be commuted with other add instructions... 311 // 312 // Calculate the negative value of Operand 1 of the sub instruction... 313 // and set it as the RHS of the add instruction we just made... 314 // 315 std::string Name = Sub->getName(); 316 Sub->setName(""); 317 Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 318 Instruction *New = 319 BinaryOperator::createAdd(Sub->getOperand(0), NegVal, Name, Sub); 320 321 // Everyone now refers to the add instruction. 322 Sub->replaceAllUsesWith(New); 323 Sub->eraseFromParent(); 324 325 DEBUG(std::cerr << "Negated: " << *New); 326 return New; 327} 328 329/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 330/// by one, change this into a multiply by a constant to assist with further 331/// reassociation. 332static Instruction *ConvertShiftToMul(Instruction *Shl) { 333 if (!isReassociableOp(Shl->getOperand(0), Instruction::Mul) && 334 !(Shl->hasOneUse() && isReassociableOp(Shl->use_back(),Instruction::Mul))) 335 return 0; 336 337 Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 338 MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 339 340 std::string Name = Shl->getName(); Shl->setName(""); 341 Instruction *Mul = BinaryOperator::createMul(Shl->getOperand(0), MulCst, 342 Name, Shl); 343 Shl->replaceAllUsesWith(Mul); 344 Shl->eraseFromParent(); 345 return Mul; 346} 347 348// Scan backwards and forwards among values with the same rank as element i to 349// see if X exists. If X does not exist, return i. 350static unsigned FindInOperandList(std::vector<ValueEntry> &Ops, unsigned i, 351 Value *X) { 352 unsigned XRank = Ops[i].Rank; 353 unsigned e = Ops.size(); 354 for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) 355 if (Ops[j].Op == X) 356 return j; 357 // Scan backwards 358 for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) 359 if (Ops[j].Op == X) 360 return j; 361 return i; 362} 363 364void Reassociate::OptimizeExpression(unsigned Opcode, 365 std::vector<ValueEntry> &Ops) { 366 // Now that we have the linearized expression tree, try to optimize it. 367 // Start by folding any constants that we found. 368Iterate: 369 bool IterateOptimization = false; 370 if (Ops.size() == 1) return; 371 372 if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 373 if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 374 Ops.pop_back(); 375 Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 376 goto Iterate; 377 } 378 379 // Check for destructive annihilation due to a constant being used. 380 if (ConstantIntegral *CstVal = dyn_cast<ConstantIntegral>(Ops.back().Op)) 381 switch (Opcode) { 382 default: break; 383 case Instruction::And: 384 if (CstVal->isNullValue()) { // ... & 0 -> 0 385 Ops[0].Op = CstVal; 386 Ops.erase(Ops.begin()+1, Ops.end()); 387 ++NumAnnihil; 388 return; 389 } else if (CstVal->isAllOnesValue()) { // ... & -1 -> ... 390 Ops.pop_back(); 391 } 392 break; 393 case Instruction::Mul: 394 if (CstVal->isNullValue()) { // ... * 0 -> 0 395 Ops[0].Op = CstVal; 396 Ops.erase(Ops.begin()+1, Ops.end()); 397 ++NumAnnihil; 398 return; 399 } else if (cast<ConstantInt>(CstVal)->getRawValue() == 1) { 400 Ops.pop_back(); // ... * 1 -> ... 401 } 402 break; 403 case Instruction::Or: 404 if (CstVal->isAllOnesValue()) { // ... | -1 -> -1 405 Ops[0].Op = CstVal; 406 Ops.erase(Ops.begin()+1, Ops.end()); 407 ++NumAnnihil; 408 return; 409 } 410 // FALLTHROUGH! 411 case Instruction::Add: 412 case Instruction::Xor: 413 if (CstVal->isNullValue()) // ... [|^+] 0 -> ... 414 Ops.pop_back(); 415 break; 416 } 417 418 // Handle destructive annihilation do to identities between elements in the 419 // argument list here. 420 switch (Opcode) { 421 default: break; 422 case Instruction::And: 423 case Instruction::Or: 424 case Instruction::Xor: 425 // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 426 // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 427 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 428 // First, check for X and ~X in the operand list. 429 if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 430 Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 431 unsigned FoundX = FindInOperandList(Ops, i, X); 432 if (FoundX != i) { 433 if (Opcode == Instruction::And) { // ...&X&~X = 0 434 Ops[0].Op = Constant::getNullValue(X->getType()); 435 Ops.erase(Ops.begin()+1, Ops.end()); 436 ++NumAnnihil; 437 return; 438 } else if (Opcode == Instruction::Or) { // ...|X|~X = -1 439 Ops[0].Op = ConstantIntegral::getAllOnesValue(X->getType()); 440 Ops.erase(Ops.begin()+1, Ops.end()); 441 ++NumAnnihil; 442 return; 443 } 444 } 445 } 446 447 // Next, check for duplicate pairs of values, which we assume are next to 448 // each other, due to our sorting criteria. 449 if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 450 if (Opcode == Instruction::And || Opcode == Instruction::Or) { 451 // Drop duplicate values. 452 Ops.erase(Ops.begin()+i); 453 --i; --e; 454 IterateOptimization = true; 455 ++NumAnnihil; 456 } else { 457 assert(Opcode == Instruction::Xor); 458 // ... X^X -> ... 459 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 460 i -= 2; e -= 2; 461 IterateOptimization = true; 462 ++NumAnnihil; 463 } 464 } 465 } 466 break; 467 468 case Instruction::Add: 469 // Scan the operand lists looking for X and -X pairs. If we find any, we 470 // can simplify the expression. X+-X == 0 471 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 472 // Check for X and -X in the operand list. 473 if (BinaryOperator::isNeg(Ops[i].Op)) { 474 Value *X = BinaryOperator::getNegArgument(Ops[i].Op); 475 unsigned FoundX = FindInOperandList(Ops, i, X); 476 if (FoundX != i) { 477 // Remove X and -X from the operand list. 478 if (Ops.size() == 2) { 479 Ops[0].Op = Constant::getNullValue(X->getType()); 480 Ops.erase(Ops.begin()+1); 481 ++NumAnnihil; 482 return; 483 } else { 484 Ops.erase(Ops.begin()+i); 485 if (i < FoundX) --FoundX; 486 Ops.erase(Ops.begin()+FoundX); 487 IterateOptimization = true; 488 ++NumAnnihil; 489 } 490 } 491 } 492 } 493 break; 494 //case Instruction::Mul: 495 } 496 497 if (IterateOptimization) goto Iterate; 498} 499 500 501/// ReassociateBB - Inspect all of the instructions in this basic block, 502/// reassociating them as we go. 503void Reassociate::ReassociateBB(BasicBlock *BB) { 504 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) { 505 // If this is a subtract instruction which is not already in negate form, 506 // see if we can convert it to X+-Y. 507 if (BI->getOpcode() == Instruction::Sub && !BinaryOperator::isNeg(BI)) 508 if (Instruction *NI = BreakUpSubtract(BI)) { 509 MadeChange = true; 510 BI = NI; 511 } 512 if (BI->getOpcode() == Instruction::Shl && 513 isa<ConstantInt>(BI->getOperand(1))) 514 if (Instruction *NI = ConvertShiftToMul(BI)) { 515 MadeChange = true; 516 BI = NI; 517 } 518 519 // If this instruction is a commutative binary operator, process it. 520 if (!BI->isAssociative()) continue; 521 BinaryOperator *I = cast<BinaryOperator>(BI); 522 523 // If this is an interior node of a reassociable tree, ignore it until we 524 // get to the root of the tree, to avoid N^2 analysis. 525 if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode())) 526 continue; 527 528 // First, walk the expression tree, linearizing the tree, collecting 529 std::vector<ValueEntry> Ops; 530 LinearizeExprTree(I, Ops); 531 532 // Now that we have linearized the tree to a list and have gathered all of 533 // the operands and their ranks, sort the operands by their rank. Use a 534 // stable_sort so that values with equal ranks will have their relative 535 // positions maintained (and so the compiler is deterministic). Note that 536 // this sorts so that the highest ranking values end up at the beginning of 537 // the vector. 538 std::stable_sort(Ops.begin(), Ops.end()); 539 540 // OptimizeExpression - Now that we have the expression tree in a convenient 541 // sorted form, optimize it globally if possible. 542 OptimizeExpression(I->getOpcode(), Ops); 543 544 if (Ops.size() == 1) { 545 // This expression tree simplified to something that isn't a tree, 546 // eliminate it. 547 I->replaceAllUsesWith(Ops[0].Op); 548 } else { 549 // Now that we ordered and optimized the expressions, splat them back into 550 // the expression tree, removing any unneeded nodes. 551 RewriteExprTree(I, 0, Ops); 552 } 553 } 554} 555 556 557bool Reassociate::runOnFunction(Function &F) { 558 // Recalculate the rank map for F 559 BuildRankMap(F); 560 561 MadeChange = false; 562 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 563 ReassociateBB(FI); 564 565 // We are done with the rank map... 566 RankMap.clear(); 567 ValueRankMap.clear(); 568 return MadeChange; 569} 570 571