1//===- InstructionCombining.cpp - Combine multiple instructions -----------===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// InstructionCombining - Combine instructions to form fewer, simple 10// instructions. This pass does not modify the CFG. This pass is where 11// algebraic simplification happens. 13// This pass combines things like: 19// This is a simple worklist driven algorithm. 21// This pass guarantees that the following canonicalizations are performed on 23// 1. If a binary operator has a constant operand, it is moved to the RHS 24// 2. Bitwise operators with constant operands are always grouped so that 25// shifts are performed first, then or's, then and's, then xor's. 26// 3. Compare instructions are converted from <,>,<=,>= to ==,!= if possible 27// 4. All cmp instructions on boolean values are replaced with logical ops 28// 5. add X, X is represented as (X*2) => (X << 1) 29// 6. Multiplies with a power-of-two constant argument are transformed into 33//===----------------------------------------------------------------------===// 108#define DEBUG_TYPE "instcombine" 116"Number of instruction combining iterations performed");
117STATISTIC(NumOneIteration,
"Number of functions with one iteration");
118STATISTIC(NumTwoIterations,
"Number of functions with two iterations");
119STATISTIC(NumThreeIterations,
"Number of functions with three iterations");
121"Number of functions with four or more iterations");
125STATISTIC(NumDeadInst ,
"Number of dead inst eliminated");
131"Controls which instructions are visited");
138"instcombine-max-sink-users",
cl::init(32),
139cl::desc(
"Maximum number of undroppable users for instruction sinking"));
143cl::desc(
"Maximum array size considered when doing a combine"));
145// FIXME: Remove this flag when it is no longer necessary to convert 146// llvm.dbg.declare to avoid inaccurate debug info. Setting this to false 147// increases variable availability at the cost of accuracy. Variables that 148// cannot be promoted by mem2reg or SROA will be described as living in memory 149// for their entire lifetime. However, passes like DSE and instcombine can 150// delete stores to the alloca, leading to misleading and inaccurate debug 151// information. This flag can be removed when those passes are fixed. 155std::optional<Instruction *>
157// Handle target specific intrinsics 158if (
II.getCalledFunction()->isTargetIntrinsic()) {
166bool &KnownBitsComputed) {
167// Handle target specific intrinsics 168if (
II.getCalledFunction()->isTargetIntrinsic()) {
170 *
this,
II, DemandedMask, Known, KnownBitsComputed);
180// Handle target specific intrinsics 181if (
II.getCalledFunction()->isTargetIntrinsic()) {
183 *
this,
II, DemandedElts, PoisonElts, PoisonElts2, PoisonElts3,
190// Approved exception for TTI use: This queries a legality property of the 191// target, not an profitability heuristic. Ideally this should be part of 192// DataLayout instead. 201auto *Inst = dyn_cast<Instruction>(
GEP);
206// If a non-trivial GEP has other uses, rewrite it to avoid duplicating 207// the offset arithmetic. 208if (Inst && !
GEP->hasOneUse() && !
GEP->hasAllConstantIndices() &&
209 !
GEP->getSourceElementType()->isIntegerTy(8)) {
218/// Legal integers and common types are considered desirable. This is used to 219/// avoid creating instructions with types that may not be supported well by the 221/// NOTE: This treats i8, i16 and i32 specially because they are common 222/// types in frontend languages. 223bool InstCombinerImpl::isDesirableIntType(
unsignedBitWidth)
const{
234/// Return true if it is desirable to convert an integer computation from a 235/// given bit width to a new bit width. 236/// We don't want to convert from a legal or desirable type (like i8) to an 237/// illegal type or from a smaller to a larger illegal type. A width of '1' 238/// is always treated as a desirable type because i1 is a fundamental type in 239/// IR, and there are many specialized optimizations for i1 types. 240/// Common/desirable widths are equally treated as legal to convert to, in 241/// order to open up more combining opportunities. 242bool InstCombinerImpl::shouldChangeType(
unsigned FromWidth,
243unsigned ToWidth)
const{
247// Convert to desirable widths even if they are not legal types. 248// Only shrink types, to prevent infinite loops. 249if (ToWidth < FromWidth && isDesirableIntType(ToWidth))
252// If this is a legal or desiable integer from type, and the result would be 253// an illegal type, don't do the transformation. 254if ((FromLegal || isDesirableIntType(FromWidth)) && !ToLegal)
257// Otherwise, if both are illegal, do not increase the size of the result. We 258// do allow things like i160 -> i64, but not i64 -> i160. 259if (!FromLegal && !ToLegal && ToWidth > FromWidth)
265/// Return true if it is desirable to convert a computation from 'From' to 'To'. 266/// We don't want to convert from a legal to an illegal type or from a smaller 267/// to a larger illegal type. i1 is always treated as a legal type because it is 268/// a fundamental type in IR, and there are many specialized optimizations for 270bool InstCombinerImpl::shouldChangeType(
Type *
From,
Type *To)
const{
271// TODO: This could be extended to allow vectors. Datalayout changes might be 272// needed to properly support that. 276unsigned FromWidth =
From->getPrimitiveSizeInBits();
278return shouldChangeType(FromWidth, ToWidth);
281// Return true, if No Signed Wrap should be maintained for I. 282// The No Signed Wrap flag can be kept if the operation "B (I.getOpcode) C", 283// where both B and C should be ConstantInts, results in a constant that does 284// not overflow. This function only handles the Add/Sub/Mul opcodes. For 285// all other opcodes, the function conservatively returns false. 287auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
288if (!OBO || !OBO->hasNoSignedWrap())
291constAPInt *BVal, *CVal;
295// We reason about Add/Sub/Mul Only. 297switch (
I.getOpcode()) {
298case Instruction::Add:
299 (void)BVal->
sadd_ov(*CVal, Overflow);
301case Instruction::Sub:
302 (void)BVal->
ssub_ov(*CVal, Overflow);
304case Instruction::Mul:
305 (void)BVal->
smul_ov(*CVal, Overflow);
308// Conservatively return false for other opcodes. 315auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
316return OBO && OBO->hasNoUnsignedWrap();
320auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
321return OBO && OBO->hasNoSignedWrap();
324/// Conservatively clears subclassOptionalData after a reassociation or 325/// commutation. We preserve fast-math flags when applicable as they can be 330I.clearSubclassOptionalData();
335I.clearSubclassOptionalData();
336I.setFastMathFlags(FMF);
339/// Combine constant operands of associative operations either before or after a 340/// cast to eliminate one of the associative operations: 341/// (op (cast (op X, C2)), C1) --> (cast (op X, op (C1, C2))) 342/// (op (cast (op X, C2)), C1) --> (op (cast X), op (C1, C2)) 345auto *Cast = dyn_cast<CastInst>(BinOp1->
getOperand(0));
346if (!Cast || !Cast->hasOneUse())
349// TODO: Enhance logic for other casts and remove this check. 350auto CastOpcode = Cast->getOpcode();
351if (CastOpcode != Instruction::ZExt)
354// TODO: Enhance logic for other BinOps and remove this check. 359auto *BinOp2 = dyn_cast<BinaryOperator>(Cast->getOperand(0));
360if (!BinOp2 || !BinOp2->hasOneUse() || BinOp2->getOpcode() != AssocOpcode)
368// TODO: This assumes a zext cast. 369// Eg, if it was a trunc, we'd cast C1 to the source type because casting C2 370// to the destination type might lose bits. 372// Fold the constants together in the destination type: 373// (op (cast (op X, C2)), C1) --> (op (cast X), FoldedC) 386 Cast->dropPoisonGeneratingFlags();
390// Simplifies IntToPtr/PtrToInt RoundTrip Cast. 391// inttoptr ( ptrtoint (x) ) --> x 392Value *InstCombinerImpl::simplifyIntToPtrRoundTripCast(
Value *Val) {
393auto *IntToPtr = dyn_cast<IntToPtrInst>(Val);
396auto *PtrToInt = dyn_cast<PtrToIntInst>(IntToPtr->getOperand(0));
397Type *CastTy = IntToPtr->getDestTy();
400 PtrToInt->getSrcTy()->getPointerAddressSpace() &&
403return PtrToInt->getOperand(0);
408/// This performs a few simplifications for operators that are associative or 411/// Commutative operators: 413/// 1. Order operands such that they are listed from right (least complex) to 414/// left (most complex). This puts constants before unary operators before 417/// Associative operators: 419/// 2. Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies. 420/// 3. Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies. 422/// Associative and commutative operators: 424/// 4. Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies. 425/// 5. Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies. 426/// 6. Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)" 427/// if C1 and C2 are constants. 433// Order operands such that they are listed from right (least complex) to 434// left (most complex). This puts constants before unary operators before 438 Changed = !
I.swapOperands();
440if (
I.isCommutative()) {
441if (
auto Pair = matchSymmetricPair(
I.getOperand(0),
I.getOperand(1))) {
451if (
I.isAssociative()) {
452// Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies. 458// Does "B op C" simplify? 460// It simplifies to V. Form "A op V". 466// Conservatively clear all optional flags since they may not be 467// preserved by the reassociation. Reset nsw/nuw based on the above 471// Note: this is only valid because SimplifyBinOp doesn't look at 472// the operands to Op0. 474I.setHasNoUnsignedWrap(
true);
477I.setHasNoSignedWrap(
true);
485// Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies. 491// Does "A op B" simplify? 493// It simplifies to V. Form "V op C". 496// Conservatively clear the optional flags, since they may not be 497// preserved by the reassociation. 506if (
I.isAssociative() &&
I.isCommutative()) {
513// Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies. 519// Does "C op A" simplify? 521// It simplifies to V. Form "V op B". 524// Conservatively clear the optional flags, since they may not be 525// preserved by the reassociation. 533// Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies. 539// Does "C op A" simplify? 541// It simplifies to V. Form "B op V". 544// Conservatively clear the optional flags, since they may not be 545// preserved by the reassociation. 553// Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)" 554// if C1 and C2 are constants. 569if (isa<FPMathOperator>(NewBO)) {
579// Conservatively clear the optional flags, since they may not be 580// preserved by the reassociation. 583I.setHasNoUnsignedWrap(
true);
590// No further simplifications. 595/// Return whether "X LOp (Y ROp Z)" is always equal to 596/// "(X LOp Y) ROp (X LOp Z)". 599// X & (Y | Z) <--> (X & Y) | (X & Z) 600// X & (Y ^ Z) <--> (X & Y) ^ (X & Z) 601if (LOp == Instruction::And)
602return ROp == Instruction::Or || ROp == Instruction::Xor;
604// X | (Y & Z) <--> (X | Y) & (X | Z) 605if (LOp == Instruction::Or)
606return ROp == Instruction::And;
608// X * (Y + Z) <--> (X * Y) + (X * Z) 609// X * (Y - Z) <--> (X * Y) - (X * Z) 610if (LOp == Instruction::Mul)
611return ROp == Instruction::Add || ROp == Instruction::Sub;
616/// Return whether "(X LOp Y) ROp Z" is always equal to 617/// "(X ROp Z) LOp (Y ROp Z)". 623// (X {&|^} Y) >> Z <--> (X >> Z) {&|^} (Y >> Z) for all shifts. 626// TODO: It would be nice to handle division, aka "(X + Y)/Z = X/Z + Y/Z", 627// but this requires knowing that the addition does not overflow and other 631/// This function returns identity value for given opcode, which can be used to 632/// factor patterns like (X * 2) + X ==> (X * 2) + (X * 1) ==> X * (2 + 1). 640/// This function predicates factorization using distributive laws. By default, 641/// it just returns the 'Op' inputs. But for special-cases like 642/// 'add(shl(X, 5), ...)', this function will have TopOpcode == Instruction::Add 643/// and Op = shl(X, 5). The 'shl' is treated as the more general 'mul X, 32' to 644/// allow more factorization opportunities. 648assert(
Op &&
"Expected a binary operator");
649LHS =
Op->getOperand(0);
650RHS =
Op->getOperand(1);
651if (TopOpcode == Instruction::Add || TopOpcode == Instruction::Sub) {
654// X << C --> X * (1 << C) 656 Instruction::Shl, ConstantInt::get(
Op->getType(), 1),
C);
657assert(
RHS &&
"Constant folding of immediate constants failed");
658return Instruction::Mul;
660// TODO: We can add other conversions e.g. shr => div etc. 663if (OtherOp && OtherOp->
getOpcode() == Instruction::AShr &&
665// lshr nneg C, X --> ashr nneg C, X 666return Instruction::AShr;
669returnOp->getOpcode();
672/// This tries to simplify binary operations by factorizing out common terms 673/// (e. g. "(A*B)+(A*C)" -> "A*(B+C)"). 678assert(
A &&
B &&
C &&
D &&
"All values must be provided");
681Value *RetVal =
nullptr;
685// Does "X op' Y" always equal "Y op' X"? 688// Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"? 690// Does the instruction have the form "(A op' B) op (A op' D)" or, in the 691// commutative case, "(A op' B) op (C op' A)"? 692if (
A ==
C || (InnerCommutative &&
A ==
D)) {
695// Consider forming "A op' (B op D)". 696// If "B op D" simplifies then it can be formed with no cost. 699// If "B op D" doesn't simplify then only go on if one of the existing 700// operations "A op' B" and "C op' D" will be zapped as no longer used. 708// Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"? 710// Does the instruction have the form "(A op' B) op (C op' B)" or, in the 711// commutative case, "(A op' B) op (B op' D)"? 712if (
B ==
D || (InnerCommutative &&
B ==
C)) {
715// Consider forming "(A op C) op' B". 716// If "A op C" simplifies then it can be formed with no cost. 719// If "A op C" doesn't simplify then only go on if one of the existing 720// operations "A op' B" and "C op' D" will be zapped as no longer used. 734// Try to add no-overflow flags to the final value. 735if (isa<BinaryOperator>(RetVal)) {
738if (isa<OverflowingBinaryOperator>(&
I)) {
739 HasNSW =
I.hasNoSignedWrap();
740 HasNUW =
I.hasNoUnsignedWrap();
742if (
auto *LOBO = dyn_cast<OverflowingBinaryOperator>(
LHS)) {
743 HasNSW &= LOBO->hasNoSignedWrap();
744 HasNUW &= LOBO->hasNoUnsignedWrap();
747if (
auto *ROBO = dyn_cast<OverflowingBinaryOperator>(
RHS)) {
748 HasNSW &= ROBO->hasNoSignedWrap();
749 HasNUW &= ROBO->hasNoUnsignedWrap();
752if (TopLevelOpcode == Instruction::Add && InnerOpcode == Instruction::Mul) {
753// We can propagate 'nsw' if we know that 754// %Y = mul nsw i16 %X, C 755// %Z = add nsw i16 %Y, %X 757// %Z = mul nsw i16 %X, C+1 759// iff C+1 isn't INT_MIN 762 cast<Instruction>(RetVal)->setHasNoSignedWrap(HasNSW);
764// nuw can be propagated with any constant or nuw value. 765 cast<Instruction>(RetVal)->setHasNoUnsignedWrap(HasNUW);
771// If `I` has one Const operand and the other matches `(ctpop (not x))`, 772// replace `(ctpop (not x))` with `(sub nuw nsw BitWidth(x), (ctpop x))`. 773// This is only useful is the new subtract can fold so we only handle the 775// 1) (add/sub/disjoint_or C, (ctpop (not x)) 776// -> (add/sub/disjoint_or C', (ctpop x)) 777// 1) (cmp pred C, (ctpop (not x)) 778// -> (cmp pred C', (ctpop x)) 780unsigned Opc =
I->getOpcode();
781unsigned ConstIdx = 1;
785// (ctpop (not x)) <-> (sub nuw nsw BitWidth(x) - (ctpop x)) 786// We can fold the BitWidth(x) with add/sub/icmp as long the other operand 788case Instruction::Sub:
791case Instruction::ICmp:
792// Signed predicates aren't correct in some edge cases like for i2 types, as 793// well since (ctpop x) is known [0, log2(BitWidth(x))] almost all signed 794// comparisons against it are simplfied to unsigned. 802case Instruction::Add:
808if (!
match(
I->getOperand(1 - ConstIdx),
813// Check other operand is ImmConstant. 819// Need extra check for icmp. Note if this check is true, it generally means 820// the icmp will simplify to true/false. 821if (Opc == Instruction::ICmp && !cast<ICmpInst>(
I)->isEquality()) {
824if (!Cmp || !Cmp->isZeroValue())
828// Check we can invert `(not x)` for free. 834"Desync between isFreeToInvert and getFreelyInverted");
840// Do the transformation here to avoid potentially introducing an infinite 843case Instruction::Sub:
847case Instruction::Add:
850case Instruction::ICmp:
861// (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C)) 863// 1) the logic_shifts match 864// 2) either both binops are binops and one is `and` or 866// (logic_shift (inv_logic_shift C1, C), C) == C1 or 868// -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C) 870// (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt)) 872// 1) the logic_shifts match 873// 2) BinOp1 == BinOp2 (if BinOp == `add`, then also requires `shl`). 875// -> (BinOp (logic_shift (BinOp X, Y)), Mask) 877// (Binop1 (Binop2 (arithmetic_shift X, Amt), Mask), (arithmetic_shift Y, Amt)) 879// 1) Binop1 is bitwise logical operator `and`, `or` or `xor` 882// -> (arithmetic_shift Binop1((not X), Y), Amt) 886auto IsValidBinOpc = [](
unsigned Opc) {
890case Instruction::And:
892case Instruction::Xor:
893case Instruction::Add:
894// Skip Sub as we only match constant masks which will canonicalize to use 900// Check if we can distribute binop arbitrarily. `add` + `lshr` has extra 902auto IsCompletelyDistributable = [](
unsigned BinOpc1,
unsigned BinOpc2,
904assert(ShOpc != Instruction::AShr);
905return (BinOpc1 != Instruction::Add && BinOpc2 != Instruction::Add) ||
906 ShOpc == Instruction::Shl;
909auto GetInvShift = [](
unsigned ShOpc) {
910assert(ShOpc != Instruction::AShr);
911return ShOpc == Instruction::LShr ? Instruction::Shl : Instruction::LShr;
914auto CanDistributeBinops = [&](
unsigned BinOpc1,
unsigned BinOpc2,
917// If the BinOp1 is `and` we don't need to check the mask. 918if (BinOpc1 == Instruction::And)
921// For all other possible transfers we need complete distributable 922// binop/shift (anything but `add` + `lshr`). 923if (!IsCompletelyDistributable(BinOpc1, BinOpc2, ShOpc))
926// If BinOp2 is `and`, any mask works (this only really helps for non-splat 927// vecs, otherwise the mask will be simplified and the following check will 929if (BinOpc2 == Instruction::And)
932// Otherwise, need mask that meets the below requirement. 933// (logic_shift (inv_logic_shift Mask, ShAmt), ShAmt) == Mask 940auto MatchBinOp = [&](
unsigned ShOpnum) ->
Instruction * {
942Value *
X, *
Y, *ShiftedX, *Mask, *Shift;
943if (!
match(
I.getOperand(ShOpnum),
946if (!
match(
I.getOperand(1 - ShOpnum),
952// Make sure we are matching instruction shifts and not ConstantExpr 953auto *IY = dyn_cast<Instruction>(
I.getOperand(ShOpnum));
954auto *IX = dyn_cast<Instruction>(ShiftedX);
958// LHS and RHS need same shift opcode 959unsigned ShOpc = IY->getOpcode();
960if (ShOpc != IX->getOpcode())
963// Make sure binop is real instruction and not ConstantExpr 964auto *BO2 = dyn_cast<Instruction>(
I.getOperand(1 - ShOpnum));
968unsigned BinOpc = BO2->getOpcode();
969// Make sure we have valid binops. 970if (!IsValidBinOpc(
I.getOpcode()) || !IsValidBinOpc(BinOpc))
973if (ShOpc == Instruction::AShr) {
985// If BinOp1 == BinOp2 and it's bitwise or shl with add, then just 986// distribute to drop the shift irrelevant of constants. 987if (BinOpc ==
I.getOpcode() &&
988 IsCompletelyDistributable(
I.getOpcode(), BinOpc, ShOpc)) {
995// Otherwise we can only distribute by constant shifting the mask, so 996// ensure we have constants. 1002// Check if we can distribute the binops. 1003if (!CanDistributeBinops(
I.getOpcode(), BinOpc, ShOpc, CMask, CShift))
1017return MatchBinOp(1);
1020// (Binop (zext C), (select C, T, F)) 1021// -> (select C, (binop 1, T), (binop 0, F)) 1023// (Binop (sext C), (select C, T, F)) 1024// -> (select C, (binop -1, T), (binop 0, F)) 1026// Attempt to simplify binary operations into a select with folded args, when 1027// one operand of the binop is a select instruction and the other operand is a 1028// zext/sext extension, whose value is the select condition. 1031// TODO: this simplification may be extended to any speculatable instruction, 1032// not just binops, and would possibly be handled better in FoldOpIntoSelect. 1035Value *
A, *CondVal, *TrueVal, *FalseVal;
1038auto MatchSelectAndCast = [&](
Value *CastOp,
Value *SelectOp) {
1040A->getType()->getScalarSizeInBits() == 1 &&
1045// Make sure one side of the binop is a select instruction, and the other is a 1046// zero/sign extension operating on a i1. 1047if (MatchSelectAndCast(
LHS,
RHS))
1049elseif (MatchSelectAndCast(
RHS,
LHS))
1054auto NewFoldedConst = [&](
bool IsTrueArm,
Value *V) {
1055bool IsCastOpRHS = (CastOp ==
RHS);
1056bool IsZExt = isa<ZExtInst>(CastOp);
1062unsignedBitWidth = V->getType()->getScalarSizeInBits();
1072// If the value used in the zext/sext is the select condition, or the negated 1073// of the select condition, the binop can be simplified. 1075Value *NewTrueVal = NewFoldedConst(
false, TrueVal);
1077 NewFoldedConst(
true, FalseVal));
1081Value *NewTrueVal = NewFoldedConst(
true, TrueVal);
1083 NewFoldedConst(
false, FalseVal));
1102// The instruction has the form "(A op' B) op (C op' D)". Try to factorize 1104if (Op0 && Op1 && LHSOpcode == RHSOpcode)
1108// The instruction has the form "(A op' B) op (C)". Try to factorize common 1116// The instruction has the form "(B) op (C op' D)". Try to factorize common 1127/// This tries to simplify binary operations which some other binary operation 1128/// distributes over either by factorizing out common terms 1129/// (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this results in 1130/// simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is a win). 1131/// Returns the simplified value, or null if it didn't simplify. 1144// The instruction has the form "(A op' B) op C". See if expanding it out 1145// to "(A op C) op' (B op C)" results in simplifications. 1149// Disable the use of undef because it's not safe to distribute undef. 1154// Do "A op C" and "B op C" both simplify? 1156// They do! Return "L op' R". 1163// Does "A op C" simplify to the identity value for the inner opcode? 1165// They do! Return "B op C". 1172// Does "B op C" simplify to the identity value for the inner opcode? 1174// They do! Return "A op C". 1183// The instruction has the form "A op (B op' C)". See if expanding it out 1184// to "(A op B) op' (A op C)" results in simplifications. 1188// Disable the use of undef because it's not safe to distribute undef. 1193// Do "A op B" and "A op C" both simplify? 1195// They do! Return "L op' R". 1202// Does "A op B" simplify to the identity value for the inner opcode? 1204// They do! Return "A op C". 1211// Does "A op C" simplify to the identity value for the inner opcode? 1213// They do! Return "A op B". 1224static std::optional<std::pair<Value *, Value *>>
1226if (
LHS->getParent() !=
RHS->getParent())
1229if (
LHS->getNumIncomingValues() < 2)
1235Value *L0 =
LHS->getIncomingValue(0);
1236Value *R0 =
RHS->getIncomingValue(0);
1238for (
unsignedI = 1, E =
LHS->getNumIncomingValues();
I != E; ++
I) {
1242if ((L0 == L1 && R0 == R1) || (L0 == R1 && R0 == L1))
1248return std::optional(std::pair(L0, R0));
1251std::optional<std::pair<Value *, Value *>>
1252InstCombinerImpl::matchSymmetricPair(
Value *LHS,
Value *RHS) {
1258case Instruction::PHI:
1260case Instruction::Select: {
1266return std::pair(TrueVal, FalseVal);
1269case Instruction::Call: {
1270// Match min(a, b) and max(a, b) 1273if (LHSMinMax && RHSMinMax &&
1280return std::pair(LHSMinMax->
getLHS(), LHSMinMax->
getRHS());
1294if (!LHSIsSelect && !RHSIsSelect)
1299if (isa<FPMathOperator>(&
I)) {
1300 FMF =
I.getFastMathFlags();
1307Value *
Cond, *True =
nullptr, *False =
nullptr;
1309// Special-case for add/negate combination. Replace the zero in the negation 1310// with the trailing add operand: 1311// (Cond ? TVal : -N) + Z --> Cond ? True : (Z - N) 1312// (Cond ? -N : FVal) + Z --> Cond ? (Z - N) : False 1314// We need an 'add' and exactly 1 arm of the select to have been simplified. 1315if (Opcode != Instruction::Add || (!True && !False) || (True && False))
1330if (LHSIsSelect && RHSIsSelect &&
A ==
D) {
1331// (A ? B : C) op (A ? E : F) -> A ? (B op E) : (C op F) 1339elseif (True && !False)
1343// (A ? B : C) op Y -> A ? (B op Y) : (C op Y) 1350// X op (D ? E : F) -> D ? (X op E) : (X op F) 1354if (
Value *NewSel = foldAddNegate(E,
F,
LHS))
1366/// Freely adapt every user of V as-if V was changed to !V. 1367/// WARNING: only if canFreelyInvertAllUsersOf() said this can be done. 1369assert(!isa<Constant>(
I) &&
"Shouldn't invert users of constant");
1371if (U == IgnoredUser)
1372continue;
// Don't consider this user. 1373switch (cast<Instruction>(U)->
getOpcode()) {
1374case Instruction::Select: {
1375auto *SI = cast<SelectInst>(U);
1377 SI->swapProfMetadata();
1380case Instruction::Br: {
1387case Instruction::Xor:
1389// Add to worklist for DCE. 1394"canFreelyInvertAllUsersOf() ?");
1399/// Given a 'sub' instruction, return the RHS of the instruction if the LHS is a 1400/// constant zero (which is the 'negate' form). 1401Value *InstCombinerImpl::dyn_castNegVal(
Value *V)
const{
1406// Constants can be considered to be negated values if they can be folded. 1411if (
C->getType()->getElementType()->isIntegerTy())
1415for (
unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
1420if (isa<UndefValue>(Elt))
1423if (!isa<ConstantInt>(Elt))
1429// Negate integer vector splats. 1430if (
auto *CV = dyn_cast<Constant>(V))
1431if (CV->getType()->isVectorTy() &&
1432 CV->getType()->getScalarType()->isIntegerTy() && CV->getSplatValue())
1439// 1) (fp_binop ({s|u}itofp x), ({s|u}itofp y)) 1440// -> ({s|u}itofp (int_binop x, y)) 1441// 2) (fp_binop ({s|u}itofp x), FpC) 1442// -> ({s|u}itofp (int_binop x, (fpto{s|u}i FpC))) 1444// Assuming the sign of the cast for x/y is `OpsFromSigned`. 1445Instruction *InstCombinerImpl::foldFBinOpOfIntCastsFromSign(
1446BinaryOperator &BO,
bool OpsFromSigned, std::array<Value *, 2> IntOps,
1450Type *IntTy = IntOps[0]->getType();
1453// This is the maximum number of inuse bits by the integer where the int -> fp 1455unsigned MaxRepresentableBits =
1458// Preserve known number of leading bits. This can allow us to trivial nsw/nuw 1460unsigned NumUsedLeadingBits[2] = {IntSz, IntSz};
1462// NB: This only comes up if OpsFromSigned is true, so there is no need to 1463// cache if between calls to `foldFBinOpOfIntCastsFromSign`. 1464auto IsNonZero = [&](
unsigned OpNo) ->
bool {
1465if (OpsKnown[OpNo].hasKnownBits() &&
1466 OpsKnown[OpNo].getKnownBits(
SQ).isNonZero())
1471auto IsNonNeg = [&](
unsigned OpNo) ->
bool {
1472// NB: This matches the impl in ValueTracking, we just try to use cached 1473// knownbits here. If we ever start supporting WithCache for 1474// `isKnownNonNegative`, change this to an explicit call. 1475return OpsKnown[OpNo].getKnownBits(
SQ).isNonNegative();
1478// Check if we know for certain that ({s|u}itofp op) is exact. 1479auto IsValidPromotion = [&](
unsigned OpNo) ->
bool {
1480// Can we treat this operand as the desired sign? 1481if (OpsFromSigned != isa<SIToFPInst>(BO.
getOperand(OpNo)) &&
1485// If fp precision >= bitwidth(op) then its exact. 1486// NB: This is slightly conservative for `sitofp`. For signed conversion, we 1487// can handle `MaxRepresentableBits == IntSz - 1` as the sign bit will be 1488// handled specially. We can't, however, increase the bound arbitrarily for 1489// `sitofp` as for larger sizes, it won't sign extend. 1490if (MaxRepresentableBits < IntSz) {
1491// Otherwise if its signed cast check that fp precisions >= bitwidth(op) - 1493// TODO: If we add support for `WithCache` in `ComputeNumSignBits`, change 1494// `IntOps[OpNo]` arguments to `KnownOps[OpNo]`. 1497// Finally for unsigned check that fp precision >= bitwidth(op) - 1498// numLeadingZeros(op). 1500 NumUsedLeadingBits[OpNo] =
1501 IntSz - OpsKnown[OpNo].getKnownBits(
SQ).countMinLeadingZeros();
1504// NB: We could also check if op is known to be a power of 2 or zero (which 1505// will always be representable). Its unlikely, however, that is we are 1506// unable to bound op in any way we will be able to pass the overflow checks 1509if (MaxRepresentableBits < NumUsedLeadingBits[OpNo])
1511// Signed + Mul also requires that op is non-zero to avoid -0 cases. 1512return !OpsFromSigned || BO.
getOpcode() != Instruction::FMul ||
1516// If we have a constant rhs, see if we can losslessly convert it to an int. 1517if (Op1FpC !=
nullptr) {
1518// Signed + Mul req non-zero 1519if (OpsFromSigned && BO.
getOpcode() == Instruction::FMul &&
1524 OpsFromSigned ? Instruction::FPToSI : Instruction::FPToUI, Op1FpC,
1526if (Op1IntC ==
nullptr)
1529 : Instruction::UIToFP,
1530 Op1IntC, FPTy,
DL) != Op1FpC)
1533// First try to keep sign of cast the same. 1534 IntOps[1] = Op1IntC;
1537// Ensure lhs/rhs integer types match. 1538if (IntTy != IntOps[1]->
getType())
1541if (Op1FpC ==
nullptr) {
1542if (!IsValidPromotion(1))
1545if (!IsValidPromotion(0))
1548// Final we check if the integer version of the binop will not overflow. 1550// Because of the precision check, we can often rule out overflows. 1551bool NeedsOverflowCheck =
true;
1552// Try to conservatively rule out overflow based on the already done precision 1554unsigned OverflowMaxOutputBits = OpsFromSigned ? 2 : 1;
1555unsigned OverflowMaxCurBits =
1556 std::max(NumUsedLeadingBits[0], NumUsedLeadingBits[1]);
1557bool OutputSigned = OpsFromSigned;
1559case Instruction::FAdd:
1560 IntOpc = Instruction::Add;
1561 OverflowMaxOutputBits += OverflowMaxCurBits;
1563case Instruction::FSub:
1564 IntOpc = Instruction::Sub;
1565 OverflowMaxOutputBits += OverflowMaxCurBits;
1567case Instruction::FMul:
1568 IntOpc = Instruction::Mul;
1569 OverflowMaxOutputBits += OverflowMaxCurBits * 2;
1574// The precision check may have already ruled out overflow. 1575if (OverflowMaxOutputBits < IntSz) {
1576 NeedsOverflowCheck =
false;
1577// We can bound unsigned overflow from sub to in range signed value (this is 1578// what allows us to avoid the overflow check for sub). 1579if (IntOpc == Instruction::Sub)
1583// Precision check did not rule out overflow, so need to check. 1584// TODO: If we add support for `WithCache` in `willNotOverflow`, change 1585// `IntOps[...]` arguments to `KnownOps[...]`. 1586if (NeedsOverflowCheck &&
1587 !willNotOverflow(IntOpc, IntOps[0], IntOps[1], BO, OutputSigned))
1591if (
auto *IntBO = dyn_cast<BinaryOperator>(IntBinOp)) {
1592 IntBO->setHasNoSignedWrap(OutputSigned);
1593 IntBO->setHasNoUnsignedWrap(!OutputSigned);
1601// 1) (fp_binop ({s|u}itofp x), ({s|u}itofp y)) 1602// -> ({s|u}itofp (int_binop x, y)) 1603// 2) (fp_binop ({s|u}itofp x), FpC) 1604// -> ({s|u}itofp (int_binop x, (fpto{s|u}i FpC))) 1606 std::array<Value *, 2> IntOps = {
nullptr,
nullptr};
1609// 1) (binop ({s|u}itofp x), ({s|u}itofp y)) 1610// 2) (binop ({s|u}itofp x), FpC) 1620// Cache KnownBits a bit to potentially save some analysis. 1623// Try treating x/y as coming from both `uitofp` and `sitofp`. There are 1624// different constraints depending on the sign of the cast. 1625// NB: `(uitofp nneg X)` == `(sitofp nneg X)`. 1626if (
Instruction *R = foldFBinOpOfIntCastsFromSign(BO,
/*OpsFromSigned=*/false,
1627 IntOps, Op1FpC, OpsKnown))
1629return foldFBinOpOfIntCastsFromSign(BO,
/*OpsFromSigned=*/true, IntOps,
1633/// A binop with a constant operand and a sign-extended boolean operand may be 1634/// converted into a select of constants by applying the binary operation to 1635/// the constant with the two possible values of the extended boolean (0 or -1). 1637// TODO: Handle non-commutative binop (constant is operand 0). 1638// TODO: Handle zext. 1639// TODO: Peek through 'not' of cast. 1645 !
X->getType()->isIntOrIntVectorTy(1))
1648// bo (sext i1 X), C --> select X, (bo -1, C), (bo 0, C) 1662 V = IsTrueArm ? SI->getTrueValue() : SI->getFalseValue();
1663 }
elseif (
match(SI->getCondition(),
1688bool FoldWithMultiUse) {
1689// Don't modify shared select instructions unless set FoldWithMultiUse 1690if (!SI->hasOneUse() && !FoldWithMultiUse)
1693Value *TV = SI->getTrueValue();
1694Value *FV = SI->getFalseValue();
1696// Bool selects with constant operands can be folded to logical ops. 1697if (SI->getType()->isIntOrIntVectorTy(1))
1700// Test if a FCmpInst instruction is used exclusively by a select as 1701// part of a minimum or maximum operation. If so, refrain from doing 1702// any other folding. This helps out other analyses which understand 1703// non-obfuscated minimum and maximum idioms. And in this case, at 1704// least one of the comparison operands has at least one user besides 1705// the compare (the select), which would often largely negate the 1706// benefit of folding anyway. 1707if (
auto *CI = dyn_cast<FCmpInst>(SI->getCondition())) {
1708if (CI->hasOneUse()) {
1709Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);
1710if ((TV == Op0 && FV == Op1) || (FV == Op0 && TV == Op1))
1715// Make sure that one of the select arms folds successfully. 1719if (!NewTV && !NewFV)
1722// Create an instruction for the arm that did not fold. 1734// NB: It is a precondition of this transform that the operands be 1744// Don't consider the simplification successful if we get back a constant 1745// expression. That's just an instruction in hiding. 1746// Also reject the case where we simplify back to the phi node. We wouldn't 1747// be able to remove it in that case. 1753// Check if incoming PHI value can be replaced with constant 1754// based on implied condition. 1756constICmpInst *ICmp = dyn_cast<ICmpInst>(&
I);
1771bool AllowMultipleUses) {
1773if (NumPHIValues == 0)
1776// We normally only transform phis with a single use. However, if a PHI has 1777// multiple uses and they are all the same operation, we can fold *all* of the 1778// uses into the PHI. 1780bool IdenticalUsers =
false;
1781if (!AllowMultipleUses && !OneUse) {
1782// Walk the use list for the instruction, comparing them to I. 1785if (UI != &
I && !
I.isIdenticalTo(UI))
1788// Otherwise, we can replace *all* users with the new PHI we form. 1789 IdenticalUsers =
true;
1792// Check that all operands are phi-translatable. 1797// Non-instructions never require phi-translation. 1798auto *
I = dyn_cast<Instruction>(
Op);
1802// Phi-translate can handle phi nodes in the same block. 1807// Operand dominates the block, no phi-translation necessary. 1811// Not phi-translatable, bail out. 1815// Check to see whether the instruction can be folded into each phi operand. 1816// If there is one operand that does not fold, remember the BB it is in. 1819bool SeenNonSimplifiedInVal =
false;
1820for (
unsigned i = 0; i != NumPHIValues; ++i) {
1829// Handle some cases that can't be fully simplified, but where we know that 1830// the two instructions will fold into one. 1831auto WillFold = [&]() {
1835// icmp of ucmp/scmp with constant will fold to icmp. 1837if (isa<CmpIntrinsic>(InVal) &&
1841// icmp eq zext(bool), 0 will fold to !bool. 1842if (isa<ZExtInst>(InVal) &&
1843 cast<ZExtInst>(InVal)->getSrcTy()->isIntOrIntVectorTy(1) &&
1857if (!OneUse && !IdenticalUsers)
1860if (SeenNonSimplifiedInVal)
1861returnnullptr;
// More than one non-simplified value. 1862 SeenNonSimplifiedInVal =
true;
1864// If there is exactly one non-simplified value, we can insert a copy of the 1865// operation in that block. However, if this is a critical edge, we would 1866// be inserting the computation on some other paths (e.g. inside a loop). 1867// Only do this if the pred block is unconditionally branching into the phi 1868// block. Also, make sure that the pred block is not dead code. 1876// If the InVal is an invoke at the end of the pred block, then we can't 1877// insert a computation after it without breaking the edge. 1878if (isa<InvokeInst>(InVal))
1879if (cast<Instruction>(InVal)->
getParent() == InBB)
1882// Do not push the operation across a loop backedge. This could result in 1883// an infinite combine loop, and is generally non-profitable (especially 1884// if the operation was originally outside the loop). 1889// Clone the instruction that uses the phi node and move it into the incoming 1890// BB because we know that the next iteration of InstCombine will simplify it. 1892for (
autoOpIndex : OpsToMoveUseToIncomingBB) {
1903 U = U->DoPHITranslation(PN->
getParent(), OpBB);
1906 Clones.
insert({OpBB, Clone});
1909 NewPhiValues[
OpIndex] = Clone;
1912// Okay, we can do the transformation: create the new PHI node. 1918for (
unsigned i = 0; i != NumPHIValues; ++i)
1921if (IdenticalUsers) {
1941// TODO: This should be similar to the incoming values check in foldOpIntoPhi: 1942// we are guarding against replicating the binop in >1 predecessor. 1943// This could miss matching a phi with 2 constant incoming values. 1944auto *Phi0 = dyn_cast<PHINode>(BO.
getOperand(0));
1945auto *Phi1 = dyn_cast<PHINode>(BO.
getOperand(1));
1946if (!Phi0 || !Phi1 || !Phi0->hasOneUse() || !Phi1->hasOneUse() ||
1947 Phi0->getNumOperands() != Phi1->getNumOperands())
1950// TODO: Remove the restriction for binop being in the same block as the phis. 1951if (BO.
getParent() != Phi0->getParent() ||
1955// Fold if there is at least one specific constant value in phi0 or phi1's 1956// incoming values that comes from the same block and this specific constant 1957// value can be used to do optimization for specific binary operator. 1959// %phi0 = phi i32 [0, %bb0], [%i, %bb1] 1960// %phi1 = phi i32 [%j, %bb0], [0, %bb1] 1961// %add = add i32 %phi0, %phi1 1963// %add = phi i32 [%j, %bb0], [%i, %bb1] 1965/*AllowRHSConstant*/false);
1968auto CanFoldIncomingValuePair = [&](std::tuple<Use &, Use &>
T) {
1969auto &Phi0Use = std::get<0>(
T);
1970auto &Phi1Use = std::get<1>(
T);
1971if (Phi0->getIncomingBlock(Phi0Use) != Phi1->getIncomingBlock(Phi1Use))
1973Value *Phi0UseV = Phi0Use.get();
1974Value *Phi1UseV = Phi1Use.get();
1977elseif (Phi1UseV ==
C)
1984if (
all_of(
zip(Phi0->operands(), Phi1->operands()),
1985 CanFoldIncomingValuePair)) {
1988assert(NewIncomingValues.
size() == Phi0->getNumOperands() &&
1989"The number of collected incoming values should equal the number " 1990"of the original PHINode operands!");
1991for (
unsignedI = 0;
I < Phi0->getNumOperands();
I++)
1992 NewPhi->
addIncoming(NewIncomingValues[
I], Phi0->getIncomingBlock(
I));
1997if (Phi0->getNumOperands() != 2 || Phi1->getNumOperands() != 2)
2000// Match a pair of incoming constants for one of the predecessor blocks. 2004 ConstBB = Phi0->getIncomingBlock(0);
2005 OtherBB = Phi0->getIncomingBlock(1);
2007 ConstBB = Phi0->getIncomingBlock(1);
2008 OtherBB = Phi0->getIncomingBlock(0);
2015// The block that we are hoisting to must reach here unconditionally. 2016// Otherwise, we could be speculatively executing an expensive or 2017// non-speculative op. 2018auto *PredBlockBranch = dyn_cast<BranchInst>(OtherBB->
getTerminator());
2019if (!PredBlockBranch || PredBlockBranch->isConditional() ||
2023// TODO: This check could be tightened to only apply to binops (div/rem) that 2024// are not safe to speculatively execute. But that could allow hoisting 2025// potentially expensive instructions (fdiv for example). 2026for (
auto BBIter = BO.
getParent()->begin(); &*BBIter != &BO; ++BBIter)
2030// Fold constants for the predecessor block with constant incoming values. 2035// Make a new binop in the predecessor block with the non-constant incoming 2039 Phi0->getIncomingValueForBlock(OtherBB),
2040 Phi1->getIncomingValueForBlock(OtherBB));
2041if (
auto *NotFoldedNewBO = dyn_cast<BinaryOperator>(NewBO))
2042 NotFoldedNewBO->copyIRFlags(&BO);
2044// Replace the binop with a phi of the new values. The old phis are dead. 2052if (!isa<Constant>(
I.getOperand(1)))
2055if (
auto *Sel = dyn_cast<SelectInst>(
I.getOperand(0))) {
2058 }
elseif (
auto *PN = dyn_cast<PHINode>(
I.getOperand(0))) {
2066// If this GEP has only 0 indices, it is the same pointer as 2067// Src. If Src is not a trivial GEP too, don't combine 2069if (
GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() &&
2076if (!isa<VectorType>(Inst.
getType()))
2082 cast<VectorType>(Inst.
getType())->getElementCount());
2084 cast<VectorType>(Inst.
getType())->getElementCount());
2086// If both operands of the binop are vector concatenations, then perform the 2087// narrow binop on each pair of the source operands followed by concatenation 2089Value *L0, *L1, *R0, *R1;
2094 cast<ShuffleVectorInst>(
LHS)->isConcat() &&
2095 cast<ShuffleVectorInst>(
RHS)->isConcat()) {
2096// This transform does not have the speculative execution constraint as 2097// below because the shuffle is a concatenation. The new binops are 2098// operating on exactly the same elements as the existing binop. 2099// TODO: We could ease the mask requirement to allow different undef lanes, 2100// but that requires an analysis of the binop-with-undef output value. 2102if (
auto *BO = dyn_cast<BinaryOperator>(NewBO0))
2105if (
auto *BO = dyn_cast<BinaryOperator>(NewBO1))
2112if (
auto *BO = dyn_cast<BinaryOperator>(V))
2116 M, Intrinsic::vector_reverse, V->getType());
2120// NOTE: Reverse shuffles don't require the speculative execution protection 2121// below because they don't affect which lanes take part in the computation. 2125// Op(rev(V1), rev(V2)) -> rev(Op(V1, V2)) 2129return createBinOpReverse(V1, V2);
2131// Op(rev(V1), RHSSplat)) -> rev(Op(V1, RHSSplat)) 2133return createBinOpReverse(V1,
RHS);
2135// Op(LHSSplat, rev(V2)) -> rev(Op(LHSSplat, V2)) 2137return createBinOpReverse(
LHS, V2);
2139// It may not be safe to reorder shuffles and things like div, urem, etc. 2140// because we may trap when executing those ops on unknown vector elements. 2147if (
auto *BO = dyn_cast<BinaryOperator>(XY))
2152// If both arguments of the binary operation are shuffles that use the same 2153// mask and shuffle within a single vector, move the shuffle after the binop. 2156 V1->
getType() == V2->getType() &&
2158// Op(shuffle(V1, Mask), shuffle(V2, Mask)) -> shuffle(Op(V1, V2), Mask) 2159return createBinOpShuffle(V1, V2, Mask);
2162// If both arguments of a commutative binop are select-shuffles that use the 2163// same mask with commuted operands, the shuffles are unnecessary. 2168auto *LShuf = cast<ShuffleVectorInst>(
LHS);
2169auto *RShuf = cast<ShuffleVectorInst>(
RHS);
2170// TODO: Allow shuffles that contain undefs in the mask? 2171// That is legal, but it reduces undef knowledge. 2172// TODO: Allow arbitrary shuffles by shuffling after binop? 2173// That might be legal, but we have to deal with poison. 2174if (LShuf->isSelect() &&
2176 RShuf->isSelect() &&
2179// LHS = shuffle V1, V2, <0, 5, 6, 3> 2180// RHS = shuffle V2, V1, <0, 5, 6, 3> 2181// LHS + RHS --> (V10+V20, V21+V11, V22+V12, V13+V23) --> V1 + V2 2188// If one argument is a shuffle within one vector and the other is a constant, 2189// try moving the shuffle after the binary operation. This canonicalization 2190// intends to move shuffles closer to other shuffles and binops closer to 2191// other binops, so they can be folded. It may also enable demanded elements 2194auto *InstVTy = dyn_cast<FixedVectorType>(Inst.
getType());
2199 cast<FixedVectorType>(V1->
getType())->getNumElements() <=
2200 InstVTy->getNumElements()) {
2202"Shuffle should not change scalar type");
2204// Find constant NewC that has property: 2205// shuffle(NewC, ShMask) = C 2206// If such constant does not exist (example: ShMask=<0,0> and C=<1,2>) 2207// reorder is not possible. A 1-to-1 mapping is not required. Example: 2208// ShMask = <1,1,2,2> and C = <5,5,6,6> --> NewC = <undef,5,6,undef> 2209bool ConstOp1 = isa<Constant>(
RHS);
2211unsigned SrcVecNumElts =
2212 cast<FixedVectorType>(V1->
getType())->getNumElements();
2215bool MayChange =
true;
2216unsigned NumElts = InstVTy->getNumElements();
2217for (
unsignedI = 0;
I < NumElts; ++
I) {
2219if (ShMask[
I] >= 0) {
2220assert(ShMask[
I] < (
int)NumElts &&
"Not expecting narrowing shuffle");
2223// 1. The constant vector contains a constant expression. 2224// 2. The shuffle needs an element of the constant vector that can't 2225// be mapped to a new constant vector. 2226// 3. This is a widening shuffle that copies elements of V1 into the 2227// extended elements (extending with poison is allowed). 2228if (!CElt || (!isa<PoisonValue>(NewCElt) && NewCElt != CElt) ||
2229I >= SrcVecNumElts) {
2233 NewVecC[ShMask[
I]] = CElt;
2235// If this is a widening shuffle, we must be able to extend with poison 2236// elements. If the original binop does not produce a poison in the high 2237// lanes, then this transform is not safe. 2238// Similarly for poison lanes due to the shuffle mask, we can only 2239// transform binops that preserve poison. 2240// TODO: We could shuffle those non-poison constant values into the 2241// result by using a constant vector (rather than an poison vector) 2242// as operand 1 of the new binop, but that might be too aggressive 2243// for target-independent shuffle creation. 2244if (
I >= SrcVecNumElts || ShMask[
I] < 0) {
2249if (!MaybePoison || !isa<PoisonValue>(MaybePoison)) {
2257// It may not be safe to execute a binop on a vector with poison elements 2258// because the entire instruction can be folded to undef or create poison 2259// that did not exist in the original code. 2260// TODO: The shift case should not be necessary. 2264// Op(shuffle(V1, Mask), C) -> shuffle(Op(V1, NewC), Mask) 2265// Op(C, shuffle(V1, Mask)) -> shuffle(Op(NewC, V1), Mask) 2266Value *NewLHS = ConstOp1 ? V1 : NewC;
2267Value *NewRHS = ConstOp1 ? NewC : V1;
2268return createBinOpShuffle(NewLHS, NewRHS, Mask);
2272// Try to reassociate to sink a splat shuffle after a binary operation. 2274// Canonicalize shuffle operand as LHS. 2275if (isa<ShuffleVectorInst>(
RHS))
2289// FIXME: This may not be safe if the analysis allows undef elements. By 2290// moving 'Y' before the splat shuffle, we are implicitly assuming 2291// that it is not undef/poison at the splat index. 2298// X and Y are splatted values, so perform the binary operation on those 2299// values followed by a splat followed by the 2nd binary operation: 2300// bo (splat X), (bo Y, OtherOp) --> bo (splat (bo X, Y)), OtherOp 2306// Intersect FMF on both new binops. Other (poison-generating) flags are 2307// dropped to be safe. 2308if (isa<FPMathOperator>(R)) {
2309 R->copyFastMathFlags(&Inst);
2312if (
auto *NewInstBO = dyn_cast<BinaryOperator>(NewBO))
2313 NewInstBO->copyIRFlags(R);
2320/// Try to narrow the width of a binop if at least 1 operand is an extend of 2321/// of a value. This requires a potentially expensive known bits check to make 2322/// sure the narrow op does not overflow. 2324// We need at least one extended operand. 2327// If this is a sub, we swap the operands since we always want an extension 2328// on the RHS. The LHS can be an extension or a constant. 2337// If both operands are the same extension from the same source type and we 2338// can eliminate at least one (hasOneUse), this might work. 2342 cast<Operator>(Op1)->getOpcode() == CastOpc &&
2343 (Op0->
hasOneUse() || Op1->hasOneUse()))) {
2344// If that did not match, see if we have a suitable constant operand. 2345// Truncating and extending must produce the same constant. 2355// Swap back now that we found our operands. 2359// Both operands have narrow versions. Last step: the math must not overflow 2360// in the narrow width. 2361if (!willNotOverflow(BO.
getOpcode(),
X,
Y, BO, IsSext))
2364// bo (ext X), (ext Y) --> ext (bo X, Y) 2365// bo (ext X), C --> ext (bo X, C') 2367if (
auto *NewBinOp = dyn_cast<BinaryOperator>(NarrowBO)) {
2369 NewBinOp->setHasNoSignedWrap();
2371 NewBinOp->setHasNoUnsignedWrap();
2376/// Determine nowrap flags for (gep (gep p, x), y) to (gep p, (x + y)) 2383/// Thread a GEP operation with constant indices through the constant true/false 2384/// arms of a select. 2387if (!
GEP.hasAllConstantIndices())
2398// gep (select Cond, TrueC, FalseC), IndexC --> select Cond, TrueC', FalseC' 2399// Propagate 'inbounds' and metadata from existing instructions. 2400// Note: using IRBuilder to create the constants for efficiency. 2403Type *Ty =
GEP.getSourceElementType();
2410// gep T, (gep i8, base, C1), (Index + C2) into 2411// gep T, (gep i8, base, C1 + C2 * sizeof(T)), Index 2415if (
GEP.getNumIndices() != 1)
2424Type *PtrTy = Src->getType()->getScalarType();
2425unsigned IndexSizeInBits =
DL.getIndexTypeSizeInBits(PtrTy);
2432if (isa<ScalableVectorType>(
BaseType))
2437 (Src->hasOneUse() &&
GEP.getOperand(1)->hasOneUse())) {
2448// Combine Indices - If the source pointer to this getelementptr instruction 2449// is a getelementptr instruction with matching element type, combine the 2450// indices of the two getelementptr instructions into a single instruction. 2457// For constant GEPs, use a more general offset-based folding approach. 2458Type *PtrTy = Src->getType()->getScalarType();
2459if (
GEP.hasAllConstantIndices() &&
2460 (Src->hasOneUse() || Src->hasAllConstantIndices())) {
2461// Split Src into a variable part and a constant suffix. 2464bool IsFirstType =
true;
2465unsigned NumVarIndices = 0;
2466for (
auto Pair :
enumerate(Src->indices())) {
2467if (!isa<ConstantInt>(Pair.value())) {
2470 NumVarIndices = Pair.index() + 1;
2475// Determine the offset for the constant suffix of Src. 2477if (NumVarIndices != Src->getNumIndices()) {
2478// FIXME: getIndexedOffsetInType() does not handled scalable vectors. 2490// Add the offset for GEP (which is fully constant). 2494// Convert the total offset back into indices. 2497if (!
Offset.isZero() || (!IsFirstType && !ConstIndices[0].isZero()))
2503 Src->getNumIndices() - NumVarIndices));
2506// Even if the total offset is inbounds, we may end up representing it 2507// by first performing a larger negative offset, and then a smaller 2508// positive one. The large negative offset might go out of bounds. Only 2509// preserve inbounds if all signs are the same. 2510if (
Idx.isNonNegative() != ConstIndices[0].isNonNegative())
2512if (!
Idx.isNonNegative())
2521if (Src->getResultElementType() !=
GEP.getSourceElementType())
2526// Find out whether the last index in the source GEP is a sequential idx. 2527bool EndsWithSequential =
false;
2530 EndsWithSequential =
I.isSequential();
2532// Can we combine the two pointer arithmetics offsets? 2533if (EndsWithSequential) {
2534// Replace: gep (gep %P, long B), long A, ... 2535// With: T = long A+B; gep %P, T, ... 2536Value *SO1 = Src->getOperand(Src->getNumOperands()-1);
2539// If they aren't the same type, then the input hasn't been processed 2540// by the loop above yet (which canonicalizes sequential index types to 2541// intptr_t). Just avoid transforming this until the input has been 2548// Only do the combine when we are sure the cost after the 2549// merge is never more than that before the merge. 2553 Indices.
append(Src->op_begin()+1, Src->op_end()-1);
2556 }
elseif (isa<Constant>(*
GEP.idx_begin()) &&
2557 cast<Constant>(*
GEP.idx_begin())->isNullValue() &&
2558 Src->getNumOperands() != 1) {
2559// Otherwise we can do the fold if the first index of the GEP is a zero 2560 Indices.
append(Src->op_begin()+1, Src->op_end());
2564if (!Indices.
empty())
2567 Src->getSourceElementType(), Src->getOperand(0), Indices,
"",
2575bool &DoesConsume,
unsignedDepth) {
2576staticValue *
const NonNull =
reinterpret_cast<Value *
>(uintptr_t(1));
2585// Constants can be considered to be not'ed values. 2592// The rest of the cases require that we invert all uses so don't bother 2593// doing the analysis if we know we can't use the result. 2594if (!WillInvertAllUses)
2597// Compares can be inverted if all of their uses are being modified to use 2599if (
auto *
I = dyn_cast<CmpInst>(V)) {
2606// If `V` is of the form `A + B` then `-1 - V` can be folded into 2607// `(-1 - B) - A` if we are willing to invert all of the uses. 2618// If `V` is of the form `A ^ ~B` then `~(A ^ ~B)` can be folded 2619// into `A ^ B` if we are willing to invert all of the uses. 2630// If `V` is of the form `B - A` then `-1 - V` can be folded into 2631// `A + (-1 - B)` if we are willing to invert all of the uses. 2639// If `V` is of the form `(~A) s>> B` then `~((~A) s>> B)` can be folded 2640// into `A s>> B` if we are willing to invert all of the uses. 2649// LogicOps are special in that we canonicalize them at the cost of an 2653// Selects/min/max with invertible operands are freely invertible 2655bool LocalDoesConsume = DoesConsume;
2657 LocalDoesConsume,
Depth))
2660 LocalDoesConsume,
Depth)) {
2661 DoesConsume = LocalDoesConsume;
2666"Unable to build inverted value for known freely invertable op");
2667if (
auto *
II = dyn_cast<IntrinsicInst>(V))
2676if (
PHINode *PN = dyn_cast<PHINode>(V)) {
2677bool LocalDoesConsume = DoesConsume;
2679for (
Use &U : PN->operands()) {
2680BasicBlock *IncomingBlock = PN->getIncomingBlock(U);
2682 U.get(),
/*WillInvertAllUses=*/false,
2684if (NewIncomingVal ==
nullptr)
2686// Make sure that we can safely erase the original PHI node. 2687if (NewIncomingVal == V)
2690 IncomingValues.
emplace_back(NewIncomingVal, IncomingBlock);
2693 DoesConsume = LocalDoesConsume;
2699for (
auto [Val, Pred] : IncomingValues)
2721// (~(A | B)) -> (~A & ~B) 2722// (~(A & B)) -> (~A | ~B) 2726bool LocalDoesConsume = DoesConsume;
2728 LocalDoesConsume,
Depth))
2731 LocalDoesConsume,
Depth)) {
2733 LocalDoesConsume,
Depth);
2734 DoesConsume = LocalDoesConsume;
2744return TryInvertAndOrUsingDeMorgan(Instruction::And,
/*IsLogical=*/false,
A,
2748return TryInvertAndOrUsingDeMorgan(Instruction::Or,
/*IsLogical=*/false,
A,
2752return TryInvertAndOrUsingDeMorgan(Instruction::And,
/*IsLogical=*/true,
A,
2756return TryInvertAndOrUsingDeMorgan(Instruction::Or,
/*IsLogical=*/true,
A,
2762/// Return true if we should canonicalize the gep to an i8 ptradd. 2765Type *GEPEltType =
GEP.getSourceElementType();
2769// Canonicalize scalable GEPs to an explicit offset using the llvm.vscale 2770// intrinsic. This has better support in BasicAA. 2774// gep i32 p, mul(O, C) -> gep i8, p, mul(O, C*4) to fold the two multiplies 2776if (
GEP.getNumIndices() == 1 &&
2782// gep (gep %p, C1), %x, C2 is expanded so the two constants can 2783// possibly be merged together. 2784auto PtrOpGep = dyn_cast<GEPOperator>(PtrOp);
2785return PtrOpGep && PtrOpGep->hasAllConstantIndices() &&
2788 return match(V, m_APInt(C)) && !C->isZero();
2794auto *Op1 = dyn_cast<GetElementPtrInst>(PN->
getOperand(0));
2798// Don't fold a GEP into itself through a PHI node. This can only happen 2799// through the back-edge of a loop. Folding a GEP into itself means that 2800// the value of the previous iteration needs to be stored in the meantime, 2801// thus requiring an additional register variable to be live, but not 2802// actually achieving anything (the GEP still needs to be executed once per 2811auto *Op2 = dyn_cast<GetElementPtrInst>(*
I);
2812if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands() ||
2813 Op1->getSourceElementType() != Op2->getSourceElementType())
2816// As for Op1 above, don't try to fold a GEP into itself. 2820// Keep track of the type as we walk the GEP. 2821Type *CurTy =
nullptr;
2823for (
unsigned J = 0,
F = Op1->getNumOperands(); J !=
F; ++J) {
2824if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType())
2827if (Op1->getOperand(J) != Op2->getOperand(J)) {
2829// We have not seen any differences yet in the GEPs feeding the 2830// PHI yet, so we record this one if it is allowed to be a 2833// The first two arguments can vary for any GEP, the rest have to be 2834// static for struct slots 2836assert(CurTy &&
"No current type?");
2843// The GEP is different by more than one input. While this could be 2844// extended to support GEPs that vary by more than one variable it 2845// doesn't make sense since it greatly increases the complexity and 2846// would result in an R+R+R addressing mode which no backend 2847// directly supports and would need to be broken into several 2848// simpler instructions anyway. 2853// Sink down a layer of the type for the next iteration. 2856 CurTy = Op1->getSourceElementType();
2864 NW &= Op2->getNoWrapFlags();
2867// If not all GEPs are identical we'll have to create a new PHI node. 2868// Check that the old PHI node has only one use so that it will get 2873auto *NewGEP = cast<GetElementPtrInst>(Op1->clone());
2874 NewGEP->setNoWrapFlags(NW);
2877// All the GEPs feeding the PHI are identical. Clone one down into our 2878// BB so that it can be merged with the current GEP. 2880// All the GEPs feeding the PHI differ at a single offset. Clone a GEP 2881// into the current block so it can be merged, and create a new PHI to 2887 NewPN = Builder.
CreatePHI(Op1->getOperand(DI)->getType(),
2892 NewPN->
addIncoming(cast<GEPOperator>(
I)->getOperand(DI),
2895 NewGEP->setOperand(DI, NewPN);
2898 NewGEP->insertBefore(*
GEP.getParent(),
GEP.getParent()->getFirstInsertionPt());
2906Type *GEPEltType =
GEP.getSourceElementType();
2912// For vector geps, use the generic demanded vector support. 2913// Skip if GEP return type is scalable. The number of elements is unknown at 2915if (
auto *GEPFVTy = dyn_cast<FixedVectorType>(GEPType)) {
2916auto VWidth = GEPFVTy->getNumElements();
2917APInt PoisonElts(VWidth, 0);
2926// TODO: 1) Scalarize splat operands, 2) scalarize entire instruction if 2927// possible (decide on canonical form for pointer broadcast), 3) exploit 2928// undef elements to decrease demanded bits 2931// Eliminate unneeded casts for indices, and replace indices which displace 2932// by multiples of a zero size type with zero. 2933bool MadeChange =
false;
2935// Index width may not be the same width as pointer width. 2936// Data layout chooses the right type based on supported integer types. 2937Type *NewScalarIndexTy =
2943// Skip indices into struct types. 2947Type *IndexTy = (*I)->getType();
2951 cast<VectorType>(IndexTy)->getElementCount())
2954// If the element type has zero size then any index over it is equivalent 2955// to an index of zero, so replace it with zero if it is not zero already. 2963if (IndexTy != NewIndexType) {
2964// If we are using a wider index than needed for this platform, shrink 2965// it to what we need. If narrower, sign-extend it to what we need. 2966// This explicit cast can make subsequent optimizations more obvious. 2974// Canonicalize constant GEPs to i8 type. 2980GEP.getNoWrapFlags()));
2990// Check to see if the inputs to the PHI node are getelementptr instructions. 2991if (
auto *PN = dyn_cast<PHINode>(PtrOp)) {
2996if (
auto *Src = dyn_cast<GEPOperator>(PtrOp))
3000if (
GEP.getNumIndices() == 1) {
3001unsigned AS =
GEP.getPointerAddressSpace();
3002if (
GEP.getOperand(1)->getType()->getScalarSizeInBits() ==
3006if (TyAllocSize == 1) {
3007// Canonicalize (gep i8* X, (ptrtoint Y)-(ptrtoint X)) to (bitcast Y), 3008// but only if the result pointer is only used as if it were an integer, 3009// or both point to the same underlying object (otherwise provenance is 3010// not necessarily retained). 3015 GEPType ==
Y->getType()) {
3016bool HasSameUnderlyingObject =
3019GEP.replaceUsesWithIf(
Y, [&](
Use &U) {
3020bool ShouldReplace = HasSameUnderlyingObject ||
3021 isa<ICmpInst>(U.getUser()) ||
3022 isa<PtrToIntInst>(U.getUser());
3023 Changed |= ShouldReplace;
3024return ShouldReplace;
3026return Changed ? &
GEP :
nullptr;
3028 }
elseif (
auto *ExactIns =
3029 dyn_cast<PossiblyExactOperator>(
GEP.getOperand(1))) {
3030// Canonicalize (gep T* X, V / sizeof(T)) to (gep i8* X, V) 3032if (ExactIns->isExact()) {
3040GEP.getPointerOperand(), V,
3041GEP.getNoWrapFlags());
3044if (ExactIns->isExact() && ExactIns->hasOneUse()) {
3045// Try to canonicalize non-i8 element type to i8 if the index is an 3046// exact instruction. If the index is an exact instruction (div/shr) 3047// with a constant RHS, we can fold the non-i8 element scale into the 3048// div/shr (similiar to the mul case, just inverted). 3050 std::optional<APInt> NewC;
3065// For sdiv we need to make sure we arent creating INT_MIN / -1. 3070if (NewC.has_value()) {
3073 ConstantInt::get(V->getType(), *NewC));
3074 cast<BinaryOperator>(NewOp)->setIsExact();
3076GEP.getPointerOperand(), NewOp,
3077GEP.getNoWrapFlags());
3083// We do not handle pointer-vector geps here. 3087if (
GEP.getNumIndices() == 1) {
3088// We can only preserve inbounds if the original gep is inbounds, the add 3089// is nsw, and the add operands are non-negative. 3090auto CanPreserveInBounds = [&](
bool AddIsNSW,
Value *Idx1,
Value *Idx2) {
3096// Try to replace ADD + GEP with GEP + GEP. 3100// %idx = add i64 %idx1, %idx2 3101// %gep = getelementptr i32, ptr %ptr, i64 %idx 3103// %newptr = getelementptr i32, ptr %ptr, i64 %idx1 3104// %newgep = getelementptr i32, ptr %newptr, i64 %idx2 3105bool IsInBounds = CanPreserveInBounds(
3106 cast<OverflowingBinaryOperator>(
GEP.getOperand(1))->hasNoSignedWrap(),
3110 Idx1,
"", IsInBounds);
3118// %add = add nsw i32 %idx1, idx2 3119// %sidx = sext i32 %add to i64 3120// %gep = getelementptr i32, ptr %ptr, i64 %sidx 3122// %newptr = getelementptr i32, ptr %ptr, i32 %idx1 3123// %newgep = getelementptr i32, ptr %newptr, i32 idx2 3124bool IsInBounds = CanPreserveInBounds(
3125/*IsNSW=*/true, Idx1,
C);
3127GEP.getSourceElementType(),
GEP.getPointerOperand(),
3138if (!
GEP.isInBounds()) {
3141APInt BasePtrOffset(IdxWidth, 0);
3142Value *UnderlyingPtrOp =
3145bool CanBeNull, CanBeFreed;
3147DL, CanBeNull, CanBeFreed);
3148if (!CanBeNull && !CanBeFreed && DerefBytes != 0) {
3149if (
GEP.accumulateConstantOffset(
DL, BasePtrOffset) &&
3151APInt AllocSize(IdxWidth, DerefBytes);
3152if (BasePtrOffset.
ule(AllocSize)) {
3154GEP.getSourceElementType(), PtrOp, Indices,
GEP.getName());
3160// nusw + nneg -> nuw 3161if (
GEP.hasNoUnsignedSignedWrap() && !
GEP.hasNoUnsignedWrap() &&
3163 return isKnownNonNegative(Idx, SQ.getWithInstruction(&GEP));
3177if (isa<ConstantPointerNull>(V))
3179if (
auto *LI = dyn_cast<LoadInst>(V))
3180return isa<GlobalVariable>(LI->getPointerOperand());
3181// Two distinct allocations will never be equal. 3185/// Given a call CB which uses an address UsedV, return true if we can prove the 3186/// call's only possible effect is storing to V. 3190// TODO: add recursion if returned attribute is present 3194// TODO: remove implementation restriction 3200// If the only possible side effect of the call is writing to the alloca, 3201// and the result isn't used, we can safely remove any reads implied by the 3202// call including those which might read the alloca itself. 3204return Dest && Dest->Ptr == UsedV;
3218switch (
I->getOpcode()) {
3220// Give up the moment we see something we can't handle. 3223case Instruction::AddrSpaceCast:
3224case Instruction::BitCast:
3225case Instruction::GetElementPtr:
3230case Instruction::ICmp: {
3232// We can fold eq/ne comparisons with null to false/true, respectively. 3233// We also fold comparisons in some conditions provided the alloc has 3234// not escaped (see isNeverEqualToUnescapedAlloc). 3237unsigned OtherIndex = (ICI->
getOperand(0) == PI) ? 1 : 0;
3241// Do not fold compares to aligned_alloc calls, as they may have to 3242// return null in case the required alignment cannot be satisfied, 3243// unless we can prove that both alignment and size are valid. 3244auto AlignmentAndSizeKnownValid = [](
CallBase *CB) {
3245// Check if alignment and size of a call to aligned_alloc is valid, 3246// that is alignment is a power-of-2 and the size is a multiple of the 3248constAPInt *Alignment;
3254auto *CB = dyn_cast<CallBase>(AI);
3256if (CB && TLI.
getLibFunc(*CB->getCalledFunction(), TheLibFunc) &&
3257 TLI.
has(TheLibFunc) && TheLibFunc == LibFunc_aligned_alloc &&
3258 !AlignmentAndSizeKnownValid(CB))
3264case Instruction::Call:
3265// Ignore no-op and store intrinsics. 3267switch (
II->getIntrinsicID()) {
3271case Intrinsic::memmove:
3272case Intrinsic::memcpy:
3273case Intrinsic::memset: {
3275if (
MI->isVolatile() ||
MI->getRawDest() != PI)
3279case Intrinsic::assume:
3280case Intrinsic::invariant_start:
3281case Intrinsic::invariant_end:
3282case Intrinsic::lifetime_start:
3283case Intrinsic::lifetime_end:
3284case Intrinsic::objectsize:
3287case Intrinsic::launder_invariant_group:
3288case Intrinsic::strip_invariant_group:
3317case Instruction::Store: {
3319if (SI->isVolatile() || SI->getPointerOperand() != PI)
3327 }
while (!Worklist.
empty());
3334// If we have a malloc call which is only used in any amount of comparisons to 3335// null and free calls, delete the calls and replace the comparisons with true 3336// or false as appropriate. 3338// This is based on the principle that we can substitute our own allocation 3339// function (which will never return null) rather than knowledge of the 3340// specific function being called. In some sense this can change the permitted 3341// outputs of a program (when we convert a malloc to an alloca, the fact that 3342// the allocation is now on the stack is potentially visible, for example), 3343// but we believe in a permissible manner. 3346// If we are removing an alloca with a dbg.declare, insert dbg.value calls 3347// before each store. 3350 std::unique_ptr<DIBuilder> DIB;
3351if (isa<AllocaInst>(
MI)) {
3353 DIB.reset(
newDIBuilder(*
MI.getModule(),
/*AllowUnresolved=*/false));
3357for (
unsigned i = 0, e =
Users.size(); i != e; ++i) {
3358// Lowering all @llvm.objectsize calls first because they may 3359// use a bitcast/GEP of the alloca we are removing. 3366if (
II->getIntrinsicID() == Intrinsic::objectsize) {
3369II,
DL, &
TLI,
AA,
/*MustSucceed=*/true, &InsertedInstructions);
3374Users[i] =
nullptr;
// Skip examining in the next loop. 3378for (
unsigned i = 0, e =
Users.size(); i != e; ++i) {
3387C->isFalseWhenEqual()));
3388 }
elseif (
auto *SI = dyn_cast<StoreInst>(
I)) {
3389for (
auto *DVI : DVIs)
3390if (DVI->isAddressOfVariable())
3392for (
auto *DVR : DVRs)
3393if (DVR->isAddressOfVariable())
3396// Casts, GEP, or anything else: we're about to delete this instruction, 3397// so it can not have any valid uses. 3404// Replace invoke with a NOP intrinsic to maintain the original CFG 3411// Remove debug intrinsics which describe the value contained within the 3412// alloca. In addition to removing dbg.{declare,addr} which simply point to 3413// the alloca, remove dbg.value(<alloca>, ..., DW_OP_deref)'s as well, e.g.: 3416// define void @foo(i32 %0) { 3417// %a = alloca i32 ; Deleted. 3418// store i32 %0, i32* %a 3419// dbg.value(i32 %0, "arg0") ; Not deleted. 3420// dbg.value(i32* %a, "arg0", DW_OP_deref) ; Deleted. 3421// call void @trivially_inlinable_no_op(i32* %a) 3426// This may not be required if we stop describing the contents of allocas 3427// using dbg.value(<alloca>, ..., DW_OP_deref), but we currently do this in 3428// the LowerDbgDeclare utility. 3430// If there is a dead store to `%a` in @trivially_inlinable_no_op, the 3431// "arg0" dbg.value may be stale after the call. However, failing to remove 3432// the DW_OP_deref dbg.value causes large gaps in location coverage. 3434// FIXME: the Assignment Tracking project has now likely made this 3435// redundant (and it's sometimes harmful). 3436for (
auto *DVI : DVIs)
3437if (DVI->isAddressOfVariable() || DVI->getExpression()->startsWithDeref())
3438 DVI->eraseFromParent();
3439for (
auto *DVR : DVRs)
3440if (DVR->isAddressOfVariable() || DVR->getExpression()->startsWithDeref())
3441 DVR->eraseFromParent();
3448/// Move the call to free before a NULL test. 3450/// Check if this free is accessed after its argument has been test 3451/// against NULL (property 0). 3452/// If yes, it is legal to move this call in its predecessor block. 3454/// The move is performed only if the block containing the call to free 3455/// will be removed, i.e.: 3456/// 1. it has only one predecessor P, and P has two successors 3457/// 2. it contains the call, noops, and an unconditional branch 3458/// 3. its successor is the same as its predecessor's successor 3460/// The profitability is out-of concern here and this function should 3461/// be called only if the caller knows this transformation would be 3462/// profitable (e.g., for code size). 3469// Validate part of constraint #1: Only one predecessor 3470// FIXME: We can extend the number of predecessor, but in that case, we 3471// would duplicate the call to free in each predecessor and it may 3472// not be profitable even for code size. 3476// Validate constraint #2: Does this block contains only the call to 3477// free, noops, and an unconditional branch? 3483// If there are only 2 instructions in the block, at this point, 3484// this is the call to free and unconditional. 3485// If there are more than 2 instructions, check that they are noops 3486// i.e., they won't hurt the performance of the generated code. 3487if (FreeInstrBB->
size() != 2) {
3489if (&Inst == &FI || &Inst == FreeInstrBBTerminator)
3491auto *Cast = dyn_cast<CastInst>(&Inst);
3492if (!Cast || !Cast->isNoopCast(
DL))
3496// Validate the rest of constraint #1 by matching on the pred branch. 3509// Validate constraint #3: Ensure the null case just falls through. 3513"Broken CFG: missing edge from predecessor to successor");
3515// At this point, we know that everything in FreeInstrBB can be moved 3518if (&Instr == FreeInstrBBTerminator)
3523"Only the branch instruction should remain");
3525// Now that we've moved the call to free before the NULL check, we have to 3526// remove any attributes on its parameter that imply it's non-null, because 3527// those attributes might have only been valid because of the NULL check, and 3528// we can get miscompiles if we keep them. This is conservative if non-null is 3529// also implied by something other than the NULL check, but it's guaranteed to 3530// be correct, and the conservativeness won't matter in practice, since the 3531// attributes are irrelevant for the call to free itself and the pointer 3532// shouldn't be used after the call. 3534 Attrs = Attrs.removeParamAttribute(FI.
getContext(), 0, Attribute::NonNull);
3535Attribute Dereferenceable = Attrs.getParamAttr(0, Attribute::Dereferenceable);
3536if (Dereferenceable.
isValid()) {
3538 Attrs = Attrs.removeParamAttribute(FI.
getContext(), 0,
3539 Attribute::Dereferenceable);
3540 Attrs = Attrs.addDereferenceableOrNullParamAttr(FI.
getContext(), 0, Bytes);
3548// free undef -> unreachable. 3549if (isa<UndefValue>(
Op)) {
3550// Leave a marker since we can't modify the CFG here. 3555// If we have 'free null' delete the instruction. This can happen in stl code 3556// when lots of inlining happens. 3557if (isa<ConstantPointerNull>(
Op))
3560// If we had free(realloc(...)) with no intervening uses, then eliminate the 3561// realloc() entirely. 3567// If we optimize for code size, try to move the call to free before the null 3568// test so that simplify cfg can remove the empty block and dead code 3569// elimination the branch. I.e., helps to turn something like: 3570// if (foo) free(foo); 3574// Note that we can only do this for 'free' and not for any flavor of 3575// 'operator delete'; there is no 'operator delete' symbol for which we are 3576// permitted to invent a call, even if we're passing in a null pointer. 3593FPClassTest ReturnClass =
F->getAttributes().getRetNoFPClass();
3606// WARNING: keep in sync with SimplifyCFGOpt::simplifyUnreachable()! 3608// Try to remove the previous instruction if it must lead to unreachable. 3609// This includes instructions like stores and "llvm.assume" that may not get 3610// removed by simple dead code elimination. 3612while (
Instruction *Prev =
I.getPrevNonDebugInstruction()) {
3613// While we theoretically can erase EH, that would result in a block that 3614// used to start with an EH no longer starting with EH, which is invalid. 3615// To make it valid, we'd need to fixup predecessors to no longer refer to 3616// this block, but that changes CFG, which is not allowed in InstCombine. 3618break;
// Can not drop any more instructions. We're done here. 3621break;
// Can not drop any more instructions. We're done here. 3622// Otherwise, this instruction can be freely erased, 3623// even if it is not side-effect free. 3625// A value may still have uses before we process it here (for example, in 3626// another unreachable block), so convert those to poison. 3642// If this store is the second-to-last instruction in the basic block 3643// (excluding debug info and bitcasts of pointers) and if the block ends with 3644// an unconditional branch, try to move the store to the successor block. 3648return BBI->isDebugOrPseudoInst() ||
3649 (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy());
3654if (BBI != FirstInstr)
3656 }
while (BBI != FirstInstr && IsNoopInstrForStoreMerging(BBI));
3658return dyn_cast<StoreInst>(BBI);
3670if (!
DeadEdges.insert({From, To}).second)
3673// Replace phi node operands in successor with poison. 3675for (
Use &U : PN.incoming_values())
3676if (PN.getIncomingBlock(U) ==
From && !isa<PoisonValue>(U)) {
3685// Under the assumption that I is unreachable, remove it and following 3686// instructions. Changes are reported directly to MadeIRChange. 3692 std::next(
I->getReverseIterator())))) {
3693if (!Inst.use_empty() && !Inst.getType()->isTokenTy()) {
3697if (Inst.isEHPad() || Inst.getType()->isTokenTy())
3699// RemoveDIs: erase debug-info on this instruction manually. 3700 Inst.dropDbgRecords();
3708for (
Value *V : Changed)
3712// Handle potentially dead successors. 3734// The live successor isn't dead. 3735if (Succ == LiveSucc)
3748// Change br (not X), label True, label False to: br X, label False, True 3752// Swap Destinations and condition... 3759// Canonicalize logical-and-with-invert as logical-or-with-invert. 3760// This is done by inverting the condition and swapping successors: 3761// br (X && !Y), T, F --> br !(X && !Y), F, T --> br (!X || Y), F, T 3763if (isa<SelectInst>(
Cond) &&
3774// If the condition is irrelevant, remove the use so that other 3775// transforms on the condition become more effective. 3779// Canonicalize, for example, fcmp_one -> fcmp_oeq. 3783// Swap destinations and condition. 3784auto *Cmp = cast<CmpInst>(
Cond);
3793if (isa<UndefValue>(
Cond)) {
3797if (
auto *CI = dyn_cast<ConstantInt>(
Cond)) {
3803// Replace all dominated uses of the condition with true/false 3804// Ignore constant expressions to avoid iterating over uses on other 3826// Replaces (switch (select cond, X, C)/(select cond, C, X)) with (switch X) if 3827// we can prove that both (switch C) and (switch X) go to the default when cond 3832unsigned CstOpIdx = IsTrueArm ? 1 : 2;
3833auto *
C = dyn_cast<ConstantInt>(
Select->getOperand(CstOpIdx));
3837BasicBlock *CstBB = SI.findCaseValue(
C)->getCaseSuccessor();
3838if (CstBB != SI.getDefaultDest())
3849// See whether we can replace the select with X 3851for (
auto Case : SI.cases())
3852if (!CR.
contains(Case.getCaseValue()->getValue()))
3863// Change 'switch (X+4) case 1:' into 'switch (X) case -3'. 3864for (
auto Case : SI.cases()) {
3866assert(isa<ConstantInt>(NewCase) &&
3867"Result of expression should be constant");
3868 Case.setValue(cast<ConstantInt>(NewCase));
3875// Change 'switch (1-X) case 1:' into 'switch (X) case 0'. 3876for (
auto Case : SI.cases()) {
3878assert(isa<ConstantInt>(NewCase) &&
3879"Result of expression should be constant");
3880 Case.setValue(cast<ConstantInt>(NewCase));
3888all_of(SI.cases(), [&](
constauto &Case) {
3889 return Case.getCaseValue()->getValue().countr_zero() >= ShiftAmt;
3891// Change 'switch (X << 2) case 4:' into 'switch (X) case 1:'. 3895Value *NewCond = Op0;
3897// If the shift may wrap, we need to mask off the shifted bits. 3902for (
auto Case : SI.cases()) {
3903constAPInt &CaseVal = Case.getCaseValue()->getValue();
3905 : CaseVal.
lshr(ShiftAmt);
3906 Case.setValue(ConstantInt::get(SI.getContext(), ShiftedCase));
3912// Fold switch(zext/sext(X)) into switch(X) if possible. 3914bool IsZExt = isa<ZExtInst>(
Cond);
3918if (
all_of(SI.cases(), [&](
constauto &Case) {
3919 const APInt &CaseVal = Case.getCaseValue()->getValue();
3920 return IsZExt ? CaseVal.isIntN(NewWidth)
3921 : CaseVal.isSignedIntN(NewWidth);
3923for (
auto &Case : SI.cases()) {
3924APInt TruncatedCase = Case.getCaseValue()->getValue().
trunc(NewWidth);
3925 Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));
3931// Fold switch(select cond, X, Y) into switch(X/Y) if possible 3932if (
auto *
Select = dyn_cast<SelectInst>(
Cond)) {
3945// Compute the number of leading bits we can ignore. 3946// TODO: A better way to determine this would use ComputeNumSignBits(). 3947for (
constauto &
C : SI.cases()) {
3949 std::min(LeadingKnownZeros,
C.getCaseValue()->getValue().countl_zero());
3951 std::min(LeadingKnownOnes,
C.getCaseValue()->getValue().countl_one());
3954unsigned NewWidth = Known.
getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes);
3956// Shrink the condition operand if the new type is smaller than the old type. 3957// But do not shrink to a non-standard type, because backend can't generate 3958// good code for that yet. 3959// TODO: We can make it aggressive again after fixing PR39569. 3960if (NewWidth > 0 && NewWidth < Known.
getBitWidth() &&
3961 shouldChangeType(Known.
getBitWidth(), NewWidth)) {
3966for (
auto Case : SI.cases()) {
3967APInt TruncatedCase = Case.getCaseValue()->getValue().
trunc(NewWidth);
3968 Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));
3973if (isa<UndefValue>(
Cond)) {
3977if (
auto *CI = dyn_cast<ConstantInt>(
Cond)) {
3979 SI.findCaseValue(CI)->getCaseSuccessor());
3995if (*EV.
idx_begin() == 0 && (OvID == Intrinsic::smul_with_overflow ||
3996 OvID == Intrinsic::umul_with_overflow)) {
3997// extractvalue (any_mul_with_overflow X, -1), 0 --> -X 4000// extractvalue (any_mul_with_overflow X, 2^n), 0 --> X << n 4001if (
C->isPowerOf2()) {
4002return BinaryOperator::CreateShl(
4004 ConstantInt::get(WO->getLHS()->getType(),
C->logBase2()));
4009// We're extracting from an overflow intrinsic. See if we're the only user. 4010// That allows us to simplify multiple result intrinsics to simpler things 4011// that just get one value. 4012if (!WO->hasOneUse())
4015// Check if we're grabbing only the result of a 'with overflow' intrinsic 4016// and replace it with a traditional binary instruction. 4020// Replace the old instruction's uses with poison. 4026assert(*EV.
idx_begin() == 1 &&
"Unexpected extract index for overflow inst");
4028// (usub LHS, RHS) overflows when LHS is unsigned-less-than RHS. 4029if (OvID == Intrinsic::usub_with_overflow)
4032// smul with i1 types overflows when both sides are set: -1 * -1 == +1, but 4033// +1 is not possible because we assume signed values. 4034if (OvID == Intrinsic::smul_with_overflow &&
4035 WO->getLHS()->getType()->isIntOrIntVectorTy(1))
4036return BinaryOperator::CreateAnd(WO->getLHS(), WO->getRHS());
4038// extractvalue (umul_with_overflow X, X), 1 -> X u> 2^(N/2)-1 4039if (OvID == Intrinsic::umul_with_overflow && WO->getLHS() == WO->getRHS()) {
4040unsignedBitWidth = WO->getLHS()->getType()->getScalarSizeInBits();
4041// Only handle even bitwidths for performance reasons. 4045 ConstantInt::get(WO->getLHS()->getType(),
4049// If only the overflow result is used, and the right hand side is a 4050// constant (or constant splat), we can remove the intrinsic by directly 4051// checking for overflow. 4053// Compute the no-wrap range for LHS given RHS=C, then construct an 4054// equivalent icmp, potentially using an offset. 4056 WO->getBinaryOp(), *
C, WO->getNoWrapKind());
4061auto *OpTy = WO->getRHS()->getType();
4062auto *NewLHS = WO->getLHS();
4066 ConstantInt::get(OpTy, NewRHSC));
4083// We're extracting from an insertvalue instruction, compare the indices 4084constunsigned *exti, *exte, *insi, *inse;
4086 exte = EV.
idx_end(), inse =
IV->idx_end();
4087 exti != exte && insi != inse;
4090// The insert and extract both reference distinctly different elements. 4091// This means the extract is not influenced by the insert, and we can 4092// replace the aggregate operand of the extract with the aggregate 4093// operand of the insert. i.e., replace 4094// %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1 4095// %E = extractvalue { i32, { i32 } } %I, 0 4097// %E = extractvalue { i32, { i32 } } %A, 0 4101if (exti == exte && insi == inse)
4102// Both iterators are at the end: Index lists are identical. Replace 4103// %B = insertvalue { i32, { i32 } } %A, i32 42, 1, 0 4104// %C = extractvalue { i32, { i32 } } %B, 1, 0 4108// The extract list is a prefix of the insert list. i.e. replace 4109// %I = insertvalue { i32, { i32 } } %A, i32 42, 1, 0 4110// %E = extractvalue { i32, { i32 } } %I, 1 4112// %X = extractvalue { i32, { i32 } } %A, 1 4113// %E = insertvalue { i32 } %X, i32 42, 0 4114// by switching the order of the insert and extract (though the 4115// insertvalue should be left in, since it may have other uses). 4122// The insert list is a prefix of the extract list 4123// We can simply remove the common indices from the extract and make it 4124// operate on the inserted value instead of the insertvalue result. 4126// %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1 4127// %E = extractvalue { i32, { i32 } } %I, 1, 0 4129// %E extractvalue { i32 } { i32 42 }, 0 4134if (
Instruction *R = foldExtractOfOverflowIntrinsic(EV))
4137if (
LoadInst *L = dyn_cast<LoadInst>(Agg)) {
4138// Bail out if the aggregate contains scalable vector type 4139if (
auto *STy = dyn_cast<StructType>(Agg->
getType());
4140 STy && STy->isScalableTy())
4143// If the (non-volatile) load only has one use, we can rewrite this to a 4144// load from a GEP. This reduces the size of the load. If a load is used 4145// only by extractvalue instructions then this either must have been 4146// optimized before, or it is a struct with padding, in which case we 4147// don't want to do the transformation as it loses padding knowledge. 4148if (L->isSimple() && L->hasOneUse()) {
4149// extractvalue has integer indices, getelementptr has Value*s. Convert. 4151// Prefix an i32 0 since we need the first element. 4156// We need to insert these at the location of the old load, not at that of 4160 L->getPointerOperand(), Indices);
4162// Whatever aliasing information we had for the orignal load must also 4163// hold for the smaller load, so propagate the annotations. 4165// Returning the load directly will cause the main loop to insert it in 4166// the wrong spot, so use replaceInstUsesWith(). 4171if (
auto *PN = dyn_cast<PHINode>(Agg))
4175// Canonicalize extract (select Cond, TV, FV) 4176// -> select cond, (extract TV), (extract FV) 4177if (
auto *SI = dyn_cast<SelectInst>(Agg))
4181// We could simplify extracts from other values. Note that nested extracts may 4182// already be simplified implicitly by the above: extract (extract (insert) ) 4183// will be translated into extract ( insert ( extract ) ) first and then just 4184// the value inserted, if appropriate. Similarly for extracts from single-use 4185// loads: extract (extract (load)) will be translated to extract (load (gep)) 4186// and if again single-use then via load (gep (gep)) to load (gep). 4187// However, double extracts from e.g. function arguments or return values 4188// aren't handled yet. 4192/// Return 'true' if the given typeinfo will match anything. 4194switch (Personality) {
4198// The GCC C EH and Rust personality only exists to support cleanups, so 4199// it's not clear what the semantics of catch clauses are. 4204// While __gnat_all_others_value will match any Ada exception, it doesn't 4205// match foreign exceptions (or didn't, before gcc-4.7). 4224 cast<ArrayType>(
LHS->
getType())->getNumElements()
4226 cast<ArrayType>(
RHS->
getType())->getNumElements();
4230// The logic here should be correct for any real-world personality function. 4231// However if that turns out not to be true, the offending logic can always 4232// be conditioned on the personality function, like the catch-all logic is. 4236// Simplify the list of clauses, eg by removing repeated catch clauses 4237// (these are often created by inlining). 4238bool MakeNewInstruction =
false;
// If true, recreate using the following: 4240bool CleanupFlag = LI.
isCleanup();
// - The new instruction is a cleanup. 4244bool isLastClause = i + 1 == e;
4250// If we already saw this clause, there is no point in having a second 4252if (AlreadyCaught.
insert(TypeInfo).second) {
4253// This catch clause was not already seen. 4256// Repeated catch clause - drop the redundant copy. 4257 MakeNewInstruction =
true;
4260// If this is a catch-all then there is no point in keeping any following 4261// clauses or marking the landingpad as having a cleanup. 4264 MakeNewInstruction =
true;
4269// A filter clause. If any of the filter elements were already caught 4270// then they can be dropped from the filter. It is tempting to try to 4271// exploit the filter further by saying that any typeinfo that does not 4272// occur in the filter can't be caught later (and thus can be dropped). 4273// However this would be wrong, since typeinfos can match without being 4274// equal (for example if one represents a C++ class, and the other some 4275// class derived from it). 4281// An empty filter catches everything, so there is no point in keeping any 4282// following clauses or marking the landingpad as having a cleanup. By 4283// dealing with this case here the following code is made a bit simpler. 4287 MakeNewInstruction =
true;
4292bool MakeNewFilter =
false;
// If true, make a new filter. 4294if (isa<ConstantAggregateZero>(FilterClause)) {
4295// Not an empty filter - it contains at least one null typeinfo. 4296assert(NumTypeInfos > 0 &&
"Should have handled empty filter already!");
4299// If this typeinfo is a catch-all then the filter can never match. 4301// Throw the filter away. 4302 MakeNewInstruction =
true;
4306// There is no point in having multiple copies of this typeinfo, so 4307// discard all but the first copy if there is more than one. 4309if (NumTypeInfos > 1)
4310 MakeNewFilter =
true;
4314 NewFilterElts.
reserve(NumTypeInfos);
4316// Remove any filter elements that were already caught or that already 4317// occurred in the filter. While there, see if any of the elements are 4318// catch-alls. If so, the filter can be discarded. 4319bool SawCatchAll =
false;
4320for (
unsigned j = 0; j != NumTypeInfos; ++j) {
4324// This element is a catch-all. Bail out, noting this fact. 4329// Even if we've seen a type in a catch clause, we don't want to 4330// remove it from the filter. An unexpected type handler may be 4331// set up for a call site which throws an exception of the same 4332// type caught. In order for the exception thrown by the unexpected 4333// handler to propagate correctly, the filter must be correctly 4334// described for the call site. 4338// void unexpected() { throw 1;} 4339// void foo() throw (int) { 4340// std::set_unexpected(unexpected); 4343// } catch (int i) {} 4346// There is no point in having multiple copies of the same typeinfo in 4347// a filter, so only add it if we didn't already. 4348if (SeenInFilter.
insert(TypeInfo).second)
4349 NewFilterElts.
push_back(cast<Constant>(Elt));
4351// A filter containing a catch-all cannot match anything by definition. 4353// Throw the filter away. 4354 MakeNewInstruction =
true;
4358// If we dropped something from the filter, make a new one. 4359if (NewFilterElts.
size() < NumTypeInfos)
4360 MakeNewFilter =
true;
4364 NewFilterElts.
size());
4366 MakeNewInstruction =
true;
4371// If the new filter is empty then it will catch everything so there is 4372// no point in keeping any following clauses or marking the landingpad 4373// as having a cleanup. The case of the original filter being empty was 4374// already handled above. 4375if (MakeNewFilter && !NewFilterElts.
size()) {
4376assert(MakeNewInstruction &&
"New filter but not a new instruction!");
4383// If several filters occur in a row then reorder them so that the shortest 4384// filters come first (those with the smallest number of elements). This is 4385// advantageous because shorter filters are more likely to match, speeding up 4386// unwinding, but mostly because it increases the effectiveness of the other 4387// filter optimizations below. 4388for (
unsigned i = 0, e = NewClauses.
size(); i + 1 < e; ) {
4390// Find the maximal 'j' s.t. the range [i, j) consists entirely of filters. 4391for (j = i; j != e; ++j)
4392if (!isa<ArrayType>(NewClauses[j]->
getType()))
4395// Check whether the filters are already sorted by length. We need to know 4396// if sorting them is actually going to do anything so that we only make a 4397// new landingpad instruction if it does. 4398for (
unsigned k = i; k + 1 < j; ++k)
4400// Not sorted, so sort the filters now. Doing an unstable sort would be 4401// correct too but reordering filters pointlessly might confuse users. 4402 std::stable_sort(NewClauses.
begin() + i, NewClauses.
begin() + j,
4404 MakeNewInstruction =
true;
4408// Look for the next batch of filters. 4412// If typeinfos matched if and only if equal, then the elements of a filter L 4413// that occurs later than a filter F could be replaced by the intersection of 4414// the elements of F and L. In reality two typeinfos can match without being 4415// equal (for example if one represents a C++ class, and the other some class 4416// derived from it) so it would be wrong to perform this transform in general. 4417// However the transform is correct and useful if F is a subset of L. In that 4418// case L can be replaced by F, and thus removed altogether since repeating a 4419// filter is pointless. So here we look at all pairs of filters F and L where 4420// L follows F in the list of clauses, and remove L if every element of F is 4421// an element of L. This can occur when inlining C++ functions with exception 4423for (
unsigned i = 0; i + 1 < NewClauses.
size(); ++i) {
4424// Examine each filter in turn. 4428// Not a filter - skip it. 4431// Examine each filter following this one. Doing this backwards means that 4432// we don't have to worry about filters disappearing under us when removed. 4433for (
unsigned j = NewClauses.
size() - 1; j != i; --j) {
4434Value *LFilter = NewClauses[j];
4437// Not a filter - skip it. 4439// If Filter is a subset of LFilter, i.e. every element of Filter is also 4440// an element of LFilter, then discard LFilter. 4442// If Filter is empty then it is a subset of LFilter. 4445 NewClauses.
erase(J);
4446 MakeNewInstruction =
true;
4447// Move on to the next filter. 4451// If Filter is longer than LFilter then it cannot be a subset of it. 4453// Move on to the next filter. 4455// At this point we know that LFilter has at least one element. 4456if (isa<ConstantAggregateZero>(LFilter)) {
// LFilter only contains zeros. 4457// Filter is a subset of LFilter iff Filter contains only zeros (as we 4458// already know that Filter is not longer than LFilter). 4459if (isa<ConstantAggregateZero>(
Filter)) {
4460assert(FElts <= LElts &&
"Should have handled this case earlier!");
4462 NewClauses.
erase(J);
4463 MakeNewInstruction =
true;
4465// Move on to the next filter. 4469if (isa<ConstantAggregateZero>(
Filter)) {
// Filter only contains zeros. 4470// Since Filter is non-empty and contains only zeros, it is a subset of 4471// LFilter iff LFilter contains a zero. 4472assert(FElts > 0 &&
"Should have eliminated the empty filter earlier!");
4473for (
unsigned l = 0; l != LElts; ++l)
4475// LFilter contains a zero - discard it. 4476 NewClauses.
erase(J);
4477 MakeNewInstruction =
true;
4480// Move on to the next filter. 4483// At this point we know that both filters are ConstantArrays. Loop over 4484// operands to see whether every element of Filter is also an element of 4485// LFilter. Since filters tend to be short this is probably faster than 4486// using a method that scales nicely. 4489for (
unsigned f = 0; f != FElts; ++f) {
4492for (
unsigned l = 0; l != LElts; ++l) {
4494if (LTypeInfo == FTypeInfo) {
4504 NewClauses.
erase(J);
4505 MakeNewInstruction =
true;
4507// Move on to the next filter. 4511// If we changed any of the clauses, replace the old landingpad instruction 4513if (MakeNewInstruction) {
4518// A landing pad with no clauses must have the cleanup flag set. It is 4519// theoretically possible, though highly unlikely, that we eliminated all 4520// clauses. If so, force the cleanup flag to true. 4521if (NewClauses.empty())
4527// Even if none of the clauses changed, we may nonetheless have understood 4528// that the cleanup flag is pointless. Clear it if so. 4530assert(!CleanupFlag &&
"Adding a cleanup, not removing one?!");
4540// Try to push freeze through instructions that propagate but don't produce 4541// poison as far as possible. If an operand of freeze follows three 4542// conditions 1) one-use, 2) does not produce poison, and 3) has all but one 4543// guaranteed-non-poison operands then push the freeze through to the one 4544// operand that is not guaranteed non-poison. The actual transform is as 4546// Op1 = ... ; Op1 can be posion 4547// Op0 = Inst(Op1, NonPoisonOps...) ; Op0 has only one use and only have 4548// ; single guaranteed-non-poison operands 4552// Op1.fr = Freeze(Op1) 4553// ... = Inst(Op1.fr, NonPoisonOps...) 4555auto *OrigOpInst = dyn_cast<Instruction>(OrigOp);
4557// While we could change the other users of OrigOp to use freeze(OrigOp), that 4558// potentially reduces their optimization potential, so let's only do this iff 4559// the OrigOp is only used by the freeze. 4560if (!OrigOpInst || !OrigOpInst->hasOneUse() || isa<PHINode>(OrigOp))
4563// We can't push the freeze through an instruction which can itself create 4564// poison. If the only source of new poison is flags, we can simply 4565// strip them (since we know the only use is the freeze and nothing can 4566// benefit from them.) 4568/*ConsiderFlagsAndMetadata*/false))
4571// If operand is guaranteed not to be poison, there is no need to add freeze 4572// to the operand. So we first find the operand that is not guaranteed to be 4574Use *MaybePoisonOperand =
nullptr;
4575for (
Use &U : OrigOpInst->operands()) {
4576if (isa<MetadataAsValue>(U.get()) ||
4579if (!MaybePoisonOperand)
4580 MaybePoisonOperand = &U;
4585 OrigOpInst->dropPoisonGeneratingAnnotations();
4587// If all operands are guaranteed to be non-poison, we can drop freeze. 4588if (!MaybePoisonOperand)
4593 MaybePoisonOperand->get(), MaybePoisonOperand->get()->
getName() +
".fr");
4595replaceUse(*MaybePoisonOperand, FrozenMaybePoisonOperand);
4601// Detect whether this is a recurrence with a start value and some number of 4602// backedge values. We'll check whether we can push the freeze through the 4603// backedge values (possibly dropping poison flags along the way) until we 4604// reach the phi again. In that case, we can move the freeze to the start 4606Use *StartU =
nullptr;
4610// Add backedge value to worklist. 4615// Don't bother handling multiple start values. 4622returnnullptr;
// Not a recurrence. 4624Value *StartV = StartU->get();
4627// We can't insert freeze if the start value is the result of the 4628// terminator (e.g. an invoke). 4636if (!Visited.
insert(V).second)
4639if (Visited.
size() > 32)
4640returnnullptr;
// Limit the total number of values we inspect. 4642// Assume that PN is non-poison, because it will be after the transform. 4648/*ConsiderFlagsAndMetadata*/false))
4656I->dropPoisonGeneratingAnnotations();
4658if (StartNeedsFreeze) {
4670if (isa<Constant>(
Op) ||
Op->hasOneUse())
4673// Move the freeze directly after the definition of its operand, so that 4674// it dominates the maximum number of uses. Note that it may not dominate 4675// *all* uses if the operand is an invoke/callbr and the use is in a phi on 4676// the normal/default destination. This is why the domination check in the 4677// replacement below is still necessary. 4679if (isa<Argument>(
Op)) {
4683auto MoveBeforeOpt = cast<Instruction>(
Op)->getInsertionPointAfterDef();
4686 MoveBefore = *MoveBeforeOpt;
4689// Don't move to the position of a debug intrinsic. 4690if (isa<DbgInfoIntrinsic>(MoveBefore))
4691 MoveBefore = MoveBefore->getNextNonDebugInstruction()->getIterator();
4692// Re-point iterator to come after any debug-info records, if we're 4693// running in "RemoveDIs" mode 4694 MoveBefore.setHeadBit(
false);
4697if (&FI != &*MoveBefore) {
4698 FI.
moveBefore(*MoveBefore->getParent(), MoveBefore);
4702Op->replaceUsesWithIf(&FI, [&](
Use &U) ->
bool {
4704 Changed |= Dominates;
4711// Check if any direct or bitcast user of this value is a shuffle instruction. 4713for (
auto *U : V->users()) {
4714if (isa<ShuffleVectorInst>(U))
4723Value *Op0 =
I.getOperand(0);
4728// freeze (phi const, x) --> phi const, (freeze x) 4729if (
auto *PN = dyn_cast<PHINode>(Op0)) {
4739// If I is freeze(undef), check its uses and fold it to a fixed constant. 4741// - select's condition: if the true value is constant, choose it by making 4742// the condition true. 4745// Note that this transform is intentionally done here rather than 4746// via an analysis in InstSimplify or at individual user sites. That is 4747// because we must produce the same value for all uses of the freeze - 4748// it's the reason "freeze" exists! 4750// TODO: This could use getBinopAbsorber() / getBinopIdentity() to avoid 4751// duplicating logic for binops at least. 4752auto getUndefReplacement = [&
I](
Type *Ty) {
4755for (
constauto *U :
I.users()) {
4764elseif (BestValue !=
C)
4765 BestValue = NullValue;
4767assert(BestValue &&
"Must have at least one use");
4772// Don't fold freeze(undef/poison) if it's used as a vector operand in 4773// a shuffle. This may improve codegen for shuffles that allow 4774// unspecified inputs. 4782Constant *ReplaceC = getUndefReplacement(
I.getType()->getScalarType());
4786// Replace uses of Op with freeze(Op). 4793/// Check for case where the call writes to an otherwise dead alloca. This 4794/// shows up for unused out-params in idiomatic C/C++ code. Note that this 4795/// helper *only* analyzes the write; doesn't check any other legality aspect. 4797auto *CB = dyn_cast<CallBase>(
I);
4799// TODO: handle e.g. store to alloca here - only worth doing if we extend 4800// to allow reload along used path as described below. Otherwise, this 4801// is simply a store to a dead allocation which will be removed. 4808// TODO: allow malloc? 4810// TODO: allow memory access dominated by move point? Note that since AI 4811// could have a reference to itself captured by the call, we would need to 4812// account for cycles in doing so. 4816for (
constUser *U :
I.users()) {
4817if (Visited.
insert(U).second)
4822while (!AllocaUsers.
empty()) {
4823auto *UserI = cast<Instruction>(AllocaUsers.
pop_back_val());
4824if (isa<GetElementPtrInst>(UserI) || isa<AddrSpaceCastInst>(UserI)) {
4830// TODO: support lifetime.start/end here 4836/// Try to move the specified instruction from its current block into the 4837/// beginning of DestBlock, which can only happen if it's safe to move the 4838/// instruction past all of the instructions between it and the end of its 4844// Cannot move control-flow-involving, volatile loads, vaarg, etc. 4845if (isa<PHINode>(
I) ||
I->isEHPad() ||
I->mayThrow() || !
I->willReturn() ||
4849// Do not sink static or dynamic alloca instructions. Static allocas must 4850// remain in the entry block, and dynamic allocas must not be sunk in between 4851// a stacksave / stackrestore pair, which would incorrectly shorten its 4853if (isa<AllocaInst>(
I))
4856// Do not sink into catchswitch blocks. 4860// Do not sink convergent call instructions. 4861if (
auto *CI = dyn_cast<CallInst>(
I)) {
4862if (CI->isConvergent())
4866// Unless we can prove that the memory write isn't visibile except on the 4867// path we're sinking to, we must bail. 4868if (
I->mayWriteToMemory()) {
4873// We can only sink load instructions if there is nothing between the load and 4874// the end of block that could change the value. 4875if (
I->mayReadFromMemory() &&
4876 !
I->hasMetadata(LLVMContext::MD_invariant_load)) {
4877// We don't want to do any sophisticated alias analysis, so we only check 4878// the instructions after I in I's parent block if we try to sink to its 4883 E =
I->getParent()->end();
4885if (Scan->mayWriteToMemory())
4889I->dropDroppableUses([&](
constUse *U) {
4890auto *
I = dyn_cast<Instruction>(U->getUser());
4891if (
I &&
I->getParent() != DestBlock) {
4897 /// FIXME: We could remove droppable uses that are not dominated by 4898 /// the new position. 4901I->moveBefore(*DestBlock, InsertPos);
4904// Also sink all related debug uses from the source basic block. Otherwise we 4905// get debug use before the def. Attempt to salvage debug uses first, to 4906// maximise the range variables have location for. If we cannot salvage, then 4907// mark the location undef: we know it was supposed to receive a new location 4908// here, but that computation has been sunk. 4912if (!DbgUsers.
empty())
4914if (!DbgVariableRecords.
empty())
4916 DbgVariableRecords);
4918// PS: there are numerous flaws with this behaviour, not least that right now 4919// assignments can be re-ordered past other assignments to the same variable 4920// if they use different Values. Creating more undef assignements can never be 4921// undone. And salvaging all users outside of this block can un-necessarily 4922// alter the lifetime of the live-value that the variable refers to. 4923// Some of these things can be resolved by tolerating debug use-before-defs in 4924// LLVM-IR, however it depends on the instruction-referencing CodeGen backend 4925// being used for more architectures. 4933// For all debug values in the destination block, the sunk instruction 4934// will still be available, so they do not need to be dropped. 4936for (
auto &DbgUser : DbgUsers)
4937if (DbgUser->getParent() != DestBlock)
4940// Process the sinking DbgUsersToSalvage in reverse order, as we only want 4941// to clone the last appearing debug intrinsic for each given variable. 4944if (DVI->getParent() == SrcBlock)
4947 [](
auto *
A,
auto *
B) {
returnB->comesBefore(
A); });
4951for (
auto *
User : DbgUsersToSink) {
4952// A dbg.declare instruction should not be cloned, since there can only be 4953// one per variable fragment. It should be left in the original place 4954// because the sunk instruction is not an alloca (otherwise we could not be 4956if (isa<DbgDeclareInst>(
User))
4961User->getDebugLoc()->getInlinedAt());
4963if (!SunkVariables.
insert(DbgUserVariable).second)
4966// Leave dbg.assign intrinsics in their original positions and there should 4967// be no need to insert a clone. 4968if (isa<DbgAssignIntrinsic>(
User))
4971 DIIClones.emplace_back(cast<DbgVariableIntrinsic>(
User->clone()));
4972if (isa<DbgDeclareInst>(
User) && isa<CastInst>(
I))
4973 DIIClones.back()->replaceVariableLocationOp(
I,
I->getOperand(0));
4977// Perform salvaging without the clones, then sink the clones. 4978if (!DIIClones.empty()) {
4980// The clones are in reverse order of original appearance, reverse again to 4981// maintain the original order. 4983 DIIClone->insertBefore(InsertPos);
4993// Implementation of tryToSinkInstructionDbgValues, but for the 4994// DbgVariableRecord of variable assignments rather than dbg.values. 4996// Fetch all DbgVariableRecords not already in the destination. 4998for (
auto &DVR : DbgVariableRecords)
4999if (DVR->getParent() != DestBlock)
5000 DbgVariableRecordsToSalvage.
push_back(DVR);
5002// Fetch a second collection, of DbgVariableRecords in the source block that 5003// we're going to sink. 5006if (DVR->getParent() == SrcBlock)
5007 DbgVariableRecordsToSink.
push_back(DVR);
5009// Sort DbgVariableRecords according to their position in the block. This is a 5010// partial order: DbgVariableRecords attached to different instructions will 5011// be ordered by the instruction order, but DbgVariableRecords attached to the 5012// same instruction won't have an order. 5014returnB->getInstruction()->comesBefore(
A->getInstruction());
5018// If there are two assignments to the same variable attached to the same 5019// instruction, the ordering between the two assignments is important. Scan 5020// for this (rare) case and establish which is the last assignment. 5021usingInstVarPair = std::pair<const Instruction *, DebugVariable>;
5023if (DbgVariableRecordsToSink.
size() > 1) {
5025// Count how many assignments to each variable there is per instruction. 5029 DVR->getDebugLoc()->getInlinedAt());
5030 CountMap[std::make_pair(DVR->getInstruction(), DbgUserVariable)] += 1;
5033// If there are any instructions with two assignments, add them to the 5034// FilterOutMap to record that they need extra filtering. 5036for (
auto It : CountMap) {
5038 FilterOutMap[It.first] =
nullptr;
5039 DupSet.
insert(It.first.first);
5043// For all instruction/variable pairs needing extra filtering, find the 5044// latest assignment. 5050 DVR.getDebugLoc()->getInlinedAt());
5052 FilterOutMap.
find(std::make_pair(Inst, DbgUserVariable));
5053if (FilterIt == FilterOutMap.
end())
5055if (FilterIt->second !=
nullptr)
5057 FilterIt->second = &DVR;
5062// Perform cloning of the DbgVariableRecords that we plan on sinking, filter 5063// out any duplicate assignments identified above. 5072 DVR->getDebugLoc()->getInlinedAt());
5074// For any variable where there were multiple assignments in the same place, 5075// ignore all but the last assignment. 5076if (!FilterOutMap.
empty()) {
5077 InstVarPair IVP = std::make_pair(DVR->getInstruction(), DbgUserVariable);
5078auto It = FilterOutMap.
find(IVP);
5081if (It != FilterOutMap.
end() && It->second != DVR)
5085if (!SunkVariables.
insert(DbgUserVariable).second)
5088if (DVR->isDbgAssign())
5095// Perform salvaging without the clones, then sink the clones. 5096if (DVRClones.
empty())
5101// The clones are in reverse order of original appearance. Assert that the 5102// head bit is set on the iterator as we _should_ have received it via 5103// getFirstInsertionPt. Inserting like this will reverse the clone order as 5104// we'll repeatedly insert at the head, such as: 5105// DVR-3 (third insertion goes here) 5106// DVR-2 (second insertion goes here) 5107// DVR-1 (first insertion goes here) 5110assert(InsertPos.getHeadBit());
5112 InsertPos->getParent()->insertDbgRecordBefore(DVRClone, InsertPos);
5119// Walk deferred instructions in reverse order, and push them to the 5120// worklist, which means they'll end up popped from the worklist in-order. 5122// Check to see if we can DCE the instruction. We do this already here to 5123// reduce the number of uses and thus allow other folds to trigger. 5124// Note that eraseInstFromFunction() may push additional instructions on 5125// the deferred worklist, so this will DCE whole instruction chains. 5136if (
I ==
nullptr)
continue;
// skip null values. 5138// Check to see if we can DCE the instruction. 5148// See if we can trivially sink this instruction to its user if we can 5149// prove that the successor is not executed more frequently than our block. 5150// Return the UserBlock if successful. 5151auto getOptionalSinkBlockForInst =
5152 [
this](
Instruction *
I) -> std::optional<BasicBlock *> {
5158unsigned NumUsers = 0;
5160for (
Use &U :
I->uses()) {
5168// Special handling for Phi nodes - get the block the use occurs in. 5170if (
PHINode *PN = dyn_cast<PHINode>(UserInst))
5171 UserBB = PN->getIncomingBlock(U);
5172// Bail out if we have uses in different blocks. We don't do any 5173// sophisticated analysis (i.e finding NearestCommonDominator of these 5175if (UserParent && UserParent != UserBB)
5177 UserParent = UserBB;
5179// Make sure these checks are done only once, naturally we do the checks 5180// the first time we get the userparent, this will save compile time. 5182// Try sinking to another block. If that block is unreachable, then do 5183// not bother. SimplifyCFG should handle it. 5188// See if the user is one of our successors that has only one 5189// predecessor, so that we don't have to split the critical edge. 5190// Another option where we can sink is a block that ends with a 5191// terminator that does not pass control to other block (such as 5192// return or unreachable or resume). In this case: 5193// - I dominates the User (by SSA form); 5194// - the User will be executed at most once. 5195// So sinking I down to User is always profitable or neutral. 5205// No user or only has droppable users. 5212auto OptBB = getOptionalSinkBlockForInst(
I);
5214auto *UserParent = *OptBB;
5215// Okay, the CFG is simple enough, try to sink this instruction. 5219// We'll add uses of the sunk instruction below, but since 5220// sinking can expose opportunities for it's *operands* add 5221// them to the worklist 5222for (
Use &U :
I->operands())
5223if (
Instruction *OpI = dyn_cast<Instruction>(U.get()))
5228// Now that we have an instruction, try combining it to simplify it. 5231I, {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
5241// Should we replace the old instruction with a new one? 5244 <<
" New = " << *Result <<
'\n');
5246// We copy the old instruction's DebugLoc to the new instruction, unless 5247// InstCombine already assigned a DebugLoc to it, in which case we 5248// should trust the more specifically selected DebugLoc. 5249if (!Result->getDebugLoc())
5250 Result->setDebugLoc(
I->getDebugLoc());
5251// We also copy annotation metadata to the new instruction. 5252 Result->copyMetadata(*
I, LLVMContext::MD_annotation);
5253// Everything uses the new instruction now. 5254I->replaceAllUsesWith(Result);
5256// Move the name to the new instruction first. 5257 Result->takeName(
I);
5259// Insert the new instruction into the basic block... 5263// Are we replace a PHI with something that isn't a PHI, or vice versa? 5264if (isa<PHINode>(Result) != isa<PHINode>(
I)) {
5265// We need to fix up the insertion point. 5266if (isa<PHINode>(
I))
// PHI -> Non-PHI 5268else// Non-PHI -> PHI 5272 Result->insertInto(InstParent, InsertPos);
5274// Push the new instruction and any users onto the worklist. 5281 <<
" New = " << *
I <<
'\n');
5283// If the instruction was modified, it's possible that it is now dead. 5300// Track the scopes used by !alias.scope and !noalias. In a function, a 5301// @llvm.experimental.noalias.scope.decl is only useful if that scope is used 5302// by both sets. If not, the declaration of the scope can be safely omitted. 5303// The MDNode of the scope can be omitted as well for the instructions that are 5304// part of this function. We do not do that at this point, as this might become 5305// too time consuming to do. 5312// This seems to be faster than checking 'mayReadOrWriteMemory()'. 5313if (!
I->hasMetadataOtherThanDebugLoc())
5316auto Track = [](
Metadata *ScopeList,
auto &Container) {
5317constauto *MDScopeList = dyn_cast_or_null<MDNode>(ScopeList);
5318if (!MDScopeList || !Container.insert(MDScopeList).second)
5320for (
constauto &
MDOperand : MDScopeList->operands())
5321if (
auto *MDScope = dyn_cast<MDNode>(
MDOperand))
5322 Container.insert(MDScope);
5325 Track(
I->getMetadata(LLVMContext::MD_alias_scope), UsedAliasScopesAndLists);
5326 Track(
I->getMetadata(LLVMContext::MD_noalias), UsedNoAliasScopesAndLists);
5335"llvm.experimental.noalias.scope.decl in use ?");
5338"llvm.experimental.noalias.scope should refer to a single scope");
5340if (
auto *MD = dyn_cast<MDNode>(
MDOperand))
5341return !UsedAliasScopesAndLists.
contains(MD) ||
5342 !UsedNoAliasScopesAndLists.
contains(MD);
5344// Not an MDNode ? throw away. 5349/// Populate the IC worklist from a function, by walking it in reverse 5350/// post-order and adding all reachable code to the worklist. 5352/// This has a couple of tricks to make the code faster and more powerful. In 5353/// particular, we constant fold and DCE instructions as we go, to avoid adding 5354/// them to the worklist (this significantly speeds up instcombine on code where 5355/// many instructions are dead or constant). Additionally, if we find a branch 5356/// whose condition is a known constant, we only visit the reachable successors. 5366if (Succ != LiveSucc &&
DeadEdges.insert({BB, Succ}).second)
5367for (
PHINode &PN : Succ->phis())
5368for (
Use &U : PN.incoming_values())
5369if (PN.getIncomingBlock(U) == BB && !isa<PoisonValue>(U)) {
5379 HandleOnlyLiveSuccessor(BB,
nullptr);
5385// ConstantProp instruction if trivially constant. 5386if (!Inst.use_empty() &&
5387 (Inst.getNumOperands() == 0 || isa<Constant>(Inst.getOperand(0))))
5391 Inst.replaceAllUsesWith(
C);
5394 Inst.eraseFromParent();
5399// See if we can constant fold its operands. 5400for (
Use &U : Inst.operands()) {
5401if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U))
5404auto *
C = cast<Constant>(U);
5412 <<
"\n New = " << *FoldRes <<
'\n');
5418// Skip processing debug and pseudo intrinsics in InstCombine. Processing 5419// these call instructions consumes non-trivial amount of time and 5420// provides no value for the optimization. 5421if (!Inst.isDebugOrPseudoInst()) {
5422 InstrsForInstructionWorklist.
push_back(&Inst);
5423 SeenAliasScopes.
analyse(&Inst);
5427// If this is a branch or switch on a constant, mark only the single 5428// live successor. Otherwise assume all successors are live. 5431if (isa<UndefValue>(BI->getCondition())) {
5432// Branch on undef is UB. 5433 HandleOnlyLiveSuccessor(BB,
nullptr);
5436if (
auto *
Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
5437bool CondVal =
Cond->getZExtValue();
5438 HandleOnlyLiveSuccessor(BB, BI->getSuccessor(!CondVal));
5441 }
elseif (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
5442if (isa<UndefValue>(SI->getCondition())) {
5443// Switch on undef is UB. 5444 HandleOnlyLiveSuccessor(BB,
nullptr);
5447if (
auto *
Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
5448 HandleOnlyLiveSuccessor(BB,
5449 SI->findCaseValue(
Cond)->getCaseSuccessor());
5455// Remove instructions inside unreachable blocks. This prevents the 5456// instcombine code from having to deal with some bad special cases, and 5457// reduces use counts of instructions. 5459if (LiveBlocks.
count(&BB))
5462unsigned NumDeadInstInBB;
5463unsigned NumDeadDbgInstInBB;
5464 std::tie(NumDeadInstInBB, NumDeadDbgInstInBB) =
5467MadeIRChange |= NumDeadInstInBB + NumDeadDbgInstInBB > 0;
5468 NumDeadInst += NumDeadInstInBB;
5471// Once we've found all of the instructions to add to instcombine's worklist, 5472// add them in reverse order. This way instcombine will visit from the top 5473// of the function down. This jives well with the way that it adds all uses 5474// of instructions to the worklist after doing a transformation, thus avoiding 5475// some N^2 behavior in pathological cases. 5478// DCE instruction if trivially dead. As we iterate in reverse program 5479// order here, we will clean up whole chains of dead instructions. 5485 Inst->eraseFromParent();
5497// Collect backedges. 5514auto &
DL =
F.getDataLayout();
5516 !
F.hasFnAttribute(
"instcombine-no-verify-fixpoint");
5518 /// Builder - This is an IRBuilder that automatically inserts new 5519 /// instructions into the worklist when they are created. 5524if (
auto *Assume = dyn_cast<AssumeInst>(
I))
5530// Lower dbg.declare intrinsics otherwise their value may be clobbered 5532bool MadeIRChange =
false;
5536// Iterate while there is work to do. 5537unsigned Iteration = 0;
5543 <<
" on " <<
F.getName()
5544 <<
" reached; stopping without verifying fixpoint\n");
5548 ++NumWorklistIterations;
5549LLVM_DEBUG(
dbgs() <<
"\n\nINSTCOMBINE ITERATION #" << Iteration <<
" on " 5550 <<
F.getName() <<
"\n");
5553 ORE, BFI, BPI, PSI,
DL, RPOT);
5556 MadeChangeInThisIteration |= IC.
run();
5557if (!MadeChangeInThisIteration)
5563"Instruction Combining on " +
Twine(
F.getName()) +
5566"Use 'instcombine<no-verify-fixpoint>' or function attribute " 5567"'instcombine-no-verify-fixpoint' to suppress this error.",
5568/*GenCrashDiag=*/false);
5574elseif (Iteration == 2)
5576elseif (Iteration == 3)
5577 ++NumThreeIterations;
5579 ++NumFourOrMoreIterations;
5589OS, MapClassName2PassName);
5596char InstCombinePass::ID = 0;
5601// No changes since last InstCombine pass, exit early. 5602if (LRT.shouldSkip(&
ID))
5615auto *BFI = (PSI && PSI->hasProfileSummary()) ?
5620 BFI, BPI, PSI, Options)) {
5621// No changes, all analyses are preserved. 5622 LRT.update(&
ID,
/*Changed=*/false);
5626// Mark all the analyses that instcombine updates as preserved. 5628 LRT.update(&
ID,
/*Changed=*/true);
5654// Required analyses. 5655auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
5656auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
5657auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
5658auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
5659auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
5660auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
5662// Optional analyses. 5664 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
5667 &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :
5670if (
auto *WrapperPass =
5671 getAnalysisIfAvailable<BranchProbabilityInfoWrapperPass>())
5672 BPI = &WrapperPass->getBPI();
5685"Combine redundant instructions",
false,
false)
5698// Initialization Routines AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static const Function * getParent(const Value *V)
This is the interface for LLVM's primary stateless and local alias analysis.
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This header defines various interfaces for pass management in LLVM.
This defines the Use class.
iv Induction Variable Users
static bool leftDistributesOverRight(Instruction::BinaryOps LOp, bool HasNUW, bool HasNSW, Intrinsic::ID ROp)
Return whether "X LOp (Y ROp Z)" is always equal to "(X LOp Y) ROp (X LOp Z)".
This file provides internal interfaces used to implement the InstCombine.
This file provides the primary interface to the instcombine pass.
static Value * simplifySwitchOnSelectUsingRanges(SwitchInst &SI, SelectInst *Select, bool IsTrueArm)
static bool isUsedWithinShuffleVector(Value *V)
static bool isNeverEqualToUnescapedAlloc(Value *V, const TargetLibraryInfo &TLI, Instruction *AI)
static bool shorter_filter(const Value *LHS, const Value *RHS)
static Instruction * foldSelectGEP(GetElementPtrInst &GEP, InstCombiner::BuilderTy &Builder)
Thread a GEP operation with constant indices through the constant true/false arms of a select.
static bool shouldMergeGEPs(GEPOperator &GEP, GEPOperator &Src)
static cl::opt< unsigned > MaxArraySize("instcombine-maxarray-size", cl::init(1024), cl::desc("Maximum array size considered when doing a combine"))
static cl::opt< unsigned > ShouldLowerDbgDeclare("instcombine-lower-dbg-declare", cl::Hidden, cl::init(true))
static bool hasNoSignedWrap(BinaryOperator &I)
static bool simplifyAssocCastAssoc(BinaryOperator *BinOp1, InstCombinerImpl &IC)
Combine constant operands of associative operations either before or after a cast to eliminate one of...
static bool combineInstructionsOverFunction(Function &F, InstructionWorklist &Worklist, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI, ProfileSummaryInfo *PSI, const InstCombineOptions &Opts)
static Value * simplifyInstructionWithPHI(Instruction &I, PHINode *PN, Value *InValue, BasicBlock *InBB, const DataLayout &DL, const SimplifyQuery SQ)
static bool shouldCanonicalizeGEPToPtrAdd(GetElementPtrInst &GEP)
Return true if we should canonicalize the gep to an i8 ptradd.
static void ClearSubclassDataAfterReassociation(BinaryOperator &I)
Conservatively clears subclassOptionalData after a reassociation or commutation.
static bool isAllocSiteRemovable(Instruction *AI, SmallVectorImpl< WeakTrackingVH > &Users, const TargetLibraryInfo &TLI)
static Value * getIdentityValue(Instruction::BinaryOps Opcode, Value *V)
This function returns identity value for given opcode, which can be used to factor patterns like (X *...
static std::optional< std::pair< Value *, Value * > > matchSymmetricPhiNodesPair(PHINode *LHS, PHINode *RHS)
static Value * foldOperationIntoSelectOperand(Instruction &I, SelectInst *SI, Value *NewOp, InstCombiner &IC)
static Instruction * canonicalizeGEPOfConstGEPI8(GetElementPtrInst &GEP, GEPOperator *Src, InstCombinerImpl &IC)
static Instruction * tryToMoveFreeBeforeNullTest(CallInst &FI, const DataLayout &DL)
Move the call to free before a NULL test.
static Value * simplifyOperationIntoSelectOperand(Instruction &I, SelectInst *SI, bool IsTrueArm)
static bool rightDistributesOverLeft(Instruction::BinaryOps LOp, Instruction::BinaryOps ROp)
Return whether "(X LOp Y) ROp Z" is always equal to "(X ROp Z) LOp (Y ROp Z)".
static Value * tryFactorization(BinaryOperator &I, const SimplifyQuery &SQ, InstCombiner::BuilderTy &Builder, Instruction::BinaryOps InnerOpcode, Value *A, Value *B, Value *C, Value *D)
This tries to simplify binary operations by factorizing out common terms (e.
static bool isRemovableWrite(CallBase &CB, Value *UsedV, const TargetLibraryInfo &TLI)
Given a call CB which uses an address UsedV, return true if we can prove the call's only possible eff...
static Instruction::BinaryOps getBinOpsForFactorization(Instruction::BinaryOps TopOpcode, BinaryOperator *Op, Value *&LHS, Value *&RHS, BinaryOperator *OtherOp)
This function predicates factorization using distributive laws.
static bool hasNoUnsignedWrap(BinaryOperator &I)
static bool SoleWriteToDeadLocal(Instruction *I, TargetLibraryInfo &TLI)
Check for case where the call writes to an otherwise dead alloca.
static cl::opt< unsigned > MaxSinkNumUsers("instcombine-max-sink-users", cl::init(32), cl::desc("Maximum number of undroppable users for instruction sinking"))
static Instruction * foldGEPOfPhi(GetElementPtrInst &GEP, PHINode *PN, IRBuilderBase &Builder)
static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo)
Return 'true' if the given typeinfo will match anything.
static cl::opt< bool > EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"), cl::init(true))
static bool maintainNoSignedWrap(BinaryOperator &I, Value *B, Value *C)
static GEPNoWrapFlags getMergedGEPNoWrapFlags(GEPOperator &GEP1, GEPOperator &GEP2)
Determine nowrap flags for (gep (gep p, x), y) to (gep p, (x + y)) transform.
This file contains the declarations for metadata subclasses.
uint64_t IntrinsicInst * II
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
static bool IsSelect(MachineInstr &MI)
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static unsigned getScalarSizeInBits(Type *Ty)
static SymbolRef::Type getType(const Symbol *Sym)
This pass exposes codegen information to IR-level passes.
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
static const uint32_t IV[8]
bool isNoAliasScopeDeclDead(Instruction *Inst)
void analyse(Instruction *I)
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
APInt trunc(unsigned width) const
Truncate to new width.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
unsigned getBitWidth() const
Return the number of bits in the APInt.
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
Class to represent array types.
uint64_t getNumElements() const
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Type * getElementType() const
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
uint64_t getDereferenceableBytes() const
Returns the number of dereferenceable bytes from the dereferenceable attribute.
bool isValid() const
Return true if the attribute is any kind of attribute.
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
InstListType::iterator iterator
Instruction iterators...
const_iterator getFirstNonPHIOrDbgOrAlloca() const
Returns an iterator to the first instruction in this block that is not a PHINode, a debug intrinsic,...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
static BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
BinaryOps getOpcode() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
static BinaryOperator * CreateNUW(BinaryOps Opc, Value *V1, Value *V2, const Twine &Name="")
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
void swapSuccessors()
Swap the successors of this branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
Analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
void swapSuccEdgesProbabilities(const BasicBlock *Src)
Swap outgoing edges probabilities for Src with branch terminator.
Represents analyses that only rely on functions' control flow.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void setAttributes(AttributeList A)
Set the attributes for this call.
bool doesNotThrow() const
Determine if the call cannot unwind.
Value * getArgOperand(unsigned i) const
AttributeList getAttributes() const
Return the attributes for this call.
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
ConstantArray - Constant Array Declarations.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * getNot(Constant *C)
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
static ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
Constant Vector Declarations.
static Constant * get(ArrayRef< Constant * > V)
This is an important base class in LLVM.
static Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
static Constant * replaceUndefsWith(Constant *C, Constant *Replacement)
Try to replace undefined constant C or undefined elements in C with Replacement.
static Constant * getAllOnesValue(Type *Ty)
const Constant * stripPointerCasts() const
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
SmallVector< APInt > getGEPIndicesForOffset(Type *&ElemTy, APInt &Offset) const
Get GEP indices to access Offset inside ElemTy.
bool isLegalInteger(uint64_t Width) const
Returns true if the specified type is known to be a native integer type supported by the CPU.
unsigned getIndexTypeSizeInBits(Type *Ty) const
Layout size of the index used in GEP calculation.
IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
int64_t getIndexedOffsetInType(Type *ElemTy, ArrayRef< Value * > Indices) const
Returns the offset from the beginning of the type for the specified indices.
This is the common base class for debug info intrinsics for variables.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
static bool shouldExecute(unsigned CounterName)
Identifies a unique instance of a variable.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void registerBranch(BranchInst *BI)
Add a branch condition to the cache.
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This instruction extracts a struct member or array element value from an aggregate value.
ArrayRef< unsigned > getIndices() const
iterator_range< idx_iterator > indices() const
idx_iterator idx_end() const
static ExtractValueInst * Create(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Value * getAggregateOperand()
idx_iterator idx_begin() const
Utility class for floating point operations which can have information about relaxed accuracy require...
Convenience struct for specifying and reasoning about fast-math flags.
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
const BasicBlock & getEntryBlock() const
Represents flags for the getelementptr instruction/expression.
GEPNoWrapFlags withoutNoUnsignedSignedWrap() const
static GEPNoWrapFlags noUnsignedWrap()
GEPNoWrapFlags intersectForOffsetAdd(GEPNoWrapFlags Other) const
Given (gep (gep p, x), y), determine the nowrap flags for (gep p, x+y).
GEPNoWrapFlags withoutNoUnsignedWrap() const
GEPNoWrapFlags getNoWrapFlags() const
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
static GetElementPtrInst * CreateInBounds(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Legacy wrapper pass to provide the GlobalsAAResult object.
This instruction compares its operands according to the predicate given to the constructor.
CmpPredicate getCmpPredicate() const
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateLogicalOp(Instruction::BinaryOps Opc, Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreatePtrAdd(Value *Ptr, Value *Offset, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
Value * CreateBinaryIntrinsic(Intrinsic::ID ID, Value *LHS, Value *RHS, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with 2 operands which is mangled on the first type.
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateAShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
ConstantInt * getInt(const APInt &AI)
Get a constant integer value.
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
This instruction inserts a struct field of array element value into an aggregate value.
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
InstCombinePass(InstCombineOptions Opts={})
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Instruction * FoldOpIntoSelect(Instruction &Op, SelectInst *SI, bool FoldWithMultiUse=false)
Given an instruction with a select as one operand and a constant as the other operand,...
Instruction * foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I)
Tries to simplify binops of select and cast of the select condition.
Instruction * foldBinOpIntoSelectOrPhi(BinaryOperator &I)
This is a convenience wrapper function for the above two functions.
bool SimplifyAssociativeOrCommutative(BinaryOperator &I)
Performs a few simplifications for operators which are associative or commutative.
Instruction * visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src)
Value * foldUsingDistributiveLaws(BinaryOperator &I)
Tries to simplify binary operations which some other binary operation distributes over.
Instruction * foldBinOpShiftWithShift(BinaryOperator &I)
Instruction * visitUnreachableInst(UnreachableInst &I)
Instruction * foldOpIntoPhi(Instruction &I, PHINode *PN, bool AllowMultipleUses=false)
Given a binary operator, cast instruction, or select which has a PHI node as operand #0,...
void handleUnreachableFrom(Instruction *I, SmallVectorImpl< BasicBlock * > &Worklist)
Value * SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &PoisonElts, unsigned Depth=0, bool AllowMultipleUsers=false) override
The specified value produces a vector with any number of elements.
Instruction * visitFreeze(FreezeInst &I)
void handlePotentiallyDeadBlocks(SmallVectorImpl< BasicBlock * > &Worklist)
bool prepareWorklist(Function &F)
Perform early cleanup and prepare the InstCombine worklist.
Instruction * visitFree(CallInst &FI, Value *FreedOp)
Instruction * visitExtractValueInst(ExtractValueInst &EV)
void handlePotentiallyDeadSuccessors(BasicBlock *BB, BasicBlock *LiveSucc)
Instruction * visitUnconditionalBranchInst(BranchInst &BI)
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Instruction * visitLandingPadInst(LandingPadInst &LI)
Instruction * visitReturnInst(ReturnInst &RI)
Instruction * visitSwitchInst(SwitchInst &SI)
Instruction * foldBinopWithPhiOperands(BinaryOperator &BO)
For a binary operator with 2 phi operands, try to hoist the binary operation before the phi.
Constant * getLosslessTrunc(Constant *C, Type *TruncTy, unsigned ExtOp)
Value * SimplifyDemandedUseFPClass(Value *V, FPClassTest DemandedMask, KnownFPClass &Known, unsigned Depth, Instruction *CxtI)
Attempts to replace V with a simpler value based on the demanded floating-point classes.
bool mergeStoreIntoSuccessor(StoreInst &SI)
Try to transform: if () { *P = v1; } else { *P = v2 } or: *P = v1; if () { *P = v2; } into a phi node...
Instruction * tryFoldInstWithCtpopWithNot(Instruction *I)
void tryToSinkInstructionDbgValues(Instruction *I, BasicBlock::iterator InsertPos, BasicBlock *SrcBlock, BasicBlock *DestBlock, SmallVectorImpl< DbgVariableIntrinsic * > &DbgUsers)
void CreateNonTerminatorUnreachable(Instruction *InsertAt)
Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...
Value * pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI)
bool run()
Run the combiner over the entire worklist until it is empty.
Instruction * foldVectorBinop(BinaryOperator &Inst)
Canonicalize the position of binops relative to shufflevector.
bool removeInstructionsBeforeUnreachable(Instruction &I)
Value * SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS, Value *RHS)
void tryToSinkInstructionDbgVariableRecords(Instruction *I, BasicBlock::iterator InsertPos, BasicBlock *SrcBlock, BasicBlock *DestBlock, SmallVectorImpl< DbgVariableRecord * > &DPUsers)
void addDeadEdge(BasicBlock *From, BasicBlock *To, SmallVectorImpl< BasicBlock * > &Worklist)
Instruction * visitAllocSite(Instruction &FI)
Instruction * visitGetElementPtrInst(GetElementPtrInst &GEP)
Instruction * visitBranchInst(BranchInst &BI)
Value * tryFactorizationFolds(BinaryOperator &I)
This tries to simplify binary operations by factorizing out common terms (e.
Instruction * foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN)
bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock)
Try to move the specified instruction from its current block into the beginning of DestBlock,...
bool freezeOtherUses(FreezeInst &FI)
void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser=nullptr)
Freely adapt every user of V as-if V was changed to !V.
The core instruction combiner logic.
const DataLayout & getDataLayout() const
bool isFreeToInvert(Value *V, bool WillInvertAllUses, bool &DoesConsume)
Return true if the specified value is free to invert (apply ~ to).
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Instruction * InsertNewInstBefore(Instruction *New, BasicBlock::iterator Old)
Inserts an instruction New before instruction Old.
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
uint64_t MaxArraySizeForCombine
Maximum size of array considered when transforming.
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
static bool isCanonicalPredicate(CmpPredicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Instruction * InsertNewInstWith(Instruction *New, BasicBlock::iterator Old)
Same as InsertNewInstBefore, but also sets the debug loc.
BranchProbabilityInfo * BPI
ReversePostOrderTraversal< BasicBlock * > & RPOT
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
std::optional< Instruction * > targetInstCombineIntrinsic(IntrinsicInst &II)
void addToWorklist(Instruction *I)
Value * getFreelyInvertedImpl(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume, unsigned Depth)
Return nonnull value if V is free to invert under the condition of WillInvertAllUses.
SmallDenseSet< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdges
Backedges, used to avoid pushing instructions across backedges in cases where this may result in infi...
std::optional< Value * > targetSimplifyDemandedVectorEltsIntrinsic(IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts, APInt &UndefElts2, APInt &UndefElts3, std::function< void(Instruction *, unsigned, APInt, APInt &)> SimplifyAndSetOp)
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
SmallDenseSet< std::pair< BasicBlock *, BasicBlock * >, 8 > DeadEdges
Edges that are known to never be taken.
std::optional< Value * > targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask, KnownBits &Known, bool &KnownBitsComputed)
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
bool isValidAddrSpaceCast(unsigned FromAS, unsigned ToAS) const
Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume)
bool isBackEdge(const BasicBlock *From, const BasicBlock *To)
void visit(Iterator Start, Iterator End)
The legacy pass manager's instcombine pass.
InstructionCombiningPass()
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
Instruction * removeOne()
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
void add(Instruction *I)
Add instruction to the worklist.
void push(Instruction *I)
Push the instruction onto the worklist stack.
Instruction * popDeferred()
void zap()
Check that the worklist is empty and nuke the backing store for the map.
void reserve(size_t Size)
static bool isBitwiseLogicOp(unsigned Opcode)
Determine if the Opcode is and/or/xor.
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
bool isAssociative() const LLVM_READONLY
Return true if the instruction is associative:
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
const Function * getFunction() const
Return the function this instruction belongs to.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
bool willReturn() const LLVM_READONLY
Return true if the instruction will return (unwinding is considered as a form of returning control fl...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
bool isBitwiseLogicOp() const
Return true if this is and/or/xor.
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A wrapper class for inspecting calls to intrinsic functions.
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, InsertPosition InsertBefore=nullptr)
The landingpad instruction holds all of the information necessary to generate correct exception handl...
bool isCleanup() const
Return 'true' if this landingpad instruction is a cleanup.
unsigned getNumClauses() const
Get the number of clauses for this landing pad.
static LandingPadInst * Create(Type *RetTy, unsigned NumReservedClauses, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedClauses is a hint for the number of incoming clauses that this landingpad w...
void addClause(Constant *ClauseVal)
Add a catch or filter clause to the landing pad.
bool isCatch(unsigned Idx) const
Return 'true' if the clause and index Idx is a catch clause.
bool isFilter(unsigned Idx) const
Return 'true' if the clause and index Idx is a filter clause.
Constant * getClause(unsigned Idx) const
Get the value of the clause at index Idx.
void setCleanup(bool V)
Indicate that this landingpad instruction is a cleanup.
A function/module analysis which provides an empty LastRunTrackingInfo.
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
An instruction for reading from memory.
const MDOperand & getOperand(unsigned I) const
unsigned getNumOperands() const
Return number of MDNode operands.
Tracking metadata reference owned by Metadata.
This is the common base class for memset/memcpy/memmove.
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
Root of the metadata hierarchy.
This class represents min/max intrinsics.
static ICmpInst::Predicate getPredicate(Intrinsic::ID ID)
Returns the comparison predicate underlying the intrinsic.
A Module instance is used to store all the information related to an LLVM module.
MDNode * getScopeList() const
OptimizationRemarkEmitter legacy analysis pass.
The optimization diagnostic interface.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
op_range incoming_values()
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
In order to facilitate speculative execution, many instructions do not invoke immediate undefined beh...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
bool hasProfileSummary() const
Returns true if profile summary is available.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Return a value (possibly void), from a function.
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, InsertPosition InsertBefore=nullptr)
This class represents a cast from signed integer to floating point.
This class represents the LLVM 'select' instruction.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, Instruction *MDFrom=nullptr)
This instruction constructs a fixed permutation of two input vectors.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
StringRef - Represent a constant reference to a string, i.e.
TargetFolder - Create constants with target dependent folding.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool has(LibFunc F) const
Tests whether a library function is available.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
std::optional< Instruction * > instCombineIntrinsic(InstCombiner &IC, IntrinsicInst &II) const
Targets can implement their own combinations for target-specific intrinsics.
std::optional< Value * > simplifyDemandedVectorEltsIntrinsic(InstCombiner &IC, IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts, APInt &UndefElts2, APInt &UndefElts3, std::function< void(Instruction *, unsigned, APInt, APInt &)> SimplifyAndSetOp) const
Can be used to implement target-specific instruction combining.
std::optional< Value * > simplifyDemandedUseBitsIntrinsic(InstCombiner &IC, IntrinsicInst &II, APInt DemandedMask, KnownBits &Known, bool &KnownBitsComputed) const
Can be used to implement target-specific instruction combining.
bool isValidAddrSpaceCast(unsigned FromAS, unsigned ToAS) const
Query the target whether the specified address space cast from FromAS to ToAS is valid.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
const fltSemantics & getFltSemantics() const
bool isVectorTy() const
True if this is an instance of VectorType.
static IntegerType * getInt1Ty(LLVMContext &C)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isStructTy() const
True if this is an instance of StructType.
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
bool isScalableTy(SmallPtrSetImpl< const Type * > &Visited) const
Return true if this is a type whose size is a known multiple of vscale.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
This class represents a cast unsigned integer to floating point.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
bool isDroppable() const
A droppable user is a user for which uses can be dropped without affecting correctness and should be ...
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
bool hasOneUser() const
Return true if there is exactly one user of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVMContext & getContext() const
All values hold a context through their type.
uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool &CanBeFreed) const
Returns the number of bytes known to be dereferenceable for the pointer value.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
constexpr ScalarTy getFixedValue() const
constexpr bool isZero() const
An efficient, type-erasing, non-owning reference to a callable.
Type * getIndexedType() const
const ParentTy * getParent() const
reverse_self_iterator getReverseIterator()
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isNoFPClassCompatibleType(Type *Ty)
Returns true if this is a type legal for the 'nofpclass' attribute.
@ C
The default llvm calling convention, compatible with C.
Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
class_match< PoisonValue > m_Poison()
Match an arbitrary poison constant.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
PtrAdd_match< PointerOpTy, OffsetOpTy > m_PtrAdd(const PointerOpTy &PointerOp, const OffsetOpTy &OffsetOp)
Matches GEP with i8 source element type.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
CmpClass_match< LHS, RHS, FCmpInst > m_FCmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)
Matches Trunc.
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
br_match m_UnconditionalBr(BasicBlock *&Succ)
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
bool match(Val *V, const Pattern &P)
BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)
Matches integer division operations.
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
DisjointOr_match< LHS, RHS > m_DisjointOr(const LHS &L, const RHS &R)
constantexpr_match m_ConstantExpr()
Match a constant expression or a constant that contains a constant expression.
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of non-negative values.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
apint_match m_APIntAllowPoison(const APInt *&Res)
Match APInt while allowing poison in splat vector constants.
OneUse_match< T > m_OneUse(const T &SubPattern)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
SpecificCmpClass_match< LHS, RHS, ICmpInst > m_SpecificICmp(CmpPredicate MatchPred, const LHS &L, const RHS &R)
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
match_combine_or< BinaryOp_match< LHS, RHS, Instruction::Add >, DisjointOr_match< LHS, RHS > > m_AddLike(const LHS &L, const RHS &R)
Match either "add" or "or disjoint".
CastInst_match< OpTy, UIToFPInst > m_UIToFP(const OpTy &Op)
CastOperator_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
match_combine_or< CastInst_match< OpTy, SExtInst >, NNegZExt_match< OpTy > > m_SExtLike(const OpTy &Op)
Match either "sext" or "zext nneg".
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
CastInst_match< OpTy, SIToFPInst > m_SIToFP(const OpTy &Op)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
cstfp_pred_ty< is_non_zero_fp > m_NonZeroFP()
Match a floating-point non-zero.
m_Intrinsic_Ty< Opnd0 >::Ty m_VecReverse(const Opnd0 &Op0)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > > > m_MaxOrMin(const LHS &L, const RHS &R)
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID)
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Value * simplifyGEPInst(Type *SrcTy, Value *Ptr, ArrayRef< Value * > Indices, GEPNoWrapFlags NW, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
bool succ_empty(const Instruction *I)
Value * simplifyFreezeInst(Value *Op, const SimplifyQuery &Q)
Given an operand for a Freeze, see if we can fold the result.
FunctionPass * createInstructionCombiningPass()
bool isSafeToSpeculativelyExecuteWithVariableReplaced(const Instruction *I)
Don't use information from its non-constant operands.
std::pair< unsigned, unsigned > removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than its terminator and any present EH pad instructi...
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
void salvageDebugInfoForDbgValues(Instruction &I, ArrayRef< DbgVariableIntrinsic * > Insns, ArrayRef< DbgVariableRecord * > DPInsns)
Implementation of salvageDebugInfo, applying only to instructions in Insns, rather than all debug use...
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the debug info intrinsics describing a value.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
auto successors(const MachineBasicBlock *BB)
bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI)
Return true if this is a call to an allocation function that does not have side effects that we are r...
std::optional< StringRef > getAllocationFamily(const Value *I, const TargetLibraryInfo *TLI)
If a function is part of an allocation family (e.g.
Value * lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, const TargetLibraryInfo *TLI, bool MustSucceed)
Try to turn a call to @llvm.objectsize into an integer value of the given Type.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Value * simplifyInstructionWithOperands(Instruction *I, ArrayRef< Value * > NewOps, const SimplifyQuery &Q)
Like simplifyInstruction but the operands of I are replaced with NewOps.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
gep_type_iterator gep_type_end(const User *GEP)
Value * getReallocatedOperand(const CallBase *CB)
If this is a call to a realloc function, return the reallocated operand.
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc,...
bool handleUnreachableTerminator(Instruction *I, SmallVectorImpl< Value * > &PoisonedValues)
If a terminator in an unreachable basic block has an operand of type Instruction, transform it into p...
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Fold the constant using the specified DataLayout.
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
Value * emitGEPOffset(IRBuilderBase *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
constexpr unsigned MaxAnalysisRecursionDepth
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
bool LowerDbgDeclare(Function &F)
Lowers llvm.dbg.declare intrinsics into appropriate set of llvm.dbg.value intrinsics.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value that has an associated llvm....
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
canCreateUndefOrPoison returns true if Op can create undef or poison from non-undef & non-poison oper...
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Value * simplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an ExtractValueInst, fold the result or return null.
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)
Point debug users of From to To or salvage them.
bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
constexpr int PoisonMaskElem
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
@ Or
Bitwise or logical OR of integers.
DWARFExpression::Operation Op
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
constexpr unsigned BitWidth
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
gep_type_iterator gep_type_begin(const User *GEP)
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
void initializeInstCombine(PassRegistry &)
Initialize all passes linked into the InstCombine library.
void initializeInstructionCombiningPassPass(PassRegistry &)
Constant * ConstantFoldBinaryInstruction(unsigned Opcode, Constant *V1, Constant *V2)
std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static unsigned int semanticsPrecision(const fltSemantics &)
unsigned countMinLeadingOnes() const
Returns the minimum number of leading one bits.
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
A CRTP mix-in to automatically provide informational APIs needed for passes.
SimplifyQuery getWithInstruction(const Instruction *I) const
SimplifyQuery getWithoutUndef() const