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