Skip to content
  • Kyle Butt's avatar
    Codegen: MachineBlockPlacement Improve probability layout. · 02d8d054
    Kyle Butt authored
    The following pattern was being layed out poorly:
    
                  A
                 / \
                B   C
               / \ / \
              D   E   ? (Doesn't matter)
    
    Where A->B is far more likely than A->C, and prob(B->D) = prob(B->E)
    
    The current algorithm gives:
    A,B,C,E (D goes on worklist)
    
    It does this even if C has a frequency count of 0. This patch
    adjusts the layout calculation so that if freq(B->E) >> freq(C->E)
    then we go ahead and layout E rather than C. Fallthrough half the time
    is better than fallthrough never, or fallthrough very rarely. The
    resulting layout is:
    
    A,B,E, (C and D are in a worklist)
    
    llvm-svn: 277187
    02d8d054
Loading