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 return BinaryOperator::CreateAdd(S1, S2,
Name, InsertBefore);
254 BinaryOperator::CreateFAdd(S1, S2,
Name, InsertBefore);
263 return BinaryOperator::CreateMul(S1, S2,
Name, InsertBefore);
266 BinaryOperator::CreateFMul(S1, S2,
Name, InsertBefore);
277 if (
auto *FMFSource = dyn_cast<Instruction>(FlagsOp))
280 return UnaryOperator::CreateFNeg(S1,
Name, InsertBefore);
285 assert((isa<UnaryOperator>(Neg) || isa<BinaryOperator>(Neg)) &&
286 "Expected a Negate!");
288 unsigned OpNo = isa<BinaryOperator>(Neg) ? 1 : 0;
328 if (
RHS.isMinValue())
331 if (
LHS.isMinValue()) {
350 if (
Opcode == Instruction::Add ||
Opcode == Instruction::FAdd) {
357 "Unknown associative operation!");
358 unsigned Bitwidth =
LHS.getBitWidth();
372 APInt Threshold = CM + Bitwidth;
373 assert(
LHS.ult(Threshold) &&
RHS.ult(Threshold) &&
"Weights not reduced!");
376 while (
LHS.uge(Threshold))
382 unsigned Threshold = CM + Bitwidth;
383 assert(
LHS.getZExtValue() < Threshold &&
RHS.getZExtValue() < Threshold &&
384 "Weights not reduced!");
385 unsigned Total =
LHS.getZExtValue() +
RHS.getZExtValue();
386 while (
Total >= Threshold)
470 assert((isa<UnaryOperator>(
I) || isa<BinaryOperator>(
I)) &&
471 "Expected a UnaryOperator or BinaryOperator!");
473 unsigned Bitwidth =
I->getType()->getScalarType()->getPrimitiveSizeInBits();
474 unsigned Opcode =
I->getOpcode();
475 assert(
I->isAssociative() &&
I->isCommutative() &&
476 "Expected an associative and commutative operation!");
490 bool Changed =
false;
514 while (!Worklist.
empty()) {
518 for (
unsigned OpIdx = 0; OpIdx <
I->getNumOperands(); ++OpIdx) {
522 assert(!
Op->use_empty() &&
"No uses, so how did we get to it?!");
529 Worklist.
push_back(std::make_pair(BO, Weight));
534 LeafMap::iterator It = Leaves.find(
Op);
535 if (It == Leaves.end()) {
538 if (!
Op->hasOneUse()) {
542 <<
"ADD USES LEAF: " << *
Op <<
" (" << Weight <<
")\n");
551 "In leaf map but not visited!");
559 assert(!
Op->hasOneUse() &&
"Only one use, but we got here twice!");
569 Worklist.
push_back(std::make_pair(BO, It->second));
577 if (!
Op->hasOneUse())
591 || (isa<FPMathOperator>(
Op) &&
593 "Should have been handled above!");
594 assert(
Op->hasOneUse() &&
"Has uses outside the expression tree!");
606 <<
"MORPH LEAF: " << *
Op <<
" (" << Weight <<
") TO ");
630 for (
Value *V : LeafOrder) {
631 LeafMap::iterator It = Leaves.find(V);
632 if (It == Leaves.end())
636 APInt Weight = It->second;
642 Ops.
push_back(std::make_pair(V, Weight));
650 assert(Identity &&
"Associative operation without identity!");
661 assert(Ops.
size() > 1 &&
"Single values should be used directly!");
675 unsigned Opcode =
I->getOpcode();
689 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
697 *ExpressionChangedEnd =
nullptr;
698 for (
unsigned i = 0; ; ++i) {
702 if (i+2 == Ops.
size()) {
703 Value *NewLHS = Ops[i].Op;
704 Value *NewRHS = Ops[i+1].Op;
705 Value *OldLHS =
Op->getOperand(0);
706 Value *OldRHS =
Op->getOperand(1);
708 if (NewLHS == OldLHS && NewRHS == OldRHS)
712 if (NewLHS == OldRHS && NewRHS == OldLHS) {
725 if (NewLHS != OldLHS) {
727 if (BO && !NotRewritable.
count(BO))
729 Op->setOperand(0, NewLHS);
731 if (NewRHS != OldRHS) {
733 if (BO && !NotRewritable.
count(BO))
735 Op->setOperand(1, NewRHS);
739 ExpressionChangedStart =
Op;
740 if (!ExpressionChangedEnd)
741 ExpressionChangedEnd =
Op;
750 Value *NewRHS = Ops[i].Op;
751 if (NewRHS !=
Op->getOperand(1)) {
753 if (NewRHS ==
Op->getOperand(0)) {
760 if (BO && !NotRewritable.
count(BO))
762 Op->setOperand(1, NewRHS);
763 ExpressionChangedStart =
Op;
764 if (!ExpressionChangedEnd)
765 ExpressionChangedEnd =
Op;
776 if (BO && !NotRewritable.
count(BO)) {
789 if (NodesToRewrite.
empty()) {
792 Undef, Undef,
"",
I);
793 if (isa<FPMathOperator>(NewOp))
800 Op->setOperand(0, NewOp);
802 ExpressionChangedStart =
Op;
803 if (!ExpressionChangedEnd)
804 ExpressionChangedEnd =
Op;
814 if (ExpressionChangedStart) {
815 bool ClearFlags =
true;
819 if (isa<FPMathOperator>(
I)) {
827 if (ExpressionChangedStart == ExpressionChangedEnd)
829 if (ExpressionChangedStart ==
I)
840 ExpressionChangedStart =
841 cast<BinaryOperator>(*ExpressionChangedStart->
user_begin());
846 for (
unsigned i = 0, e = NodesToRewrite.
size(); i != e; ++i)
847 RedoInsts.insert(NodesToRewrite[i]);
859 if (
auto *
C = dyn_cast<Constant>(V)) {
861 Constant *Res =
C->getType()->isFPOrFPVectorTy()
882 if (
I->getOpcode() == Instruction::Add) {
883 I->setHasNoUnsignedWrap(
false);
884 I->setHasNoSignedWrap(
false);
893 I->setName(
I->getName()+
".neg");
903 for (
User *U : V->users()) {
916 C->containsUndefOrPoisonElement())
925 if (
Instruction *InstInput = dyn_cast<Instruction>(V)) {
926 auto InsertPtOpt = InstInput->getInsertionPointAfterDef();
929 InsertPt = *InsertPtOpt;
937 TheNeg->
moveBefore(*InsertPt->getParent(), InsertPt);
938 if (TheNeg->
getOpcode() == Instruction::Sub) {
964 auto Enqueue = [&](
Value *V) {
965 auto *
I = dyn_cast<Instruction>(V);
978 while (!Worklist.
empty()) {
982 switch (
I->getOpcode()) {
983 case Instruction::Or:
990 case Instruction::Shl:
991 case Instruction::ZExt:
993 if (!Enqueue(
I->getOperand(0)))
997 case Instruction::Load:
1015 for (
auto Op : {Instruction::Add, Instruction::Sub, Instruction::Mul,
1038 New->setHasNoSignedWrap();
1039 New->setHasNoUnsignedWrap();
1043 Or->replaceAllUsesWith(New);
1044 New->setDebugLoc(
Or->getDebugLoc());
1046 LLVM_DEBUG(
dbgs() <<
"Converted or into an add: " << *New <<
'\n');
1106 auto *SA = cast<ConstantInt>(Shl->
getOperand(1));
1110 BinaryOperator::CreateMul(Shl->
getOperand(0), MulCst,
"", Shl);
1122 bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
1123 bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
1125 if (NSW && (NUW || SA->getValue().ult(
BitWidth - 1)))
1126 Mul->setHasNoSignedWrap(
true);
1127 Mul->setHasNoUnsignedWrap(NUW);
1136 unsigned XRank = Ops[i].Rank;
1137 unsigned e = Ops.
size();
1138 for (
unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {
1143 if (I1->isIdenticalTo(I2))
1147 for (
unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {
1152 if (I1->isIdenticalTo(I2))
1162 if (Ops.
size() == 1)
return Ops.
back();
1181 for (
unsigned i = 0, e = Tree.
size(); i != e; ++i) {
1183 Factors.
append(
E.second.getZExtValue(),
1187 bool FoundFactor =
false;
1188 bool NeedsNegate =
false;
1189 for (
unsigned i = 0, e = Factors.
size(); i != e; ++i) {
1198 if (
ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].
Op))
1199 if (FC1->getValue() == -FC2->getValue()) {
1200 FoundFactor = NeedsNegate =
true;
1205 if (
ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[i].
Op)) {
1206 const APFloat &F1 = FC1->getValueAPF();
1207 APFloat F2(FC2->getValueAPF());
1210 FoundFactor = NeedsNegate =
true;
1220 RewriteExprTree(BO, Factors);
1228 if (Factors.
size() == 1) {
1229 RedoInsts.insert(BO);
1232 RewriteExprTree(BO, Factors);
1266 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1273 if (
Opcode == Instruction::And)
1276 if (
Opcode == Instruction::Or)
1284 if (i+1 != Ops.
size() && Ops[i+1].Op == Ops[i].Op) {
1285 if (
Opcode == Instruction::And ||
Opcode == Instruction::Or) {
1313 const APInt &ConstOpnd) {
1346 if (C1 != ConstOpnd)
1355 RedoInsts.insert(
T);
1375 int DeadInstNum = 1;
1393 APInt C3((~C1) ^ C2);
1396 if (!C3.isZero() && !C3.isAllOnes()) {
1398 if (NewInstNum > DeadInstNum)
1414 if (NewInstNum > DeadInstNum)
1432 RedoInsts.insert(
T);
1434 RedoInsts.insert(
T);
1447 if (Ops.
size() == 1)
1452 Type *Ty = Ops[0].Op->getType();
1456 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1464 O.setSymbolicRank(getRank(
O.getSymbolicPart()));
1474 for (
unsigned i = 0, e = Opnds.
size(); i != e; ++i)
1491 return LHS->getSymbolicRank() <
RHS->getSymbolicRank();
1496 bool Changed =
false;
1497 for (
unsigned i = 0, e = Opnds.
size(); i < e; i++) {
1498 XorOpnd *CurrOpnd = OpndPtrs[i];
1503 if (!ConstOpnd.
isZero() && CombineXorOpnd(
I, CurrOpnd, ConstOpnd, CV)) {
1513 if (!PrevOpnd || CurrOpnd->
getSymbolicPart() != PrevOpnd->getSymbolicPart()) {
1514 PrevOpnd = CurrOpnd;
1520 if (CombineXorOpnd(
I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
1525 PrevOpnd = CurrOpnd;
1537 for (
const XorOpnd &O : Opnds) {
1543 if (!ConstOpnd.
isZero()) {
1548 unsigned Sz = Ops.
size();
1550 return Ops.
back().Op;
1570 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1571 Value *TheOp = Ops[i].Op;
1575 if (i+1 != Ops.
size() && Ops[i+1].Op == TheOp) {
1577 unsigned NumFound = 0;
1581 }
while (i != Ops.
size() && Ops[i].Op == TheOp);
1583 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << NumFound <<
"]: " << *TheOp
1596 RedoInsts.insert(
Mul);
1623 if (Ops.
size() == 2 &&
1658 unsigned MaxOcc = 0;
1659 Value *MaxOccVal =
nullptr;
1660 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1669 assert(Factors.
size() > 1 &&
"Bad linearize!");
1677 unsigned Occ = ++FactorOccurrences[
Factor];
1687 if (CI->isNegative() && !CI->isMinValue(
true)) {
1691 unsigned Occ = ++FactorOccurrences[
Factor];
1698 if (CF->isNegative()) {
1704 unsigned Occ = ++FactorOccurrences[
Factor];
1716 LLVM_DEBUG(
dbgs() <<
"\nFACTORING [" << MaxOcc <<
"]: " << *MaxOccVal
1725 I->getType()->isIntOrIntVectorTy()
1726 ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal)
1730 for (
unsigned i = 0; i != Ops.
size(); ++i) {
1737 if (
Value *V = RemoveFactorFromExpression(Ops[i].
Op, MaxOccVal)) {
1740 for (
unsigned j = Ops.
size(); j != i;) {
1742 if (Ops[j].
Op == Ops[i].
Op) {
1754 unsigned NumAddedValues = NewMulOps.
size();
1760 assert(NumAddedValues > 1 &&
"Each occurrence should contribute a value");
1761 (void)NumAddedValues;
1763 RedoInsts.insert(VI);
1770 RedoInsts.insert(V2);
1801 unsigned FactorPowerSum = 0;
1811 FactorPowerSum += Count;
1818 if (FactorPowerSum < 4)
1835 FactorPowerSum += Count;
1842 assert(FactorPowerSum >= 4);
1845 return LHS.Power >
RHS.Power;
1853 if (Ops.
size() == 1)
1862 }
while (!Ops.
empty());
1874ReassociatePass::buildMinimalMultiplyDAG(
IRBuilderBase &Builder,
1876 assert(Factors[0].Power);
1878 for (
unsigned LastIdx = 0,
Idx = 1,
Size = Factors.
size();
1880 if (Factors[
Idx].Power != Factors[LastIdx].Power) {
1893 }
while (
Idx <
Size && Factors[
Idx].Power == Factors[LastIdx].Power);
1899 RedoInsts.insert(
MI);
1907 return LHS.Power == RHS.Power;
1919 if (Factors[0].Power) {
1920 Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors);
1924 if (OuterProduct.
size() == 1)
1925 return OuterProduct.
front();
1949 if (
auto FPI = dyn_cast<FPMathOperator>(
I))
1952 Value *
V = buildMinimalMultiplyDAG(Builder, Factors);
1967 unsigned Opcode =
I->getOpcode();
1968 while (!Ops.
empty()) {
1969 if (
auto *
C = dyn_cast<Constant>(Ops.
back().Op)) {
1996 if (Ops.
size() == 1)
return Ops[0].Op;
2000 unsigned NumOps = Ops.
size();
2003 case Instruction::And:
2004 case Instruction::Or:
2009 case Instruction::Xor:
2010 if (
Value *Result = OptimizeXor(
I, Ops))
2014 case Instruction::Add:
2015 case Instruction::FAdd:
2016 if (
Value *Result = OptimizeAdd(
I, Ops))
2020 case Instruction::Mul:
2021 case Instruction::FMul:
2022 if (
Value *Result = OptimizeMul(
I, Ops))
2027 if (Ops.
size() != NumOps)
2028 return OptimizeExpression(
I, Ops);
2034void ReassociatePass::RecursivelyEraseDeadInsts(
Instruction *
I,
2035 OrderedSet &Insts) {
2038 ValueRankMap.erase(
I);
2040 RedoInsts.remove(
I);
2042 I->eraseFromParent();
2043 for (
auto *
Op : Ops)
2045 if (OpInst->use_empty())
2046 Insts.insert(OpInst);
2056 ValueRankMap.erase(
I);
2057 RedoInsts.remove(
I);
2059 I->eraseFromParent();
2062 for (
unsigned i = 0, e = Ops.size(); i != e; ++i)
2067 while (
Op->hasOneUse() &&
Op->user_back()->getOpcode() ==
Opcode &&
2069 Op =
Op->user_back();
2076 if (ValueRankMap.contains(
Op))
2077 RedoInsts.insert(
Op);
2097 switch (
I->getOpcode()) {
2098 case Instruction::FMul:
2110 case Instruction::FDiv:
2135 assert((
I->getOpcode() == Instruction::FAdd ||
2136 I->getOpcode() == Instruction::FSub) &&
"Expected fadd/fsub");
2142 if (Candidates.
empty())
2148 bool IsFSub =
I->getOpcode() == Instruction::FSub;
2149 bool NeedsSubtract = !IsFSub && Candidates.
size() % 2 == 1;
2157 "Expecting only 1 constant operand");
2158 assert(
C->isNegative() &&
"Expected negative FP constant");
2164 "Expecting only 1 constant operand");
2165 assert(
C->isNegative() &&
"Expected negative FP constant");
2170 assert(MadeChange ==
true &&
"Negative constant candidate was not changed");
2173 if (Candidates.size() % 2 == 0)
2178 assert(Candidates.size() % 2 == 1 &&
"Expected odd number");
2182 I->replaceAllUsesWith(NewInst);
2183 RedoInsts.insert(
I);
2184 return dyn_cast<Instruction>(NewInst);
2215 if (!isa<UnaryOperator>(
I) && !isa<BinaryOperator>(
I))
2218 if (
I->getOpcode() == Instruction::Shl && isa<ConstantInt>(
I->getOperand(1)))
2226 RedoInsts.insert(
I);
2234 if (
I->isCommutative())
2235 canonicalizeOperands(
I);
2252 if (
I->getType()->isIntegerTy(1))
2257 if (
I->getOpcode() == Instruction::Or &&
2261 nullptr,
nullptr,
I))) {
2263 RedoInsts.insert(
I);
2270 if (
I->getOpcode() == Instruction::Sub) {
2273 RedoInsts.insert(
I);
2287 RedoInsts.insert(Tmp);
2289 RedoInsts.insert(
I);
2294 }
else if (
I->getOpcode() == Instruction::FNeg ||
2295 I->getOpcode() == Instruction::FSub) {
2298 RedoInsts.insert(
I);
2304 Value *
Op = isa<BinaryOperator>(
I) ?
I->getOperand(1) :
2314 RedoInsts.insert(Tmp);
2316 RedoInsts.insert(
I);
2324 if (!
I->isAssociative())
return;
2343 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::Sub)
2346 cast<Instruction>(BO->
user_back())->getOpcode() == Instruction::FSub)
2349 ReassociateExpression(BO);
2374 if (
Value *V = OptimizeExpression(
I, Ops)) {
2381 I->replaceAllUsesWith(V);
2383 if (
I->getDebugLoc())
2384 VI->setDebugLoc(
I->getDebugLoc());
2385 RedoInsts.insert(
I);
2394 if (
I->hasOneUse()) {
2395 if (
I->getOpcode() == Instruction::Mul &&
2396 cast<Instruction>(
I->user_back())->getOpcode() == Instruction::Add &&
2397 isa<ConstantInt>(Ops.
back().Op) &&
2398 cast<ConstantInt>(Ops.
back().Op)->isMinusOne()) {
2401 }
else if (
I->getOpcode() == Instruction::FMul &&
2402 cast<Instruction>(
I->user_back())->getOpcode() ==
2403 Instruction::FAdd &&
2404 isa<ConstantFP>(Ops.
back().Op) &&
2405 cast<ConstantFP>(Ops.
back().Op)->isExactlyValue(-1.0)) {
2413 if (Ops.
size() == 1) {
2420 I->replaceAllUsesWith(Ops[0].
Op);
2422 OI->setDebugLoc(
I->getDebugLoc());
2423 RedoInsts.insert(
I);
2427 if (Ops.
size() > 2 && Ops.
size() <= GlobalReassociateLimit) {
2435 unsigned BestRank = 0;
2436 std::pair<unsigned, unsigned> BestPair;
2437 unsigned Idx =
I->getOpcode() - Instruction::BinaryOpsBegin;
2438 unsigned LimitIdx = 0;
2448 int StartIdx = Ops.
size() - 1;
2453 for (
int i = StartIdx - 1; i != -1; --i) {
2454 const Value *Val = Ops[i].Op;
2455 const auto *CurrLeafInstr = dyn_cast<Instruction>(Val);
2457 if (!CurrLeafInstr) {
2476 SeenBB = &
I->getParent()->getParent()->getEntryBlock();
2482 FirstSeenBB = SeenBB;
2485 if (FirstSeenBB != SeenBB) {
2491 << LimitIdx <<
", " << StartIdx <<
"]\n");
2496 for (
unsigned i = Ops.
size() - 1; i > LimitIdx; --i) {
2498 for (
int j = i - 1;
j >= (int)LimitIdx; --
j) {
2500 Value *Op0 = Ops[i].Op;
2502 if (std::less<Value *>()(Op1, Op0))
2504 auto it = PairMap[
Idx].find({Op0, Op1});
2505 if (it != PairMap[
Idx].
end()) {
2511 if (it->second.isValid())
2512 Score += it->second.Score;
2515 unsigned MaxRank = std::max(Ops[i].Rank, Ops[j].Rank);
2529 if (Score > Max || (Score == Max && MaxRank < BestRank)) {
2537 auto Op0 = Ops[BestPair.first];
2538 auto Op1 = Ops[BestPair.second];
2539 Ops.
erase(&Ops[BestPair.second]);
2540 Ops.
erase(&Ops[BestPair.first]);
2549 RewriteExprTree(
I, Ops);
2557 if (!
I.isAssociative())
2561 if (
I.hasOneUse() &&
I.user_back()->getOpcode() ==
I.getOpcode())
2569 while (!Worklist.
empty() && Ops.
size() <= GlobalReassociateLimit) {
2583 if (Ops.
size() > GlobalReassociateLimit)
2587 unsigned BinaryIdx =
I.getOpcode() - Instruction::BinaryOpsBegin;
2589 for (
unsigned i = 0; i < Ops.
size() - 1; ++i) {
2590 for (
unsigned j = i + 1;
j < Ops.
size(); ++
j) {
2592 Value *Op0 = Ops[i];
2594 if (std::less<Value *>()(Op1, Op0))
2596 if (!Visited.
insert({Op0, Op1}).second)
2598 auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, {Op0, Op1, 1}});
2604 assert(res.first->second.isValid() &&
"WeakVH invalidated");
2605 ++res.first->second.Score;
2621 BuildRankMap(
F, RPOT);
2638 assert(RankMap.count(&*BI) &&
"BB should be ranked.");
2645 assert(II->getParent() == &*BI &&
"Moved to a different block!");
2656 while (!ToRedo.
empty()) {
2659 RecursivelyEraseDeadInsts(
I, ToRedo);
2666 while (!RedoInsts.empty()) {
2668 RedoInsts.erase(RedoInsts.begin());
2678 ValueRankMap.clear();
2679 for (
auto &Entry : PairMap)
2704 if (skipFunction(
F))
2708 auto PA = Impl.
run(
F, DummyFAM);
2722char ReassociateLegacyPass::ID = 0;
2725 "Reassociate expressions",
false,
false)
2729 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.
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 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 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.
static constexpr uint32_t Opcode
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=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.
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="", 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.
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.