Closed
Bug 584608
Opened 14 years ago
Closed 10 years ago
Use bitmap in AR instead of array of LIns*
Categories
(Core Graveyard :: Nanojit, defect)
Core Graveyard
Nanojit
Tracking
(Not tracked)
RESOLVED
WONTFIX
Future
People
(Reporter: edwsmith, Unassigned)
References
Details
Attachments
(1 file)
9.53 KB,
patch
|
Details | Diff | Splinter Review |
While discussing phi resolution with Bill, we realized the _entries[] array in AR is only used to track what slots are free/used; the LIns* value stored in each slot is only used for verbose output and sanity checking. Here's a start of a patch that uses a bitmap for allocation instead. It doesn't address Bug 534797 in general (allocating space for >2 slots is still quadratic), but we could use BSF/BSR instructions (aka msbSet(), aka nRegisterAllocFromSet()) to make the common cases faster; and the scan for empty holes could be improved by skipping 32/64 bits at a time. A different AR structure might work better anyway (segregated free list?), in which case this patch merely abstracts access to _entries[]. posting in case we want to take this further.
Reporter | ||
Updated•14 years ago
|
Target Milestone: --- → Future
Reporter | ||
Updated•14 years ago
|
Attachment #463051 -
Attachment is patch: true
Attachment #463051 -
Attachment mime type: application/octet-stream → text/plain
Reporter | ||
Comment 1•14 years ago
|
||
note to self: the decl for _used[] should round up in case NJ_MAX_STACK_ENTRY isn't a multiple of 32.
Reporter | ||
Comment 2•14 years ago
|
||
Copied comment from Bill Maddox from bug 584935: > I would prefer an AR representation based on an ordered list of allocated > regions. This would allow annotations to associated with the regions. The > current phi node prototype (see bug 575527) requires that a phi node be begin > its lifetime in a register, meaning that a block may have no more phi nodes > than allocatable registers of the proper class. I have given some thought to > what would be needed to relax this restriction, and find it desirable to be > able to coalesce stack allocations, i.e., to have more than one LIns sharing a > slot. In this case, we would have to delay deallocation until all LIns holding > the AR slot are dead, suggesting that a reference count be maintained for the > AR reservation. > > A more immediate issue with both the present scheme and a bitmap is that they > don't handle large multi-word allocations well, e.g., stack-allocated arrays. > This may be adequate for the current use cases, but limits the applicability of > NanoJIT.
Reporter | ||
Comment 3•14 years ago
|
||
Comment on attachment 463051 [details] [diff] [review] use AR::_used[] bitmap instead of _entries[]. Comment copied from Nick Nethercote on bug 584935, because it really applies to this patch: > class AR > { > private: > uint32_t _highWaterMark; /* index of highest entry used since last clear() */ >+ uint32_t _used[NJ_MAX_STACK_ENTRY/(8*sizeof(uint32_t))]; >+#if defined(_DEBUG) > LIns* _entries[ NJ_MAX_STACK_ENTRY ]; /* maps to 4B contiguous locations relative to the frame pointer. > NB: _entries[0] is always unused */ >+#endif I'd like a comment explaining _used, that it's a bitset implemented using 32-bit values. I'd also like a comment explaining the connection between _used and _entries; and since they are so closely linked their names should be more similar, maybe _usedBits and _usedInstrs?
Reporter | ||
Updated•14 years ago
|
Assignee: nobody → edwsmith
Reporter | ||
Comment 4•14 years ago
|
||
I haven't found any evidence by profiling the JIT that this is a worthwhile patch, so I'm un-assigning myself. If new evidence emerges, anyone is free to pick this up.
Assignee: edwsmith → nobody
Assignee | ||
Updated•10 years ago
|
Product: Core → Core Graveyard
Comment 5•10 years ago
|
||
Nanojit has been dead for several years. Its Bugzilla component has been moved to the graveyard (bug 984276). I checked all the open bugs. They're all uninteresting, so I'm WONTFIXing them all. Apologies for the bugspam.
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → WONTFIX
You need to log in
before you can comment on or make changes to this bug.
Description
•