def consider_constant(self, TYPE, value, gc):
        if value is not lltype.top_container(value):
            return
        if id(value) in self.seen_roots:
            return
        self.seen_roots[id(value)] = True

        if isinstance(TYPE, (lltype.GcStruct, lltype.GcArray)):
            typeid = self.get_type_id(TYPE)
            hdr = gc.gcheaderbuilder.new_header(value)
            adr = llmemory.cast_ptr_to_adr(hdr)
            gc.init_gc_object_immortal(adr, typeid)
            self.all_prebuilt_gc.append(value)

        # The following collects the addresses of all the fields that have
        # a GC Pointer type, inside the current prebuilt object.  All such
        # fields are potential roots: unless the structure is immutable,
        # they could be changed later to point to GC heap objects.
        adr = llmemory.cast_ptr_to_adr(value._as_ptr())
        if TYPE._gckind == "gc":
            if gc.prebuilt_gc_objects_are_static_roots or gc.DEBUG:
                appendto = self.addresses_of_static_ptrs
            else:
                return
        else:
            appendto = self.addresses_of_static_ptrs_in_nongc
        for a in gc_pointers_inside(value, adr, mutable_only=True):
            appendto.append(a)

def ll_arraycopy(source, dest, source_start, dest_start, length):
    from pypy.rpython.lltypesystem.lloperation import llop
    from pypy.rlib.objectmodel import keepalive_until_here

    # supports non-overlapping copies only
    if not we_are_translated():
        if source == dest:
            assert (source_start + length <= dest_start or
                    dest_start + length <= source_start)

    TP = lltype.typeOf(source).TO
    assert TP == lltype.typeOf(dest).TO
    if isinstance(TP.OF, lltype.Ptr) and TP.OF.TO._gckind == 'gc':
        # perform a write barrier that copies necessary flags from
        # source to dest
        if not llop.gc_writebarrier_before_copy(lltype.Bool, source, dest):
            # if the write barrier is not supported, copy by hand
            for i in range(length):
                dest[i + dest_start] = source[i + source_start]
            return
    source_addr = llmemory.cast_ptr_to_adr(source)
    dest_addr   = llmemory.cast_ptr_to_adr(dest)
    cp_source_addr = (source_addr + llmemory.itemoffsetof(TP, 0) +
                      llmemory.sizeof(TP.OF) * source_start)
    cp_dest_addr = (dest_addr + llmemory.itemoffsetof(TP, 0) +
                    llmemory.sizeof(TP.OF) * dest_start)
    
    llmemory.raw_memcopy(cp_source_addr, cp_dest_addr,
                         llmemory.sizeof(TP.OF) * length)
    keepalive_until_here(source)
    keepalive_until_here(dest)

def ll_shrink_array(p, smallerlength):
    from pypy.rpython.lltypesystem.lloperation import llop
    from pypy.rlib.objectmodel import keepalive_until_here

    if llop.shrink_array(lltype.Bool, p, smallerlength):
        return p    # done by the GC
    # XXX we assume for now that the type of p is GcStruct containing a
    # variable array, with no further pointers anywhere, and exactly one
    # field in the fixed part -- like STR and UNICODE.

    TP = lltype.typeOf(p).TO
    newp = lltype.malloc(TP, smallerlength)

    assert len(TP._names) == 2
    field = getattr(p, TP._names[0])
    setattr(newp, TP._names[0], field)

    ARRAY = getattr(TP, TP._arrayfld)
    offset = (llmemory.offsetof(TP, TP._arrayfld) +
              llmemory.itemoffsetof(ARRAY, 0))
    source_addr = llmemory.cast_ptr_to_adr(p)    + offset
    dest_addr   = llmemory.cast_ptr_to_adr(newp) + offset
    llmemory.raw_memcopy(source_addr, dest_addr, 
                         llmemory.sizeof(ARRAY.OF) * smallerlength)

    keepalive_until_here(p)
    keepalive_until_here(newp)
    return newp

def test_gc_pointers_inside():
    from pypy.rpython import rclass
    PT = lltype.Ptr(lltype.GcStruct('T'))
    S1 = lltype.GcStruct('S', ('x', PT), ('y', PT))
    S2 = lltype.GcStruct('S', ('x', PT), ('y', PT),
                         hints={'immutable': True})
    accessor = rclass.FieldListAccessor()
    S3 = lltype.GcStruct('S', ('x', PT), ('y', PT),
                         hints={'immutable_fields': accessor})
    accessor.initialize(S3, {'x': IR_IMMUTABLE})
    #
    s1 = lltype.malloc(S1)
    adr = llmemory.cast_ptr_to_adr(s1)
    lst = list(gc_pointers_inside(s1._obj, adr, mutable_only=True))
    expected = [adr + llmemory.offsetof(S1, 'x'),
                adr + llmemory.offsetof(S1, 'y')]
    assert lst == expected or lst == expected[::-1]
    #
    s2 = lltype.malloc(S2)
    adr = llmemory.cast_ptr_to_adr(s2)
    lst = list(gc_pointers_inside(s2._obj, adr, mutable_only=True))
    assert lst == []
    #
    s3 = lltype.malloc(S3)
    adr = llmemory.cast_ptr_to_adr(s3)
    lst = list(gc_pointers_inside(s3._obj, adr, mutable_only=True))
    assert lst == [adr + llmemory.offsetof(S3, 'y')]

 def walk_roots(self, collect_stack_root,
                collect_static_in_prebuilt_nongc,
                collect_static_in_prebuilt_gc):
     gc = self.tester.gc
     layoutbuilder = self.tester.layoutbuilder
     if collect_static_in_prebuilt_gc:
         for addrofaddr in layoutbuilder.addresses_of_static_ptrs:
             if addrofaddr.address[0]:
                 collect_static_in_prebuilt_gc(gc, addrofaddr)
     if collect_static_in_prebuilt_nongc:
         for addrofaddr in layoutbuilder.addresses_of_static_ptrs_in_nongc:
             if addrofaddr.address[0]:
                 collect_static_in_prebuilt_nongc(gc, addrofaddr)
     if collect_stack_root:
         stackroots = self.tester.stackroots
         a = lltype.malloc(ADDR_ARRAY, len(stackroots), flavor='raw')
         for i in range(len(a)):
             a[i] = llmemory.cast_ptr_to_adr(stackroots[i])
         a_base = lltype.direct_arrayitems(a)
         for i in range(len(a)):
             ai = lltype.direct_ptradd(a_base, i)
             collect_stack_root(gc, llmemory.cast_ptr_to_adr(ai))
         for i in range(len(a)):
             PTRTYPE = lltype.typeOf(stackroots[i])
             stackroots[i] = llmemory.cast_adr_to_ptr(a[i], PTRTYPE)
         lltype.free(a, flavor='raw')

 def writebarrier_before_copy(self, source, dest, source_start, dest_start, length):
     if self.gc.needs_write_barrier:
         source_addr = llmemory.cast_ptr_to_adr(source)
         dest_addr = llmemory.cast_ptr_to_adr(dest)
         return self.gc.writebarrier_before_copy(source_addr, dest_addr, source_start, dest_start, length)
     else:
         return True

 def copy_string_contents(src, dst, srcstart, dststart, length):
     assert srcstart >= 0
     assert dststart >= 0
     assert length >= 0
     src = llmemory.cast_ptr_to_adr(src) + _str_ofs(srcstart)
     dst = llmemory.cast_ptr_to_adr(dst) + _str_ofs(dststart)
     llmemory.raw_memcopy(src, dst, llmemory.sizeof(CHAR_TP) * length)

 def get_address_of_gcref(self, gcref):
     assert lltype.typeOf(gcref) == llmemory.GCREF
     # first look in the hashtable, using an inexact hash (fails after
     # the object moves)
     addr = llmemory.cast_ptr_to_adr(gcref)
     hash = llmemory.cast_adr_to_int(addr)
     hash -= hash >> self.HASHTABLE_BITS
     hash &= self.HASHTABLE_SIZE - 1
     addr_ref = self.hashtable[hash]
     # the following test is safe anyway, because the addresses found
     # in the hashtable are always the addresses of nonmovable stuff
     # ('addr_ref' is an address inside self.list, not directly the
     # address of a real moving GC object -- that's 'addr_ref.address[0]'.)
     if addr_ref.address[0] == addr:
         return addr_ref
     # if it fails, add an entry to the list
     if self.nextindex == len(self.list):
         # reallocate first, increasing a bit the size every time
         self.oldlists.append(self.list)
         self.list = self.alloc_gcref_list(len(self.list) // 4 * 5)
         self.nextindex = 0
     # add it
     index = self.nextindex
     self.list[index] = gcref
     addr_ref = lltype.direct_ptradd(lltype.direct_arrayitems(self.list),
                                     index)
     addr_ref = llmemory.cast_ptr_to_adr(addr_ref)
     self.nextindex = index + 1
     # record it in the hashtable
     self.hashtable[hash] = addr_ref
     return addr_ref

def test_allocate_new_page():
    pagesize = hdrsize + 16
    arenasize = pagesize * 4 - 1
    #
    def checknewpage(page, size_class):
        size = WORD * size_class
        assert (ac._nuninitialized(page, size_class) ==
                    (pagesize - hdrsize) // size)
        assert page.nfree == 0
        page1 = page.freeblock - hdrsize
        assert llmemory.cast_ptr_to_adr(page) == page1
        assert page.nextpage == PAGE_NULL
    #
    ac = ArenaCollection(arenasize, pagesize, 99)
    assert ac.num_uninitialized_pages == 0
    assert ac.total_memory_used == 0
    #
    page = ac.allocate_new_page(5)
    checknewpage(page, 5)
    assert ac.num_uninitialized_pages == 2
    assert ac.current_arena.freepages - pagesize == cast_ptr_to_adr(page)
    assert ac.page_for_size[5] == page
    #
    page = ac.allocate_new_page(3)
    checknewpage(page, 3)
    assert ac.num_uninitialized_pages == 1
    assert ac.current_arena.freepages - pagesize == cast_ptr_to_adr(page)
    assert ac.page_for_size[3] == page
    #
    page = ac.allocate_new_page(4)
    checknewpage(page, 4)
    assert ac.num_uninitialized_pages == 0
    assert ac.page_for_size[4] == page

 def setinterior(self, toplevelcontainer, inneraddr, INNERTYPE, newvalue):
     if (
         lltype.typeOf(toplevelcontainer).TO._gckind == "gc"
         and isinstance(INNERTYPE, lltype.Ptr)
         and INNERTYPE.TO._gckind == "gc"
     ):
         self.gc.write_barrier(llmemory.cast_ptr_to_adr(newvalue), llmemory.cast_ptr_to_adr(toplevelcontainer))
     llheap.setinterior(toplevelcontainer, inneraddr, INNERTYPE, newvalue)

    def malloc(self, typeid, length=0, zero=False, coallocator=None):
        """For testing.  The interface used by the gctransformer is
        the four malloc_[fixed,var]size[_clear]() functions.
        And (if they exist) to the coalloc_[fixed,var]size_clear functions
        """
        # Rules about fallbacks in case of missing malloc methods:
        #  * malloc_fixedsize_clear() and malloc_varsize_clear() are mandatory
        #  * malloc_fixedsize() and malloc_varsize() fallback to the above
        #  * coalloc_fixedsize_clear() and coalloc_varsize_clear() are optional
        # There is no non-clear version of coalloc for now.
        # XXX: as of r49360, gctransformer.framework never inserts calls
        # to malloc_varsize(), but always uses malloc_varsize_clear()

        size = self.fixed_size(typeid)
        needs_finalizer = bool(self.getfinalizer(typeid))
        weakptr_offset = self.weakpointer_offset(typeid)
        #XXX cannot compare weakptr_offset with -1
        #contains_weakptr = weakpointer_offset. != -1
        if isinstance(weakptr_offset, int):
            assert weakptr_offset == -1
            contains_weakptr = False
        else:
            contains_weakptr = True
        assert not (needs_finalizer and contains_weakptr)
        if self.is_varsize(typeid):
            assert not contains_weakptr
            itemsize = self.varsize_item_sizes(typeid)
            offset_to_length = self.varsize_offset_to_length(typeid)
            if (coallocator is not None and
                hasattr(self, "coalloc_varsize_clear")):
                assert not needs_finalizer
                coallocator = llmemory.cast_ptr_to_adr(coallocator)
                ref = self.coalloc_varsize_clear(coallocator, typeid,
                                                 length, size,
                                                 itemsize, offset_to_length)
            else:
                if zero or not hasattr(self, 'malloc_varsize'):
                    malloc_varsize = self.malloc_varsize_clear
                else:
                    malloc_varsize = self.malloc_varsize
                ref = malloc_varsize(typeid, length, size, itemsize,
                                     offset_to_length, True, needs_finalizer)
        else:
            if (coallocator is not None and
                hasattr(self, "coalloc_fixedsize_clear")):
                assert not needs_finalizer
                coallocator = llmemory.cast_ptr_to_adr(coallocator)
                ref = self.coalloc_fixedsize_clear(coallocator, typeid, size)
            else:
                if zero or not hasattr(self, 'malloc_fixedsize'):
                    malloc_fixedsize = self.malloc_fixedsize_clear
                else:
                    malloc_fixedsize = self.malloc_fixedsize
                ref = malloc_fixedsize(typeid, size, True, needs_finalizer,
                                       contains_weakptr)
        # lots of cast and reverse-cast around...
        return llmemory.cast_ptr_to_adr(ref)

 def writearray(self, p, index, newvalue):
     if self.gc.needs_write_barrier:
         newaddr = llmemory.cast_ptr_to_adr(newvalue)
         addr_struct = llmemory.cast_ptr_to_adr(p)
         if hasattr(self.gc, 'write_barrier_from_array'):
             self.gc.write_barrier_from_array(newaddr, addr_struct, index)
         else:
             self.gc.write_barrier(newaddr, addr_struct)
     p[index] = newvalue

 def do_write_barrier(self, gcref_struct, gcref_newptr):
     hdr_addr = llmemory.cast_ptr_to_adr(gcref_struct)
     hdr_addr -= self.gcheaderbuilder.size_gc_header
     hdr = llmemory.cast_adr_to_ptr(hdr_addr, self.HDRPTR)
     if hdr.tid & self.GCClass.JIT_WB_IF_FLAG:
         # get a pointer to the 'remember_young_pointer' function from
         # the GC, and call it immediately
         llop1 = self.llop1
         funcptr = llop1.get_write_barrier_failing_case(self.WB_FUNCPTR)
         funcptr(llmemory.cast_ptr_to_adr(gcref_struct))

def longername(a, b, size):
    if 1:
        baseofs = itemoffsetof(TP, 0)
        onesize = sizeof(TP.OF)
        size = baseofs + onesize*(size - 1)
        raw_memcopy(cast_ptr_to_adr(b)+baseofs, cast_ptr_to_adr(a)+baseofs, size)
    else:
        a = []
        for i in range(x):
            a.append(i)
    return 0

 def f():
     x = lltype.malloc(S)
     x.x = 10
     y = lltype.malloc(S)
     y.x = 20
     z = x
     llop.gc_x_become(lltype.Void,
                      llmemory.cast_ptr_to_adr(x),
                      llmemory.cast_ptr_to_adr(y))
     # keep 'y' alive until the x_become() is finished, because in
     # theory it could go away as soon as only its address is present
     objectmodel.keepalive_until_here(y)
     return z.x

def _ll_list_resize_really(l, newsize):
    """
    Ensure l.items has room for at least newsize elements, and set
    l.length to newsize.  Note that l.items may change, and even if
    newsize is less than l.length on entry.
    """
    allocated = len(l.items)

    # This over-allocates proportional to the list size, making room
    # for additional growth.  The over-allocation is mild, but is
    # enough to give linear-time amortized behavior over a long
    # sequence of appends() in the presence of a poorly-performing
    # system malloc().
    # The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
    if newsize <= 0:
        ll_assert(newsize == 0, "negative list length")
        l.length = 0
        l.items = _ll_new_empty_item_array(typeOf(l).TO)
        return
    else:
        if newsize < 9:
            some = 3
        else:
            some = 6
        some += newsize >> 3
        try:
            new_allocated = ovfcheck(newsize + some)
        except OverflowError:
            raise MemoryError
    # XXX consider to have a real realloc
    items = l.items
    newitems = malloc(typeOf(l).TO.items.TO, new_allocated)
    before_len = l.length
    if before_len < new_allocated:
        p = before_len - 1
    else:
        p = new_allocated - 1
    ITEM = typeOf(l).TO.ITEM
    if isinstance(ITEM, Ptr):
        while p >= 0:
            newitems[p] = items[p]
            items[p] = nullptr(ITEM.TO)
            p -= 1
    else:
        source = cast_ptr_to_adr(items) + itemoffsetof(typeOf(l.items).TO, 0)
        dest = cast_ptr_to_adr(newitems) + itemoffsetof(typeOf(l.items).TO, 0)
        s = p + 1
        raw_memcopy(source, dest, sizeof(ITEM) * s)
        keepalive_until_here(items)
    l.length = newsize
    l.items = newitems

 def produce_into(self, builder, r):
     fail_subset = builder.subset_of_intvars(r)
     subset, f, exc = self.raising_func_code(builder, r)
     TP = lltype.FuncType([lltype.Signed] * len(subset), lltype.Void)
     ptr = llhelper(lltype.Ptr(TP), f)
     c_addr = ConstAddr(llmemory.cast_ptr_to_adr(ptr), builder.cpu)
     args = [c_addr] + subset
     descr = builder.cpu.calldescrof(TP, TP.ARGS, TP.RESULT)
     self.put(builder, args, descr)
     exc_box = ConstAddr(llmemory.cast_ptr_to_adr(exc), builder.cpu)
     op = ResOperation(rop.GUARD_EXCEPTION, [exc_box], BoxPtr(),
                       descr=BasicFailDescr())
     op.setfailargs(fail_subset)
     builder.loop.operations.append(op)

 def produce_into(self, builder, r):
     subset, f, exc = self.raising_func_code(builder, r)
     TP = lltype.FuncType([lltype.Signed] * len(subset), lltype.Void)
     ptr = llhelper(lltype.Ptr(TP), f)
     c_addr = ConstAddr(llmemory.cast_ptr_to_adr(ptr), builder.cpu)
     args = [c_addr] + subset
     descr = self.getcalldescr(builder, TP)
     self.put(builder, args, descr)
     op = ResOperation(rop.GUARD_NO_EXCEPTION, [], BoxPtr(),
                       descr=BasicFailDescr())
     op._exc_box = ConstAddr(llmemory.cast_ptr_to_adr(exc), builder.cpu)
     op.setfailargs(builder.subset_of_intvars(r))
     builder.should_fail_by = op
     builder.guard_op = op
     builder.loop.operations.append(op)

 def malloc_nonmovable(self, typeid, length, zero):
     # helper for testing, same as GCBase.malloc
     if self.is_varsize(typeid):
         gcref = self.malloc_varsize_slowpath(typeid, length, True)
     else:
         raise NotImplementedError("Not supported")
     return llmemory.cast_ptr_to_adr(gcref)

    def malloc(self, typeid, length=0, zero=False):
        """For testing.  The interface used by the gctransformer is
        the four malloc_[fixed,var]size[_clear]() functions.
        """
        # Rules about fallbacks in case of missing malloc methods:
        #  * malloc_fixedsize_clear() and malloc_varsize_clear() are mandatory
        #  * malloc_fixedsize() and malloc_varsize() fallback to the above
        # XXX: as of r49360, gctransformer.framework never inserts calls
        # to malloc_varsize(), but always uses malloc_varsize_clear()

        size = self.fixed_size(typeid)
        needs_finalizer = bool(self.getfinalizer(typeid))
        contains_weakptr = self.weakpointer_offset(typeid) >= 0
        assert not (needs_finalizer and contains_weakptr)
        if self.is_varsize(typeid):
            assert not contains_weakptr
            assert not needs_finalizer
            itemsize = self.varsize_item_sizes(typeid)
            offset_to_length = self.varsize_offset_to_length(typeid)
            if zero or not hasattr(self, 'malloc_varsize'):
                malloc_varsize = self.malloc_varsize_clear
            else:
                malloc_varsize = self.malloc_varsize
            ref = malloc_varsize(typeid, length, size, itemsize,
                                 offset_to_length, True)
        else:
            if zero or not hasattr(self, 'malloc_fixedsize'):
                malloc_fixedsize = self.malloc_fixedsize_clear
            else:
                malloc_fixedsize = self.malloc_fixedsize
            ref = malloc_fixedsize(typeid, size, True, needs_finalizer,
                                   contains_weakptr)
        # lots of cast and reverse-cast around...
        return llmemory.cast_ptr_to_adr(ref)