[llvm-dev] Dataflow analysis regression in 3.7

[Davide Italiano via llvm-dev]

>
> I'm sure that adjusting that threshold has many implications, so I don't
> want to touch that.
>

We shouldn't, unless there's a very good reason for.
Funny enough, this was fixed just yesterday by Chad's commit
https://reviews.llvm.org/D34901 so the function now just gets folded
to `ret i32 1` (as you expected).

>>
>> (e.g. a more powerful range solver could realize that a is always in
>> the range [5;12]).
>

As I pointed out, this could've been caught by a more powerful range
analysis (before SimplifyCFG "destroys" the CFG). There's a balance to
keep between how aggressive SimplifyCFG gets VS what other passes
should/could do.

Without the last commit you have, after SimplifyCFG:

define i32 @dataflow(i32 %b) local_unnamed_addr #0 {
entry:
  %cmp = icmp eq i32 %b, 4
  %mul = mul nsw i32 %b, 3
  %phitmp = icmp eq i32 %mul, 4
  %a.0 = select i1 %cmp, i1 %phitmp, i1 false
  %. = select i1 %a.0, i32 0, i32 1
  ret i32 %.
}

but just before:

define i32 @dataflow(i32 %b) local_unnamed_addr #0 {
entry:
  %cmp = icmp eq i32 %b, 4
  br i1 %cmp, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  %vSSA_sigma = phi i32 [ %b, %entry ]
  %mul = mul nsw i32 3, %vSSA_sigma
  br label %if.end

if.else:                                          ; preds = %entry
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then
  %a.0 = phi i32 [ %mul, %if.then ], [ 5, %if.else ]
  %cmp1 = icmp eq i32 %a.0, 4
  br i1 %cmp1, label %if.then2, label %if.else3

if.then2:                                         ; preds = %if.end
  br label %cleanup

if.else3:                                         ; preds = %if.end
  br label %cleanup

cleanup:                                          ; preds = %if.else3, %if.then2
  %retval.0 = phi i32 [ 0, %if.then2 ], [ 1, %if.else3 ]
  ret i32 %retval.0
}

On the latter, you can find (after transforming to e-SSA) that:

Analysis for function: dataflow
[4, 4]  %vSSA_sigma = phi i32 [ %b, %entry ]
[12, 12]  %mul = mul nsw i32 3, %vSSA_sigma
[5, 12]  %a.0 = phi i32 [ %mul, %if.then ], [ 5, %if.else ]
[0, 1]  %retval.0 = phi i32 [ 0, %if.then2 ], [ 1, %if.else3 ]

Note that our VRP algorithm (correlated-propagation) currently doesn't
catch that, but a more powerful analysis does (and it's faster on
large testcases & has an interprocedural version, the code is on
github).
http://homepages.dcc.ufmg.br/~raphael/papers/CGO13.pdf [and the predecessor
paper from Zhendong Su, circa 2004 IIRC, I don't have a link handy sorry :)]

[I just put a 10 lines intraprocedural/interprocedural client on top
of it that prints the found ranges
https://github.com/dcci/range-analysis/commit/f9677dfd032f811ed545977690f8d7aead7cccaa]

Thanks,

--
Davide