Skip to content
  • Dan Gohman's avatar
    Optimize SelectionDAG's AssignTopologicalOrder even further. · 86aa16a6
    Dan Gohman authored
    Completely eliminate the TopOrder std::vector. Instead, sort
    the AllNodes list in place. This also eliminates the need to
    call AllNodes.size(), a linear-time operation, before
    performing the sort.
    
    Also, eliminate the Sources temporary std::vector, since it
    essentially duplicates the sorted result as it is being
    built.
    
    This also changes the direction of the topological sort
    from bottom-up to top-down. The AllNodes list starts out in
    roughly top-down order, so this reduces the amount of
    reordering needed. Top-down is also more convenient for
    Legalize, and ISel needed only minor adjustments.
    
    llvm-svn: 56867
    86aa16a6
Loading