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;
384 assert((isa<UnaryOperator>(
I) || isa<BinaryOperator>(
I)) &&
385 "Expected a UnaryOperator or BinaryOperator!");
387 unsigned Opcode =
I->getOpcode();
388 assert(
I->isAssociative() &&
I->isCommutative() &&
389 "Expected an associative and commutative operation!");
403 bool Changed =
false;
428 while (!Worklist.
empty()) {
432 if (isa<OverflowingBinaryOperator>(
I)) {
433 Flags.HasNUW &=
I->hasNoUnsignedWrap();
434 Flags.HasNSW &=
I->hasNoSignedWrap();
437 for (
unsigned OpIdx = 0; OpIdx <
I->getNumOperands(); ++OpIdx) {
440 assert(!
Op->use_empty() &&
"No uses, so how did we get to it?!");
447 Worklist.
push_back(std::make_pair(BO, Weight));
452 LeafMap::iterator It = Leaves.find(
Op);
453 if (It == Leaves.end()) {
456 if (!
Op->hasOneUse()) {
460 <<
"ADD USES LEAF: " << *
Op <<
" (" << Weight <<
")\n");
469 "In leaf map but not visited!");
472 It->second += Weight;
473 assert(It->second >= Weight &&
"Weight overflows");
477 if (!
Op->hasOneUse())
491 || (isa<FPMathOperator>(
Op) &&
493 "Should have been handled above!");
494 assert(
Op->hasOneUse() &&
"Has uses outside the expression tree!");
506 <<
"MORPH LEAF: " << *
Op <<
" (" << Weight <<
") TO ");
530 for (
Value *V : LeafOrder) {
531 LeafMap::iterator It = Leaves.find(V);
532 if (It == Leaves.end())
539 Ops.
push_back(std::make_pair(V, Weight));
540 if (Opcode == Instruction::Add && Flags.AllKnownNonNegative && Flags.HasNSW)
549 assert(Identity &&
"Associative operation without identity!");
561 assert(Ops.
size() > 1 &&
"Single values should be used directly!");
575 unsigned Opcode =
I->getOpcode();
589 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
597 *ExpressionChangedEnd =
nullptr;
598 for (
unsigned i = 0; ; ++i) {
602 if (i+2 == Ops.
size()) {
603 Value *NewLHS = Ops[i].Op;
604 Value *NewRHS = Ops[i+1].Op;
605 Value *OldLHS =
Op->getOperand(0);
606 Value *OldRHS =
Op->getOperand(1);
608 if (NewLHS == OldLHS && NewRHS == OldRHS)
612 if (NewLHS == OldRHS && NewRHS == OldLHS) {
625 if (NewLHS != OldLHS) {
627 if (BO && !NotRewritable.
count(BO))
629 Op->setOperand(0, NewLHS);
631 if (NewRHS != OldRHS) {
633 if (BO && !NotRewritable.
count(BO))
635 Op->setOperand(1, NewRHS);
639 ExpressionChangedStart =
Op;
640 if (!ExpressionChangedEnd)
641 ExpressionChangedEnd =
Op;
650 Value *NewRHS = Ops[i].Op;
651 if (NewRHS !=
Op->getOperand(1)) {
653 if (NewRHS ==
Op->getOperand(0)) {
660 if (BO && !NotRewritable.
count(BO))
662 Op->setOperand(1, NewRHS);
663 ExpressionChangedStart =
Op;
664 if (!ExpressionChangedEnd)
665 ExpressionChangedEnd =
Op;
676 if (BO && !NotRewritable.
count(BO)) {
689 if (NodesToRewrite.
empty()) {
692 Poison,
"",
I->getIterator());
693 if (isa<FPMathOperator>(NewOp))
700 Op->setOperand(0, NewOp);
702 ExpressionChangedStart =
Op;
703 if (!ExpressionChangedEnd)
704 ExpressionChangedEnd =
Op;
714 if (ExpressionChangedStart) {
715 bool ClearFlags =
true;
719 if (isa<FPMathOperator>(
I)) {
728 if (ExpressionChangedStart->
getOpcode() == Instruction::Add) {
737 if (ExpressionChangedStart == ExpressionChangedEnd)
739 if (ExpressionChangedStart ==
I)
750 ExpressionChangedStart =
751 cast<BinaryOperator>(*ExpressionChangedStart->
user_begin());
756 for (
unsigned i = 0, e = NodesToRewrite.
size(); i != e; ++i)
757 RedoInsts.insert(NodesToRewrite[i]);
769 if (
auto *
C = dyn_cast<Constant>(V)) {
771 Constant *Res =
C->getType()->isFPOrFPVectorTy()
792 if (
I->getOpcode() == Instruction::Add) {
793 I->setHasNoUnsignedWrap(
false);
794 I->setHasNoSignedWrap(
false);
803 I->setName(
I->getName()+
".neg");
813 for (
User *U : V->users()) {
826 C->containsUndefOrPoisonElement())
835 if (
Instruction *InstInput = dyn_cast<Instruction>(V)) {
836 auto InsertPtOpt = InstInput->getInsertionPointAfterDef();
839 InsertPt = *InsertPtOpt;
850 if (TheNeg->
getParent() != InsertPt->getParent())
852 TheNeg->
moveBefore(*InsertPt->getParent(), InsertPt);
854 if (TheNeg->
getOpcode() == Instruction::Sub) {
881 auto Enqueue = [&](
Value *V) {
882 auto *
I = dyn_cast<Instruction>(V);
895 while (!Worklist.
empty()) {
899 switch (
I->getOpcode()) {
900 case Instruction::Or:
907 case Instruction::Shl:
908 case Instruction::ZExt:
910 if (!Enqueue(
I->getOperand(0)))
914 case Instruction::Load:
932 for (
auto Op : {Instruction::Add, Instruction::Sub, Instruction::Mul,
954 Or->getIterator(),
Or);
955 New->setHasNoSignedWrap();
956 New->setHasNoUnsignedWrap();
960 Or->replaceAllUsesWith(New);
961 New->setDebugLoc(
Or->getDebugLoc());
963 LLVM_DEBUG(
dbgs() <<
"Converted or into an add: " << *New <<
'\n');
1024 auto *SA = cast<ConstantInt>(Shl->
getOperand(1));
1026 assert(MulCst &&
"Constant folding of immediate constants failed");
1041 bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
1042 bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
1044 if (NSW && (NUW || SA->getValue().ult(
BitWidth - 1)))
1045 Mul->setHasNoSignedWrap(
true);
1046 Mul->setHasNoUnsignedWrap(NUW);
1055 unsigned XRank = Ops[i].Rank;
1056 unsigned e = Ops.
size();
1057 for (
unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {
1062 if (I1->isIdenticalTo(I2))
1066 for (
unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {
1071 if (I1->isIdenticalTo(I2))
1081 if (Ops.
size() == 1)
return Ops.
back();
1085 return CreateAdd(V2, V1,
"reass.add", It, &*It);
1101 for (
unsigned i = 0, e = Tree.
size(); i != e; ++i) {
1106 bool FoundFactor =
false;
1107 bool NeedsNegate =
false;
1108 for (
unsigned i = 0, e = Factors.
size(); i != e; ++i) {
1117 if (
ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].
Op))
1118 if (FC1->getValue() == -FC2->getValue()) {
1119 FoundFactor = NeedsNegate =
true;
1124 if (
ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[i].
Op)) {
1125 const APFloat &F1 = FC1->getValueAPF();
1126 APFloat F2(FC2->getValueAPF());
1129 FoundFactor = NeedsNegate =
true;
1139 RewriteExprTree(BO, Factors, Flags);
1147 if (Factors.
size() == 1) {
1148 RedoInsts.insert(BO);
1151 RewriteExprTree(BO, Factors, Flags);
1185 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1192 if (Opcode == Instruction::And)
1195 if (Opcode == Instruction::Or)
1203 if (i+1 != Ops.
size() && Ops[i+1].Op == Ops[i].Op) {
1204 if (Opcode == Instruction::And || Opcode == Instruction::Or) {
1213 assert(Opcode == Instruction::Xor);
1232 const APInt &ConstOpnd) {
1240 Opnd, ConstantInt::get(Opnd->
getType(), ConstOpnd),
"and.ra",
1242 I->setDebugLoc(InsertBefore->getDebugLoc());
1265 if (C1 != ConstOpnd)
1274 RedoInsts.insert(
T);
1294 int DeadInstNum = 1;
1312 APInt C3((~C1) ^ C2);
1315 if (!C3.isZero() && !C3.isAllOnes()) {
1317 if (NewInstNum > DeadInstNum)
1333 if (NewInstNum > DeadInstNum)
1351 RedoInsts.insert(
T);
1353 RedoInsts.insert(
T);
1366 if (Ops.
size() == 1)
1371 Type *Ty = Ops[0].Op->getType();
1375 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1383 O.setSymbolicRank(getRank(
O.getSymbolicPart()));
1393 for (
unsigned i = 0, e = Opnds.
size(); i != e; ++i)
1410 return LHS->getSymbolicRank() <
RHS->getSymbolicRank();
1415 bool Changed =
false;
1416 for (
unsigned i = 0, e = Opnds.
size(); i < e; i++) {
1417 XorOpnd *CurrOpnd = OpndPtrs[i];
1422 if (!ConstOpnd.
isZero() &&
1423 CombineXorOpnd(
I->getIterator(), CurrOpnd, ConstOpnd, CV)) {
1433 if (!PrevOpnd || CurrOpnd->
getSymbolicPart() != PrevOpnd->getSymbolicPart()) {
1434 PrevOpnd = CurrOpnd;
1440 if (CombineXorOpnd(
I->getIterator(), CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
1445 PrevOpnd = CurrOpnd;
1457 for (
const XorOpnd &O : Opnds) {
1463 if (!ConstOpnd.
isZero()) {
1464 Value *
C = ConstantInt::get(Ty, ConstOpnd);
1468 unsigned Sz = Ops.
size();
1470 return Ops.
back().Op;
1473 return ConstantInt::get(Ty, ConstOpnd);
1490 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1491 Value *TheOp = Ops[i].Op;
1495 if (i+1 != Ops.
size() && Ops[i+1].Op == TheOp) {
1497 unsigned NumFound = 0;
1501 }
while (i != Ops.
size() && Ops[i].Op == TheOp);
1503 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << NumFound <<
"]: " << *TheOp
1510 ConstantInt::get(Ty, NumFound) :
ConstantFP::
get(Ty, NumFound);
1516 RedoInsts.insert(
Mul);
1543 if (Ops.
size() == 2 &&
1578 unsigned MaxOcc = 0;
1579 Value *MaxOccVal =
nullptr;
1580 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1589 assert(Factors.
size() > 1 &&
"Bad linearize!");
1597 unsigned Occ = ++FactorOccurrences[
Factor];
1607 if (CI->isNegative() && !CI->isMinValue(
true)) {
1608 Factor = ConstantInt::get(CI->getContext(), -CI->getValue());
1611 unsigned Occ = ++FactorOccurrences[
Factor];
1618 if (CF->isNegative()) {
1621 Factor = ConstantFP::get(CF->getContext(),
F);
1624 unsigned Occ = ++FactorOccurrences[
Factor];
1636 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << MaxOcc <<
"]: " << *MaxOccVal
1645 I->getType()->isIntOrIntVectorTy()
1646 ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal)
1650 for (
unsigned i = 0; i != Ops.
size(); ++i) {
1657 if (
Value *V = RemoveFactorFromExpression(Ops[i].
Op, MaxOccVal)) {
1660 for (
unsigned j = Ops.
size(); j != i;) {
1662 if (Ops[j].
Op == Ops[i].
Op) {
1674 unsigned NumAddedValues = NewMulOps.
size();
1680 assert(NumAddedValues > 1 &&
"Each occurrence should contribute a value");
1681 (void)NumAddedValues;
1683 RedoInsts.insert(VI);
1690 RedoInsts.insert(V2);
1721 unsigned FactorPowerSum = 0;
1731 FactorPowerSum += Count;
1738 if (FactorPowerSum < 4)
1755 FactorPowerSum += Count;
1762 assert(FactorPowerSum >= 4);
1765 return LHS.Power >
RHS.Power;
1773 if (Ops.
size() == 1)
1782 }
while (!Ops.
empty());
1794ReassociatePass::buildMinimalMultiplyDAG(
IRBuilderBase &Builder,
1796 assert(Factors[0].Power);
1798 for (
unsigned LastIdx = 0,
Idx = 1,
Size = Factors.
size();
1800 if (Factors[
Idx].Power != Factors[LastIdx].Power) {
1813 }
while (
Idx <
Size && Factors[
Idx].Power == Factors[LastIdx].Power);
1819 RedoInsts.insert(
MI);
1827 return LHS.Power ==
RHS.Power;
1839 if (Factors[0].Power) {
1840 Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors);
1844 if (OuterProduct.
size() == 1)
1845 return OuterProduct.
front();
1869 if (
auto FPI = dyn_cast<FPMathOperator>(
I))
1872 Value *
V = buildMinimalMultiplyDAG(Builder, Factors);
1887 unsigned Opcode =
I->getOpcode();
1888 while (!Ops.
empty()) {
1889 if (
auto *
C = dyn_cast<Constant>(Ops.
back().Op)) {
1916 if (Ops.
size() == 1)
return Ops[0].Op;
1920 unsigned NumOps = Ops.
size();
1923 case Instruction::And:
1924 case Instruction::Or:
1929 case Instruction::Xor:
1930 if (
Value *Result = OptimizeXor(
I, Ops))
1934 case Instruction::Add:
1935 case Instruction::FAdd:
1936 if (
Value *Result = OptimizeAdd(
I, Ops))
1940 case Instruction::Mul:
1941 case Instruction::FMul:
1942 if (
Value *Result = OptimizeMul(
I, Ops))
1947 if (Ops.
size() != NumOps)
1948 return OptimizeExpression(
I, Ops);
1954void ReassociatePass::RecursivelyEraseDeadInsts(
Instruction *
I,
1955 OrderedSet &Insts) {
1958 ValueRankMap.erase(
I);
1960 RedoInsts.remove(
I);
1962 I->eraseFromParent();
1963 for (
auto *
Op : Ops)
1965 if (OpInst->use_empty())
1966 Insts.insert(OpInst);
1976 ValueRankMap.erase(
I);
1977 RedoInsts.remove(
I);
1979 I->eraseFromParent();
1982 for (
unsigned i = 0, e = Ops.size(); i != e; ++i)
1986 unsigned Opcode =
Op->getOpcode();
1987 while (
Op->hasOneUse() &&
Op->user_back()->getOpcode() == Opcode &&
1989 Op =
Op->user_back();
1996 if (ValueRankMap.contains(
Op))
1997 RedoInsts.insert(
Op);
2017 switch (
I->getOpcode()) {
2018 case Instruction::FMul:
2030 case Instruction::FDiv:
2055 assert((
I->getOpcode() == Instruction::FAdd ||
2056 I->getOpcode() == Instruction::FSub) &&
"Expected fadd/fsub");
2062 if (Candidates.
empty())
2068 bool IsFSub =
I->getOpcode() == Instruction::FSub;
2069 bool NeedsSubtract = !IsFSub && Candidates.
size() % 2 == 1;
2077 "Expecting only 1 constant operand");
2078 assert(
C->isNegative() &&
"Expected negative FP constant");
2079 Negatible->setOperand(0, ConstantFP::get(Negatible->getType(),
abs(*
C)));
2084 "Expecting only 1 constant operand");
2085 assert(
C->isNegative() &&
"Expected negative FP constant");
2086 Negatible->setOperand(1, ConstantFP::get(Negatible->getType(),
abs(*
C)));
2090 assert(MadeChange ==
true &&
"Negative constant candidate was not changed");
2093 if (Candidates.size() % 2 == 0)
2098 assert(Candidates.size() % 2 == 1 &&
"Expected odd number");
2102 I->replaceAllUsesWith(NewInst);
2103 RedoInsts.insert(
I);
2104 return dyn_cast<Instruction>(NewInst);
2135 if (!isa<UnaryOperator>(
I) && !isa<BinaryOperator>(
I))
2138 if (
I->getOpcode() == Instruction::Shl && isa<ConstantInt>(
I->getOperand(1)))
2146 RedoInsts.insert(
I);
2154 if (
I->isCommutative())
2155 canonicalizeOperands(
I);
2172 if (
I->getType()->isIntegerTy(1))
2177 if (
I->getOpcode() == Instruction::Or &&
2179 (cast<PossiblyDisjointInst>(
I)->isDisjoint() ||
2182 nullptr,
nullptr,
I)))) {
2184 RedoInsts.insert(
I);
2191 if (
I->getOpcode() == Instruction::Sub) {
2194 RedoInsts.insert(
I);
2208 RedoInsts.insert(Tmp);
2210 RedoInsts.insert(
I);
2215 }
else if (
I->getOpcode() == Instruction::FNeg ||
2216 I->getOpcode() == Instruction::FSub) {
2219 RedoInsts.insert(
I);
2225 Value *
Op = isa<BinaryOperator>(
I) ?
I->getOperand(1) :
2235 RedoInsts.insert(Tmp);
2237 RedoInsts.insert(
I);
2245 if (!
I->isAssociative())
return;
2264 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::Sub)
2267 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::FSub)
2270 ReassociateExpression(BO);
2296 if (
Value *V = OptimizeExpression(
I, Ops)) {
2303 I->replaceAllUsesWith(V);
2305 if (
I->getDebugLoc())
2306 VI->setDebugLoc(
I->getDebugLoc());
2307 RedoInsts.insert(
I);
2316 if (
I->hasOneUse()) {
2317 if (
I->getOpcode() == Instruction::Mul &&
2318 cast<Instruction>(
I->user_back())->getOpcode() == Instruction::Add &&
2319 isa<ConstantInt>(Ops.
back().Op) &&
2320 cast<ConstantInt>(Ops.
back().Op)->isMinusOne()) {
2323 }
else if (
I->getOpcode() == Instruction::FMul &&
2324 cast<Instruction>(
I->user_back())->getOpcode() ==
2325 Instruction::FAdd &&
2326 isa<ConstantFP>(Ops.
back().Op) &&
2327 cast<ConstantFP>(Ops.
back().Op)->isExactlyValue(-1.0)) {
2335 if (Ops.
size() == 1) {
2342 I->replaceAllUsesWith(Ops[0].
Op);
2344 OI->setDebugLoc(
I->getDebugLoc());
2345 RedoInsts.insert(
I);
2349 if (Ops.
size() > 2 && Ops.
size() <= GlobalReassociateLimit) {
2357 unsigned BestRank = 0;
2358 std::pair<unsigned, unsigned> BestPair;
2359 unsigned Idx =
I->getOpcode() - Instruction::BinaryOpsBegin;
2360 unsigned LimitIdx = 0;
2370 int StartIdx = Ops.
size() - 1;
2375 for (
int i = StartIdx - 1; i != -1; --i) {
2376 const Value *Val = Ops[i].Op;
2377 const auto *CurrLeafInstr = dyn_cast<Instruction>(Val);
2379 if (!CurrLeafInstr) {
2398 SeenBB = &
I->getParent()->getParent()->getEntryBlock();
2404 FirstSeenBB = SeenBB;
2407 if (FirstSeenBB != SeenBB) {
2413 << LimitIdx <<
", " << StartIdx <<
"]\n");
2418 for (
unsigned i = Ops.
size() - 1; i > LimitIdx; --i) {
2420 for (
int j = i - 1;
j >= (int)LimitIdx; --
j) {
2422 Value *Op0 = Ops[i].Op;
2424 if (std::less<Value *>()(Op1, Op0))
2426 auto it = PairMap[
Idx].find({Op0, Op1});
2427 if (it != PairMap[
Idx].
end()) {
2433 if (it->second.isValid())
2434 Score += it->second.Score;
2437 unsigned MaxRank = std::max(Ops[i].Rank, Ops[j].Rank);
2451 if (Score > Max || (Score == Max && MaxRank < BestRank)) {
2459 auto Op0 = Ops[BestPair.first];
2460 auto Op1 = Ops[BestPair.second];
2461 Ops.
erase(&Ops[BestPair.second]);
2462 Ops.
erase(&Ops[BestPair.first]);
2471 RewriteExprTree(
I, Ops, Flags);
2479 if (!
I.isAssociative() || !
I.isBinaryOp())
2483 if (
I.hasOneUse() &&
I.user_back()->getOpcode() ==
I.getOpcode())
2491 while (!Worklist.
empty() && Ops.
size() <= GlobalReassociateLimit) {
2505 if (Ops.
size() > GlobalReassociateLimit)
2509 unsigned BinaryIdx =
I.getOpcode() - Instruction::BinaryOpsBegin;
2511 for (
unsigned i = 0; i < Ops.
size() - 1; ++i) {
2512 for (
unsigned j = i + 1;
j < Ops.
size(); ++
j) {
2514 Value *Op0 = Ops[i];
2516 if (std::less<Value *>()(Op1, Op0))
2518 if (!Visited.
insert({Op0, Op1}).second)
2520 auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, {Op0, Op1, 1}});
2526 assert(res.first->second.isValid() &&
"WeakVH invalidated");
2527 ++res.first->second.Score;
2543 BuildRankMap(
F, RPOT);
2560 assert(RankMap.count(&*BI) &&
"BB should be ranked.");
2567 assert(
II->getParent() == &*BI &&
"Moved to a different block!");
2578 while (!ToRedo.
empty()) {
2581 RecursivelyEraseDeadInsts(
I, ToRedo);
2588 while (!RedoInsts.empty()) {
2590 RedoInsts.erase(RedoInsts.begin());
2600 ValueRankMap.clear();
2601 for (
auto &Entry : PairMap)
2626 if (skipFunction(
F))
2630 auto PA = Impl.
run(
F, DummyFAM);
2644char ReassociateLegacyPass::ID = 0;
2647 "Reassociate expressions",
false,
false)
2651 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)
uint64_t IntrinsicInst * II
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 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...
std::pair< Value *, uint64_t > RepeatedValue
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 LinearizeExprTree(Instruction *I, SmallVectorImpl< RepeatedValue > &Ops, ReassociatePass::OrderedSet &ToRedo, reassociate::OverflowTracking &Flags)
Given an associative binary expression, return the leaf nodes in Ops along with their weights (how ma...
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 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 getBoolValue() const
Convert APInt to a boolean value.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
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 * CreateNeg(Value *Op, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
BinaryOps getOpcode() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
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 * 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.
void dropLocation()
Drop the instruction's debug location.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
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...
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.
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.
const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
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.
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="", InsertPosition InsertBefore=nullptr)
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.
const ParentTy * getParent() const
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'.
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.
auto unique(Range &&R, Predicate P)
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 isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
bool mayHaveNonDefUseDependency(const Instruction &I)
Returns true if the result or effects of the given instructions I depend values not reachable through...
Constant * ConstantFoldBinaryInstruction(unsigned Opcode, Constant *V1, Constant *V2)
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.