PTO-TILE-MODEL-EXECUTION-SORTING

1// PTO-UNIT: {"id":"PTO-TILE-MODEL-EXECUTION-SORTING","surface":"tile","classification":["model","execution","sorting"],"depends_on":["PTO-TILE-MODEL-LEGALITY-SORTING"]}2
3func TSORT(4    destination: TileIndex,5    destination_indices: TileIndex,6    source: TileIndex,7    sort_width: integer {1..64},8    descending: boolean)9begin10    assert TileOperandsLegal_TSORT(11        destination,12        destination_indices,13        source,14        sort_width,15        descending);16
17    let source_tile = _Tiles[[source]];18    let source_has_signaling_nan =19        TileSortSourceHasSignalingNaN(source);20    assert source_tile.valid_columns >= 1;21    let column_count =22        source_tile.valid_columns as integer {1..65535};23    var result_values = _Tiles[[destination]];24    var result_indices = _Tiles[[destination_indices]];25    var values = source_tile;26    var indices = result_indices;27
28    for row = 0 to source_tile.valid_rows - 1 looplimit 65536 do29        for column = 0 to source_tile.valid_columns - 1 looplimit 65536 do30            let element = TileLogicalLinearIndex(31                source_tile,32                row as integer {0..65535},33                column as integer {0..65535});34            indices = TileInfoWithLogicalElement(indices, element,35                Zeros{PTO_XLEN} + (column MOD sort_width));36        end;37
38        let group_count: integer {1..65535} =39            ((column_count - 1) DIVRM sort_width) + 1;40        for group = 0 to group_count - 1 looplimit 65536 do41            let group_begin = (group * sort_width)42                as integer {0..65535};43            let group_end =44                if group_begin + sort_width < column_count then45                    group_begin + sort_width46                else47                    column_count;48
49            for sort_pass = 0 to 63 do50                for offset = 0 to 62 do51                    let left_column = group_begin + offset;52                    if left_column + 1 < group_end then53                        let left_element = TileLogicalLinearIndex(54                            source_tile,55                            row as integer {0..65535},56                            left_column as integer {0..65535});57                        let right_element = TileLogicalLinearIndex(58                            source_tile,59                            row as integer {0..65535},60                            (left_column + 1) as integer {0..65535});61                        if !TileSortLeftBefore(62                               TileReadLogicalElement(values, left_element),63                               TileReadLogicalElement(values, right_element),64                               descending,65                               source_tile.data_type) then66                            let left_value =67                                TileReadLogicalElement(values, left_element);68                            let right_value =69                                TileReadLogicalElement(values, right_element);70                            values = TileInfoWithLogicalElement(71                                values, left_element, right_value);72                            values = TileInfoWithLogicalElement(73                                values, right_element, left_value);74
75                            let left_index =76                                TileReadLogicalElement(indices, left_element);77                            let right_index =78                                TileReadLogicalElement(indices, right_element);79                            indices = TileInfoWithLogicalElement(80                                indices, left_element, right_index);81                            indices = TileInfoWithLogicalElement(82                                indices, right_element, left_index);83                        end;84                    end;85                end;86            end;87        end;88    end;89
90    result_values = values;91    result_values = TileWithValidRegionDefined(result_values);92    result_values = TileWithPadding(result_values, TilePad_Null);93    result_values.location = TileLocation_Any;94
95    result_indices = indices;96    result_indices = TileWithValidRegionDefined(result_indices);97    result_indices = TileWithPadding(result_indices, TilePad_Null);98    result_indices.location = TileLocation_Any;99
100    // Numeric status and both result Tiles are one non-faulting architectural101    // publication group.  Signaling NaNs remain stable sortable values and102    // set the sticky invalid flag instead of making the operation illegal.103    if source_has_signaling_nan then104        RecordNumericStatusFlags(Zeros{5} + 1);105    end;106    _Tiles[[destination]] = result_values;107    _Tiles[[destination_indices]] = result_indices;108end;109
110func TMRGSORT(111    destination: TileIndex,112    source_left: TileIndex,113    source_right: TileIndex,114    descending: boolean)115begin116    assert TileOperandsLegal_TMRGSORT(117        destination,118        source_left,119        source_right,120        descending);121
122    let left_tile = _Tiles[[source_left]];123    let right_tile = _Tiles[[source_right]];124    let source_has_signaling_nan =125        TileSortSourceHasSignalingNaN(source_left) ||126        TileSortSourceHasSignalingNaN(source_right);127    var result = _Tiles[[destination]];128    var left_column: integer {0..65535} = 0;129    var right_column: integer {0..65535} = 0;130    let output_columns =131        left_tile.valid_columns + right_tile.valid_columns;132
133    for output_column = 0 to output_columns - 1 looplimit 65536 do134        var take_left = right_column >= right_tile.valid_columns;135        if left_column < left_tile.valid_columns &&136           right_column < right_tile.valid_columns then137            let left_element = TileLogicalLinearIndex(138                left_tile,139                0,140                left_column);141            let right_element = TileLogicalLinearIndex(142                right_tile,143                0,144                right_column);145            take_left = TileSortLeftBefore(146                TileReadLogicalElement(left_tile, left_element),147                TileReadLogicalElement(right_tile, right_element),148                descending,149                left_tile.data_type);150        end;151
152        if take_left then153            let left_element = TileLogicalLinearIndex(154                left_tile,155                0,156                left_column);157            let output_element = TileLogicalLinearIndex(158                result,159                0,160                output_column as integer {0..65535});161            result = TileInfoWithLogicalElement(result, output_element,162                TileReadLogicalElement(left_tile, left_element));163            left_column = (left_column + 1) as integer {0..65535};164        else165            let right_element = TileLogicalLinearIndex(166                right_tile,167                0,168                right_column);169            let output_element = TileLogicalLinearIndex(170                result,171                0,172                output_column as integer {0..65535});173            result = TileInfoWithLogicalElement(result, output_element,174                TileReadLogicalElement(right_tile, right_element));175            right_column = (right_column + 1) as integer {0..65535};176        end;177    end;178
179    result = TileWithValidRegionDefined(result);180    result = TileWithPadding(result, TilePad_Null);181    result.location = TileLocation_Any;182    if source_has_signaling_nan then183        RecordNumericStatusFlags(Zeros{5} + 1);184    end;185    _Tiles[[destination]] = result;186end;187