Changes between Version 2 and Version 3 of CarryQueue

Aug 18, 2010, 7:38:42 AM (9 years ago)



  • CarryQueue

    v2 v3  
    4141The code for handling this issue in the compiler might have dependency on the target language. For example in C we may need to call a macro or function that has inline assembly while in assembly we may do something slightly different. Also it has minor interaction with Factor Out pass of the compiler. If a code for loading/storing carry queues is needed to be put inside an if-then-else statement, this code must be put inside both branches of the statement. So one may prefer to put this pass after the Factor Out pass so that workload of Factor Out does not become larger, but this is not necessary.
     43== Carry Queue and While Loop Unrolling ==
     45These new notes (August 18, 2010) elaborate an optimized implementation for while loops,
     46involving a single unrolling.
     48For each block of data, there may be carries for variables within
     49the while loop.  Thus, if there are any such variables, the loop
     50body must be executed at least once.   
     52However, once the loop is executed, the input carries have all
     53been accounted for.   Subsequent iterations should use input carry values
     54of zero for all add with carry operations.   Output carries for each
     55iteration must still be accumulated and or'd together for each
     56iteration.  However, the zeroing of input carries means that
     57add-with-carry operations can be replaced by normal add operations
     58for the second and subsequent operations.   These are faster.
     59Furthermore, the carry queue is needed for accumulating output
     60carries only.
     62This suggests that it may be beneficial to unroll the loop in a
     63way such that the first iteration only uses add-with-carry operation
     64and subsequent iterations use the straight add operation.