Styrka reduktion

I kompilatorkonstruktion är hållfasthetsreduktion en kompilatoroptimering där dyra operationer ersätts med likvärdiga men billigare operationer . Det klassiska exemplet på styrkeminskning omvandlar "starka" multiplikationer inuti en loop till "svagare" tillägg – något som ofta förekommer vid arrayadressering. ( Cooper, Simpson & Vick 1995 , s. 1)

Exempel på hållfasthetsminskning inkluderar:

  • ersätta en multiplikation inom en slinga med en addition
  • ersätta en exponentiering inom en loop med en multiplikation

Kodanalys

Det mesta av ett programs exekveringstid spenderas vanligtvis i en liten del av koden (kallad hot spot ), och den koden finns ofta i en loop som körs om och om igen.

En kompilator använder metoder för att identifiera loopar och känna igen egenskaperna hos registervärden inom dessa loopar. För styrkeminskning är kompilatorn intresserad av:

  • Loop-invarianter: de värden som inte ändras i en loops kropp.
  • Induktionsvariabler: de värden som itereras varje gång genom slingan.

Loop-invarianter är i huvudsak konstanter inom en loop, men deras värde kan ändras utanför loopen. Induktionsvariabler förändras med kända mängder. Termerna är relativa till en viss slinga. När slingor är kapslade kan en induktionsvariabel i den yttre slingan vara en slinginvariant i den inre slingan.

Styrkreduktion letar efter uttryck som involverar en loopinvariant och en induktionsvariabel. Vissa av dessa uttryck kan förenklas. Till exempel multiplikationen av loopinvariant c och induktionsvariabel i 

  
   0    

        
 c  =  7  ;  för  (  i  =  ;  i  <  N  ;  i  ++  )  {  y  [  i  ]  =  c  *  i  ;  }

kan ersättas med successiva svagare tillägg

  
  0
   0    

      
        
 c  =  7  ;  k  =  ;  för  (  i  =  ;  i  <  N  ;  i  ++  )  {  y  [  i  ]  =  k  ;  k  =  k  +  c  ;  }

Exempel på styrkeminskning

Nedan är ett exempel som kommer att styrka-reducera alla slingmultiplikationer som uppstod från arrayindexeringsadressberäkningar.

Föreställ dig en enkel loop som sätter en array till identitetsmatrisen . 

   0    

       0    
    
          
    
      
 för  (  i  =  ;  i  <  n  ;  i  ++  )  {  för  (  j  =  ;  j  <  n  ;  j  ++  )  {  A  [  i  ,  j  ]  =  0,0  ;  }  A  [  i  ,  i  ]  =  1,0  ;  }

Mellankod

Kompilatorn kommer att se denna kod som

  
  
        
  
                             
        
       

      
      
               
  
                             
             
            

           
             
                             
                
               
             
             

               
            
      
  
      
                            
          
          
          
        
        

      
          
       
  
   0010  ; för (i = 0, i < n; i++)   0020  ; {   0030  r1  =  #0; i = 0   0040  G0000:  0050  last  r2  ,  n  ; i < n   0060  cmp  r1  ,  r2  0070  bge  G0001  0080  0090  ; för (j = 0; j < n; j++)   0100  ; {   0110  r3  =  #0; j = 0   0120  G0002:  0130  last  r4  ,  n  ; j < n   0140  cmp  r3  ,  r4  0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0180  belastning  r7  ,  n  0190  r8  =  r1  *  r7  ; beräkna nedsänkt i * n + j   0200  r9  =  r8  +  r3  0210  r10  =  r9  *  #8 ; beräkna byte adress   0220  fr3  =  #0.0  0230  fstore  fr3  ,  A  [  r10  ]  0240  0250  r3  =  r3  +  # 1 ; j++   0260  br  G0002  0270  ; }   0280  G0003:  0290  ; A[i,i] = 1,0;   0300  last  r12  ,  n  ; beräkna nedsänkt i * n + i   0310  r13  =  r1  *  r12  0320  r14  =  r13  +  r1  0330  r15  =  r14  *  #8 ; beräkna byte adress   0340  fr4  =  #1.0  0350  fstore  fr4  ,  A  [  r15  ]  0360  0370  ; i++   0380  r1  =  r1  +  #1  0390  br  G0000  0400  ; }   0410  G0001:

Detta uttrycker 2-dimensionell array A som en 1-dimensionell array av n*n storlek, så att när högnivåkoden uttrycker A[x, y] internt kommer den att vara A[(x*n)+y] för alla givet giltiga index x och y.

Många optimeringar

Kompilatorn kommer att börja göra många optimeringar – inte bara styrkeminskning. Uttryck som är konstanta (invarianta) inom en slinga kommer att hissas ut ur slingan. Konstanter kan laddas utanför båda slingorna—såsom flyttalsregister fr3 och fr4. Erkännande av att vissa variabler inte ändras gör att register kan slås samman; n är konstant, så r2, r4, r7, r12 kan hissas och kollapsas. Det gemensamma värdet i*n beräknas i (den hissade) r8 och r13, så de kollapsar. Den innersta slingan (0120-0260) har reducerats från 11 till 7 mellaninstruktioner. Den enda multipliceringen som återstår i den innersta slingan är linjen 0210:s multiplikation med 8. 

  
    
        
        
 
 
 
        
        
  
                             
       

                             
 
      
        
               
  
                             
            

           
                             
               
             

               
            
        
  
      
                            
          
        

      
          
       
    
   0010  ; för (i = 0, i < n; i++)   0020  {  0030  r1  =  #0; i = 0   0050  last  r2  ,  n  0130  ; last r4, n dödad;  använd r2   0180  ; last r7, n dödad;  använd r2   0300  ; last r12, n dödad;  använd r2   0220  fr3  =  #0.0  0340  fr4  =  #1.0  0040  G0000:  0060  cmp  r1  ,  r2  ; i < n   0070  bge  G0001  0080  0190  r8  =  r1  *  r2  ; beräkna subskript i * n   0310  ; r13 = r1 * r2 dödad;  använd r8 ;  beräkna subskript i * n   0090  ; för (j = 0; j < n; j++)   0100  {  0110  r3  =  #0; j = 0   0120  G0002:  0140  cmp  r3  ,  r2  ; j < n   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0200  r9  =  r8  +  r3  ; beräkna nedsänkt i * n + j   0210  r10  =  r9  *  #8 ; beräkna byte adress   0230  fstore  fr3  ,  A  [  r10  ]  0240  0250  r3  =  r3  +  #1; j++   0260  br  G0002  0270  }  0280  G0003:  0290  ; A[i,i] = 1,0;   0320  r14  =  r8  +  rl  ; beräkna nedsänkt i * n + i   0330  r15  =  r14  *  #8 ; beräkna byte adress   0350  fstore  fr4  ,  A  [  r15  ]  0360  0370  ;i++  0380  r1  =  r1  +  #1  0390  br  G0000  0400  }  0410  G0001:

Det finns fler optimeringar att göra. Register r3 är huvudvariabeln i den innersta slingan (0140-0260); den ökas med 1 varje gång genom slingan. Register r8 (som är invariant i den innersta slingan) läggs till r3. Istället för att använda r3 kan kompilatorn eliminera r3 och använda r9. Slingan, istället för att styras av r3 = 0 till n-1, kan styras av r9=r8+0 till r8+n-1. Det lägger till fyra instruktioner och dödar fyra instruktioner, men det finns en instruktion färre i slingan.

  
                                
                            
  
  
                            
            

           
  
               
             

  
               
             0110  ; r3 = #0 dödad;  j = 0   0115  r9  =  r8  ; ny uppgift   0117  r20  =  r8  +  r2  ; ny gräns   0120  G0002:  0140  ; cmp r3, r2 dödade ;  j < n   0145  cmp  r9  ,  r20  ; r8 + j < r8 + n = r20   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0200  ; r9 = r8 + r3 dödade;  beräkna nedsänkt i * n + j   0210  r10  =  r9  *  #8 ; beräkna byte adress   0230  fstore  fr3  ,  A  [  r10  ]  0240  0250  ; r3 = r3 + #1 dödad;  j++   0255  r9  =  r9  +  #1; ny loop variabel   0260  br  G0002

Nu är r9 slingvariabeln, men den samverkar med multiplicera med 8. Här får vi göra lite styrka reduktion. Multipliceringen med 8 kan reduceras till några successiva tillägg av 8. Nu finns det inga multiplikationer inuti slingan.

                                
                            
                
  
                            
            

           
  
             

               
               
             0115  r9  =  r8  ; ny uppgift   0117  r20  =  r8  +  r2  ; ny gräns   0118  r10  =  r8  *  #8 ; initialt värde på r10   0120  G0002:  0145  cmp  r9  ,  r20  ; r8 + j < r8 + n = r20   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0210  ; r10 = r9 * #8 dödad;  beräkna byte-adress   0230  fstore  fr3  ,  A  [  r10  ]  0240  0245  r10  =  r10  +  #8; styrka reducerad multiplicera   0255  r9  =  r9  +  #1 ; loop variabel   0260  br  G0002

Register r9 och r10 (= 8*r9) behövs inte båda; r9 kan elimineras i slingan. Slingan är nu 5 instruktioner.

  
                            
                
                
  
  
                           
            

           
             

               
  
             0115  ; r9 = r8 dödade   0117  r20  =  r8  +  r2  ; gräns   0118  r10  =  r8  *  #8 ; initialt värde på r10   0119  r22  =  r20  *  #8 ; ny gräns   0120  G0002:  0145  ; cmp r9, r20 dödade ;  r8 + j < r8 + n = r20   0147  cmp  r10  ,  r22  ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0230  fstore  fr3  ,  A  [  r10  ]  0240  0245  r10  =  r10  +  #8 ; styrka reducerad multiplicera   0255  ; r9 = r9 + #1 dödad;  loop variabel   0260  br  G0002

Yttre slinga

Tillbaka till hela bilden:

  
    
        
        
        
        
  
                             
       

                             
                            
           
           
      
        
  
                           
            

           
             

               
            
        
  
      
                            
          
        

      
          
       
    
   0010  ; för (i = 0, i < n; i++)   0020  {  0030  r1  =  #0; i = 0   0050  belastning  r2  ,  n  0220  fr3  =  #0.0  0340  fr4  =  #1.0  0040  G0000:  0060  cmp  r1  ,  r2  ; i < n   0070  bge  G0001  0080  0190  r8  =  r1  *  r2  ; beräkna subscript i * n   0117  r20  =  r8  +  r2  ; gräns   0118  r10  =  r8  *  #8 ; initialt värde på r10   0119  r22  =  r20  *  #8 ; ny gräns   0090  ; för (j = 0; j < n; j++)   0100  {  0120  G0002:  0147  cmp  r10  ,  r22  ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0230  fstore  fr3  ,  A  [  r10  ]  0240  0245  r10  =  r10  +  #8 ; styrka reducerad multiplicera   0260  br  G0002  0270  }  0280  G0003:  0290  ; A[i,i] = 1,0;   0320  r14  =  r8  +  rl  ; beräkna nedsänkt i * n + i   0330  r15  =  r14  *  #8 ; beräkna byte adress   0350  fstore  fr4  ,  A  [  r15  ]  0360  0370  ;i++  0380  r1  =  r1  +  #1  0390  br  G0000  0400  }  0410  G0001:

Det finns nu fyra multiplikationer inom den yttre slingan som ökar r1. Register r8 = r1*r2 vid 0190 kan styrkas reduceras genom att ställa in det innan det går in i slingan (0055) och öka det med r2 i botten av slingan (0385).

Värdet r8*8 (vid 0118) kan styrkas reduceras genom att initiera det (0056) och lägga till 8*r2 till det när r8 blir inkrementerat (0386).

Register r20 inkrementeras med invarianten/konstanten r2 varje gång genom slingan vid 0117. Efter att ha inkrementerats multipliceras det med 8 för att skapa r22 vid 0119. Den multiplikationen kan styrkas reduceras genom att lägga till 8*r2 varje gång genom slingan .

  
    
        
        
        
        
                             
          
          
                            
          
  
                             
       

  
  
                              
  
      
        
  
                           
            

           
             

               
            
        
  
      
                            
          
        

      
           
                             
                          
                          
       
    
   0010  ; för (i = 0, i < n; i++)   0020  {  0030  r1  =  #0; i = 0   0050  belastning  r2  ,  n  0220  fr3  =  #0,0  0340  fr4  =  #1,0  0055  r8  =  r1  *  r2  ; ställ in initialt värde för r8   0056  r40  =  r8  *  #8 ; initialvärde för r8 * 8   0057  r30  =  r2  *  #8 ; ökning för r40   0058  r20  =  r8  +  r2  ; kopierad från 0117   0058  r22  =  r20  *  #8 ; initialt värde på r22   0040  G0000:  0060  cmp  r1  ,  r2  ; i < n   0070  bge  G0001  0080  0190  ; r8 = r1 * r2 dödad;  beräkna subskript i * n   0117  ; r20 = r8 + r2 dödad - död kod   0118  r10  =  r40  ; styrka reducerat uttryck till r40   0119  ; r22 = r20 * #8 dödad ;  styrka reducerad   0090  ; för (j = 0; j < n; j++)   0100  {  0120  G0002:  0147  cmp  r10  ,  r22  ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0230  fstore  fr3  ,  A  [  r10  ]  0240  0245  r10  =  r10  +  #8 ; styrka reducerad multiplicera   0260  br  G0002  0270  }  0280  G0003:  0290  ; A[i,i] = 1,0;   0320  r14  =  r8  +  rl  ; beräkna nedsänkt i * n + i   0330  r15  =  r14  *  #8 ; beräkna byte adress   0350  fstore  fr4  ,  A  [  r15  ]  0360  0370  ;i++  0380  r1  =  r1  +  #1  0385  r8  =  r8  +  r2  ; styrka reducera r8 = r1 * r2   0386  r40  =  r40  +  r30  ; styrka reducera uttryck r8 * 8   0388  r22  =  r22  +  r30  ; styrka reducera r22 = r20 * 8   0390  br  G0000  0400  }  0410  G0001:

Den sista multiplicera

Det lämnar de två slingorna med endast en multiplikationsoperation (vid 0330) inom den yttre slingan och inga multiplikationer inom den inre slingan.

  
    
        
        
        
        
                             
          
          
                            
          
  
                             
       

                              
      
        
  
                           
            

           
             

               
            
        
  
      
                            
          
        

      
           
                             
                          
                          
       
    
   0010  ; för (i = 0, i < n; i++)   0020  {  0030  r1  =  #0; i = 0   0050  belastning  r2  ,  n  0220  fr3  =  #0,0  0340  fr4  =  #1,0  0055  r8  =  r1  *  r2  ; ställ in initialt värde för r8   0056  r40  =  r8  *  #8 ; initialvärde för r8 * 8   0057  r30  =  r2  *  #8 ; ökning för r40   0058  r20  =  r8  +  r2  ; kopierad från 0117   0058  r22  =  r20  *  #8 ; initialt värde på r22   0040  G0000:  0060  cmp  r1  ,  r2  ; i < n   0070  bge  G0001  0080  0118  r10  =  r40  ; styrka reducerat uttryck till r40   0090  ; för (j = 0; j < n; j++)   0100  {  0120  G0002:  0147  cmp  r10  ,  r22  ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0230  fstore  fr3  ,  A  [  r10  ]  0240  0245  r10  =  r10  +  #8 ; styrka reducerad multiplicera   0260  br  G0002  0270  }  0280  G0003:  0290  ; A[i,i] = 1,0;   0320  r14  =  r8  +  rl  ; beräkna nedsänkt i * n + i   0330  r15  =  r14  *  #8 ; beräkna byte adress   0350  fstore  fr4  ,  A  [  r15  ]  0360  0370  ;i++  0380  r1  =  r1  +  #1  0385  r8  =  r8  +  r2  ; styrka reducera r8 = r1 * r2   0386  r40  =  r40  +  r30  ; styrka reducera uttryck r8 * 8   0388  r22  =  r22  +  r30  ; styrka reducera r22 = r20 * 8   0390  br  G0000  0400  }  0410  G0001:

Vid linje 0320 är r14 summan av r8 och rl, och r8 och rl inkrementeras i slingan. Register r8 stöts av r2 (=n) och r1 stöts med 1. Följaktligen stöts r14 med n+1 varje gång genom slingan. Den sista slingmultipliceringen vid 0330 kan styrkas reduceras genom att lägga till (r2+1)*8 varje gång genom slingan.

  
    
        
        
        
        
                             
          
          
                            
          
                            
          
          
          
  
                             
       

                              
      
        
  
                           
            

           
             

               
            
        
  
      
  
  
        

      
           
                             
                          
                          
                          
       
    
   0010  ; för (i = 0, i < n; i++)   0020  {  0030  r1  =  #0; i = 0   0050  belastning  r2  ,  n  0220  fr3  =  #0,0  0340  fr4  =  #1,0  0055  r8  =  r1  *  r2  ; ställ in initialt värde för r8   0056  r40  =  r8  *  #8 ; initialvärde för r8 * 8   0057  r30  =  r2  *  #8 ; ökning för r40   0058  r20  =  r8  +  r2  ; kopierad från 0117   0058  r22  =  r20  *  #8 ; initialt värde på r22   005  A  r14  =  r8  +  r1  ; kopierad från 0320   005  B  r15  =  r14  *  #8 ; initialt värde på r15 (0330)   005  C  r49  =  r2  +  #1  005  D  r50  =  r49  *  #8 ; styrka reducerad ökning   0040  G0000:  0060  cmp  r1  ,  r2  ; i < n   0070  bge  G0001  0080  0118  r10  =  r40  ; styrka reducerat uttryck till r40   0090  ; för (j = 0; j < n; j++)   0100  {  0120  G0002:  0147  cmp  r10  ,  r22  ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0230  fstore  fr3  ,  A  [  r10  ]  0240  0245  r10  =  r10  +  #8 ; styrka reducerad multiplicera   0260  br  G0002  0270  }  0280  G0003:  0290  ; A[i,i] = 1,0;   0320  ; r14 = r8 + r1 dödad;  död kod   0330  ; r15 = r14 * #8 dödad;  styrka reducerad   0350  fstore  fr4  ,  A  [  r15  ]  0360  0370  ;i++  0380  r1  =  r1  +  #1  0385  r8  =  r8  +  r2  ; styrka reducera r8 = r1 * r2   0386  r40  =  r40  +  r30  ; styrka reducera uttryck r8 * 8   0388  r22  =  r22  +  r30  ; styrka reducera r22 = r20 * 8   0389  r15  =  r15  +  r50  ; styrka reducera r15 = r14 * 8   0390  br  G0000  0400  }  0410  G0001:

Det finns ännu mer att gå. Konstant vikning kommer att känna igen att r1=0 i ingressen, så flera instruktioner kommer att rensa upp. Register r8 används inte i slingan, så det kan försvinna.

Dessutom används r1 bara för att styra slingan, så r1 kan ersättas med en annan induktionsvariabel som r40. Där jag gick 0 <= i < n, går register r40 0 <= r40 < 8 * n * n.

  
    
  
        
        
        
  
        
          
  
           
  
              
          
          
                           
  
  
                           
       

                              
      
        
  
                           
            

           
             

               
            
        
  
      
        

      
  
  
                          
                          
                          
       
    
   0010  ; för (i = 0, i < n; i++)   0020  {  0030  ; rl = #0;  i = 0, blir dödkod   0050  last  r2  ,  n  0220  fr3  =  #0.0  0340  fr4  =  #1.0  0055  ; r8 = #0 dödad;  r8 används inte längre   0056  r40  =  #0 ; initialvärde för r8 * 8   0057  r30  =  r2  *  #8 ; ökning för r40   0058  ; r20 = r2 dödad;  r8 = 0, blir död kod   0058  r22  =  r2  *  #8 ; r20 = r2   005  A  ; r14 = #0 dödad;  r8 = 0, blir död kod   005  B  r15  =  #0 ; r14 = 0   005  C  r49  =  r2  +  #1  005  D  r50  =  r49  *  #8; styrka reducerat steg   005  D  r60  =  r2  *  r30  ; ny gräns för r40   0040  G0000:  0060  ; cmp r1, r2 dödade ;  i < n;  induktionsvariabel ersatt   0065  cmp  r40  ,  r60  ; i * 8 * n < 8 * n * n   0070  bge  G0001  0080  0118  r10  =  r40  ; styrka reducerat uttryck till r40   0090  ; för (j = 0; j < n; j++)   0100  {  0120  G0002:  0147  cmp  r10  ,  r22  ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22   0150  bge  G0003  0160  0170  ; A[i,j] = 0,0;   0230  fstore  fr3  ,  A  [  r10  ]  0240  0245  r10  =  r10  +  #8 ; styrka reducerad multiplicera   0260  br  G0002  0270  }  0280  G0003:  0290  ; A[i,i] = 1,0;   0350  fstore  fr4  ,  A  [  r15  ]  0360  0370  ;i++  0380  ; r1 = r1 + #1 dödad;  död kod (r40 styrslinga)   0385  ; r8 = r8 + r2 dödad;  död kod   0386  r40  =  r40  +  r30  ; styrka reducera uttryck r8 * 8   0388  r22  =  r22  +  r30  ; styrka reducera r22 = r20 * 8   0389  r15  =  r15  +  r50  ; styrka reducera r15 = r14 * 8   0390  br  G0000  0400  }  0410  G0001:

Andra hållfasthetsminskningsoperationer

Detta material är omtvistat. Det beskrivs bättre som titthålsoptimering och instruktionsuppgift.

Operatörsstyrkeminskning använder matematiska identiteter för att ersätta långsamma matematiska operationer med snabbare operationer. Fördelarna beror på mål-CPU och ibland på den omgivande koden (vilket kan påverka tillgängligheten för andra funktionella enheter inom CPU).

  • ersätta heltalsdivision eller multiplikation med en potens av 2 med ett aritmetiskt skift eller logiskt skift
  • ersätter heltalsmultiplikation med en konstant med en kombination av skift, adderar eller subtraherar
  • ersätter heltalsdivision med en konstant med en multiplikation, och drar fördel av det begränsade intervallet av maskinheltal. Denna metod fungerar också om divisor är ett icke-heltal som är tillräckligt större än 1, t.ex. √2 eller π.
Ursprunglig beräkning Ersättningsberäkning
y = x / 8 y = x >> 3
y = x * 64 y = x << 6
y = x * 2 y = x << 1
y = x * 15 y = (x << 4) - x
y = x / 10 (där x är av typen uint16_t) y = ((uint32_t)x * (uint32_t)0xCCCD) >> 19)
y = x / π (där x är av typen uint16_t) y = (((uint32_t)x * (uint32_t)0x45F3) >> 16) + x) >> 2)

Induktionsvariabel (föräldralös)

Induktionsvariabel eller rekursiv hållfasthetsreduktion ersätter en funktion av någon systematiskt föränderlig variabel med en enklare beräkning med hjälp av tidigare värden för funktionen. I ett procedurprogrammeringsspråk skulle detta gälla för ett uttryck som involverar en loopvariabel och i ett deklarativt språk skulle det gälla argumentet för en rekursiv funktion . Till exempel, 

              f  x  =  ...  (  3  **  x  )  ...  (  f  (  x  +  1  ))  ...

blir

      
 
                  f  x  =  f'  x  1  där  f'  x  z  =  ...  z  ...  (  f'  (  x  +  1  )  (  3  *  z  ))  ...

tar modifierad rekursiv funktion f ′ en andra parameter z = 3 ** x, vilket gör att den dyra beräkningen (3 ** x) kan ersättas med den billigare (3 * z).

Se även

Anteckningar

  1. ^   Steven Muchnick; Muchnick and Associates (15 augusti 1997). Avancerad kompilatordesignimplementering . Morgan Kaufmann. ISBN 978-1-55860-320-2 . Styrka reduktion.
  2. ^ I språk som C och Java har heltalsdivision avrundning-mot-noll semantik, medan en bitförskjutning alltid avrundar nedåt, vilket kräver specialbehandling för negativa tal. Till exempel i Java evalueras -3 / 2 till -1 , medan -3 >> 1 evalueras till -2 . Så i det här fallet kan kompilatorn inte optimera division med två genom att ersätta den med en bitförskjutning.
  3. ^ Granlund, Torbjörn; Peter L. Montgomery. "Division med invarianta heltal med multiplikation" (PDF) .
  4. ^ Jones, Nigel. "Division av heltal med konstanter" .
Hämtad från " https://en.wikipedia.org/w/index.php?title=Strength_reduction&oldid=1085849871 "