On 04/20/2013 01:42 PM, Christian König wrote:
Am 19.04.2013 18:50, schrieb Vadim Girlin:
On 04/19/2013 08:35 PM, Christian König wrote:
Hey Vadim,
Am 19.04.2013 18:18, schrieb Vadim Girlin:
[SNIP]
In theory, yes, some optimizations in this branch are typically used
on the earlier compilation stages, not on the target machine code. On
the other hand, there are some differences that might make it harder,
e.g. many algorithms require SSA form, and though it's possible to do
similar optimizations without SSA, it would be hard to implement.
Also
I wanted to support both default backend and llvm backend for
increased testing coverage and to be able to compare the
efficiency of
the algorithms in my experiments etc.
Yeah I know, missing an SSA implementation is also something that
always
bothered me a bit with both TGSI and GLSL (while I haven't done much
with GLSL, so maybe I misjudge here).
Can you name the different algorithms used?
There is a short description of the algorithms and passes in the
notes.markdown file [1] in that branch, there are also links in the
end to the full description of some algorithms, though some of them
were modified/adapted for this branch.
It's not a strict prerequisite, but I think we both agree that doing
things like LICM on R600 bytecode isn't the best idea over all (when
doing it on GLSL would be beneficial for all drivers not only r600).
In fact there is no special LICM pass, it's done by the GCM (Global
Code Motion, [2]), which probably could be also called global
scheduler. In fact in my branch this pass is combined with some
hw-specific scheduling logic, e.g. grouping fetch/alu instructions to
reduce clause type switching in the code and the number of required CF
instructions, potentially it can also schedule clauses to expose more
parallelism with the BARRIER bit usage.
Yeah I already thought that you're using something like this.
On one hand that is really good, cause it is specialized on so produces
really optimal code for the r600 target. But on the other hand it's bad,
cause it is specialized on so produces really optimal code ONLY on the
r600 target....
I think such pass on higher level (GLSL IR or TGSI) would at least
need some callbacks or caps to be tunable for the target.
Anyway the result of GCM pass is affected by the CFG structure, so
when the target applies e.g. if-conversion or any other
target-specific control flow optimization, this means that you might
want to apply similar pass again on the target instruction level for
better results, and then previous pass on higher level IR looks not
very useful.
Also there are some high level operations that are translated to the
bunch of target instructions, e.g. integer division on r600.
High-level pass can't hoist "i/5" (where i is loop counter) out of the
loop, but after translation to target instructions it's possible to
hoist some of the resulting instructions, producing more efficient code.
One more point is that GCM allows to achieve best efficiency when used
with GVN (Global Value Numbering) pass, e.g. GCM allows GVN to not
care about code placement during elimination of redundant operations,
so you'll probably want to implement high-level GVN pass as well.
I think it's possible to implement GVN-GCM on GLSL or TGSI level, but
I suspect it will require a lot more efforts than it was required by
implementation of these passes in my branch, and will be less efficient.
Just speculating, what would it take to make those passes run on the
LLVM Machine Instruction representation instead of your own
representation?
Main difference between IRs is the representation of control flow,
r600-sb relies on the fact that r600 arch doesn't have arbitrary
control flow, this renders CFGs superfluous. Implementation of these
passes on CFGs will be more complicated, it will also require the
computation of dominance frontiers, loops detection and analysis, etc.
On the r600-sb's IR these passes are greatly simplified.
Regarding the GCM, original algorithm as described in that pdf works
on the CFG, so it shouldn't be hard to implement in LLVM, but I'm not
sure how it will fit into the LLVM infrastructure. LLVM has GVN-PRE,
LICM and other passes that together do basically the same thing as
GVN-GCM, so if you implement it, you might want to get rid of LLVM's
own passes that duplicate the same functionality, and I'm not sure if
this would be easy, possibly there are some interdependencies etc.
Also I saw mentions of some plans (e.g. [1],[2]) regarding the
implementation of global code motion in LLVM, looks like there is
already some work in progress.
