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)

defect
Not set
normal

Tracking

(Not tracked)

RESOLVED WONTFIX
Future

People

(Reporter: edwsmith, Unassigned)

References

Details

Attachments

(1 file)

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.
Target Milestone: --- → Future
Blocks: 534797
Attachment #463051 - Attachment is patch: true
Attachment #463051 - Attachment mime type: application/octet-stream → text/plain
note to self: the decl for _used[] should round up in case NJ_MAX_STACK_ENTRY isn't a multiple of 32.
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.
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?
Assignee: nobody → edwsmith
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
Product: Core → Core Graveyard
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.

Attachment

General

Creator:
Created:
Updated:
Size: