Patch for llvm::DepthFirstIterator.h and llvm::PostOrderIterator.h

Hi @clang and @llvm,

attached you'll find a patch dealing with some iterator issues I already mentioned in both lists. Since there was no reaction I cross-post again - now IMHO production-ready code.
The patch is considered to get checked-in out of the box. It should not affect the behavior of existing and working code. I really need it for clang AST processing.

Changes:
1. Both iterators now can deal with sub-nodes==0 - they just skip them silently. For AST processing this is badly needed as you sometimes have 0-nodes in the AST (e.g. in 'for(;:wink: {}'). Until now both iterators crash if they traverse a sub-node==0.
2. In llvm::PostOrderIterator.h I fixed a compile bug which occured if used with external storage (which apparently nobody does until now).
3. I changed the behavior of llvm::DepthFirstIterator.h regarding the retrieving of the first child. This is now retrieved in exactly that moment it's needed. Until now it was retrieved too early, thus you actually couldn't change the childs of a just processed node. I can't think of an insane working example, which would break due to this change.
4. I added a public skipChilds member function to df_iterator which acts similiar to operator++. However it skips all childs of the currently processed node and returns *this. You can use it like in
for (i = df_begin(), e = df_end(); i!=e;)
{
  foo() ? i.skipChilds() : ++i;
}

Best
Olaf Krzikalla

llvm-iterator.patch (5.24 KB)

Hi Olaf,

This patch looks good to me. I just have a few minor comments:

> + inline df_iterator() { CurrentTopNode = 0; /* End is when stack is empty */ }

Should the comment here be updated to say that the End
is reached when the stack is empty and when CurrentTopNode
is null?

> + inline void toNext()
> + {

LLVM style puts the open brace on the same line as the function name.

> + inline _Self& skipChilds() { // skips all childs of the current node and traverses to next node

The plural of "child" is "children"; please rename this function
accordingly. Also, please format this line and a few others so
that they don't exceed 80 columns.

Thanks,

Dan

Dear staff,

     I downloaded an llvm version from the svn trunk at June 12, because the released 2.5 version can not support "gcc -g -Ox", and x=1,2,3. I use the version in svn to compile an httpd.bc file succefully with dbgstoppoint() functions. However, when I use llc to compile the bc file to .s file (llc -f -o httpd.s httpd.bc), I met this error (the httpd.bc file will be attached at the next email):

llc: /home/heming/defens/llvm-2.5/lib/CodeGen/AsmPrinter/DwarfDebug.cpp:1235: void llvm::DwarfDebug::ConstructCompileUnit(llvm::GlobalVariable*): Assertion `!MainCU && "Multiple main compile units are found!"' failed.
0 llc 0x00000000011c0f6c
1 llc 0x00000000011c148a
2 libpthread.so.0 0x00007fa91db297d0
3 libc.so.6 0x00007fa91cc3a095 gsignal + 53
4 libc.so.6 0x00007fa91cc3baf0 abort + 272
5 libc.so.6 0x00007fa91cc332df __assert_fail + 239
6 llc 0x0000000000ebfdad
7 llc 0x0000000000ebffa6
8 llc 0x0000000000ec2f7b
9 llc 0x0000000000eb95e0 llvm::DwarfWriter::BeginModule(llvm::Module*, llvm::MachineModuleInfo*, llvm::raw_ostream&, llvm::AsmPrinter*, llvm::TargetAsmInfo const*) + 166
10 llc 0x0000000000b9b513
11 llc 0x0000000001142c73 llvm::FPPassManager::doInitialization(llvm::Module&) + 65
12 llc 0x0000000001142d96 llvm::FunctionPassManagerImpl::doInitialization(llvm::Module&) + 58
13 llc 0x0000000001142e01 llvm::FunctionPassManager::doInitialization() + 41
14 llc 0x000000000084b43d main + 2481
15 libc.so.6 0x00007fa91cc261c4 __libc_start_main + 244
16 llc 0x0000000000849849
Stack dump:
0. Program arguments: llc -f -o httpd.s httpd.bc
Aborted

Quoting hc2428@columbia.edu:

The httpd.bc file is compiled with "-g -O0" option (I pass "-g -O0" to CFLAGS). If I eliminate the -g option (just pass "-O0" to CFLAGS), I got the httpd.bc file with a size of 1.1M bytes, and the llc can compile the httpd.bc file to httpd.s file. If I added the -g option, I got the httpd.bc file with a size of 3.8M bytes, and I got the error as below when using llc.

Quoting hc2428@columbia.edu:

Here is the httpd.bc file I got with "-g -O0" option.

httpd.bc.tar.gz (1.8 MB)

hc2428@columbia.edu wrote:

Dear staff,

     I downloaded an llvm version from the svn trunk at June 12, because the released 2.5 version can not support "gcc -g -Ox", and x=1,2,3. I use the version in svn to compile an httpd.bc file succefully with dbgstoppoint() functions. However, when I use llc to compile the bc file to .s file (llc -f -o httpd.s httpd.bc), I met this error (the httpd.bc file will be attached at the next email):

llc: /home/heming/defens/llvm-2.5/lib/CodeGen/AsmPrinter/DwarfDebug.cpp:1235: void llvm::DwarfDebug::ConstructCompileUnit(llvm::GlobalVariable*): Assertion `!MainCU && "Multiple main compile units are found!"' failed.

http://llvm.org/PR3494 . I'm guessing you did what I did; took a bunch of .bc files compiled with debug info and merged them with llvm-link or llvm-ld or some other sort of merge, then tried to compile the result. This is known broken.

Nick

Hi,

I've done all the minor changes you recommended and have attached a new patch including both files again (even if po_iterator didn't change).
However:

Dan Gohman schrieb:

The plural of "child" is "children"; please rename this function
accordingly.

Is "childs" just sloppy, is it american english or is it just a misconception of foreigners like me?
I think I've already seen it somewhere.

Best
Olaf

llvm-iterator.patch (5.34 KB)

"Childs" is a last name, and "child's" is posessive, but no native
English speaker would ever use "childs".

-Eli

Hi,

I've done all the minor changes you recommended and have attached a new patch including both files again (even if po_iterator didn't change).

Ok, it looks good to me.

However:

Dan Gohman schrieb:

The plural of "child" is "children"; please rename this function

accordingly.

Is "childs" just sloppy, is it american english or is it just a misconception of foreigners like me?
I think I've already seen it somewhere.

Sloppiness seems unlikely here, and it's not specific to American English.

Dan