Go to the documentation of this file.
64 using namespace PatternMatch;
66 #define DEBUG_TYPE "reassociate"
68 STATISTIC(NumChanged,
"Number of insts reassociated");
69 STATISTIC(NumAnnihil,
"Number of expr tree annihilated");
70 STATISTIC(NumFactor ,
"Number of multiplies factored");
77 << *Ops[0].Op->getType() <<
'\t';
78 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i) {
80 Ops[
i].Op->printAsOperand(
dbgs(),
false,
M);
81 dbgs() <<
", #" << Ops[
i].Rank <<
"] ";
98 bool isInvalid()
const {
return SymbolicPart ==
nullptr; }
112 unsigned SymbolicRank;
117 assert(!isa<ConstantInt>(V) &&
"No ConstantInt");
122 if (
I && (
I->getOpcode() == Instruction::Or ||
123 I->getOpcode() == Instruction::And)) {
124 Value *V0 =
I->getOperand(0);
125 Value *V1 =
I->getOperand(1);
133 isOr = (
I->getOpcode() == Instruction::Or);
147 auto *
I = dyn_cast<Instruction>(V);
148 if (
I &&
I->hasOneUse() &&
I->getOpcode() == Opcode)
149 if (!isa<FPMathOperator>(
I) ||
I->isFast())
150 return cast<BinaryOperator>(
I);
156 auto *
I = dyn_cast<Instruction>(V);
157 if (
I &&
I->hasOneUse() &&
158 (
I->getOpcode() == Opcode1 ||
I->getOpcode() == Opcode2))
159 if (!isa<FPMathOperator>(
I) ||
I->isFast())
160 return cast<BinaryOperator>(
I);
164 void ReassociatePass::BuildRankMap(
Function &
F,
169 for (
auto &
Arg :
F.args()) {
170 ValueRankMap[&
Arg] = ++Rank;
177 unsigned BBRank = RankMap[
BB] = ++Rank << 16;
184 ValueRankMap[&
I] = ++BBRank;
188 unsigned ReassociatePass::getRank(
Value *V) {
191 if (isa<Argument>(V))
return ValueRankMap[V];
195 if (
unsigned Rank = ValueRankMap[
I])
202 unsigned Rank = 0, MaxRank = RankMap[
I->getParent()];
203 for (
unsigned i = 0,
e =
I->getNumOperands();
i !=
e && Rank != MaxRank; ++
i)
204 Rank =
std::max(Rank, getRank(
I->getOperand(
i)));
215 return ValueRankMap[
I] = Rank;
219 void ReassociatePass::canonicalizeOperands(
Instruction *
I) {
220 assert(isa<BinaryOperator>(
I) &&
"Expected binary operator.");
221 assert(
I->isCommutative() &&
"Expected commutative operator.");
227 if (isa<Constant>(
LHS) || getRank(
RHS) < getRank(
LHS))
228 cast<BinaryOperator>(
I)->swapOperands();
237 BinaryOperator::CreateFAdd(S1, S2,
Name, InsertBefore);
249 BinaryOperator::CreateFMul(S1, S2,
Name, InsertBefore);
260 if (
auto *FMFSource = dyn_cast<Instruction>(FlagsOp))
263 return UnaryOperator::CreateFNeg(S1,
Name, InsertBefore);
268 assert((isa<UnaryOperator>(Neg) || isa<BinaryOperator>(Neg)) &&
269 "Expected a Negate!");
271 unsigned OpNo = isa<BinaryOperator>(Neg) ? 1 : 0;
311 if (
RHS.isMinValue())
314 if (
LHS.isMinValue()) {
340 "Unknown associative operation!");
341 unsigned Bitwidth =
LHS.getBitWidth();
355 APInt Threshold = CM + Bitwidth;
356 assert(
LHS.ult(Threshold) &&
RHS.ult(Threshold) &&
"Weights not reduced!");
359 while (
LHS.uge(Threshold))
365 unsigned Threshold = CM + Bitwidth;
366 assert(
LHS.getZExtValue() < Threshold &&
RHS.getZExtValue() < Threshold &&
367 "Weights not reduced!");
368 unsigned Total =
LHS.getZExtValue() +
RHS.getZExtValue();
369 while (Total >= Threshold)
452 assert((isa<UnaryOperator>(
I) || isa<BinaryOperator>(
I)) &&
453 "Expected a UnaryOperator or BinaryOperator!");
455 unsigned Bitwidth =
I->getType()->getScalarType()->getPrimitiveSizeInBits();
456 unsigned Opcode =
I->getOpcode();
457 assert(
I->isAssociative() &&
I->isCommutative() &&
458 "Expected an associative and commutative operation!");
471 Worklist.push_back(std::make_pair(
I,
APInt(Bitwidth, 1)));
472 bool Changed =
false;
496 while (!Worklist.empty()) {
500 for (
unsigned OpIdx = 0; OpIdx <
I->getNumOperands(); ++OpIdx) {
504 assert(!
Op->use_empty() &&
"No uses, so how did we get to it?!");
511 Worklist.push_back(std::make_pair(BO, Weight));
516 LeafMap::iterator It = Leaves.find(
Op);
517 if (It == Leaves.end()) {
520 if (!
Op->hasOneUse()) {
524 <<
"ADD USES LEAF: " << *
Op <<
" (" << Weight <<
")\n");
525 LeafOrder.push_back(
Op);
533 "In leaf map but not visited!");
538 #if 0 // TODO: Re-enable once PR13021 is fixed.
541 assert(!
Op->hasOneUse() &&
"Only one use, but we got here twice!");
551 Worklist.push_back(std::make_pair(BO, It->second));
559 if (!
Op->hasOneUse())
573 || (isa<FPMathOperator>(
Op) &&
574 !cast<Instruction>(
Op)->isFast())) &&
575 "Should have been handled above!");
576 assert(
Op->hasOneUse() &&
"Has uses outside the expression tree!");
584 <<
"MORPH LEAF: " << *
Op <<
" (" << Weight <<
") TO ");
587 Worklist.push_back(std::make_pair(Tmp, Weight));
596 LeafOrder.push_back(
Op);
603 for (
unsigned i = 0,
e = LeafOrder.size();
i !=
e; ++
i) {
605 LeafMap::iterator It = Leaves.find(V);
606 if (It == Leaves.end())
610 APInt Weight = It->second;
616 Ops.push_back(std::make_pair(V, Weight));
624 assert(Identity &&
"Associative operation without identity!");
635 assert(Ops.size() > 1 &&
"Single values should be used directly!");
649 unsigned Opcode =
I->getOpcode();
663 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i)
670 for (
unsigned i = 0; ; ++
i) {
674 if (
i+2 == Ops.size()) {
675 Value *NewLHS = Ops[
i].Op;
676 Value *NewRHS = Ops[
i+1].Op;
677 Value *OldLHS =
Op->getOperand(0);
678 Value *OldRHS =
Op->getOperand(1);
680 if (NewLHS == OldLHS && NewRHS == OldRHS)
684 if (NewLHS == OldRHS && NewRHS == OldLHS) {
697 if (NewLHS != OldLHS) {
699 if (BO && !NotRewritable.
count(BO))
700 NodesToRewrite.push_back(BO);
701 Op->setOperand(0, NewLHS);
703 if (NewRHS != OldRHS) {
705 if (BO && !NotRewritable.
count(BO))
706 NodesToRewrite.push_back(BO);
707 Op->setOperand(1, NewRHS);
711 ExpressionChanged =
Op;
720 Value *NewRHS = Ops[
i].Op;
721 if (NewRHS !=
Op->getOperand(1)) {
723 if (NewRHS ==
Op->getOperand(0)) {
730 if (BO && !NotRewritable.
count(BO))
731 NodesToRewrite.push_back(BO);
732 Op->setOperand(1, NewRHS);
733 ExpressionChanged =
Op;
744 if (BO && !NotRewritable.
count(BO)) {
757 if (NodesToRewrite.empty()) {
768 Op->setOperand(0, NewOp);
770 ExpressionChanged =
Op;
780 if (ExpressionChanged)
783 if (isa<FPMathOperator>(
I)) {
790 if (ExpressionChanged ==
I)
799 ExpressionChanged = cast<BinaryOperator>(*ExpressionChanged->
user_begin());
803 for (
unsigned i = 0,
e = NodesToRewrite.size();
i !=
e; ++
i)
804 RedoInsts.insert(NodesToRewrite[
i]);
816 if (
auto *
C = dyn_cast<Constant>(V))
835 I->setHasNoUnsignedWrap(
false);
836 I->setHasNoSignedWrap(
false);
845 I->setName(
I->getName()+
".neg");
869 bool FoundCatchSwitch =
false;
872 if (
Instruction *InstInput = dyn_cast<Instruction>(V)) {
873 if (
InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) {
874 InsertPt = II->getNormalDest()->begin();
876 InsertPt = ++InstInput->getIterator();
883 while (InsertPt !=
BB->end() && (isa<PHINode>(InsertPt) ||
884 InsertPt->isEHPad())) {
885 if (isa<CatchSwitchInst>(InsertPt))
888 FoundCatchSwitch =
true;
899 if (FoundCatchSwitch)
903 if (TheNeg->
getOpcode() == Instruction::Sub) {
909 ToRedo.insert(TheNeg);
916 ToRedo.insert(NewNeg);
929 auto Enqueue = [&](
Value *V) {
930 auto *
I = dyn_cast<Instruction>(V);
943 while (!Worklist.empty()) {
947 switch (
I->getOpcode()) {
948 case Instruction::Or:
955 case Instruction::Shl:
956 case Instruction::ZExt:
958 if (!Enqueue(
I->getOperand(0)))
1003 New->setHasNoSignedWrap();
1004 New->setHasNoUnsignedWrap();
1008 Or->replaceAllUsesWith(New);
1009 New->setDebugLoc(
Or->getDebugLoc());
1011 LLVM_DEBUG(
dbgs() <<
"Converted or into an add: " << *New <<
'\n');
1071 auto *SA = cast<ConstantInt>(Shl->
getOperand(1));
1087 bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
1088 bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
1090 if (NSW && (NUW || SA->getValue().ult(
BitWidth - 1)))
1101 unsigned XRank = Ops[
i].Rank;
1102 unsigned e = Ops.size();
1103 for (
unsigned j =
i+1;
j !=
e && Ops[
j].Rank == XRank; ++
j) {
1108 if (
I1->isIdenticalTo(I2))
1112 for (
unsigned j =
i-1;
j != ~0U && Ops[
j].Rank == XRank; --
j) {
1117 if (
I1->isIdenticalTo(I2))
1127 if (Ops.size() == 1)
return Ops.back();
1146 for (
unsigned i = 0,
e = Tree.size();
i !=
e; ++
i) {
1148 Factors.
append(
E.second.getZExtValue(),
1152 bool FoundFactor =
false;
1153 bool NeedsNegate =
false;
1154 for (
unsigned i = 0,
e = Factors.size();
i !=
e; ++
i) {
1157 Factors.
erase(Factors.begin()+
i);
1164 if (FC1->getValue() == -FC2->getValue()) {
1165 FoundFactor = NeedsNegate =
true;
1166 Factors.
erase(Factors.begin()+
i);
1170 if (
ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[
i].
Op)) {
1171 const APFloat &F1 = FC1->getValueAPF();
1172 APFloat F2(FC2->getValueAPF());
1175 FoundFactor = NeedsNegate =
true;
1176 Factors.
erase(Factors.begin() +
i);
1185 RewriteExprTree(BO, Factors);
1193 if (Factors.size() == 1) {
1194 RedoInsts.insert(BO);
1197 RewriteExprTree(BO, Factors);
1202 V =
CreateNeg(V,
"neg", &*InsertPt, BO);
1215 Factors.push_back(V);
1231 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i) {
1238 if (Opcode == Instruction::And)
1241 if (Opcode == Instruction::Or)
1249 if (
i+1 != Ops.size() && Ops[
i+1].Op == Ops[
i].Op) {
1250 if (Opcode == Instruction::And || Opcode == Instruction::Or) {
1252 Ops.
erase(Ops.begin()+
i);
1259 assert(Opcode == Instruction::Xor);
1264 Ops.
erase(Ops.begin()+
i, Ops.begin()+
i+2);
1278 const APInt &ConstOpnd) {
1311 if (
C1 != ConstOpnd)
1320 RedoInsts.insert(
T);
1340 int DeadInstNum = 1;
1361 if (!C3.isZero() && !C3.isAllOnes()) {
1363 if (NewInstNum > DeadInstNum)
1379 if (NewInstNum > DeadInstNum)
1397 RedoInsts.insert(
T);
1399 RedoInsts.insert(
T);
1412 if (Ops.size() == 1)
1417 Type *Ty = Ops[0].Op->getType();
1421 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i) {
1429 O.setSymbolicRank(getRank(
O.getSymbolicPart()));
1439 for (
unsigned i = 0,
e = Opnds.size();
i !=
e; ++
i)
1440 OpndPtrs.push_back(&Opnds[
i]);
1456 return LHS->getSymbolicRank() <
RHS->getSymbolicRank();
1461 bool Changed =
false;
1462 for (
unsigned i = 0,
e = Opnds.size();
i <
e;
i++) {
1468 if (!ConstOpnd.
isZero() && CombineXorOpnd(
I, CurrOpnd, ConstOpnd, CV)) {
1478 if (!PrevOpnd || CurrOpnd->
getSymbolicPart() != PrevOpnd->getSymbolicPart()) {
1479 PrevOpnd = CurrOpnd;
1485 if (CombineXorOpnd(
I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
1490 PrevOpnd = CurrOpnd;
1502 for (
unsigned int i = 0,
e = Opnds.size();
i <
e;
i++) {
1509 if (!ConstOpnd.
isZero()) {
1514 unsigned Sz = Ops.size();
1516 return Ops.back().Op;
1536 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i) {
1537 Value *TheOp = Ops[
i].Op;
1541 if (
i+1 != Ops.size() && Ops[
i+1].Op == TheOp) {
1543 unsigned NumFound = 0;
1545 Ops.
erase(Ops.begin()+
i);
1547 }
while (
i != Ops.size() && Ops[
i].Op == TheOp);
1549 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << NumFound <<
"]: " << *TheOp
1562 RedoInsts.insert(Mul);
1589 if (Ops.size() == 2 &&
1597 Ops.
erase(Ops.begin()+
i);
1602 Ops.
erase(Ops.begin()+FoundX);
1624 unsigned MaxOcc = 0;
1625 Value *MaxOccVal =
nullptr;
1626 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i) {
1635 assert(Factors.size() > 1 &&
"Bad linearize!");
1639 for (
unsigned i = 0,
e = Factors.size();
i !=
e; ++
i) {
1644 unsigned Occ = ++FactorOccurrences[
Factor];
1654 if (CI->isNegative() && !CI->isMinValue(
true)) {
1658 unsigned Occ = ++FactorOccurrences[
Factor];
1665 if (CF->isNegative()) {
1671 unsigned Occ = ++FactorOccurrences[
Factor];
1683 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << MaxOcc <<
"]: " << *MaxOccVal
1692 I->getType()->isIntOrIntVectorTy()
1697 for (
unsigned i = 0;
i != Ops.size(); ++
i) {
1704 if (
Value *V = RemoveFactorFromExpression(Ops[
i].
Op, MaxOccVal)) {
1707 for (
unsigned j = Ops.size();
j !=
i;) {
1709 if (Ops[
j].
Op == Ops[
i].
Op) {
1710 NewMulOps.push_back(V);
1711 Ops.
erase(Ops.begin()+
j);
1721 unsigned NumAddedValues = NewMulOps.size();
1727 assert(NumAddedValues > 1 &&
"Each occurrence should contribute a value");
1728 (void)NumAddedValues;
1730 RedoInsts.insert(
VI);
1737 RedoInsts.insert(
V2);
1768 unsigned FactorPowerSum = 0;
1769 for (
unsigned Idx = 1, Size = Ops.size(); Idx < Size; ++Idx) {
1774 for (; Idx < Size && Ops[Idx].Op ==
Op; ++Idx)
1778 FactorPowerSum += Count;
1785 if (FactorPowerSum < 4)
1790 for (
unsigned Idx = 1; Idx < Ops.size(); ++Idx) {
1795 for (; Idx < Ops.size() && Ops[Idx].
Op ==
Op; ++Idx)
1802 FactorPowerSum += Count;
1803 Factors.push_back(
Factor(
Op, Count));
1804 Ops.
erase(Ops.begin()+Idx, Ops.begin()+Idx+Count);
1809 assert(FactorPowerSum >= 4);
1812 return LHS.Power >
RHS.Power;
1820 if (Ops.size() == 1)
1829 }
while (!Ops.empty());
1843 assert(Factors[0].Power);
1845 for (
unsigned LastIdx = 0, Idx = 1, Size = Factors.size();
1846 Idx < Size && Factors[Idx].Power > 0; ++Idx) {
1847 if (Factors[Idx].Power != Factors[LastIdx].Power) {
1856 InnerProduct.push_back(Factors[LastIdx].
Base);
1858 InnerProduct.push_back(Factors[Idx].
Base);
1860 }
while (Idx < Size && Factors[Idx].Power == Factors[LastIdx].Power);
1866 RedoInsts.insert(
MI);
1874 return LHS.Power == RHS.Power;
1881 for (
unsigned Idx = 0, Size = Factors.size(); Idx != Size; ++Idx) {
1882 if (Factors[Idx].Power & 1)
1883 OuterProduct.push_back(Factors[Idx].
Base);
1884 Factors[Idx].Power >>= 1;
1886 if (Factors[0].Power) {
1887 Value *SquareRoot = buildMinimalMultiplyDAG(
Builder, Factors);
1888 OuterProduct.push_back(SquareRoot);
1889 OuterProduct.push_back(SquareRoot);
1891 if (OuterProduct.size() == 1)
1892 return OuterProduct.front();
1916 if (
auto FPI = dyn_cast<FPMathOperator>(
I))
1917 Builder.setFastMathFlags(FPI->getFastMathFlags());
1933 unsigned Opcode =
I->getOpcode();
1934 while (!Ops.empty() && isa<Constant>(Ops.back().Op)) {
1951 if (Ops.size() == 1)
return Ops[0].Op;
1955 unsigned NumOps = Ops.size();
1958 case Instruction::And:
1959 case Instruction::Or:
1964 case Instruction::Xor:
1965 if (
Value *Result = OptimizeXor(
I, Ops))
1970 case Instruction::FAdd:
1971 if (
Value *Result = OptimizeAdd(
I, Ops))
1976 case Instruction::FMul:
1977 if (
Value *Result = OptimizeMul(
I, Ops))
1982 if (Ops.size() != NumOps)
1983 return OptimizeExpression(
I, Ops);
1989 void ReassociatePass::RecursivelyEraseDeadInsts(
Instruction *
I,
1990 OrderedSet &Insts) {
1993 ValueRankMap.erase(
I);
1995 RedoInsts.remove(
I);
1997 I->eraseFromParent();
2000 if (OpInst->use_empty())
2001 Insts.insert(OpInst);
2011 ValueRankMap.erase(
I);
2012 RedoInsts.remove(
I);
2014 I->eraseFromParent();
2017 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i)
2021 unsigned Opcode =
Op->getOpcode();
2022 while (
Op->hasOneUse() &&
Op->user_back()->getOpcode() == Opcode &&
2024 Op =
Op->user_back();
2031 if (ValueRankMap.find(
Op) != ValueRankMap.end())
2032 RedoInsts.insert(
Op);
2052 switch (
I->getOpcode()) {
2053 case Instruction::FMul:
2059 Candidates.push_back(
I);
2065 case Instruction::FDiv:
2073 Candidates.push_back(
I);
2090 assert((
I->getOpcode() == Instruction::FAdd ||
2091 I->getOpcode() == Instruction::FSub) &&
"Expected fadd/fsub");
2097 if (Candidates.empty())
2103 bool IsFSub =
I->getOpcode() == Instruction::FSub;
2104 bool NeedsSubtract = !IsFSub && Candidates.size() % 2 == 1;
2112 "Expecting only 1 constant operand");
2113 assert(
C->isNegative() &&
"Expected negative FP constant");
2119 "Expecting only 1 constant operand");
2120 assert(
C->isNegative() &&
"Expected negative FP constant");
2125 assert(MadeChange ==
true &&
"Negative constant candidate was not changed");
2128 if (Candidates.size() % 2 == 0)
2133 assert(Candidates.size() % 2 == 1 &&
"Expected odd number");
2137 I->replaceAllUsesWith(NewInst);
2138 RedoInsts.insert(
I);
2139 return dyn_cast<Instruction>(NewInst);
2170 if (!isa<UnaryOperator>(
I) && !isa<BinaryOperator>(
I))
2173 if (
I->getOpcode() == Instruction::Shl && isa<ConstantInt>(
I->getOperand(1)))
2181 RedoInsts.insert(
I);
2189 if (
I->isCommutative())
2190 canonicalizeOperands(
I);
2197 if (
I->getType()->isFPOrFPVectorTy() && !
I->isFast())
2206 if (
I->getType()->isIntegerTy(1))
2211 if (
I->getOpcode() == Instruction::Or &&
2214 I->getModule()->getDataLayout(),
nullptr,
I,
2217 RedoInsts.insert(
I);
2224 if (
I->getOpcode() == Instruction::Sub) {
2227 RedoInsts.insert(
I);
2241 RedoInsts.insert(Tmp);
2243 RedoInsts.insert(
I);
2248 }
else if (
I->getOpcode() == Instruction::FNeg ||
2249 I->getOpcode() == Instruction::FSub) {
2252 RedoInsts.insert(
I);
2258 Value *
Op = isa<BinaryOperator>(
I) ?
I->getOperand(1) :
2268 RedoInsts.insert(Tmp);
2270 RedoInsts.insert(
I);
2278 if (!
I->isAssociative())
return;
2297 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::Sub)
2300 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::FSub)
2303 ReassociateExpression(BO);
2328 if (
Value *V = OptimizeExpression(
I, Ops)) {
2335 I->replaceAllUsesWith(V);
2337 if (
I->getDebugLoc())
2338 VI->setDebugLoc(
I->getDebugLoc());
2339 RedoInsts.insert(
I);
2348 if (
I->hasOneUse()) {
2351 isa<ConstantInt>(Ops.back().Op) &&
2352 cast<ConstantInt>(Ops.back().Op)->isMinusOne()) {
2354 Ops.
insert(Ops.begin(), Tmp);
2355 }
else if (
I->getOpcode() == Instruction::FMul &&
2356 cast<Instruction>(
I->user_back())->getOpcode() ==
2357 Instruction::FAdd &&
2358 isa<ConstantFP>(Ops.back().Op) &&
2359 cast<ConstantFP>(Ops.back().Op)->isExactlyValue(-1.0)) {
2361 Ops.
insert(Ops.begin(), Tmp);
2367 if (Ops.size() == 1) {
2374 I->replaceAllUsesWith(Ops[0].
Op);
2376 OI->setDebugLoc(
I->getDebugLoc());
2377 RedoInsts.insert(
I);
2381 if (Ops.size() > 2 && Ops.size() <= GlobalReassociateLimit) {
2389 unsigned BestRank = 0;
2390 std::pair<unsigned, unsigned> BestPair;
2391 unsigned Idx =
I->getOpcode() - Instruction::BinaryOpsBegin;
2392 for (
unsigned i = 0;
i < Ops.size() - 1; ++
i)
2393 for (
unsigned j =
i + 1;
j < Ops.size(); ++
j) {
2397 if (std::less<Value *>()(Op1, Op0))
2399 auto it = PairMap[Idx].find({Op0, Op1});
2400 if (
it != PairMap[Idx].
end()) {
2406 if (
it->second.isValid())
2407 Score +=
it->second.Score;
2410 unsigned MaxRank =
std::max(Ops[
i].Rank, Ops[
j].Rank);
2411 if (Score > Max || (Score == Max && MaxRank < BestRank)) {
2418 auto Op0 = Ops[BestPair.first];
2419 auto Op1 = Ops[BestPair.second];
2420 Ops.
erase(&Ops[BestPair.second]);
2421 Ops.
erase(&Ops[BestPair.first]);
2428 RewriteExprTree(
I, Ops);
2436 if (!
I.isAssociative())
2440 if (
I.hasOneUse() &&
I.user_back()->getOpcode() ==
I.getOpcode())
2448 while (!Worklist.empty() && Ops.size() <= GlobalReassociateLimit) {
2462 if (Ops.size() > GlobalReassociateLimit)
2466 unsigned BinaryIdx =
I.getOpcode() - Instruction::BinaryOpsBegin;
2468 for (
unsigned i = 0;
i < Ops.size() - 1; ++
i) {
2469 for (
unsigned j =
i + 1;
j < Ops.size(); ++
j) {
2473 if (std::less<Value *>()(Op1, Op0))
2475 if (!Visited.
insert({Op0, Op1}).second)
2477 auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, {Op0, Op1, 1}});
2483 assert(res.first->second.isValid() &&
"WeakVH invalidated");
2484 ++res.first->second.Score;
2500 BuildRankMap(
F, RPOT);
2517 assert(RankMap.count(&*BI) &&
"BB should be ranked.");
2524 assert(II->getParent() == &*BI &&
"Moved to a different block!");
2535 while (!ToRedo.empty()) {
2538 RecursivelyEraseDeadInsts(
I, ToRedo);
2545 while (!RedoInsts.empty()) {
2547 RedoInsts.erase(RedoInsts.begin());
2557 ValueRankMap.clear();
2558 for (
auto &Entry : PairMap)
2583 if (skipFunction(
F))
2587 auto PA = Impl.
run(
F, DummyFAM);
2604 "Reassociate expressions",
false,
false)
2608 return new ReassociateLegacyPass();
A set of analyses that are preserved following a run of a transformation pass.
static bool ShouldBreakUpSubtract(Instruction *Sub)
Return true if we should break up this subtract of X-Y into (X + -Y).
static BinaryOperator * LowerNegateToMultiply(Instruction *Neg)
Replace 0-X with X*-1.
This is an optimization pass for GlobalISel generic memory operations.
iterator erase(const_iterator CI)
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
@ Or
Bitwise or logical OR of integers.
bool mayHaveNonDefUseDependency(const Instruction &I)
Returns true if the result or effects of the given instructions I depend values not reachable through...
bool hasOneUse() const
Return true if there is exactly one use of this value.
InstListType::iterator iterator
Instruction iterators...
const Function * getParent() const
Return the enclosing method, or null if none.
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Reassociate commutative expressions.
instcombine should handle this C2 when C1
static Value * createAndInstr(Instruction *InsertBefore, Value *Opnd, const APInt &ConstOpnd)
Helper function of CombineXorOpnd().
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static bool collectMultiplyFactors(SmallVectorImpl< ValueEntry > &Ops, SmallVectorImpl< Factor > &Factors)
Build up a vector of value/power pairs factoring a product.
const BasicBlock & getEntryBlock() const
apfloat_match m_APFloat(const APFloat *&Res)
Match a ConstantFP or splatted ConstantVector, binding the specified pointer to the contained APFloat...
INITIALIZE_PASS(ReassociateLegacyPass, "reassociate", "Reassociate expressions", false, false) FunctionPass *llvm
bool isFPOrFPVectorTy() const
Return true if this is a FP type or a vector of FP.
The instances of the Type class are immutable: once they are created, they are never changed.
const_iterator end(StringRef path)
Get end iterator over path.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
user_iterator user_begin()
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
LLVM_NODISCARD T pop_back_val()
static Value * EmitAddTreeOfValues(Instruction *I, SmallVectorImpl< WeakTrackingVH > &Ops)
Emit a tree of add instructions, summing Ops together and returning the result.
void setSymbolicRank(unsigned R)
NUW NUW NUW NUW Exact static Exact BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
Convenience struct for specifying and reasoning about fast-math flags.
bool isMinValue() const
Determine if this is the smallest unsigned value.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
This is the shared class of boolean and integer constants.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
static void IncorporateWeight(APInt &LHS, const APInt &RHS, unsigned Opcode)
Add the extra weight 'RHS' to the existing weight 'LHS', reducing the combined weight using any speci...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
static unsigned FindInOperandList(const SmallVectorImpl< ValueEntry > &Ops, unsigned i, Value *X)
Scan backwards and forwards among values with the same rank as element i to see if X exists.
(vector float) vec_cmpeq(*A, *B) C
iterator begin()
Instruction iterator methods.
Represent the analysis usage information of a pass.
static void getNegatibleInsts(Value *V, SmallVectorImpl< Instruction * > &Candidates)
Recursively analyze an expression to build a list of instructions that have negative floating-point c...
static Optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
static Value * OptimizeAndOrXor(unsigned Opcode, SmallVectorImpl< ValueEntry > &Ops)
Optimize a series of operands to an 'and', 'or', or 'xor' instruction.
bool isNilpotent() const
Return true if the instruction is nilpotent:
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Utility class representing a non-constant Xor-operand.
static Constant * getBinOpAbsorber(unsigned Opcode, Type *Ty)
Return the absorbing element for the given binary operation, i.e.
const char * getOpcodeName() const
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
static Constant * getAllOnesValue(Type *Ty)
BinaryOps getOpcode() const
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
STATISTIC(NumFunctions, "Total number of functions")
ConstantFP - Floating Point Values [float, double].
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
std::pair< Value *, APInt > RepeatedValue
unsigned getIntegerBitWidth() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static Constant * getFNeg(Constant *C)
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
void initializeReassociateLegacyPassPass(PassRegistry &)
SetVector< AssertingVH< Instruction >, std::deque< AssertingVH< Instruction > >> OrderedSet
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
static BinaryOperator * ConvertShiftToMul(Instruction *Shl)
If this is a shift of a reassociable multiply or is used by one, change this into a multiply by a con...
This is an important base class in LLVM.
static UnaryOperator * CreateFNegFMF(Value *Op, Instruction *FMFSource, const Twine &Name="", Instruction *InsertBefore=nullptr)
const APInt & getConstPart() const
static BinaryOperator * isReassociableOp(Value *V, unsigned Opcode)
Return true if V is an instruction of the specified opcode and if it only has one use.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, ScalarEvolution *SE, LoopInfo *LI)
isInteresting - Test whether the given expression is "interesting" when used by the given expression,...
Legacy wrapper pass to provide the BasicAAResult object.
static Instruction * CreateNeg(Value *S1, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.
void clearSubclassOptionalData()
Clear the optional flags contained in this value.
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Value * NegateValue(Value *V, Instruction *BI, ReassociatePass::OrderedSet &ToRedo)
Insert instructions before the instruction pointed to by BI, that computes the negative version of th...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
bool isIdempotent() const
Return true if the instruction is idempotent:
bool getBoolValue() const
Convert APInt to a boolean value.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static unsigned CarmichaelShift(unsigned Bitwidth)
Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael function.
A Module instance is used to store all the information related to an LLVM module.
Value * getSymbolicPart() const
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Class for arbitrary precision integers.
void setOperand(unsigned i, Value *Val)
static void PrintOps(Instruction *I, const SmallVectorImpl< ValueEntry > &Ops)
Print out the expression identified in the Ops list.
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 any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
static BinaryOperator * convertOrWithNoCommonBitsToAdd(Instruction *Or)
If we have (X|Y), and iff X and Y have no common bits set, transform this into (X+Y) to allow arithme...
void setPreservesCFG()
This function should be called by the pass, iff they do not:
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
static void FindSingleUseMultiplyFactors(Value *V, SmallVectorImpl< Value * > &Factors)
If V is a single-use multiply, recursively add its operands as factors, otherwise add V to the list o...
Type * getType() const
All values are typed, get the type of this value.
Represents analyses that only rely on functions' control flow.
unsigned getSymbolicRank() const
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Common base class shared among various IRBuilders.
self_iterator getIterator()
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
StringRef getName() const
Return a constant reference to the value's name.
FunctionPass * createReassociatePass()
static bool runOnFunction(Function &F, bool PostInlining)
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
void stable_sort(R &&Range)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Should compile to something r4 addze r3 instead we get
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
constexpr unsigned BitWidth
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
auto unique(Range &&R, Predicate P)
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in @llvm.dbg intrinsics with undef.
void preserveSet()
Mark an analysis set as preserved.
static bool LinearizeExprTree(Instruction *I, SmallVectorImpl< RepeatedValue > &Ops)
Given an associative binary expression, return the leaf nodes in Ops along with their weights (how ma...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
const BasicBlock * getParent() const
void deleteValue()
Delete a pointer to a generic Value.
Legacy wrapper pass to provide the GlobalsAAResult object.
BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)
Matches a register negated by a G_SUB.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
void takeName(Value *V)
Transfer the name from V to this value.
Value * getOperand(unsigned i) const
void reserve(size_type N)
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Utility class representing a base and exponent pair which form one factor of some product.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
static Value * buildMultiplyTree(IRBuilderBase &Builder, SmallVectorImpl< Value * > &Ops)
Build a tree of multiplies, computing the product of Ops.
LLVM Value Representation.
static BinaryOperator * BreakUpSubtract(Instruction *Sub, ReassociatePass::OrderedSet &ToRedo)
If we have (X-Y), and if either X is an add, or if this is only used by an add, transform this into (...
iterator_range< user_iterator > users()
static bool shouldConvertOrWithNoCommonBitsToAdd(Instruction *Or)
Return true if it may be profitable to convert this (X|Y) into (X+Y).
static bool isLoadCombineCandidate(Instruction *Or)
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
reference emplace_back(ArgTypes &&... Args)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
iterator insert(iterator I, T &&Elt)
@ Undef
Value of the register doesn't matter.