66using namespace PatternMatch;
68#define DEBUG_TYPE "reassociate"
70STATISTIC(NumChanged,
"Number of insts reassociated");
71STATISTIC(NumAnnihil,
"Number of expr tree annihilated");
72STATISTIC(NumFactor ,
"Number of multiplies factored");
76 cl::desc(
"Only reorder expressions within a basic block "
77 "when exposing CSE opportunities"),
85 << *Ops[0].Op->getType() <<
'\t';
86 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
88 Ops[i].Op->printAsOperand(
dbgs(),
false, M);
89 dbgs() <<
", #" << Ops[i].Rank <<
"] ";
106 bool isInvalid()
const {
return SymbolicPart ==
nullptr; }
120 unsigned SymbolicRank;
125 assert(!isa<ConstantInt>(V) &&
"No ConstantInt");
130 if (
I && (
I->getOpcode() == Instruction::Or ||
131 I->getOpcode() == Instruction::And)) {
132 Value *V0 =
I->getOperand(0);
133 Value *V1 =
I->getOperand(1);
141 isOr = (
I->getOpcode() == Instruction::Or);
157 assert(
I && isa<FPMathOperator>(
I) &&
"Should only check FP ops");
158 return I->hasAllowReassoc() &&
I->hasNoSignedZeros();
164 auto *BO = dyn_cast<BinaryOperator>(V);
165 if (BO && BO->hasOneUse() && BO->getOpcode() == Opcode)
173 auto *BO = dyn_cast<BinaryOperator>(V);
174 if (BO && BO->hasOneUse() &&
175 (BO->getOpcode() == Opcode1 || BO->getOpcode() == Opcode2))
181void ReassociatePass::BuildRankMap(
Function &
F,
186 for (
auto &Arg :
F.args()) {
187 ValueRankMap[&Arg] = ++Rank;
188 LLVM_DEBUG(
dbgs() <<
"Calculated Rank[" << Arg.getName() <<
"] = " << Rank
194 unsigned BBRank = RankMap[BB] = ++Rank << 16;
201 ValueRankMap[&
I] = ++BBRank;
205unsigned ReassociatePass::getRank(
Value *V) {
208 if (isa<Argument>(V))
return ValueRankMap[
V];
212 if (
unsigned Rank = ValueRankMap[
I])
219 unsigned Rank = 0, MaxRank = RankMap[
I->getParent()];
220 for (
unsigned i = 0, e =
I->getNumOperands(); i != e && Rank != MaxRank; ++i)
221 Rank = std::max(Rank, getRank(
I->getOperand(i)));
229 LLVM_DEBUG(
dbgs() <<
"Calculated Rank[" <<
V->getName() <<
"] = " << Rank
232 return ValueRankMap[
I] = Rank;
236void ReassociatePass::canonicalizeOperands(
Instruction *
I) {
237 assert(isa<BinaryOperator>(
I) &&
"Expected binary operator.");
238 assert(
I->isCommutative() &&
"Expected commutative operator.");
242 if (LHS == RHS || isa<Constant>(RHS))
244 if (isa<Constant>(LHS) || getRank(RHS) < getRank(LHS))
245 cast<BinaryOperator>(
I)->swapOperands();
251 if (
S1->getType()->isIntOrIntVectorTy())
252 return BinaryOperator::CreateAdd(
S1, S2,
Name, InsertBefore);
255 BinaryOperator::CreateFAdd(
S1, S2,
Name, InsertBefore);
264 if (
S1->getType()->isIntOrIntVectorTy())
265 return BinaryOperator::CreateMul(
S1, S2,
Name, InsertBefore);
268 BinaryOperator::CreateFMul(
S1, S2,
Name, InsertBefore);
277 if (
S1->getType()->isIntOrIntVectorTy())
280 if (
auto *FMFSource = dyn_cast<Instruction>(FlagsOp))
283 return UnaryOperator::CreateFNeg(
S1,
Name, InsertBefore);
288 assert((isa<UnaryOperator>(Neg) || isa<BinaryOperator>(Neg)) &&
289 "Expected a Negate!");
291 unsigned OpNo = isa<BinaryOperator>(Neg) ? 1 : 0;
332 if (
RHS.isMinValue())
335 if (
LHS.isMinValue()) {
354 if (Opcode == Instruction::Add || Opcode == Instruction::FAdd) {
360 assert((Opcode == Instruction::Mul || Opcode == Instruction::FMul) &&
361 "Unknown associative operation!");
362 unsigned Bitwidth =
LHS.getBitWidth();
376 APInt Threshold = CM + Bitwidth;
377 assert(
LHS.ult(Threshold) &&
RHS.ult(Threshold) &&
"Weights not reduced!");
380 while (
LHS.uge(Threshold))
386 unsigned Threshold = CM + Bitwidth;
387 assert(
LHS.getZExtValue() < Threshold &&
RHS.getZExtValue() < Threshold &&
388 "Weights not reduced!");
389 unsigned Total =
LHS.getZExtValue() +
RHS.getZExtValue();
390 while (
Total >= Threshold)
475 assert((isa<UnaryOperator>(
I) || isa<BinaryOperator>(
I)) &&
476 "Expected a UnaryOperator or BinaryOperator!");
478 unsigned Bitwidth =
I->getType()->getScalarType()->getPrimitiveSizeInBits();
479 unsigned Opcode =
I->getOpcode();
480 assert(
I->isAssociative() &&
I->isCommutative() &&
481 "Expected an associative and commutative operation!");
495 bool Changed =
false;
519 while (!Worklist.
empty()) {
523 if (isa<OverflowingBinaryOperator>(
I))
524 HasNUW &=
I->hasNoUnsignedWrap();
526 for (
unsigned OpIdx = 0; OpIdx <
I->getNumOperands(); ++OpIdx) {
530 assert(!
Op->use_empty() &&
"No uses, so how did we get to it?!");
537 Worklist.
push_back(std::make_pair(BO, Weight));
542 LeafMap::iterator It = Leaves.find(
Op);
543 if (It == Leaves.end()) {
546 if (!
Op->hasOneUse()) {
550 <<
"ADD USES LEAF: " << *
Op <<
" (" << Weight <<
")\n");
559 "In leaf map but not visited!");
567 assert(!
Op->hasOneUse() &&
"Only one use, but we got here twice!");
577 Worklist.
push_back(std::make_pair(BO, It->second));
585 if (!
Op->hasOneUse())
599 || (isa<FPMathOperator>(
Op) &&
601 "Should have been handled above!");
602 assert(
Op->hasOneUse() &&
"Has uses outside the expression tree!");
614 <<
"MORPH LEAF: " << *
Op <<
" (" << Weight <<
") TO ");
638 for (
Value *V : LeafOrder) {
639 LeafMap::iterator It = Leaves.find(V);
640 if (It == Leaves.end())
644 APInt Weight = It->second;
650 Ops.
push_back(std::make_pair(V, Weight));
658 assert(Identity &&
"Associative operation without identity!");
670 assert(Ops.
size() > 1 &&
"Single values should be used directly!");
684 unsigned Opcode =
I->getOpcode();
698 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
706 *ExpressionChangedEnd =
nullptr;
707 for (
unsigned i = 0; ; ++i) {
711 if (i+2 == Ops.
size()) {
712 Value *NewLHS = Ops[i].Op;
713 Value *NewRHS = Ops[i+1].Op;
714 Value *OldLHS =
Op->getOperand(0);
715 Value *OldRHS =
Op->getOperand(1);
717 if (NewLHS == OldLHS && NewRHS == OldRHS)
721 if (NewLHS == OldRHS && NewRHS == OldLHS) {
734 if (NewLHS != OldLHS) {
736 if (BO && !NotRewritable.
count(BO))
738 Op->setOperand(0, NewLHS);
740 if (NewRHS != OldRHS) {
742 if (BO && !NotRewritable.
count(BO))
744 Op->setOperand(1, NewRHS);
748 ExpressionChangedStart =
Op;
749 if (!ExpressionChangedEnd)
750 ExpressionChangedEnd =
Op;
759 Value *NewRHS = Ops[i].Op;
760 if (NewRHS !=
Op->getOperand(1)) {
762 if (NewRHS ==
Op->getOperand(0)) {
769 if (BO && !NotRewritable.
count(BO))
771 Op->setOperand(1, NewRHS);
772 ExpressionChangedStart =
Op;
773 if (!ExpressionChangedEnd)
774 ExpressionChangedEnd =
Op;
785 if (BO && !NotRewritable.
count(BO)) {
798 if (NodesToRewrite.
empty()) {
801 Undef,
"",
I->getIterator());
802 if (isa<FPMathOperator>(NewOp))
809 Op->setOperand(0, NewOp);
811 ExpressionChangedStart =
Op;
812 if (!ExpressionChangedEnd)
813 ExpressionChangedEnd =
Op;
823 if (ExpressionChangedStart) {
824 bool ClearFlags =
true;
828 if (isa<FPMathOperator>(
I)) {
837 if (HasNUW && ExpressionChangedStart->
getOpcode() == Instruction::Add)
842 if (ExpressionChangedStart == ExpressionChangedEnd)
844 if (ExpressionChangedStart ==
I)
855 ExpressionChangedStart =
856 cast<BinaryOperator>(*ExpressionChangedStart->
user_begin());
861 for (
unsigned i = 0, e = NodesToRewrite.
size(); i != e; ++i)
862 RedoInsts.insert(NodesToRewrite[i]);
874 if (
auto *
C = dyn_cast<Constant>(V)) {
876 Constant *Res =
C->getType()->isFPOrFPVectorTy()
897 if (
I->getOpcode() == Instruction::Add) {
898 I->setHasNoUnsignedWrap(
false);
899 I->setHasNoSignedWrap(
false);
908 I->setName(
I->getName()+
".neg");
918 for (
User *U : V->users()) {
931 C->containsUndefOrPoisonElement())
940 if (
Instruction *InstInput = dyn_cast<Instruction>(V)) {
941 auto InsertPtOpt = InstInput->getInsertionPointAfterDef();
944 InsertPt = *InsertPtOpt;
952 TheNeg->
moveBefore(*InsertPt->getParent(), InsertPt);
953 if (TheNeg->
getOpcode() == Instruction::Sub) {
980 auto Enqueue = [&](
Value *V) {
981 auto *
I = dyn_cast<Instruction>(V);
994 while (!Worklist.
empty()) {
998 switch (
I->getOpcode()) {
999 case Instruction::Or:
1006 case Instruction::Shl:
1007 case Instruction::ZExt:
1009 if (!Enqueue(
I->getOperand(0)))
1013 case Instruction::Load:
1031 for (
auto Op : {Instruction::Add, Instruction::Sub, Instruction::Mul,
1053 Or->getIterator(),
Or);
1054 New->setHasNoSignedWrap();
1055 New->setHasNoUnsignedWrap();
1059 Or->replaceAllUsesWith(New);
1060 New->setDebugLoc(
Or->getDebugLoc());
1062 LLVM_DEBUG(
dbgs() <<
"Converted or into an add: " << *New <<
'\n');
1123 auto *SA = cast<ConstantInt>(Shl->
getOperand(1));
1139 bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
1140 bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
1142 if (NSW && (NUW || SA->getValue().ult(
BitWidth - 1)))
1143 Mul->setHasNoSignedWrap(
true);
1144 Mul->setHasNoUnsignedWrap(NUW);
1153 unsigned XRank = Ops[i].Rank;
1154 unsigned e = Ops.
size();
1155 for (
unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {
1160 if (I1->isIdenticalTo(I2))
1164 for (
unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {
1169 if (I1->isIdenticalTo(I2))
1179 if (Ops.
size() == 1)
return Ops.
back();
1183 return CreateAdd(V2, V1,
"reass.add", It, &*It);
1199 for (
unsigned i = 0, e = Tree.
size(); i != e; ++i) {
1201 Factors.
append(E.second.getZExtValue(),
1205 bool FoundFactor =
false;
1206 bool NeedsNegate =
false;
1207 for (
unsigned i = 0, e = Factors.
size(); i != e; ++i) {
1216 if (
ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].
Op))
1217 if (FC1->getValue() == -FC2->getValue()) {
1218 FoundFactor = NeedsNegate =
true;
1223 if (
ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[i].
Op)) {
1224 const APFloat &F1 = FC1->getValueAPF();
1225 APFloat F2(FC2->getValueAPF());
1228 FoundFactor = NeedsNegate =
true;
1238 RewriteExprTree(BO, Factors, HasNUW);
1246 if (Factors.
size() == 1) {
1247 RedoInsts.insert(BO);
1250 RewriteExprTree(BO, Factors, HasNUW);
1284 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1291 if (Opcode == Instruction::And)
1294 if (Opcode == Instruction::Or)
1302 if (i+1 != Ops.
size() && Ops[i+1].Op == Ops[i].Op) {
1303 if (Opcode == Instruction::And || Opcode == Instruction::Or) {
1312 assert(Opcode == Instruction::Xor);
1331 const APInt &ConstOpnd) {
1339 Opnd, ConstantInt::get(Opnd->
getType(), ConstOpnd),
"and.ra",
1341 I->setDebugLoc(InsertBefore->getDebugLoc());
1364 if (C1 != ConstOpnd)
1373 RedoInsts.insert(
T);
1393 int DeadInstNum = 1;
1411 APInt C3((~C1) ^ C2);
1414 if (!C3.isZero() && !C3.isAllOnes()) {
1416 if (NewInstNum > DeadInstNum)
1432 if (NewInstNum > DeadInstNum)
1450 RedoInsts.insert(
T);
1452 RedoInsts.insert(
T);
1465 if (Ops.
size() == 1)
1470 Type *Ty = Ops[0].Op->getType();
1474 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1482 O.setSymbolicRank(getRank(
O.getSymbolicPart()));
1492 for (
unsigned i = 0, e = Opnds.
size(); i != e; ++i)
1509 return LHS->getSymbolicRank() <
RHS->getSymbolicRank();
1514 bool Changed =
false;
1515 for (
unsigned i = 0, e = Opnds.
size(); i < e; i++) {
1516 XorOpnd *CurrOpnd = OpndPtrs[i];
1521 if (!ConstOpnd.
isZero() &&
1522 CombineXorOpnd(
I->getIterator(), CurrOpnd, ConstOpnd, CV)) {
1532 if (!PrevOpnd || CurrOpnd->
getSymbolicPart() != PrevOpnd->getSymbolicPart()) {
1533 PrevOpnd = CurrOpnd;
1539 if (CombineXorOpnd(
I->getIterator(), CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
1544 PrevOpnd = CurrOpnd;
1556 for (
const XorOpnd &O : Opnds) {
1562 if (!ConstOpnd.
isZero()) {
1563 Value *
C = ConstantInt::get(Ty, ConstOpnd);
1567 unsigned Sz = Ops.
size();
1569 return Ops.
back().Op;
1572 return ConstantInt::get(Ty, ConstOpnd);
1589 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1590 Value *TheOp = Ops[i].Op;
1594 if (i+1 != Ops.
size() && Ops[i+1].Op == TheOp) {
1596 unsigned NumFound = 0;
1600 }
while (i != Ops.
size() && Ops[i].Op == TheOp);
1602 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << NumFound <<
"]: " << *TheOp
1609 ConstantInt::get(Ty, NumFound) :
ConstantFP::
get(Ty, NumFound);
1615 RedoInsts.insert(
Mul);
1642 if (Ops.
size() == 2 &&
1677 unsigned MaxOcc = 0;
1678 Value *MaxOccVal =
nullptr;
1679 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1688 assert(Factors.
size() > 1 &&
"Bad linearize!");
1696 unsigned Occ = ++FactorOccurrences[
Factor];
1706 if (CI->isNegative() && !CI->isMinValue(
true)) {
1707 Factor = ConstantInt::get(CI->getContext(), -CI->getValue());
1710 unsigned Occ = ++FactorOccurrences[
Factor];
1717 if (CF->isNegative()) {
1720 Factor = ConstantFP::get(CF->getContext(),
F);
1723 unsigned Occ = ++FactorOccurrences[
Factor];
1735 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << MaxOcc <<
"]: " << *MaxOccVal
1744 I->getType()->isIntOrIntVectorTy()
1745 ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal)
1749 for (
unsigned i = 0; i != Ops.
size(); ++i) {
1756 if (
Value *V = RemoveFactorFromExpression(Ops[i].
Op, MaxOccVal)) {
1759 for (
unsigned j = Ops.
size(); j != i;) {
1761 if (Ops[j].
Op == Ops[i].
Op) {
1773 unsigned NumAddedValues = NewMulOps.
size();
1779 assert(NumAddedValues > 1 &&
"Each occurrence should contribute a value");
1780 (void)NumAddedValues;
1782 RedoInsts.insert(VI);
1789 RedoInsts.insert(V2);
1820 unsigned FactorPowerSum = 0;
1830 FactorPowerSum += Count;
1837 if (FactorPowerSum < 4)
1854 FactorPowerSum += Count;
1861 assert(FactorPowerSum >= 4);
1864 return LHS.Power >
RHS.Power;
1872 if (Ops.
size() == 1)
1881 }
while (!Ops.
empty());
1893ReassociatePass::buildMinimalMultiplyDAG(
IRBuilderBase &Builder,
1895 assert(Factors[0].Power);
1897 for (
unsigned LastIdx = 0,
Idx = 1,
Size = Factors.
size();
1899 if (Factors[
Idx].Power != Factors[LastIdx].Power) {
1912 }
while (
Idx <
Size && Factors[
Idx].Power == Factors[LastIdx].Power);
1918 RedoInsts.insert(
MI);
1926 return LHS.Power == RHS.Power;
1938 if (Factors[0].Power) {
1939 Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors);
1943 if (OuterProduct.
size() == 1)
1944 return OuterProduct.
front();
1968 if (
auto FPI = dyn_cast<FPMathOperator>(
I))
1971 Value *
V = buildMinimalMultiplyDAG(Builder, Factors);
1986 unsigned Opcode =
I->getOpcode();
1987 while (!Ops.
empty()) {
1988 if (
auto *
C = dyn_cast<Constant>(Ops.
back().Op)) {
2015 if (Ops.
size() == 1)
return Ops[0].Op;
2019 unsigned NumOps = Ops.
size();
2022 case Instruction::And:
2023 case Instruction::Or:
2028 case Instruction::Xor:
2029 if (
Value *Result = OptimizeXor(
I, Ops))
2033 case Instruction::Add:
2034 case Instruction::FAdd:
2035 if (
Value *Result = OptimizeAdd(
I, Ops))
2039 case Instruction::Mul:
2040 case Instruction::FMul:
2041 if (
Value *Result = OptimizeMul(
I, Ops))
2046 if (Ops.
size() != NumOps)
2047 return OptimizeExpression(
I, Ops);
2053void ReassociatePass::RecursivelyEraseDeadInsts(
Instruction *
I,
2054 OrderedSet &Insts) {
2057 ValueRankMap.erase(
I);
2059 RedoInsts.remove(
I);
2061 I->eraseFromParent();
2062 for (
auto *
Op : Ops)
2064 if (OpInst->use_empty())
2065 Insts.insert(OpInst);
2075 ValueRankMap.erase(
I);
2076 RedoInsts.remove(
I);
2078 I->eraseFromParent();
2081 for (
unsigned i = 0, e = Ops.size(); i != e; ++i)
2085 unsigned Opcode =
Op->getOpcode();
2086 while (
Op->hasOneUse() &&
Op->user_back()->getOpcode() == Opcode &&
2088 Op =
Op->user_back();
2095 if (ValueRankMap.contains(
Op))
2096 RedoInsts.insert(
Op);
2116 switch (
I->getOpcode()) {
2117 case Instruction::FMul:
2129 case Instruction::FDiv:
2154 assert((
I->getOpcode() == Instruction::FAdd ||
2155 I->getOpcode() == Instruction::FSub) &&
"Expected fadd/fsub");
2161 if (Candidates.
empty())
2167 bool IsFSub =
I->getOpcode() == Instruction::FSub;
2168 bool NeedsSubtract = !IsFSub && Candidates.
size() % 2 == 1;
2176 "Expecting only 1 constant operand");
2177 assert(
C->isNegative() &&
"Expected negative FP constant");
2178 Negatible->setOperand(0, ConstantFP::get(Negatible->getType(),
abs(*
C)));
2183 "Expecting only 1 constant operand");
2184 assert(
C->isNegative() &&
"Expected negative FP constant");
2185 Negatible->setOperand(1, ConstantFP::get(Negatible->getType(),
abs(*
C)));
2189 assert(MadeChange ==
true &&
"Negative constant candidate was not changed");
2192 if (Candidates.size() % 2 == 0)
2197 assert(Candidates.size() % 2 == 1 &&
"Expected odd number");
2201 I->replaceAllUsesWith(NewInst);
2202 RedoInsts.insert(
I);
2203 return dyn_cast<Instruction>(NewInst);
2234 if (!isa<UnaryOperator>(
I) && !isa<BinaryOperator>(
I))
2237 if (
I->getOpcode() == Instruction::Shl && isa<ConstantInt>(
I->getOperand(1)))
2245 RedoInsts.insert(
I);
2253 if (
I->isCommutative())
2254 canonicalizeOperands(
I);
2271 if (
I->getType()->isIntegerTy(1))
2276 if (
I->getOpcode() == Instruction::Or &&
2278 (cast<PossiblyDisjointInst>(
I)->isDisjoint() ||
2281 nullptr,
nullptr,
I)))) {
2283 RedoInsts.insert(
I);
2290 if (
I->getOpcode() == Instruction::Sub) {
2293 RedoInsts.insert(
I);
2307 RedoInsts.insert(Tmp);
2309 RedoInsts.insert(
I);
2314 }
else if (
I->getOpcode() == Instruction::FNeg ||
2315 I->getOpcode() == Instruction::FSub) {
2318 RedoInsts.insert(
I);
2324 Value *
Op = isa<BinaryOperator>(
I) ?
I->getOperand(1) :
2334 RedoInsts.insert(Tmp);
2336 RedoInsts.insert(
I);
2344 if (!
I->isAssociative())
return;
2363 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::Sub)
2366 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::FSub)
2369 ReassociateExpression(BO);
2381 Ops.
append(E.second.getZExtValue(),
ValueEntry(getRank(E.first), E.first));
2395 if (
Value *V = OptimizeExpression(
I, Ops)) {
2402 I->replaceAllUsesWith(V);
2404 if (
I->getDebugLoc())
2405 VI->setDebugLoc(
I->getDebugLoc());
2406 RedoInsts.insert(
I);
2415 if (
I->hasOneUse()) {
2416 if (
I->getOpcode() == Instruction::Mul &&
2417 cast<Instruction>(
I->user_back())->getOpcode() == Instruction::Add &&
2418 isa<ConstantInt>(Ops.
back().Op) &&
2419 cast<ConstantInt>(Ops.
back().Op)->isMinusOne()) {
2422 }
else if (
I->getOpcode() == Instruction::FMul &&
2423 cast<Instruction>(
I->user_back())->getOpcode() ==
2424 Instruction::FAdd &&
2425 isa<ConstantFP>(Ops.
back().Op) &&
2426 cast<ConstantFP>(Ops.
back().Op)->isExactlyValue(-1.0)) {
2434 if (Ops.
size() == 1) {
2441 I->replaceAllUsesWith(Ops[0].
Op);
2443 OI->setDebugLoc(
I->getDebugLoc());
2444 RedoInsts.insert(
I);
2448 if (Ops.
size() > 2 && Ops.
size() <= GlobalReassociateLimit) {
2456 unsigned BestRank = 0;
2457 std::pair<unsigned, unsigned> BestPair;
2458 unsigned Idx =
I->getOpcode() - Instruction::BinaryOpsBegin;
2459 unsigned LimitIdx = 0;
2469 int StartIdx = Ops.
size() - 1;
2474 for (
int i = StartIdx - 1; i != -1; --i) {
2475 const Value *Val = Ops[i].Op;
2476 const auto *CurrLeafInstr = dyn_cast<Instruction>(Val);
2478 if (!CurrLeafInstr) {
2497 SeenBB = &
I->getParent()->getParent()->getEntryBlock();
2503 FirstSeenBB = SeenBB;
2506 if (FirstSeenBB != SeenBB) {
2512 << LimitIdx <<
", " << StartIdx <<
"]\n");
2517 for (
unsigned i = Ops.
size() - 1; i > LimitIdx; --i) {
2519 for (
int j = i - 1;
j >= (int)LimitIdx; --
j) {
2521 Value *Op0 = Ops[i].Op;
2523 if (std::less<Value *>()(Op1, Op0))
2525 auto it = PairMap[
Idx].find({Op0, Op1});
2526 if (it != PairMap[
Idx].
end()) {
2532 if (it->second.isValid())
2533 Score += it->second.Score;
2536 unsigned MaxRank = std::max(Ops[i].Rank, Ops[j].Rank);
2550 if (Score > Max || (Score == Max && MaxRank < BestRank)) {
2558 auto Op0 = Ops[BestPair.first];
2559 auto Op1 = Ops[BestPair.second];
2560 Ops.
erase(&Ops[BestPair.second]);
2561 Ops.
erase(&Ops[BestPair.first]);
2570 RewriteExprTree(
I, Ops, HasNUW);
2578 if (!
I.isAssociative() || !
I.isBinaryOp())
2582 if (
I.hasOneUse() &&
I.user_back()->getOpcode() ==
I.getOpcode())
2590 while (!Worklist.
empty() && Ops.
size() <= GlobalReassociateLimit) {
2604 if (Ops.
size() > GlobalReassociateLimit)
2608 unsigned BinaryIdx =
I.getOpcode() - Instruction::BinaryOpsBegin;
2610 for (
unsigned i = 0; i < Ops.
size() - 1; ++i) {
2611 for (
unsigned j = i + 1;
j < Ops.
size(); ++
j) {
2613 Value *Op0 = Ops[i];
2615 if (std::less<Value *>()(Op1, Op0))
2617 if (!Visited.
insert({Op0, Op1}).second)
2619 auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, {Op0, Op1, 1}});
2625 assert(res.first->second.isValid() &&
"WeakVH invalidated");
2626 ++res.first->second.Score;
2642 BuildRankMap(
F, RPOT);
2659 assert(RankMap.count(&*BI) &&
"BB should be ranked.");
2666 assert(II->getParent() == &*BI &&
"Moved to a different block!");
2677 while (!ToRedo.
empty()) {
2680 RecursivelyEraseDeadInsts(
I, ToRedo);
2687 while (!RedoInsts.empty()) {
2689 RedoInsts.erase(RedoInsts.begin());
2699 ValueRankMap.clear();
2700 for (
auto &Entry : PairMap)
2725 if (skipFunction(
F))
2729 auto PA = Impl.
run(
F, DummyFAM);
2743char ReassociateLegacyPass::ID = 0;
2746 "Reassociate expressions",
false,
false)
2750 return new ReassociateLegacyPass();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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.
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,...
static bool isReassociableOp(Instruction *I, unsigned IntOpcode, unsigned FPOpcode)
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 Value * EmitAddTreeOfValues(BasicBlock::iterator It, SmallVectorImpl< WeakTrackingVH > &Ops)
Emit a tree of add instructions, summing Ops together and returning the result.
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 BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore, Value *FlagsOp)
static unsigned CarmichaelShift(unsigned Bitwidth)
Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael function.
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 BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator 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 cl::opt< bool > UseCSELocalOpt(DEBUG_TYPE "-use-cse-local", cl::desc("Only reorder expressions within a basic block " "when exposing CSE opportunities"), cl::init(true), cl::Hidden)
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 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, bool &HasNUW)
Given an associative binary expression, return the leaf nodes in Ops along with their weights (how ma...
std::pair< Value *, APInt > RepeatedValue
static Instruction * CreateNeg(Value *S1, const Twine &Name, BasicBlock::iterator InsertBefore, Value *FlagsOp)
static bool hasFPAssociativeFlags(Instruction *I)
Return true if I is an instruction with the FastMathFlags that are needed for general reassociation s...
static Value * createAndInstr(BasicBlock::iterator InsertBefore, Value *Opnd, const APInt &ConstOpnd)
Helper function of CombineXorOpnd().
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 bool isLoadCombineCandidate(Instruction *Or)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static unsigned getFastMathFlags(const MachineInstr &I)
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.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
static BinaryOperator * CreateNeg(Value *Op, const Twine &Name, BasicBlock::iterator InsertBefore)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
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 HasNSW=false)
ConstantFP - Floating Point Values [float, double].
This is the shared class of boolean and integer constants.
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.
This class represents an Operation in the Expression.
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.
Value * CreateFAddFMF(Value *L, Value *R, Instruction *FMFSource, const Twine &Name="")
Copy fast-math-flags from an instruction rather than using the builder's default FMF.
Value * CreateFSubFMF(Value *L, Value *R, Instruction *FMFSource, const Twine &Name="")
Copy fast-math-flags from an instruction rather than using the builder's default FMF.
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Value * CreateFMul(Value *L, Value *R, const Twine &Name="", MDNode *FPMD=nullptr)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
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.
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 empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
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, BasicBlock::iterator InsertBefore)
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.
initializer< Ty > init(const Ty &Val)
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
bool haveNoCommonBitsSet(const WithCache< const Value * > &LHSCache, const WithCache< const Value * > &RHSCache, const SimplifyQuery &SQ)
Return true if LHS and RHS have no common bits set.
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 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.
DWARFExpression::Operation Op
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.