Page MenuHomePhabricator

jkreiner (Justin Kreiner)
User

Projects

User does not belong to any projects.

User Details

User Since
Mar 10 2021, 1:07 PM (14 w, 4 d)

Recent Activity

Fri, May 28

jkreiner updated subscribers of D99205: Add jump-threading optimization for deterministic finite automata.

Naive question: does your new pass "result in irreducible control flow that harms other optimizations"? From the ASCII art diagram in the commit message it looks like it does. Why is that OK?

It could produce irreducible control flow like that, but the pass is late enough in the pipeline that it won't have a negative impact. I experimented with putting it early in the pipeline and the gains I measured weren't great, but it seems to be profitable where it is right now.

Naive follow-up question: why does this have to be a complete new implementation of jump threading? Would it be feasible to have a single implementation that takes a "don't create irreducible control flow" flag?

Fri, May 28, 8:12 AM · Restricted Project

Thu, May 27

jkreiner updated the diff for D99205: Add jump-threading optimization for deterministic finite automata.
Thu, May 27, 11:54 AM · Restricted Project
jkreiner added a comment to D99205: Add jump-threading optimization for deterministic finite automata.

For our downstream arch we're seeing gains up to 27%.

Thu, May 27, 11:01 AM · Restricted Project

Wed, May 26

jkreiner updated the diff for D99205: Add jump-threading optimization for deterministic finite automata.

Fixed a failing opt pipeline test.

Wed, May 26, 1:40 PM · Restricted Project
jkreiner updated the diff for D99205: Add jump-threading optimization for deterministic finite automata.

Addressed reviewer comments, and moved the pass earlier in the pipeline.

Wed, May 26, 11:52 AM · Restricted Project

May 21 2021

jkreiner added inline comments to D99205: Add jump-threading optimization for deterministic finite automata.
May 21 2021, 1:35 PM · Restricted Project
jkreiner added inline comments to D99205: Add jump-threading optimization for deterministic finite automata.
May 21 2021, 6:53 AM · Restricted Project

May 18 2021

jkreiner added inline comments to D99205: Add jump-threading optimization for deterministic finite automata.
May 18 2021, 7:38 AM · Restricted Project

May 13 2021

jkreiner added a comment to D99205: Add jump-threading optimization for deterministic finite automata.

I removed the unnecessary conditions, and used the llvm::DenseMap instead.

May 13 2021, 11:54 AM · Restricted Project
jkreiner updated the diff for D99205: Add jump-threading optimization for deterministic finite automata.

Implemented a cost model to avoid cloning too much code, and addressed reviewer comments.

May 13 2021, 10:51 AM · Restricted Project

May 4 2021

jkreiner added a comment to D99205: Add jump-threading optimization for deterministic finite automata.

In case anyone is interested, there is some context about this patch over here: https://reviews.llvm.org/D88307

May 4 2021, 2:33 PM · Restricted Project
jkreiner added a comment to D99205: Add jump-threading optimization for deterministic finite automata.

If we're going to be cloning basic blocks, we need some sort of cost computation. Some blocks aren't legal to clone, and some are expensive simply due to size. (Illegal to clone like this: convergent, noduplicate, indirectbr predecessors.) See llvm/Analysis/CodeMetrics.h.

That is a good point, I agree we will need a cost model for the transformation. I have started working on one and gathering more performance stats. Also thanks for sharing CodeMetrics.h, I can add a check for those types of blocks that aren't legal to clone.

May 4 2021, 2:14 PM · Restricted Project
jkreiner updated the diff for D99205: Add jump-threading optimization for deterministic finite automata.

There were some formatting issues with the previous diff.

May 4 2021, 1:15 PM · Restricted Project
jkreiner updated the diff for D99205: Add jump-threading optimization for deterministic finite automata.
May 4 2021, 12:47 PM · Restricted Project

Apr 16 2021

jkreiner added a comment to D99205: Add jump-threading optimization for deterministic finite automata.
Apr 16 2021, 1:45 PM · Restricted Project
jkreiner added a comment to D99205: Add jump-threading optimization for deterministic finite automata.

Hi everyone, I wanted to give another progress update on this patch. We have gotten the transformation working on the coremark opportunity resulting in a speedup of over 20% for the benchmark. It also works on some smaller testcases such as std::merge. We are in the process of testing it more extensively and debugging issues that come up. Also there is still some work with cleaning up the codegen, refactoring, and writing test cases. An updated version will be submitted soon.

Apr 16 2021, 11:17 AM · Restricted Project

Mar 23 2021

jkreiner added a comment to D88307: [DON'T MERGE] Jump-threading for finite state automata.

Hi, I have posted the analysis mentioned above: https://reviews.llvm.org/D99205

Mar 23 2021, 2:07 PM · Restricted Project
jkreiner updated the summary of D99205: Add jump-threading optimization for deterministic finite automata.
Mar 23 2021, 1:57 PM · Restricted Project
jkreiner updated the diff for D99205: Add jump-threading optimization for deterministic finite automata.
Mar 23 2021, 12:56 PM · Restricted Project
jkreiner requested review of D99205: Add jump-threading optimization for deterministic finite automata.
Mar 23 2021, 12:16 PM · Restricted Project

Mar 10 2021

jkreiner added a comment to D88307: [DON'T MERGE] Jump-threading for finite state automata.

Hi, I just wanted to give an update about the pass @amehsan mentioned before. We revised the implementation so that it handles more general cases such as the std::merge example provided above. The core idea remains the same of using an analyze-then-transform approach to first find paths in an FSM that have the opportunity to be threaded, and then transforming them to skip over the expensive switch operation when it is possible to do so.

Mar 10 2021, 1:39 PM · Restricted Project