39 #define DEBUG_TYPE "aggressive-instcombine"
43 "Number of truncations eliminated by reducing bit width of expression DAG");
45 "Number of instructions whose bit width was reduced");
50 unsigned Opc =
I->getOpcode();
52 case Instruction::Trunc:
53 case Instruction::ZExt:
54 case Instruction::SExt:
59 case Instruction::Sub:
60 case Instruction::Mul:
61 case Instruction::And:
63 case Instruction::Xor:
64 Ops.push_back(
I->getOperand(0));
65 Ops.push_back(
I->getOperand(1));
68 Ops.push_back(
I->getOperand(1));
69 Ops.push_back(
I->getOperand(2));
76 bool TruncInstCombine::buildTruncExpressionDag() {
82 Worklist.push_back(CurrentTruncInst->
getOperand(0));
84 while (!Worklist.empty()) {
85 Value *Curr = Worklist.back();
87 if (isa<Constant>(Curr)) {
92 auto *
I = dyn_cast<Instruction>(Curr);
102 InstInfoMap.insert(std::make_pair(
I,
Info()));
106 if (InstInfoMap.count(
I)) {
114 unsigned Opc =
I->getOpcode();
116 case Instruction::Trunc:
117 case Instruction::ZExt:
118 case Instruction::SExt:
125 case Instruction::Sub:
126 case Instruction::Mul:
127 case Instruction::And:
128 case Instruction::Or:
129 case Instruction::Xor:
149 unsigned TruncInstCombine::getMinBitWidth() {
156 unsigned OrigBitWidth =
159 if (isa<Constant>(Src))
160 return TruncBitWidth;
162 Worklist.push_back(Src);
163 InstInfoMap[cast<Instruction>(Src)].ValidBitWidth = TruncBitWidth;
165 while (!Worklist.empty()) {
166 Value *Curr = Worklist.back();
168 if (isa<Constant>(Curr)) {
174 auto *
I = cast<Instruction>(Curr);
176 auto &
Info = InstInfoMap[
I];
187 if (
auto *IOp = dyn_cast<Instruction>(Operand))
189 std::max(
Info.MinBitWidth, InstInfoMap[IOp].MinBitWidth);
195 unsigned ValidBitWidth =
Info.ValidBitWidth;
202 if (
auto *IOp = dyn_cast<Instruction>(Operand)) {
206 unsigned IOpBitwidth = InstInfoMap.lookup(IOp).ValidBitWidth;
207 if (IOpBitwidth >= ValidBitWidth)
209 InstInfoMap[IOp].ValidBitWidth = ValidBitWidth;
210 Worklist.push_back(IOp);
213 unsigned MinBitWidth = InstInfoMap.lookup(cast<Instruction>(Src)).MinBitWidth;
214 assert(MinBitWidth >= TruncBitWidth);
216 if (MinBitWidth > TruncBitWidth) {
232 bool FromLegal = MinBitWidth == 1 || DL.
isLegalInteger(OrigBitWidth);
233 bool ToLegal = MinBitWidth == 1 || DL.
isLegalInteger(MinBitWidth);
234 if (!DstTy->
isVectorTy() && FromLegal && !ToLegal)
240 Type *TruncInstCombine::getBestTruncatedType() {
241 if (!buildTruncExpressionDag())
248 unsigned DesiredBitWidth = 0;
249 for (
auto Itr : InstInfoMap) {
253 bool IsExtInst = (isa<ZExtInst>(
I) || isa<SExtInst>(
I));
254 for (
auto *U :
I->users())
255 if (
auto *UI = dyn_cast<Instruction>(U))
256 if (UI != CurrentTruncInst && !InstInfoMap.count(UI)) {
262 unsigned ExtInstBitWidth =
263 I->getOperand(0)->getType()->getScalarSizeInBits();
264 if (DesiredBitWidth && DesiredBitWidth != ExtInstBitWidth)
266 DesiredBitWidth = ExtInstBitWidth;
270 unsigned OrigBitWidth =
275 unsigned MinBitWidth = getMinBitWidth();
279 if (MinBitWidth >= OrigBitWidth ||
280 (DesiredBitWidth && DesiredBitWidth != MinBitWidth))
291 if (
auto *VTy = dyn_cast<VectorType>(V->
getType()))
296 Value *TruncInstCombine::getReducedOperand(
Value *V,
Type *SclTy) {
298 if (
auto *
C = dyn_cast<Constant>(V)) {
304 auto *
I = cast<Instruction>(V);
305 Info Entry = InstInfoMap.lookup(
I);
307 return Entry.NewValue;
310 void TruncInstCombine::ReduceExpressionDag(
Type *SclTy) {
311 NumInstrsReduced += InstInfoMap.size();
312 for (
auto &Itr : InstInfoMap) {
316 assert(!NodeInfo.NewValue &&
"Instruction has been evaluated");
319 Value *Res =
nullptr;
320 unsigned Opc =
I->getOpcode();
322 case Instruction::Trunc:
323 case Instruction::ZExt:
324 case Instruction::SExt: {
329 if (
I->getOperand(0)->getType() == Ty) {
330 assert(!isa<TruncInst>(
I) &&
"Cannot reach here with TruncInst");
331 NodeInfo.NewValue =
I->getOperand(0);
336 Res =
Builder.CreateIntCast(
I->getOperand(0), Ty,
337 Opc == Instruction::SExt);
344 auto *Entry =
find(Worklist,
I);
345 if (Entry != Worklist.end()) {
346 if (
auto *NewCI = dyn_cast<TruncInst>(Res))
349 Worklist.
erase(Entry);
350 }
else if (
auto *NewCI = dyn_cast<TruncInst>(Res))
351 Worklist.push_back(NewCI);
355 case Instruction::Sub:
356 case Instruction::Mul:
357 case Instruction::And:
358 case Instruction::Or:
359 case Instruction::Xor: {
360 Value *LHS = getReducedOperand(
I->getOperand(0), SclTy);
361 Value *RHS = getReducedOperand(
I->getOperand(1), SclTy);
366 Value *Op0 =
I->getOperand(0);
367 Value *LHS = getReducedOperand(
I->getOperand(1), SclTy);
368 Value *RHS = getReducedOperand(
I->getOperand(2), SclTy);
369 Res =
Builder.CreateSelect(Op0, LHS, RHS);
376 NodeInfo.NewValue = Res;
377 if (
auto *ResI = dyn_cast<Instruction>(Res))
381 Value *Res = getReducedOperand(CurrentTruncInst->
getOperand(0), SclTy);
385 Res =
Builder.CreateIntCast(Res, DstTy,
false);
386 if (
auto *ResI = dyn_cast<Instruction>(Res))
387 ResI->takeName(CurrentTruncInst);
396 for (
auto I = InstInfoMap.rbegin(),
E = InstInfoMap.rend();
I !=
E; ++
I) {
400 if (
I->first->use_empty())
401 I->first->eraseFromParent();
406 bool MadeIRChange =
false;
414 if (
auto *CI = dyn_cast<TruncInst>(&
I))
415 Worklist.push_back(CI);
421 while (!Worklist.empty()) {
424 if (
Type *NewDstSclTy = getBestTruncatedType()) {
426 dbgs() <<
"ICE: TruncInstCombine reducing type of expression dag "
428 << CurrentTruncInst <<
'\n');
429 ReduceExpressionDag(NewDstSclTy);