Loop inversion

Inom datavetenskap är loopinversion en kompilatoroptimering och looptransformation där en while-loop ersätts av ett if-block som innehåller en do..while-loop . När det används på rätt sätt kan det förbättra prestandan på grund av instruktionspipelining .

Exempel i C

    
    0
      
      0
    
   int  i  ,  a  [  100  ];  i  =  ;  while  (  i  <  100  )  {  a  [  i  ]  =  ;  i  ++  ;  } 

är ekvivalent med:

    
    0
      
     
        0
      
        
   int  i  ,  a  [  100  ];  i  =  ;  if  (  i  <  100  )  {  do  {  a  [  i  ]  =  ;  i  ++  ;  }  while  (  i  <  100  );  } 

Trots den till synes större komplexiteten i det andra exemplet kan det faktiskt köras snabbare på moderna processorer eftersom de använder en instruktionspipeline . Av naturen orsakar varje hopp i koden ett pipelinestopp , vilket är en nackdel för prestandan.

Dessutom tillåter loopinversion säker loop-invariant kodrörelse .

Exempel i treadresskod

i := 0 L1: om i >= 100 goto L2 a[i] := 0 i := i + 1 goto L1 L2:

Om jag hade initialiserats vid 100, skulle instruktionerna som kördes vid körning ha varit:

 om i >= 100  goto L2 

Låt oss anta att jag hade initialiserats till något värde som är mindre än 100. Låt oss nu titta på instruktionerna som körs i ögonblicket efter att i har ökats till 99 i slingan:

 goto L1  if i < 100  a[i] := 0  i := i + 1  goto L1  if i >= 100  goto L2  <<vid L2>> 

Låt oss nu titta på den optimerade versionen:

i := 0 om i >= 100 goto L2 L1: a[i] := 0 i := i + 1 om i < 100 goto L1 L2:

Återigen, låt oss titta på instruktionerna som körs om i initieras till 100:

 om i >= 100  goto L2 

Vi slösade inte bort några cykler jämfört med originalversionen. Tänk nu på fallet där jag har ökats till 99:

 om i < 100  goto L1  a[i] := 0  i := i + 1  om i < 100  <<vid L2>> 

Som du kan se har två goto s (och därmed två pipeline stalls) eliminerats i utförandet.