Source

pypy-sandbox-4-pycode / pypy / jit / backend / ppc / ppcgen / regalloc.py

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
from pypy.jit.backend.llsupport.regalloc import (RegisterManager, FrameManager,
                                                 TempBox, compute_vars_longevity)
from pypy.jit.backend.ppc.ppcgen.arch import (WORD, MY_COPY_OF_REGS)
from pypy.jit.backend.ppc.ppcgen.jump import (remap_frame_layout_mixed,
                                              remap_frame_layout)
from pypy.jit.backend.ppc.ppcgen.locations import imm
from pypy.jit.backend.ppc.ppcgen.helper.regalloc import (_check_imm_arg, 
                                                         prepare_cmp_op,
                                                         prepare_unary_int_op,
                                                         prepare_binary_int_op,
                                                         prepare_binary_int_op_with_imm,
                                                         prepare_unary_cmp)
from pypy.jit.metainterp.history import (INT, REF, FLOAT, Const, ConstInt, 
                                         ConstPtr, Box)
from pypy.jit.metainterp.history import JitCellToken, TargetToken
from pypy.jit.metainterp.resoperation import rop
from pypy.jit.backend.ppc.ppcgen import locations
from pypy.rpython.lltypesystem import rffi, lltype, rstr
from pypy.jit.backend.llsupport import symbolic
from pypy.jit.backend.llsupport.descr import ArrayDescr
from pypy.jit.codewriter.effectinfo import EffectInfo
import pypy.jit.backend.ppc.ppcgen.register as r
from pypy.jit.codewriter import heaptracker
from pypy.jit.backend.llsupport.descr import unpack_arraydescr
from pypy.jit.backend.llsupport.descr import unpack_fielddescr
from pypy.jit.backend.llsupport.descr import unpack_interiorfielddescr

# xxx hack: set a default value for TargetToken._arm_loop_code.  If 0, we know
# that it is a LABEL that was not compiled yet.
TargetToken._ppc_loop_code = 0

class TempInt(TempBox):
    type = INT

    def __repr__(self):
        return "<TempInt at %s>" % (id(self),)

class TempPtr(TempBox):
    type = REF

    def __repr__(self):
        return "<TempPtr at %s>" % (id(self),)

class PPCRegisterManager(RegisterManager):
    all_regs              = r.MANAGED_REGS
    box_types             = None       # or a list of acceptable types
    no_lower_byte_regs    = all_regs
    save_around_call_regs = r.VOLATILES

    REGLOC_TO_COPY_AREA_OFS = {
        r.r0:   MY_COPY_OF_REGS + 0 * WORD,
        r.r2:   MY_COPY_OF_REGS + 1 * WORD,
        r.r3:   MY_COPY_OF_REGS + 2 * WORD,
        r.r4:   MY_COPY_OF_REGS + 3 * WORD,
        r.r5:   MY_COPY_OF_REGS + 4 * WORD,
        r.r6:   MY_COPY_OF_REGS + 5 * WORD,
        r.r7:   MY_COPY_OF_REGS + 6 * WORD,
        r.r8:   MY_COPY_OF_REGS + 7 * WORD,
        r.r9:   MY_COPY_OF_REGS + 8 * WORD,
        r.r10:  MY_COPY_OF_REGS + 9 * WORD,
        r.r11:  MY_COPY_OF_REGS + 10 * WORD,
        r.r12:  MY_COPY_OF_REGS + 11 * WORD,
        r.r13:  MY_COPY_OF_REGS + 12 * WORD,
        r.r14:  MY_COPY_OF_REGS + 13 * WORD,
        r.r15:  MY_COPY_OF_REGS + 14 * WORD,
        r.r16:  MY_COPY_OF_REGS + 15 * WORD,
        r.r17:  MY_COPY_OF_REGS + 16 * WORD,
        r.r18:  MY_COPY_OF_REGS + 17 * WORD,
        r.r19:  MY_COPY_OF_REGS + 18 * WORD,
        r.r20:  MY_COPY_OF_REGS + 19 * WORD,
        r.r21:  MY_COPY_OF_REGS + 20 * WORD,
        r.r22:  MY_COPY_OF_REGS + 21 * WORD,
        r.r23:  MY_COPY_OF_REGS + 22 * WORD,
        r.r24:  MY_COPY_OF_REGS + 23 * WORD,
        r.r25:  MY_COPY_OF_REGS + 24 * WORD,
        r.r26:  MY_COPY_OF_REGS + 25 * WORD,
        r.r27:  MY_COPY_OF_REGS + 26 * WORD,
        r.r28:  MY_COPY_OF_REGS + 27 * WORD,
        r.r29:  MY_COPY_OF_REGS + 28 * WORD,
        r.r30:  MY_COPY_OF_REGS + 29 * WORD,
        r.r31:  MY_COPY_OF_REGS + 30 * WORD,
    }

    def __init__(self, longevity, frame_manager=None, assembler=None):
        RegisterManager.__init__(self, longevity, frame_manager, assembler)

    def call_result_location(self, v):
        return r.r3

    def convert_to_imm(self, c):
        if isinstance(c, ConstInt):
            val = rffi.cast(lltype.Signed, c.value)
            return locations.ImmLocation(val)
        else:
            assert isinstance(c, ConstPtr)
            return locations.ImmLocation(rffi.cast(lltype.Signed, c.value))

    def allocate_scratch_reg(self, type=INT, selected_reg=None, forbidden_vars=None):
        """Allocate a scratch register, possibly spilling a managed register.
        This register is freed after emitting the current operation and can not
        be spilled"""
        box = TempBox()
        reg = self.force_allocate_reg(box,
                            selected_reg=selected_reg,
                            forbidden_vars=forbidden_vars)
        return reg, box

class PPCFrameManager(FrameManager):
    def __init__(self):
        FrameManager.__init__(self)
        self.used = []

    @staticmethod
    def frame_pos(loc, type):
        num_words = PPCFrameManager.frame_size(type)
        if type == FLOAT:
            assert 0, "not implemented yet"
        return locations.StackLocation(loc, num_words=num_words, type=type)

    @staticmethod
    def frame_size(type):
        if type == FLOAT:
            assert 0, "TODO"
        return 1

    @staticmethod
    def get_loc_index(loc):
        assert loc.is_stack()
        if loc.type == FLOAT:
            assert 0, "not implemented yet"
        return loc.position

class Regalloc(object):

    def __init__(self, frame_manager=None, assembler=None):
        self.cpu = assembler.cpu
        self.frame_manager = frame_manager
        self.assembler = assembler
        self.jump_target_descr = None
        self.final_jump_op = None

    def _prepare(self,  inputargs, operations):
        longevity, last_real_usage = compute_vars_longevity(
                                                    inputargs, operations)
        self.longevity = longevity
        self.last_real_usage = last_real_usage
        fm = self.frame_manager
        asm = self.assembler
        self.rm = PPCRegisterManager(longevity, fm, asm)

    def prepare_loop(self, inputargs, operations):
        self._prepare(inputargs, operations)
        self._set_initial_bindings(inputargs)
        self.possibly_free_vars(list(inputargs))

    def prepare_bridge(self, inputargs, arglocs, ops):
        self._prepare(inputargs, ops)
        self._update_bindings(arglocs, inputargs)

    def _set_initial_bindings(self, inputargs):
        arg_index = 0
        count = 0
        n_register_args = len(r.PARAM_REGS)
        cur_frame_pos = -self.assembler.OFFSET_STACK_ARGS // WORD + 1
        for box in inputargs:
            assert isinstance(box, Box)
            # handle inputargs in argument registers
            if box.type == FLOAT and arg_index % 2 != 0:
                assert 0, "not implemented yet"
            if arg_index < n_register_args:
                if box.type == FLOAT:
                    assert 0, "not implemented yet"
                else:
                    loc = r.PARAM_REGS[arg_index]
                    self.try_allocate_reg(box, selected_reg=loc)
                    arg_index += 1
            else:
                # treat stack args as stack locations with a negative offset
                if box.type == FLOAT:
                    assert 0, "not implemented yet"
                else:
                    cur_frame_pos -= 1
                    count += 1
                loc = self.frame_manager.frame_pos(cur_frame_pos, box.type)
                self.frame_manager.set_binding(box, loc)

    def _update_bindings(self, locs, inputargs):
        used = {}
        i = 0
        for loc in locs:
            arg = inputargs[i]
            i += 1
            if loc.is_reg():
                self.rm.reg_bindings[arg] = loc
            elif loc.is_vfp_reg():
                assert 0, "not supported"
            else:
                assert loc.is_stack()
                self.frame_manager.set_binding(arg, loc)
            used[loc] = None

        # XXX combine with x86 code and move to llsupport
        self.rm.free_regs = []
        for reg in self.rm.all_regs:
            if reg not in used:
                self.rm.free_regs.append(reg)
        # note: we need to make a copy of inputargs because possibly_free_vars
        # is also used on op args, which is a non-resizable list
        self.possibly_free_vars(list(inputargs))

    def possibly_free_var(self, var):
        self.rm.possibly_free_var(var)

    def possibly_free_vars(self, vars):
        for var in vars:
            self.possibly_free_var(var)

    def possibly_free_vars_for_op(self, op):
        for i in range(op.numargs()):
            var = op.getarg(i)
            if var is not None:
                self.possibly_free_var(var)

    def try_allocate_reg(self, v, selected_reg=None, need_lower_byte=False):
        return self.rm.try_allocate_reg(v, selected_reg, need_lower_byte)

    def force_allocate_reg(self, var, forbidden_vars=[], selected_reg=None, 
            need_lower_byte=False):
        return self.rm.force_allocate_reg(var, forbidden_vars, selected_reg,
                need_lower_byte)

    def allocate_scratch_reg(self, type=INT, forbidden_vars=[], selected_reg=None):
        assert type == INT # XXX extend this once floats are supported
        return self.rm.allocate_scratch_reg(type=type,
                        forbidden_vars=forbidden_vars,
                        selected_reg=selected_reg)

    def _check_invariants(self):
        self.rm._check_invariants()

    def loc(self, var):
        if var.type == FLOAT:
            assert 0, "not implemented yet"
        return self.rm.loc(var)

    def position(self):
        return self.rm.position

    def next_instruction(self):
        self.rm.next_instruction()

    def force_spill_var(self, var):
        if var.type == FLOAT:
            assert 0, "not implemented yet"
        else:
            self.rm.force_spill_var(var)

    def before_call(self, force_store=[], save_all_regs=False):
        self.rm.before_call(force_store, save_all_regs)

    def after_call(self, v):
        if v.type == FLOAT:
            assert 0, "not implemented yet"
        else:
            return self.rm.after_call(v)

    def call_result_location(self, v):
        if v.type == FLOAT:
            assert 0, "not implemented yet"
        else:
            return self.rm.call_result_location(v)

    def _ensure_value_is_boxed(self, thing, forbidden_vars=[]):
        box = None
        loc = None
        if isinstance(thing, Const):
            if isinstance(thing, ConstPtr):
                box = TempPtr()
            else:
                box = TempInt()
            loc = self.force_allocate_reg(box, forbidden_vars=forbidden_vars)
            imm = self.rm.convert_to_imm(thing)
            self.assembler.mc.load_imm(loc, imm.value)
        else:
            loc = self.make_sure_var_in_reg(thing,
                    forbidden_vars=forbidden_vars)
            box = thing
        return loc, box

    def make_sure_var_in_reg(self, var, forbidden_vars=[],
                             selected_reg=None, need_lower_byte=False):
        return self.rm.make_sure_var_in_reg(var, forbidden_vars,
                selected_reg, need_lower_byte)

    def _sync_var(self, v):
        if v.type == FLOAT:
            assert 0, "not implemented yet"
        else:
            self.rm._sync_var(v)

    # ******************************************************
    # *         P R E P A R E  O P E R A T I O N S         * 
    # ******************************************************


    def void(self, op):
        return []

    prepare_int_add = prepare_binary_int_op_with_imm()
    prepare_int_sub = prepare_binary_int_op_with_imm()
    prepare_int_floordiv = prepare_binary_int_op_with_imm()

    prepare_int_mul = prepare_binary_int_op()
    prepare_int_mod = prepare_binary_int_op()
    prepare_int_and = prepare_binary_int_op()
    prepare_int_or = prepare_binary_int_op()
    prepare_int_xor = prepare_binary_int_op()
    prepare_int_lshift = prepare_binary_int_op()
    prepare_int_rshift = prepare_binary_int_op()
    prepare_uint_rshift = prepare_binary_int_op()
    prepare_uint_floordiv = prepare_binary_int_op()

    prepare_int_add_ovf = prepare_binary_int_op()
    prepare_int_sub_ovf = prepare_binary_int_op()
    prepare_int_mul_ovf = prepare_binary_int_op()

    prepare_int_neg = prepare_unary_int_op()
    prepare_int_invert = prepare_unary_int_op()

    prepare_int_le = prepare_cmp_op()
    prepare_int_lt = prepare_cmp_op()
    prepare_int_ge = prepare_cmp_op()
    prepare_int_gt = prepare_cmp_op()
    prepare_int_eq = prepare_cmp_op()
    prepare_int_ne = prepare_cmp_op()

    prepare_ptr_eq = prepare_int_eq
    prepare_ptr_ne = prepare_int_ne

    prepare_instance_ptr_eq = prepare_ptr_eq
    prepare_instance_ptr_ne = prepare_ptr_ne

    prepare_uint_lt = prepare_cmp_op()
    prepare_uint_le = prepare_cmp_op()
    prepare_uint_gt = prepare_cmp_op()
    prepare_uint_ge = prepare_cmp_op()

    prepare_int_is_true = prepare_unary_cmp()
    prepare_int_is_zero = prepare_unary_cmp()

    def prepare_finish(self, op):
        args = [None] * (op.numargs() + 1)
        for i in range(op.numargs()):
            arg = op.getarg(i)
            if arg:
                args[i] = self.loc(arg)
                self.possibly_free_var(arg)
        n = self.cpu.get_fail_descr_number(op.getdescr())
        args[-1] = imm(n)
        return args

    def prepare_call_malloc_gc(self, op):
        args = [imm(rffi.cast(lltype.Signed, op.getarg(0).getint()))]
        return args

    def _prepare_guard(self, op, args=None):
        if args is None:
            args = []
        args.append(imm(len(self.frame_manager.used)))
        for arg in op.getfailargs():
            if arg:
                args.append(self.loc(arg))
            else:
                args.append(None)
        return args
    
    def prepare_guard_true(self, op):
        l0, box = self._ensure_value_is_boxed(op.getarg(0))
        args = self._prepare_guard(op, [l0])
        self.possibly_free_var(box)
        self.possibly_free_vars(op.getfailargs())
        return args

    prepare_guard_false = prepare_guard_true
    prepare_guard_nonnull = prepare_guard_true
    prepare_guard_isnull = prepare_guard_true

    def prepare_guard_no_overflow(self, op):
        locs = self._prepare_guard(op)
        self.possibly_free_vars(op.getfailargs())
        return locs

    prepare_guard_overflow = prepare_guard_no_overflow
    prepare_guard_not_invalidated = prepare_guard_no_overflow

    def prepare_guard_exception(self, op):
        boxes = list(op.getarglist())
        arg0 = ConstInt(rffi.cast(lltype.Signed, op.getarg(0).getint()))
        loc, box = self._ensure_value_is_boxed(arg0)
        boxes.append(box)
        box = TempInt()
        loc1 = self.force_allocate_reg(box, boxes)
        boxes.append(box)
        if op.result in self.longevity:
            resloc = self.force_allocate_reg(op.result, boxes)
            boxes.append(op.result)
        else:
            resloc = None
        pos_exc_value = imm(self.cpu.pos_exc_value())
        pos_exception = imm(self.cpu.pos_exception())
        arglocs = self._prepare_guard(op, [loc, loc1, resloc, pos_exc_value, pos_exception])
        self.possibly_free_vars(boxes)
        self.possibly_free_vars(op.getfailargs())
        return arglocs

    def prepare_guard_no_exception(self, op):
        loc, box = self._ensure_value_is_boxed(
                    ConstInt(self.cpu.pos_exception()))
        arglocs = self._prepare_guard(op, [loc])
        self.possibly_free_var(box)
        self.possibly_free_vars(op.getfailargs())
        return arglocs

    def prepare_guard_value(self, op):
        boxes = list(op.getarglist())
        b0, b1 = boxes
        imm_b1 = _check_imm_arg(b1)
        l0, box = self._ensure_value_is_boxed(b0, boxes)
        boxes.append(box)
        if not imm_b1:
            l1, box = self._ensure_value_is_boxed(b1,boxes)
            boxes.append(box)
        else:
            l1 = self.make_sure_var_in_reg(b1)
        assert op.result is None
        arglocs = self._prepare_guard(op, [l0, l1])
        self.possibly_free_vars(boxes)
        self.possibly_free_vars(op.getfailargs())
        return arglocs

    def prepare_guard_class(self, op):
        assert isinstance(op.getarg(0), Box)
        boxes = list(op.getarglist())

        x, x_box = self._ensure_value_is_boxed(boxes[0], boxes)
        boxes.append(x_box)

        t = TempInt()
        y = self.force_allocate_reg(t, boxes)
        boxes.append(t)
        y_val = rffi.cast(lltype.Signed, op.getarg(1).getint())
        self.assembler.mc.load_imm(y, y_val)

        offset = self.cpu.vtable_offset
        assert offset is not None
        offset_loc, offset_box = self._ensure_value_is_boxed(ConstInt(offset), boxes)
        boxes.append(offset_box)
        arglocs = self._prepare_guard(op, [x, y, offset_loc])
        self.possibly_free_vars(boxes)
        self.possibly_free_vars(op.getfailargs())
        return arglocs

    prepare_guard_nonnull_class = prepare_guard_class

    def compute_hint_frame_locations(self, operations):
        # optimization only: fill in the 'hint_frame_locations' dictionary
        # of rm and xrm based on the JUMP at the end of the loop, by looking
        # at where we would like the boxes to be after the jump.
        op = operations[-1]
        if op.getopnum() != rop.JUMP:
            return
        self.final_jump_op = op
        descr = op.getdescr()
        assert isinstance(descr, TargetToken)
        if descr._ppc_loop_code != 0:
            # if the target LABEL was already compiled, i.e. if it belongs
            # to some already-compiled piece of code
            self._compute_hint_frame_locations_from_descr(descr)
        #else:
        #   The loop ends in a JUMP going back to a LABEL in the same loop.
        #   We cannot fill 'hint_frame_locations' immediately, but we can
        #   wait until the corresponding prepare_op_label() to know where the
        #   we would like the boxes to be after the jump.

    def _compute_hint_frame_locations_from_descr(self, descr):
        arglocs = self.assembler.target_arglocs(descr)
        jump_op = self.final_jump_op
        assert len(arglocs) == jump_op.numargs()
        for i in range(jump_op.numargs()):
            box = jump_op.getarg(i)
            if isinstance(box, Box):
                loc = arglocs[i]
                if loc is not None and loc.is_stack():
                    self.frame_manager.hint_frame_locations[box] = loc

    def prepare_op_jump(self, op):
        descr = op.getdescr()
        assert isinstance(descr, TargetToken)
        self.jump_target_descr = descr
        arglocs = self.assembler.target_arglocs(descr)

        # get temporary locs
        tmploc = r.SCRATCH

        # Part about non-floats
        src_locations1 = []
        dst_locations1 = []

        # Build the two lists
        for i in range(op.numargs()):
            box = op.getarg(i)
            src_loc = self.loc(box)
            dst_loc = arglocs[i]
            if box.type != FLOAT:
                src_locations1.append(src_loc)
                dst_locations1.append(dst_loc)
            else:
                assert 0, "not implemented yet"

        remap_frame_layout(self.assembler, src_locations1, 
            dst_locations1, tmploc)
        return []

    def prepare_guard_call_release_gil(self, op, guard_op):
        # first, close the stack in the sense of the asmgcc GC root tracker
        gcrootmap = self.cpu.gc_ll_descr.gcrootmap
        if gcrootmap:
            arglocs = []
            argboxes = []
            for i in range(op.numargs()):
                loc, box = self._ensure_value_is_boxed(op.getarg(i), argboxes)
                arglocs.append(loc)
                argboxes.append(box)
            self.assembler.call_release_gil(gcrootmap, arglocs, fcond)
            self.possibly_free_vars(argboxes)
        # do the call
        faildescr = guard_op.getdescr()
        fail_index = self.cpu.get_fail_descr_number(faildescr)
        self.assembler._write_fail_index(fail_index)
        args = [imm(rffi.cast(lltype.Signed, op.getarg(0).getint()))]
        self.assembler.emit_call(op, args, self, fail_index)
        # then reopen the stack
        if gcrootmap:
            self.assembler.call_reacquire_gil(gcrootmap, r.r0, fcond)
        locs = self._prepare_guard(guard_op)
        self.possibly_free_vars(guard_op.getfailargs())
        return locs

    def prepare_jump(self, op):
        descr = op.getdescr()
        assert isinstance(descr, TargetToken)
        self.jump_target_descr = descr
        arglocs = self.assembler.target_arglocs(descr)

        # get temporary locs
        tmploc = r.SCRATCH

        # Part about non-floats
        src_locations1 = []
        dst_locations1 = []

        # Build the four lists
        for i in range(op.numargs()):
            box = op.getarg(i)
            src_loc = self.loc(box)
            dst_loc = arglocs[i]
            if box.type != FLOAT:
                src_locations1.append(src_loc)
                dst_locations1.append(dst_loc)
            else:
                assert 0, "not implemented yet"

        remap_frame_layout(self.assembler, src_locations1,
                dst_locations1, tmploc)
        return []

    def prepare_setfield_gc(self, op):
        boxes = list(op.getarglist())
        b0, b1 = boxes
        ofs, size, ptr = unpack_fielddescr(op.getdescr())
        base_loc, base_box = self._ensure_value_is_boxed(b0, boxes)
        boxes.append(base_box)
        value_loc, value_box = self._ensure_value_is_boxed(b1, boxes)
        boxes.append(value_box)
        c_ofs = ConstInt(ofs)
        if _check_imm_arg(c_ofs):
            ofs_loc = imm(ofs)
        else:
            ofs_loc, ofs_box = self._ensure_value_is_boxed(c_ofs, boxes)
            boxes.append(ofs_box)
        self.possibly_free_vars(boxes)
        return [value_loc, base_loc, ofs_loc, imm(size)]

    prepare_setfield_raw = prepare_setfield_gc

    def prepare_getfield_gc(self, op):
        a0 = op.getarg(0)
        ofs, size, ptr = unpack_fielddescr(op.getdescr())
        base_loc, base_box = self._ensure_value_is_boxed(a0)
        c_ofs = ConstInt(ofs)
        if _check_imm_arg(c_ofs):
            ofs_loc = imm(ofs)
        else:
            ofs_loc, ofs_box = self._ensure_value_is_boxed(c_ofs, [base_box])
            self.possibly_free_var(ofs_box)
        self.possibly_free_var(a0)
        self.possibly_free_var(base_box)
        res = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)
        return [base_loc, ofs_loc, res, imm(size)]

    prepare_getfield_raw = prepare_getfield_gc
    prepare_getfield_raw_pure = prepare_getfield_gc
    prepare_getfield_gc_pure = prepare_getfield_gc

    def prepare_arraylen_gc(self, op):
        arraydescr = op.getdescr()
        assert isinstance(arraydescr, ArrayDescr)
        ofs = arraydescr.lendescr.offset
        arg = op.getarg(0)
        base_loc, base_box = self._ensure_value_is_boxed(arg)
        self.possibly_free_vars([arg, base_box])

        res = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)
        return [res, base_loc, imm(ofs)]

    def prepare_setarrayitem_gc(self, op):
        a0, a1, a2 = list(op.getarglist())
        size, ofs, _ = unpack_arraydescr(op.getdescr())
        scale = get_scale(size)
        args = op.getarglist()
        base_loc, _ = self._ensure_value_is_boxed(a0, args)
        ofs_loc, _ = self._ensure_value_is_boxed(a1, args)
        value_loc, _ = self._ensure_value_is_boxed(a2, args)
        assert _check_imm_arg(ofs)
        return [value_loc, base_loc, ofs_loc, imm(scale), imm(ofs)]

    prepare_setarrayitem_raw = prepare_setarrayitem_gc

    def prepare_getarrayitem_gc(self, op):
        a0, a1 = boxes = list(op.getarglist())
        size, ofs, _ = unpack_arraydescr(op.getdescr())
        scale = get_scale(size)
        base_loc, base_box  = self._ensure_value_is_boxed(a0, boxes)
        boxes.append(base_box)
        ofs_loc, ofs_box = self._ensure_value_is_boxed(a1, boxes)
        boxes.append(ofs_box)
        self.possibly_free_vars(boxes)
        res = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)
        assert _check_imm_arg(ofs)
        return [res, base_loc, ofs_loc, imm(scale), imm(ofs)]

    prepare_getarrayitem_raw = prepare_getarrayitem_gc
    prepare_getarrayitem_gc_pure = prepare_getarrayitem_gc

    def prepare_strlen(self, op):
        l0, box = self._ensure_value_is_boxed(op.getarg(0))
        boxes = [box]

        basesize, itemsize, ofs_length = symbolic.get_array_token(rstr.STR,
                                         self.cpu.translate_support_code)
        ofs_box = ConstInt(ofs_length)
        imm_ofs = _check_imm_arg(ofs_box)

        if imm_ofs:
            l1 = self.make_sure_var_in_reg(ofs_box, boxes)
        else:
            l1, box1 = self._ensure_value_is_boxed(ofs_box, boxes)
            boxes.append(box1)

        self.possibly_free_vars(boxes)
        res = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)
        return [l0, l1, res]

    def prepare_strgetitem(self, op):
        boxes = list(op.getarglist())
        base_loc, box = self._ensure_value_is_boxed(boxes[0])
        boxes.append(box)

        a1 = boxes[1]
        imm_a1 = _check_imm_arg(a1)
        if imm_a1:
            ofs_loc = self.make_sure_var_in_reg(a1, boxes)
        else:
            ofs_loc, box = self._ensure_value_is_boxed(a1, boxes)
            boxes.append(box)

        self.possibly_free_vars(boxes)
        res = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)

        basesize, itemsize, ofs_length = symbolic.get_array_token(rstr.STR,
                                         self.cpu.translate_support_code)
        assert itemsize == 1
        return [res, base_loc, ofs_loc, imm(basesize)]

    def prepare_strsetitem(self, op):
        boxes = list(op.getarglist())

        base_loc, box = self._ensure_value_is_boxed(boxes[0], boxes)
        boxes.append(box)

        ofs_loc, box = self._ensure_value_is_boxed(boxes[1], boxes)
        boxes.append(box)

        value_loc, box = self._ensure_value_is_boxed(boxes[2], boxes)
        boxes.append(box)

        self.possibly_free_vars(boxes)

        basesize, itemsize, ofs_length = symbolic.get_array_token(rstr.STR,
                                         self.cpu.translate_support_code)
        assert itemsize == 1
        return [value_loc, base_loc, ofs_loc, imm(basesize)]

    prepare_copystrcontent = void
    prepare_copyunicodecontent = void

    def prepare_unicodelen(self, op):
        l0, box = self._ensure_value_is_boxed(op.getarg(0))
        boxes = [box]
        basesize, itemsize, ofs_length = symbolic.get_array_token(rstr.UNICODE,
                                         self.cpu.translate_support_code)
        ofs_box = ConstInt(ofs_length)
        imm_ofs = _check_imm_arg(ofs_box)

        if imm_ofs:
            l1 = imm(ofs_length)
        else:
            l1, box1 = self._ensure_value_is_boxed(ofs_box, boxes)
            boxes.append(box1)

        self.possibly_free_vars(boxes)
        res = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)
        return [l0, l1, res]

    def prepare_unicodegetitem(self, op):
        boxes = list(op.getarglist())
        base_loc, box = self._ensure_value_is_boxed(boxes[0], boxes)
        boxes.append(box)
        ofs_loc, box = self._ensure_value_is_boxed(boxes[1], boxes)
        boxes.append(box)
        self.possibly_free_vars(boxes)

        res = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)

        basesize, itemsize, ofs_length = symbolic.get_array_token(rstr.UNICODE,
                                         self.cpu.translate_support_code)
        scale = itemsize/2
        return [res, base_loc, ofs_loc, imm(scale), imm(basesize), imm(itemsize)]

    def prepare_unicodesetitem(self, op):
        boxes = list(op.getarglist())
        base_loc, box = self._ensure_value_is_boxed(boxes[0], boxes)
        boxes.append(box)
        ofs_loc, box = self._ensure_value_is_boxed(boxes[1], boxes)
        boxes.append(box)
        value_loc, box = self._ensure_value_is_boxed(boxes[2], boxes)
        boxes.append(box)

        self.possibly_free_vars(boxes)

        basesize, itemsize, ofs_length = symbolic.get_array_token(rstr.UNICODE,
                                         self.cpu.translate_support_code)
        scale = itemsize/2
        return [value_loc, base_loc, ofs_loc, imm(scale), imm(basesize), imm(itemsize)]

    def prepare_same_as(self, op):
        arg = op.getarg(0)
        imm_arg = _check_imm_arg(arg)
        if imm_arg:
            argloc = self.make_sure_var_in_reg(arg)
        else:
            argloc, box = self._ensure_value_is_boxed(arg)
            self.possibly_free_var(box)

        resloc = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)
        return [argloc, resloc]

    prepare_cast_ptr_to_int = prepare_same_as
    prepare_cast_int_to_ptr = prepare_same_as

    def prepare_call(self, op):
        effectinfo = op.getdescr().get_extra_info()
        if effectinfo is not None:
            oopspecindex = effectinfo.oopspecindex
            if oopspecindex == EffectInfo.OS_MATH_SQRT:
                args = self.prepare_op_math_sqrt(op, fcond)
                self.assembler.emit_op_math_sqrt(op, args, self, fcond)
                return
        args = [imm(rffi.cast(lltype.Signed, op.getarg(0).getint()))]
        return args

    prepare_debug_merge_point = void
    prepare_jit_debug = void

    def prepare_cond_call_gc_wb(self, op):
        assert op.result is None
        N = op.numargs()
        # we force all arguments in a reg (unless they are Consts),
        # because it will be needed anyway by the following setfield_gc
        # or setarrayitem_gc. It avoids loading it twice from the memory.
        arglocs = []
        argboxes = []
        for i in range(N):
            loc, box = self._ensure_value_is_boxed(op.getarg(i), argboxes)
            arglocs.append(loc)
            argboxes.append(box)
        self.rm.possibly_free_vars(argboxes)
        return arglocs

    prepare_cond_call_gc_wb_array = prepare_cond_call_gc_wb

    def prepare_force_token(self, op):
        res_loc = self.force_allocate_reg(op.result)
        self.possibly_free_var(op.result)
        return [res_loc]

    def prepare_label(self, op):
        # XXX big refactoring needed?
        descr = op.getdescr()
        assert isinstance(descr, TargetToken)
        inputargs = op.getarglist()
        arglocs = [None] * len(inputargs)
        #
        # we use force_spill() on the boxes that are not going to be really
        # used any more in the loop, but that are kept alive anyway
        # by being in a next LABEL's or a JUMP's argument or fail_args
        # of some guard
        position = self.rm.position
        for arg in inputargs:
            assert isinstance(arg, Box)
            if self.last_real_usage.get(arg, -1) <= position:
                self.force_spill_var(arg)

        #
        for i in range(len(inputargs)):
            arg = inputargs[i]
            assert isinstance(arg, Box)
            loc = self.loc(arg)
            arglocs[i] = loc
            if loc.is_reg():
                self.frame_manager.mark_as_free(arg)
        #
        descr._ppc_arglocs = arglocs
        descr._ppc_loop_code = self.assembler.mc.currpos()
        descr._ppc_clt = self.assembler.current_clt
        self.assembler.target_tokens_currently_compiling[descr] = None
        self.possibly_free_vars_for_op(op)
        #
        # if the LABEL's descr is precisely the target of the JUMP at the
        # end of the same loop, i.e. if what we are compiling is a single
        # loop that ends up jumping to this LABEL, then we can now provide
        # the hints about the expected position of the spilled variables.
        jump_op = self.final_jump_op
        if jump_op is not None and jump_op.getdescr() is descr:
            self._compute_hint_frame_locations_from_descr(descr)

    def prepare_guard_call_may_force(self, op, guard_op):
        faildescr = guard_op.getdescr()
        fail_index = self.cpu.get_fail_descr_number(faildescr)
        self.assembler._write_fail_index(fail_index)
        args = [imm(rffi.cast(lltype.Signed, op.getarg(0).getint()))]
        for v in guard_op.getfailargs():
            if v in self.rm.reg_bindings:
                self.force_spill_var(v)
        self.assembler.emit_call(op, args, self, fail_index)
        locs = self._prepare_guard(guard_op)
        self.possibly_free_vars(guard_op.getfailargs())
        return locs

    def prepare_guard_call_assembler(self, op, guard_op):
        descr = op.getdescr()
        assert isinstance(descr, JitCellToken)
        jd = descr.outermost_jitdriver_sd
        assert jd is not None
        #size = jd.portal_calldescr.get_result_size(self.cpu.translate_support_code)
        size = jd.portal_calldescr.get_result_size()
        vable_index = jd.index_of_virtualizable
        if vable_index >= 0:
            self._sync_var(op.getarg(vable_index))
            vable = self.frame_manager.loc(op.getarg(vable_index))
        else:
            vable = imm(0)
        self.possibly_free_vars(guard_op.getfailargs())
        return [imm(size), vable]

    def _prepare_args_for_new_op(self, new_args):
        gc_ll_descr = self.cpu.gc_ll_descr
        args = gc_ll_descr.args_for_new(new_args)
        arglocs = []
        for i in range(len(args)):
            arg = args[i]
            t = TempInt()
            l = self.force_allocate_reg(t, selected_reg=r.MANAGED_REGS[i])
            self.assembler.load(l, imm(arg))
            arglocs.append(t)
        return arglocs

    def _malloc_varsize(self, ofs_items, ofs_length, itemsize, op):
        v = op.getarg(0)
        res_v = op.result
        boxes = [v, res_v]
        itemsize_box = ConstInt(itemsize)
        ofs_items_box = ConstInt(ofs_items)
        if _check_imm_arg(ofs_items_box):
            ofs_items_loc = self.convert_to_imm(ofs_items_box)
        else:
            ofs_items_loc, ofs_items_box = self._ensure_value_is_boxed(ofs_items_box, boxes)
            boxes.append(ofs_items_box)
        vloc, vbox = self._ensure_value_is_boxed(v, [res_v])
        boxes.append(vbox)
        size, size_box = self._ensure_value_is_boxed(itemsize_box, boxes)
        boxes.append(size_box)
        self.assembler._regalloc_malloc_varsize(size, size_box,
                                vloc, vbox, ofs_items_loc, self, res_v)
        base_loc = self.make_sure_var_in_reg(res_v)

        value_loc, vbox = self._ensure_value_is_boxed(v, [res_v])
        boxes.append(vbox)
        self.possibly_free_vars(boxes)
        assert value_loc.is_reg()
        assert base_loc.is_reg()
        return [value_loc, base_loc, imm(ofs_length)]

    # from ../x86/regalloc.py:791
    def _unpack_fielddescr(self, fielddescr):
        assert isinstance(fielddescr, BaseFieldDescr)
        ofs = fielddescr.offset
        size = fielddescr.get_field_size(self.cpu.translate_support_code)
        ptr = fielddescr.is_pointer_field()
        return ofs, size, ptr

    # from ../x86/regalloc.py:779
    def _unpack_arraydescr(self, arraydescr):
        assert isinstance(arraydescr, BaseArrayDescr)
        cpu = self.cpu
        ofs_length = arraydescr.get_ofs_length(cpu.translate_support_code)
        ofs = arraydescr.get_base_size(cpu.translate_support_code)
        size = arraydescr.get_item_size(cpu.translate_support_code)
        ptr = arraydescr.is_array_of_pointers()
        scale = 0
        while (1 << scale) < size:
            scale += 1
        assert (1 << scale) == size
        return size, scale, ofs, ofs_length, ptr

    def prepare_force_spill(self, op):
        self.force_spill_var(op.getarg(0))
        return []

def add_none_argument(fn):
    return lambda self, op: fn(self, op, None)

def notimplemented(self, op):
    raise NotImplementedError, op

def notimplemented_with_guard(self, op, guard_op):

    raise NotImplementedError, op

operations = [notimplemented] * (rop._LAST + 1)
operations_with_guard = [notimplemented_with_guard] * (rop._LAST + 1)

def get_scale(size):
    scale = 0
    while (1 << scale) < size:
        scale += 1
    assert (1 << scale) == size
    return scale

for key, value in rop.__dict__.items():
    key = key.lower()
    if key.startswith('_'):
        continue
    methname = 'prepare_%s' % key
    if hasattr(Regalloc, methname):
        func = getattr(Regalloc, methname).im_func
        operations[value] = func

for key, value in rop.__dict__.items():
    key = key.lower()
    if key.startswith('_'):
        continue
    methname = 'prepare_guard_%s' % key
    if hasattr(Regalloc, methname):
        func = getattr(Regalloc, methname).im_func
        operations_with_guard[value] = func
        operations[value] = add_none_argument(func)

Regalloc.operations = operations
Regalloc.operations_with_guard = operations_with_guard