This attachment causes -domset to eat up more than 512MB of RAM. Test with "ulimit -v $((512*1024))"
Created attachment 632 [details] testcase $ ulimit -v $((512*1024)) $ llvm/Debug/bin/opt -domset bugpoint-passes.bc WARNING: You're attempting to print out a bytecode file. This is inadvisable as it may cause display problems. If you REALLY want to taste LLVM bytecode first-hand, you can force output with the `-f' option. terminate called after throwing an instance of 'St9bad_alloc' what(): St9bad_alloc Aborted
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) \ if (a > b) goto gt; \ if (a < b) goto lt; #define C4(x,b) C((x)[0], b) C((x)[1],b) C((x)[2],b) C((x)[3],b) #define C16(x,y) C4(x, (y)[0]) C4(x, (y)[1]) C4(x, (y)[2]) C4(x, (y)[3]) #define C64(x,y) C16(x,y) C16(x+4,y) C16(x+8,y) C16(x+12,y) #define C256(x,y) C64(x,y) C64(x,y+4) C64(x,y+8) C64(x,y+12) #define C1024(x,y) C256(x,y) C256(x+16,y) C256(x+32,y) C256(x+48,y) #define C4096(x,y) C1024(x,y) C1024(x,y+16) C1024(x,y+32) C1024(x,y+48) unsigned foo(int x[64], int y[64]) { C4096(x,y); return 0x01234567; gt: return 0x12345678; lt: return 0xF0123456; }
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 track any fallout from these changes. Hopefully there won't be any! http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046938.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046939.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046940.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046941.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046942.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046943.html
These changes prevents llvm-gcc from building. I'm attaching full testcase and bugpoint-reduced. Steps to reproduce: ./opt -licm
Created attachment 766 [details] "Source" .bc
Created attachment 767 [details] Bugpoint-reduced testcase
The "bad" patch is the one applied to LoopSimplify.cpp
So, I reverted two LoopSimplify.cpp patches and big "purge" patch (due to need of DomSet for LoopSimplify). This fixed llvm-gcc.
This is done, right Owen? Care to close it?
This is, indeed, done.