Hello Chapel developers,
With recent work on tuplesVSarrays performance issue I noticed that part of
performance degradation was related to aliasing. I have discovered quite
trivial case where adding noalias and alias.scope metadata would greatly
improve performance, due to LLVM being unable to notice that specific array
doesn't alias:
Here is a link to the full file:
https://github.com/coodie/chapel/blob/2d1e0c52a7727bda863afb9e43f626
1d321d1aa2/test/llvm/noalias-experiment/experiment.chpl
Here is most relevant part of the code:
for i in Dom do
for k in 1..subOrder do
Array[i] = subArray[k];
Array and subArray are trivially known not to alias (because both of these
symbols aren't references so they cannot alias). In this case this is
equivalent to:
const x = subArray[subOrder];
for i in Dom do
Array[i] = x;
But LLVM is unable to see that. What I did is adding specific metadata that
says that loads and stores in `Array[i] = subArray[k];` assignment don't
alias, and in this particular case it gave performance improvement - the
code run 3x faster with subOrder of 30, but gave improvement when subOrder
was smaller which is not surprising as there was less stores to eliminate.
I believe there are more complex (and useful) cases where extra information
about aliasing would improve performance due to some optimizations occuring
and this is what I'm currently trying to find which is quite difficult,
because adding metadata the way I did for this experiment is incredibly
tedious and difficult when there are more arrays.
My idea for adding this metadata would be for expressions that contain
array symbol that are known not to alias (because, say they are all marked
as 'var'). That's probably not the most precise explanation, but what I
want to say is that I just want to cover simple and obvious cases. Here is
clearer example of place where I find adding this metadata is plausible:
var A : [1..a];
var B : [1..b];
var C : [1..c];
//... possibly some computation here
for i in 1..a do
for j in 1..b do
for k in 1..c do
A[i] = A[i]+B[j]*C[k];
In the innermost loop expression we can mark references to A[i], B[j] and
C[k] to be not aliasing.
The way it is done in LLVM is to create metadata for domain, add metadata
for every 'scope', create lists of scopes and then mark loads and stores
using alias.scope and noalias metadata. When operation is marked using
noalias with reference to list of scopes, this means that this load doesn't
alias with with scopes in this list. When operation is marked with
alias.scope it means that this operation refers to certain scopes.
I think it's best to actually read the documentation as it's described
pretty well in there:
http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata
Basic idea is fairly simple: for every distinct array symbol in expression
create new scope, and list of scopes not containing this array's scope but
al remaining ones in the expression. Then mark all loads and stores to this
array using noalias with list of remaining arrays and alias.scope with
scope referring only to this array.
So in general, when we generate store and load we need to know at this
point:
1) Expression we are in
2) Array symbol we are referring to
3) Whether expression is good candidate to add the metadata
Current chapel compiler implementation doesn't make it very easy to access
any of that information in functions generating stores and loads
(codegenStoreLLVM, codegenLoadLLVM) and before compiler gets to the
codegen, there is a lot of things going on. Since I'm excited about this
It'd be great if some developer helped me with that (someone who knows AST
and LLVM relatively well).
Anyway, I'd like to receive some feedback on general idea: which cases we
could cover (they don't necessarily need to be related to arrays), would it
be easy/hard to implement, where it could possibly improve performance.
Cheers, Przemek
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Chapel-developers mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-developers
