Slingdelning

Loop splitting är en kompilatoroptimeringsteknik . Den försöker förenkla en loop eller eliminera beroenden genom att dela upp den i flera loopar som har samma kroppar men itererar över olika sammanhängande delar av indexintervallet.

Loop peeling

Loop peeling är ett specialfall av loop splitting som delar upp eventuella problematiska första (eller sista) få iterationer från loopen och utför dem utanför loopkroppen.

Anta att en loop skrevs så här:

    
   0  
 
       
     
  int  p  =  10  ;  för  (  int  i  =  ;  i  <  10  ;  ++  i  )  {  y  [  i  ]  =  x  [  i  ]  +  x  [  p  ];  p  =  i  ;  } 

Lägg märke till att p = 10 endast för den första iterationen, och för alla andra iterationer, p = i - 1 . En kompilator kan dra fördel av detta genom att avveckla (eller "skala") den första iterationen från slingan.

Efter att ha skalat den första iterationen skulle koden se ut så här:

 0  0  
     
 
       
  y  [  ]  =  x  [  ]  +  x  [  10  ];  för  (  int  i  =  1  ;  i  <  10  ;  ++  i  )  {  y  [  i  ]  =  x  [  i  ]  +  x  [  i  -1  ];  } 

Denna ekvivalenta form eliminerar behovet av variabeln p inuti slingkroppen.

Loop peeling introducerades i gcc i version 3.4. Mer generaliserad slinguppdelning lades till i GCC 7.

Kort historia av termen

Tydligen användes termen för första gången av Cannings, Thompson och Skolnick i deras uppsats från 1976 om beräkningsmodeller för (mänskligt) arv. Där användes termen för att beteckna en metod för att kollapsa fenotypisk information på föräldrar. Därifrån användes termen igen i deras tidningar, inklusive deras nyskapande artikel om sannolikhetsfunktioner på komplexa stamtavlor.

Inom kompilatorteknik dök termen först upp i slutet av 1980-talets tidningar om VLIW och superskalär kompilering, inklusive och.

Vidare läsning

•    Kennedy, Ken ; Allen, Randy (2002). "Kapitel 5.7. Indexuppdelning - Kapitel 5.7.2. Loop Peeling". Optimizing Compilers for Modern Architectures: A Dependence-Based Approach (2011 digitaltryck av 1:a upplagan). Academic Press / Morgan Kaufmann Publishers / Elsevier . s. 211 -212. ISBN 978-1-55860-286-1 . LCCN 2001092381 .