Traditional Dataflow Algorithm

Is there a traditional dataflow algorithm buried in LLVM somewhere? I
need to be able to do some very late transformations (after regalloc)
and we aren't in SSA anymore. I will need a dataflow analysis to ensure
correctness.

At one point I thought I remembered seeing a generic fixed-point
dataflow analysis engine but now I can't find it. Does it still exist
or did it ever exist? If it's not there, would folks be interested in
such a thing if I wrote one?

                             -David

Is there a traditional dataflow algorithm buried in LLVM somewhere? I
need to be able to do some very late transformations (after regalloc)
and we aren't in SSA anymore. I will need a dataflow analysis to ensure
correctness.

At one point I thought I remembered seeing a generic fixed-point
dataflow analysis engine but now I can't find it. Does it still exist
or did it ever exist? If it's not there, would folks be interested in
such a thing if I wrote one?

I might have use for a machine instruction level dataflow analysis for a project that I'm working on.

-- John T.

Generic MI level data flow across virtual registers could make sense. Although the generic part is trivial anyway, so implementing it as some kind of template seems silly until we have multiple clients.

David was asking for a post-register-rewrite analysis, which I think is a totally different problem and best implemented separately by each target. The target knows best which register units are overwritten or preserved by an operation. We try to fake it with undef/implicit-use/implicit-def, but it isn't reliable. Reaching defs just can't be reliably rediscovered in a generic way after we drop explicit subregister information.

-Andy

Andrew Trick <atrick@apple.com> writes:

David was asking for a post-register-rewrite analysis, which I think
is a totally different problem and best implemented separately by each
target. The target knows best which register units are overwritten or
preserved by an operation. We try to fake it with
undef/implicit-use/implicit-def, but it isn't reliable. Reaching defs
just can't be reliably rediscovered in a generic way after we drop
explicit subregister information.

I don't see why not. All of the subregister information is exposed in a
generic way through TargetRegisterInfo.

Your statement that undef/implicit-use/implicit-def isn't reliable is
news to me. It seems unsafe to even provide it if it's incorrect.

                             -David

Andrew Trick <atrick@apple.com> writes:

David was asking for a post-register-rewrite analysis, which I think
is a totally different problem and best implemented separately by each
target. The target knows best which register units are overwritten or
preserved by an operation. We try to fake it with
undef/implicit-use/implicit-def, but it isn’t reliable. Reaching defs
just can’t be reliably rediscovered in a generic way after we drop
explicit subregister information.

I don’t see why not. All of the subregister information is exposed in a
generic way through TargetRegisterInfo.

Your statement that undef/implicit-use/implicit-def isn’t reliable is

It may currently work well for your target. But it’s easy for other targets to add a pass that breaks these guarantees but still generates correct code.

The last example I remember from the mailing list was copying an ARM S register using two neon VEXTs.

news to me. It seems unsafe to even provide it if it’s incorrect.

I completely agree which is exactly why I think they should be eliminated and would discourage a generic postRA data flow framework based on them.

-Andy