Eliminate domset from LLVM #1543
Comments
|
Chris points out that domset is O(n^2) and should just be eliminated. |
|
on top of that, it's incredibly inefficient, even for being N^2 :) |
|
The .bc file doesn't disassemble anymore. Can you please attach a gzip'd .ll file? -Chris |
|
I think, the source "testcase" was: #define C(a,b) #define C4(x,b) C((x)[0], b) C((x)[1],b) C((x)[2],b) C((x)[3],b) #define C64(x,y) C16(x,y) C16(x+4,y) C16(x+8,y) C16(x+12,y) #define C1024(x,y) C256(x,y) C256(x+16,y) C256(x+32,y) C256(x+48,y) unsigned foo(int x[64], int y[64]) return 0x01234567; |
|
The attachment is a .ll.bz2. I probably should've mentioned that. |
|
Ah, ok. So this is a simple case where you have a) a very very large program, and b) N^2 domsets. The best solution is to eliminate domset from LLVM, so I'll change the title. ET-Forest is now the preferred datastructure for most dom-set-like queries. -Chris |
|
One place to start: LoopSimplify uses DominatorSet+DomTree. Instead, it should use ETForest+DomTree. -Chris |
|
This is done, as of the following patches. I'm going to keep this bug open to http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046938.html |
|
These changes prevents llvm-gcc from building. I'm attaching full testcase and Steps to reproduce: |
|
The "bad" patch is the one applied to LoopSimplify.cpp |
|
So, I reverted two LoopSimplify.cpp patches and big "purge" patch (due to need |
|
This is done, right Owen? Care to close it? |
|
This is, indeed, done. |
A dummy argument in an entry point of a subprogram with multiple
entry points need not be defined in other entry points. It is only
legal to reference such an argument when calling an entry point that
does have a definition. An entry point without such a definition
needs a local "substitute" definition sufficient to generate code.
It is nonconformant to reference such a definition at runtime.
Most such definitions and associated code will be deleted as dead
code at compile time. However, that is not always possible, as in
the following code. This code is conformant if all calls to entry
point ss set m=3, and all calls to entry point ee set n=3.
subroutine ss(a, b, m, d, k) ! no x, y, n
integer :: a(m), b(a(m)), m, d(k)
integer :: x(n), y(x(n)), n
integer :: k
1 print*, m, k
print*, a
print*, b
print*, d
if (m == 3) return
entry ee(x, y, n, d, k) ! no a, b, m
print*, n, k
print*, x
print*, y
print*, d
if (n /= 3) goto 1
end
integer :: xx(3), yy(5), zz(3)
xx = 5
yy = 7
zz = 9
call ss(xx, yy, 3, zz, 3)
call ss(xx, yy, 3, zz, 3)
end
Lowering currently generates fir::UndefOp's for all unused arguments.
This is usually ok, but cases such as the one here incorrectly access
unused UndefOp arguments for m and n from an entry point that doesn't
have a proper definition.
The problem is addressed by creating a more complete definition of an
unused argument in most cases. This is implemented in large part by
moving the definition of an unused argument from mapDummiesAndResults
to mapSymbolAttributes. The code in mapSymbolAttributes then chooses
one of three code generation options, depending on information
available there.
Extended Description
This attachment causes -domset to eat up more than 512MB of RAM. Test with
"ulimit -v $((512*1024))"
The text was updated successfully, but these errors were encountered: