freenode/#clasp - IRC Chatlog
Search
19:31:47
drmeister
If anyone has suggestions of how to tie these specialized array classes into the type system so that subtypep works with them - I'd very much appreciate the help.
19:32:31
drmeister
Generic function dispatch with the specialized arrays won't work because (subtypep (class-of arg) 'vector) isn't returning the correct result.
20:13:30
drmeister
It means I still have to weave 'core:simple-vector-int8-t into the SUBTYPEP framework
20:47:17
Bike
'foo and (find-class 'foo) should be identical as far as any type related function is concerned, if the class exists.
20:56:43
drmeister
Adding those classes to hierarchy.lisp was sufficient to get GF dispatch to work properly.
20:58:11
drmeister
The question is then how to make subtypep work. If I told subtypep that these classes are equivalent to 'vector and 'array - I think that might be enough.
20:59:09
Bike
if you tell it a specialized array class is identical to vector it will give wrong answers.
20:59:50
drmeister
Right - what if it says that a specialized array class with one dimension was an array but didn't say it was a vector?
21:00:35
drmeister
Each type (int32, int16 etc) that I have a specialized array on has three new classes.
21:01:11
Bike
But one of those classes includes all specialized arrays with that specialization, including non-vectors?
21:01:24
drmeister
The md-array-xxx and simple-array-xxx are subtypes of array and if DIM=1 subtypes of vector
21:02:20
Bike
"array" refers to a particular set of objects, which includes non-vectors, so array is not a subtype of vector
21:02:55
Bike
if md-array-fixnum is the set of all arrays that are specialized to FIXNUM, md-array-fixnum is not a subtype of vector
21:05:23
Bike
a type is a set of objects. a class is an object that is sometimes identified with a type.
21:05:33
drmeister
An md-array-fixnum can represent an array of fixnums with any rank - those are all subtypes of 'array. It it has rank = 1 is it not a subtype of 'vector?
21:06:26
Bike
that class (or the type identified with it) contains some objects that are vectors, and some that are not.
21:06:43
Bike
since it contains objects that are not vectors, the class/type can't be a subtype of vector.
21:13:10
drmeister
https://github.com/drmeister/clasp/blob/dev/src/lisp/kernel/lsp/predlib.lsp#L1506
21:17:10
Bike
it looks like it canonicalizes types. and for classes it calls register-class. that does i think find-registered-tag to find "classes which belong to the core type system of LISP (ARRAY, NUMBER, etc)"
21:21:45
Bike
that would work except simple-vector doesn't work like that. it would be (simple-array byte32 (*)) i think.
21:51:54
drmeister
I hope it means that (subtypep 'core:simple-vector-byte8-t 'vector) will now return T
21:52:56
drmeister
https://github.com/drmeister/clasp/blob/dev/src/lisp/kernel/lsp/predlib.lsp#L1252
3:46:23
Bike
i wrote eliminate-superfluous-temporaries again. on a big function it takes ~55 ms and reduces the number of variables 43%, and the time for mark-dynamic-extent by about the same fraction. so i should probably see about testing it thoroughly for incorporation
3:47:59
beach
Sounds good. I hope you used the correct definition of "superfluous", unlike what I did in the first version.
3:49:07
Bike
well basically what it does is, it looks at all inputs to all instructions, and if the instruction is dominated by an assignment to an input, it replaces that input with whatever the input to the assignment is.
3:49:35
Bike
so i think it's correct. i actually made it dumber than it could be because i figured it would be enough (and was apparently correct)
3:50:11
beach
I am unable to determine in real time whether that is correct, so I need time to think about it.
3:51:38
beach
Also, we should be careful. Current register-allocation algorithms assign a permanent location for a lexical variable, either in a register or on the stack. Eliminating temporaries might make it impossible to spill some variable around a loop, for instance.
3:54:54
Bike
i don't know about that, but there needs to be something or a lot of analysis is harder than it needs to be.
3:55:24
Bike
currently something like (when (typeq c cons) (+ (car c) (cdr c))) does three checks because the temps obscure type information.
3:57:43
Bike
and then the temp is never used again, so the information about temp being a cons is irrelevant later.
3:58:50
Bike
information is lost. the car and cdr forms just check C, which has no information associated with it.
4:00:37
Bike
so to do anything helpful something has to know that c and temp have the same value at the car and cdr forms. the obvious way of doing that is eliminating the temp
4:01:42
Bike
it would be relevant for THE, and i guess semantics around the and typeq could be rearranged somehow
4:02:20
Bike
you mean propagating type information in the reverse direction from control flow, right? typeq doesn't imply anything about the type of its argument before the typeq is executed, see.
4:02:49
beach
It seems to me that in the true branch of the TYPEQ, it ought to be possible to decide that the type of C is the same as that of TEMP.
4:03:58
Bike
if value numbering means tracking sets of variables that have the same value at given control points, that's what eliminate-superfluous-temporaries does.
4:04:06
beach
It is able to determine that two lexical locations contain the same value at particular control points.
4:05:14
beach
Given the papers I have read, I seriously doubt that your simple technique covers the general case.
4:06:48
beach
From what I have read, Kildall's algorithm is the only one that really works for global value numbering. But it has to be the right domain.
4:08:45
beach
It is bound to be very complicated in the presence of nested functions that can be executed in separate threads, and such.
4:10:08
Bike
well, it is kildall. but again, i made it really simple, there's no way it does the complete thing. I mostly just wanted to fix obvious cases like (foo x) having a temp.
4:11:16
beach
Sure. What I am saying is that it might be worthwhile for you to read up on global value numbering and contemplate how it would work in the presence of complex control structures like we have. On paid time, obviously! :)
4:11:59
beach
Global value numbering is certainly one analysis that Cleavir should provide to its clients.
4:12:39
Bike
i tried rewriting it (ast-to-hir) but i think i've convinced myself that's not the way to go
4:14:08
Bike
it looks like global value numbering is also supposed to work with operations, like if x = y then (car x) = (car y), which seems a good deal trickier
4:15:45
beach
But it could be worthwhile. I often write things like (car x) several times rather than introducing a temporary.
4:16:27
beach
Again, it gets tricky in the presence of threads and other complex control structures.
4:17:59
Bike
well, for a start i can ignore cells, which makes it easier. i'm still not sure what to do with cells in general