39 #define DEBUG_TYPE "aggressive-instcombine"
41 STATISTIC(NumExprsReduced,
"Number of truncations eliminated by reducing bit "
42 "width of expression graph");
44 "Number of instructions whose bit width was reduced");
49 unsigned Opc =
I->getOpcode();
51 case Instruction::Trunc:
52 case Instruction::ZExt:
53 case Instruction::SExt:
58 case Instruction::Sub:
60 case Instruction::And:
62 case Instruction::Xor:
63 case Instruction::Shl:
64 case Instruction::LShr:
65 case Instruction::AShr:
66 case Instruction::UDiv:
67 case Instruction::URem:
68 case Instruction::InsertElement:
69 Ops.push_back(
I->getOperand(0));
70 Ops.push_back(
I->getOperand(1));
72 case Instruction::ExtractElement:
73 Ops.push_back(
I->getOperand(0));
76 Ops.push_back(
I->getOperand(1));
77 Ops.push_back(
I->getOperand(2));
79 case Instruction::PHI:
80 for (
Value *V : cast<PHINode>(
I)->incoming_values())
88 bool TruncInstCombine::buildTruncExpressionGraph() {
94 Worklist.push_back(CurrentTruncInst->
getOperand(0));
96 while (!Worklist.empty()) {
97 Value *Curr = Worklist.back();
99 if (isa<Constant>(Curr)) {
104 auto *
I = dyn_cast<Instruction>(Curr);
114 InstInfoMap.insert(std::make_pair(
I,
Info()));
118 if (InstInfoMap.count(
I)) {
126 unsigned Opc =
I->getOpcode();
128 case Instruction::Trunc:
129 case Instruction::ZExt:
130 case Instruction::SExt:
137 case Instruction::Sub:
139 case Instruction::And:
140 case Instruction::Or:
141 case Instruction::Xor:
142 case Instruction::Shl:
143 case Instruction::LShr:
144 case Instruction::AShr:
145 case Instruction::UDiv:
146 case Instruction::URem:
147 case Instruction::InsertElement:
148 case Instruction::ExtractElement:
155 case Instruction::PHI: {
161 Worklist.push_back(
Op);
175 unsigned TruncInstCombine::getMinBitWidth() {
182 unsigned OrigBitWidth =
185 if (isa<Constant>(Src))
186 return TruncBitWidth;
188 Worklist.push_back(Src);
189 InstInfoMap[cast<Instruction>(Src)].ValidBitWidth = TruncBitWidth;
191 while (!Worklist.empty()) {
192 Value *Curr = Worklist.back();
194 if (isa<Constant>(Curr)) {
200 auto *
I = cast<Instruction>(Curr);
202 auto &
Info = InstInfoMap[
I];
213 if (
auto *IOp = dyn_cast<Instruction>(Operand))
215 std::max(
Info.MinBitWidth, InstInfoMap[IOp].MinBitWidth);
221 unsigned ValidBitWidth =
Info.ValidBitWidth;
228 if (
auto *IOp = dyn_cast<Instruction>(Operand)) {
232 unsigned IOpBitwidth = InstInfoMap.lookup(IOp).ValidBitWidth;
233 if (IOpBitwidth >= ValidBitWidth)
235 InstInfoMap[IOp].ValidBitWidth = ValidBitWidth;
236 Worklist.push_back(IOp);
239 unsigned MinBitWidth = InstInfoMap.lookup(cast<Instruction>(Src)).MinBitWidth;
240 assert(MinBitWidth >= TruncBitWidth);
242 if (MinBitWidth > TruncBitWidth) {
258 bool FromLegal = MinBitWidth == 1 || DL.
isLegalInteger(OrigBitWidth);
259 bool ToLegal = MinBitWidth == 1 || DL.
isLegalInteger(MinBitWidth);
260 if (!DstTy->
isVectorTy() && FromLegal && !ToLegal)
266 Type *TruncInstCombine::getBestTruncatedType() {
267 if (!buildTruncExpressionGraph())
274 unsigned DesiredBitWidth = 0;
275 for (
auto Itr : InstInfoMap) {
279 bool IsExtInst = (isa<ZExtInst>(
I) || isa<SExtInst>(
I));
280 for (
auto *U :
I->users())
281 if (
auto *UI = dyn_cast<Instruction>(U))
282 if (UI != CurrentTruncInst && !InstInfoMap.count(UI)) {
288 unsigned ExtInstBitWidth =
289 I->getOperand(0)->getType()->getScalarSizeInBits();
290 if (DesiredBitWidth && DesiredBitWidth != ExtInstBitWidth)
292 DesiredBitWidth = ExtInstBitWidth;
296 unsigned OrigBitWidth =
307 for (
auto &Itr : InstInfoMap) {
310 KnownBits KnownRHS = computeKnownBits(
I->getOperand(1));
314 if (MinBitWidth == OrigBitWidth)
316 if (
I->getOpcode() == Instruction::LShr) {
317 KnownBits KnownLHS = computeKnownBits(
I->getOperand(0));
321 if (
I->getOpcode() == Instruction::AShr) {
322 unsigned NumSignBits = ComputeNumSignBits(
I->getOperand(0));
323 MinBitWidth =
std::max(MinBitWidth, OrigBitWidth - NumSignBits + 1);
325 if (MinBitWidth >= OrigBitWidth)
327 Itr.second.MinBitWidth = MinBitWidth;
329 if (
I->getOpcode() == Instruction::UDiv ||
330 I->getOpcode() == Instruction::URem) {
331 unsigned MinBitWidth = 0;
332 for (
const auto &
Op :
I->operands()) {
336 if (MinBitWidth >= OrigBitWidth)
339 Itr.second.MinBitWidth = MinBitWidth;
345 unsigned MinBitWidth = getMinBitWidth();
349 if (MinBitWidth >= OrigBitWidth ||
350 (DesiredBitWidth && DesiredBitWidth != MinBitWidth))
361 if (
auto *VTy = dyn_cast<VectorType>(V->
getType()))
366 Value *TruncInstCombine::getReducedOperand(
Value *V,
Type *SclTy) {
368 if (
auto *
C = dyn_cast<Constant>(V)) {
374 auto *
I = cast<Instruction>(V);
375 Info Entry = InstInfoMap.lookup(
I);
377 return Entry.NewValue;
380 void TruncInstCombine::ReduceExpressionGraph(
Type *SclTy) {
381 NumInstrsReduced += InstInfoMap.size();
384 for (
auto &Itr : InstInfoMap) {
388 assert(!NodeInfo.NewValue &&
"Instruction has been evaluated");
391 Value *Res =
nullptr;
392 unsigned Opc =
I->getOpcode();
394 case Instruction::Trunc:
395 case Instruction::ZExt:
396 case Instruction::SExt: {
401 if (
I->getOperand(0)->getType() == Ty) {
402 assert(!isa<TruncInst>(
I) &&
"Cannot reach here with TruncInst");
403 NodeInfo.NewValue =
I->getOperand(0);
408 Res =
Builder.CreateIntCast(
I->getOperand(0), Ty,
409 Opc == Instruction::SExt);
416 auto *Entry =
find(Worklist,
I);
417 if (Entry != Worklist.end()) {
418 if (
auto *NewCI = dyn_cast<TruncInst>(Res))
421 Worklist.
erase(Entry);
422 }
else if (
auto *NewCI = dyn_cast<TruncInst>(Res))
423 Worklist.push_back(NewCI);
427 case Instruction::Sub:
429 case Instruction::And:
430 case Instruction::Or:
431 case Instruction::Xor:
432 case Instruction::Shl:
433 case Instruction::LShr:
434 case Instruction::AShr:
435 case Instruction::UDiv:
436 case Instruction::URem: {
437 Value *
LHS = getReducedOperand(
I->getOperand(0), SclTy);
438 Value *
RHS = getReducedOperand(
I->getOperand(1), SclTy);
441 if (
auto *PEO = dyn_cast<PossiblyExactOperator>(
I))
442 if (
auto *ResI = dyn_cast<Instruction>(Res))
443 ResI->setIsExact(PEO->isExact());
446 case Instruction::ExtractElement: {
447 Value *Vec = getReducedOperand(
I->getOperand(0), SclTy);
448 Value *Idx =
I->getOperand(1);
449 Res =
Builder.CreateExtractElement(Vec, Idx);
452 case Instruction::InsertElement: {
453 Value *Vec = getReducedOperand(
I->getOperand(0), SclTy);
454 Value *NewElt = getReducedOperand(
I->getOperand(1), SclTy);
455 Value *Idx =
I->getOperand(2);
456 Res =
Builder.CreateInsertElement(Vec, NewElt, Idx);
460 Value *Op0 =
I->getOperand(0);
461 Value *
LHS = getReducedOperand(
I->getOperand(1), SclTy);
462 Value *
RHS = getReducedOperand(
I->getOperand(2), SclTy);
466 case Instruction::PHI: {
468 OldNewPHINodes.push_back(
469 std::make_pair(cast<PHINode>(
I), cast<PHINode>(Res)));
476 NodeInfo.NewValue = Res;
477 if (
auto *ResI = dyn_cast<Instruction>(Res))
481 for (
auto &Node : OldNewPHINodes) {
485 NewPN->
addIncoming(getReducedOperand(std::get<0>(Incoming), SclTy),
486 std::get<1>(Incoming));
489 Value *Res = getReducedOperand(CurrentTruncInst->
getOperand(0), SclTy);
493 Res =
Builder.CreateIntCast(Res, DstTy,
false);
494 if (
auto *ResI = dyn_cast<Instruction>(Res))
495 ResI->takeName(CurrentTruncInst);
503 for (
auto &Node : OldNewPHINodes) {
506 InstInfoMap.erase(OldPN);
517 if (
I.first->use_empty())
518 I.first->eraseFromParent();
520 assert((isa<SExtInst>(
I.first) || isa<ZExtInst>(
I.first)) &&
521 "Only {SExt, ZExt}Inst might have unreduced users");
526 bool MadeIRChange =
false;
534 if (
auto *CI = dyn_cast<TruncInst>(&
I))
535 Worklist.push_back(CI);
541 while (!Worklist.empty()) {
544 if (
Type *NewDstSclTy = getBestTruncatedType()) {
546 dbgs() <<
"ICE: TruncInstCombine reducing type of expression graph "
548 << CurrentTruncInst <<
'\n');
549 ReduceExpressionGraph(NewDstSclTy);