6c95154ca5b0 — Leonard Ritter a month ago
* work on kernel
4 files changed, 148 insertions(+), 285 deletions(-)

M bin/tukan
R include/KHR/khrplatform.h => 
A => testing/test_compute_process.sc
A => testing/test_register_allocation.sc
M bin/tukan +4 -1
@@ 1,6 1,9 @@ 
 #!/usr/bin/env scopes
 
 import ..lib.tukan.use
-import tukan.main
+import tukan.kernel
+
+tukan.kernel.boot;
 
 
+

          
R include/KHR/khrplatform.h =>  +0 -284
@@ 1,284 0,0 @@ 
-#ifndef __khrplatform_h_
-#define __khrplatform_h_
-
-/*
-** Copyright (c) 2008-2009 The Khronos Group Inc.
-**
-** Permission is hereby granted, free of charge, to any person obtaining a
-** copy of this software and/or associated documentation files (the
-** "Materials"), to deal in the Materials without restriction, including
-** without limitation the rights to use, copy, modify, merge, publish,
-** distribute, sublicense, and/or sell copies of the Materials, and to
-** permit persons to whom the Materials are furnished to do so, subject to
-** the following conditions:
-**
-** The above copyright notice and this permission notice shall be included
-** in all copies or substantial portions of the Materials.
-**
-** THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
-** MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
-** IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
-** CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
-** TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
-** MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS.
-*/
-
-/* Khronos platform-specific types and definitions.
- *
- * $Revision: 32517 $ on $Date: 2016-03-11 02:41:19 -0800 (Fri, 11 Mar 2016) $
- *
- * Adopters may modify this file to suit their platform. Adopters are
- * encouraged to submit platform specific modifications to the Khronos
- * group so that they can be included in future versions of this file.
- * Please submit changes by sending them to the public Khronos Bugzilla
- * (http://khronos.org/bugzilla) by filing a bug against product
- * "Khronos (general)" component "Registry".
- *
- * A predefined template which fills in some of the bug fields can be
- * reached using http://tinyurl.com/khrplatform-h-bugreport, but you
- * must create a Bugzilla login first.
- *
- *
- * See the Implementer's Guidelines for information about where this file
- * should be located on your system and for more details of its use:
- *    http://www.khronos.org/registry/implementers_guide.pdf
- *
- * This file should be included as
- *        #include <KHR/khrplatform.h>
- * by Khronos client API header files that use its types and defines.
- *
- * The types in khrplatform.h should only be used to define API-specific types.
- *
- * Types defined in khrplatform.h:
- *    khronos_int8_t              signed   8  bit
- *    khronos_uint8_t             unsigned 8  bit
- *    khronos_int16_t             signed   16 bit
- *    khronos_uint16_t            unsigned 16 bit
- *    khronos_int32_t             signed   32 bit
- *    khronos_uint32_t            unsigned 32 bit
- *    khronos_int64_t             signed   64 bit
- *    khronos_uint64_t            unsigned 64 bit
- *    khronos_intptr_t            signed   same number of bits as a pointer
- *    khronos_uintptr_t           unsigned same number of bits as a pointer
- *    khronos_ssize_t             signed   size
- *    khronos_usize_t             unsigned size
- *    khronos_float_t             signed   32 bit floating point
- *    khronos_time_ns_t           unsigned 64 bit time in nanoseconds
- *    khronos_utime_nanoseconds_t unsigned time interval or absolute time in
- *                                         nanoseconds
- *    khronos_stime_nanoseconds_t signed time interval in nanoseconds
- *    khronos_boolean_enum_t      enumerated boolean type. This should
- *      only be used as a base type when a client API's boolean type is
- *      an enum. Client APIs which use an integer or other type for
- *      booleans cannot use this as the base type for their boolean.
- *
- * Tokens defined in khrplatform.h:
- *
- *    KHRONOS_FALSE, KHRONOS_TRUE Enumerated boolean false/true values.
- *
- *    KHRONOS_SUPPORT_INT64 is 1 if 64 bit integers are supported; otherwise 0.
- *    KHRONOS_SUPPORT_FLOAT is 1 if floats are supported; otherwise 0.
- *
- * Calling convention macros defined in this file:
- *    KHRONOS_APICALL
- *    KHRONOS_APIENTRY
- *    KHRONOS_APIATTRIBUTES
- *
- * These may be used in function prototypes as:
- *
- *      KHRONOS_APICALL void KHRONOS_APIENTRY funcname(
- *                                  int arg1,
- *                                  int arg2) KHRONOS_APIATTRIBUTES;
- */
-
-/*-------------------------------------------------------------------------
- * Definition of KHRONOS_APICALL
- *-------------------------------------------------------------------------
- * This precedes the return type of the function in the function prototype.
- */
-#if defined(_WIN32) && !defined(__SCITECH_SNAP__)
-#   define KHRONOS_APICALL __declspec(dllimport)
-#elif defined (__SYMBIAN32__)
-#   define KHRONOS_APICALL IMPORT_C
-#elif defined(__ANDROID__)
-#   define KHRONOS_APICALL __attribute__((visibility("default")))
-#else
-#   define KHRONOS_APICALL
-#endif
-
-/*-------------------------------------------------------------------------
- * Definition of KHRONOS_APIENTRY
- *-------------------------------------------------------------------------
- * This follows the return type of the function  and precedes the function
- * name in the function prototype.
- */
-#if defined(_WIN32) && !defined(_WIN32_WCE) && !defined(__SCITECH_SNAP__)
-    /* Win32 but not WinCE */
-#   define KHRONOS_APIENTRY __stdcall
-#else
-#   define KHRONOS_APIENTRY
-#endif
-
-/*-------------------------------------------------------------------------
- * Definition of KHRONOS_APIATTRIBUTES
- *-------------------------------------------------------------------------
- * This follows the closing parenthesis of the function prototype arguments.
- */
-#if defined (__ARMCC_2__)
-#define KHRONOS_APIATTRIBUTES __softfp
-#else
-#define KHRONOS_APIATTRIBUTES
-#endif
-
-/*-------------------------------------------------------------------------
- * basic type definitions
- *-----------------------------------------------------------------------*/
-#if (defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L) || defined(__GNUC__) || defined(__SCO__) || defined(__USLC__)
-
-
-/*
- * Using <stdint.h>
- */
-#include <stdint.h>
-typedef int32_t                 khronos_int32_t;
-typedef uint32_t                khronos_uint32_t;
-typedef int64_t                 khronos_int64_t;
-typedef uint64_t                khronos_uint64_t;
-#define KHRONOS_SUPPORT_INT64   1
-#define KHRONOS_SUPPORT_FLOAT   1
-
-#elif defined(__VMS ) || defined(__sgi)
-
-/*
- * Using <inttypes.h>
- */
-#include <inttypes.h>
-typedef int32_t                 khronos_int32_t;
-typedef uint32_t                khronos_uint32_t;
-typedef int64_t                 khronos_int64_t;
-typedef uint64_t                khronos_uint64_t;
-#define KHRONOS_SUPPORT_INT64   1
-#define KHRONOS_SUPPORT_FLOAT   1
-
-#elif defined(_WIN32) && !defined(__SCITECH_SNAP__)
-
-/*
- * Win32
- */
-typedef __int32                 khronos_int32_t;
-typedef unsigned __int32        khronos_uint32_t;
-typedef __int64                 khronos_int64_t;
-typedef unsigned __int64        khronos_uint64_t;
-#define KHRONOS_SUPPORT_INT64   1
-#define KHRONOS_SUPPORT_FLOAT   1
-
-#elif defined(__sun__) || defined(__digital__)
-
-/*
- * Sun or Digital
- */
-typedef int                     khronos_int32_t;
-typedef unsigned int            khronos_uint32_t;
-#if defined(__arch64__) || defined(_LP64)
-typedef long int                khronos_int64_t;
-typedef unsigned long int       khronos_uint64_t;
-#else
-typedef long long int           khronos_int64_t;
-typedef unsigned long long int  khronos_uint64_t;
-#endif /* __arch64__ */
-#define KHRONOS_SUPPORT_INT64   1
-#define KHRONOS_SUPPORT_FLOAT   1
-
-#elif 0
-
-/*
- * Hypothetical platform with no float or int64 support
- */
-typedef int                     khronos_int32_t;
-typedef unsigned int            khronos_uint32_t;
-#define KHRONOS_SUPPORT_INT64   0
-#define KHRONOS_SUPPORT_FLOAT   0
-
-#else
-
-/*
- * Generic fallback
- */
-#include <stdint.h>
-typedef int32_t                 khronos_int32_t;
-typedef uint32_t                khronos_uint32_t;
-typedef int64_t                 khronos_int64_t;
-typedef uint64_t                khronos_uint64_t;
-#define KHRONOS_SUPPORT_INT64   1
-#define KHRONOS_SUPPORT_FLOAT   1
-
-#endif
-
-
-/*
- * Types that are (so far) the same on all platforms
- */
-typedef signed   char          khronos_int8_t;
-typedef unsigned char          khronos_uint8_t;
-typedef signed   short int     khronos_int16_t;
-typedef unsigned short int     khronos_uint16_t;
-
-/*
- * Types that differ between LLP64 and LP64 architectures - in LLP64,
- * pointers are 64 bits, but 'long' is still 32 bits. Win64 appears
- * to be the only LLP64 architecture in current use.
- */
-#ifdef _WIN64
-typedef signed   long long int khronos_intptr_t;
-typedef unsigned long long int khronos_uintptr_t;
-typedef signed   long long int khronos_ssize_t;
-typedef unsigned long long int khronos_usize_t;
-#else
-typedef signed   long  int     khronos_intptr_t;
-typedef unsigned long  int     khronos_uintptr_t;
-typedef signed   long  int     khronos_ssize_t;
-typedef unsigned long  int     khronos_usize_t;
-#endif
-
-#if KHRONOS_SUPPORT_FLOAT
-/*
- * Float type
- */
-typedef          float         khronos_float_t;
-#endif
-
-#if KHRONOS_SUPPORT_INT64
-/* Time types
- *
- * These types can be used to represent a time interval in nanoseconds or
- * an absolute Unadjusted System Time.  Unadjusted System Time is the number
- * of nanoseconds since some arbitrary system event (e.g. since the last
- * time the system booted).  The Unadjusted System Time is an unsigned
- * 64 bit value that wraps back to 0 every 584 years.  Time intervals
- * may be either signed or unsigned.
- */
-typedef khronos_uint64_t       khronos_utime_nanoseconds_t;
-typedef khronos_int64_t        khronos_stime_nanoseconds_t;
-#endif
-
-/*
- * Dummy value used to pad enum types to 32 bits.
- */
-#ifndef KHRONOS_MAX_ENUM
-#define KHRONOS_MAX_ENUM 0x7FFFFFFF
-#endif
-
-/*
- * Enumerated boolean type
- *
- * Values other than zero should be considered to be true.  Therefore
- * comparisons should not be made against KHRONOS_TRUE.
- */
-typedef enum {
-    KHRONOS_FALSE = 0,
-    KHRONOS_TRUE  = 1,
-    KHRONOS_BOOLEAN_ENUM_FORCE_SIZE = KHRONOS_MAX_ENUM
-} khronos_boolean_enum_t;
-
-#endif /* __khrplatform_h_ */

          
A => testing/test_compute_process.sc +35 -0
@@ 0,0 1,35 @@ 
+
+#!/usr/bin/env scopes
+
+import ..lib.tukan.use
+using import tukan.gpucall
+using import glsl
+using import glm
+using import testing
+
+#
+    how would a shader indicate what
+
+shared tmp : vec3
+
+@@ gpufn
+fn testfunc (x y)
+    tmp =
+        vec3
+            x + y
+            x - y
+            x * y
+    unpack (deref tmp)
+
+print (testfunc 2.0 3.0)
+print (testfunc 0.1 0.2)
+
+test ((gpucall bitcount 5) == (bitcount 5))
+test ((gpucall findlsb 32768) == (findlsb 32768))
+test ((gpucall bitreverse 0b10010110) == (bitreverse 0b10010110))
+test (all? ((gpucall findmsb (vectorof i32 1 3 5 9)) == (vectorof i32 0 1 2 3)))
+test ((gpucall findmsb 6) == (findmsb 6))
+test ((gpucall findmsb 0) == (findmsb 0))
+test ((gpucall findlsb 0) == (findlsb 0))
+
+;
  No newline at end of file

          
A => testing/test_register_allocation.sc +109 -0
@@ 0,0 1,109 @@ 
+
+#   register allocation algorithm idea in O(n)
+
+    by leonard ritter
+
+    based on DAG visualization here:
+
+    https://twitter.com/paniq/status/1297661746832973825
+
+using import Array
+using import Map
+
+# if false, find lifetime from out edges instead - either method has
+    its advantages.
+let USE_IN_EDGES = true
+
+# the hardcoded demo DAG is based on the petersen graph
+
+fn in-edges (i)
+    local result : (Array i32)
+    inline node (...)
+        va-map
+            inline (x)
+                'append result x
+            ...
+    switch i
+    case 0 (node 1 4)
+    case 1 (node 2)
+    case 2 (node 3)
+    case 3 (node)
+    case 4 (node 3)
+    case 5 (node 0)
+    case 6 (node 1 8)
+    case 7 (node 2 5)
+    case 8 (node 3 5)
+    case 9 (node 4 6 7)
+    default;
+    result
+
+fn out-edges (i)
+    local result : (Array i32)
+    inline nodeto (...)
+        va-map
+            inline (x)
+                'append result x
+            ...
+    switch i
+    case 0 (nodeto 5)
+    case 1 (nodeto 0 6)
+    case 2 (nodeto 1 7)
+    case 3 (nodeto 2 4 8)
+    case 4 (nodeto 0 9)
+    case 5 (nodeto 7 8)
+    case 6 (nodeto 9)
+    case 7 (nodeto 9)
+    case 8 (nodeto 6)
+    case 9 (nodeto)
+    default;
+    result
+
+# hardcoded topo order as topological sorting is not what we want to demo here
+local topo-order =
+    arrayof i32 3 2 4 1 0 5 7 8 6 9
+local inverse-topo-order : (array i32 10)
+local node-eol : (array i32 10)
+# build map inverse
+for i node in (enumerate topo-order)
+    static-if USE_IN_EDGES
+        # keep incoming nodes alive for as long as we're alive
+        for source in (in-edges node)
+            let dest = (node-eol @ source)
+            dest = (max dest i)
+    else
+        inverse-topo-order @ node = i
+
+# now do register allocation
+let MAX_REGISTERS = 10
+local registers : (array i32 MAX_REGISTERS)
+# walk nodes in topological order
+for i node in (enumerate topo-order)
+    let register =
+        # find free register
+        for j end-of-life in (enumerate registers)
+            # any register being consumed in this frame or earlier is fine
+            if (end-of-life <= i)
+                # found one
+                break j
+        else
+            error "register overflow"
+    let end-of-life =
+        static-if USE_IN_EDGES
+            node-eol @ node
+        else
+            # find last access
+            fold (best = 0) for j in (out-edges node)
+                let time = (inverse-topo-order @ j)
+                max best time
+    # allocate register providing end of life time
+    registers @ register = end-of-life
+    # the final assigned register
+    print "node" node "sets register" register "for" (end-of-life - i) "cycles"
+    # print active registers
+    #do
+        for j end-of-life in (enumerate registers)
+            if (end-of-life > i)
+                sc_write (repr j)
+                sc_write " "
+        sc_write "\n"
+