[LLVMbugs] [Bug 11991] New: BB vectorizer search for pair vector instructions is O(n^2) and can be improved to be O(n)

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=11991

             Bug #: 11991
           Summary: BB vectorizer search for pair vector instructions is
                    O(n^2) and can be improved to be O(n)
           Product: new-bugs
           Version: unspecified
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: spop at codeaurora.org
                CC: hfinkel at anl.gov, llvmbugs at cs.uiuc.edu
    Classification: Unclassified


Currently the BB vectorizer has a complexity of O(n^2) in the number
of instructions in a basic block.  This is due to the search algorithm
for vectorizable instructions pairs:

for i in BBinstructions
  for j in BBinstructions
    if (isVectPairable(i, j))
      push pair(i, j)

This can be improved in an algorithm that is O(n*t) in number of
instructions times the number of vectorizable types, and because the
number of types that can be vectorized are finite, the algorithm is
actually O(n):

for i in BBinstructions
  if (isVectorizableType1(i))
    push i into Type1Instructions
  else if (isVectorizableType2(i))
    push i into Type2Instructions
  etc.

In the end we get all vectorizable pairs by their types in these vectors.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.