65using namespace PatternMatch;
67#define DEBUG_TYPE "reassociate"
69STATISTIC(NumChanged,
"Number of insts reassociated");
70STATISTIC(NumAnnihil,
"Number of expr tree annihilated");
71STATISTIC(NumFactor ,
"Number of multiplies factored");
78 << *Ops[0].Op->getType() <<
'\t';
79 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
81 Ops[i].Op->printAsOperand(
dbgs(),
false, M);
82 dbgs() <<
", #" << Ops[i].Rank <<
"] ";
99 bool isInvalid()
const {
return SymbolicPart ==
nullptr; }
113 unsigned SymbolicRank;
118 assert(!isa<ConstantInt>(V) &&
"No ConstantInt");
123 if (
I && (
I->getOpcode() == Instruction::Or ||
124 I->getOpcode() == Instruction::And)) {
125 Value *V0 =
I->getOperand(0);
126 Value *V1 =
I->getOperand(1);
134 isOr = (
I->getOpcode() == Instruction::Or);
150 assert(
I && isa<FPMathOperator>(
I) &&
"Should only check FP ops");
151 return I->hasAllowReassoc() &&
I->hasNoSignedZeros();
157 auto *BO = dyn_cast<BinaryOperator>(V);
158 if (BO && BO->hasOneUse() && BO->getOpcode() == Opcode)
166 auto *BO = dyn_cast<BinaryOperator>(V);
167 if (BO && BO->hasOneUse() &&
168 (BO->getOpcode() == Opcode1 || BO->getOpcode() == Opcode2))
174void ReassociatePass::BuildRankMap(
Function &
F,
179 for (
auto &
Arg :
F.args()) {
180 ValueRankMap[&
Arg] = ++Rank;
187 unsigned BBRank = RankMap[BB] = ++Rank << 16;
194 ValueRankMap[&
I] = ++BBRank;
198unsigned ReassociatePass::getRank(
Value *V) {
201 if (isa<Argument>(V))
return ValueRankMap[
V];
205 if (
unsigned Rank = ValueRankMap[
I])
212 unsigned Rank = 0, MaxRank = RankMap[
I->getParent()];
213 for (
unsigned i = 0, e =
I->getNumOperands(); i != e && Rank != MaxRank; ++i)
214 Rank = std::max(Rank, getRank(
I->getOperand(i)));
222 LLVM_DEBUG(
dbgs() <<
"Calculated Rank[" <<
V->getName() <<
"] = " << Rank
225 return ValueRankMap[
I] = Rank;
229void ReassociatePass::canonicalizeOperands(
Instruction *
I) {
230 assert(isa<BinaryOperator>(
I) &&
"Expected binary operator.");
231 assert(
I->isCommutative() &&
"Expected commutative operator.");
235 if (LHS == RHS || isa<Constant>(RHS))
237 if (isa<Constant>(LHS) || getRank(RHS) < getRank(LHS))
238 cast<BinaryOperator>(
I)->swapOperands();
244 return BinaryOperator::CreateAdd(S1, S2,
Name, InsertBefore);
247 BinaryOperator::CreateFAdd(S1, S2,
Name, InsertBefore);
256 return BinaryOperator::CreateMul(S1, S2,
Name, InsertBefore);
259 BinaryOperator::CreateFMul(S1, S2,
Name, InsertBefore);
270 if (
auto *FMFSource = dyn_cast<Instruction>(FlagsOp))
273 return UnaryOperator::CreateFNeg(S1,
Name, InsertBefore);
278 assert((isa<UnaryOperator>(Neg) || isa<BinaryOperator>(Neg)) &&
279 "Expected a Negate!");
281 unsigned OpNo = isa<BinaryOperator>(Neg) ? 1 : 0;
321 if (
RHS.isMinValue())
324 if (
LHS.isMinValue()) {
343 if (Opcode == Instruction::Add || Opcode == Instruction::FAdd) {
349 assert((Opcode == Instruction::Mul || Opcode == Instruction::FMul) &&
350 "Unknown associative operation!");
351 unsigned Bitwidth =
LHS.getBitWidth();
365 APInt Threshold = CM + Bitwidth;
366 assert(
LHS.ult(Threshold) &&
RHS.ult(Threshold) &&
"Weights not reduced!");
369 while (
LHS.uge(Threshold))
375 unsigned Threshold = CM + Bitwidth;
376 assert(
LHS.getZExtValue() < Threshold &&
RHS.getZExtValue() < Threshold &&
377 "Weights not reduced!");
378 unsigned Total =
LHS.getZExtValue() +
RHS.getZExtValue();
379 while (
Total >= Threshold)
463 assert((isa<UnaryOperator>(
I) || isa<BinaryOperator>(
I)) &&
464 "Expected a UnaryOperator or BinaryOperator!");
466 unsigned Bitwidth =
I->getType()->getScalarType()->getPrimitiveSizeInBits();
467 unsigned Opcode =
I->getOpcode();
468 assert(
I->isAssociative() &&
I->isCommutative() &&
469 "Expected an associative and commutative operation!");
483 bool Changed =
false;
507 while (!Worklist.
empty()) {
511 for (
unsigned OpIdx = 0; OpIdx <
I->getNumOperands(); ++OpIdx) {
512 Value *Op =
I->getOperand(OpIdx);
514 LLVM_DEBUG(
dbgs() <<
"OPERAND: " << *Op <<
" (" << Weight <<
")\n");
515 assert(!Op->use_empty() &&
"No uses, so how did we get to it?!");
520 assert(Visited.
insert(Op).second &&
"Not first visit!");
521 LLVM_DEBUG(
dbgs() <<
"DIRECT ADD: " << *Op <<
" (" << Weight <<
")\n");
522 Worklist.
push_back(std::make_pair(BO, Weight));
527 LeafMap::iterator It = Leaves.find(Op);
528 if (It == Leaves.end()) {
530 assert(Visited.
insert(Op).second &&
"Not first visit!");
531 if (!Op->hasOneUse()) {
535 <<
"ADD USES LEAF: " << *Op <<
" (" << Weight <<
")\n");
544 "In leaf map but not visited!");
552 assert(!Op->hasOneUse() &&
"Only one use, but we got here twice!");
561 LLVM_DEBUG(
dbgs() <<
"UNLEAF: " << *Op <<
" (" << It->second <<
")\n");
562 Worklist.
push_back(std::make_pair(BO, It->second));
570 if (!Op->hasOneUse())
582 assert((!isa<Instruction>(Op) ||
583 cast<Instruction>(Op)->
getOpcode() != Opcode
584 || (isa<FPMathOperator>(Op) &&
586 "Should have been handled above!");
587 assert(Op->hasOneUse() &&
"Has uses outside the expression tree!");
599 <<
"MORPH LEAF: " << *Op <<
" (" << Weight <<
") TO ");
614 LLVM_DEBUG(
dbgs() <<
"ADD LEAF: " << *Op <<
" (" << Weight <<
")\n");
623 for (
unsigned i = 0, e = LeafOrder.
size(); i != e; ++i) {
624 Value *V = LeafOrder[i];
625 LeafMap::iterator It = Leaves.find(V);
626 if (It == Leaves.end())
630 APInt Weight = It->second;
636 Ops.
push_back(std::make_pair(V, Weight));
644 assert(Identity &&
"Associative operation without identity!");
655 assert(Ops.
size() > 1 &&
"Single values should be used directly!");
669 unsigned Opcode =
I->getOpcode();
683 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
684 NotRewritable.
insert(Ops[i].Op);
690 for (
unsigned i = 0; ; ++i) {
694 if (i+2 == Ops.
size()) {
695 Value *NewLHS = Ops[i].Op;
696 Value *NewRHS = Ops[i+1].Op;
697 Value *OldLHS =
Op->getOperand(0);
698 Value *OldRHS =
Op->getOperand(1);
700 if (NewLHS == OldLHS && NewRHS == OldRHS)
704 if (NewLHS == OldRHS && NewRHS == OldLHS) {
717 if (NewLHS != OldLHS) {
719 if (BO && !NotRewritable.
count(BO))
721 Op->setOperand(0, NewLHS);
723 if (NewRHS != OldRHS) {
725 if (BO && !NotRewritable.
count(BO))
727 Op->setOperand(1, NewRHS);
731 ExpressionChanged =
Op;
740 Value *NewRHS = Ops[i].Op;
741 if (NewRHS !=
Op->getOperand(1)) {
743 if (NewRHS ==
Op->getOperand(0)) {
750 if (BO && !NotRewritable.
count(BO))
752 Op->setOperand(1, NewRHS);
753 ExpressionChanged =
Op;
764 if (BO && !NotRewritable.
count(BO)) {
777 if (NodesToRewrite.
empty()) {
780 Undef, Undef,
"",
I);
781 if (isa<FPMathOperator>(NewOp))
788 Op->setOperand(0, NewOp);
790 ExpressionChanged =
Op;
800 if (ExpressionChanged)
803 if (isa<FPMathOperator>(
I)) {
810 if (ExpressionChanged ==
I)
819 ExpressionChanged = cast<BinaryOperator>(*ExpressionChanged->
user_begin());
823 for (
unsigned i = 0, e = NodesToRewrite.
size(); i != e; ++i)
824 RedoInsts.insert(NodesToRewrite[i]);
836 if (
auto *
C = dyn_cast<Constant>(V)) {
838 Constant *Res =
C->getType()->isFPOrFPVectorTy()
859 if (
I->getOpcode() == Instruction::Add) {
860 I->setHasNoUnsignedWrap(
false);
861 I->setHasNoSignedWrap(
false);
870 I->setName(
I->getName()+
".neg");
880 for (
User *U : V->users()) {
893 C->containsUndefOrPoisonElement())
902 if (
Instruction *InstInput = dyn_cast<Instruction>(V)) {
911 if (TheNeg->
getOpcode() == Instruction::Sub) {
937 auto Enqueue = [&](
Value *V) {
938 auto *
I = dyn_cast<Instruction>(V);
951 while (!Worklist.
empty()) {
955 switch (
I->getOpcode()) {
956 case Instruction::Or:
958 for (
Value *Op :
I->operands())
963 case Instruction::Shl:
964 case Instruction::ZExt:
966 if (!Enqueue(
I->getOperand(0)))
970 case Instruction::Load:
988 for (
auto Op : {Instruction::Add, Instruction::Sub, Instruction::Mul,
1011 New->setHasNoSignedWrap();
1012 New->setHasNoUnsignedWrap();
1016 Or->replaceAllUsesWith(New);
1017 New->setDebugLoc(
Or->getDebugLoc());
1019 LLVM_DEBUG(
dbgs() <<
"Converted or into an add: " << *New <<
'\n');
1079 auto *SA = cast<ConstantInt>(Shl->
getOperand(1));
1083 BinaryOperator::CreateMul(Shl->
getOperand(0), MulCst,
"", Shl);
1095 bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
1096 bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
1098 if (NSW && (NUW || SA->getValue().ult(
BitWidth - 1)))
1099 Mul->setHasNoSignedWrap(
true);
1100 Mul->setHasNoUnsignedWrap(NUW);
1109 unsigned XRank = Ops[i].Rank;
1110 unsigned e = Ops.
size();
1111 for (
unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {
1114 if (
Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
1116 if (I1->isIdenticalTo(I2))
1120 for (
unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {
1123 if (
Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
1125 if (I1->isIdenticalTo(I2))
1135 if (Ops.
size() == 1)
return Ops.
back();
1154 for (
unsigned i = 0, e = Tree.
size(); i != e; ++i) {
1156 Factors.
append(
E.second.getZExtValue(),
1160 bool FoundFactor =
false;
1161 bool NeedsNegate =
false;
1162 for (
unsigned i = 0, e = Factors.
size(); i != e; ++i) {
1163 if (Factors[i].Op ==
Factor) {
1171 if (
ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op))
1172 if (FC1->getValue() == -FC2->getValue()) {
1173 FoundFactor = NeedsNegate =
true;
1178 if (
ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[i].Op)) {
1179 const APFloat &F1 = FC1->getValueAPF();
1180 APFloat F2(FC2->getValueAPF());
1183 FoundFactor = NeedsNegate =
true;
1193 RewriteExprTree(BO, Factors);
1201 if (Factors.
size() == 1) {
1202 RedoInsts.insert(BO);
1205 RewriteExprTree(BO, Factors);
1239 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1246 if (Opcode == Instruction::And)
1249 if (Opcode == Instruction::Or)
1257 if (i+1 != Ops.
size() && Ops[i+1].Op == Ops[i].Op) {
1258 if (Opcode == Instruction::And || Opcode == Instruction::Or) {
1267 assert(Opcode == Instruction::Xor);
1286 const APInt &ConstOpnd) {
1319 if (C1 != ConstOpnd)
1328 RedoInsts.insert(
T);
1348 int DeadInstNum = 1;
1366 APInt C3((~C1) ^ C2);
1369 if (!C3.isZero() && !C3.isAllOnes()) {
1371 if (NewInstNum > DeadInstNum)
1387 if (NewInstNum > DeadInstNum)
1405 RedoInsts.insert(
T);
1407 RedoInsts.insert(
T);
1420 if (Ops.
size() == 1)
1425 Type *Ty = Ops[0].Op->getType();
1429 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1437 O.setSymbolicRank(getRank(
O.getSymbolicPart()));
1447 for (
unsigned i = 0, e = Opnds.
size(); i != e; ++i)
1464 return LHS->getSymbolicRank() <
RHS->getSymbolicRank();
1469 bool Changed =
false;
1470 for (
unsigned i = 0, e = Opnds.
size(); i < e; i++) {
1471 XorOpnd *CurrOpnd = OpndPtrs[i];
1476 if (!ConstOpnd.
isZero() && CombineXorOpnd(
I, CurrOpnd, ConstOpnd, CV)) {
1486 if (!PrevOpnd || CurrOpnd->
getSymbolicPart() != PrevOpnd->getSymbolicPart()) {
1487 PrevOpnd = CurrOpnd;
1493 if (CombineXorOpnd(
I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
1498 PrevOpnd = CurrOpnd;
1510 for (
unsigned int i = 0, e = Opnds.
size(); i < e; i++) {
1517 if (!ConstOpnd.
isZero()) {
1522 unsigned Sz = Ops.
size();
1524 return Ops.
back().Op;
1544 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1545 Value *TheOp = Ops[i].Op;
1549 if (i+1 != Ops.
size() && Ops[i+1].Op == TheOp) {
1551 unsigned NumFound = 0;
1555 }
while (i != Ops.
size() && Ops[i].Op == TheOp);
1557 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << NumFound <<
"]: " << *TheOp
1570 RedoInsts.insert(
Mul);
1597 if (Ops.
size() == 2 &&
1632 unsigned MaxOcc = 0;
1633 Value *MaxOccVal =
nullptr;
1634 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1643 assert(Factors.
size() > 1 &&
"Bad linearize!");
1647 for (
unsigned i = 0, e = Factors.
size(); i != e; ++i) {
1652 unsigned Occ = ++FactorOccurrences[
Factor];
1662 if (CI->isNegative() && !CI->isMinValue(
true)) {
1666 unsigned Occ = ++FactorOccurrences[
Factor];
1673 if (CF->isNegative()) {
1679 unsigned Occ = ++FactorOccurrences[
Factor];
1691 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << MaxOcc <<
"]: " << *MaxOccVal
1700 I->getType()->isIntOrIntVectorTy()
1701 ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal)
1705 for (
unsigned i = 0; i != Ops.
size(); ++i) {
1712 if (
Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) {
1715 for (
unsigned j = Ops.
size(); j != i;) {
1717 if (Ops[j].Op == Ops[i].Op) {
1729 unsigned NumAddedValues = NewMulOps.
size();
1735 assert(NumAddedValues > 1 &&
"Each occurrence should contribute a value");
1736 (void)NumAddedValues;
1738 RedoInsts.insert(VI);
1745 RedoInsts.insert(V2);
1776 unsigned FactorPowerSum = 0;
1786 FactorPowerSum += Count;
1793 if (FactorPowerSum < 4)
1810 FactorPowerSum += Count;
1817 assert(FactorPowerSum >= 4);
1820 return LHS.Power >
RHS.Power;
1828 if (Ops.
size() == 1)
1837 }
while (!Ops.
empty());
1849ReassociatePass::buildMinimalMultiplyDAG(
IRBuilderBase &Builder,
1851 assert(Factors[0].Power);
1853 for (
unsigned LastIdx = 0,
Idx = 1,
Size = Factors.
size();
1855 if (Factors[
Idx].Power != Factors[LastIdx].Power) {
1868 }
while (
Idx <
Size && Factors[
Idx].Power == Factors[LastIdx].Power);
1874 RedoInsts.insert(
MI);
1882 return LHS.Power == RHS.Power;
1894 if (Factors[0].Power) {
1895 Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors);
1899 if (OuterProduct.
size() == 1)
1900 return OuterProduct.
front();
1924 if (
auto FPI = dyn_cast<FPMathOperator>(
I))
1925 Builder.setFastMathFlags(FPI->getFastMathFlags());
1927 Value *
V = buildMinimalMultiplyDAG(Builder, Factors);
1942 unsigned Opcode =
I->getOpcode();
1943 while (!Ops.
empty()) {
1944 if (
auto *
C = dyn_cast<Constant>(Ops.
back().Op)) {
1971 if (Ops.
size() == 1)
return Ops[0].Op;
1975 unsigned NumOps = Ops.
size();
1978 case Instruction::And:
1979 case Instruction::Or:
1984 case Instruction::Xor:
1985 if (
Value *Result = OptimizeXor(
I, Ops))
1989 case Instruction::Add:
1990 case Instruction::FAdd:
1991 if (
Value *Result = OptimizeAdd(
I, Ops))
1995 case Instruction::Mul:
1996 case Instruction::FMul:
1997 if (
Value *Result = OptimizeMul(
I, Ops))
2002 if (Ops.
size() != NumOps)
2003 return OptimizeExpression(
I, Ops);
2009void ReassociatePass::RecursivelyEraseDeadInsts(
Instruction *
I,
2010 OrderedSet &Insts) {
2013 ValueRankMap.erase(
I);
2015 RedoInsts.remove(
I);
2017 I->eraseFromParent();
2018 for (
auto *Op : Ops)
2019 if (
Instruction *OpInst = dyn_cast<Instruction>(Op))
2020 if (OpInst->use_empty())
2021 Insts.insert(OpInst);
2031 ValueRankMap.erase(
I);
2032 RedoInsts.remove(
I);
2034 I->eraseFromParent();
2037 for (
unsigned i = 0, e = Ops.size(); i != e; ++i)
2038 if (
Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
2041 unsigned Opcode =
Op->getOpcode();
2042 while (
Op->hasOneUse() &&
Op->user_back()->getOpcode() == Opcode &&
2043 Visited.
insert(Op).second)
2044 Op =
Op->user_back();
2051 if (ValueRankMap.contains(Op))
2052 RedoInsts.insert(Op);
2072 switch (
I->getOpcode()) {
2073 case Instruction::FMul:
2085 case Instruction::FDiv:
2110 assert((
I->getOpcode() == Instruction::FAdd ||
2111 I->getOpcode() == Instruction::FSub) &&
"Expected fadd/fsub");
2117 if (Candidates.
empty())
2123 bool IsFSub =
I->getOpcode() == Instruction::FSub;
2124 bool NeedsSubtract = !IsFSub && Candidates.
size() % 2 == 1;
2132 "Expecting only 1 constant operand");
2133 assert(
C->isNegative() &&
"Expected negative FP constant");
2139 "Expecting only 1 constant operand");
2140 assert(
C->isNegative() &&
"Expected negative FP constant");
2145 assert(MadeChange ==
true &&
"Negative constant candidate was not changed");
2148 if (Candidates.size() % 2 == 0)
2153 assert(Candidates.size() % 2 == 1 &&
"Expected odd number");
2155 Value *NewInst = IsFSub ?
Builder.CreateFAddFMF(OtherOp, Op,
I)
2156 :
Builder.CreateFSubFMF(OtherOp, Op,
I);
2157 I->replaceAllUsesWith(NewInst);
2158 RedoInsts.insert(
I);
2159 return dyn_cast<Instruction>(NewInst);
2175 if (
Instruction *R = canonicalizeNegFPConstantsForOp(
I, Op,
X))
2178 if (
Instruction *R = canonicalizeNegFPConstantsForOp(
I, Op,
X))
2181 if (
Instruction *R = canonicalizeNegFPConstantsForOp(
I, Op,
X))
2190 if (!isa<UnaryOperator>(
I) && !isa<BinaryOperator>(
I))
2193 if (
I->getOpcode() == Instruction::Shl && isa<ConstantInt>(
I->getOperand(1)))
2201 RedoInsts.insert(
I);
2209 if (
I->isCommutative())
2210 canonicalizeOperands(
I);
2227 if (
I->getType()->isIntegerTy(1))
2232 if (
I->getOpcode() == Instruction::Or &&
2235 I->getModule()->getDataLayout(),
nullptr,
I,
2238 RedoInsts.insert(
I);
2245 if (
I->getOpcode() == Instruction::Sub) {
2248 RedoInsts.insert(
I);
2262 RedoInsts.insert(Tmp);
2264 RedoInsts.insert(
I);
2269 }
else if (
I->getOpcode() == Instruction::FNeg ||
2270 I->getOpcode() == Instruction::FSub) {
2273 RedoInsts.insert(
I);
2279 Value *
Op = isa<BinaryOperator>(
I) ?
I->getOperand(1) :
2289 RedoInsts.insert(Tmp);
2291 RedoInsts.insert(
I);
2299 if (!
I->isAssociative())
return;
2318 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::Sub)
2321 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::FSub)
2324 ReassociateExpression(BO);
2349 if (
Value *V = OptimizeExpression(
I, Ops)) {
2356 I->replaceAllUsesWith(V);
2358 if (
I->getDebugLoc())
2359 VI->setDebugLoc(
I->getDebugLoc());
2360 RedoInsts.insert(
I);
2369 if (
I->hasOneUse()) {
2370 if (
I->getOpcode() == Instruction::Mul &&
2371 cast<Instruction>(
I->user_back())->getOpcode() == Instruction::Add &&
2372 isa<ConstantInt>(Ops.
back().Op) &&
2373 cast<ConstantInt>(Ops.
back().Op)->isMinusOne()) {
2376 }
else if (
I->getOpcode() == Instruction::FMul &&
2377 cast<Instruction>(
I->user_back())->getOpcode() ==
2378 Instruction::FAdd &&
2379 isa<ConstantFP>(Ops.
back().Op) &&
2380 cast<ConstantFP>(Ops.
back().Op)->isExactlyValue(-1.0)) {
2388 if (Ops.
size() == 1) {
2395 I->replaceAllUsesWith(Ops[0].Op);
2396 if (
Instruction *OI = dyn_cast<Instruction>(Ops[0].Op))
2397 OI->setDebugLoc(
I->getDebugLoc());
2398 RedoInsts.insert(
I);
2402 if (Ops.
size() > 2 && Ops.
size() <= GlobalReassociateLimit) {
2410 unsigned BestRank = 0;
2411 std::pair<unsigned, unsigned> BestPair;
2412 unsigned Idx =
I->getOpcode() - Instruction::BinaryOpsBegin;
2413 for (
unsigned i = 0; i < Ops.
size() - 1; ++i)
2414 for (
unsigned j = i + 1;
j < Ops.
size(); ++
j) {
2416 Value *Op0 = Ops[i].Op;
2418 if (std::less<Value *>()(Op1, Op0))
2420 auto it = PairMap[
Idx].find({Op0, Op1});
2421 if (it != PairMap[
Idx].
end()) {
2427 if (it->second.isValid())
2428 Score += it->second.Score;
2431 unsigned MaxRank = std::max(Ops[i].Rank, Ops[j].Rank);
2432 if (Score > Max || (Score == Max && MaxRank < BestRank)) {
2439 auto Op0 = Ops[BestPair.first];
2440 auto Op1 = Ops[BestPair.second];
2441 Ops.
erase(&Ops[BestPair.second]);
2442 Ops.
erase(&Ops[BestPair.first]);
2449 RewriteExprTree(
I, Ops);
2457 if (!
I.isAssociative())
2461 if (
I.hasOneUse() &&
I.user_back()->getOpcode() ==
I.getOpcode())
2469 while (!Worklist.
empty() && Ops.
size() <= GlobalReassociateLimit) {
2483 if (Ops.
size() > GlobalReassociateLimit)
2487 unsigned BinaryIdx =
I.getOpcode() - Instruction::BinaryOpsBegin;
2489 for (
unsigned i = 0; i < Ops.
size() - 1; ++i) {
2490 for (
unsigned j = i + 1;
j < Ops.
size(); ++
j) {
2492 Value *Op0 = Ops[i];
2494 if (std::less<Value *>()(Op1, Op0))
2496 if (!Visited.
insert({Op0, Op1}).second)
2498 auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, {Op0, Op1, 1}});
2504 assert(res.first->second.isValid() &&
"WeakVH invalidated");
2505 ++res.first->second.Score;
2521 BuildRankMap(
F, RPOT);
2538 assert(RankMap.count(&*BI) &&
"BB should be ranked.");
2545 assert(II->getParent() == &*BI &&
"Moved to a different block!");
2556 while (!ToRedo.
empty()) {
2559 RecursivelyEraseDeadInsts(
I, ToRedo);
2566 while (!RedoInsts.empty()) {
2568 RedoInsts.erase(RedoInsts.begin());
2578 ValueRankMap.clear();
2579 for (
auto &Entry : PairMap)
2604 if (skipFunction(
F))
2608 auto PA = Impl.
run(
F, DummyFAM);
2622char ReassociateLegacyPass::ID = 0;
2625 "Reassociate expressions",
false,
false)
2629 return new ReassociateLegacyPass();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
This file declares a class to represent arbitrary precision floating point values and provide a varie...
This file implements a class to represent arbitrary precision integral constant values and operations...
This is the interface for LLVM's primary stateless and local alias analysis.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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 defines the DenseMap class.
static bool runOnFunction(Function &F, bool PostInlining)
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
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...
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,...
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
static void PrintOps(Instruction *I, const SmallVectorImpl< ValueEntry > &Ops)
Print out the expression identified in the Ops list.
static bool ShouldBreakUpSubtract(Instruction *Sub)
Return true if we should break up this subtract of X-Y into (X + -Y).
static Value * buildMultiplyTree(IRBuilderBase &Builder, SmallVectorImpl< Value * > &Ops)
Build a tree of multiplies, computing the product of Ops.
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 unsigned CarmichaelShift(unsigned Bitwidth)
Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael function.
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
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 (...
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...
static Value * OptimizeAndOrXor(unsigned Opcode, SmallVectorImpl< ValueEntry > &Ops)
Optimize a series of operands to an 'and', 'or', or 'xor' instruction.
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...
static Instruction * CreateNeg(Value *S1, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
static bool collectMultiplyFactors(SmallVectorImpl< ValueEntry > &Ops, SmallVectorImpl< Factor > &Factors)
Build up a vector of value/power pairs factoring a product.
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...
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.
static BinaryOperator * LowerNegateToMultiply(Instruction *Neg)
Replace 0-X with X*-1.
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.
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 bool LinearizeExprTree(Instruction *I, SmallVectorImpl< RepeatedValue > &Ops, ReassociatePass::OrderedSet &ToRedo)
Given an associative binary expression, return the leaf nodes in Ops along with their weights (how ma...
std::pair< Value *, APInt > RepeatedValue
static bool hasFPAssociativeFlags(Instruction *I)
Return true if I is an instruction with the FastMathFlags that are needed for general reassociation s...
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...
static bool shouldConvertOrWithNoCommonBitsToAdd(Instruction *Or)
Return true if it may be profitable to convert this (X|Y) into (X+Y).
static Value * createAndInstr(Instruction *InsertBefore, Value *Opnd, const APInt &ConstOpnd)
Helper function of CombineXorOpnd().
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
static bool isLoadCombineCandidate(Instruction *Or)
static Value * EmitAddTreeOfValues(Instruction *I, SmallVectorImpl< WeakTrackingVH > &Ops)
Emit a tree of add instructions, summing Ops together and returning the result.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallSet 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 std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
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.
bool isMinValue() const
Determine if this is the smallest unsigned value.
bool getBoolValue() const
Convert APInt to a boolean value.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
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:
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
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.
static 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...
BinaryOps getOpcode() const
Represents analyses that only rely on functions' control flow.
static Constant * getBinOpAbsorber(unsigned Opcode, Type *Ty)
Return the absorbing element for the given binary operation, i.e.
static Constant * getShl(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 HasNUW=false, bool HasNSW=false)
ConstantFP - Floating Point Values [float, double].
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...
This is the shared class of boolean and integer constants.
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.
This is an important base class in LLVM.
static Constant * getAllOnesValue(Type *Ty)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Convenience struct for specifying and reasoning about fast-math flags.
FunctionPass class - This class is used to implement most global optimizations.
const BasicBlock & getEntryBlock() const
Legacy wrapper pass to provide the GlobalsAAResult object.
Common base class shared among various IRBuilders.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
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 andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
const BasicBlock * getParent() const
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
bool isNilpotent() const
Return true if the instruction is nilpotent:
const char * getOpcodeName() const
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Instruction * getInsertionPointAfterDef()
Get the first insertion point at which the result of this instruction is defined.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
bool isIdempotent() const
Return true if the instruction is idempotent:
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
A Module instance is used to store all the information related to an LLVM module.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
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.
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
Reassociate commutative expressions.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
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.
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.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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.
unsigned getIntegerBitWidth() const
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static UnaryOperator * CreateFNegFMF(Value *Op, Instruction *FMFSource, const Twine &Name="", Instruction *InsertBefore=nullptr)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
void clearSubclassOptionalData()
Clear the optional flags contained in this value.
void deleteValue()
Delete a pointer to a generic Value.
void takeName(Value *V)
Transfer the name from V to this value.
self_iterator getIterator()
Utility class representing a non-constant Xor-operand.
Value * getSymbolicPart() const
unsigned getSymbolicRank() const
void setSymbolicRank(unsigned R)
const APInt & getConstPart() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
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.
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
apfloat_match m_APFloat(const APFloat *&Res)
Match a ConstantFP or splatted ConstantVector, binding the specified pointer to the contained APFloat...
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'.
@ Undef
Value of the register doesn't matter.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
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...
APFloat abs(APFloat X)
Returns the absolute value of the argument.
FunctionPass * createReassociatePass()
void initializeReassociateLegacyPassPass(PassRegistry &)
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.
Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
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.
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in @llvm.dbg intrinsics with undef.
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
@ Or
Bitwise or logical OR of integers.
@ Mul
Product of integers.
constexpr unsigned BitWidth
bool mayHaveNonDefUseDependency(const Instruction &I)
Returns true if the result or effects of the given instructions I depend values not reachable through...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Utility class representing a base and exponent pair which form one factor of some product.