Use trivial data-dependencies to ignore non-rt functions with trivial conditionals about stoat HOT 3 OPEN

One of the issues with stoat (documented at LAC) is that it does not use any data dependent information to determine if a function will be called.

For example if you have the function:

void a(void) {
  if(0)
    b();
}

Then stoat will (to the best of my knowledge) report that a can possibly call b as clang is called with -O0.

The above case is fairly easy to handle with a few of LLVM's optimization passes, though optimization operations make it a fair bit harder to reason about the original code. The case that you're interested in is a harder one however as you want to be able to propagate a constant through a function call. As to why this is difficult let's look at the minimum test example:

void a(void) { }

void b(int c)
{
    if(c)
        a();
}

void d(void) { b(1); }

void e(void) { b(0); }

Translated to LLVM IR this looks like:

; ModuleID = '<stdin>'
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: nounwind uwtable
define void @a() #0 {
  ret void
}

; Function Attrs: nounwind uwtable
define void @b(i32 %c) #0 {
  %1 = alloca i32, align 4
  store i32 %c, i32* %1, align 4
  %2 = load i32, i32* %1, align 4
  %3 = icmp ne i32 %2, 0
  br i1 %3, label %4, label %5

; <label>:4                                       ; preds = %0
  call void @a()
  br label %5

; <label>:5                                       ; preds = %4, %0
  ret void
}

; Function Attrs: nounwind uwtable
define void @d() #0 {
  call void @b(i32 1)
  ret void
}

; Function Attrs: nounwind uwtable
define void @e() #0 {
  call void @b(i32 0)
  ret void
}

attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"clang version 3.8.0-2ubuntu4 (tags/RELEASE_380/final)"}

To use the data dependency within function b(), we must look at the branch above <label>:4 . From there we need to establish if %3 is true/false. Next we need to invert the logic about %2 to say that 0== no branch, then a few more steps have to trace the value back to being an argument.

Expanding this to across functions, then there needs to be a new node in the stoat graph which is a specialization of b() whenever there's a 0 argument. With that established then there likely needs to be another pass over all calls of b() to determine if they're b(special-case) or b(unknown-case). Then it's possible to say that e calls b_specialization0 rather than just b().

So the feature request is certainly doable, but a non-trivial bit of work. My current suggestion is to have separate functions for realtime and non-realtime operations, though I realize that this may not always be a possibility. In those cases a suppression would be useful.

from stoat.

hmm I see.
would it be possible to add a decorator/attribute for functions that can be called like this?
that would mean only selected functions will need to go through the special argument verification

from stoat.

An attribute doesn't save that much time/effort IMO. Most of the work is in the complexity of implementing the feature, not the time spent executing the feature after it's implemented.

from stoat.