InstructionCombining.cpp revision 335799
1201546Sdavidxu//===- InstructionCombining.cpp - Combine multiple instructions -----------===// 2201546Sdavidxu// 3201546Sdavidxu// The LLVM Compiler Infrastructure 4201546Sdavidxu// 5201546Sdavidxu// This file is distributed under the University of Illinois Open Source 6201546Sdavidxu// License. See LICENSE.TXT for details. 7201546Sdavidxu// 8201546Sdavidxu//===----------------------------------------------------------------------===// 9201546Sdavidxu// 10201546Sdavidxu// InstructionCombining - Combine instructions to form fewer, simple 11201546Sdavidxu// instructions. This pass does not modify the CFG. This pass is where 12201546Sdavidxu// algebraic simplification happens. 13201546Sdavidxu// 14201546Sdavidxu// This pass combines things like: 15201546Sdavidxu// %Y = add i32 %X, 1 16201546Sdavidxu// %Z = add i32 %Y, 1 17201546Sdavidxu// into: 18201546Sdavidxu// %Z = add i32 %X, 2 19201546Sdavidxu// 20201546Sdavidxu// This is a simple worklist driven algorithm. 21201546Sdavidxu// 22201546Sdavidxu// This pass guarantees that the following canonicalizations are performed on 23201546Sdavidxu// the program: 24201546Sdavidxu// 1. If a binary operator has a constant operand, it is moved to the RHS 25201546Sdavidxu// 2. Bitwise operators with constant operands are always grouped so that 26201546Sdavidxu// shifts are performed first, then or's, then and's, then xor's. 27201546Sdavidxu// 3. Compare instructions are converted from <,>,<=,>= to ==,!= if possible 28201546Sdavidxu// 4. All cmp instructions on boolean values are replaced with logical ops 29201546Sdavidxu// 5. add X, X is represented as (X*2) => (X << 1) 30201546Sdavidxu// 6. Multiplies with a power-of-two constant argument are transformed into 31201546Sdavidxu// shifts. 32201546Sdavidxu// ... etc. 33201546Sdavidxu// 34201546Sdavidxu//===----------------------------------------------------------------------===// 35201546Sdavidxu 36201546Sdavidxu#include "InstCombineInternal.h" 37201546Sdavidxu#include "llvm-c/Initialization.h" 38201546Sdavidxu#include "llvm/ADT/APInt.h" 39201546Sdavidxu#include "llvm/ADT/ArrayRef.h" 40201546Sdavidxu#include "llvm/ADT/DenseMap.h" 41201546Sdavidxu#include "llvm/ADT/None.h" 42201546Sdavidxu#include "llvm/ADT/SmallPtrSet.h" 43201546Sdavidxu#include "llvm/ADT/SmallVector.h" 44201546Sdavidxu#include "llvm/ADT/Statistic.h" 45201546Sdavidxu#include "llvm/ADT/TinyPtrVector.h" 46201546Sdavidxu#include "llvm/Analysis/AliasAnalysis.h" 47201546Sdavidxu#include "llvm/Analysis/AssumptionCache.h" 48201546Sdavidxu#include "llvm/Analysis/BasicAliasAnalysis.h" 49201546Sdavidxu#include "llvm/Analysis/CFG.h" 50201546Sdavidxu#include "llvm/Analysis/ConstantFolding.h" 51201546Sdavidxu#include "llvm/Analysis/EHPersonalities.h" 52201546Sdavidxu#include "llvm/Analysis/GlobalsModRef.h" 53201546Sdavidxu#include "llvm/Analysis/InstructionSimplify.h" 54201546Sdavidxu#include "llvm/Analysis/LoopInfo.h" 55201546Sdavidxu#include "llvm/Analysis/MemoryBuiltins.h" 56201546Sdavidxu#include "llvm/Analysis/OptimizationRemarkEmitter.h" 57201546Sdavidxu#include "llvm/Analysis/TargetFolder.h" 58201546Sdavidxu#include "llvm/Analysis/TargetLibraryInfo.h" 59201546Sdavidxu#include "llvm/Analysis/ValueTracking.h" 60201546Sdavidxu#include "llvm/IR/BasicBlock.h" 61201546Sdavidxu#include "llvm/IR/CFG.h" 62201546Sdavidxu#include "llvm/IR/Constant.h" 63201546Sdavidxu#include "llvm/IR/Constants.h" 64201546Sdavidxu#include "llvm/IR/DIBuilder.h" 65#include "llvm/IR/DataLayout.h" 66#include "llvm/IR/DerivedTypes.h" 67#include "llvm/IR/Dominators.h" 68#include "llvm/IR/Function.h" 69#include "llvm/IR/GetElementPtrTypeIterator.h" 70#include "llvm/IR/IRBuilder.h" 71#include "llvm/IR/InstrTypes.h" 72#include "llvm/IR/Instruction.h" 73#include "llvm/IR/Instructions.h" 74#include "llvm/IR/IntrinsicInst.h" 75#include "llvm/IR/Intrinsics.h" 76#include "llvm/IR/Metadata.h" 77#include "llvm/IR/Operator.h" 78#include "llvm/IR/PassManager.h" 79#include "llvm/IR/PatternMatch.h" 80#include "llvm/IR/Type.h" 81#include "llvm/IR/Use.h" 82#include "llvm/IR/User.h" 83#include "llvm/IR/Value.h" 84#include "llvm/IR/ValueHandle.h" 85#include "llvm/Pass.h" 86#include "llvm/Support/CBindingWrapping.h" 87#include "llvm/Support/Casting.h" 88#include "llvm/Support/CommandLine.h" 89#include "llvm/Support/Compiler.h" 90#include "llvm/Support/Debug.h" 91#include "llvm/Support/DebugCounter.h" 92#include "llvm/Support/ErrorHandling.h" 93#include "llvm/Support/KnownBits.h" 94#include "llvm/Support/raw_ostream.h" 95#include "llvm/Transforms/InstCombine/InstCombine.h" 96#include "llvm/Transforms/InstCombine/InstCombineWorklist.h" 97#include "llvm/Transforms/Scalar.h" 98#include "llvm/Transforms/Utils/Local.h" 99#include <algorithm> 100#include <cassert> 101#include <cstdint> 102#include <memory> 103#include <string> 104#include <utility> 105 106using namespace llvm; 107using namespace llvm::PatternMatch; 108 109#define DEBUG_TYPE "instcombine" 110 111STATISTIC(NumCombined , "Number of insts combined"); 112STATISTIC(NumConstProp, "Number of constant folds"); 113STATISTIC(NumDeadInst , "Number of dead inst eliminated"); 114STATISTIC(NumSunkInst , "Number of instructions sunk"); 115STATISTIC(NumExpand, "Number of expansions"); 116STATISTIC(NumFactor , "Number of factorizations"); 117STATISTIC(NumReassoc , "Number of reassociations"); 118DEBUG_COUNTER(VisitCounter, "instcombine-visit", 119 "Controls which instructions are visited"); 120 121static cl::opt<bool> 122EnableExpensiveCombines("expensive-combines", 123 cl::desc("Enable expensive instruction combines")); 124 125static cl::opt<unsigned> 126MaxArraySize("instcombine-maxarray-size", cl::init(1024), 127 cl::desc("Maximum array size considered when doing a combine")); 128 129// FIXME: Remove this flag when it is no longer necessary to convert 130// llvm.dbg.declare to avoid inaccurate debug info. Setting this to false 131// increases variable availability at the cost of accuracy. Variables that 132// cannot be promoted by mem2reg or SROA will be described as living in memory 133// for their entire lifetime. However, passes like DSE and instcombine can 134// delete stores to the alloca, leading to misleading and inaccurate debug 135// information. This flag can be removed when those passes are fixed. 136static cl::opt<unsigned> ShouldLowerDbgDeclare("instcombine-lower-dbg-declare", 137 cl::Hidden, cl::init(true)); 138 139Value *InstCombiner::EmitGEPOffset(User *GEP) { 140 return llvm::EmitGEPOffset(&Builder, DL, GEP); 141} 142 143/// Return true if it is desirable to convert an integer computation from a 144/// given bit width to a new bit width. 145/// We don't want to convert from a legal to an illegal type or from a smaller 146/// to a larger illegal type. A width of '1' is always treated as a legal type 147/// because i1 is a fundamental type in IR, and there are many specialized 148/// optimizations for i1 types. 149bool InstCombiner::shouldChangeType(unsigned FromWidth, 150 unsigned ToWidth) const { 151 bool FromLegal = FromWidth == 1 || DL.isLegalInteger(FromWidth); 152 bool ToLegal = ToWidth == 1 || DL.isLegalInteger(ToWidth); 153 154 // If this is a legal integer from type, and the result would be an illegal 155 // type, don't do the transformation. 156 if (FromLegal && !ToLegal) 157 return false; 158 159 // Otherwise, if both are illegal, do not increase the size of the result. We 160 // do allow things like i160 -> i64, but not i64 -> i160. 161 if (!FromLegal && !ToLegal && ToWidth > FromWidth) 162 return false; 163 164 return true; 165} 166 167/// Return true if it is desirable to convert a computation from 'From' to 'To'. 168/// We don't want to convert from a legal to an illegal type or from a smaller 169/// to a larger illegal type. i1 is always treated as a legal type because it is 170/// a fundamental type in IR, and there are many specialized optimizations for 171/// i1 types. 172bool InstCombiner::shouldChangeType(Type *From, Type *To) const { 173 assert(From->isIntegerTy() && To->isIntegerTy()); 174 175 unsigned FromWidth = From->getPrimitiveSizeInBits(); 176 unsigned ToWidth = To->getPrimitiveSizeInBits(); 177 return shouldChangeType(FromWidth, ToWidth); 178} 179 180// Return true, if No Signed Wrap should be maintained for I. 181// The No Signed Wrap flag can be kept if the operation "B (I.getOpcode) C", 182// where both B and C should be ConstantInts, results in a constant that does 183// not overflow. This function only handles the Add and Sub opcodes. For 184// all other opcodes, the function conservatively returns false. 185static bool MaintainNoSignedWrap(BinaryOperator &I, Value *B, Value *C) { 186 OverflowingBinaryOperator *OBO = dyn_cast<OverflowingBinaryOperator>(&I); 187 if (!OBO || !OBO->hasNoSignedWrap()) 188 return false; 189 190 // We reason about Add and Sub Only. 191 Instruction::BinaryOps Opcode = I.getOpcode(); 192 if (Opcode != Instruction::Add && Opcode != Instruction::Sub) 193 return false; 194 195 const APInt *BVal, *CVal; 196 if (!match(B, m_APInt(BVal)) || !match(C, m_APInt(CVal))) 197 return false; 198 199 bool Overflow = false; 200 if (Opcode == Instruction::Add) 201 (void)BVal->sadd_ov(*CVal, Overflow); 202 else 203 (void)BVal->ssub_ov(*CVal, Overflow); 204 205 return !Overflow; 206} 207 208/// Conservatively clears subclassOptionalData after a reassociation or 209/// commutation. We preserve fast-math flags when applicable as they can be 210/// preserved. 211static void ClearSubclassDataAfterReassociation(BinaryOperator &I) { 212 FPMathOperator *FPMO = dyn_cast<FPMathOperator>(&I); 213 if (!FPMO) { 214 I.clearSubclassOptionalData(); 215 return; 216 } 217 218 FastMathFlags FMF = I.getFastMathFlags(); 219 I.clearSubclassOptionalData(); 220 I.setFastMathFlags(FMF); 221} 222 223/// Combine constant operands of associative operations either before or after a 224/// cast to eliminate one of the associative operations: 225/// (op (cast (op X, C2)), C1) --> (cast (op X, op (C1, C2))) 226/// (op (cast (op X, C2)), C1) --> (op (cast X), op (C1, C2)) 227static bool simplifyAssocCastAssoc(BinaryOperator *BinOp1) { 228 auto *Cast = dyn_cast<CastInst>(BinOp1->getOperand(0)); 229 if (!Cast || !Cast->hasOneUse()) 230 return false; 231 232 // TODO: Enhance logic for other casts and remove this check. 233 auto CastOpcode = Cast->getOpcode(); 234 if (CastOpcode != Instruction::ZExt) 235 return false; 236 237 // TODO: Enhance logic for other BinOps and remove this check. 238 if (!BinOp1->isBitwiseLogicOp()) 239 return false; 240 241 auto AssocOpcode = BinOp1->getOpcode(); 242 auto *BinOp2 = dyn_cast<BinaryOperator>(Cast->getOperand(0)); 243 if (!BinOp2 || !BinOp2->hasOneUse() || BinOp2->getOpcode() != AssocOpcode) 244 return false; 245 246 Constant *C1, *C2; 247 if (!match(BinOp1->getOperand(1), m_Constant(C1)) || 248 !match(BinOp2->getOperand(1), m_Constant(C2))) 249 return false; 250 251 // TODO: This assumes a zext cast. 252 // Eg, if it was a trunc, we'd cast C1 to the source type because casting C2 253 // to the destination type might lose bits. 254 255 // Fold the constants together in the destination type: 256 // (op (cast (op X, C2)), C1) --> (op (cast X), FoldedC) 257 Type *DestTy = C1->getType(); 258 Constant *CastC2 = ConstantExpr::getCast(CastOpcode, C2, DestTy); 259 Constant *FoldedC = ConstantExpr::get(AssocOpcode, C1, CastC2); 260 Cast->setOperand(0, BinOp2->getOperand(0)); 261 BinOp1->setOperand(1, FoldedC); 262 return true; 263} 264 265/// This performs a few simplifications for operators that are associative or 266/// commutative: 267/// 268/// Commutative operators: 269/// 270/// 1. Order operands such that they are listed from right (least complex) to 271/// left (most complex). This puts constants before unary operators before 272/// binary operators. 273/// 274/// Associative operators: 275/// 276/// 2. Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies. 277/// 3. Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies. 278/// 279/// Associative and commutative operators: 280/// 281/// 4. Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies. 282/// 5. Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies. 283/// 6. Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)" 284/// if C1 and C2 are constants. 285bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I) { 286 Instruction::BinaryOps Opcode = I.getOpcode(); 287 bool Changed = false; 288 289 do { 290 // Order operands such that they are listed from right (least complex) to 291 // left (most complex). This puts constants before unary operators before 292 // binary operators. 293 if (I.isCommutative() && getComplexity(I.getOperand(0)) < 294 getComplexity(I.getOperand(1))) 295 Changed = !I.swapOperands(); 296 297 BinaryOperator *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0)); 298 BinaryOperator *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1)); 299 300 if (I.isAssociative()) { 301 // Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies. 302 if (Op0 && Op0->getOpcode() == Opcode) { 303 Value *A = Op0->getOperand(0); 304 Value *B = Op0->getOperand(1); 305 Value *C = I.getOperand(1); 306 307 // Does "B op C" simplify? 308 if (Value *V = SimplifyBinOp(Opcode, B, C, SQ.getWithInstruction(&I))) { 309 // It simplifies to V. Form "A op V". 310 I.setOperand(0, A); 311 I.setOperand(1, V); 312 // Conservatively clear the optional flags, since they may not be 313 // preserved by the reassociation. 314 if (MaintainNoSignedWrap(I, B, C) && 315 (!Op0 || (isa<BinaryOperator>(Op0) && Op0->hasNoSignedWrap()))) { 316 // Note: this is only valid because SimplifyBinOp doesn't look at 317 // the operands to Op0. 318 I.clearSubclassOptionalData(); 319 I.setHasNoSignedWrap(true); 320 } else { 321 ClearSubclassDataAfterReassociation(I); 322 } 323 324 Changed = true; 325 ++NumReassoc; 326 continue; 327 } 328 } 329 330 // Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies. 331 if (Op1 && Op1->getOpcode() == Opcode) { 332 Value *A = I.getOperand(0); 333 Value *B = Op1->getOperand(0); 334 Value *C = Op1->getOperand(1); 335 336 // Does "A op B" simplify? 337 if (Value *V = SimplifyBinOp(Opcode, A, B, SQ.getWithInstruction(&I))) { 338 // It simplifies to V. Form "V op C". 339 I.setOperand(0, V); 340 I.setOperand(1, C); 341 // Conservatively clear the optional flags, since they may not be 342 // preserved by the reassociation. 343 ClearSubclassDataAfterReassociation(I); 344 Changed = true; 345 ++NumReassoc; 346 continue; 347 } 348 } 349 } 350 351 if (I.isAssociative() && I.isCommutative()) { 352 if (simplifyAssocCastAssoc(&I)) { 353 Changed = true; 354 ++NumReassoc; 355 continue; 356 } 357 358 // Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies. 359 if (Op0 && Op0->getOpcode() == Opcode) { 360 Value *A = Op0->getOperand(0); 361 Value *B = Op0->getOperand(1); 362 Value *C = I.getOperand(1); 363 364 // Does "C op A" simplify? 365 if (Value *V = SimplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) { 366 // It simplifies to V. Form "V op B". 367 I.setOperand(0, V); 368 I.setOperand(1, B); 369 // Conservatively clear the optional flags, since they may not be 370 // preserved by the reassociation. 371 ClearSubclassDataAfterReassociation(I); 372 Changed = true; 373 ++NumReassoc; 374 continue; 375 } 376 } 377 378 // Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies. 379 if (Op1 && Op1->getOpcode() == Opcode) { 380 Value *A = I.getOperand(0); 381 Value *B = Op1->getOperand(0); 382 Value *C = Op1->getOperand(1); 383 384 // Does "C op A" simplify? 385 if (Value *V = SimplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) { 386 // It simplifies to V. Form "B op V". 387 I.setOperand(0, B); 388 I.setOperand(1, V); 389 // Conservatively clear the optional flags, since they may not be 390 // preserved by the reassociation. 391 ClearSubclassDataAfterReassociation(I); 392 Changed = true; 393 ++NumReassoc; 394 continue; 395 } 396 } 397 398 // Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)" 399 // if C1 and C2 are constants. 400 if (Op0 && Op1 && 401 Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode && 402 isa<Constant>(Op0->getOperand(1)) && 403 isa<Constant>(Op1->getOperand(1)) && 404 Op0->hasOneUse() && Op1->hasOneUse()) { 405 Value *A = Op0->getOperand(0); 406 Constant *C1 = cast<Constant>(Op0->getOperand(1)); 407 Value *B = Op1->getOperand(0); 408 Constant *C2 = cast<Constant>(Op1->getOperand(1)); 409 410 Constant *Folded = ConstantExpr::get(Opcode, C1, C2); 411 BinaryOperator *New = BinaryOperator::Create(Opcode, A, B); 412 if (isa<FPMathOperator>(New)) { 413 FastMathFlags Flags = I.getFastMathFlags(); 414 Flags &= Op0->getFastMathFlags(); 415 Flags &= Op1->getFastMathFlags(); 416 New->setFastMathFlags(Flags); 417 } 418 InsertNewInstWith(New, I); 419 New->takeName(Op1); 420 I.setOperand(0, New); 421 I.setOperand(1, Folded); 422 // Conservatively clear the optional flags, since they may not be 423 // preserved by the reassociation. 424 ClearSubclassDataAfterReassociation(I); 425 426 Changed = true; 427 continue; 428 } 429 } 430 431 // No further simplifications. 432 return Changed; 433 } while (true); 434} 435 436/// Return whether "X LOp (Y ROp Z)" is always equal to 437/// "(X LOp Y) ROp (X LOp Z)". 438static bool LeftDistributesOverRight(Instruction::BinaryOps LOp, 439 Instruction::BinaryOps ROp) { 440 switch (LOp) { 441 default: 442 return false; 443 444 case Instruction::And: 445 // And distributes over Or and Xor. 446 switch (ROp) { 447 default: 448 return false; 449 case Instruction::Or: 450 case Instruction::Xor: 451 return true; 452 } 453 454 case Instruction::Mul: 455 // Multiplication distributes over addition and subtraction. 456 switch (ROp) { 457 default: 458 return false; 459 case Instruction::Add: 460 case Instruction::Sub: 461 return true; 462 } 463 464 case Instruction::Or: 465 // Or distributes over And. 466 switch (ROp) { 467 default: 468 return false; 469 case Instruction::And: 470 return true; 471 } 472 } 473} 474 475/// Return whether "(X LOp Y) ROp Z" is always equal to 476/// "(X ROp Z) LOp (Y ROp Z)". 477static bool RightDistributesOverLeft(Instruction::BinaryOps LOp, 478 Instruction::BinaryOps ROp) { 479 if (Instruction::isCommutative(ROp)) 480 return LeftDistributesOverRight(ROp, LOp); 481 482 switch (LOp) { 483 default: 484 return false; 485 // (X >> Z) & (Y >> Z) -> (X&Y) >> Z for all shifts. 486 // (X >> Z) | (Y >> Z) -> (X|Y) >> Z for all shifts. 487 // (X >> Z) ^ (Y >> Z) -> (X^Y) >> Z for all shifts. 488 case Instruction::And: 489 case Instruction::Or: 490 case Instruction::Xor: 491 switch (ROp) { 492 default: 493 return false; 494 case Instruction::Shl: 495 case Instruction::LShr: 496 case Instruction::AShr: 497 return true; 498 } 499 } 500 // TODO: It would be nice to handle division, aka "(X + Y)/Z = X/Z + Y/Z", 501 // but this requires knowing that the addition does not overflow and other 502 // such subtleties. 503 return false; 504} 505 506/// This function returns identity value for given opcode, which can be used to 507/// factor patterns like (X * 2) + X ==> (X * 2) + (X * 1) ==> X * (2 + 1). 508static Value *getIdentityValue(Instruction::BinaryOps Opcode, Value *V) { 509 if (isa<Constant>(V)) 510 return nullptr; 511 512 return ConstantExpr::getBinOpIdentity(Opcode, V->getType()); 513} 514 515/// This function factors binary ops which can be combined using distributive 516/// laws. This function tries to transform 'Op' based TopLevelOpcode to enable 517/// factorization e.g for ADD(SHL(X , 2), MUL(X, 5)), When this function called 518/// with TopLevelOpcode == Instruction::Add and Op = SHL(X, 2), transforms 519/// SHL(X, 2) to MUL(X, 4) i.e. returns Instruction::Mul with LHS set to 'X' and 520/// RHS to 4. 521static Instruction::BinaryOps 522getBinOpsForFactorization(Instruction::BinaryOps TopLevelOpcode, 523 BinaryOperator *Op, Value *&LHS, Value *&RHS) { 524 assert(Op && "Expected a binary operator"); 525 526 LHS = Op->getOperand(0); 527 RHS = Op->getOperand(1); 528 529 switch (TopLevelOpcode) { 530 default: 531 return Op->getOpcode(); 532 533 case Instruction::Add: 534 case Instruction::Sub: 535 if (Op->getOpcode() == Instruction::Shl) { 536 if (Constant *CST = dyn_cast<Constant>(Op->getOperand(1))) { 537 // The multiplier is really 1 << CST. 538 RHS = ConstantExpr::getShl(ConstantInt::get(Op->getType(), 1), CST); 539 return Instruction::Mul; 540 } 541 } 542 return Op->getOpcode(); 543 } 544 545 // TODO: We can add other conversions e.g. shr => div etc. 546} 547 548/// This tries to simplify binary operations by factorizing out common terms 549/// (e. g. "(A*B)+(A*C)" -> "A*(B+C)"). 550Value *InstCombiner::tryFactorization(BinaryOperator &I, 551 Instruction::BinaryOps InnerOpcode, 552 Value *A, Value *B, Value *C, Value *D) { 553 assert(A && B && C && D && "All values must be provided"); 554 555 Value *V = nullptr; 556 Value *SimplifiedInst = nullptr; 557 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 558 Instruction::BinaryOps TopLevelOpcode = I.getOpcode(); 559 560 // Does "X op' Y" always equal "Y op' X"? 561 bool InnerCommutative = Instruction::isCommutative(InnerOpcode); 562 563 // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"? 564 if (LeftDistributesOverRight(InnerOpcode, TopLevelOpcode)) 565 // Does the instruction have the form "(A op' B) op (A op' D)" or, in the 566 // commutative case, "(A op' B) op (C op' A)"? 567 if (A == C || (InnerCommutative && A == D)) { 568 if (A != C) 569 std::swap(C, D); 570 // Consider forming "A op' (B op D)". 571 // If "B op D" simplifies then it can be formed with no cost. 572 V = SimplifyBinOp(TopLevelOpcode, B, D, SQ.getWithInstruction(&I)); 573 // If "B op D" doesn't simplify then only go on if both of the existing 574 // operations "A op' B" and "C op' D" will be zapped as no longer used. 575 if (!V && LHS->hasOneUse() && RHS->hasOneUse()) 576 V = Builder.CreateBinOp(TopLevelOpcode, B, D, RHS->getName()); 577 if (V) { 578 SimplifiedInst = Builder.CreateBinOp(InnerOpcode, A, V); 579 } 580 } 581 582 // Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"? 583 if (!SimplifiedInst && RightDistributesOverLeft(TopLevelOpcode, InnerOpcode)) 584 // Does the instruction have the form "(A op' B) op (C op' B)" or, in the 585 // commutative case, "(A op' B) op (B op' D)"? 586 if (B == D || (InnerCommutative && B == C)) { 587 if (B != D) 588 std::swap(C, D); 589 // Consider forming "(A op C) op' B". 590 // If "A op C" simplifies then it can be formed with no cost. 591 V = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I)); 592 593 // If "A op C" doesn't simplify then only go on if both of the existing 594 // operations "A op' B" and "C op' D" will be zapped as no longer used. 595 if (!V && LHS->hasOneUse() && RHS->hasOneUse()) 596 V = Builder.CreateBinOp(TopLevelOpcode, A, C, LHS->getName()); 597 if (V) { 598 SimplifiedInst = Builder.CreateBinOp(InnerOpcode, V, B); 599 } 600 } 601 602 if (SimplifiedInst) { 603 ++NumFactor; 604 SimplifiedInst->takeName(&I); 605 606 // Check if we can add NSW flag to SimplifiedInst. If so, set NSW flag. 607 // TODO: Check for NUW. 608 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SimplifiedInst)) { 609 if (isa<OverflowingBinaryOperator>(SimplifiedInst)) { 610 bool HasNSW = false; 611 if (isa<OverflowingBinaryOperator>(&I)) 612 HasNSW = I.hasNoSignedWrap(); 613 614 if (auto *LOBO = dyn_cast<OverflowingBinaryOperator>(LHS)) 615 HasNSW &= LOBO->hasNoSignedWrap(); 616 617 if (auto *ROBO = dyn_cast<OverflowingBinaryOperator>(RHS)) 618 HasNSW &= ROBO->hasNoSignedWrap(); 619 620 // We can propagate 'nsw' if we know that 621 // %Y = mul nsw i16 %X, C 622 // %Z = add nsw i16 %Y, %X 623 // => 624 // %Z = mul nsw i16 %X, C+1 625 // 626 // iff C+1 isn't INT_MIN 627 const APInt *CInt; 628 if (TopLevelOpcode == Instruction::Add && 629 InnerOpcode == Instruction::Mul) 630 if (match(V, m_APInt(CInt)) && !CInt->isMinSignedValue()) 631 BO->setHasNoSignedWrap(HasNSW); 632 } 633 } 634 } 635 return SimplifiedInst; 636} 637 638/// This tries to simplify binary operations which some other binary operation 639/// distributes over either by factorizing out common terms 640/// (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this results in 641/// simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is a win). 642/// Returns the simplified value, or null if it didn't simplify. 643Value *InstCombiner::SimplifyUsingDistributiveLaws(BinaryOperator &I) { 644 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 645 BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 646 BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 647 Instruction::BinaryOps TopLevelOpcode = I.getOpcode(); 648 649 { 650 // Factorization. 651 Value *A, *B, *C, *D; 652 Instruction::BinaryOps LHSOpcode, RHSOpcode; 653 if (Op0) 654 LHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op0, A, B); 655 if (Op1) 656 RHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op1, C, D); 657 658 // The instruction has the form "(A op' B) op (C op' D)". Try to factorize 659 // a common term. 660 if (Op0 && Op1 && LHSOpcode == RHSOpcode) 661 if (Value *V = tryFactorization(I, LHSOpcode, A, B, C, D)) 662 return V; 663 664 // The instruction has the form "(A op' B) op (C)". Try to factorize common 665 // term. 666 if (Op0) 667 if (Value *Ident = getIdentityValue(LHSOpcode, RHS)) 668 if (Value *V = 669 tryFactorization(I, LHSOpcode, A, B, RHS, Ident)) 670 return V; 671 672 // The instruction has the form "(B) op (C op' D)". Try to factorize common 673 // term. 674 if (Op1) 675 if (Value *Ident = getIdentityValue(RHSOpcode, LHS)) 676 if (Value *V = 677 tryFactorization(I, RHSOpcode, LHS, Ident, C, D)) 678 return V; 679 } 680 681 // Expansion. 682 if (Op0 && RightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) { 683 // The instruction has the form "(A op' B) op C". See if expanding it out 684 // to "(A op C) op' (B op C)" results in simplifications. 685 Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 686 Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op' 687 688 Value *L = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I)); 689 Value *R = SimplifyBinOp(TopLevelOpcode, B, C, SQ.getWithInstruction(&I)); 690 691 // Do "A op C" and "B op C" both simplify? 692 if (L && R) { 693 // They do! Return "L op' R". 694 ++NumExpand; 695 C = Builder.CreateBinOp(InnerOpcode, L, R); 696 C->takeName(&I); 697 return C; 698 } 699 700 // Does "A op C" simplify to the identity value for the inner opcode? 701 if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) { 702 // They do! Return "B op C". 703 ++NumExpand; 704 C = Builder.CreateBinOp(TopLevelOpcode, B, C); 705 C->takeName(&I); 706 return C; 707 } 708 709 // Does "B op C" simplify to the identity value for the inner opcode? 710 if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) { 711 // They do! Return "A op C". 712 ++NumExpand; 713 C = Builder.CreateBinOp(TopLevelOpcode, A, C); 714 C->takeName(&I); 715 return C; 716 } 717 } 718 719 if (Op1 && LeftDistributesOverRight(TopLevelOpcode, Op1->getOpcode())) { 720 // The instruction has the form "A op (B op' C)". See if expanding it out 721 // to "(A op B) op' (A op C)" results in simplifications. 722 Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 723 Instruction::BinaryOps InnerOpcode = Op1->getOpcode(); // op' 724 725 Value *L = SimplifyBinOp(TopLevelOpcode, A, B, SQ.getWithInstruction(&I)); 726 Value *R = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I)); 727 728 // Do "A op B" and "A op C" both simplify? 729 if (L && R) { 730 // They do! Return "L op' R". 731 ++NumExpand; 732 A = Builder.CreateBinOp(InnerOpcode, L, R); 733 A->takeName(&I); 734 return A; 735 } 736 737 // Does "A op B" simplify to the identity value for the inner opcode? 738 if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) { 739 // They do! Return "A op C". 740 ++NumExpand; 741 A = Builder.CreateBinOp(TopLevelOpcode, A, C); 742 A->takeName(&I); 743 return A; 744 } 745 746 // Does "A op C" simplify to the identity value for the inner opcode? 747 if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) { 748 // They do! Return "A op B". 749 ++NumExpand; 750 A = Builder.CreateBinOp(TopLevelOpcode, A, B); 751 A->takeName(&I); 752 return A; 753 } 754 } 755 756 return SimplifySelectsFeedingBinaryOp(I, LHS, RHS); 757} 758 759Value *InstCombiner::SimplifySelectsFeedingBinaryOp(BinaryOperator &I, 760 Value *LHS, Value *RHS) { 761 Instruction::BinaryOps Opcode = I.getOpcode(); 762 // (op (select (a, b, c)), (select (a, d, e))) -> (select (a, (op b, d), (op 763 // c, e))) 764 Value *A, *B, *C, *D, *E; 765 Value *SI = nullptr; 766 if (match(LHS, m_Select(m_Value(A), m_Value(B), m_Value(C))) && 767 match(RHS, m_Select(m_Specific(A), m_Value(D), m_Value(E)))) { 768 bool SelectsHaveOneUse = LHS->hasOneUse() && RHS->hasOneUse(); 769 BuilderTy::FastMathFlagGuard Guard(Builder); 770 if (isa<FPMathOperator>(&I)) 771 Builder.setFastMathFlags(I.getFastMathFlags()); 772 773 Value *V1 = SimplifyBinOp(Opcode, C, E, SQ.getWithInstruction(&I)); 774 Value *V2 = SimplifyBinOp(Opcode, B, D, SQ.getWithInstruction(&I)); 775 if (V1 && V2) 776 SI = Builder.CreateSelect(A, V2, V1); 777 else if (V2 && SelectsHaveOneUse) 778 SI = Builder.CreateSelect(A, V2, Builder.CreateBinOp(Opcode, C, E)); 779 else if (V1 && SelectsHaveOneUse) 780 SI = Builder.CreateSelect(A, Builder.CreateBinOp(Opcode, B, D), V1); 781 782 if (SI) 783 SI->takeName(&I); 784 } 785 786 return SI; 787} 788 789/// Given a 'sub' instruction, return the RHS of the instruction if the LHS is a 790/// constant zero (which is the 'negate' form). 791Value *InstCombiner::dyn_castNegVal(Value *V) const { 792 if (BinaryOperator::isNeg(V)) 793 return BinaryOperator::getNegArgument(V); 794 795 // Constants can be considered to be negated values if they can be folded. 796 if (ConstantInt *C = dyn_cast<ConstantInt>(V)) 797 return ConstantExpr::getNeg(C); 798 799 if (ConstantDataVector *C = dyn_cast<ConstantDataVector>(V)) 800 if (C->getType()->getElementType()->isIntegerTy()) 801 return ConstantExpr::getNeg(C); 802 803 if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) { 804 for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) { 805 Constant *Elt = CV->getAggregateElement(i); 806 if (!Elt) 807 return nullptr; 808 809 if (isa<UndefValue>(Elt)) 810 continue; 811 812 if (!isa<ConstantInt>(Elt)) 813 return nullptr; 814 } 815 return ConstantExpr::getNeg(CV); 816 } 817 818 return nullptr; 819} 820 821/// Given a 'fsub' instruction, return the RHS of the instruction if the LHS is 822/// a constant negative zero (which is the 'negate' form). 823Value *InstCombiner::dyn_castFNegVal(Value *V, bool IgnoreZeroSign) const { 824 if (BinaryOperator::isFNeg(V, IgnoreZeroSign)) 825 return BinaryOperator::getFNegArgument(V); 826 827 // Constants can be considered to be negated values if they can be folded. 828 if (ConstantFP *C = dyn_cast<ConstantFP>(V)) 829 return ConstantExpr::getFNeg(C); 830 831 if (ConstantDataVector *C = dyn_cast<ConstantDataVector>(V)) 832 if (C->getType()->getElementType()->isFloatingPointTy()) 833 return ConstantExpr::getFNeg(C); 834 835 return nullptr; 836} 837 838static Value *foldOperationIntoSelectOperand(Instruction &I, Value *SO, 839 InstCombiner::BuilderTy &Builder) { 840 if (auto *Cast = dyn_cast<CastInst>(&I)) 841 return Builder.CreateCast(Cast->getOpcode(), SO, I.getType()); 842 843 assert(I.isBinaryOp() && "Unexpected opcode for select folding"); 844 845 // Figure out if the constant is the left or the right argument. 846 bool ConstIsRHS = isa<Constant>(I.getOperand(1)); 847 Constant *ConstOperand = cast<Constant>(I.getOperand(ConstIsRHS)); 848 849 if (auto *SOC = dyn_cast<Constant>(SO)) { 850 if (ConstIsRHS) 851 return ConstantExpr::get(I.getOpcode(), SOC, ConstOperand); 852 return ConstantExpr::get(I.getOpcode(), ConstOperand, SOC); 853 } 854 855 Value *Op0 = SO, *Op1 = ConstOperand; 856 if (!ConstIsRHS) 857 std::swap(Op0, Op1); 858 859 auto *BO = cast<BinaryOperator>(&I); 860 Value *RI = Builder.CreateBinOp(BO->getOpcode(), Op0, Op1, 861 SO->getName() + ".op"); 862 auto *FPInst = dyn_cast<Instruction>(RI); 863 if (FPInst && isa<FPMathOperator>(FPInst)) 864 FPInst->copyFastMathFlags(BO); 865 return RI; 866} 867 868Instruction *InstCombiner::FoldOpIntoSelect(Instruction &Op, SelectInst *SI) { 869 // Don't modify shared select instructions. 870 if (!SI->hasOneUse()) 871 return nullptr; 872 873 Value *TV = SI->getTrueValue(); 874 Value *FV = SI->getFalseValue(); 875 if (!(isa<Constant>(TV) || isa<Constant>(FV))) 876 return nullptr; 877 878 // Bool selects with constant operands can be folded to logical ops. 879 if (SI->getType()->isIntOrIntVectorTy(1)) 880 return nullptr; 881 882 // If it's a bitcast involving vectors, make sure it has the same number of 883 // elements on both sides. 884 if (auto *BC = dyn_cast<BitCastInst>(&Op)) { 885 VectorType *DestTy = dyn_cast<VectorType>(BC->getDestTy()); 886 VectorType *SrcTy = dyn_cast<VectorType>(BC->getSrcTy()); 887 888 // Verify that either both or neither are vectors. 889 if ((SrcTy == nullptr) != (DestTy == nullptr)) 890 return nullptr; 891 892 // If vectors, verify that they have the same number of elements. 893 if (SrcTy && SrcTy->getNumElements() != DestTy->getNumElements()) 894 return nullptr; 895 } 896 897 // Test if a CmpInst instruction is used exclusively by a select as 898 // part of a minimum or maximum operation. If so, refrain from doing 899 // any other folding. This helps out other analyses which understand 900 // non-obfuscated minimum and maximum idioms, such as ScalarEvolution 901 // and CodeGen. And in this case, at least one of the comparison 902 // operands has at least one user besides the compare (the select), 903 // which would often largely negate the benefit of folding anyway. 904 if (auto *CI = dyn_cast<CmpInst>(SI->getCondition())) { 905 if (CI->hasOneUse()) { 906 Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1); 907 if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) || 908 (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1)) 909 return nullptr; 910 } 911 } 912 913 Value *NewTV = foldOperationIntoSelectOperand(Op, TV, Builder); 914 Value *NewFV = foldOperationIntoSelectOperand(Op, FV, Builder); 915 return SelectInst::Create(SI->getCondition(), NewTV, NewFV, "", nullptr, SI); 916} 917 918static Value *foldOperationIntoPhiValue(BinaryOperator *I, Value *InV, 919 InstCombiner::BuilderTy &Builder) { 920 bool ConstIsRHS = isa<Constant>(I->getOperand(1)); 921 Constant *C = cast<Constant>(I->getOperand(ConstIsRHS)); 922 923 if (auto *InC = dyn_cast<Constant>(InV)) { 924 if (ConstIsRHS) 925 return ConstantExpr::get(I->getOpcode(), InC, C); 926 return ConstantExpr::get(I->getOpcode(), C, InC); 927 } 928 929 Value *Op0 = InV, *Op1 = C; 930 if (!ConstIsRHS) 931 std::swap(Op0, Op1); 932 933 Value *RI = Builder.CreateBinOp(I->getOpcode(), Op0, Op1, "phitmp"); 934 auto *FPInst = dyn_cast<Instruction>(RI); 935 if (FPInst && isa<FPMathOperator>(FPInst)) 936 FPInst->copyFastMathFlags(I); 937 return RI; 938} 939 940Instruction *InstCombiner::foldOpIntoPhi(Instruction &I, PHINode *PN) { 941 unsigned NumPHIValues = PN->getNumIncomingValues(); 942 if (NumPHIValues == 0) 943 return nullptr; 944 945 // We normally only transform phis with a single use. However, if a PHI has 946 // multiple uses and they are all the same operation, we can fold *all* of the 947 // uses into the PHI. 948 if (!PN->hasOneUse()) { 949 // Walk the use list for the instruction, comparing them to I. 950 for (User *U : PN->users()) { 951 Instruction *UI = cast<Instruction>(U); 952 if (UI != &I && !I.isIdenticalTo(UI)) 953 return nullptr; 954 } 955 // Otherwise, we can replace *all* users with the new PHI we form. 956 } 957 958 // Check to see if all of the operands of the PHI are simple constants 959 // (constantint/constantfp/undef). If there is one non-constant value, 960 // remember the BB it is in. If there is more than one or if *it* is a PHI, 961 // bail out. We don't do arbitrary constant expressions here because moving 962 // their computation can be expensive without a cost model. 963 BasicBlock *NonConstBB = nullptr; 964 for (unsigned i = 0; i != NumPHIValues; ++i) { 965 Value *InVal = PN->getIncomingValue(i); 966 if (isa<Constant>(InVal) && !isa<ConstantExpr>(InVal)) 967 continue; 968 969 if (isa<PHINode>(InVal)) return nullptr; // Itself a phi. 970 if (NonConstBB) return nullptr; // More than one non-const value. 971 972 NonConstBB = PN->getIncomingBlock(i); 973 974 // If the InVal is an invoke at the end of the pred block, then we can't 975 // insert a computation after it without breaking the edge. 976 if (InvokeInst *II = dyn_cast<InvokeInst>(InVal)) 977 if (II->getParent() == NonConstBB) 978 return nullptr; 979 980 // If the incoming non-constant value is in I's block, we will remove one 981 // instruction, but insert another equivalent one, leading to infinite 982 // instcombine. 983 if (isPotentiallyReachable(I.getParent(), NonConstBB, &DT, LI)) 984 return nullptr; 985 } 986 987 // If there is exactly one non-constant value, we can insert a copy of the 988 // operation in that block. However, if this is a critical edge, we would be 989 // inserting the computation on some other paths (e.g. inside a loop). Only 990 // do this if the pred block is unconditionally branching into the phi block. 991 if (NonConstBB != nullptr) { 992 BranchInst *BI = dyn_cast<BranchInst>(NonConstBB->getTerminator()); 993 if (!BI || !BI->isUnconditional()) return nullptr; 994 } 995 996 // Okay, we can do the transformation: create the new PHI node. 997 PHINode *NewPN = PHINode::Create(I.getType(), PN->getNumIncomingValues()); 998 InsertNewInstBefore(NewPN, *PN); 999 NewPN->takeName(PN); 1000 1001 // If we are going to have to insert a new computation, do so right before the 1002 // predecessor's terminator. 1003 if (NonConstBB) 1004 Builder.SetInsertPoint(NonConstBB->getTerminator()); 1005 1006 // Next, add all of the operands to the PHI. 1007 if (SelectInst *SI = dyn_cast<SelectInst>(&I)) { 1008 // We only currently try to fold the condition of a select when it is a phi, 1009 // not the true/false values. 1010 Value *TrueV = SI->getTrueValue(); 1011 Value *FalseV = SI->getFalseValue(); 1012 BasicBlock *PhiTransBB = PN->getParent(); 1013 for (unsigned i = 0; i != NumPHIValues; ++i) { 1014 BasicBlock *ThisBB = PN->getIncomingBlock(i); 1015 Value *TrueVInPred = TrueV->DoPHITranslation(PhiTransBB, ThisBB); 1016 Value *FalseVInPred = FalseV->DoPHITranslation(PhiTransBB, ThisBB); 1017 Value *InV = nullptr; 1018 // Beware of ConstantExpr: it may eventually evaluate to getNullValue, 1019 // even if currently isNullValue gives false. 1020 Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i)); 1021 // For vector constants, we cannot use isNullValue to fold into 1022 // FalseVInPred versus TrueVInPred. When we have individual nonzero 1023 // elements in the vector, we will incorrectly fold InC to 1024 // `TrueVInPred`. 1025 if (InC && !isa<ConstantExpr>(InC) && isa<ConstantInt>(InC)) 1026 InV = InC->isNullValue() ? FalseVInPred : TrueVInPred; 1027 else { 1028 // Generate the select in the same block as PN's current incoming block. 1029 // Note: ThisBB need not be the NonConstBB because vector constants 1030 // which are constants by definition are handled here. 1031 // FIXME: This can lead to an increase in IR generation because we might 1032 // generate selects for vector constant phi operand, that could not be 1033 // folded to TrueVInPred or FalseVInPred as done for ConstantInt. For 1034 // non-vector phis, this transformation was always profitable because 1035 // the select would be generated exactly once in the NonConstBB. 1036 Builder.SetInsertPoint(ThisBB->getTerminator()); 1037 InV = Builder.CreateSelect(PN->getIncomingValue(i), TrueVInPred, 1038 FalseVInPred, "phitmp"); 1039 } 1040 NewPN->addIncoming(InV, ThisBB); 1041 } 1042 } else if (CmpInst *CI = dyn_cast<CmpInst>(&I)) { 1043 Constant *C = cast<Constant>(I.getOperand(1)); 1044 for (unsigned i = 0; i != NumPHIValues; ++i) { 1045 Value *InV = nullptr; 1046 if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i))) 1047 InV = ConstantExpr::getCompare(CI->getPredicate(), InC, C); 1048 else if (isa<ICmpInst>(CI)) 1049 InV = Builder.CreateICmp(CI->getPredicate(), PN->getIncomingValue(i), 1050 C, "phitmp"); 1051 else 1052 InV = Builder.CreateFCmp(CI->getPredicate(), PN->getIncomingValue(i), 1053 C, "phitmp"); 1054 NewPN->addIncoming(InV, PN->getIncomingBlock(i)); 1055 } 1056 } else if (auto *BO = dyn_cast<BinaryOperator>(&I)) { 1057 for (unsigned i = 0; i != NumPHIValues; ++i) { 1058 Value *InV = foldOperationIntoPhiValue(BO, PN->getIncomingValue(i), 1059 Builder); 1060 NewPN->addIncoming(InV, PN->getIncomingBlock(i)); 1061 } 1062 } else { 1063 CastInst *CI = cast<CastInst>(&I); 1064 Type *RetTy = CI->getType(); 1065 for (unsigned i = 0; i != NumPHIValues; ++i) { 1066 Value *InV; 1067 if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i))) 1068 InV = ConstantExpr::getCast(CI->getOpcode(), InC, RetTy); 1069 else 1070 InV = Builder.CreateCast(CI->getOpcode(), PN->getIncomingValue(i), 1071 I.getType(), "phitmp"); 1072 NewPN->addIncoming(InV, PN->getIncomingBlock(i)); 1073 } 1074 } 1075 1076 for (auto UI = PN->user_begin(), E = PN->user_end(); UI != E;) { 1077 Instruction *User = cast<Instruction>(*UI++); 1078 if (User == &I) continue; 1079 replaceInstUsesWith(*User, NewPN); 1080 eraseInstFromFunction(*User); 1081 } 1082 return replaceInstUsesWith(I, NewPN); 1083} 1084 1085Instruction *InstCombiner::foldOpWithConstantIntoOperand(BinaryOperator &I) { 1086 assert(isa<Constant>(I.getOperand(1)) && "Unexpected operand type"); 1087 1088 if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) { 1089 if (Instruction *NewSel = FoldOpIntoSelect(I, Sel)) 1090 return NewSel; 1091 } else if (auto *PN = dyn_cast<PHINode>(I.getOperand(0))) { 1092 if (Instruction *NewPhi = foldOpIntoPhi(I, PN)) 1093 return NewPhi; 1094 } 1095 return nullptr; 1096} 1097 1098/// Given a pointer type and a constant offset, determine whether or not there 1099/// is a sequence of GEP indices into the pointed type that will land us at the 1100/// specified offset. If so, fill them into NewIndices and return the resultant 1101/// element type, otherwise return null. 1102Type *InstCombiner::FindElementAtOffset(PointerType *PtrTy, int64_t Offset, 1103 SmallVectorImpl<Value *> &NewIndices) { 1104 Type *Ty = PtrTy->getElementType(); 1105 if (!Ty->isSized()) 1106 return nullptr; 1107 1108 // Start with the index over the outer type. Note that the type size 1109 // might be zero (even if the offset isn't zero) if the indexed type 1110 // is something like [0 x {int, int}] 1111 Type *IntPtrTy = DL.getIntPtrType(PtrTy); 1112 int64_t FirstIdx = 0; 1113 if (int64_t TySize = DL.getTypeAllocSize(Ty)) { 1114 FirstIdx = Offset/TySize; 1115 Offset -= FirstIdx*TySize; 1116 1117 // Handle hosts where % returns negative instead of values [0..TySize). 1118 if (Offset < 0) { 1119 --FirstIdx; 1120 Offset += TySize; 1121 assert(Offset >= 0); 1122 } 1123 assert((uint64_t)Offset < (uint64_t)TySize && "Out of range offset"); 1124 } 1125 1126 NewIndices.push_back(ConstantInt::get(IntPtrTy, FirstIdx)); 1127 1128 // Index into the types. If we fail, set OrigBase to null. 1129 while (Offset) { 1130 // Indexing into tail padding between struct/array elements. 1131 if (uint64_t(Offset * 8) >= DL.getTypeSizeInBits(Ty)) 1132 return nullptr; 1133 1134 if (StructType *STy = dyn_cast<StructType>(Ty)) { 1135 const StructLayout *SL = DL.getStructLayout(STy); 1136 assert(Offset < (int64_t)SL->getSizeInBytes() && 1137 "Offset must stay within the indexed type"); 1138 1139 unsigned Elt = SL->getElementContainingOffset(Offset); 1140 NewIndices.push_back(ConstantInt::get(Type::getInt32Ty(Ty->getContext()), 1141 Elt)); 1142 1143 Offset -= SL->getElementOffset(Elt); 1144 Ty = STy->getElementType(Elt); 1145 } else if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) { 1146 uint64_t EltSize = DL.getTypeAllocSize(AT->getElementType()); 1147 assert(EltSize && "Cannot index into a zero-sized array"); 1148 NewIndices.push_back(ConstantInt::get(IntPtrTy,Offset/EltSize)); 1149 Offset %= EltSize; 1150 Ty = AT->getElementType(); 1151 } else { 1152 // Otherwise, we can't index into the middle of this atomic type, bail. 1153 return nullptr; 1154 } 1155 } 1156 1157 return Ty; 1158} 1159 1160static bool shouldMergeGEPs(GEPOperator &GEP, GEPOperator &Src) { 1161 // If this GEP has only 0 indices, it is the same pointer as 1162 // Src. If Src is not a trivial GEP too, don't combine 1163 // the indices. 1164 if (GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() && 1165 !Src.hasOneUse()) 1166 return false; 1167 return true; 1168} 1169 1170/// Return a value X such that Val = X * Scale, or null if none. 1171/// If the multiplication is known not to overflow, then NoSignedWrap is set. 1172Value *InstCombiner::Descale(Value *Val, APInt Scale, bool &NoSignedWrap) { 1173 assert(isa<IntegerType>(Val->getType()) && "Can only descale integers!"); 1174 assert(cast<IntegerType>(Val->getType())->getBitWidth() == 1175 Scale.getBitWidth() && "Scale not compatible with value!"); 1176 1177 // If Val is zero or Scale is one then Val = Val * Scale. 1178 if (match(Val, m_Zero()) || Scale == 1) { 1179 NoSignedWrap = true; 1180 return Val; 1181 } 1182 1183 // If Scale is zero then it does not divide Val. 1184 if (Scale.isMinValue()) 1185 return nullptr; 1186 1187 // Look through chains of multiplications, searching for a constant that is 1188 // divisible by Scale. For example, descaling X*(Y*(Z*4)) by a factor of 4 1189 // will find the constant factor 4 and produce X*(Y*Z). Descaling X*(Y*8) by 1190 // a factor of 4 will produce X*(Y*2). The principle of operation is to bore 1191 // down from Val: 1192 // 1193 // Val = M1 * X || Analysis starts here and works down 1194 // M1 = M2 * Y || Doesn't descend into terms with more 1195 // M2 = Z * 4 \/ than one use 1196 // 1197 // Then to modify a term at the bottom: 1198 // 1199 // Val = M1 * X 1200 // M1 = Z * Y || Replaced M2 with Z 1201 // 1202 // Then to work back up correcting nsw flags. 1203 1204 // Op - the term we are currently analyzing. Starts at Val then drills down. 1205 // Replaced with its descaled value before exiting from the drill down loop. 1206 Value *Op = Val; 1207 1208 // Parent - initially null, but after drilling down notes where Op came from. 1209 // In the example above, Parent is (Val, 0) when Op is M1, because M1 is the 1210 // 0'th operand of Val. 1211 std::pair<Instruction *, unsigned> Parent; 1212 1213 // Set if the transform requires a descaling at deeper levels that doesn't 1214 // overflow. 1215 bool RequireNoSignedWrap = false; 1216 1217 // Log base 2 of the scale. Negative if not a power of 2. 1218 int32_t logScale = Scale.exactLogBase2(); 1219 1220 for (;; Op = Parent.first->getOperand(Parent.second)) { // Drill down 1221 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) { 1222 // If Op is a constant divisible by Scale then descale to the quotient. 1223 APInt Quotient(Scale), Remainder(Scale); // Init ensures right bitwidth. 1224 APInt::sdivrem(CI->getValue(), Scale, Quotient, Remainder); 1225 if (!Remainder.isMinValue()) 1226 // Not divisible by Scale. 1227 return nullptr; 1228 // Replace with the quotient in the parent. 1229 Op = ConstantInt::get(CI->getType(), Quotient); 1230 NoSignedWrap = true; 1231 break; 1232 } 1233 1234 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op)) { 1235 if (BO->getOpcode() == Instruction::Mul) { 1236 // Multiplication. 1237 NoSignedWrap = BO->hasNoSignedWrap(); 1238 if (RequireNoSignedWrap && !NoSignedWrap) 1239 return nullptr; 1240 1241 // There are three cases for multiplication: multiplication by exactly 1242 // the scale, multiplication by a constant different to the scale, and 1243 // multiplication by something else. 1244 Value *LHS = BO->getOperand(0); 1245 Value *RHS = BO->getOperand(1); 1246 1247 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1248 // Multiplication by a constant. 1249 if (CI->getValue() == Scale) { 1250 // Multiplication by exactly the scale, replace the multiplication 1251 // by its left-hand side in the parent. 1252 Op = LHS; 1253 break; 1254 } 1255 1256 // Otherwise drill down into the constant. 1257 if (!Op->hasOneUse()) 1258 return nullptr; 1259 1260 Parent = std::make_pair(BO, 1); 1261 continue; 1262 } 1263 1264 // Multiplication by something else. Drill down into the left-hand side 1265 // since that's where the reassociate pass puts the good stuff. 1266 if (!Op->hasOneUse()) 1267 return nullptr; 1268 1269 Parent = std::make_pair(BO, 0); 1270 continue; 1271 } 1272 1273 if (logScale > 0 && BO->getOpcode() == Instruction::Shl && 1274 isa<ConstantInt>(BO->getOperand(1))) { 1275 // Multiplication by a power of 2. 1276 NoSignedWrap = BO->hasNoSignedWrap(); 1277 if (RequireNoSignedWrap && !NoSignedWrap) 1278 return nullptr; 1279 1280 Value *LHS = BO->getOperand(0); 1281 int32_t Amt = cast<ConstantInt>(BO->getOperand(1))-> 1282 getLimitedValue(Scale.getBitWidth()); 1283 // Op = LHS << Amt. 1284 1285 if (Amt == logScale) { 1286 // Multiplication by exactly the scale, replace the multiplication 1287 // by its left-hand side in the parent. 1288 Op = LHS; 1289 break; 1290 } 1291 if (Amt < logScale || !Op->hasOneUse()) 1292 return nullptr; 1293 1294 // Multiplication by more than the scale. Reduce the multiplying amount 1295 // by the scale in the parent. 1296 Parent = std::make_pair(BO, 1); 1297 Op = ConstantInt::get(BO->getType(), Amt - logScale); 1298 break; 1299 } 1300 } 1301 1302 if (!Op->hasOneUse()) 1303 return nullptr; 1304 1305 if (CastInst *Cast = dyn_cast<CastInst>(Op)) { 1306 if (Cast->getOpcode() == Instruction::SExt) { 1307 // Op is sign-extended from a smaller type, descale in the smaller type. 1308 unsigned SmallSize = Cast->getSrcTy()->getPrimitiveSizeInBits(); 1309 APInt SmallScale = Scale.trunc(SmallSize); 1310 // Suppose Op = sext X, and we descale X as Y * SmallScale. We want to 1311 // descale Op as (sext Y) * Scale. In order to have 1312 // sext (Y * SmallScale) = (sext Y) * Scale 1313 // some conditions need to hold however: SmallScale must sign-extend to 1314 // Scale and the multiplication Y * SmallScale should not overflow. 1315 if (SmallScale.sext(Scale.getBitWidth()) != Scale) 1316 // SmallScale does not sign-extend to Scale. 1317 return nullptr; 1318 assert(SmallScale.exactLogBase2() == logScale); 1319 // Require that Y * SmallScale must not overflow. 1320 RequireNoSignedWrap = true; 1321 1322 // Drill down through the cast. 1323 Parent = std::make_pair(Cast, 0); 1324 Scale = SmallScale; 1325 continue; 1326 } 1327 1328 if (Cast->getOpcode() == Instruction::Trunc) { 1329 // Op is truncated from a larger type, descale in the larger type. 1330 // Suppose Op = trunc X, and we descale X as Y * sext Scale. Then 1331 // trunc (Y * sext Scale) = (trunc Y) * Scale 1332 // always holds. However (trunc Y) * Scale may overflow even if 1333 // trunc (Y * sext Scale) does not, so nsw flags need to be cleared 1334 // from this point up in the expression (see later). 1335 if (RequireNoSignedWrap) 1336 return nullptr; 1337 1338 // Drill down through the cast. 1339 unsigned LargeSize = Cast->getSrcTy()->getPrimitiveSizeInBits(); 1340 Parent = std::make_pair(Cast, 0); 1341 Scale = Scale.sext(LargeSize); 1342 if (logScale + 1 == (int32_t)Cast->getType()->getPrimitiveSizeInBits()) 1343 logScale = -1; 1344 assert(Scale.exactLogBase2() == logScale); 1345 continue; 1346 } 1347 } 1348 1349 // Unsupported expression, bail out. 1350 return nullptr; 1351 } 1352 1353 // If Op is zero then Val = Op * Scale. 1354 if (match(Op, m_Zero())) { 1355 NoSignedWrap = true; 1356 return Op; 1357 } 1358 1359 // We know that we can successfully descale, so from here on we can safely 1360 // modify the IR. Op holds the descaled version of the deepest term in the 1361 // expression. NoSignedWrap is 'true' if multiplying Op by Scale is known 1362 // not to overflow. 1363 1364 if (!Parent.first) 1365 // The expression only had one term. 1366 return Op; 1367 1368 // Rewrite the parent using the descaled version of its operand. 1369 assert(Parent.first->hasOneUse() && "Drilled down when more than one use!"); 1370 assert(Op != Parent.first->getOperand(Parent.second) && 1371 "Descaling was a no-op?"); 1372 Parent.first->setOperand(Parent.second, Op); 1373 Worklist.Add(Parent.first); 1374 1375 // Now work back up the expression correcting nsw flags. The logic is based 1376 // on the following observation: if X * Y is known not to overflow as a signed 1377 // multiplication, and Y is replaced by a value Z with smaller absolute value, 1378 // then X * Z will not overflow as a signed multiplication either. As we work 1379 // our way up, having NoSignedWrap 'true' means that the descaled value at the 1380 // current level has strictly smaller absolute value than the original. 1381 Instruction *Ancestor = Parent.first; 1382 do { 1383 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Ancestor)) { 1384 // If the multiplication wasn't nsw then we can't say anything about the 1385 // value of the descaled multiplication, and we have to clear nsw flags 1386 // from this point on up. 1387 bool OpNoSignedWrap = BO->hasNoSignedWrap(); 1388 NoSignedWrap &= OpNoSignedWrap; 1389 if (NoSignedWrap != OpNoSignedWrap) { 1390 BO->setHasNoSignedWrap(NoSignedWrap); 1391 Worklist.Add(Ancestor); 1392 } 1393 } else if (Ancestor->getOpcode() == Instruction::Trunc) { 1394 // The fact that the descaled input to the trunc has smaller absolute 1395 // value than the original input doesn't tell us anything useful about 1396 // the absolute values of the truncations. 1397 NoSignedWrap = false; 1398 } 1399 assert((Ancestor->getOpcode() != Instruction::SExt || NoSignedWrap) && 1400 "Failed to keep proper track of nsw flags while drilling down?"); 1401 1402 if (Ancestor == Val) 1403 // Got to the top, all done! 1404 return Val; 1405 1406 // Move up one level in the expression. 1407 assert(Ancestor->hasOneUse() && "Drilled down when more than one use!"); 1408 Ancestor = Ancestor->user_back(); 1409 } while (true); 1410} 1411 1412/// \brief Creates node of binary operation with the same attributes as the 1413/// specified one but with other operands. 1414static Value *CreateBinOpAsGiven(BinaryOperator &Inst, Value *LHS, Value *RHS, 1415 InstCombiner::BuilderTy &B) { 1416 Value *BO = B.CreateBinOp(Inst.getOpcode(), LHS, RHS); 1417 // If LHS and RHS are constant, BO won't be a binary operator. 1418 if (BinaryOperator *NewBO = dyn_cast<BinaryOperator>(BO)) 1419 NewBO->copyIRFlags(&Inst); 1420 return BO; 1421} 1422 1423/// \brief Makes transformation of binary operation specific for vector types. 1424/// \param Inst Binary operator to transform. 1425/// \return Pointer to node that must replace the original binary operator, or 1426/// null pointer if no transformation was made. 1427Value *InstCombiner::SimplifyVectorOp(BinaryOperator &Inst) { 1428 if (!Inst.getType()->isVectorTy()) return nullptr; 1429 1430 // It may not be safe to reorder shuffles and things like div, urem, etc. 1431 // because we may trap when executing those ops on unknown vector elements. 1432 // See PR20059. 1433 if (!isSafeToSpeculativelyExecute(&Inst)) 1434 return nullptr; 1435 1436 unsigned VWidth = cast<VectorType>(Inst.getType())->getNumElements(); 1437 Value *LHS = Inst.getOperand(0), *RHS = Inst.getOperand(1); 1438 assert(cast<VectorType>(LHS->getType())->getNumElements() == VWidth); 1439 assert(cast<VectorType>(RHS->getType())->getNumElements() == VWidth); 1440 1441 // If both arguments of the binary operation are shuffles that use the same 1442 // mask and shuffle within a single vector, move the shuffle after the binop: 1443 // Op(shuffle(v1, m), shuffle(v2, m)) -> shuffle(Op(v1, v2), m) 1444 auto *LShuf = dyn_cast<ShuffleVectorInst>(LHS); 1445 auto *RShuf = dyn_cast<ShuffleVectorInst>(RHS); 1446 if (LShuf && RShuf && LShuf->getMask() == RShuf->getMask() && 1447 isa<UndefValue>(LShuf->getOperand(1)) && 1448 isa<UndefValue>(RShuf->getOperand(1)) && 1449 LShuf->getOperand(0)->getType() == RShuf->getOperand(0)->getType()) { 1450 Value *NewBO = CreateBinOpAsGiven(Inst, LShuf->getOperand(0), 1451 RShuf->getOperand(0), Builder); 1452 return Builder.CreateShuffleVector( 1453 NewBO, UndefValue::get(NewBO->getType()), LShuf->getMask()); 1454 } 1455 1456 // If one argument is a shuffle within one vector, the other is a constant, 1457 // try moving the shuffle after the binary operation. 1458 ShuffleVectorInst *Shuffle = nullptr; 1459 Constant *C1 = nullptr; 1460 if (isa<ShuffleVectorInst>(LHS)) Shuffle = cast<ShuffleVectorInst>(LHS); 1461 if (isa<ShuffleVectorInst>(RHS)) Shuffle = cast<ShuffleVectorInst>(RHS); 1462 if (isa<Constant>(LHS)) C1 = cast<Constant>(LHS); 1463 if (isa<Constant>(RHS)) C1 = cast<Constant>(RHS); 1464 if (Shuffle && C1 && 1465 (isa<ConstantVector>(C1) || isa<ConstantDataVector>(C1)) && 1466 isa<UndefValue>(Shuffle->getOperand(1)) && 1467 Shuffle->getType() == Shuffle->getOperand(0)->getType()) { 1468 SmallVector<int, 16> ShMask = Shuffle->getShuffleMask(); 1469 // Find constant C2 that has property: 1470 // shuffle(C2, ShMask) = C1 1471 // If such constant does not exist (example: ShMask=<0,0> and C1=<1,2>) 1472 // reorder is not possible. 1473 SmallVector<Constant*, 16> C2M(VWidth, 1474 UndefValue::get(C1->getType()->getScalarType())); 1475 bool MayChange = true; 1476 for (unsigned I = 0; I < VWidth; ++I) { 1477 if (ShMask[I] >= 0) { 1478 assert(ShMask[I] < (int)VWidth); 1479 if (!isa<UndefValue>(C2M[ShMask[I]])) { 1480 MayChange = false; 1481 break; 1482 } 1483 C2M[ShMask[I]] = C1->getAggregateElement(I); 1484 } 1485 } 1486 if (MayChange) { 1487 Constant *C2 = ConstantVector::get(C2M); 1488 Value *NewLHS = isa<Constant>(LHS) ? C2 : Shuffle->getOperand(0); 1489 Value *NewRHS = isa<Constant>(LHS) ? Shuffle->getOperand(0) : C2; 1490 Value *NewBO = CreateBinOpAsGiven(Inst, NewLHS, NewRHS, Builder); 1491 return Builder.CreateShuffleVector(NewBO, 1492 UndefValue::get(Inst.getType()), Shuffle->getMask()); 1493 } 1494 } 1495 1496 return nullptr; 1497} 1498 1499Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { 1500 SmallVector<Value*, 8> Ops(GEP.op_begin(), GEP.op_end()); 1501 1502 if (Value *V = SimplifyGEPInst(GEP.getSourceElementType(), Ops, 1503 SQ.getWithInstruction(&GEP))) 1504 return replaceInstUsesWith(GEP, V); 1505 1506 Value *PtrOp = GEP.getOperand(0); 1507 1508 // Eliminate unneeded casts for indices, and replace indices which displace 1509 // by multiples of a zero size type with zero. 1510 bool MadeChange = false; 1511 Type *IntPtrTy = 1512 DL.getIntPtrType(GEP.getPointerOperandType()->getScalarType()); 1513 1514 gep_type_iterator GTI = gep_type_begin(GEP); 1515 for (User::op_iterator I = GEP.op_begin() + 1, E = GEP.op_end(); I != E; 1516 ++I, ++GTI) { 1517 // Skip indices into struct types. 1518 if (GTI.isStruct()) 1519 continue; 1520 1521 // Index type should have the same width as IntPtr 1522 Type *IndexTy = (*I)->getType(); 1523 Type *NewIndexType = IndexTy->isVectorTy() ? 1524 VectorType::get(IntPtrTy, IndexTy->getVectorNumElements()) : IntPtrTy; 1525 1526 // If the element type has zero size then any index over it is equivalent 1527 // to an index of zero, so replace it with zero if it is not zero already. 1528 Type *EltTy = GTI.getIndexedType(); 1529 if (EltTy->isSized() && DL.getTypeAllocSize(EltTy) == 0) 1530 if (!isa<Constant>(*I) || !cast<Constant>(*I)->isNullValue()) { 1531 *I = Constant::getNullValue(NewIndexType); 1532 MadeChange = true; 1533 } 1534 1535 if (IndexTy != NewIndexType) { 1536 // If we are using a wider index than needed for this platform, shrink 1537 // it to what we need. If narrower, sign-extend it to what we need. 1538 // This explicit cast can make subsequent optimizations more obvious. 1539 *I = Builder.CreateIntCast(*I, NewIndexType, true); 1540 MadeChange = true; 1541 } 1542 } 1543 if (MadeChange) 1544 return &GEP; 1545 1546 // Check to see if the inputs to the PHI node are getelementptr instructions. 1547 if (PHINode *PN = dyn_cast<PHINode>(PtrOp)) { 1548 GetElementPtrInst *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0)); 1549 if (!Op1) 1550 return nullptr; 1551 1552 // Don't fold a GEP into itself through a PHI node. This can only happen 1553 // through the back-edge of a loop. Folding a GEP into itself means that 1554 // the value of the previous iteration needs to be stored in the meantime, 1555 // thus requiring an additional register variable to be live, but not 1556 // actually achieving anything (the GEP still needs to be executed once per 1557 // loop iteration). 1558 if (Op1 == &GEP) 1559 return nullptr; 1560 1561 int DI = -1; 1562 1563 for (auto I = PN->op_begin()+1, E = PN->op_end(); I !=E; ++I) { 1564 GetElementPtrInst *Op2 = dyn_cast<GetElementPtrInst>(*I); 1565 if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands()) 1566 return nullptr; 1567 1568 // As for Op1 above, don't try to fold a GEP into itself. 1569 if (Op2 == &GEP) 1570 return nullptr; 1571 1572 // Keep track of the type as we walk the GEP. 1573 Type *CurTy = nullptr; 1574 1575 for (unsigned J = 0, F = Op1->getNumOperands(); J != F; ++J) { 1576 if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType()) 1577 return nullptr; 1578 1579 if (Op1->getOperand(J) != Op2->getOperand(J)) { 1580 if (DI == -1) { 1581 // We have not seen any differences yet in the GEPs feeding the 1582 // PHI yet, so we record this one if it is allowed to be a 1583 // variable. 1584 1585 // The first two arguments can vary for any GEP, the rest have to be 1586 // static for struct slots 1587 if (J > 1 && CurTy->isStructTy()) 1588 return nullptr; 1589 1590 DI = J; 1591 } else { 1592 // The GEP is different by more than one input. While this could be 1593 // extended to support GEPs that vary by more than one variable it 1594 // doesn't make sense since it greatly increases the complexity and 1595 // would result in an R+R+R addressing mode which no backend 1596 // directly supports and would need to be broken into several 1597 // simpler instructions anyway. 1598 return nullptr; 1599 } 1600 } 1601 1602 // Sink down a layer of the type for the next iteration. 1603 if (J > 0) { 1604 if (J == 1) { 1605 CurTy = Op1->getSourceElementType(); 1606 } else if (CompositeType *CT = dyn_cast<CompositeType>(CurTy)) { 1607 CurTy = CT->getTypeAtIndex(Op1->getOperand(J)); 1608 } else { 1609 CurTy = nullptr; 1610 } 1611 } 1612 } 1613 } 1614 1615 // If not all GEPs are identical we'll have to create a new PHI node. 1616 // Check that the old PHI node has only one use so that it will get 1617 // removed. 1618 if (DI != -1 && !PN->hasOneUse()) 1619 return nullptr; 1620 1621 GetElementPtrInst *NewGEP = cast<GetElementPtrInst>(Op1->clone()); 1622 if (DI == -1) { 1623 // All the GEPs feeding the PHI are identical. Clone one down into our 1624 // BB so that it can be merged with the current GEP. 1625 GEP.getParent()->getInstList().insert( 1626 GEP.getParent()->getFirstInsertionPt(), NewGEP); 1627 } else { 1628 // All the GEPs feeding the PHI differ at a single offset. Clone a GEP 1629 // into the current block so it can be merged, and create a new PHI to 1630 // set that index. 1631 PHINode *NewPN; 1632 { 1633 IRBuilderBase::InsertPointGuard Guard(Builder); 1634 Builder.SetInsertPoint(PN); 1635 NewPN = Builder.CreatePHI(Op1->getOperand(DI)->getType(), 1636 PN->getNumOperands()); 1637 } 1638 1639 for (auto &I : PN->operands()) 1640 NewPN->addIncoming(cast<GEPOperator>(I)->getOperand(DI), 1641 PN->getIncomingBlock(I)); 1642 1643 NewGEP->setOperand(DI, NewPN); 1644 GEP.getParent()->getInstList().insert( 1645 GEP.getParent()->getFirstInsertionPt(), NewGEP); 1646 NewGEP->setOperand(DI, NewPN); 1647 } 1648 1649 GEP.setOperand(0, NewGEP); 1650 PtrOp = NewGEP; 1651 } 1652 1653 // Combine Indices - If the source pointer to this getelementptr instruction 1654 // is a getelementptr instruction, combine the indices of the two 1655 // getelementptr instructions into a single instruction. 1656 if (GEPOperator *Src = dyn_cast<GEPOperator>(PtrOp)) { 1657 if (!shouldMergeGEPs(*cast<GEPOperator>(&GEP), *Src)) 1658 return nullptr; 1659 1660 // Note that if our source is a gep chain itself then we wait for that 1661 // chain to be resolved before we perform this transformation. This 1662 // avoids us creating a TON of code in some cases. 1663 if (GEPOperator *SrcGEP = 1664 dyn_cast<GEPOperator>(Src->getOperand(0))) 1665 if (SrcGEP->getNumOperands() == 2 && shouldMergeGEPs(*Src, *SrcGEP)) 1666 return nullptr; // Wait until our source is folded to completion. 1667 1668 SmallVector<Value*, 8> Indices; 1669 1670 // Find out whether the last index in the source GEP is a sequential idx. 1671 bool EndsWithSequential = false; 1672 for (gep_type_iterator I = gep_type_begin(*Src), E = gep_type_end(*Src); 1673 I != E; ++I) 1674 EndsWithSequential = I.isSequential(); 1675 1676 // Can we combine the two pointer arithmetics offsets? 1677 if (EndsWithSequential) { 1678 // Replace: gep (gep %P, long B), long A, ... 1679 // With: T = long A+B; gep %P, T, ... 1680 Value *SO1 = Src->getOperand(Src->getNumOperands()-1); 1681 Value *GO1 = GEP.getOperand(1); 1682 1683 // If they aren't the same type, then the input hasn't been processed 1684 // by the loop above yet (which canonicalizes sequential index types to 1685 // intptr_t). Just avoid transforming this until the input has been 1686 // normalized. 1687 if (SO1->getType() != GO1->getType()) 1688 return nullptr; 1689 1690 Value *Sum = 1691 SimplifyAddInst(GO1, SO1, false, false, SQ.getWithInstruction(&GEP)); 1692 // Only do the combine when we are sure the cost after the 1693 // merge is never more than that before the merge. 1694 if (Sum == nullptr) 1695 return nullptr; 1696 1697 // Update the GEP in place if possible. 1698 if (Src->getNumOperands() == 2) { 1699 GEP.setOperand(0, Src->getOperand(0)); 1700 GEP.setOperand(1, Sum); 1701 return &GEP; 1702 } 1703 Indices.append(Src->op_begin()+1, Src->op_end()-1); 1704 Indices.push_back(Sum); 1705 Indices.append(GEP.op_begin()+2, GEP.op_end()); 1706 } else if (isa<Constant>(*GEP.idx_begin()) && 1707 cast<Constant>(*GEP.idx_begin())->isNullValue() && 1708 Src->getNumOperands() != 1) { 1709 // Otherwise we can do the fold if the first index of the GEP is a zero 1710 Indices.append(Src->op_begin()+1, Src->op_end()); 1711 Indices.append(GEP.idx_begin()+1, GEP.idx_end()); 1712 } 1713 1714 if (!Indices.empty()) 1715 return GEP.isInBounds() && Src->isInBounds() 1716 ? GetElementPtrInst::CreateInBounds( 1717 Src->getSourceElementType(), Src->getOperand(0), Indices, 1718 GEP.getName()) 1719 : GetElementPtrInst::Create(Src->getSourceElementType(), 1720 Src->getOperand(0), Indices, 1721 GEP.getName()); 1722 } 1723 1724 if (GEP.getNumIndices() == 1) { 1725 unsigned AS = GEP.getPointerAddressSpace(); 1726 if (GEP.getOperand(1)->getType()->getScalarSizeInBits() == 1727 DL.getPointerSizeInBits(AS)) { 1728 Type *Ty = GEP.getSourceElementType(); 1729 uint64_t TyAllocSize = DL.getTypeAllocSize(Ty); 1730 1731 bool Matched = false; 1732 uint64_t C; 1733 Value *V = nullptr; 1734 if (TyAllocSize == 1) { 1735 V = GEP.getOperand(1); 1736 Matched = true; 1737 } else if (match(GEP.getOperand(1), 1738 m_AShr(m_Value(V), m_ConstantInt(C)))) { 1739 if (TyAllocSize == 1ULL << C) 1740 Matched = true; 1741 } else if (match(GEP.getOperand(1), 1742 m_SDiv(m_Value(V), m_ConstantInt(C)))) { 1743 if (TyAllocSize == C) 1744 Matched = true; 1745 } 1746 1747 if (Matched) { 1748 // Canonicalize (gep i8* X, -(ptrtoint Y)) 1749 // to (inttoptr (sub (ptrtoint X), (ptrtoint Y))) 1750 // The GEP pattern is emitted by the SCEV expander for certain kinds of 1751 // pointer arithmetic. 1752 if (match(V, m_Neg(m_PtrToInt(m_Value())))) { 1753 Operator *Index = cast<Operator>(V); 1754 Value *PtrToInt = Builder.CreatePtrToInt(PtrOp, Index->getType()); 1755 Value *NewSub = Builder.CreateSub(PtrToInt, Index->getOperand(1)); 1756 return CastInst::Create(Instruction::IntToPtr, NewSub, GEP.getType()); 1757 } 1758 // Canonicalize (gep i8* X, (ptrtoint Y)-(ptrtoint X)) 1759 // to (bitcast Y) 1760 Value *Y; 1761 if (match(V, m_Sub(m_PtrToInt(m_Value(Y)), 1762 m_PtrToInt(m_Specific(GEP.getOperand(0)))))) { 1763 return CastInst::CreatePointerBitCastOrAddrSpaceCast(Y, 1764 GEP.getType()); 1765 } 1766 } 1767 } 1768 } 1769 1770 // We do not handle pointer-vector geps here. 1771 if (GEP.getType()->isVectorTy()) 1772 return nullptr; 1773 1774 // Handle gep(bitcast x) and gep(gep x, 0, 0, 0). 1775 Value *StrippedPtr = PtrOp->stripPointerCasts(); 1776 PointerType *StrippedPtrTy = cast<PointerType>(StrippedPtr->getType()); 1777 1778 if (StrippedPtr != PtrOp) { 1779 bool HasZeroPointerIndex = false; 1780 if (ConstantInt *C = dyn_cast<ConstantInt>(GEP.getOperand(1))) 1781 HasZeroPointerIndex = C->isZero(); 1782 1783 // Transform: GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ... 1784 // into : GEP [10 x i8]* X, i32 0, ... 1785 // 1786 // Likewise, transform: GEP (bitcast i8* X to [0 x i8]*), i32 0, ... 1787 // into : GEP i8* X, ... 1788 // 1789 // This occurs when the program declares an array extern like "int X[];" 1790 if (HasZeroPointerIndex) { 1791 if (ArrayType *CATy = 1792 dyn_cast<ArrayType>(GEP.getSourceElementType())) { 1793 // GEP (bitcast i8* X to [0 x i8]*), i32 0, ... ? 1794 if (CATy->getElementType() == StrippedPtrTy->getElementType()) { 1795 // -> GEP i8* X, ... 1796 SmallVector<Value*, 8> Idx(GEP.idx_begin()+1, GEP.idx_end()); 1797 GetElementPtrInst *Res = GetElementPtrInst::Create( 1798 StrippedPtrTy->getElementType(), StrippedPtr, Idx, GEP.getName()); 1799 Res->setIsInBounds(GEP.isInBounds()); 1800 if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace()) 1801 return Res; 1802 // Insert Res, and create an addrspacecast. 1803 // e.g., 1804 // GEP (addrspacecast i8 addrspace(1)* X to [0 x i8]*), i32 0, ... 1805 // -> 1806 // %0 = GEP i8 addrspace(1)* X, ... 1807 // addrspacecast i8 addrspace(1)* %0 to i8* 1808 return new AddrSpaceCastInst(Builder.Insert(Res), GEP.getType()); 1809 } 1810 1811 if (ArrayType *XATy = 1812 dyn_cast<ArrayType>(StrippedPtrTy->getElementType())){ 1813 // GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ... ? 1814 if (CATy->getElementType() == XATy->getElementType()) { 1815 // -> GEP [10 x i8]* X, i32 0, ... 1816 // At this point, we know that the cast source type is a pointer 1817 // to an array of the same type as the destination pointer 1818 // array. Because the array type is never stepped over (there 1819 // is a leading zero) we can fold the cast into this GEP. 1820 if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace()) { 1821 GEP.setOperand(0, StrippedPtr); 1822 GEP.setSourceElementType(XATy); 1823 return &GEP; 1824 } 1825 // Cannot replace the base pointer directly because StrippedPtr's 1826 // address space is different. Instead, create a new GEP followed by 1827 // an addrspacecast. 1828 // e.g., 1829 // GEP (addrspacecast [10 x i8] addrspace(1)* X to [0 x i8]*), 1830 // i32 0, ... 1831 // -> 1832 // %0 = GEP [10 x i8] addrspace(1)* X, ... 1833 // addrspacecast i8 addrspace(1)* %0 to i8* 1834 SmallVector<Value*, 8> Idx(GEP.idx_begin(), GEP.idx_end()); 1835 Value *NewGEP = GEP.isInBounds() 1836 ? Builder.CreateInBoundsGEP( 1837 nullptr, StrippedPtr, Idx, GEP.getName()) 1838 : Builder.CreateGEP(nullptr, StrippedPtr, Idx, 1839 GEP.getName()); 1840 return new AddrSpaceCastInst(NewGEP, GEP.getType()); 1841 } 1842 } 1843 } 1844 } else if (GEP.getNumOperands() == 2) { 1845 // Transform things like: 1846 // %t = getelementptr i32* bitcast ([2 x i32]* %str to i32*), i32 %V 1847 // into: %t1 = getelementptr [2 x i32]* %str, i32 0, i32 %V; bitcast 1848 Type *SrcElTy = StrippedPtrTy->getElementType(); 1849 Type *ResElTy = GEP.getSourceElementType(); 1850 if (SrcElTy->isArrayTy() && 1851 DL.getTypeAllocSize(SrcElTy->getArrayElementType()) == 1852 DL.getTypeAllocSize(ResElTy)) { 1853 Type *IdxType = DL.getIntPtrType(GEP.getType()); 1854 Value *Idx[2] = { Constant::getNullValue(IdxType), GEP.getOperand(1) }; 1855 Value *NewGEP = 1856 GEP.isInBounds() 1857 ? Builder.CreateInBoundsGEP(nullptr, StrippedPtr, Idx, 1858 GEP.getName()) 1859 : Builder.CreateGEP(nullptr, StrippedPtr, Idx, GEP.getName()); 1860 1861 // V and GEP are both pointer types --> BitCast 1862 return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP, 1863 GEP.getType()); 1864 } 1865 1866 // Transform things like: 1867 // %V = mul i64 %N, 4 1868 // %t = getelementptr i8* bitcast (i32* %arr to i8*), i32 %V 1869 // into: %t1 = getelementptr i32* %arr, i32 %N; bitcast 1870 if (ResElTy->isSized() && SrcElTy->isSized()) { 1871 // Check that changing the type amounts to dividing the index by a scale 1872 // factor. 1873 uint64_t ResSize = DL.getTypeAllocSize(ResElTy); 1874 uint64_t SrcSize = DL.getTypeAllocSize(SrcElTy); 1875 if (ResSize && SrcSize % ResSize == 0) { 1876 Value *Idx = GEP.getOperand(1); 1877 unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits(); 1878 uint64_t Scale = SrcSize / ResSize; 1879 1880 // Earlier transforms ensure that the index has type IntPtrType, which 1881 // considerably simplifies the logic by eliminating implicit casts. 1882 assert(Idx->getType() == DL.getIntPtrType(GEP.getType()) && 1883 "Index not cast to pointer width?"); 1884 1885 bool NSW; 1886 if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) { 1887 // Successfully decomposed Idx as NewIdx * Scale, form a new GEP. 1888 // If the multiplication NewIdx * Scale may overflow then the new 1889 // GEP may not be "inbounds". 1890 Value *NewGEP = 1891 GEP.isInBounds() && NSW 1892 ? Builder.CreateInBoundsGEP(nullptr, StrippedPtr, NewIdx, 1893 GEP.getName()) 1894 : Builder.CreateGEP(nullptr, StrippedPtr, NewIdx, 1895 GEP.getName()); 1896 1897 // The NewGEP must be pointer typed, so must the old one -> BitCast 1898 return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP, 1899 GEP.getType()); 1900 } 1901 } 1902 } 1903 1904 // Similarly, transform things like: 1905 // getelementptr i8* bitcast ([100 x double]* X to i8*), i32 %tmp 1906 // (where tmp = 8*tmp2) into: 1907 // getelementptr [100 x double]* %arr, i32 0, i32 %tmp2; bitcast 1908 if (ResElTy->isSized() && SrcElTy->isSized() && SrcElTy->isArrayTy()) { 1909 // Check that changing to the array element type amounts to dividing the 1910 // index by a scale factor. 1911 uint64_t ResSize = DL.getTypeAllocSize(ResElTy); 1912 uint64_t ArrayEltSize = 1913 DL.getTypeAllocSize(SrcElTy->getArrayElementType()); 1914 if (ResSize && ArrayEltSize % ResSize == 0) { 1915 Value *Idx = GEP.getOperand(1); 1916 unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits(); 1917 uint64_t Scale = ArrayEltSize / ResSize; 1918 1919 // Earlier transforms ensure that the index has type IntPtrType, which 1920 // considerably simplifies the logic by eliminating implicit casts. 1921 assert(Idx->getType() == DL.getIntPtrType(GEP.getType()) && 1922 "Index not cast to pointer width?"); 1923 1924 bool NSW; 1925 if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) { 1926 // Successfully decomposed Idx as NewIdx * Scale, form a new GEP. 1927 // If the multiplication NewIdx * Scale may overflow then the new 1928 // GEP may not be "inbounds". 1929 Value *Off[2] = { 1930 Constant::getNullValue(DL.getIntPtrType(GEP.getType())), 1931 NewIdx}; 1932 1933 Value *NewGEP = GEP.isInBounds() && NSW 1934 ? Builder.CreateInBoundsGEP( 1935 SrcElTy, StrippedPtr, Off, GEP.getName()) 1936 : Builder.CreateGEP(SrcElTy, StrippedPtr, Off, 1937 GEP.getName()); 1938 // The NewGEP must be pointer typed, so must the old one -> BitCast 1939 return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP, 1940 GEP.getType()); 1941 } 1942 } 1943 } 1944 } 1945 } 1946 1947 // addrspacecast between types is canonicalized as a bitcast, then an 1948 // addrspacecast. To take advantage of the below bitcast + struct GEP, look 1949 // through the addrspacecast. 1950 Value *ASCStrippedPtrOp = PtrOp; 1951 if (AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(PtrOp)) { 1952 // X = bitcast A addrspace(1)* to B addrspace(1)* 1953 // Y = addrspacecast A addrspace(1)* to B addrspace(2)* 1954 // Z = gep Y, <...constant indices...> 1955 // Into an addrspacecasted GEP of the struct. 1956 if (BitCastInst *BC = dyn_cast<BitCastInst>(ASC->getOperand(0))) 1957 ASCStrippedPtrOp = BC; 1958 } 1959 1960 /// See if we can simplify: 1961 /// X = bitcast A* to B* 1962 /// Y = gep X, <...constant indices...> 1963 /// into a gep of the original struct. This is important for SROA and alias 1964 /// analysis of unions. If "A" is also a bitcast, wait for A/X to be merged. 1965 if (BitCastInst *BCI = dyn_cast<BitCastInst>(ASCStrippedPtrOp)) { 1966 Value *Operand = BCI->getOperand(0); 1967 PointerType *OpType = cast<PointerType>(Operand->getType()); 1968 unsigned OffsetBits = DL.getPointerTypeSizeInBits(GEP.getType()); 1969 APInt Offset(OffsetBits, 0); 1970 if (!isa<BitCastInst>(Operand) && 1971 GEP.accumulateConstantOffset(DL, Offset)) { 1972 1973 // If this GEP instruction doesn't move the pointer, just replace the GEP 1974 // with a bitcast of the real input to the dest type. 1975 if (!Offset) { 1976 // If the bitcast is of an allocation, and the allocation will be 1977 // converted to match the type of the cast, don't touch this. 1978 if (isa<AllocaInst>(Operand) || isAllocationFn(Operand, &TLI)) { 1979 // See if the bitcast simplifies, if so, don't nuke this GEP yet. 1980 if (Instruction *I = visitBitCast(*BCI)) { 1981 if (I != BCI) { 1982 I->takeName(BCI); 1983 BCI->getParent()->getInstList().insert(BCI->getIterator(), I); 1984 replaceInstUsesWith(*BCI, I); 1985 } 1986 return &GEP; 1987 } 1988 } 1989 1990 if (Operand->getType()->getPointerAddressSpace() != GEP.getAddressSpace()) 1991 return new AddrSpaceCastInst(Operand, GEP.getType()); 1992 return new BitCastInst(Operand, GEP.getType()); 1993 } 1994 1995 // Otherwise, if the offset is non-zero, we need to find out if there is a 1996 // field at Offset in 'A's type. If so, we can pull the cast through the 1997 // GEP. 1998 SmallVector<Value*, 8> NewIndices; 1999 if (FindElementAtOffset(OpType, Offset.getSExtValue(), NewIndices)) { 2000 Value *NGEP = 2001 GEP.isInBounds() 2002 ? Builder.CreateInBoundsGEP(nullptr, Operand, NewIndices) 2003 : Builder.CreateGEP(nullptr, Operand, NewIndices); 2004 2005 if (NGEP->getType() == GEP.getType()) 2006 return replaceInstUsesWith(GEP, NGEP); 2007 NGEP->takeName(&GEP); 2008 2009 if (NGEP->getType()->getPointerAddressSpace() != GEP.getAddressSpace()) 2010 return new AddrSpaceCastInst(NGEP, GEP.getType()); 2011 return new BitCastInst(NGEP, GEP.getType()); 2012 } 2013 } 2014 } 2015 2016 if (!GEP.isInBounds()) { 2017 unsigned PtrWidth = 2018 DL.getPointerSizeInBits(PtrOp->getType()->getPointerAddressSpace()); 2019 APInt BasePtrOffset(PtrWidth, 0); 2020 Value *UnderlyingPtrOp = 2021 PtrOp->stripAndAccumulateInBoundsConstantOffsets(DL, 2022 BasePtrOffset); 2023 if (auto *AI = dyn_cast<AllocaInst>(UnderlyingPtrOp)) { 2024 if (GEP.accumulateConstantOffset(DL, BasePtrOffset) && 2025 BasePtrOffset.isNonNegative()) { 2026 APInt AllocSize(PtrWidth, DL.getTypeAllocSize(AI->getAllocatedType())); 2027 if (BasePtrOffset.ule(AllocSize)) { 2028 return GetElementPtrInst::CreateInBounds( 2029 PtrOp, makeArrayRef(Ops).slice(1), GEP.getName()); 2030 } 2031 } 2032 } 2033 } 2034 2035 return nullptr; 2036} 2037 2038static bool isNeverEqualToUnescapedAlloc(Value *V, const TargetLibraryInfo *TLI, 2039 Instruction *AI) { 2040 if (isa<ConstantPointerNull>(V)) 2041 return true; 2042 if (auto *LI = dyn_cast<LoadInst>(V)) 2043 return isa<GlobalVariable>(LI->getPointerOperand()); 2044 // Two distinct allocations will never be equal. 2045 // We rely on LookThroughBitCast in isAllocLikeFn being false, since looking 2046 // through bitcasts of V can cause 2047 // the result statement below to be true, even when AI and V (ex: 2048 // i8* ->i32* ->i8* of AI) are the same allocations. 2049 return isAllocLikeFn(V, TLI) && V != AI; 2050} 2051 2052static bool isAllocSiteRemovable(Instruction *AI, 2053 SmallVectorImpl<WeakTrackingVH> &Users, 2054 const TargetLibraryInfo *TLI) { 2055 SmallVector<Instruction*, 4> Worklist; 2056 Worklist.push_back(AI); 2057 2058 do { 2059 Instruction *PI = Worklist.pop_back_val(); 2060 for (User *U : PI->users()) { 2061 Instruction *I = cast<Instruction>(U); 2062 switch (I->getOpcode()) { 2063 default: 2064 // Give up the moment we see something we can't handle. 2065 return false; 2066 2067 case Instruction::AddrSpaceCast: 2068 case Instruction::BitCast: 2069 case Instruction::GetElementPtr: 2070 Users.emplace_back(I); 2071 Worklist.push_back(I); 2072 continue; 2073 2074 case Instruction::ICmp: { 2075 ICmpInst *ICI = cast<ICmpInst>(I); 2076 // We can fold eq/ne comparisons with null to false/true, respectively. 2077 // We also fold comparisons in some conditions provided the alloc has 2078 // not escaped (see isNeverEqualToUnescapedAlloc). 2079 if (!ICI->isEquality()) 2080 return false; 2081 unsigned OtherIndex = (ICI->getOperand(0) == PI) ? 1 : 0; 2082 if (!isNeverEqualToUnescapedAlloc(ICI->getOperand(OtherIndex), TLI, AI)) 2083 return false; 2084 Users.emplace_back(I); 2085 continue; 2086 } 2087 2088 case Instruction::Call: 2089 // Ignore no-op and store intrinsics. 2090 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 2091 switch (II->getIntrinsicID()) { 2092 default: 2093 return false; 2094 2095 case Intrinsic::memmove: 2096 case Intrinsic::memcpy: 2097 case Intrinsic::memset: { 2098 MemIntrinsic *MI = cast<MemIntrinsic>(II); 2099 if (MI->isVolatile() || MI->getRawDest() != PI) 2100 return false; 2101 LLVM_FALLTHROUGH; 2102 } 2103 case Intrinsic::invariant_start: 2104 case Intrinsic::invariant_end: 2105 case Intrinsic::lifetime_start: 2106 case Intrinsic::lifetime_end: 2107 case Intrinsic::objectsize: 2108 Users.emplace_back(I); 2109 continue; 2110 } 2111 } 2112 2113 if (isFreeCall(I, TLI)) { 2114 Users.emplace_back(I); 2115 continue; 2116 } 2117 return false; 2118 2119 case Instruction::Store: { 2120 StoreInst *SI = cast<StoreInst>(I); 2121 if (SI->isVolatile() || SI->getPointerOperand() != PI) 2122 return false; 2123 Users.emplace_back(I); 2124 continue; 2125 } 2126 } 2127 llvm_unreachable("missing a return?"); 2128 } 2129 } while (!Worklist.empty()); 2130 return true; 2131} 2132 2133Instruction *InstCombiner::visitAllocSite(Instruction &MI) { 2134 // If we have a malloc call which is only used in any amount of comparisons 2135 // to null and free calls, delete the calls and replace the comparisons with 2136 // true or false as appropriate. 2137 SmallVector<WeakTrackingVH, 64> Users; 2138 2139 // If we are removing an alloca with a dbg.declare, insert dbg.value calls 2140 // before each store. 2141 TinyPtrVector<DbgInfoIntrinsic *> DIIs; 2142 std::unique_ptr<DIBuilder> DIB; 2143 if (isa<AllocaInst>(MI)) { 2144 DIIs = FindDbgAddrUses(&MI); 2145 DIB.reset(new DIBuilder(*MI.getModule(), /*AllowUnresolved=*/false)); 2146 } 2147 2148 if (isAllocSiteRemovable(&MI, Users, &TLI)) { 2149 for (unsigned i = 0, e = Users.size(); i != e; ++i) { 2150 // Lowering all @llvm.objectsize calls first because they may 2151 // use a bitcast/GEP of the alloca we are removing. 2152 if (!Users[i]) 2153 continue; 2154 2155 Instruction *I = cast<Instruction>(&*Users[i]); 2156 2157 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 2158 if (II->getIntrinsicID() == Intrinsic::objectsize) { 2159 ConstantInt *Result = lowerObjectSizeCall(II, DL, &TLI, 2160 /*MustSucceed=*/true); 2161 replaceInstUsesWith(*I, Result); 2162 eraseInstFromFunction(*I); 2163 Users[i] = nullptr; // Skip examining in the next loop. 2164 } 2165 } 2166 } 2167 for (unsigned i = 0, e = Users.size(); i != e; ++i) { 2168 if (!Users[i]) 2169 continue; 2170 2171 Instruction *I = cast<Instruction>(&*Users[i]); 2172 2173 if (ICmpInst *C = dyn_cast<ICmpInst>(I)) { 2174 replaceInstUsesWith(*C, 2175 ConstantInt::get(Type::getInt1Ty(C->getContext()), 2176 C->isFalseWhenEqual())); 2177 } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I) || 2178 isa<AddrSpaceCastInst>(I)) { 2179 replaceInstUsesWith(*I, UndefValue::get(I->getType())); 2180 } else if (auto *SI = dyn_cast<StoreInst>(I)) { 2181 for (auto *DII : DIIs) 2182 ConvertDebugDeclareToDebugValue(DII, SI, *DIB); 2183 } 2184 eraseInstFromFunction(*I); 2185 } 2186 2187 if (InvokeInst *II = dyn_cast<InvokeInst>(&MI)) { 2188 // Replace invoke with a NOP intrinsic to maintain the original CFG 2189 Module *M = II->getModule(); 2190 Function *F = Intrinsic::getDeclaration(M, Intrinsic::donothing); 2191 InvokeInst::Create(F, II->getNormalDest(), II->getUnwindDest(), 2192 None, "", II->getParent()); 2193 } 2194 2195 for (auto *DII : DIIs) 2196 eraseInstFromFunction(*DII); 2197 2198 return eraseInstFromFunction(MI); 2199 } 2200 return nullptr; 2201} 2202 2203/// \brief Move the call to free before a NULL test. 2204/// 2205/// Check if this free is accessed after its argument has been test 2206/// against NULL (property 0). 2207/// If yes, it is legal to move this call in its predecessor block. 2208/// 2209/// The move is performed only if the block containing the call to free 2210/// will be removed, i.e.: 2211/// 1. it has only one predecessor P, and P has two successors 2212/// 2. it contains the call and an unconditional branch 2213/// 3. its successor is the same as its predecessor's successor 2214/// 2215/// The profitability is out-of concern here and this function should 2216/// be called only if the caller knows this transformation would be 2217/// profitable (e.g., for code size). 2218static Instruction * 2219tryToMoveFreeBeforeNullTest(CallInst &FI) { 2220 Value *Op = FI.getArgOperand(0); 2221 BasicBlock *FreeInstrBB = FI.getParent(); 2222 BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor(); 2223 2224 // Validate part of constraint #1: Only one predecessor 2225 // FIXME: We can extend the number of predecessor, but in that case, we 2226 // would duplicate the call to free in each predecessor and it may 2227 // not be profitable even for code size. 2228 if (!PredBB) 2229 return nullptr; 2230 2231 // Validate constraint #2: Does this block contains only the call to 2232 // free and an unconditional branch? 2233 // FIXME: We could check if we can speculate everything in the 2234 // predecessor block 2235 if (FreeInstrBB->size() != 2) 2236 return nullptr; 2237 BasicBlock *SuccBB; 2238 if (!match(FreeInstrBB->getTerminator(), m_UnconditionalBr(SuccBB))) 2239 return nullptr; 2240 2241 // Validate the rest of constraint #1 by matching on the pred branch. 2242 TerminatorInst *TI = PredBB->getTerminator(); 2243 BasicBlock *TrueBB, *FalseBB; 2244 ICmpInst::Predicate Pred; 2245 if (!match(TI, m_Br(m_ICmp(Pred, m_Specific(Op), m_Zero()), TrueBB, FalseBB))) 2246 return nullptr; 2247 if (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE) 2248 return nullptr; 2249 2250 // Validate constraint #3: Ensure the null case just falls through. 2251 if (SuccBB != (Pred == ICmpInst::ICMP_EQ ? TrueBB : FalseBB)) 2252 return nullptr; 2253 assert(FreeInstrBB == (Pred == ICmpInst::ICMP_EQ ? FalseBB : TrueBB) && 2254 "Broken CFG: missing edge from predecessor to successor"); 2255 2256 FI.moveBefore(TI); 2257 return &FI; 2258} 2259 2260Instruction *InstCombiner::visitFree(CallInst &FI) { 2261 Value *Op = FI.getArgOperand(0); 2262 2263 // free undef -> unreachable. 2264 if (isa<UndefValue>(Op)) { 2265 // Insert a new store to null because we cannot modify the CFG here. 2266 Builder.CreateStore(ConstantInt::getTrue(FI.getContext()), 2267 UndefValue::get(Type::getInt1PtrTy(FI.getContext()))); 2268 return eraseInstFromFunction(FI); 2269 } 2270 2271 // If we have 'free null' delete the instruction. This can happen in stl code 2272 // when lots of inlining happens. 2273 if (isa<ConstantPointerNull>(Op)) 2274 return eraseInstFromFunction(FI); 2275 2276 // If we optimize for code size, try to move the call to free before the null 2277 // test so that simplify cfg can remove the empty block and dead code 2278 // elimination the branch. I.e., helps to turn something like: 2279 // if (foo) free(foo); 2280 // into 2281 // free(foo); 2282 if (MinimizeSize) 2283 if (Instruction *I = tryToMoveFreeBeforeNullTest(FI)) 2284 return I; 2285 2286 return nullptr; 2287} 2288 2289Instruction *InstCombiner::visitReturnInst(ReturnInst &RI) { 2290 if (RI.getNumOperands() == 0) // ret void 2291 return nullptr; 2292 2293 Value *ResultOp = RI.getOperand(0); 2294 Type *VTy = ResultOp->getType(); 2295 if (!VTy->isIntegerTy()) 2296 return nullptr; 2297 2298 // There might be assume intrinsics dominating this return that completely 2299 // determine the value. If so, constant fold it. 2300 KnownBits Known = computeKnownBits(ResultOp, 0, &RI); 2301 if (Known.isConstant()) 2302 RI.setOperand(0, Constant::getIntegerValue(VTy, Known.getConstant())); 2303 2304 return nullptr; 2305} 2306 2307Instruction *InstCombiner::visitBranchInst(BranchInst &BI) { 2308 // Change br (not X), label True, label False to: br X, label False, True 2309 Value *X = nullptr; 2310 BasicBlock *TrueDest; 2311 BasicBlock *FalseDest; 2312 if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) && 2313 !isa<Constant>(X)) { 2314 // Swap Destinations and condition... 2315 BI.setCondition(X); 2316 BI.swapSuccessors(); 2317 return &BI; 2318 } 2319 2320 // If the condition is irrelevant, remove the use so that other 2321 // transforms on the condition become more effective. 2322 if (BI.isConditional() && !isa<ConstantInt>(BI.getCondition()) && 2323 BI.getSuccessor(0) == BI.getSuccessor(1)) { 2324 BI.setCondition(ConstantInt::getFalse(BI.getCondition()->getType())); 2325 return &BI; 2326 } 2327 2328 // Canonicalize, for example, icmp_ne -> icmp_eq or fcmp_one -> fcmp_oeq. 2329 CmpInst::Predicate Pred; 2330 if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), TrueDest, 2331 FalseDest)) && 2332 !isCanonicalPredicate(Pred)) { 2333 // Swap destinations and condition. 2334 CmpInst *Cond = cast<CmpInst>(BI.getCondition()); 2335 Cond->setPredicate(CmpInst::getInversePredicate(Pred)); 2336 BI.swapSuccessors(); 2337 Worklist.Add(Cond); 2338 return &BI; 2339 } 2340 2341 return nullptr; 2342} 2343 2344Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) { 2345 Value *Cond = SI.getCondition(); 2346 Value *Op0; 2347 ConstantInt *AddRHS; 2348 if (match(Cond, m_Add(m_Value(Op0), m_ConstantInt(AddRHS)))) { 2349 // Change 'switch (X+4) case 1:' into 'switch (X) case -3'. 2350 for (auto Case : SI.cases()) { 2351 Constant *NewCase = ConstantExpr::getSub(Case.getCaseValue(), AddRHS); 2352 assert(isa<ConstantInt>(NewCase) && 2353 "Result of expression should be constant"); 2354 Case.setValue(cast<ConstantInt>(NewCase)); 2355 } 2356 SI.setCondition(Op0); 2357 return &SI; 2358 } 2359 2360 KnownBits Known = computeKnownBits(Cond, 0, &SI); 2361 unsigned LeadingKnownZeros = Known.countMinLeadingZeros(); 2362 unsigned LeadingKnownOnes = Known.countMinLeadingOnes(); 2363 2364 // Compute the number of leading bits we can ignore. 2365 // TODO: A better way to determine this would use ComputeNumSignBits(). 2366 for (auto &C : SI.cases()) { 2367 LeadingKnownZeros = std::min( 2368 LeadingKnownZeros, C.getCaseValue()->getValue().countLeadingZeros()); 2369 LeadingKnownOnes = std::min( 2370 LeadingKnownOnes, C.getCaseValue()->getValue().countLeadingOnes()); 2371 } 2372 2373 unsigned NewWidth = Known.getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes); 2374 2375 // Shrink the condition operand if the new type is smaller than the old type. 2376 // This may produce a non-standard type for the switch, but that's ok because 2377 // the backend should extend back to a legal type for the target. 2378 if (NewWidth > 0 && NewWidth < Known.getBitWidth()) { 2379 IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth); 2380 Builder.SetInsertPoint(&SI); 2381 Value *NewCond = Builder.CreateTrunc(Cond, Ty, "trunc"); 2382 SI.setCondition(NewCond); 2383 2384 for (auto Case : SI.cases()) { 2385 APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth); 2386 Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase)); 2387 } 2388 return &SI; 2389 } 2390 2391 return nullptr; 2392} 2393 2394Instruction *InstCombiner::visitExtractValueInst(ExtractValueInst &EV) { 2395 Value *Agg = EV.getAggregateOperand(); 2396 2397 if (!EV.hasIndices()) 2398 return replaceInstUsesWith(EV, Agg); 2399 2400 if (Value *V = SimplifyExtractValueInst(Agg, EV.getIndices(), 2401 SQ.getWithInstruction(&EV))) 2402 return replaceInstUsesWith(EV, V); 2403 2404 if (InsertValueInst *IV = dyn_cast<InsertValueInst>(Agg)) { 2405 // We're extracting from an insertvalue instruction, compare the indices 2406 const unsigned *exti, *exte, *insi, *inse; 2407 for (exti = EV.idx_begin(), insi = IV->idx_begin(), 2408 exte = EV.idx_end(), inse = IV->idx_end(); 2409 exti != exte && insi != inse; 2410 ++exti, ++insi) { 2411 if (*insi != *exti) 2412 // The insert and extract both reference distinctly different elements. 2413 // This means the extract is not influenced by the insert, and we can 2414 // replace the aggregate operand of the extract with the aggregate 2415 // operand of the insert. i.e., replace 2416 // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1 2417 // %E = extractvalue { i32, { i32 } } %I, 0 2418 // with 2419 // %E = extractvalue { i32, { i32 } } %A, 0 2420 return ExtractValueInst::Create(IV->getAggregateOperand(), 2421 EV.getIndices()); 2422 } 2423 if (exti == exte && insi == inse) 2424 // Both iterators are at the end: Index lists are identical. Replace 2425 // %B = insertvalue { i32, { i32 } } %A, i32 42, 1, 0 2426 // %C = extractvalue { i32, { i32 } } %B, 1, 0 2427 // with "i32 42" 2428 return replaceInstUsesWith(EV, IV->getInsertedValueOperand()); 2429 if (exti == exte) { 2430 // The extract list is a prefix of the insert list. i.e. replace 2431 // %I = insertvalue { i32, { i32 } } %A, i32 42, 1, 0 2432 // %E = extractvalue { i32, { i32 } } %I, 1 2433 // with 2434 // %X = extractvalue { i32, { i32 } } %A, 1 2435 // %E = insertvalue { i32 } %X, i32 42, 0 2436 // by switching the order of the insert and extract (though the 2437 // insertvalue should be left in, since it may have other uses). 2438 Value *NewEV = Builder.CreateExtractValue(IV->getAggregateOperand(), 2439 EV.getIndices()); 2440 return InsertValueInst::Create(NewEV, IV->getInsertedValueOperand(), 2441 makeArrayRef(insi, inse)); 2442 } 2443 if (insi == inse) 2444 // The insert list is a prefix of the extract list 2445 // We can simply remove the common indices from the extract and make it 2446 // operate on the inserted value instead of the insertvalue result. 2447 // i.e., replace 2448 // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1 2449 // %E = extractvalue { i32, { i32 } } %I, 1, 0 2450 // with 2451 // %E extractvalue { i32 } { i32 42 }, 0 2452 return ExtractValueInst::Create(IV->getInsertedValueOperand(), 2453 makeArrayRef(exti, exte)); 2454 } 2455 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Agg)) { 2456 // We're extracting from an intrinsic, see if we're the only user, which 2457 // allows us to simplify multiple result intrinsics to simpler things that 2458 // just get one value. 2459 if (II->hasOneUse()) { 2460 // Check if we're grabbing the overflow bit or the result of a 'with 2461 // overflow' intrinsic. If it's the latter we can remove the intrinsic 2462 // and replace it with a traditional binary instruction. 2463 switch (II->getIntrinsicID()) { 2464 case Intrinsic::uadd_with_overflow: 2465 case Intrinsic::sadd_with_overflow: 2466 if (*EV.idx_begin() == 0) { // Normal result. 2467 Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); 2468 replaceInstUsesWith(*II, UndefValue::get(II->getType())); 2469 eraseInstFromFunction(*II); 2470 return BinaryOperator::CreateAdd(LHS, RHS); 2471 } 2472 2473 // If the normal result of the add is dead, and the RHS is a constant, 2474 // we can transform this into a range comparison. 2475 // overflow = uadd a, -4 --> overflow = icmp ugt a, 3 2476 if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow) 2477 if (ConstantInt *CI = dyn_cast<ConstantInt>(II->getArgOperand(1))) 2478 return new ICmpInst(ICmpInst::ICMP_UGT, II->getArgOperand(0), 2479 ConstantExpr::getNot(CI)); 2480 break; 2481 case Intrinsic::usub_with_overflow: 2482 case Intrinsic::ssub_with_overflow: 2483 if (*EV.idx_begin() == 0) { // Normal result. 2484 Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); 2485 replaceInstUsesWith(*II, UndefValue::get(II->getType())); 2486 eraseInstFromFunction(*II); 2487 return BinaryOperator::CreateSub(LHS, RHS); 2488 } 2489 break; 2490 case Intrinsic::umul_with_overflow: 2491 case Intrinsic::smul_with_overflow: 2492 if (*EV.idx_begin() == 0) { // Normal result. 2493 Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); 2494 replaceInstUsesWith(*II, UndefValue::get(II->getType())); 2495 eraseInstFromFunction(*II); 2496 return BinaryOperator::CreateMul(LHS, RHS); 2497 } 2498 break; 2499 default: 2500 break; 2501 } 2502 } 2503 } 2504 if (LoadInst *L = dyn_cast<LoadInst>(Agg)) 2505 // If the (non-volatile) load only has one use, we can rewrite this to a 2506 // load from a GEP. This reduces the size of the load. If a load is used 2507 // only by extractvalue instructions then this either must have been 2508 // optimized before, or it is a struct with padding, in which case we 2509 // don't want to do the transformation as it loses padding knowledge. 2510 if (L->isSimple() && L->hasOneUse()) { 2511 // extractvalue has integer indices, getelementptr has Value*s. Convert. 2512 SmallVector<Value*, 4> Indices; 2513 // Prefix an i32 0 since we need the first element. 2514 Indices.push_back(Builder.getInt32(0)); 2515 for (ExtractValueInst::idx_iterator I = EV.idx_begin(), E = EV.idx_end(); 2516 I != E; ++I) 2517 Indices.push_back(Builder.getInt32(*I)); 2518 2519 // We need to insert these at the location of the old load, not at that of 2520 // the extractvalue. 2521 Builder.SetInsertPoint(L); 2522 Value *GEP = Builder.CreateInBoundsGEP(L->getType(), 2523 L->getPointerOperand(), Indices); 2524 Instruction *NL = Builder.CreateLoad(GEP); 2525 // Whatever aliasing information we had for the orignal load must also 2526 // hold for the smaller load, so propagate the annotations. 2527 AAMDNodes Nodes; 2528 L->getAAMetadata(Nodes); 2529 NL->setAAMetadata(Nodes); 2530 // Returning the load directly will cause the main loop to insert it in 2531 // the wrong spot, so use replaceInstUsesWith(). 2532 return replaceInstUsesWith(EV, NL); 2533 } 2534 // We could simplify extracts from other values. Note that nested extracts may 2535 // already be simplified implicitly by the above: extract (extract (insert) ) 2536 // will be translated into extract ( insert ( extract ) ) first and then just 2537 // the value inserted, if appropriate. Similarly for extracts from single-use 2538 // loads: extract (extract (load)) will be translated to extract (load (gep)) 2539 // and if again single-use then via load (gep (gep)) to load (gep). 2540 // However, double extracts from e.g. function arguments or return values 2541 // aren't handled yet. 2542 return nullptr; 2543} 2544 2545/// Return 'true' if the given typeinfo will match anything. 2546static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo) { 2547 switch (Personality) { 2548 case EHPersonality::GNU_C: 2549 case EHPersonality::GNU_C_SjLj: 2550 case EHPersonality::Rust: 2551 // The GCC C EH and Rust personality only exists to support cleanups, so 2552 // it's not clear what the semantics of catch clauses are. 2553 return false; 2554 case EHPersonality::Unknown: 2555 return false; 2556 case EHPersonality::GNU_Ada: 2557 // While __gnat_all_others_value will match any Ada exception, it doesn't 2558 // match foreign exceptions (or didn't, before gcc-4.7). 2559 return false; 2560 case EHPersonality::GNU_CXX: 2561 case EHPersonality::GNU_CXX_SjLj: 2562 case EHPersonality::GNU_ObjC: 2563 case EHPersonality::MSVC_X86SEH: 2564 case EHPersonality::MSVC_Win64SEH: 2565 case EHPersonality::MSVC_CXX: 2566 case EHPersonality::CoreCLR: 2567 return TypeInfo->isNullValue(); 2568 } 2569 llvm_unreachable("invalid enum"); 2570} 2571 2572static bool shorter_filter(const Value *LHS, const Value *RHS) { 2573 return 2574 cast<ArrayType>(LHS->getType())->getNumElements() 2575 < 2576 cast<ArrayType>(RHS->getType())->getNumElements(); 2577} 2578 2579Instruction *InstCombiner::visitLandingPadInst(LandingPadInst &LI) { 2580 // The logic here should be correct for any real-world personality function. 2581 // However if that turns out not to be true, the offending logic can always 2582 // be conditioned on the personality function, like the catch-all logic is. 2583 EHPersonality Personality = 2584 classifyEHPersonality(LI.getParent()->getParent()->getPersonalityFn()); 2585 2586 // Simplify the list of clauses, eg by removing repeated catch clauses 2587 // (these are often created by inlining). 2588 bool MakeNewInstruction = false; // If true, recreate using the following: 2589 SmallVector<Constant *, 16> NewClauses; // - Clauses for the new instruction; 2590 bool CleanupFlag = LI.isCleanup(); // - The new instruction is a cleanup. 2591 2592 SmallPtrSet<Value *, 16> AlreadyCaught; // Typeinfos known caught already. 2593 for (unsigned i = 0, e = LI.getNumClauses(); i != e; ++i) { 2594 bool isLastClause = i + 1 == e; 2595 if (LI.isCatch(i)) { 2596 // A catch clause. 2597 Constant *CatchClause = LI.getClause(i); 2598 Constant *TypeInfo = CatchClause->stripPointerCasts(); 2599 2600 // If we already saw this clause, there is no point in having a second 2601 // copy of it. 2602 if (AlreadyCaught.insert(TypeInfo).second) { 2603 // This catch clause was not already seen. 2604 NewClauses.push_back(CatchClause); 2605 } else { 2606 // Repeated catch clause - drop the redundant copy. 2607 MakeNewInstruction = true; 2608 } 2609 2610 // If this is a catch-all then there is no point in keeping any following 2611 // clauses or marking the landingpad as having a cleanup. 2612 if (isCatchAll(Personality, TypeInfo)) { 2613 if (!isLastClause) 2614 MakeNewInstruction = true; 2615 CleanupFlag = false; 2616 break; 2617 } 2618 } else { 2619 // A filter clause. If any of the filter elements were already caught 2620 // then they can be dropped from the filter. It is tempting to try to 2621 // exploit the filter further by saying that any typeinfo that does not 2622 // occur in the filter can't be caught later (and thus can be dropped). 2623 // However this would be wrong, since typeinfos can match without being 2624 // equal (for example if one represents a C++ class, and the other some 2625 // class derived from it). 2626 assert(LI.isFilter(i) && "Unsupported landingpad clause!"); 2627 Constant *FilterClause = LI.getClause(i); 2628 ArrayType *FilterType = cast<ArrayType>(FilterClause->getType()); 2629 unsigned NumTypeInfos = FilterType->getNumElements(); 2630 2631 // An empty filter catches everything, so there is no point in keeping any 2632 // following clauses or marking the landingpad as having a cleanup. By 2633 // dealing with this case here the following code is made a bit simpler. 2634 if (!NumTypeInfos) { 2635 NewClauses.push_back(FilterClause); 2636 if (!isLastClause) 2637 MakeNewInstruction = true; 2638 CleanupFlag = false; 2639 break; 2640 } 2641 2642 bool MakeNewFilter = false; // If true, make a new filter. 2643 SmallVector<Constant *, 16> NewFilterElts; // New elements. 2644 if (isa<ConstantAggregateZero>(FilterClause)) { 2645 // Not an empty filter - it contains at least one null typeinfo. 2646 assert(NumTypeInfos > 0 && "Should have handled empty filter already!"); 2647 Constant *TypeInfo = 2648 Constant::getNullValue(FilterType->getElementType()); 2649 // If this typeinfo is a catch-all then the filter can never match. 2650 if (isCatchAll(Personality, TypeInfo)) { 2651 // Throw the filter away. 2652 MakeNewInstruction = true; 2653 continue; 2654 } 2655 2656 // There is no point in having multiple copies of this typeinfo, so 2657 // discard all but the first copy if there is more than one. 2658 NewFilterElts.push_back(TypeInfo); 2659 if (NumTypeInfos > 1) 2660 MakeNewFilter = true; 2661 } else { 2662 ConstantArray *Filter = cast<ConstantArray>(FilterClause); 2663 SmallPtrSet<Value *, 16> SeenInFilter; // For uniquing the elements. 2664 NewFilterElts.reserve(NumTypeInfos); 2665 2666 // Remove any filter elements that were already caught or that already 2667 // occurred in the filter. While there, see if any of the elements are 2668 // catch-alls. If so, the filter can be discarded. 2669 bool SawCatchAll = false; 2670 for (unsigned j = 0; j != NumTypeInfos; ++j) { 2671 Constant *Elt = Filter->getOperand(j); 2672 Constant *TypeInfo = Elt->stripPointerCasts(); 2673 if (isCatchAll(Personality, TypeInfo)) { 2674 // This element is a catch-all. Bail out, noting this fact. 2675 SawCatchAll = true; 2676 break; 2677 } 2678 2679 // Even if we've seen a type in a catch clause, we don't want to 2680 // remove it from the filter. An unexpected type handler may be 2681 // set up for a call site which throws an exception of the same 2682 // type caught. In order for the exception thrown by the unexpected 2683 // handler to propagate correctly, the filter must be correctly 2684 // described for the call site. 2685 // 2686 // Example: 2687 // 2688 // void unexpected() { throw 1;} 2689 // void foo() throw (int) { 2690 // std::set_unexpected(unexpected); 2691 // try { 2692 // throw 2.0; 2693 // } catch (int i) {} 2694 // } 2695 2696 // There is no point in having multiple copies of the same typeinfo in 2697 // a filter, so only add it if we didn't already. 2698 if (SeenInFilter.insert(TypeInfo).second) 2699 NewFilterElts.push_back(cast<Constant>(Elt)); 2700 } 2701 // A filter containing a catch-all cannot match anything by definition. 2702 if (SawCatchAll) { 2703 // Throw the filter away. 2704 MakeNewInstruction = true; 2705 continue; 2706 } 2707 2708 // If we dropped something from the filter, make a new one. 2709 if (NewFilterElts.size() < NumTypeInfos) 2710 MakeNewFilter = true; 2711 } 2712 if (MakeNewFilter) { 2713 FilterType = ArrayType::get(FilterType->getElementType(), 2714 NewFilterElts.size()); 2715 FilterClause = ConstantArray::get(FilterType, NewFilterElts); 2716 MakeNewInstruction = true; 2717 } 2718 2719 NewClauses.push_back(FilterClause); 2720 2721 // If the new filter is empty then it will catch everything so there is 2722 // no point in keeping any following clauses or marking the landingpad 2723 // as having a cleanup. The case of the original filter being empty was 2724 // already handled above. 2725 if (MakeNewFilter && !NewFilterElts.size()) { 2726 assert(MakeNewInstruction && "New filter but not a new instruction!"); 2727 CleanupFlag = false; 2728 break; 2729 } 2730 } 2731 } 2732 2733 // If several filters occur in a row then reorder them so that the shortest 2734 // filters come first (those with the smallest number of elements). This is 2735 // advantageous because shorter filters are more likely to match, speeding up 2736 // unwinding, but mostly because it increases the effectiveness of the other 2737 // filter optimizations below. 2738 for (unsigned i = 0, e = NewClauses.size(); i + 1 < e; ) { 2739 unsigned j; 2740 // Find the maximal 'j' s.t. the range [i, j) consists entirely of filters. 2741 for (j = i; j != e; ++j) 2742 if (!isa<ArrayType>(NewClauses[j]->getType())) 2743 break; 2744 2745 // Check whether the filters are already sorted by length. We need to know 2746 // if sorting them is actually going to do anything so that we only make a 2747 // new landingpad instruction if it does. 2748 for (unsigned k = i; k + 1 < j; ++k) 2749 if (shorter_filter(NewClauses[k+1], NewClauses[k])) { 2750 // Not sorted, so sort the filters now. Doing an unstable sort would be 2751 // correct too but reordering filters pointlessly might confuse users. 2752 std::stable_sort(NewClauses.begin() + i, NewClauses.begin() + j, 2753 shorter_filter); 2754 MakeNewInstruction = true; 2755 break; 2756 } 2757 2758 // Look for the next batch of filters. 2759 i = j + 1; 2760 } 2761 2762 // If typeinfos matched if and only if equal, then the elements of a filter L 2763 // that occurs later than a filter F could be replaced by the intersection of 2764 // the elements of F and L. In reality two typeinfos can match without being 2765 // equal (for example if one represents a C++ class, and the other some class 2766 // derived from it) so it would be wrong to perform this transform in general. 2767 // However the transform is correct and useful if F is a subset of L. In that 2768 // case L can be replaced by F, and thus removed altogether since repeating a 2769 // filter is pointless. So here we look at all pairs of filters F and L where 2770 // L follows F in the list of clauses, and remove L if every element of F is 2771 // an element of L. This can occur when inlining C++ functions with exception 2772 // specifications. 2773 for (unsigned i = 0; i + 1 < NewClauses.size(); ++i) { 2774 // Examine each filter in turn. 2775 Value *Filter = NewClauses[i]; 2776 ArrayType *FTy = dyn_cast<ArrayType>(Filter->getType()); 2777 if (!FTy) 2778 // Not a filter - skip it. 2779 continue; 2780 unsigned FElts = FTy->getNumElements(); 2781 // Examine each filter following this one. Doing this backwards means that 2782 // we don't have to worry about filters disappearing under us when removed. 2783 for (unsigned j = NewClauses.size() - 1; j != i; --j) { 2784 Value *LFilter = NewClauses[j]; 2785 ArrayType *LTy = dyn_cast<ArrayType>(LFilter->getType()); 2786 if (!LTy) 2787 // Not a filter - skip it. 2788 continue; 2789 // If Filter is a subset of LFilter, i.e. every element of Filter is also 2790 // an element of LFilter, then discard LFilter. 2791 SmallVectorImpl<Constant *>::iterator J = NewClauses.begin() + j; 2792 // If Filter is empty then it is a subset of LFilter. 2793 if (!FElts) { 2794 // Discard LFilter. 2795 NewClauses.erase(J); 2796 MakeNewInstruction = true; 2797 // Move on to the next filter. 2798 continue; 2799 } 2800 unsigned LElts = LTy->getNumElements(); 2801 // If Filter is longer than LFilter then it cannot be a subset of it. 2802 if (FElts > LElts) 2803 // Move on to the next filter. 2804 continue; 2805 // At this point we know that LFilter has at least one element. 2806 if (isa<ConstantAggregateZero>(LFilter)) { // LFilter only contains zeros. 2807 // Filter is a subset of LFilter iff Filter contains only zeros (as we 2808 // already know that Filter is not longer than LFilter). 2809 if (isa<ConstantAggregateZero>(Filter)) { 2810 assert(FElts <= LElts && "Should have handled this case earlier!"); 2811 // Discard LFilter. 2812 NewClauses.erase(J); 2813 MakeNewInstruction = true; 2814 } 2815 // Move on to the next filter. 2816 continue; 2817 } 2818 ConstantArray *LArray = cast<ConstantArray>(LFilter); 2819 if (isa<ConstantAggregateZero>(Filter)) { // Filter only contains zeros. 2820 // Since Filter is non-empty and contains only zeros, it is a subset of 2821 // LFilter iff LFilter contains a zero. 2822 assert(FElts > 0 && "Should have eliminated the empty filter earlier!"); 2823 for (unsigned l = 0; l != LElts; ++l) 2824 if (LArray->getOperand(l)->isNullValue()) { 2825 // LFilter contains a zero - discard it. 2826 NewClauses.erase(J); 2827 MakeNewInstruction = true; 2828 break; 2829 } 2830 // Move on to the next filter. 2831 continue; 2832 } 2833 // At this point we know that both filters are ConstantArrays. Loop over 2834 // operands to see whether every element of Filter is also an element of 2835 // LFilter. Since filters tend to be short this is probably faster than 2836 // using a method that scales nicely. 2837 ConstantArray *FArray = cast<ConstantArray>(Filter); 2838 bool AllFound = true; 2839 for (unsigned f = 0; f != FElts; ++f) { 2840 Value *FTypeInfo = FArray->getOperand(f)->stripPointerCasts(); 2841 AllFound = false; 2842 for (unsigned l = 0; l != LElts; ++l) { 2843 Value *LTypeInfo = LArray->getOperand(l)->stripPointerCasts(); 2844 if (LTypeInfo == FTypeInfo) { 2845 AllFound = true; 2846 break; 2847 } 2848 } 2849 if (!AllFound) 2850 break; 2851 } 2852 if (AllFound) { 2853 // Discard LFilter. 2854 NewClauses.erase(J); 2855 MakeNewInstruction = true; 2856 } 2857 // Move on to the next filter. 2858 } 2859 } 2860 2861 // If we changed any of the clauses, replace the old landingpad instruction 2862 // with a new one. 2863 if (MakeNewInstruction) { 2864 LandingPadInst *NLI = LandingPadInst::Create(LI.getType(), 2865 NewClauses.size()); 2866 for (unsigned i = 0, e = NewClauses.size(); i != e; ++i) 2867 NLI->addClause(NewClauses[i]); 2868 // A landing pad with no clauses must have the cleanup flag set. It is 2869 // theoretically possible, though highly unlikely, that we eliminated all 2870 // clauses. If so, force the cleanup flag to true. 2871 if (NewClauses.empty()) 2872 CleanupFlag = true; 2873 NLI->setCleanup(CleanupFlag); 2874 return NLI; 2875 } 2876 2877 // Even if none of the clauses changed, we may nonetheless have understood 2878 // that the cleanup flag is pointless. Clear it if so. 2879 if (LI.isCleanup() != CleanupFlag) { 2880 assert(!CleanupFlag && "Adding a cleanup, not removing one?!"); 2881 LI.setCleanup(CleanupFlag); 2882 return &LI; 2883 } 2884 2885 return nullptr; 2886} 2887 2888/// Try to move the specified instruction from its current block into the 2889/// beginning of DestBlock, which can only happen if it's safe to move the 2890/// instruction past all of the instructions between it and the end of its 2891/// block. 2892static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { 2893 assert(I->hasOneUse() && "Invariants didn't hold!"); 2894 2895 // Cannot move control-flow-involving, volatile loads, vaarg, etc. 2896 if (isa<PHINode>(I) || I->isEHPad() || I->mayHaveSideEffects() || 2897 isa<TerminatorInst>(I)) 2898 return false; 2899 2900 // Do not sink alloca instructions out of the entry block. 2901 if (isa<AllocaInst>(I) && I->getParent() == 2902 &DestBlock->getParent()->getEntryBlock()) 2903 return false; 2904 2905 // Do not sink into catchswitch blocks. 2906 if (isa<CatchSwitchInst>(DestBlock->getTerminator())) 2907 return false; 2908 2909 // Do not sink convergent call instructions. 2910 if (auto *CI = dyn_cast<CallInst>(I)) { 2911 if (CI->isConvergent()) 2912 return false; 2913 } 2914 // We can only sink load instructions if there is nothing between the load and 2915 // the end of block that could change the value. 2916 if (I->mayReadFromMemory()) { 2917 for (BasicBlock::iterator Scan = I->getIterator(), 2918 E = I->getParent()->end(); 2919 Scan != E; ++Scan) 2920 if (Scan->mayWriteToMemory()) 2921 return false; 2922 } 2923 2924 BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt(); 2925 I->moveBefore(&*InsertPos); 2926 ++NumSunkInst; 2927 return true; 2928} 2929 2930bool InstCombiner::run() { 2931 while (!Worklist.isEmpty()) { 2932 Instruction *I = Worklist.RemoveOne(); 2933 if (I == nullptr) continue; // skip null values. 2934 2935 // Check to see if we can DCE the instruction. 2936 if (isInstructionTriviallyDead(I, &TLI)) { 2937 DEBUG(dbgs() << "IC: DCE: " << *I << '\n'); 2938 eraseInstFromFunction(*I); 2939 ++NumDeadInst; 2940 MadeIRChange = true; 2941 continue; 2942 } 2943 2944 if (!DebugCounter::shouldExecute(VisitCounter)) 2945 continue; 2946 2947 // Instruction isn't dead, see if we can constant propagate it. 2948 if (!I->use_empty() && 2949 (I->getNumOperands() == 0 || isa<Constant>(I->getOperand(0)))) { 2950 if (Constant *C = ConstantFoldInstruction(I, DL, &TLI)) { 2951 DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I << '\n'); 2952 2953 // Add operands to the worklist. 2954 replaceInstUsesWith(*I, C); 2955 ++NumConstProp; 2956 if (isInstructionTriviallyDead(I, &TLI)) 2957 eraseInstFromFunction(*I); 2958 MadeIRChange = true; 2959 continue; 2960 } 2961 } 2962 2963 // In general, it is possible for computeKnownBits to determine all bits in 2964 // a value even when the operands are not all constants. 2965 Type *Ty = I->getType(); 2966 if (ExpensiveCombines && !I->use_empty() && Ty->isIntOrIntVectorTy()) { 2967 KnownBits Known = computeKnownBits(I, /*Depth*/0, I); 2968 if (Known.isConstant()) { 2969 Constant *C = ConstantInt::get(Ty, Known.getConstant()); 2970 DEBUG(dbgs() << "IC: ConstFold (all bits known) to: " << *C << 2971 " from: " << *I << '\n'); 2972 2973 // Add operands to the worklist. 2974 replaceInstUsesWith(*I, C); 2975 ++NumConstProp; 2976 if (isInstructionTriviallyDead(I, &TLI)) 2977 eraseInstFromFunction(*I); 2978 MadeIRChange = true; 2979 continue; 2980 } 2981 } 2982 2983 // See if we can trivially sink this instruction to a successor basic block. 2984 if (I->hasOneUse()) { 2985 BasicBlock *BB = I->getParent(); 2986 Instruction *UserInst = cast<Instruction>(*I->user_begin()); 2987 BasicBlock *UserParent; 2988 2989 // Get the block the use occurs in. 2990 if (PHINode *PN = dyn_cast<PHINode>(UserInst)) 2991 UserParent = PN->getIncomingBlock(*I->use_begin()); 2992 else 2993 UserParent = UserInst->getParent(); 2994 2995 if (UserParent != BB) { 2996 bool UserIsSuccessor = false; 2997 // See if the user is one of our successors. 2998 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 2999 if (*SI == UserParent) { 3000 UserIsSuccessor = true; 3001 break; 3002 } 3003 3004 // If the user is one of our immediate successors, and if that successor 3005 // only has us as a predecessors (we'd have to split the critical edge 3006 // otherwise), we can keep going. 3007 if (UserIsSuccessor && UserParent->getUniquePredecessor()) { 3008 // Okay, the CFG is simple enough, try to sink this instruction. 3009 if (TryToSinkInstruction(I, UserParent)) { 3010 DEBUG(dbgs() << "IC: Sink: " << *I << '\n'); 3011 MadeIRChange = true; 3012 // We'll add uses of the sunk instruction below, but since sinking 3013 // can expose opportunities for it's *operands* add them to the 3014 // worklist 3015 for (Use &U : I->operands()) 3016 if (Instruction *OpI = dyn_cast<Instruction>(U.get())) 3017 Worklist.Add(OpI); 3018 } 3019 } 3020 } 3021 } 3022 3023 // Now that we have an instruction, try combining it to simplify it. 3024 Builder.SetInsertPoint(I); 3025 Builder.SetCurrentDebugLocation(I->getDebugLoc()); 3026 3027#ifndef NDEBUG 3028 std::string OrigI; 3029#endif 3030 DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str();); 3031 DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n'); 3032 3033 if (Instruction *Result = visit(*I)) { 3034 ++NumCombined; 3035 // Should we replace the old instruction with a new one? 3036 if (Result != I) { 3037 DEBUG(dbgs() << "IC: Old = " << *I << '\n' 3038 << " New = " << *Result << '\n'); 3039 3040 if (I->getDebugLoc()) 3041 Result->setDebugLoc(I->getDebugLoc()); 3042 // Everything uses the new instruction now. 3043 I->replaceAllUsesWith(Result); 3044 3045 // Move the name to the new instruction first. 3046 Result->takeName(I); 3047 3048 // Push the new instruction and any users onto the worklist. 3049 Worklist.AddUsersToWorkList(*Result); 3050 Worklist.Add(Result); 3051 3052 // Insert the new instruction into the basic block... 3053 BasicBlock *InstParent = I->getParent(); 3054 BasicBlock::iterator InsertPos = I->getIterator(); 3055 3056 // If we replace a PHI with something that isn't a PHI, fix up the 3057 // insertion point. 3058 if (!isa<PHINode>(Result) && isa<PHINode>(InsertPos)) 3059 InsertPos = InstParent->getFirstInsertionPt(); 3060 3061 InstParent->getInstList().insert(InsertPos, Result); 3062 3063 eraseInstFromFunction(*I); 3064 } else { 3065 DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n' 3066 << " New = " << *I << '\n'); 3067 3068 // If the instruction was modified, it's possible that it is now dead. 3069 // if so, remove it. 3070 if (isInstructionTriviallyDead(I, &TLI)) { 3071 eraseInstFromFunction(*I); 3072 } else { 3073 Worklist.AddUsersToWorkList(*I); 3074 Worklist.Add(I); 3075 } 3076 } 3077 MadeIRChange = true; 3078 } 3079 } 3080 3081 Worklist.Zap(); 3082 return MadeIRChange; 3083} 3084 3085/// Walk the function in depth-first order, adding all reachable code to the 3086/// worklist. 3087/// 3088/// This has a couple of tricks to make the code faster and more powerful. In 3089/// particular, we constant fold and DCE instructions as we go, to avoid adding 3090/// them to the worklist (this significantly speeds up instcombine on code where 3091/// many instructions are dead or constant). Additionally, if we find a branch 3092/// whose condition is a known constant, we only visit the reachable successors. 3093static bool AddReachableCodeToWorklist(BasicBlock *BB, const DataLayout &DL, 3094 SmallPtrSetImpl<BasicBlock *> &Visited, 3095 InstCombineWorklist &ICWorklist, 3096 const TargetLibraryInfo *TLI) { 3097 bool MadeIRChange = false; 3098 SmallVector<BasicBlock*, 256> Worklist; 3099 Worklist.push_back(BB); 3100 3101 SmallVector<Instruction*, 128> InstrsForInstCombineWorklist; 3102 DenseMap<Constant *, Constant *> FoldedConstants; 3103 3104 do { 3105 BB = Worklist.pop_back_val(); 3106 3107 // We have now visited this block! If we've already been here, ignore it. 3108 if (!Visited.insert(BB).second) 3109 continue; 3110 3111 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) { 3112 Instruction *Inst = &*BBI++; 3113 3114 // DCE instruction if trivially dead. 3115 if (isInstructionTriviallyDead(Inst, TLI)) { 3116 ++NumDeadInst; 3117 DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n'); 3118 salvageDebugInfo(*Inst); 3119 Inst->eraseFromParent(); 3120 MadeIRChange = true; 3121 continue; 3122 } 3123 3124 // ConstantProp instruction if trivially constant. 3125 if (!Inst->use_empty() && 3126 (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0)))) 3127 if (Constant *C = ConstantFoldInstruction(Inst, DL, TLI)) { 3128 DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " 3129 << *Inst << '\n'); 3130 Inst->replaceAllUsesWith(C); 3131 ++NumConstProp; 3132 if (isInstructionTriviallyDead(Inst, TLI)) 3133 Inst->eraseFromParent(); 3134 MadeIRChange = true; 3135 continue; 3136 } 3137 3138 // See if we can constant fold its operands. 3139 for (Use &U : Inst->operands()) { 3140 if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U)) 3141 continue; 3142 3143 auto *C = cast<Constant>(U); 3144 Constant *&FoldRes = FoldedConstants[C]; 3145 if (!FoldRes) 3146 FoldRes = ConstantFoldConstant(C, DL, TLI); 3147 if (!FoldRes) 3148 FoldRes = C; 3149 3150 if (FoldRes != C) { 3151 DEBUG(dbgs() << "IC: ConstFold operand of: " << *Inst 3152 << "\n Old = " << *C 3153 << "\n New = " << *FoldRes << '\n'); 3154 U = FoldRes; 3155 MadeIRChange = true; 3156 } 3157 } 3158 3159 // Skip processing debug intrinsics in InstCombine. Processing these call instructions 3160 // consumes non-trivial amount of time and provides no value for the optimization. 3161 if (!isa<DbgInfoIntrinsic>(Inst)) 3162 InstrsForInstCombineWorklist.push_back(Inst); 3163 } 3164 3165 // Recursively visit successors. If this is a branch or switch on a 3166 // constant, only visit the reachable successor. 3167 TerminatorInst *TI = BB->getTerminator(); 3168 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 3169 if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) { 3170 bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue(); 3171 BasicBlock *ReachableBB = BI->getSuccessor(!CondVal); 3172 Worklist.push_back(ReachableBB); 3173 continue; 3174 } 3175 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 3176 if (ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition())) { 3177 Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor()); 3178 continue; 3179 } 3180 } 3181 3182 for (BasicBlock *SuccBB : TI->successors()) 3183 Worklist.push_back(SuccBB); 3184 } while (!Worklist.empty()); 3185 3186 // Once we've found all of the instructions to add to instcombine's worklist, 3187 // add them in reverse order. This way instcombine will visit from the top 3188 // of the function down. This jives well with the way that it adds all uses 3189 // of instructions to the worklist after doing a transformation, thus avoiding 3190 // some N^2 behavior in pathological cases. 3191 ICWorklist.AddInitialGroup(InstrsForInstCombineWorklist); 3192 3193 return MadeIRChange; 3194} 3195 3196/// \brief Populate the IC worklist from a function, and prune any dead basic 3197/// blocks discovered in the process. 3198/// 3199/// This also does basic constant propagation and other forward fixing to make 3200/// the combiner itself run much faster. 3201static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL, 3202 TargetLibraryInfo *TLI, 3203 InstCombineWorklist &ICWorklist) { 3204 bool MadeIRChange = false; 3205 3206 // Do a depth-first traversal of the function, populate the worklist with 3207 // the reachable instructions. Ignore blocks that are not reachable. Keep 3208 // track of which blocks we visit. 3209 SmallPtrSet<BasicBlock *, 32> Visited; 3210 MadeIRChange |= 3211 AddReachableCodeToWorklist(&F.front(), DL, Visited, ICWorklist, TLI); 3212 3213 // Do a quick scan over the function. If we find any blocks that are 3214 // unreachable, remove any instructions inside of them. This prevents 3215 // the instcombine code from having to deal with some bad special cases. 3216 for (BasicBlock &BB : F) { 3217 if (Visited.count(&BB)) 3218 continue; 3219 3220 unsigned NumDeadInstInBB = removeAllNonTerminatorAndEHPadInstructions(&BB); 3221 MadeIRChange |= NumDeadInstInBB > 0; 3222 NumDeadInst += NumDeadInstInBB; 3223 } 3224 3225 return MadeIRChange; 3226} 3227 3228static bool combineInstructionsOverFunction( 3229 Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA, 3230 AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, 3231 OptimizationRemarkEmitter &ORE, bool ExpensiveCombines = true, 3232 LoopInfo *LI = nullptr) { 3233 auto &DL = F.getParent()->getDataLayout(); 3234 ExpensiveCombines |= EnableExpensiveCombines; 3235 3236 /// Builder - This is an IRBuilder that automatically inserts new 3237 /// instructions into the worklist when they are created. 3238 IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder( 3239 F.getContext(), TargetFolder(DL), 3240 IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) { 3241 Worklist.Add(I); 3242 if (match(I, m_Intrinsic<Intrinsic::assume>())) 3243 AC.registerAssumption(cast<CallInst>(I)); 3244 })); 3245 3246 // Lower dbg.declare intrinsics otherwise their value may be clobbered 3247 // by instcombiner. 3248 bool MadeIRChange = false; 3249 if (ShouldLowerDbgDeclare) 3250 MadeIRChange = LowerDbgDeclare(F); 3251 3252 // Iterate while there is work to do. 3253 int Iteration = 0; 3254 while (true) { 3255 ++Iteration; 3256 DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on " 3257 << F.getName() << "\n"); 3258 3259 MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist); 3260 3261 InstCombiner IC(Worklist, Builder, F.optForMinSize(), ExpensiveCombines, AA, 3262 AC, TLI, DT, ORE, DL, LI); 3263 IC.MaxArraySizeForCombine = MaxArraySize; 3264 3265 if (!IC.run()) 3266 break; 3267 } 3268 3269 return MadeIRChange || Iteration > 1; 3270} 3271 3272PreservedAnalyses InstCombinePass::run(Function &F, 3273 FunctionAnalysisManager &AM) { 3274 auto &AC = AM.getResult<AssumptionAnalysis>(F); 3275 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 3276 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 3277 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 3278 3279 auto *LI = AM.getCachedResult<LoopAnalysis>(F); 3280 3281 auto *AA = &AM.getResult<AAManager>(F); 3282 if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, 3283 ExpensiveCombines, LI)) 3284 // No changes, all analyses are preserved. 3285 return PreservedAnalyses::all(); 3286 3287 // Mark all the analyses that instcombine updates as preserved. 3288 PreservedAnalyses PA; 3289 PA.preserveSet<CFGAnalyses>(); 3290 PA.preserve<AAManager>(); 3291 PA.preserve<BasicAA>(); 3292 PA.preserve<GlobalsAA>(); 3293 return PA; 3294} 3295 3296void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const { 3297 AU.setPreservesCFG(); 3298 AU.addRequired<AAResultsWrapperPass>(); 3299 AU.addRequired<AssumptionCacheTracker>(); 3300 AU.addRequired<TargetLibraryInfoWrapperPass>(); 3301 AU.addRequired<DominatorTreeWrapperPass>(); 3302 AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); 3303 AU.addPreserved<DominatorTreeWrapperPass>(); 3304 AU.addPreserved<AAResultsWrapperPass>(); 3305 AU.addPreserved<BasicAAWrapperPass>(); 3306 AU.addPreserved<GlobalsAAWrapperPass>(); 3307} 3308 3309bool InstructionCombiningPass::runOnFunction(Function &F) { 3310 if (skipFunction(F)) 3311 return false; 3312 3313 // Required analyses. 3314 auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 3315 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 3316 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 3317 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 3318 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); 3319 3320 // Optional analyses. 3321 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); 3322 auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; 3323 3324 return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, 3325 ExpensiveCombines, LI); 3326} 3327 3328char InstructionCombiningPass::ID = 0; 3329 3330INITIALIZE_PASS_BEGIN(InstructionCombiningPass, "instcombine", 3331 "Combine redundant instructions", false, false) 3332INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 3333INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 3334INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 3335INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 3336INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) 3337INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) 3338INITIALIZE_PASS_END(InstructionCombiningPass, "instcombine", 3339 "Combine redundant instructions", false, false) 3340 3341// Initialization Routines 3342void llvm::initializeInstCombine(PassRegistry &Registry) { 3343 initializeInstructionCombiningPassPass(Registry); 3344} 3345 3346void LLVMInitializeInstCombine(LLVMPassRegistryRef R) { 3347 initializeInstructionCombiningPassPass(*unwrap(R)); 3348} 3349 3350FunctionPass *llvm::createInstructionCombiningPass(bool ExpensiveCombines) { 3351 return new InstructionCombiningPass(ExpensiveCombines); 3352} 3353