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 #include "llvm/Transforms/Scalar.h" 24 #include "llvm/ADT/DenseMap.h" 25 #include "llvm/ADT/PostOrderIterator.h" 26 #include "llvm/ADT/STLExtras.h" 27 #include "llvm/ADT/SetVector.h" 28 #include "llvm/ADT/Statistic.h" 29 #include "llvm/IR/CFG.h" 30 #include "llvm/IR/Constants.h" 31 #include "llvm/IR/DerivedTypes.h" 32 #include "llvm/IR/Function.h" 33 #include "llvm/IR/IRBuilder.h" 34 #include "llvm/IR/Instructions.h" 35 #include "llvm/IR/IntrinsicInst.h" 36 #include "llvm/IR/ValueHandle.h" 37 #include "llvm/Pass.h" 38 #include "llvm/Support/Debug.h" 39 #include "llvm/Support/raw_ostream.h" 40 #include "llvm/Transforms/Utils/Local.h" 41 #include <algorithm> 42 using namespace llvm; 43 44 #define DEBUG_TYPE "reassociate" 45 46 STATISTIC(NumChanged, "Number of insts reassociated"); 47 STATISTIC(NumAnnihil, "Number of expr tree annihilated"); 48 STATISTIC(NumFactor , "Number of multiplies factored"); 49 50 namespace { 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 /// 64 static 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 Ops[i].Op->printAsOperand(dbgs(), false, M); 71 dbgs() << ", #" << Ops[i].Rank << "] "; 72 } 73 } 74 #endif 75 76 namespace { 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 /// Utility class representing a non-constant Xor-operand. We classify 115 /// non-constant Xor-Operands into two categories: 116 /// C1) The operand is in the form "X & C", where C is a constant and C != ~0 117 /// C2) 118 /// C2.1) The operand is in the form of "X | C", where C is a non-zero 119 /// constant. 120 /// C2.2) Any operand E which doesn't fall into C1 and C2.1, we view this 121 /// operand as "E | 0" 122 class XorOpnd { 123 public: 124 XorOpnd(Value *V); 125 126 bool isInvalid() const { return SymbolicPart == nullptr; } 127 bool isOrExpr() const { return isOr; } 128 Value *getValue() const { return OrigVal; } 129 Value *getSymbolicPart() const { return SymbolicPart; } 130 unsigned getSymbolicRank() const { return SymbolicRank; } 131 const APInt &getConstPart() const { return ConstPart; } 132 133 void Invalidate() { SymbolicPart = OrigVal = nullptr; } 134 void setSymbolicRank(unsigned R) { SymbolicRank = R; } 135 136 // Sort the XorOpnd-Pointer in ascending order of symbolic-value-rank. 137 // The purpose is twofold: 138 // 1) Cluster together the operands sharing the same symbolic-value. 139 // 2) Operand having smaller symbolic-value-rank is permuted earlier, which 140 // could potentially shorten crital path, and expose more loop-invariants. 141 // Note that values' rank are basically defined in RPO order (FIXME). 142 // So, if Rank(X) < Rank(Y) < Rank(Z), it means X is defined earlier 143 // than Y which is defined earlier than Z. Permute "x | 1", "Y & 2", 144 // "z" in the order of X-Y-Z is better than any other orders. 145 struct PtrSortFunctor { 146 bool operator()(XorOpnd * const &LHS, XorOpnd * const &RHS) { 147 return LHS->getSymbolicRank() < RHS->getSymbolicRank(); 148 } 149 }; 150 private: 151 Value *OrigVal; 152 Value *SymbolicPart; 153 APInt ConstPart; 154 unsigned SymbolicRank; 155 bool isOr; 156 }; 157 } 158 159 namespace { 160 class Reassociate : public FunctionPass { 161 DenseMap<BasicBlock*, unsigned> RankMap; 162 DenseMap<AssertingVH<Value>, unsigned> ValueRankMap; 163 SetVector<AssertingVH<Instruction> > RedoInsts; 164 bool MadeChange; 165 public: 166 static char ID; // Pass identification, replacement for typeid 167 Reassociate() : FunctionPass(ID) { 168 initializeReassociatePass(*PassRegistry::getPassRegistry()); 169 } 170 171 bool runOnFunction(Function &F) override; 172 173 void getAnalysisUsage(AnalysisUsage &AU) const override { 174 AU.setPreservesCFG(); 175 } 176 private: 177 void BuildRankMap(Function &F); 178 unsigned getRank(Value *V); 179 void canonicalizeOperands(Instruction *I); 180 void ReassociateExpression(BinaryOperator *I); 181 void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 182 Value *OptimizeExpression(BinaryOperator *I, 183 SmallVectorImpl<ValueEntry> &Ops); 184 Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops); 185 Value *OptimizeXor(Instruction *I, SmallVectorImpl<ValueEntry> &Ops); 186 bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, APInt &ConstOpnd, 187 Value *&Res); 188 bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2, 189 APInt &ConstOpnd, Value *&Res); 190 bool collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops, 191 SmallVectorImpl<Factor> &Factors); 192 Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder, 193 SmallVectorImpl<Factor> &Factors); 194 Value *OptimizeMul(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 195 Value *RemoveFactorFromExpression(Value *V, Value *Factor); 196 void EraseInst(Instruction *I); 197 void OptimizeInst(Instruction *I); 198 Instruction *canonicalizeNegConstExpr(Instruction *I); 199 }; 200 } 201 202 XorOpnd::XorOpnd(Value *V) { 203 assert(!isa<ConstantInt>(V) && "No ConstantInt"); 204 OrigVal = V; 205 Instruction *I = dyn_cast<Instruction>(V); 206 SymbolicRank = 0; 207 208 if (I && (I->getOpcode() == Instruction::Or || 209 I->getOpcode() == Instruction::And)) { 210 Value *V0 = I->getOperand(0); 211 Value *V1 = I->getOperand(1); 212 if (isa<ConstantInt>(V0)) 213 std::swap(V0, V1); 214 215 if (ConstantInt *C = dyn_cast<ConstantInt>(V1)) { 216 ConstPart = C->getValue(); 217 SymbolicPart = V0; 218 isOr = (I->getOpcode() == Instruction::Or); 219 return; 220 } 221 } 222 223 // view the operand as "V | 0" 224 SymbolicPart = V; 225 ConstPart = APInt::getNullValue(V->getType()->getIntegerBitWidth()); 226 isOr = true; 227 } 228 229 char Reassociate::ID = 0; 230 INITIALIZE_PASS(Reassociate, "reassociate", 231 "Reassociate expressions", false, false) 232 233 // Public interface to the Reassociate pass 234 FunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 235 236 /// isReassociableOp - Return true if V is an instruction of the specified 237 /// opcode and if it only has one use. 238 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 239 if (V->hasOneUse() && isa<Instruction>(V) && 240 cast<Instruction>(V)->getOpcode() == Opcode && 241 (!isa<FPMathOperator>(V) || 242 cast<Instruction>(V)->hasUnsafeAlgebra())) 243 return cast<BinaryOperator>(V); 244 return nullptr; 245 } 246 247 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode1, 248 unsigned Opcode2) { 249 if (V->hasOneUse() && isa<Instruction>(V) && 250 (cast<Instruction>(V)->getOpcode() == Opcode1 || 251 cast<Instruction>(V)->getOpcode() == Opcode2) && 252 (!isa<FPMathOperator>(V) || 253 cast<Instruction>(V)->hasUnsafeAlgebra())) 254 return cast<BinaryOperator>(V); 255 return nullptr; 256 } 257 258 static bool isUnmovableInstruction(Instruction *I) { 259 switch (I->getOpcode()) { 260 case Instruction::PHI: 261 case Instruction::LandingPad: 262 case Instruction::Alloca: 263 case Instruction::Load: 264 case Instruction::Invoke: 265 case Instruction::UDiv: 266 case Instruction::SDiv: 267 case Instruction::FDiv: 268 case Instruction::URem: 269 case Instruction::SRem: 270 case Instruction::FRem: 271 return true; 272 case Instruction::Call: 273 return !isa<DbgInfoIntrinsic>(I); 274 default: 275 return false; 276 } 277 } 278 279 void Reassociate::BuildRankMap(Function &F) { 280 unsigned i = 2; 281 282 // Assign distinct ranks to function arguments. 283 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) { 284 ValueRankMap[&*I] = ++i; 285 DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n"); 286 } 287 288 ReversePostOrderTraversal<Function*> RPOT(&F); 289 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 290 E = RPOT.end(); I != E; ++I) { 291 BasicBlock *BB = *I; 292 unsigned BBRank = RankMap[BB] = ++i << 16; 293 294 // Walk the basic block, adding precomputed ranks for any instructions that 295 // we cannot move. This ensures that the ranks for these instructions are 296 // all different in the block. 297 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 298 if (isUnmovableInstruction(I)) 299 ValueRankMap[&*I] = ++BBRank; 300 } 301 } 302 303 unsigned Reassociate::getRank(Value *V) { 304 Instruction *I = dyn_cast<Instruction>(V); 305 if (!I) { 306 if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument. 307 return 0; // Otherwise it's a global or constant, rank 0. 308 } 309 310 if (unsigned Rank = ValueRankMap[I]) 311 return Rank; // Rank already known? 312 313 // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 314 // we can reassociate expressions for code motion! Since we do not recurse 315 // for PHI nodes, we cannot have infinite recursion here, because there 316 // cannot be loops in the value graph that do not go through PHI nodes. 317 unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 318 for (unsigned i = 0, e = I->getNumOperands(); 319 i != e && Rank != MaxRank; ++i) 320 Rank = std::max(Rank, getRank(I->getOperand(i))); 321 322 // If this is a not or neg instruction, do not count it for rank. This 323 // assures us that X and ~X will have the same rank. 324 if (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I) && 325 !BinaryOperator::isFNeg(I)) 326 ++Rank; 327 328 DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = " << Rank << "\n"); 329 330 return ValueRankMap[I] = Rank; 331 } 332 333 // Canonicalize constants to RHS. Otherwise, sort the operands by rank. 334 void Reassociate::canonicalizeOperands(Instruction *I) { 335 assert(isa<BinaryOperator>(I) && "Expected binary operator."); 336 assert(I->isCommutative() && "Expected commutative operator."); 337 338 Value *LHS = I->getOperand(0); 339 Value *RHS = I->getOperand(1); 340 unsigned LHSRank = getRank(LHS); 341 unsigned RHSRank = getRank(RHS); 342 343 if (isa<Constant>(RHS)) 344 return; 345 346 if (isa<Constant>(LHS) || RHSRank < LHSRank) 347 cast<BinaryOperator>(I)->swapOperands(); 348 } 349 350 static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name, 351 Instruction *InsertBefore, Value *FlagsOp) { 352 if (S1->getType()->isIntOrIntVectorTy()) 353 return BinaryOperator::CreateAdd(S1, S2, Name, InsertBefore); 354 else { 355 BinaryOperator *Res = 356 BinaryOperator::CreateFAdd(S1, S2, Name, InsertBefore); 357 Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags()); 358 return Res; 359 } 360 } 361 362 static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name, 363 Instruction *InsertBefore, Value *FlagsOp) { 364 if (S1->getType()->isIntOrIntVectorTy()) 365 return BinaryOperator::CreateMul(S1, S2, Name, InsertBefore); 366 else { 367 BinaryOperator *Res = 368 BinaryOperator::CreateFMul(S1, S2, Name, InsertBefore); 369 Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags()); 370 return Res; 371 } 372 } 373 374 static BinaryOperator *CreateNeg(Value *S1, const Twine &Name, 375 Instruction *InsertBefore, Value *FlagsOp) { 376 if (S1->getType()->isIntOrIntVectorTy()) 377 return BinaryOperator::CreateNeg(S1, Name, InsertBefore); 378 else { 379 BinaryOperator *Res = BinaryOperator::CreateFNeg(S1, Name, InsertBefore); 380 Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags()); 381 return Res; 382 } 383 } 384 385 /// LowerNegateToMultiply - Replace 0-X with X*-1. 386 /// 387 static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) { 388 Type *Ty = Neg->getType(); 389 Constant *NegOne = Ty->isIntOrIntVectorTy() ? 390 ConstantInt::getAllOnesValue(Ty) : ConstantFP::get(Ty, -1.0); 391 392 BinaryOperator *Res = CreateMul(Neg->getOperand(1), NegOne, "", Neg, Neg); 393 Neg->setOperand(1, Constant::getNullValue(Ty)); // Drop use of op. 394 Res->takeName(Neg); 395 Neg->replaceAllUsesWith(Res); 396 Res->setDebugLoc(Neg->getDebugLoc()); 397 return Res; 398 } 399 400 /// CarmichaelShift - Returns k such that lambda(2^Bitwidth) = 2^k, where lambda 401 /// is the Carmichael function. This means that x^(2^k) === 1 mod 2^Bitwidth for 402 /// every odd x, i.e. x^(2^k) = 1 for every odd x in Bitwidth-bit arithmetic. 403 /// Note that 0 <= k < Bitwidth, and if Bitwidth > 3 then x^(2^k) = 0 for every 404 /// even x in Bitwidth-bit arithmetic. 405 static unsigned CarmichaelShift(unsigned Bitwidth) { 406 if (Bitwidth < 3) 407 return Bitwidth - 1; 408 return Bitwidth - 2; 409 } 410 411 /// IncorporateWeight - Add the extra weight 'RHS' to the existing weight 'LHS', 412 /// reducing the combined weight using any special properties of the operation. 413 /// The existing weight LHS represents the computation X op X op ... op X where 414 /// X occurs LHS times. The combined weight represents X op X op ... op X with 415 /// X occurring LHS + RHS times. If op is "Xor" for example then the combined 416 /// operation is equivalent to X if LHS + RHS is odd, or 0 if LHS + RHS is even; 417 /// the routine returns 1 in LHS in the first case, and 0 in LHS in the second. 418 static void IncorporateWeight(APInt &LHS, const APInt &RHS, unsigned Opcode) { 419 // If we were working with infinite precision arithmetic then the combined 420 // weight would be LHS + RHS. But we are using finite precision arithmetic, 421 // and the APInt sum LHS + RHS may not be correct if it wraps (it is correct 422 // for nilpotent operations and addition, but not for idempotent operations 423 // and multiplication), so it is important to correctly reduce the combined 424 // weight back into range if wrapping would be wrong. 425 426 // If RHS is zero then the weight didn't change. 427 if (RHS.isMinValue()) 428 return; 429 // If LHS is zero then the combined weight is RHS. 430 if (LHS.isMinValue()) { 431 LHS = RHS; 432 return; 433 } 434 // From this point on we know that neither LHS nor RHS is zero. 435 436 if (Instruction::isIdempotent(Opcode)) { 437 // Idempotent means X op X === X, so any non-zero weight is equivalent to a 438 // weight of 1. Keeping weights at zero or one also means that wrapping is 439 // not a problem. 440 assert(LHS == 1 && RHS == 1 && "Weights not reduced!"); 441 return; // Return a weight of 1. 442 } 443 if (Instruction::isNilpotent(Opcode)) { 444 // Nilpotent means X op X === 0, so reduce weights modulo 2. 445 assert(LHS == 1 && RHS == 1 && "Weights not reduced!"); 446 LHS = 0; // 1 + 1 === 0 modulo 2. 447 return; 448 } 449 if (Opcode == Instruction::Add || Opcode == Instruction::FAdd) { 450 // TODO: Reduce the weight by exploiting nsw/nuw? 451 LHS += RHS; 452 return; 453 } 454 455 assert((Opcode == Instruction::Mul || Opcode == Instruction::FMul) && 456 "Unknown associative operation!"); 457 unsigned Bitwidth = LHS.getBitWidth(); 458 // If CM is the Carmichael number then a weight W satisfying W >= CM+Bitwidth 459 // can be replaced with W-CM. That's because x^W=x^(W-CM) for every Bitwidth 460 // bit number x, since either x is odd in which case x^CM = 1, or x is even in 461 // which case both x^W and x^(W - CM) are zero. By subtracting off multiples 462 // of CM like this weights can always be reduced to the range [0, CM+Bitwidth) 463 // which by a happy accident means that they can always be represented using 464 // Bitwidth bits. 465 // TODO: Reduce the weight by exploiting nsw/nuw? (Could do much better than 466 // the Carmichael number). 467 if (Bitwidth > 3) { 468 /// CM - The value of Carmichael's lambda function. 469 APInt CM = APInt::getOneBitSet(Bitwidth, CarmichaelShift(Bitwidth)); 470 // Any weight W >= Threshold can be replaced with W - CM. 471 APInt Threshold = CM + Bitwidth; 472 assert(LHS.ult(Threshold) && RHS.ult(Threshold) && "Weights not reduced!"); 473 // For Bitwidth 4 or more the following sum does not overflow. 474 LHS += RHS; 475 while (LHS.uge(Threshold)) 476 LHS -= CM; 477 } else { 478 // To avoid problems with overflow do everything the same as above but using 479 // a larger type. 480 unsigned CM = 1U << CarmichaelShift(Bitwidth); 481 unsigned Threshold = CM + Bitwidth; 482 assert(LHS.getZExtValue() < Threshold && RHS.getZExtValue() < Threshold && 483 "Weights not reduced!"); 484 unsigned Total = LHS.getZExtValue() + RHS.getZExtValue(); 485 while (Total >= Threshold) 486 Total -= CM; 487 LHS = Total; 488 } 489 } 490 491 typedef std::pair<Value*, APInt> RepeatedValue; 492 493 /// LinearizeExprTree - Given an associative binary expression, return the leaf 494 /// nodes in Ops along with their weights (how many times the leaf occurs). The 495 /// original expression is the same as 496 /// (Ops[0].first op Ops[0].first op ... Ops[0].first) <- Ops[0].second times 497 /// op 498 /// (Ops[1].first op Ops[1].first op ... Ops[1].first) <- Ops[1].second times 499 /// op 500 /// ... 501 /// op 502 /// (Ops[N].first op Ops[N].first op ... Ops[N].first) <- Ops[N].second times 503 /// 504 /// Note that the values Ops[0].first, ..., Ops[N].first are all distinct. 505 /// 506 /// This routine may modify the function, in which case it returns 'true'. The 507 /// changes it makes may well be destructive, changing the value computed by 'I' 508 /// to something completely different. Thus if the routine returns 'true' then 509 /// you MUST either replace I with a new expression computed from the Ops array, 510 /// or use RewriteExprTree to put the values back in. 511 /// 512 /// A leaf node is either not a binary operation of the same kind as the root 513 /// node 'I' (i.e. is not a binary operator at all, or is, but with a different 514 /// opcode), or is the same kind of binary operator but has a use which either 515 /// does not belong to the expression, or does belong to the expression but is 516 /// a leaf node. Every leaf node has at least one use that is a non-leaf node 517 /// of the expression, while for non-leaf nodes (except for the root 'I') every 518 /// use is a non-leaf node of the expression. 519 /// 520 /// For example: 521 /// expression graph node names 522 /// 523 /// + | I 524 /// / \ | 525 /// + + | A, B 526 /// / \ / \ | 527 /// * + * | C, D, E 528 /// / \ / \ / \ | 529 /// + * | F, G 530 /// 531 /// The leaf nodes are C, E, F and G. The Ops array will contain (maybe not in 532 /// that order) (C, 1), (E, 1), (F, 2), (G, 2). 533 /// 534 /// The expression is maximal: if some instruction is a binary operator of the 535 /// same kind as 'I', and all of its uses are non-leaf nodes of the expression, 536 /// then the instruction also belongs to the expression, is not a leaf node of 537 /// it, and its operands also belong to the expression (but may be leaf nodes). 538 /// 539 /// NOTE: This routine will set operands of non-leaf non-root nodes to undef in 540 /// order to ensure that every non-root node in the expression has *exactly one* 541 /// use by a non-leaf node of the expression. This destruction means that the 542 /// caller MUST either replace 'I' with a new expression or use something like 543 /// RewriteExprTree to put the values back in if the routine indicates that it 544 /// made a change by returning 'true'. 545 /// 546 /// In the above example either the right operand of A or the left operand of B 547 /// will be replaced by undef. If it is B's operand then this gives: 548 /// 549 /// + | I 550 /// / \ | 551 /// + + | A, B - operand of B replaced with undef 552 /// / \ \ | 553 /// * + * | C, D, E 554 /// / \ / \ / \ | 555 /// + * | F, G 556 /// 557 /// Note that such undef operands can only be reached by passing through 'I'. 558 /// For example, if you visit operands recursively starting from a leaf node 559 /// then you will never see such an undef operand unless you get back to 'I', 560 /// which requires passing through a phi node. 561 /// 562 /// Note that this routine may also mutate binary operators of the wrong type 563 /// that have all uses inside the expression (i.e. only used by non-leaf nodes 564 /// of the expression) if it can turn them into binary operators of the right 565 /// type and thus make the expression bigger. 566 567 static bool LinearizeExprTree(BinaryOperator *I, 568 SmallVectorImpl<RepeatedValue> &Ops) { 569 DEBUG(dbgs() << "LINEARIZE: " << *I << '\n'); 570 unsigned Bitwidth = I->getType()->getScalarType()->getPrimitiveSizeInBits(); 571 unsigned Opcode = I->getOpcode(); 572 assert(I->isAssociative() && I->isCommutative() && 573 "Expected an associative and commutative operation!"); 574 575 // Visit all operands of the expression, keeping track of their weight (the 576 // number of paths from the expression root to the operand, or if you like 577 // the number of times that operand occurs in the linearized expression). 578 // For example, if I = X + A, where X = A + B, then I, X and B have weight 1 579 // while A has weight two. 580 581 // Worklist of non-leaf nodes (their operands are in the expression too) along 582 // with their weights, representing a certain number of paths to the operator. 583 // If an operator occurs in the worklist multiple times then we found multiple 584 // ways to get to it. 585 SmallVector<std::pair<BinaryOperator*, APInt>, 8> Worklist; // (Op, Weight) 586 Worklist.push_back(std::make_pair(I, APInt(Bitwidth, 1))); 587 bool Changed = false; 588 589 // Leaves of the expression are values that either aren't the right kind of 590 // operation (eg: a constant, or a multiply in an add tree), or are, but have 591 // some uses that are not inside the expression. For example, in I = X + X, 592 // X = A + B, the value X has two uses (by I) that are in the expression. If 593 // X has any other uses, for example in a return instruction, then we consider 594 // X to be a leaf, and won't analyze it further. When we first visit a value, 595 // if it has more than one use then at first we conservatively consider it to 596 // be a leaf. Later, as the expression is explored, we may discover some more 597 // uses of the value from inside the expression. If all uses turn out to be 598 // from within the expression (and the value is a binary operator of the right 599 // kind) then the value is no longer considered to be a leaf, and its operands 600 // are explored. 601 602 // Leaves - Keeps track of the set of putative leaves as well as the number of 603 // paths to each leaf seen so far. 604 typedef DenseMap<Value*, APInt> LeafMap; 605 LeafMap Leaves; // Leaf -> Total weight so far. 606 SmallVector<Value*, 8> LeafOrder; // Ensure deterministic leaf output order. 607 608 #ifndef NDEBUG 609 SmallPtrSet<Value*, 8> Visited; // For sanity checking the iteration scheme. 610 #endif 611 while (!Worklist.empty()) { 612 std::pair<BinaryOperator*, APInt> P = Worklist.pop_back_val(); 613 I = P.first; // We examine the operands of this binary operator. 614 615 for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) { // Visit operands. 616 Value *Op = I->getOperand(OpIdx); 617 APInt Weight = P.second; // Number of paths to this operand. 618 DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n"); 619 assert(!Op->use_empty() && "No uses, so how did we get to it?!"); 620 621 // If this is a binary operation of the right kind with only one use then 622 // add its operands to the expression. 623 if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) { 624 assert(Visited.insert(Op).second && "Not first visit!"); 625 DEBUG(dbgs() << "DIRECT ADD: " << *Op << " (" << Weight << ")\n"); 626 Worklist.push_back(std::make_pair(BO, Weight)); 627 continue; 628 } 629 630 // Appears to be a leaf. Is the operand already in the set of leaves? 631 LeafMap::iterator It = Leaves.find(Op); 632 if (It == Leaves.end()) { 633 // Not in the leaf map. Must be the first time we saw this operand. 634 assert(Visited.insert(Op).second && "Not first visit!"); 635 if (!Op->hasOneUse()) { 636 // This value has uses not accounted for by the expression, so it is 637 // not safe to modify. Mark it as being a leaf. 638 DEBUG(dbgs() << "ADD USES LEAF: " << *Op << " (" << Weight << ")\n"); 639 LeafOrder.push_back(Op); 640 Leaves[Op] = Weight; 641 continue; 642 } 643 // No uses outside the expression, try morphing it. 644 } else if (It != Leaves.end()) { 645 // Already in the leaf map. 646 assert(Visited.count(Op) && "In leaf map but not visited!"); 647 648 // Update the number of paths to the leaf. 649 IncorporateWeight(It->second, Weight, Opcode); 650 651 #if 0 // TODO: Re-enable once PR13021 is fixed. 652 // The leaf already has one use from inside the expression. As we want 653 // exactly one such use, drop this new use of the leaf. 654 assert(!Op->hasOneUse() && "Only one use, but we got here twice!"); 655 I->setOperand(OpIdx, UndefValue::get(I->getType())); 656 Changed = true; 657 658 // If the leaf is a binary operation of the right kind and we now see 659 // that its multiple original uses were in fact all by nodes belonging 660 // to the expression, then no longer consider it to be a leaf and add 661 // its operands to the expression. 662 if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) { 663 DEBUG(dbgs() << "UNLEAF: " << *Op << " (" << It->second << ")\n"); 664 Worklist.push_back(std::make_pair(BO, It->second)); 665 Leaves.erase(It); 666 continue; 667 } 668 #endif 669 670 // If we still have uses that are not accounted for by the expression 671 // then it is not safe to modify the value. 672 if (!Op->hasOneUse()) 673 continue; 674 675 // No uses outside the expression, try morphing it. 676 Weight = It->second; 677 Leaves.erase(It); // Since the value may be morphed below. 678 } 679 680 // At this point we have a value which, first of all, is not a binary 681 // expression of the right kind, and secondly, is only used inside the 682 // expression. This means that it can safely be modified. See if we 683 // can usefully morph it into an expression of the right kind. 684 assert((!isa<Instruction>(Op) || 685 cast<Instruction>(Op)->getOpcode() != Opcode 686 || (isa<FPMathOperator>(Op) && 687 !cast<Instruction>(Op)->hasUnsafeAlgebra())) && 688 "Should have been handled above!"); 689 assert(Op->hasOneUse() && "Has uses outside the expression tree!"); 690 691 // If this is a multiply expression, turn any internal negations into 692 // multiplies by -1 so they can be reassociated. 693 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op)) 694 if ((Opcode == Instruction::Mul && BinaryOperator::isNeg(BO)) || 695 (Opcode == Instruction::FMul && BinaryOperator::isFNeg(BO))) { 696 DEBUG(dbgs() << "MORPH LEAF: " << *Op << " (" << Weight << ") TO "); 697 BO = LowerNegateToMultiply(BO); 698 DEBUG(dbgs() << *BO << '\n'); 699 Worklist.push_back(std::make_pair(BO, Weight)); 700 Changed = true; 701 continue; 702 } 703 704 // Failed to morph into an expression of the right type. This really is 705 // a leaf. 706 DEBUG(dbgs() << "ADD LEAF: " << *Op << " (" << Weight << ")\n"); 707 assert(!isReassociableOp(Op, Opcode) && "Value was morphed?"); 708 LeafOrder.push_back(Op); 709 Leaves[Op] = Weight; 710 } 711 } 712 713 // The leaves, repeated according to their weights, represent the linearized 714 // form of the expression. 715 for (unsigned i = 0, e = LeafOrder.size(); i != e; ++i) { 716 Value *V = LeafOrder[i]; 717 LeafMap::iterator It = Leaves.find(V); 718 if (It == Leaves.end()) 719 // Node initially thought to be a leaf wasn't. 720 continue; 721 assert(!isReassociableOp(V, Opcode) && "Shouldn't be a leaf!"); 722 APInt Weight = It->second; 723 if (Weight.isMinValue()) 724 // Leaf already output or weight reduction eliminated it. 725 continue; 726 // Ensure the leaf is only output once. 727 It->second = 0; 728 Ops.push_back(std::make_pair(V, Weight)); 729 } 730 731 // For nilpotent operations or addition there may be no operands, for example 732 // because the expression was "X xor X" or consisted of 2^Bitwidth additions: 733 // in both cases the weight reduces to 0 causing the value to be skipped. 734 if (Ops.empty()) { 735 Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, I->getType()); 736 assert(Identity && "Associative operation without identity!"); 737 Ops.push_back(std::make_pair(Identity, APInt(Bitwidth, 1))); 738 } 739 740 return Changed; 741 } 742 743 // RewriteExprTree - Now that the operands for this expression tree are 744 // linearized and optimized, emit them in-order. 745 void Reassociate::RewriteExprTree(BinaryOperator *I, 746 SmallVectorImpl<ValueEntry> &Ops) { 747 assert(Ops.size() > 1 && "Single values should be used directly!"); 748 749 // Since our optimizations should never increase the number of operations, the 750 // new expression can usually be written reusing the existing binary operators 751 // from the original expression tree, without creating any new instructions, 752 // though the rewritten expression may have a completely different topology. 753 // We take care to not change anything if the new expression will be the same 754 // as the original. If more than trivial changes (like commuting operands) 755 // were made then we are obliged to clear out any optional subclass data like 756 // nsw flags. 757 758 /// NodesToRewrite - Nodes from the original expression available for writing 759 /// the new expression into. 760 SmallVector<BinaryOperator*, 8> NodesToRewrite; 761 unsigned Opcode = I->getOpcode(); 762 BinaryOperator *Op = I; 763 764 /// NotRewritable - The operands being written will be the leaves of the new 765 /// expression and must not be used as inner nodes (via NodesToRewrite) by 766 /// mistake. Inner nodes are always reassociable, and usually leaves are not 767 /// (if they were they would have been incorporated into the expression and so 768 /// would not be leaves), so most of the time there is no danger of this. But 769 /// in rare cases a leaf may become reassociable if an optimization kills uses 770 /// of it, or it may momentarily become reassociable during rewriting (below) 771 /// due it being removed as an operand of one of its uses. Ensure that misuse 772 /// of leaf nodes as inner nodes cannot occur by remembering all of the future 773 /// leaves and refusing to reuse any of them as inner nodes. 774 SmallPtrSet<Value*, 8> NotRewritable; 775 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 776 NotRewritable.insert(Ops[i].Op); 777 778 // ExpressionChanged - Non-null if the rewritten expression differs from the 779 // original in some non-trivial way, requiring the clearing of optional flags. 780 // Flags are cleared from the operator in ExpressionChanged up to I inclusive. 781 BinaryOperator *ExpressionChanged = nullptr; 782 for (unsigned i = 0; ; ++i) { 783 // The last operation (which comes earliest in the IR) is special as both 784 // operands will come from Ops, rather than just one with the other being 785 // a subexpression. 786 if (i+2 == Ops.size()) { 787 Value *NewLHS = Ops[i].Op; 788 Value *NewRHS = Ops[i+1].Op; 789 Value *OldLHS = Op->getOperand(0); 790 Value *OldRHS = Op->getOperand(1); 791 792 if (NewLHS == OldLHS && NewRHS == OldRHS) 793 // Nothing changed, leave it alone. 794 break; 795 796 if (NewLHS == OldRHS && NewRHS == OldLHS) { 797 // The order of the operands was reversed. Swap them. 798 DEBUG(dbgs() << "RA: " << *Op << '\n'); 799 Op->swapOperands(); 800 DEBUG(dbgs() << "TO: " << *Op << '\n'); 801 MadeChange = true; 802 ++NumChanged; 803 break; 804 } 805 806 // The new operation differs non-trivially from the original. Overwrite 807 // the old operands with the new ones. 808 DEBUG(dbgs() << "RA: " << *Op << '\n'); 809 if (NewLHS != OldLHS) { 810 BinaryOperator *BO = isReassociableOp(OldLHS, Opcode); 811 if (BO && !NotRewritable.count(BO)) 812 NodesToRewrite.push_back(BO); 813 Op->setOperand(0, NewLHS); 814 } 815 if (NewRHS != OldRHS) { 816 BinaryOperator *BO = isReassociableOp(OldRHS, Opcode); 817 if (BO && !NotRewritable.count(BO)) 818 NodesToRewrite.push_back(BO); 819 Op->setOperand(1, NewRHS); 820 } 821 DEBUG(dbgs() << "TO: " << *Op << '\n'); 822 823 ExpressionChanged = Op; 824 MadeChange = true; 825 ++NumChanged; 826 827 break; 828 } 829 830 // Not the last operation. The left-hand side will be a sub-expression 831 // while the right-hand side will be the current element of Ops. 832 Value *NewRHS = Ops[i].Op; 833 if (NewRHS != Op->getOperand(1)) { 834 DEBUG(dbgs() << "RA: " << *Op << '\n'); 835 if (NewRHS == Op->getOperand(0)) { 836 // The new right-hand side was already present as the left operand. If 837 // we are lucky then swapping the operands will sort out both of them. 838 Op->swapOperands(); 839 } else { 840 // Overwrite with the new right-hand side. 841 BinaryOperator *BO = isReassociableOp(Op->getOperand(1), Opcode); 842 if (BO && !NotRewritable.count(BO)) 843 NodesToRewrite.push_back(BO); 844 Op->setOperand(1, NewRHS); 845 ExpressionChanged = Op; 846 } 847 DEBUG(dbgs() << "TO: " << *Op << '\n'); 848 MadeChange = true; 849 ++NumChanged; 850 } 851 852 // Now deal with the left-hand side. If this is already an operation node 853 // from the original expression then just rewrite the rest of the expression 854 // into it. 855 BinaryOperator *BO = isReassociableOp(Op->getOperand(0), Opcode); 856 if (BO && !NotRewritable.count(BO)) { 857 Op = BO; 858 continue; 859 } 860 861 // Otherwise, grab a spare node from the original expression and use that as 862 // the left-hand side. If there are no nodes left then the optimizers made 863 // an expression with more nodes than the original! This usually means that 864 // they did something stupid but it might mean that the problem was just too 865 // hard (finding the mimimal number of multiplications needed to realize a 866 // multiplication expression is NP-complete). Whatever the reason, smart or 867 // stupid, create a new node if there are none left. 868 BinaryOperator *NewOp; 869 if (NodesToRewrite.empty()) { 870 Constant *Undef = UndefValue::get(I->getType()); 871 NewOp = BinaryOperator::Create(Instruction::BinaryOps(Opcode), 872 Undef, Undef, "", I); 873 if (NewOp->getType()->isFPOrFPVectorTy()) 874 NewOp->setFastMathFlags(I->getFastMathFlags()); 875 } else { 876 NewOp = NodesToRewrite.pop_back_val(); 877 } 878 879 DEBUG(dbgs() << "RA: " << *Op << '\n'); 880 Op->setOperand(0, NewOp); 881 DEBUG(dbgs() << "TO: " << *Op << '\n'); 882 ExpressionChanged = Op; 883 MadeChange = true; 884 ++NumChanged; 885 Op = NewOp; 886 } 887 888 // If the expression changed non-trivially then clear out all subclass data 889 // starting from the operator specified in ExpressionChanged, and compactify 890 // the operators to just before the expression root to guarantee that the 891 // expression tree is dominated by all of Ops. 892 if (ExpressionChanged) 893 do { 894 // Preserve FastMathFlags. 895 if (isa<FPMathOperator>(I)) { 896 FastMathFlags Flags = I->getFastMathFlags(); 897 ExpressionChanged->clearSubclassOptionalData(); 898 ExpressionChanged->setFastMathFlags(Flags); 899 } else 900 ExpressionChanged->clearSubclassOptionalData(); 901 902 if (ExpressionChanged == I) 903 break; 904 ExpressionChanged->moveBefore(I); 905 ExpressionChanged = cast<BinaryOperator>(*ExpressionChanged->user_begin()); 906 } while (1); 907 908 // Throw away any left over nodes from the original expression. 909 for (unsigned i = 0, e = NodesToRewrite.size(); i != e; ++i) 910 RedoInsts.insert(NodesToRewrite[i]); 911 } 912 913 /// NegateValue - Insert instructions before the instruction pointed to by BI, 914 /// that computes the negative version of the value specified. The negative 915 /// version of the value is returned, and BI is left pointing at the instruction 916 /// that should be processed next by the reassociation pass. 917 static Value *NegateValue(Value *V, Instruction *BI) { 918 if (Constant *C = dyn_cast<Constant>(V)) { 919 if (C->getType()->isFPOrFPVectorTy()) { 920 return ConstantExpr::getFNeg(C); 921 } 922 return ConstantExpr::getNeg(C); 923 } 924 925 926 // We are trying to expose opportunity for reassociation. One of the things 927 // that we want to do to achieve this is to push a negation as deep into an 928 // expression chain as possible, to expose the add instructions. In practice, 929 // this means that we turn this: 930 // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 931 // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 932 // the constants. We assume that instcombine will clean up the mess later if 933 // we introduce tons of unnecessary negation instructions. 934 // 935 if (BinaryOperator *I = 936 isReassociableOp(V, Instruction::Add, Instruction::FAdd)) { 937 // Push the negates through the add. 938 I->setOperand(0, NegateValue(I->getOperand(0), BI)); 939 I->setOperand(1, NegateValue(I->getOperand(1), BI)); 940 941 // We must move the add instruction here, because the neg instructions do 942 // not dominate the old add instruction in general. By moving it, we are 943 // assured that the neg instructions we just inserted dominate the 944 // instruction we are about to insert after them. 945 // 946 I->moveBefore(BI); 947 I->setName(I->getName()+".neg"); 948 return I; 949 } 950 951 // Okay, we need to materialize a negated version of V with an instruction. 952 // Scan the use lists of V to see if we have one already. 953 for (User *U : V->users()) { 954 if (!BinaryOperator::isNeg(U) && !BinaryOperator::isFNeg(U)) 955 continue; 956 957 // We found one! Now we have to make sure that the definition dominates 958 // this use. We do this by moving it to the entry block (if it is a 959 // non-instruction value) or right after the definition. These negates will 960 // be zapped by reassociate later, so we don't need much finesse here. 961 BinaryOperator *TheNeg = cast<BinaryOperator>(U); 962 963 // Verify that the negate is in this function, V might be a constant expr. 964 if (TheNeg->getParent()->getParent() != BI->getParent()->getParent()) 965 continue; 966 967 BasicBlock::iterator InsertPt; 968 if (Instruction *InstInput = dyn_cast<Instruction>(V)) { 969 if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) { 970 InsertPt = II->getNormalDest()->begin(); 971 } else { 972 InsertPt = InstInput; 973 ++InsertPt; 974 } 975 while (isa<PHINode>(InsertPt)) ++InsertPt; 976 } else { 977 InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin(); 978 } 979 TheNeg->moveBefore(InsertPt); 980 return TheNeg; 981 } 982 983 // Insert a 'neg' instruction that subtracts the value from zero to get the 984 // negation. 985 return CreateNeg(V, V->getName() + ".neg", BI, BI); 986 } 987 988 /// ShouldBreakUpSubtract - Return true if we should break up this subtract of 989 /// X-Y into (X + -Y). 990 static bool ShouldBreakUpSubtract(Instruction *Sub) { 991 // If this is a negation, we can't split it up! 992 if (BinaryOperator::isNeg(Sub) || BinaryOperator::isFNeg(Sub)) 993 return false; 994 995 // Don't breakup X - undef. 996 if (isa<UndefValue>(Sub->getOperand(1))) 997 return false; 998 999 // Don't bother to break this up unless either the LHS is an associable add or 1000 // subtract or if this is only used by one. 1001 Value *V0 = Sub->getOperand(0); 1002 if (isReassociableOp(V0, Instruction::Add, Instruction::FAdd) || 1003 isReassociableOp(V0, Instruction::Sub, Instruction::FSub)) 1004 return true; 1005 Value *V1 = Sub->getOperand(1); 1006 if (isReassociableOp(V1, Instruction::Add, Instruction::FAdd) || 1007 isReassociableOp(V1, Instruction::Sub, Instruction::FSub)) 1008 return true; 1009 Value *VB = Sub->user_back(); 1010 if (Sub->hasOneUse() && 1011 (isReassociableOp(VB, Instruction::Add, Instruction::FAdd) || 1012 isReassociableOp(VB, Instruction::Sub, Instruction::FSub))) 1013 return true; 1014 1015 return false; 1016 } 1017 1018 /// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 1019 /// only used by an add, transform this into (X+(0-Y)) to promote better 1020 /// reassociation. 1021 static BinaryOperator *BreakUpSubtract(Instruction *Sub) { 1022 // Convert a subtract into an add and a neg instruction. This allows sub 1023 // instructions to be commuted with other add instructions. 1024 // 1025 // Calculate the negative value of Operand 1 of the sub instruction, 1026 // and set it as the RHS of the add instruction we just made. 1027 // 1028 Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 1029 BinaryOperator *New = CreateAdd(Sub->getOperand(0), NegVal, "", Sub, Sub); 1030 Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op. 1031 Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op. 1032 New->takeName(Sub); 1033 1034 // Everyone now refers to the add instruction. 1035 Sub->replaceAllUsesWith(New); 1036 New->setDebugLoc(Sub->getDebugLoc()); 1037 1038 DEBUG(dbgs() << "Negated: " << *New << '\n'); 1039 return New; 1040 } 1041 1042 /// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 1043 /// by one, change this into a multiply by a constant to assist with further 1044 /// reassociation. 1045 static BinaryOperator *ConvertShiftToMul(Instruction *Shl) { 1046 Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 1047 MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 1048 1049 BinaryOperator *Mul = 1050 BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl); 1051 Shl->setOperand(0, UndefValue::get(Shl->getType())); // Drop use of op. 1052 Mul->takeName(Shl); 1053 1054 // Everyone now refers to the mul instruction. 1055 Shl->replaceAllUsesWith(Mul); 1056 Mul->setDebugLoc(Shl->getDebugLoc()); 1057 1058 // We can safely preserve the nuw flag in all cases. It's also safe to turn a 1059 // nuw nsw shl into a nuw nsw mul. However, nsw in isolation requires special 1060 // handling. 1061 bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap(); 1062 bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap(); 1063 if (NSW && NUW) 1064 Mul->setHasNoSignedWrap(true); 1065 Mul->setHasNoUnsignedWrap(NUW); 1066 return Mul; 1067 } 1068 1069 /// FindInOperandList - Scan backwards and forwards among values with the same 1070 /// rank as element i to see if X exists. If X does not exist, return i. This 1071 /// is useful when scanning for 'x' when we see '-x' because they both get the 1072 /// same rank. 1073 static unsigned FindInOperandList(SmallVectorImpl<ValueEntry> &Ops, unsigned i, 1074 Value *X) { 1075 unsigned XRank = Ops[i].Rank; 1076 unsigned e = Ops.size(); 1077 for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) { 1078 if (Ops[j].Op == X) 1079 return j; 1080 if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op)) 1081 if (Instruction *I2 = dyn_cast<Instruction>(X)) 1082 if (I1->isIdenticalTo(I2)) 1083 return j; 1084 } 1085 // Scan backwards. 1086 for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) { 1087 if (Ops[j].Op == X) 1088 return j; 1089 if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op)) 1090 if (Instruction *I2 = dyn_cast<Instruction>(X)) 1091 if (I1->isIdenticalTo(I2)) 1092 return j; 1093 } 1094 return i; 1095 } 1096 1097 /// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together 1098 /// and returning the result. Insert the tree before I. 1099 static Value *EmitAddTreeOfValues(Instruction *I, 1100 SmallVectorImpl<WeakVH> &Ops){ 1101 if (Ops.size() == 1) return Ops.back(); 1102 1103 Value *V1 = Ops.back(); 1104 Ops.pop_back(); 1105 Value *V2 = EmitAddTreeOfValues(I, Ops); 1106 return CreateAdd(V2, V1, "tmp", I, I); 1107 } 1108 1109 /// RemoveFactorFromExpression - If V is an expression tree that is a 1110 /// multiplication sequence, and if this sequence contains a multiply by Factor, 1111 /// remove Factor from the tree and return the new tree. 1112 Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { 1113 BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul); 1114 if (!BO) 1115 return nullptr; 1116 1117 SmallVector<RepeatedValue, 8> Tree; 1118 MadeChange |= LinearizeExprTree(BO, Tree); 1119 SmallVector<ValueEntry, 8> Factors; 1120 Factors.reserve(Tree.size()); 1121 for (unsigned i = 0, e = Tree.size(); i != e; ++i) { 1122 RepeatedValue E = Tree[i]; 1123 Factors.append(E.second.getZExtValue(), 1124 ValueEntry(getRank(E.first), E.first)); 1125 } 1126 1127 bool FoundFactor = false; 1128 bool NeedsNegate = false; 1129 for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 1130 if (Factors[i].Op == Factor) { 1131 FoundFactor = true; 1132 Factors.erase(Factors.begin()+i); 1133 break; 1134 } 1135 1136 // If this is a negative version of this factor, remove it. 1137 if (ConstantInt *FC1 = dyn_cast<ConstantInt>(Factor)) { 1138 if (ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op)) 1139 if (FC1->getValue() == -FC2->getValue()) { 1140 FoundFactor = NeedsNegate = true; 1141 Factors.erase(Factors.begin()+i); 1142 break; 1143 } 1144 } else if (ConstantFP *FC1 = dyn_cast<ConstantFP>(Factor)) { 1145 if (ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[i].Op)) { 1146 APFloat F1(FC1->getValueAPF()); 1147 APFloat F2(FC2->getValueAPF()); 1148 F2.changeSign(); 1149 if (F1.compare(F2) == APFloat::cmpEqual) { 1150 FoundFactor = NeedsNegate = true; 1151 Factors.erase(Factors.begin() + i); 1152 break; 1153 } 1154 } 1155 } 1156 } 1157 1158 if (!FoundFactor) { 1159 // Make sure to restore the operands to the expression tree. 1160 RewriteExprTree(BO, Factors); 1161 return nullptr; 1162 } 1163 1164 BasicBlock::iterator InsertPt = BO; ++InsertPt; 1165 1166 // If this was just a single multiply, remove the multiply and return the only 1167 // remaining operand. 1168 if (Factors.size() == 1) { 1169 RedoInsts.insert(BO); 1170 V = Factors[0].Op; 1171 } else { 1172 RewriteExprTree(BO, Factors); 1173 V = BO; 1174 } 1175 1176 if (NeedsNegate) 1177 V = CreateNeg(V, "neg", InsertPt, BO); 1178 1179 return V; 1180 } 1181 1182 /// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively 1183 /// add its operands as factors, otherwise add V to the list of factors. 1184 /// 1185 /// Ops is the top-level list of add operands we're trying to factor. 1186 static void FindSingleUseMultiplyFactors(Value *V, 1187 SmallVectorImpl<Value*> &Factors, 1188 const SmallVectorImpl<ValueEntry> &Ops) { 1189 BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul); 1190 if (!BO) { 1191 Factors.push_back(V); 1192 return; 1193 } 1194 1195 // Otherwise, add the LHS and RHS to the list of factors. 1196 FindSingleUseMultiplyFactors(BO->getOperand(1), Factors, Ops); 1197 FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops); 1198 } 1199 1200 /// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor' 1201 /// instruction. This optimizes based on identities. If it can be reduced to 1202 /// a single Value, it is returned, otherwise the Ops list is mutated as 1203 /// necessary. 1204 static Value *OptimizeAndOrXor(unsigned Opcode, 1205 SmallVectorImpl<ValueEntry> &Ops) { 1206 // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 1207 // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 1208 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1209 // First, check for X and ~X in the operand list. 1210 assert(i < Ops.size()); 1211 if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 1212 Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 1213 unsigned FoundX = FindInOperandList(Ops, i, X); 1214 if (FoundX != i) { 1215 if (Opcode == Instruction::And) // ...&X&~X = 0 1216 return Constant::getNullValue(X->getType()); 1217 1218 if (Opcode == Instruction::Or) // ...|X|~X = -1 1219 return Constant::getAllOnesValue(X->getType()); 1220 } 1221 } 1222 1223 // Next, check for duplicate pairs of values, which we assume are next to 1224 // each other, due to our sorting criteria. 1225 assert(i < Ops.size()); 1226 if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 1227 if (Opcode == Instruction::And || Opcode == Instruction::Or) { 1228 // Drop duplicate values for And and Or. 1229 Ops.erase(Ops.begin()+i); 1230 --i; --e; 1231 ++NumAnnihil; 1232 continue; 1233 } 1234 1235 // Drop pairs of values for Xor. 1236 assert(Opcode == Instruction::Xor); 1237 if (e == 2) 1238 return Constant::getNullValue(Ops[0].Op->getType()); 1239 1240 // Y ^ X^X -> Y 1241 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 1242 i -= 1; e -= 2; 1243 ++NumAnnihil; 1244 } 1245 } 1246 return nullptr; 1247 } 1248 1249 /// Helper funciton of CombineXorOpnd(). It creates a bitwise-and 1250 /// instruction with the given two operands, and return the resulting 1251 /// instruction. There are two special cases: 1) if the constant operand is 0, 1252 /// it will return NULL. 2) if the constant is ~0, the symbolic operand will 1253 /// be returned. 1254 static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd, 1255 const APInt &ConstOpnd) { 1256 if (ConstOpnd != 0) { 1257 if (!ConstOpnd.isAllOnesValue()) { 1258 LLVMContext &Ctx = Opnd->getType()->getContext(); 1259 Instruction *I; 1260 I = BinaryOperator::CreateAnd(Opnd, ConstantInt::get(Ctx, ConstOpnd), 1261 "and.ra", InsertBefore); 1262 I->setDebugLoc(InsertBefore->getDebugLoc()); 1263 return I; 1264 } 1265 return Opnd; 1266 } 1267 return nullptr; 1268 } 1269 1270 // Helper function of OptimizeXor(). It tries to simplify "Opnd1 ^ ConstOpnd" 1271 // into "R ^ C", where C would be 0, and R is a symbolic value. 1272 // 1273 // If it was successful, true is returned, and the "R" and "C" is returned 1274 // via "Res" and "ConstOpnd", respectively; otherwise, false is returned, 1275 // and both "Res" and "ConstOpnd" remain unchanged. 1276 // 1277 bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, 1278 APInt &ConstOpnd, Value *&Res) { 1279 // Xor-Rule 1: (x | c1) ^ c2 = (x | c1) ^ (c1 ^ c1) ^ c2 1280 // = ((x | c1) ^ c1) ^ (c1 ^ c2) 1281 // = (x & ~c1) ^ (c1 ^ c2) 1282 // It is useful only when c1 == c2. 1283 if (Opnd1->isOrExpr() && Opnd1->getConstPart() != 0) { 1284 if (!Opnd1->getValue()->hasOneUse()) 1285 return false; 1286 1287 const APInt &C1 = Opnd1->getConstPart(); 1288 if (C1 != ConstOpnd) 1289 return false; 1290 1291 Value *X = Opnd1->getSymbolicPart(); 1292 Res = createAndInstr(I, X, ~C1); 1293 // ConstOpnd was C2, now C1 ^ C2. 1294 ConstOpnd ^= C1; 1295 1296 if (Instruction *T = dyn_cast<Instruction>(Opnd1->getValue())) 1297 RedoInsts.insert(T); 1298 return true; 1299 } 1300 return false; 1301 } 1302 1303 1304 // Helper function of OptimizeXor(). It tries to simplify 1305 // "Opnd1 ^ Opnd2 ^ ConstOpnd" into "R ^ C", where C would be 0, and R is a 1306 // symbolic value. 1307 // 1308 // If it was successful, true is returned, and the "R" and "C" is returned 1309 // via "Res" and "ConstOpnd", respectively (If the entire expression is 1310 // evaluated to a constant, the Res is set to NULL); otherwise, false is 1311 // returned, and both "Res" and "ConstOpnd" remain unchanged. 1312 bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2, 1313 APInt &ConstOpnd, Value *&Res) { 1314 Value *X = Opnd1->getSymbolicPart(); 1315 if (X != Opnd2->getSymbolicPart()) 1316 return false; 1317 1318 // This many instruction become dead.(At least "Opnd1 ^ Opnd2" will die.) 1319 int DeadInstNum = 1; 1320 if (Opnd1->getValue()->hasOneUse()) 1321 DeadInstNum++; 1322 if (Opnd2->getValue()->hasOneUse()) 1323 DeadInstNum++; 1324 1325 // Xor-Rule 2: 1326 // (x | c1) ^ (x & c2) 1327 // = (x|c1) ^ (x&c2) ^ (c1 ^ c1) = ((x|c1) ^ c1) ^ (x & c2) ^ c1 1328 // = (x & ~c1) ^ (x & c2) ^ c1 // Xor-Rule 1 1329 // = (x & c3) ^ c1, where c3 = ~c1 ^ c2 // Xor-rule 3 1330 // 1331 if (Opnd1->isOrExpr() != Opnd2->isOrExpr()) { 1332 if (Opnd2->isOrExpr()) 1333 std::swap(Opnd1, Opnd2); 1334 1335 const APInt &C1 = Opnd1->getConstPart(); 1336 const APInt &C2 = Opnd2->getConstPart(); 1337 APInt C3((~C1) ^ C2); 1338 1339 // Do not increase code size! 1340 if (C3 != 0 && !C3.isAllOnesValue()) { 1341 int NewInstNum = ConstOpnd != 0 ? 1 : 2; 1342 if (NewInstNum > DeadInstNum) 1343 return false; 1344 } 1345 1346 Res = createAndInstr(I, X, C3); 1347 ConstOpnd ^= C1; 1348 1349 } else if (Opnd1->isOrExpr()) { 1350 // Xor-Rule 3: (x | c1) ^ (x | c2) = (x & c3) ^ c3 where c3 = c1 ^ c2 1351 // 1352 const APInt &C1 = Opnd1->getConstPart(); 1353 const APInt &C2 = Opnd2->getConstPart(); 1354 APInt C3 = C1 ^ C2; 1355 1356 // Do not increase code size 1357 if (C3 != 0 && !C3.isAllOnesValue()) { 1358 int NewInstNum = ConstOpnd != 0 ? 1 : 2; 1359 if (NewInstNum > DeadInstNum) 1360 return false; 1361 } 1362 1363 Res = createAndInstr(I, X, C3); 1364 ConstOpnd ^= C3; 1365 } else { 1366 // Xor-Rule 4: (x & c1) ^ (x & c2) = (x & (c1^c2)) 1367 // 1368 const APInt &C1 = Opnd1->getConstPart(); 1369 const APInt &C2 = Opnd2->getConstPart(); 1370 APInt C3 = C1 ^ C2; 1371 Res = createAndInstr(I, X, C3); 1372 } 1373 1374 // Put the original operands in the Redo list; hope they will be deleted 1375 // as dead code. 1376 if (Instruction *T = dyn_cast<Instruction>(Opnd1->getValue())) 1377 RedoInsts.insert(T); 1378 if (Instruction *T = dyn_cast<Instruction>(Opnd2->getValue())) 1379 RedoInsts.insert(T); 1380 1381 return true; 1382 } 1383 1384 /// Optimize a series of operands to an 'xor' instruction. If it can be reduced 1385 /// to a single Value, it is returned, otherwise the Ops list is mutated as 1386 /// necessary. 1387 Value *Reassociate::OptimizeXor(Instruction *I, 1388 SmallVectorImpl<ValueEntry> &Ops) { 1389 if (Value *V = OptimizeAndOrXor(Instruction::Xor, Ops)) 1390 return V; 1391 1392 if (Ops.size() == 1) 1393 return nullptr; 1394 1395 SmallVector<XorOpnd, 8> Opnds; 1396 SmallVector<XorOpnd*, 8> OpndPtrs; 1397 Type *Ty = Ops[0].Op->getType(); 1398 APInt ConstOpnd(Ty->getIntegerBitWidth(), 0); 1399 1400 // Step 1: Convert ValueEntry to XorOpnd 1401 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1402 Value *V = Ops[i].Op; 1403 if (!isa<ConstantInt>(V)) { 1404 XorOpnd O(V); 1405 O.setSymbolicRank(getRank(O.getSymbolicPart())); 1406 Opnds.push_back(O); 1407 } else 1408 ConstOpnd ^= cast<ConstantInt>(V)->getValue(); 1409 } 1410 1411 // NOTE: From this point on, do *NOT* add/delete element to/from "Opnds". 1412 // It would otherwise invalidate the "Opnds"'s iterator, and hence invalidate 1413 // the "OpndPtrs" as well. For the similar reason, do not fuse this loop 1414 // with the previous loop --- the iterator of the "Opnds" may be invalidated 1415 // when new elements are added to the vector. 1416 for (unsigned i = 0, e = Opnds.size(); i != e; ++i) 1417 OpndPtrs.push_back(&Opnds[i]); 1418 1419 // Step 2: Sort the Xor-Operands in a way such that the operands containing 1420 // the same symbolic value cluster together. For instance, the input operand 1421 // sequence ("x | 123", "y & 456", "x & 789") will be sorted into: 1422 // ("x | 123", "x & 789", "y & 456"). 1423 std::stable_sort(OpndPtrs.begin(), OpndPtrs.end(), XorOpnd::PtrSortFunctor()); 1424 1425 // Step 3: Combine adjacent operands 1426 XorOpnd *PrevOpnd = nullptr; 1427 bool Changed = false; 1428 for (unsigned i = 0, e = Opnds.size(); i < e; i++) { 1429 XorOpnd *CurrOpnd = OpndPtrs[i]; 1430 // The combined value 1431 Value *CV; 1432 1433 // Step 3.1: Try simplifying "CurrOpnd ^ ConstOpnd" 1434 if (ConstOpnd != 0 && CombineXorOpnd(I, CurrOpnd, ConstOpnd, CV)) { 1435 Changed = true; 1436 if (CV) 1437 *CurrOpnd = XorOpnd(CV); 1438 else { 1439 CurrOpnd->Invalidate(); 1440 continue; 1441 } 1442 } 1443 1444 if (!PrevOpnd || CurrOpnd->getSymbolicPart() != PrevOpnd->getSymbolicPart()) { 1445 PrevOpnd = CurrOpnd; 1446 continue; 1447 } 1448 1449 // step 3.2: When previous and current operands share the same symbolic 1450 // value, try to simplify "PrevOpnd ^ CurrOpnd ^ ConstOpnd" 1451 // 1452 if (CombineXorOpnd(I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) { 1453 // Remove previous operand 1454 PrevOpnd->Invalidate(); 1455 if (CV) { 1456 *CurrOpnd = XorOpnd(CV); 1457 PrevOpnd = CurrOpnd; 1458 } else { 1459 CurrOpnd->Invalidate(); 1460 PrevOpnd = nullptr; 1461 } 1462 Changed = true; 1463 } 1464 } 1465 1466 // Step 4: Reassemble the Ops 1467 if (Changed) { 1468 Ops.clear(); 1469 for (unsigned int i = 0, e = Opnds.size(); i < e; i++) { 1470 XorOpnd &O = Opnds[i]; 1471 if (O.isInvalid()) 1472 continue; 1473 ValueEntry VE(getRank(O.getValue()), O.getValue()); 1474 Ops.push_back(VE); 1475 } 1476 if (ConstOpnd != 0) { 1477 Value *C = ConstantInt::get(Ty->getContext(), ConstOpnd); 1478 ValueEntry VE(getRank(C), C); 1479 Ops.push_back(VE); 1480 } 1481 int Sz = Ops.size(); 1482 if (Sz == 1) 1483 return Ops.back().Op; 1484 else if (Sz == 0) { 1485 assert(ConstOpnd == 0); 1486 return ConstantInt::get(Ty->getContext(), ConstOpnd); 1487 } 1488 } 1489 1490 return nullptr; 1491 } 1492 1493 /// OptimizeAdd - Optimize a series of operands to an 'add' instruction. This 1494 /// optimizes based on identities. If it can be reduced to a single Value, it 1495 /// is returned, otherwise the Ops list is mutated as necessary. 1496 Value *Reassociate::OptimizeAdd(Instruction *I, 1497 SmallVectorImpl<ValueEntry> &Ops) { 1498 // Scan the operand lists looking for X and -X pairs. If we find any, we 1499 // can simplify expressions like X+-X == 0 and X+~X ==-1. While we're at it, 1500 // scan for any 1501 // duplicates. We want to canonicalize Y+Y+Y+Z -> 3*Y+Z. 1502 1503 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1504 Value *TheOp = Ops[i].Op; 1505 // Check to see if we've seen this operand before. If so, we factor all 1506 // instances of the operand together. Due to our sorting criteria, we know 1507 // that these need to be next to each other in the vector. 1508 if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) { 1509 // Rescan the list, remove all instances of this operand from the expr. 1510 unsigned NumFound = 0; 1511 do { 1512 Ops.erase(Ops.begin()+i); 1513 ++NumFound; 1514 } while (i != Ops.size() && Ops[i].Op == TheOp); 1515 1516 DEBUG(dbgs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n'); 1517 ++NumFactor; 1518 1519 // Insert a new multiply. 1520 Type *Ty = TheOp->getType(); 1521 Constant *C = Ty->isIntOrIntVectorTy() ? 1522 ConstantInt::get(Ty, NumFound) : ConstantFP::get(Ty, NumFound); 1523 Instruction *Mul = CreateMul(TheOp, C, "factor", I, I); 1524 1525 // Now that we have inserted a multiply, optimize it. This allows us to 1526 // handle cases that require multiple factoring steps, such as this: 1527 // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6 1528 RedoInsts.insert(Mul); 1529 1530 // If every add operand was a duplicate, return the multiply. 1531 if (Ops.empty()) 1532 return Mul; 1533 1534 // Otherwise, we had some input that didn't have the dupe, such as 1535 // "A + A + B" -> "A*2 + B". Add the new multiply to the list of 1536 // things being added by this operation. 1537 Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul)); 1538 1539 --i; 1540 e = Ops.size(); 1541 continue; 1542 } 1543 1544 // Check for X and -X or X and ~X in the operand list. 1545 if (!BinaryOperator::isNeg(TheOp) && !BinaryOperator::isFNeg(TheOp) && 1546 !BinaryOperator::isNot(TheOp)) 1547 continue; 1548 1549 Value *X = nullptr; 1550 if (BinaryOperator::isNeg(TheOp) || BinaryOperator::isFNeg(TheOp)) 1551 X = BinaryOperator::getNegArgument(TheOp); 1552 else if (BinaryOperator::isNot(TheOp)) 1553 X = BinaryOperator::getNotArgument(TheOp); 1554 1555 unsigned FoundX = FindInOperandList(Ops, i, X); 1556 if (FoundX == i) 1557 continue; 1558 1559 // Remove X and -X from the operand list. 1560 if (Ops.size() == 2 && 1561 (BinaryOperator::isNeg(TheOp) || BinaryOperator::isFNeg(TheOp))) 1562 return Constant::getNullValue(X->getType()); 1563 1564 // Remove X and ~X from the operand list. 1565 if (Ops.size() == 2 && BinaryOperator::isNot(TheOp)) 1566 return Constant::getAllOnesValue(X->getType()); 1567 1568 Ops.erase(Ops.begin()+i); 1569 if (i < FoundX) 1570 --FoundX; 1571 else 1572 --i; // Need to back up an extra one. 1573 Ops.erase(Ops.begin()+FoundX); 1574 ++NumAnnihil; 1575 --i; // Revisit element. 1576 e -= 2; // Removed two elements. 1577 1578 // if X and ~X we append -1 to the operand list. 1579 if (BinaryOperator::isNot(TheOp)) { 1580 Value *V = Constant::getAllOnesValue(X->getType()); 1581 Ops.insert(Ops.end(), ValueEntry(getRank(V), V)); 1582 e += 1; 1583 } 1584 } 1585 1586 // Scan the operand list, checking to see if there are any common factors 1587 // between operands. Consider something like A*A+A*B*C+D. We would like to 1588 // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies. 1589 // To efficiently find this, we count the number of times a factor occurs 1590 // for any ADD operands that are MULs. 1591 DenseMap<Value*, unsigned> FactorOccurrences; 1592 1593 // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4) 1594 // where they are actually the same multiply. 1595 unsigned MaxOcc = 0; 1596 Value *MaxOccVal = nullptr; 1597 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1598 BinaryOperator *BOp = 1599 isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul); 1600 if (!BOp) 1601 continue; 1602 1603 // Compute all of the factors of this added value. 1604 SmallVector<Value*, 8> Factors; 1605 FindSingleUseMultiplyFactors(BOp, Factors, Ops); 1606 assert(Factors.size() > 1 && "Bad linearize!"); 1607 1608 // Add one to FactorOccurrences for each unique factor in this op. 1609 SmallPtrSet<Value*, 8> Duplicates; 1610 for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 1611 Value *Factor = Factors[i]; 1612 if (!Duplicates.insert(Factor).second) 1613 continue; 1614 1615 unsigned Occ = ++FactorOccurrences[Factor]; 1616 if (Occ > MaxOcc) { 1617 MaxOcc = Occ; 1618 MaxOccVal = Factor; 1619 } 1620 1621 // If Factor is a negative constant, add the negated value as a factor 1622 // because we can percolate the negate out. Watch for minint, which 1623 // cannot be positivified. 1624 if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) { 1625 if (CI->isNegative() && !CI->isMinValue(true)) { 1626 Factor = ConstantInt::get(CI->getContext(), -CI->getValue()); 1627 assert(!Duplicates.count(Factor) && 1628 "Shouldn't have two constant factors, missed a canonicalize"); 1629 unsigned Occ = ++FactorOccurrences[Factor]; 1630 if (Occ > MaxOcc) { 1631 MaxOcc = Occ; 1632 MaxOccVal = Factor; 1633 } 1634 } 1635 } else if (ConstantFP *CF = dyn_cast<ConstantFP>(Factor)) { 1636 if (CF->isNegative()) { 1637 APFloat F(CF->getValueAPF()); 1638 F.changeSign(); 1639 Factor = ConstantFP::get(CF->getContext(), F); 1640 assert(!Duplicates.count(Factor) && 1641 "Shouldn't have two constant factors, missed a canonicalize"); 1642 unsigned Occ = ++FactorOccurrences[Factor]; 1643 if (Occ > MaxOcc) { 1644 MaxOcc = Occ; 1645 MaxOccVal = Factor; 1646 } 1647 } 1648 } 1649 } 1650 } 1651 1652 // If any factor occurred more than one time, we can pull it out. 1653 if (MaxOcc > 1) { 1654 DEBUG(dbgs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n'); 1655 ++NumFactor; 1656 1657 // Create a new instruction that uses the MaxOccVal twice. If we don't do 1658 // this, we could otherwise run into situations where removing a factor 1659 // from an expression will drop a use of maxocc, and this can cause 1660 // RemoveFactorFromExpression on successive values to behave differently. 1661 Instruction *DummyInst = 1662 I->getType()->isIntOrIntVectorTy() 1663 ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal) 1664 : BinaryOperator::CreateFAdd(MaxOccVal, MaxOccVal); 1665 1666 SmallVector<WeakVH, 4> NewMulOps; 1667 for (unsigned i = 0; i != Ops.size(); ++i) { 1668 // Only try to remove factors from expressions we're allowed to. 1669 BinaryOperator *BOp = 1670 isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul); 1671 if (!BOp) 1672 continue; 1673 1674 if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { 1675 // The factorized operand may occur several times. Convert them all in 1676 // one fell swoop. 1677 for (unsigned j = Ops.size(); j != i;) { 1678 --j; 1679 if (Ops[j].Op == Ops[i].Op) { 1680 NewMulOps.push_back(V); 1681 Ops.erase(Ops.begin()+j); 1682 } 1683 } 1684 --i; 1685 } 1686 } 1687 1688 // No need for extra uses anymore. 1689 delete DummyInst; 1690 1691 unsigned NumAddedValues = NewMulOps.size(); 1692 Value *V = EmitAddTreeOfValues(I, NewMulOps); 1693 1694 // Now that we have inserted the add tree, optimize it. This allows us to 1695 // handle cases that require multiple factoring steps, such as this: 1696 // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C)) 1697 assert(NumAddedValues > 1 && "Each occurrence should contribute a value"); 1698 (void)NumAddedValues; 1699 if (Instruction *VI = dyn_cast<Instruction>(V)) 1700 RedoInsts.insert(VI); 1701 1702 // Create the multiply. 1703 Instruction *V2 = CreateMul(V, MaxOccVal, "tmp", I, I); 1704 1705 // Rerun associate on the multiply in case the inner expression turned into 1706 // a multiply. We want to make sure that we keep things in canonical form. 1707 RedoInsts.insert(V2); 1708 1709 // If every add operand included the factor (e.g. "A*B + A*C"), then the 1710 // entire result expression is just the multiply "A*(B+C)". 1711 if (Ops.empty()) 1712 return V2; 1713 1714 // Otherwise, we had some input that didn't have the factor, such as 1715 // "A*B + A*C + D" -> "A*(B+C) + D". Add the new multiply to the list of 1716 // things being added by this operation. 1717 Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); 1718 } 1719 1720 return nullptr; 1721 } 1722 1723 /// \brief Build up a vector of value/power pairs factoring a product. 1724 /// 1725 /// Given a series of multiplication operands, build a vector of factors and 1726 /// the powers each is raised to when forming the final product. Sort them in 1727 /// the order of descending power. 1728 /// 1729 /// (x*x) -> [(x, 2)] 1730 /// ((x*x)*x) -> [(x, 3)] 1731 /// ((((x*y)*x)*y)*x) -> [(x, 3), (y, 2)] 1732 /// 1733 /// \returns Whether any factors have a power greater than one. 1734 bool Reassociate::collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops, 1735 SmallVectorImpl<Factor> &Factors) { 1736 // FIXME: Have Ops be (ValueEntry, Multiplicity) pairs, simplifying this. 1737 // Compute the sum of powers of simplifiable factors. 1738 unsigned FactorPowerSum = 0; 1739 for (unsigned Idx = 1, Size = Ops.size(); Idx < Size; ++Idx) { 1740 Value *Op = Ops[Idx-1].Op; 1741 1742 // Count the number of occurrences of this value. 1743 unsigned Count = 1; 1744 for (; Idx < Size && Ops[Idx].Op == Op; ++Idx) 1745 ++Count; 1746 // Track for simplification all factors which occur 2 or more times. 1747 if (Count > 1) 1748 FactorPowerSum += Count; 1749 } 1750 1751 // We can only simplify factors if the sum of the powers of our simplifiable 1752 // factors is 4 or higher. When that is the case, we will *always* have 1753 // a simplification. This is an important invariant to prevent cyclicly 1754 // trying to simplify already minimal formations. 1755 if (FactorPowerSum < 4) 1756 return false; 1757 1758 // Now gather the simplifiable factors, removing them from Ops. 1759 FactorPowerSum = 0; 1760 for (unsigned Idx = 1; Idx < Ops.size(); ++Idx) { 1761 Value *Op = Ops[Idx-1].Op; 1762 1763 // Count the number of occurrences of this value. 1764 unsigned Count = 1; 1765 for (; Idx < Ops.size() && Ops[Idx].Op == Op; ++Idx) 1766 ++Count; 1767 if (Count == 1) 1768 continue; 1769 // Move an even number of occurrences to Factors. 1770 Count &= ~1U; 1771 Idx -= Count; 1772 FactorPowerSum += Count; 1773 Factors.push_back(Factor(Op, Count)); 1774 Ops.erase(Ops.begin()+Idx, Ops.begin()+Idx+Count); 1775 } 1776 1777 // None of the adjustments above should have reduced the sum of factor powers 1778 // below our mininum of '4'. 1779 assert(FactorPowerSum >= 4); 1780 1781 std::stable_sort(Factors.begin(), Factors.end(), Factor::PowerDescendingSorter()); 1782 return true; 1783 } 1784 1785 /// \brief Build a tree of multiplies, computing the product of Ops. 1786 static Value *buildMultiplyTree(IRBuilder<> &Builder, 1787 SmallVectorImpl<Value*> &Ops) { 1788 if (Ops.size() == 1) 1789 return Ops.back(); 1790 1791 Value *LHS = Ops.pop_back_val(); 1792 do { 1793 if (LHS->getType()->isIntOrIntVectorTy()) 1794 LHS = Builder.CreateMul(LHS, Ops.pop_back_val()); 1795 else 1796 LHS = Builder.CreateFMul(LHS, Ops.pop_back_val()); 1797 } while (!Ops.empty()); 1798 1799 return LHS; 1800 } 1801 1802 /// \brief Build a minimal multiplication DAG for (a^x)*(b^y)*(c^z)*... 1803 /// 1804 /// Given a vector of values raised to various powers, where no two values are 1805 /// equal and the powers are sorted in decreasing order, compute the minimal 1806 /// DAG of multiplies to compute the final product, and return that product 1807 /// value. 1808 Value *Reassociate::buildMinimalMultiplyDAG(IRBuilder<> &Builder, 1809 SmallVectorImpl<Factor> &Factors) { 1810 assert(Factors[0].Power); 1811 SmallVector<Value *, 4> OuterProduct; 1812 for (unsigned LastIdx = 0, Idx = 1, Size = Factors.size(); 1813 Idx < Size && Factors[Idx].Power > 0; ++Idx) { 1814 if (Factors[Idx].Power != Factors[LastIdx].Power) { 1815 LastIdx = Idx; 1816 continue; 1817 } 1818 1819 // We want to multiply across all the factors with the same power so that 1820 // we can raise them to that power as a single entity. Build a mini tree 1821 // for that. 1822 SmallVector<Value *, 4> InnerProduct; 1823 InnerProduct.push_back(Factors[LastIdx].Base); 1824 do { 1825 InnerProduct.push_back(Factors[Idx].Base); 1826 ++Idx; 1827 } while (Idx < Size && Factors[Idx].Power == Factors[LastIdx].Power); 1828 1829 // Reset the base value of the first factor to the new expression tree. 1830 // We'll remove all the factors with the same power in a second pass. 1831 Value *M = Factors[LastIdx].Base = buildMultiplyTree(Builder, InnerProduct); 1832 if (Instruction *MI = dyn_cast<Instruction>(M)) 1833 RedoInsts.insert(MI); 1834 1835 LastIdx = Idx; 1836 } 1837 // Unique factors with equal powers -- we've folded them into the first one's 1838 // base. 1839 Factors.erase(std::unique(Factors.begin(), Factors.end(), 1840 Factor::PowerEqual()), 1841 Factors.end()); 1842 1843 // Iteratively collect the base of each factor with an add power into the 1844 // outer product, and halve each power in preparation for squaring the 1845 // expression. 1846 for (unsigned Idx = 0, Size = Factors.size(); Idx != Size; ++Idx) { 1847 if (Factors[Idx].Power & 1) 1848 OuterProduct.push_back(Factors[Idx].Base); 1849 Factors[Idx].Power >>= 1; 1850 } 1851 if (Factors[0].Power) { 1852 Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors); 1853 OuterProduct.push_back(SquareRoot); 1854 OuterProduct.push_back(SquareRoot); 1855 } 1856 if (OuterProduct.size() == 1) 1857 return OuterProduct.front(); 1858 1859 Value *V = buildMultiplyTree(Builder, OuterProduct); 1860 return V; 1861 } 1862 1863 Value *Reassociate::OptimizeMul(BinaryOperator *I, 1864 SmallVectorImpl<ValueEntry> &Ops) { 1865 // We can only optimize the multiplies when there is a chain of more than 1866 // three, such that a balanced tree might require fewer total multiplies. 1867 if (Ops.size() < 4) 1868 return nullptr; 1869 1870 // Try to turn linear trees of multiplies without other uses of the 1871 // intermediate stages into minimal multiply DAGs with perfect sub-expression 1872 // re-use. 1873 SmallVector<Factor, 4> Factors; 1874 if (!collectMultiplyFactors(Ops, Factors)) 1875 return nullptr; // All distinct factors, so nothing left for us to do. 1876 1877 IRBuilder<> Builder(I); 1878 Value *V = buildMinimalMultiplyDAG(Builder, Factors); 1879 if (Ops.empty()) 1880 return V; 1881 1882 ValueEntry NewEntry = ValueEntry(getRank(V), V); 1883 Ops.insert(std::lower_bound(Ops.begin(), Ops.end(), NewEntry), NewEntry); 1884 return nullptr; 1885 } 1886 1887 Value *Reassociate::OptimizeExpression(BinaryOperator *I, 1888 SmallVectorImpl<ValueEntry> &Ops) { 1889 // Now that we have the linearized expression tree, try to optimize it. 1890 // Start by folding any constants that we found. 1891 Constant *Cst = nullptr; 1892 unsigned Opcode = I->getOpcode(); 1893 while (!Ops.empty() && isa<Constant>(Ops.back().Op)) { 1894 Constant *C = cast<Constant>(Ops.pop_back_val().Op); 1895 Cst = Cst ? ConstantExpr::get(Opcode, C, Cst) : C; 1896 } 1897 // If there was nothing but constants then we are done. 1898 if (Ops.empty()) 1899 return Cst; 1900 1901 // Put the combined constant back at the end of the operand list, except if 1902 // there is no point. For example, an add of 0 gets dropped here, while a 1903 // multiplication by zero turns the whole expression into zero. 1904 if (Cst && Cst != ConstantExpr::getBinOpIdentity(Opcode, I->getType())) { 1905 if (Cst == ConstantExpr::getBinOpAbsorber(Opcode, I->getType())) 1906 return Cst; 1907 Ops.push_back(ValueEntry(0, Cst)); 1908 } 1909 1910 if (Ops.size() == 1) return Ops[0].Op; 1911 1912 // Handle destructive annihilation due to identities between elements in the 1913 // argument list here. 1914 unsigned NumOps = Ops.size(); 1915 switch (Opcode) { 1916 default: break; 1917 case Instruction::And: 1918 case Instruction::Or: 1919 if (Value *Result = OptimizeAndOrXor(Opcode, Ops)) 1920 return Result; 1921 break; 1922 1923 case Instruction::Xor: 1924 if (Value *Result = OptimizeXor(I, Ops)) 1925 return Result; 1926 break; 1927 1928 case Instruction::Add: 1929 case Instruction::FAdd: 1930 if (Value *Result = OptimizeAdd(I, Ops)) 1931 return Result; 1932 break; 1933 1934 case Instruction::Mul: 1935 case Instruction::FMul: 1936 if (Value *Result = OptimizeMul(I, Ops)) 1937 return Result; 1938 break; 1939 } 1940 1941 if (Ops.size() != NumOps) 1942 return OptimizeExpression(I, Ops); 1943 return nullptr; 1944 } 1945 1946 /// EraseInst - Zap the given instruction, adding interesting operands to the 1947 /// work list. 1948 void Reassociate::EraseInst(Instruction *I) { 1949 assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!"); 1950 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 1951 // Erase the dead instruction. 1952 ValueRankMap.erase(I); 1953 RedoInsts.remove(I); 1954 I->eraseFromParent(); 1955 // Optimize its operands. 1956 SmallPtrSet<Instruction *, 8> Visited; // Detect self-referential nodes. 1957 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 1958 if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) { 1959 // If this is a node in an expression tree, climb to the expression root 1960 // and add that since that's where optimization actually happens. 1961 unsigned Opcode = Op->getOpcode(); 1962 while (Op->hasOneUse() && Op->user_back()->getOpcode() == Opcode && 1963 Visited.insert(Op).second) 1964 Op = Op->user_back(); 1965 RedoInsts.insert(Op); 1966 } 1967 } 1968 1969 // Canonicalize expressions of the following form: 1970 // x + (-Constant * y) -> x - (Constant * y) 1971 // x - (-Constant * y) -> x + (Constant * y) 1972 Instruction *Reassociate::canonicalizeNegConstExpr(Instruction *I) { 1973 if (!I->hasOneUse() || I->getType()->isVectorTy()) 1974 return nullptr; 1975 1976 // Must be a mul, fmul, or fdiv instruction. 1977 unsigned Opcode = I->getOpcode(); 1978 if (Opcode != Instruction::Mul && Opcode != Instruction::FMul && 1979 Opcode != Instruction::FDiv) 1980 return nullptr; 1981 1982 // Must have at least one constant operand. 1983 Constant *C0 = dyn_cast<Constant>(I->getOperand(0)); 1984 Constant *C1 = dyn_cast<Constant>(I->getOperand(1)); 1985 if (!C0 && !C1) 1986 return nullptr; 1987 1988 // Must be a negative ConstantInt or ConstantFP. 1989 Constant *C = C0 ? C0 : C1; 1990 unsigned ConstIdx = C0 ? 0 : 1; 1991 if (auto *CI = dyn_cast<ConstantInt>(C)) { 1992 if (!CI->isNegative() || CI->isMinValue(true)) 1993 return nullptr; 1994 } else if (auto *CF = dyn_cast<ConstantFP>(C)) { 1995 if (!CF->isNegative()) 1996 return nullptr; 1997 } else 1998 return nullptr; 1999 2000 // User must be a binary operator with one or more uses. 2001 Instruction *User = I->user_back(); 2002 if (!isa<BinaryOperator>(User) || !User->getNumUses()) 2003 return nullptr; 2004 2005 unsigned UserOpcode = User->getOpcode(); 2006 if (UserOpcode != Instruction::Add && UserOpcode != Instruction::FAdd && 2007 UserOpcode != Instruction::Sub && UserOpcode != Instruction::FSub) 2008 return nullptr; 2009 2010 // Subtraction is not commutative. Explicitly, the following transform is 2011 // not valid: (-Constant * y) - x -> x + (Constant * y) 2012 if (!User->isCommutative() && User->getOperand(1) != I) 2013 return nullptr; 2014 2015 // Change the sign of the constant. 2016 if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 2017 I->setOperand(ConstIdx, ConstantInt::get(CI->getContext(), -CI->getValue())); 2018 else { 2019 ConstantFP *CF = cast<ConstantFP>(C); 2020 APFloat Val = CF->getValueAPF(); 2021 Val.changeSign(); 2022 I->setOperand(ConstIdx, ConstantFP::get(CF->getContext(), Val)); 2023 } 2024 2025 // Canonicalize I to RHS to simplify the next bit of logic. E.g., 2026 // ((-Const*y) + x) -> (x + (-Const*y)). 2027 if (User->getOperand(0) == I && User->isCommutative()) 2028 cast<BinaryOperator>(User)->swapOperands(); 2029 2030 Value *Op0 = User->getOperand(0); 2031 Value *Op1 = User->getOperand(1); 2032 BinaryOperator *NI; 2033 switch(UserOpcode) { 2034 default: 2035 llvm_unreachable("Unexpected Opcode!"); 2036 case Instruction::Add: 2037 NI = BinaryOperator::CreateSub(Op0, Op1); 2038 break; 2039 case Instruction::Sub: 2040 NI = BinaryOperator::CreateAdd(Op0, Op1); 2041 break; 2042 case Instruction::FAdd: 2043 NI = BinaryOperator::CreateFSub(Op0, Op1); 2044 NI->setFastMathFlags(cast<FPMathOperator>(User)->getFastMathFlags()); 2045 break; 2046 case Instruction::FSub: 2047 NI = BinaryOperator::CreateFAdd(Op0, Op1); 2048 NI->setFastMathFlags(cast<FPMathOperator>(User)->getFastMathFlags()); 2049 break; 2050 } 2051 2052 NI->insertBefore(User); 2053 NI->setName(User->getName()); 2054 User->replaceAllUsesWith(NI); 2055 NI->setDebugLoc(I->getDebugLoc()); 2056 RedoInsts.insert(I); 2057 MadeChange = true; 2058 return NI; 2059 } 2060 2061 /// OptimizeInst - Inspect and optimize the given instruction. Note that erasing 2062 /// instructions is not allowed. 2063 void Reassociate::OptimizeInst(Instruction *I) { 2064 // Only consider operations that we understand. 2065 if (!isa<BinaryOperator>(I)) 2066 return; 2067 2068 if (I->getOpcode() == Instruction::Shl && isa<ConstantInt>(I->getOperand(1))) 2069 // If an operand of this shift is a reassociable multiply, or if the shift 2070 // is used by a reassociable multiply or add, turn into a multiply. 2071 if (isReassociableOp(I->getOperand(0), Instruction::Mul) || 2072 (I->hasOneUse() && 2073 (isReassociableOp(I->user_back(), Instruction::Mul) || 2074 isReassociableOp(I->user_back(), Instruction::Add)))) { 2075 Instruction *NI = ConvertShiftToMul(I); 2076 RedoInsts.insert(I); 2077 MadeChange = true; 2078 I = NI; 2079 } 2080 2081 // Canonicalize negative constants out of expressions. 2082 if (Instruction *Res = canonicalizeNegConstExpr(I)) 2083 I = Res; 2084 2085 // Commute binary operators, to canonicalize the order of their operands. 2086 // This can potentially expose more CSE opportunities, and makes writing other 2087 // transformations simpler. 2088 if (I->isCommutative()) 2089 canonicalizeOperands(I); 2090 2091 // TODO: We should optimize vector Xor instructions, but they are 2092 // currently unsupported. 2093 if (I->getType()->isVectorTy() && I->getOpcode() == Instruction::Xor) 2094 return; 2095 2096 // Don't optimize floating point instructions that don't have unsafe algebra. 2097 if (I->getType()->isFloatingPointTy() && !I->hasUnsafeAlgebra()) 2098 return; 2099 2100 // Do not reassociate boolean (i1) expressions. We want to preserve the 2101 // original order of evaluation for short-circuited comparisons that 2102 // SimplifyCFG has folded to AND/OR expressions. If the expression 2103 // is not further optimized, it is likely to be transformed back to a 2104 // short-circuited form for code gen, and the source order may have been 2105 // optimized for the most likely conditions. 2106 if (I->getType()->isIntegerTy(1)) 2107 return; 2108 2109 // If this is a subtract instruction which is not already in negate form, 2110 // see if we can convert it to X+-Y. 2111 if (I->getOpcode() == Instruction::Sub) { 2112 if (ShouldBreakUpSubtract(I)) { 2113 Instruction *NI = BreakUpSubtract(I); 2114 RedoInsts.insert(I); 2115 MadeChange = true; 2116 I = NI; 2117 } else if (BinaryOperator::isNeg(I)) { 2118 // Otherwise, this is a negation. See if the operand is a multiply tree 2119 // and if this is not an inner node of a multiply tree. 2120 if (isReassociableOp(I->getOperand(1), Instruction::Mul) && 2121 (!I->hasOneUse() || 2122 !isReassociableOp(I->user_back(), Instruction::Mul))) { 2123 Instruction *NI = LowerNegateToMultiply(I); 2124 RedoInsts.insert(I); 2125 MadeChange = true; 2126 I = NI; 2127 } 2128 } 2129 } else if (I->getOpcode() == Instruction::FSub) { 2130 if (ShouldBreakUpSubtract(I)) { 2131 Instruction *NI = BreakUpSubtract(I); 2132 RedoInsts.insert(I); 2133 MadeChange = true; 2134 I = NI; 2135 } else if (BinaryOperator::isFNeg(I)) { 2136 // Otherwise, this is a negation. See if the operand is a multiply tree 2137 // and if this is not an inner node of a multiply tree. 2138 if (isReassociableOp(I->getOperand(1), Instruction::FMul) && 2139 (!I->hasOneUse() || 2140 !isReassociableOp(I->user_back(), Instruction::FMul))) { 2141 Instruction *NI = LowerNegateToMultiply(I); 2142 RedoInsts.insert(I); 2143 MadeChange = true; 2144 I = NI; 2145 } 2146 } 2147 } 2148 2149 // If this instruction is an associative binary operator, process it. 2150 if (!I->isAssociative()) return; 2151 BinaryOperator *BO = cast<BinaryOperator>(I); 2152 2153 // If this is an interior node of a reassociable tree, ignore it until we 2154 // get to the root of the tree, to avoid N^2 analysis. 2155 unsigned Opcode = BO->getOpcode(); 2156 if (BO->hasOneUse() && BO->user_back()->getOpcode() == Opcode) 2157 return; 2158 2159 // If this is an add tree that is used by a sub instruction, ignore it 2160 // until we process the subtract. 2161 if (BO->hasOneUse() && BO->getOpcode() == Instruction::Add && 2162 cast<Instruction>(BO->user_back())->getOpcode() == Instruction::Sub) 2163 return; 2164 if (BO->hasOneUse() && BO->getOpcode() == Instruction::FAdd && 2165 cast<Instruction>(BO->user_back())->getOpcode() == Instruction::FSub) 2166 return; 2167 2168 ReassociateExpression(BO); 2169 } 2170 2171 void Reassociate::ReassociateExpression(BinaryOperator *I) { 2172 // First, walk the expression tree, linearizing the tree, collecting the 2173 // operand information. 2174 SmallVector<RepeatedValue, 8> Tree; 2175 MadeChange |= LinearizeExprTree(I, Tree); 2176 SmallVector<ValueEntry, 8> Ops; 2177 Ops.reserve(Tree.size()); 2178 for (unsigned i = 0, e = Tree.size(); i != e; ++i) { 2179 RepeatedValue E = Tree[i]; 2180 Ops.append(E.second.getZExtValue(), 2181 ValueEntry(getRank(E.first), E.first)); 2182 } 2183 2184 DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n'); 2185 2186 // Now that we have linearized the tree to a list and have gathered all of 2187 // the operands and their ranks, sort the operands by their rank. Use a 2188 // stable_sort so that values with equal ranks will have their relative 2189 // positions maintained (and so the compiler is deterministic). Note that 2190 // this sorts so that the highest ranking values end up at the beginning of 2191 // the vector. 2192 std::stable_sort(Ops.begin(), Ops.end()); 2193 2194 // OptimizeExpression - Now that we have the expression tree in a convenient 2195 // sorted form, optimize it globally if possible. 2196 if (Value *V = OptimizeExpression(I, Ops)) { 2197 if (V == I) 2198 // Self-referential expression in unreachable code. 2199 return; 2200 // This expression tree simplified to something that isn't a tree, 2201 // eliminate it. 2202 DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n'); 2203 I->replaceAllUsesWith(V); 2204 if (Instruction *VI = dyn_cast<Instruction>(V)) 2205 VI->setDebugLoc(I->getDebugLoc()); 2206 RedoInsts.insert(I); 2207 ++NumAnnihil; 2208 return; 2209 } 2210 2211 // We want to sink immediates as deeply as possible except in the case where 2212 // this is a multiply tree used only by an add, and the immediate is a -1. 2213 // In this case we reassociate to put the negation on the outside so that we 2214 // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y 2215 if (I->hasOneUse()) { 2216 if (I->getOpcode() == Instruction::Mul && 2217 cast<Instruction>(I->user_back())->getOpcode() == Instruction::Add && 2218 isa<ConstantInt>(Ops.back().Op) && 2219 cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) { 2220 ValueEntry Tmp = Ops.pop_back_val(); 2221 Ops.insert(Ops.begin(), Tmp); 2222 } else if (I->getOpcode() == Instruction::FMul && 2223 cast<Instruction>(I->user_back())->getOpcode() == 2224 Instruction::FAdd && 2225 isa<ConstantFP>(Ops.back().Op) && 2226 cast<ConstantFP>(Ops.back().Op)->isExactlyValue(-1.0)) { 2227 ValueEntry Tmp = Ops.pop_back_val(); 2228 Ops.insert(Ops.begin(), Tmp); 2229 } 2230 } 2231 2232 DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n'); 2233 2234 if (Ops.size() == 1) { 2235 if (Ops[0].Op == I) 2236 // Self-referential expression in unreachable code. 2237 return; 2238 2239 // This expression tree simplified to something that isn't a tree, 2240 // eliminate it. 2241 I->replaceAllUsesWith(Ops[0].Op); 2242 if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op)) 2243 OI->setDebugLoc(I->getDebugLoc()); 2244 RedoInsts.insert(I); 2245 return; 2246 } 2247 2248 // Now that we ordered and optimized the expressions, splat them back into 2249 // the expression tree, removing any unneeded nodes. 2250 RewriteExprTree(I, Ops); 2251 } 2252 2253 bool Reassociate::runOnFunction(Function &F) { 2254 if (skipOptnoneFunction(F)) 2255 return false; 2256 2257 // Calculate the rank map for F 2258 BuildRankMap(F); 2259 2260 MadeChange = false; 2261 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { 2262 // Optimize every instruction in the basic block. 2263 for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; ) 2264 if (isInstructionTriviallyDead(II)) { 2265 EraseInst(II++); 2266 } else { 2267 OptimizeInst(II); 2268 assert(II->getParent() == BI && "Moved to a different block!"); 2269 ++II; 2270 } 2271 2272 // If this produced extra instructions to optimize, handle them now. 2273 while (!RedoInsts.empty()) { 2274 Instruction *I = RedoInsts.pop_back_val(); 2275 if (isInstructionTriviallyDead(I)) 2276 EraseInst(I); 2277 else 2278 OptimizeInst(I); 2279 } 2280 } 2281 2282 // We are done with the rank map. 2283 RankMap.clear(); 2284 ValueRankMap.clear(); 2285 2286 return MadeChange; 2287 } 2288