556 lines · cpp
1//===- TruncInstCombine.cpp -----------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// TruncInstCombine - looks for expression graphs post-dominated by TruncInst10// and for each eligible graph, it will create a reduced bit-width expression,11// replace the old expression with this new one and remove the old expression.12// Eligible expression graph is such that:13// 1. Contains only supported instructions.14// 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.15// 3. Can be evaluated into type with reduced legal bit-width.16// 4. All instructions in the graph must not have users outside the graph.17// The only exception is for {ZExt, SExt}Inst with operand type equal to18// the new reduced type evaluated in (3).19//20// The motivation for this optimization is that evaluating and expression using21// smaller bit-width is preferable, especially for vectorization where we can22// fit more values in one vectorized instruction. In addition, this optimization23// may decrease the number of cast instructions, but will not increase it.24//25//===----------------------------------------------------------------------===//26 27#include "AggressiveInstCombineInternal.h"28#include "llvm/ADT/STLExtras.h"29#include "llvm/ADT/Statistic.h"30#include "llvm/Analysis/ConstantFolding.h"31#include "llvm/IR/DataLayout.h"32#include "llvm/IR/Dominators.h"33#include "llvm/IR/IRBuilder.h"34#include "llvm/IR/Instruction.h"35#include "llvm/Support/KnownBits.h"36 37using namespace llvm;38 39#define DEBUG_TYPE "aggressive-instcombine"40 41STATISTIC(NumExprsReduced, "Number of truncations eliminated by reducing bit "42 "width of expression graph");43STATISTIC(NumInstrsReduced,44 "Number of instructions whose bit width was reduced");45 46/// Given an instruction and a container, it fills all the relevant operands of47/// that instruction, with respect to the Trunc expression graph optimizaton.48static void getRelevantOperands(Instruction *I, SmallVectorImpl<Value *> &Ops) {49 unsigned Opc = I->getOpcode();50 switch (Opc) {51 case Instruction::Trunc:52 case Instruction::ZExt:53 case Instruction::SExt:54 // These CastInst are considered leaves of the evaluated expression, thus,55 // their operands are not relevent.56 break;57 case Instruction::Add:58 case Instruction::Sub:59 case Instruction::Mul:60 case Instruction::And:61 case Instruction::Or: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));71 break;72 case Instruction::ExtractElement:73 Ops.push_back(I->getOperand(0));74 break;75 case Instruction::Select:76 Ops.push_back(I->getOperand(1));77 Ops.push_back(I->getOperand(2));78 break;79 case Instruction::PHI:80 llvm::append_range(Ops, cast<PHINode>(I)->incoming_values());81 break;82 default:83 llvm_unreachable("Unreachable!");84 }85}86 87bool TruncInstCombine::buildTruncExpressionGraph() {88 SmallVector<Value *, 8> Worklist;89 SmallVector<Instruction *, 8> Stack;90 // Clear old instructions info.91 InstInfoMap.clear();92 93 Worklist.push_back(CurrentTruncInst->getOperand(0));94 95 while (!Worklist.empty()) {96 Value *Curr = Worklist.back();97 98 if (isa<Constant>(Curr)) {99 Worklist.pop_back();100 continue;101 }102 103 auto *I = dyn_cast<Instruction>(Curr);104 if (!I)105 return false;106 107 if (!Stack.empty() && Stack.back() == I) {108 // Already handled all instruction operands, can remove it from both the109 // Worklist and the Stack, and add it to the instruction info map.110 Worklist.pop_back();111 Stack.pop_back();112 // Insert I to the Info map.113 InstInfoMap.try_emplace(I);114 continue;115 }116 117 if (InstInfoMap.count(I)) {118 Worklist.pop_back();119 continue;120 }121 122 // Add the instruction to the stack before start handling its operands.123 Stack.push_back(I);124 125 unsigned Opc = I->getOpcode();126 switch (Opc) {127 case Instruction::Trunc:128 case Instruction::ZExt:129 case Instruction::SExt:130 // trunc(trunc(x)) -> trunc(x)131 // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest132 // trunc(ext(x)) -> trunc(x) if the source type is larger than the new133 // dest134 break;135 case Instruction::Add:136 case Instruction::Sub:137 case Instruction::Mul:138 case Instruction::And:139 case Instruction::Or:140 case Instruction::Xor:141 case Instruction::Shl:142 case Instruction::LShr:143 case Instruction::AShr:144 case Instruction::UDiv:145 case Instruction::URem:146 case Instruction::InsertElement:147 case Instruction::ExtractElement:148 case Instruction::Select: {149 SmallVector<Value *, 2> Operands;150 getRelevantOperands(I, Operands);151 append_range(Worklist, Operands);152 break;153 }154 case Instruction::PHI: {155 SmallVector<Value *, 2> Operands;156 getRelevantOperands(I, Operands);157 // Add only operands not in Stack to prevent cycle158 for (auto *Op : Operands)159 if (!llvm::is_contained(Stack, Op))160 Worklist.push_back(Op);161 break;162 }163 default:164 // TODO: Can handle more cases here:165 // 1. shufflevector166 // 2. sdiv, srem167 // ...168 return false;169 }170 }171 return true;172}173 174unsigned TruncInstCombine::getMinBitWidth() {175 SmallVector<Value *, 8> Worklist;176 SmallVector<Instruction *, 8> Stack;177 178 Value *Src = CurrentTruncInst->getOperand(0);179 Type *DstTy = CurrentTruncInst->getType();180 unsigned TruncBitWidth = DstTy->getScalarSizeInBits();181 unsigned OrigBitWidth =182 CurrentTruncInst->getOperand(0)->getType()->getScalarSizeInBits();183 184 if (isa<Constant>(Src))185 return TruncBitWidth;186 187 Worklist.push_back(Src);188 InstInfoMap[cast<Instruction>(Src)].ValidBitWidth = TruncBitWidth;189 190 while (!Worklist.empty()) {191 Value *Curr = Worklist.back();192 193 if (isa<Constant>(Curr)) {194 Worklist.pop_back();195 continue;196 }197 198 // Otherwise, it must be an instruction.199 auto *I = cast<Instruction>(Curr);200 201 auto &Info = InstInfoMap[I];202 203 SmallVector<Value *, 2> Operands;204 getRelevantOperands(I, Operands);205 206 if (!Stack.empty() && Stack.back() == I) {207 // Already handled all instruction operands, can remove it from both, the208 // Worklist and the Stack, and update MinBitWidth.209 Worklist.pop_back();210 Stack.pop_back();211 for (auto *Operand : Operands)212 if (auto *IOp = dyn_cast<Instruction>(Operand))213 Info.MinBitWidth =214 std::max(Info.MinBitWidth, InstInfoMap[IOp].MinBitWidth);215 continue;216 }217 218 // Add the instruction to the stack before start handling its operands.219 Stack.push_back(I);220 unsigned ValidBitWidth = Info.ValidBitWidth;221 222 // Update minimum bit-width before handling its operands. This is required223 // when the instruction is part of a loop.224 Info.MinBitWidth = std::max(Info.MinBitWidth, Info.ValidBitWidth);225 226 for (auto *Operand : Operands)227 if (auto *IOp = dyn_cast<Instruction>(Operand)) {228 // If we already calculated the minimum bit-width for this valid229 // bit-width, or for a smaller valid bit-width, then just keep the230 // answer we already calculated.231 unsigned IOpBitwidth = InstInfoMap.lookup(IOp).ValidBitWidth;232 if (IOpBitwidth >= ValidBitWidth)233 continue;234 InstInfoMap[IOp].ValidBitWidth = ValidBitWidth;235 Worklist.push_back(IOp);236 }237 }238 unsigned MinBitWidth = InstInfoMap.lookup(cast<Instruction>(Src)).MinBitWidth;239 assert(MinBitWidth >= TruncBitWidth);240 241 if (MinBitWidth > TruncBitWidth) {242 // In this case reducing expression with vector type might generate a new243 // vector type, which is not preferable as it might result in generating244 // sub-optimal code.245 if (DstTy->isVectorTy())246 return OrigBitWidth;247 // Use the smallest integer type in the range [MinBitWidth, OrigBitWidth).248 Type *Ty = DL.getSmallestLegalIntType(DstTy->getContext(), MinBitWidth);249 // Update minimum bit-width with the new destination type bit-width if250 // succeeded to find such, otherwise, with original bit-width.251 MinBitWidth = Ty ? Ty->getScalarSizeInBits() : OrigBitWidth;252 } else { // MinBitWidth == TruncBitWidth253 // In this case the expression can be evaluated with the trunc instruction254 // destination type, and trunc instruction can be omitted. However, we255 // should not perform the evaluation if the original type is a legal scalar256 // type and the target type is illegal.257 bool FromLegal = MinBitWidth == 1 || DL.isLegalInteger(OrigBitWidth);258 bool ToLegal = MinBitWidth == 1 || DL.isLegalInteger(MinBitWidth);259 if (!DstTy->isVectorTy() && FromLegal && !ToLegal)260 return OrigBitWidth;261 }262 return MinBitWidth;263}264 265Type *TruncInstCombine::getBestTruncatedType() {266 if (!buildTruncExpressionGraph())267 return nullptr;268 269 // We don't want to duplicate instructions, which isn't profitable. Thus, we270 // can't shrink something that has multiple users, unless all users are271 // post-dominated by the trunc instruction, i.e., were visited during the272 // expression evaluation.273 unsigned DesiredBitWidth = 0;274 for (auto Itr : InstInfoMap) {275 Instruction *I = Itr.first;276 if (I->hasOneUse())277 continue;278 bool IsExtInst = (isa<ZExtInst>(I) || isa<SExtInst>(I));279 for (auto *U : I->users())280 if (auto *UI = dyn_cast<Instruction>(U))281 if (UI != CurrentTruncInst && !InstInfoMap.count(UI)) {282 if (!IsExtInst)283 return nullptr;284 // If this is an extension from the dest type, we can eliminate it,285 // even if it has multiple users. Thus, update the DesiredBitWidth and286 // validate all extension instructions agrees on same DesiredBitWidth.287 unsigned ExtInstBitWidth =288 I->getOperand(0)->getType()->getScalarSizeInBits();289 if (DesiredBitWidth && DesiredBitWidth != ExtInstBitWidth)290 return nullptr;291 DesiredBitWidth = ExtInstBitWidth;292 }293 }294 295 unsigned OrigBitWidth =296 CurrentTruncInst->getOperand(0)->getType()->getScalarSizeInBits();297 298 // Initialize MinBitWidth for shift instructions with the minimum number299 // that is greater than shift amount (i.e. shift amount + 1).300 // For `lshr` adjust MinBitWidth so that all potentially truncated301 // bits of the value-to-be-shifted are zeros.302 // For `ashr` adjust MinBitWidth so that all potentially truncated303 // bits of the value-to-be-shifted are sign bits (all zeros or ones)304 // and even one (first) untruncated bit is sign bit.305 // Exit early if MinBitWidth is not less than original bitwidth.306 for (auto &Itr : InstInfoMap) {307 Instruction *I = Itr.first;308 if (I->isShift()) {309 KnownBits KnownRHS = computeKnownBits(I->getOperand(1));310 unsigned MinBitWidth = KnownRHS.getMaxValue()311 .uadd_sat(APInt(OrigBitWidth, 1))312 .getLimitedValue(OrigBitWidth);313 if (MinBitWidth == OrigBitWidth)314 return nullptr;315 if (I->getOpcode() == Instruction::LShr) {316 KnownBits KnownLHS = computeKnownBits(I->getOperand(0));317 MinBitWidth =318 std::max(MinBitWidth, KnownLHS.getMaxValue().getActiveBits());319 }320 if (I->getOpcode() == Instruction::AShr) {321 unsigned NumSignBits = ComputeNumSignBits(I->getOperand(0));322 MinBitWidth = std::max(MinBitWidth, OrigBitWidth - NumSignBits + 1);323 }324 if (MinBitWidth >= OrigBitWidth)325 return nullptr;326 Itr.second.MinBitWidth = MinBitWidth;327 }328 if (I->getOpcode() == Instruction::UDiv ||329 I->getOpcode() == Instruction::URem) {330 unsigned MinBitWidth = 0;331 for (const auto &Op : I->operands()) {332 KnownBits Known = computeKnownBits(Op);333 MinBitWidth =334 std::max(Known.getMaxValue().getActiveBits(), MinBitWidth);335 if (MinBitWidth >= OrigBitWidth)336 return nullptr;337 }338 Itr.second.MinBitWidth = MinBitWidth;339 }340 }341 342 // Calculate minimum allowed bit-width allowed for shrinking the currently343 // visited truncate's operand.344 unsigned MinBitWidth = getMinBitWidth();345 346 // Check that we can shrink to smaller bit-width than original one and that347 // it is similar to the DesiredBitWidth is such exists.348 if (MinBitWidth >= OrigBitWidth ||349 (DesiredBitWidth && DesiredBitWidth != MinBitWidth))350 return nullptr;351 352 return IntegerType::get(CurrentTruncInst->getContext(), MinBitWidth);353}354 355/// Given a reduced scalar type \p Ty and a \p V value, return a reduced type356/// for \p V, according to its type, if it vector type, return the vector357/// version of \p Ty, otherwise return \p Ty.358static Type *getReducedType(Value *V, Type *Ty) {359 assert(Ty && !Ty->isVectorTy() && "Expect Scalar Type");360 if (auto *VTy = dyn_cast<VectorType>(V->getType()))361 return VectorType::get(Ty, VTy->getElementCount());362 return Ty;363}364 365Value *TruncInstCombine::getReducedOperand(Value *V, Type *SclTy) {366 Type *Ty = getReducedType(V, SclTy);367 if (auto *C = dyn_cast<Constant>(V)) {368 C = ConstantExpr::getTrunc(C, Ty);369 // If we got a constantexpr back, try to simplify it with DL info.370 return ConstantFoldConstant(C, DL, &TLI);371 }372 373 auto *I = cast<Instruction>(V);374 Info Entry = InstInfoMap.lookup(I);375 assert(Entry.NewValue);376 return Entry.NewValue;377}378 379void TruncInstCombine::ReduceExpressionGraph(Type *SclTy) {380 NumInstrsReduced += InstInfoMap.size();381 // Pairs of old and new phi-nodes382 SmallVector<std::pair<PHINode *, PHINode *>, 2> OldNewPHINodes;383 for (auto &Itr : InstInfoMap) { // Forward384 Instruction *I = Itr.first;385 TruncInstCombine::Info &NodeInfo = Itr.second;386 387 assert(!NodeInfo.NewValue && "Instruction has been evaluated");388 389 IRBuilder<> Builder(I);390 Value *Res = nullptr;391 unsigned Opc = I->getOpcode();392 switch (Opc) {393 case Instruction::Trunc:394 case Instruction::ZExt:395 case Instruction::SExt: {396 Type *Ty = getReducedType(I, SclTy);397 // If the source type of the cast is the type we're trying for then we can398 // just return the source. There's no need to insert it because it is not399 // new.400 if (I->getOperand(0)->getType() == Ty) {401 assert(!isa<TruncInst>(I) && "Cannot reach here with TruncInst");402 NodeInfo.NewValue = I->getOperand(0);403 continue;404 }405 // Otherwise, must be the same type of cast, so just reinsert a new one.406 // This also handles the case of zext(trunc(x)) -> zext(x).407 Res = Builder.CreateIntCast(I->getOperand(0), Ty,408 Opc == Instruction::SExt);409 410 // Update Worklist entries with new value if needed.411 // There are three possible changes to the Worklist:412 // 1. Update Old-TruncInst -> New-TruncInst.413 // 2. Remove Old-TruncInst (if New node is not TruncInst).414 // 3. Add New-TruncInst (if Old node was not TruncInst).415 auto *Entry = find(Worklist, I);416 if (Entry != Worklist.end()) {417 if (auto *NewCI = dyn_cast<TruncInst>(Res))418 *Entry = NewCI;419 else420 Worklist.erase(Entry);421 } else if (auto *NewCI = dyn_cast<TruncInst>(Res))422 Worklist.push_back(NewCI);423 break;424 }425 case Instruction::Add:426 case Instruction::Sub:427 case Instruction::Mul:428 case Instruction::And:429 case Instruction::Or:430 case Instruction::Xor:431 case Instruction::Shl:432 case Instruction::LShr:433 case Instruction::AShr:434 case Instruction::UDiv:435 case Instruction::URem: {436 Value *LHS = getReducedOperand(I->getOperand(0), SclTy);437 Value *RHS = getReducedOperand(I->getOperand(1), SclTy);438 Res = Builder.CreateBinOp((Instruction::BinaryOps)Opc, LHS, RHS);439 // Preserve `exact` flag since truncation doesn't change exactness440 if (auto *PEO = dyn_cast<PossiblyExactOperator>(I))441 if (auto *ResI = dyn_cast<Instruction>(Res))442 ResI->setIsExact(PEO->isExact());443 break;444 }445 case Instruction::ExtractElement: {446 Value *Vec = getReducedOperand(I->getOperand(0), SclTy);447 Value *Idx = I->getOperand(1);448 Res = Builder.CreateExtractElement(Vec, Idx);449 break;450 }451 case Instruction::InsertElement: {452 Value *Vec = getReducedOperand(I->getOperand(0), SclTy);453 Value *NewElt = getReducedOperand(I->getOperand(1), SclTy);454 Value *Idx = I->getOperand(2);455 Res = Builder.CreateInsertElement(Vec, NewElt, Idx);456 break;457 }458 case Instruction::Select: {459 Value *Op0 = I->getOperand(0);460 Value *LHS = getReducedOperand(I->getOperand(1), SclTy);461 Value *RHS = getReducedOperand(I->getOperand(2), SclTy);462 Res = Builder.CreateSelect(Op0, LHS, RHS, "", I);463 break;464 }465 case Instruction::PHI: {466 Res = Builder.CreatePHI(getReducedType(I, SclTy), I->getNumOperands());467 OldNewPHINodes.push_back(468 std::make_pair(cast<PHINode>(I), cast<PHINode>(Res)));469 break;470 }471 default:472 llvm_unreachable("Unhandled instruction");473 }474 475 NodeInfo.NewValue = Res;476 if (auto *ResI = dyn_cast<Instruction>(Res))477 ResI->takeName(I);478 }479 480 for (auto &Node : OldNewPHINodes) {481 PHINode *OldPN = Node.first;482 PHINode *NewPN = Node.second;483 for (auto Incoming : zip(OldPN->incoming_values(), OldPN->blocks()))484 NewPN->addIncoming(getReducedOperand(std::get<0>(Incoming), SclTy),485 std::get<1>(Incoming));486 }487 488 Value *Res = getReducedOperand(CurrentTruncInst->getOperand(0), SclTy);489 Type *DstTy = CurrentTruncInst->getType();490 if (Res->getType() != DstTy) {491 IRBuilder<> Builder(CurrentTruncInst);492 Res = Builder.CreateIntCast(Res, DstTy, false);493 if (auto *ResI = dyn_cast<Instruction>(Res))494 ResI->takeName(CurrentTruncInst);495 }496 CurrentTruncInst->replaceAllUsesWith(Res);497 498 // Erase old expression graph, which was replaced by the reduced expression499 // graph.500 CurrentTruncInst->eraseFromParent();501 // First, erase old phi-nodes and its uses502 for (auto &Node : OldNewPHINodes) {503 PHINode *OldPN = Node.first;504 OldPN->replaceAllUsesWith(PoisonValue::get(OldPN->getType()));505 InstInfoMap.erase(OldPN);506 OldPN->eraseFromParent();507 }508 // Now we have expression graph turned into dag.509 // We iterate backward, which means we visit the instruction before we510 // visit any of its operands, this way, when we get to the operand, we already511 // removed the instructions (from the expression dag) that uses it.512 for (auto &I : llvm::reverse(InstInfoMap)) {513 // We still need to check that the instruction has no users before we erase514 // it, because {SExt, ZExt}Inst Instruction might have other users that was515 // not reduced, in such case, we need to keep that instruction.516 if (I.first->use_empty())517 I.first->eraseFromParent();518 else519 assert((isa<SExtInst>(I.first) || isa<ZExtInst>(I.first)) &&520 "Only {SExt, ZExt}Inst might have unreduced users");521 }522}523 524bool TruncInstCombine::run(Function &F) {525 bool MadeIRChange = false;526 527 // Collect all TruncInst in the function into the Worklist for evaluating.528 for (auto &BB : F) {529 // Ignore unreachable basic block.530 if (!DT.isReachableFromEntry(&BB))531 continue;532 for (auto &I : BB)533 if (auto *CI = dyn_cast<TruncInst>(&I))534 Worklist.push_back(CI);535 }536 537 // Process all TruncInst in the Worklist, for each instruction:538 // 1. Check if it dominates an eligible expression graph to be reduced.539 // 2. Create a reduced expression graph and replace the old one with it.540 while (!Worklist.empty()) {541 CurrentTruncInst = Worklist.pop_back_val();542 543 if (Type *NewDstSclTy = getBestTruncatedType()) {544 LLVM_DEBUG(545 dbgs() << "ICE: TruncInstCombine reducing type of expression graph "546 "dominated by: "547 << CurrentTruncInst << '\n');548 ReduceExpressionGraph(NewDstSclTy);549 ++NumExprsReduced;550 MadeIRChange = true;551 }552 }553 554 return MadeIRChange;555}556