hexagon compiler runs "forever" on matrix-spec-types at O2

[androm3da]

As of 20.1.4 clang would build this test case within ~20 minutes or so on my Xeon Gold 6136 CPU.

Now, it seems to run for hours - I've let it go for 7 hours and it has not finished. I have seen similar behavior with llc -O2 matrix-types-spec.ll.

matrix-types-spec.ll.txt

[llvmbot]

@llvm/issue-subscribers-backend-hexagon

Author: Brian Cain (androm3da)

As of [20.1.4](https://github.com/quic/toolchain_for_hexagon/releases/tag/v20.1.4) clang would build this test case within ~20 minutes or so on my Xeon Gold 6136 CPU.

Now, it seems to run for hours - I've let it go for 7 hours and it has not finished. I have seen similar behavior with llc -O2 matrix-types-spec.ll.

matrix-types-spec.ll.txt

[aankit-ca]

I've narrowed down the issue to the MachinePipeliner pass which took about 9 hours to run on a reduced version of the original example.

===-------------------------------------------------------------------------===
                          Pass execution timing report
===-------------------------------------------------------------------------===
  Total Execution Time: 32789.9193 seconds (32797.0895 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  32713.6319 ( 99.8%)   4.7475 ( 99.5%)  32718.3794 ( 99.8%)  32725.4233 ( 99.8%)  Modulo Software Pipelining
  58.6751 (  0.2%)   0.0139 (  0.3%)  58.6890 (  0.2%)  58.7968 (  0.2%)  Hexagon DAG->DAG Pattern Instruction Selection
   7.9919 (  0.0%)   0.0000 (  0.0%)   7.9919 (  0.0%)   7.9921 (  0.0%)  Machine Instruction Scheduler
   1.5369 (  0.0%)   0.0000 (  0.0%)   1.5369 (  0.0%)   1.5369 (  0.0%)  Post RA top-down list latency scheduler
   0.7863 (  0.0%)   0.0000 (  0.0%)   0.7863 (  0.0%)   0.7864 (  0.0%)  Hexagon Packetizer
   0.6647 (  0.0%)   0.0000 (  0.0%)   0.6647 (  0.0%)   0.6647 (  0.0%)  Prologue/Epilogue Insertion & Frame Finalization

The addDependenciesBetweenSUs functions seems to be the culprit here:

llvm-project/llvm/lib/CodeGen/MachinePipeliner.cpp

Line 1089 in d30fd56

void LoopCarriedOrderDepsTracker::addLoopCarriedDepenenciesForChunks(

@kasuga-fj Can you please look into this issue?

I've captured the IR before the machine pipeliner pass that you can use to work on this:

before_pipeliner_21.0.mir.txt

To run:

llc -O2 before_pipeliner_21.0.mir -run-pass=pipeliner  -o after-pipeliner.mir

[kasuga-fj]

Okay, I'll take a look next week.

Here's my early comment (I haven't run the test yet):
At a glance, I don't think the root cause of the original issue is LoopCarriedOrderDepsTracker::addLoopCarriedDepenenciesForChunks, because it's not merged into LLVM 20.1.4. Without any investigation, I suspect that SMSchedule::orderDependence may have triggered the issue, as I encountered a similar problem when running some random tests locally. The function is a recursive one, and it looks to me that the function potentially lead infinite recursion. IIRC, I let it run for several days back then, but it never completed.

On the other hand, I agree with that addLoopCarriedDepenenciesForChunks can be time-consuming, and I'm open to mitigating it if it becomes a problem.

@aankit-ca Could you check which function is actually causing the issue? Or do you have any data indicating that addLoopCarriedDepenenciesForChunks is the culprit?

[kasuga-fj]

Sorry, I misunderstood the issue's description... Yes, I now agree with addLoopCarriedDepenenciesForChunks would be the culprit.

[aankit-ca]

Yeah, in this particular case, it took about 9 hours to run