[llvm-bugs] [Bug 47867] New: Exponential time in Machine Instruction Scheduler with StackTagging and large allocas

[via llvm-bugs]

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

            Bug ID: 47867
           Summary: Exponential time in Machine Instruction Scheduler with
                    StackTagging and large allocas
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: eugeni.stepanov at gmail.com
                CC: llvm-bugs at lists.llvm.org

// compile with -target aarch64-linux-android30 -march=armv8+memtag -c
-fsanitize=memtag -O2

#include <string.h>

void g(void *);
void f() {
  char buf[N*1024];
  memset(buf, 42, sizeof(buf));
  g(buf);
}

N   time in MIS, s
1   0.0010
2   0.0028
3   0.0080
4   0.0180
8   0.1511
16   1.2634
24   4.3588
32  10.3364
40  20.2147
48  35.1360

All the time is spent in BaseMemOpClusterMutation::clusterNeighboringMemOps and
its callees:

  for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {
    // Decision to cluster mem ops is taken based on target dependent logic     
    auto MemOpa = MemOpRecords[Idx];

    // Seek for the next load/store to do the cluster.                          
    unsigned NextIdx = Idx + 1;
    for (; NextIdx < End; ++NextIdx)
      // Skip if MemOpb has been clustered already or has dependency with       
      // MemOpa.                                                                
      if (!SUnit2ClusterInfo.count(MemOpRecords[NextIdx].SU->NodeNum) &&
          !DAG->IsReachable(MemOpRecords[NextIdx].SU, MemOpa.SU) &&
          !DAG->IsReachable(MemOpa.SU, MemOpRecords[NextIdx].SU))
        break;
    if (NextIdx == End)
      continue;

It's not clear to me why the algorithm is exponential (or at least seems to
be), but it is triggered by AArch64StackTagging inserting an absurd amount of
STG instructions.

I'll work around in stack tagging by not applying the -stack-tagging-merge-init
optimization to large allocas.

-- 
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/20201015/a8336651/attachment.html>