[llvm-bugs] [Bug 25507] New: [Polly] Unnecessarily complicated schedule

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=25507

            Bug ID: 25507
           Summary: [Polly] Unnecessarily complicated schedule
           Product: Projects
           Version: unspecified
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Polly
          Assignee: polly-dev at googlegroups.com
          Reporter: llvm at meinersbur.de
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

Created attachment 15279
  --> https://llvm.org/bugs/attachment.cgi?id=15279&action=edit
Extract from MultiSource/Benchmark/Ptrdist/bc/number.c

$ clang loopschedule.c -c -O3 -mllvm -polly -mllvm -debug -mllvm
-debug-only=polly-ast -mllvm -polly-process-unprofitable

emits the following schedule for the loop "while.body => while.end"

      for (int c0 = 0; c0 < min(n2, n1); c0 += 1)
        Stmt_while_body(c0);
      if (n1 <= 0) {
        Stmt_while_body(0);
      } else if (n2 <= 0)
        Stmt_while_body(0);

    Context:
    [n2, n1] -> {  : n2 >= -2147483648 and n2 <= 2147483647 and n1 >=
-2147483648 and n1 <= 2147483647 }
    Assumed Context:
    [n2, n1] -> {  :  }
    Boundary Context:
    [n2, n1] -> {  :  }
    Statements
        Stmt_while_body
            Domain :=
                [n2, n1] -> { Stmt_while_body[i0] : i0 >= 0 and i0 <= -1 + n1
and i0 <= -1 + n2; Stmt_while_body[0] : n1 <= 0 or (n2 <= 0 and n1 >= 1) };



The initial loop condition is hoisted outside of the scop, i.e

if ((n1 > 0) && (n2 > 0)) {
  // Scop
}


1) The generated schedule has two conditions (n1 <= 0) and (n2 <= 0) that are
never evaluated code, i.e. 2/3 of the generated code is effectively dead.


2) After passing the hoisted initial condition, the BasicBlock while.body must
be executed at least once before the condition is checked again. Still, CodeGen
inserts a second initial check into "polly.loop_if". It results into an
additional branch that is not optimized away by later LLVM passes and
potentially "undef" to appear after -mem2reg.


We might analyze the hoisted condition to translate into additional assumptions
(Here: n1 > 0 && n2 > 0). Unfortunately, there is no LLVM analysis to tell the
the possible range of a value.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20151112/2887d660/attachment.html>