This is an archive of the discontinued LLVM Phabricator instance.

Allow InstCombiner to eliminate truncates even if it will require inserting additional instructions
AbandonedPublic

Authored by igor-laevsky on Jun 19 2015, 7:53 AM.

Details

Summary

Currently InstCombiner can eliminate truncate when entire expression tree can be evaluated in a narrower type without adding additional instructions.

However there are some cases when it is profitable to evaluate expression in a narrower type, even if it will require adding additional instructions. (See test case in the patch)

In this patch I split "CanEvaluateTruncated" function into two: "EstimateCostForTruncatedEvaluation" and "IsProfitableToEvaluateTruncated". First one is basically an old "CanEvaluateTruncated", but it also calculates cost for truncating expression tree. Second function basically just calls "EstimateCostForTruncatedEvaluation" and compares cost of the truncation with some threshold.

Currently cost model is very simple - we want to truncate expression tree only if we will remove more instructions than we will add. Probably it can be somehow adjusted in the future.

Diff Detail

Repository
rL LLVM

Event Timeline

igor-laevsky retitled this revision from to Allow InstCombiner to eliminate truncates even if it will require inserting additional instructions.
igor-laevsky updated this object.
igor-laevsky edited the test plan for this revision. (Show Details)
igor-laevsky added reviewers: reames, sanjoy, majnemer.
igor-laevsky set the repository for this revision to rL LLVM.
igor-laevsky added a subscriber: Unknown Object (MLST).
sanjoy requested changes to this revision.Jun 22 2015, 10:41 AM
sanjoy edited edge metadata.

Overall, I think this is going in the right direction.

Some comments inline.

lib/Transforms/InstCombine/InstCombineCasts.cpp
234

Don't construct a std::string here -- just using I->getName() + ".truncated" will construct an llvm::Twine for you.

237

Use InsertBefore = I->getNextNode()

239

I'm not sure I understand this assert -- InsertBefore is not the instruction instcombine visited, right?

342

Nit: "increase"

345

If we change the bit handing the !isa<Instruction> case below, will we need this to return a bool? Or will it always "succeed"?

352

Why does the This is not a recognized instruction bit apply here?

471

I'd just move this within InstCombiner. Then you won't need IC and will be able to use ShouldChangeType without making it public.

This revision now requires changes to proceed.Jun 22 2015, 10:41 AM
igor-laevsky edited edge metadata.
igor-laevsky added inline comments.
lib/Transforms/InstCombine/InstCombineCasts.cpp
234

done

237

done

239

Naming is slightly confusing here. I have changed it a bit.

342

done

352

"V" could be Argument, MetadataAsValue, InlineAsm or BasicBlock.

We can handle Argument by adding special case into "EvaluateInDifferentType".

Probably for MetadataAsValue and BasicBlock we can just assert false - should not meet this instructions in arithmetic expression trees.

InlineAsm we can probably handle similarly to the Argument, but I am not absolutely sure how it works.

This are possible extensions, but they feel more like a separate change.

471

Agree. Actually both "IsProfitableToEvaluateTruncated" and "EstimateCostForTruncatedEvaluation" should live inside InstCombiner. I don't want to add too much unrelated refactoring, so I will do this in a separate change and move "ShouldChangeType" back to the private section.

sanjoy added inline comments.Jun 24 2015, 7:36 PM
lib/Transforms/InstCombine/InstCombineCasts.cpp
228

Spelling: guaranteed

238

I still don't understand this assert: why can't you have IR like:

%i = add i32 ...  ;; I == %i
br label %foo

foo:
use(%i)
340

Nit: "arrive at the same value"

342

Nit: "increase cost"

343

Nit: decrease

352

We can handle Argument by adding special case into "EvaluateInDifferentType"

Why would you need any special casing in EvaluateInDifferentType? Doesn't it have a catch-all that will take any iN to iM by using a trunc instruction?

360–365

We can eliminate the extension only if it has at most one use. Right now, if I'm reading the code correctly, you'll consider this case to be profitable:

X = f()
Y = g()

A = zext(B) from i32 to i64
C = zext(D) from i32 to i64

M = A + C + X + Y

use(A)
use(C)

and translate it to

X = f()
Y = g()

A = zext(B) from i32 to i64
C = zext(D) from i32 to i64

M = B + D + trunc(X) + trunc(Y)

use(A)
use(C)
454–455

I'd either remove the default: break; or move this bit of logic into the default: clause.

465

What is Ty?

471

Use either Instruction *I or Value *V.

igor-laevsky edited edge metadata.
igor-laevsky added inline comments.
lib/Transforms/InstCombine/InstCombineCasts.cpp
238

I->getParent()->end() is end of the instruction list, not a terminator instruction. We will fail this assertion if "I" was a terminator. In other words "I++ == BB->end()"

352

Yes, but special case is required to determine place where to insert this additional explicit trunc. I am not saying this is anyhow complicated, just seems more like a separate change.

360–365

That's right. I fixed the patch to update cost only for casts with single use.

Overall, this LGTM given that the cleanup changes discussed happen promptly. However, I'd wait for @majnemer to take a final look before checking in.

lib/Transforms/InstCombine/InstCombineCasts.cpp
225

It isn't clear what 'truncating expression type' means here. Can you turn this into an assert?

238

Yes, you're right. I confused myself.

371

Given that we're now tracking a generalized cost, does it make sense to remove this and have

case Inst::Add:
  bool Left = EstimateCostFor(LHS);
  bool Right = EstimateCostFor(LHS);
  if (Left && Right) {
    if (!I->hasOneUse())
      Cost++;  // new add instruction  (or may be +=2 because of code duplication)
    return true;
  } else return false;

(Not necessarily in this change, but in a later change?)

igor-laevsky added inline comments.Jun 30 2015, 9:11 AM
lib/Transforms/InstCombine/InstCombineCasts.cpp
225

There is an assertion for this on the next line. It checks that we can reach destination type by applying truncate instruction.

371

It is possible. However I would be careful about such transform since it increases register pressure, some targets might not respond to this change positively.

Gentle ping. @majnemer, can you please take a quick look at this?

reames edited edge metadata.Jul 31 2015, 4:50 PM

Looking through the patch, this looks entirely reasonable to me. However, I'm not comfortable enough with this code to sign off. Can we get someone familiar with InstCombine and our canonicalization rules around truncation to take a quick look?

lib/Transforms/InstCombine/InstCombineCasts.cpp
488

You might consider passing the CostThreshold in to CanEvaluateTruncated and return early if the running cost estimate ever gets too high above CostThreshold. We want to allow analysis of cases close to the threshold, but not burn a lot of compile time. Having said that, I'm just being pedantic. I don't think this is an actual issue.

igor-laevsky added inline comments.Aug 11 2015, 6:28 AM
lib/Transforms/InstCombine/InstCombineCasts.cpp
488

Thanks for taking a look.

I think it would be easier to just bailout on the number of visited instruction. It would give direct control on the maximum number of iterations which directly affects compile time.

Anyway I am not changing iteration count for this method. I guess if no one ever got a problem with it, I should not address it either. At least not in this change.

igor-laevsky edited edge metadata.
majnemer edited edge metadata.Aug 12 2015, 12:01 PM

Could this be split into two changes: one which adds the cost model and another which teaches EvaluateInDifferentType how to insert truncates?

Could this be split into two changes: one which adds the cost model and another which teaches EvaluateInDifferentType how to insert truncates?

Sure. Please take a look at http://reviews.llvm.org/D12012 and http://reviews.llvm.org/D12013

igor-laevsky abandoned this revision.Aug 13 2015, 9:58 AM