This is an archive of the discontinued LLVM Phabricator instance.

[InstCombineCasts] Add cost model to decide which truncates are worth removing

Authored by igor-laevsky on Aug 13 2015, 9:56 AM.



This is based on

Currently InstCombiner will eliminate truncate only 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 calls "EstimateCostForTruncatedEvaluation" and compares cost of the truncation with constant threshold. Cost model is very simple - we want to truncate expression tree only if we will remove more instructions than we will add.

Diff Detail


Event Timeline

igor-laevsky retitled this revision from to [InstCombineCasts] Add cost model to decide which truncates are worth removing.
igor-laevsky updated this object.
igor-laevsky added a reviewer: majnemer.
igor-laevsky set the repository for this revision to rL LLVM.
igor-laevsky added a subscriber: llvm-commits.
hfinkel added inline comments.

Currently cost model is simple -> Currently, the cost model is simple


This does not seem right. Arbitrary instructions don't commute with truncation, by which I mean trunc(arbitrary(x, y)) != arbitrary(trunc(x), trunc(y)) in general. Also, for many instructions you'd hit the llvm_unreachable in the default case in EvaluateInDifferentType.

igor-laevsky added a reviewer: hfinkel.
igor-laevsky marked an inline comment as done.Aug 17 2015, 7:21 AM
igor-laevsky added inline comments.

Thanks for taking a look.

You are right, but I am not relying on trunc's associativity. When we visit unknown instruction, we will stop looking deeper into expression tree and truncate it right before problematic instruction. For example say we have something like this:
add i64 (i64 bad_inst1(a, b), i64 bad_inst2(c, d))
EstimateCostForTruncatedEvaluation we will return true for this expression, and EvaluateInDifferentType will do the following transform:
add i32 (trunc (i64 bad_inst1(a, b)), trunc (i64 bad_inst2(c, d)))

Regarding your second question. Sorry, I should have better emphasise that this revision is based on which extends default case in EvaluateInDifferentType to allow it to insert truncates.

igor-laevsky abandoned this revision.Feb 27 2017, 8:29 AM