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