Compute the loop nest depth of each CfgNode and weight Variables by it.

tests_lit/llvm2ice_tests/loop-nest-depth.ll

+; Test the the loop nest depth is correctly calculated for basic blocks.
+

[jvoung (off chromium), 2015/09/01 18:56:18]

Can you check that this works with "make -f Makefile.standalone MINIMAL=1
check-lit"? I think it:

"REQUIRES: allow_dump"

[ascull, 2015/09/03 19:52:38]

Yep, MINIAL=1 fails but the require fixes things.

+; Single threaded so that the dumps used for checking happen in order
+; RUN: %p2i --filetype=obj --disassemble -i %s --args -O2 --verbose=loop \
+; RUN: --threads=0 | FileCheck %s
+

[Jim Stichnoth, 2015/09/01 22:17:38]

I'd like to see at least one test with loops and phi instructions (into and out
of the loop) and O2.  Perhaps simple_loop.ll is good enough.

[ascull, 2015/09/03 19:52:38]

Does the early exit satisfy this need?

All test are -O2 loop analysis only happen there.

+define void @test_single_loop(i1 %a) {

[jvoung (off chromium), 2015/09/01 18:56:18]

Hmm, technically PNaCl does not allow i1 parameters, only i32 and larger (i.e.,
i64):
https://developer.chrome.com/native-client/reference/pnacl-bitcode-abi#scalar...
(this is because most targets have 32-bit wide stack slots or parameter
registers only, and you'd have to otherwise specify whether to sign extend or
zero extend to fill it up).

So I worry that the bitcode reader could become stricter and break on this test.

You could trunc i32 %a to i1 early in the function though.

Similar below.

[ascull, 2015/09/03 19:52:38]

Done.

+entry:
+  br label %loop0
+
+loop0:                               ; <-+
+  br label %loop1                    ;   |
+loop1:                               ;   |
+  br i1 %a, label %loop0, label %out ; --+
+
+out:
+  ret void
+}
+

[jvoung (off chromium), 2015/09/01 18:56:18]

Can you still CHECK-LABEL: test_single_loop

to help FileCheck partition the log?

[ascull, 2015/09/03 19:52:38]

Done.

+; CHECK: After loop nest depth analysis
+; CHECK-NEXT: LoopNestDepth = 0
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 0
+

[jvoung (off chromium), 2015/09/01 18:56:18]

Could add a "negative" test -- some non-loopy code with branches (like a
diamond).

Also, what about something irreducible like example d in:
https://en.wikipedia.org/wiki/Control_flow_graph#Definition

or something with multiple exits like c?

[ascull, 2015/09/03 19:52:38]

Done.

+define void @test_single_loop_with_continue(i1 %a, i1 %b) {
+entry:
+  br label %loop0
+
+loop0:                                 ; <-+
+  br label %loop1                      ;   |
+loop1:                                 ;   |
+  br i1 %a, label %loop0, label %loop2 ; --+
+loop2:                                 ;   |
+  br i1 %b, label %loop0, label %out   ; --+
+
+out:
+  ret void
+}
+
+; CHECK: After loop nest depth analysis
+; CHECK-NEXT: LoopNestDepth = 0
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 0
+
+define void @test_two_nested_loops(i1 %a, i1 %b) {
+entry:
+  br label %loop0_0
+
+loop0_0:                                   ; <---+
+  br label %loop1_0                        ;     |
+loop1_0:                                   ; <-+ |
+  br label %loop1_1                        ;   | |
+loop1_1:                                   ;   | |
+  br i1 %a, label %loop1_0, label %loop0_1 ; --+ |
+loop0_1:                                   ;     |
+  br i1 %b, label %loop0_0, label %out     ; ----+
+
+out:
+  ret void
+}
+
+; CHECK: After loop nest depth analysis
+; CHECK-NEXT: LoopNestDepth = 0
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 0
+
+define void @test_two_nested_loops_with_continue(i1 %a, i1 %b, i1 %c) {
+entry:
+  br label %loop0_0
+
+loop0_0:                                   ; <---+
+  br label %loop1_0                        ;     |
+loop1_0:                                   ; <-+ |
+  br label %loop1_1                        ;   | |
+loop1_1:                                   ;   | |
+  br i1 %a, label %loop1_0, label %loop1_2 ; --+ |
+loop1_2:                                   ;   | |
+  br i1 %a, label %loop1_0, label %loop0_1 ; --+ |
+loop0_1:                                   ;     |
+  br i1 %b, label %loop0_0, label %out     ; ----+
+
+out:
+  ret void
+}
+
+; CHECK: After loop nest depth analysis
+; CHECK-NEXT: LoopNestDepth = 0
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 0
+
+define void @test_multiple_nested_loops(i1 %a, i1 %b) {
+entry:
+  br label %loop0_0
+
+loop0_0:                                   ; <---+
+  br label %loop1_0                        ;     |
+loop1_0:                                   ; <-+ |
+  br label %loop1_1                        ;   | |
+loop1_1:                                   ;   | |
+  br i1 %a, label %loop1_0, label %loop0_1 ; --+ |
+loop0_1:                                   ;     |
+  br label %loop2_0                        ;     |
+loop2_0:                                   ; <-+ |
+  br label %loop2_1                        ;   | |
+loop2_1:                                   ;   | |
+  br i1 %a, label %loop2_0, label %loop0_2 ; --+ |
+loop0_2:                                   ;     |
+  br i1 %b, label %loop0_0, label %out     ; ----+
+
+out:
+  ret void
+}
+
+; CHECK: After loop nest depth analysis
+; CHECK-NEXT: LoopNestDepth = 0
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 0
+
+define void @test_three_nested_loops(i1 %a, i1 %b, i1 %c) {
+entry:
+  br label %loop0_0
+
+loop0_0:                                   ; <-----+
+  br label %loop1_0                        ;       |
+loop1_0:                                   ; <---+ |
+  br label %loop2_0                        ;     | |
+loop2_0:                                   ; <-+ | |
+  br label %loop2_1                        ;   | | |
+loop2_1:                                   ;   | | |
+  br i1 %a, label %loop2_0, label %loop1_1 ; --+ | |
+loop1_1:                                   ;     | |
+  br i1 %b, label %loop1_0, label %loop0_1 ; ----+ |
+loop0_1:                                   ;       |
+  br i1 %c, label %loop0_0, label %out     ; ------+
+
+out:
+  ret void
+}
+
+; CHECK: After loop nest depth analysis
+; CHECK-NEXT: LoopNestDepth = 0
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 3
+; CHECK-NEXT: LoopNestDepth = 3
+; CHECK-NEXT: LoopNestDepth = 2
+; CHECK-NEXT: LoopNestDepth = 1
+; CHECK-NEXT: LoopNestDepth = 0