-
Notifications
You must be signed in to change notification settings - Fork 14
/
oexpl-run-data-structures.html
897 lines (640 loc) · 48.5 KB
/
oexpl-run-data-structures.html
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
<!Doctype html>
<html lang="en">
<head>
<title>OExpL Runtime Data Structures</title>
<meta charset="UTF-8">
<!--<link rel="stylesheet" href="css/bootstrap.min.css">-->
<link rel="stylesheet" href="css/style_new.css">
<link rel="stylesheet" href="js/embed-2cd369fa1c0830bd3aa06c21d4f14a13e060d2d31bbaae740f4af4.css"><div id="gist28627206" class="gist">
<link rel="stylesheet" href="js/embed-cbe5b40fa72b0964f90d4919c2da8f8f94d7c9f6c2aa49c07f6fa3.css"><div id="gist28627206" class="gist">
<script src="js/jquery-1.12.1.min.js" charset="utf-8"></script>
<script src="js/bootstrap.min.js" charset="utf-8"></script>
<script src="js/sticky_sidebar.js" charset="utf-8"></script>
</head>
<div class="container">
<header id="navtop">
<a href="index.html" class="logo fleft"><img src="img/logo.png" alt=""></a>
<nav class="fright">
<ul>
<li><a href="index.html">Home</a></li>
<li><a href="about.html">About</a></li>
<!-- <li><a href="help.html">Help</a></li> -->
<li><a href="roadmap.html">Roadmap</a></li>
<li><a href="documentation.html" class="navactive">Documentation</a></li>
</ul>
</nav>
</header>
<body>
<div class="Services-page main grid-wrap">
<header class="grid col-full">
<hr/>
<p class="fleft">Runtime Data Structures for OExpL</p>
<br>
<br>
</header>
<aside class="grid col-one-quarter mq2-col-full sticky_sidebar">
<menu>
<ul>
<li><a class="sec" href="#nav-virtual-function-table">Virtual Function Table</a></li>
<li><a class="sec" href="#nav-illustration">Illustration</a></li>
<li><a class="sec" href="#nav-runtimebinding">Run Time Binding</a></li>
<li><a class="sec" href="#nav-methodinvocations">Method Invocations</a></li>
<li><a class="sec" href="#nav-runtimestackmanagementformethodinvocations">Run time Stack Management for Method invocations</a></li>
<!-- <li><a class="sec" href="#nav-resolvestrategy">Resolving Strategy</a></li>-->
<!-- <li><a class="sec" href="#nav-resolve">Resolving Strategy using Virtual Function Table</a></li> -->
</ul>
</menu>
<!-- <a class="button" href="">Download as PDF</a> -->
</aside>
<section class="grid col-three-quarters mq2-col-full">
<div class="grid-wrap">
<article class="grid col-full" id="nav-virtual-function-table">
<h2>Virtual Function Table</h2>
<p>
<b>Virtual Function Table</b> is a run time data structure that is used to resolve at run time the
call addresses of methods in a class. Such mechanism (or other table schemes) needs to be
implemented by compilers for languages that support <a href="https://en.wikipedia.org/wiki/Inheritance_(object-oriented_programming)">
inheritance</a>, <a href="https://en.wikipedia.org/wiki/Subtyping">subtype Polymorphism</a> and <a href="https://en.wikipedia.org/wiki/Method_overriding">method over-riding</a>.
A run time virtual function table is maintained in the memory for each class. <b>The compiler generates code
to initialize the table for each class such that each function that can be invoked from the class has an entry
in the table</b>. For each function defined or inherited by a class, the table will contain the call address of
the function in the code region of memory. <b>If a function is inherited by a class from its parent and is
not over-ridden by the class, the call address stored
will be that of the function defined in the parent class</b>. The
same address will be stored for the function in the virtual function table of the parent class as well.
</p>
<p>
The OExpL compiler maintains a virtual function table of eight words for each class. Hence, a class can have at most eight
member functions. The i-th entry in the table holds the address of the i-th function of the class (identified by the
field <b>Funcposition</b> in the <a href="http://silcnitc.github.io/oexpl-data-structures.html">class table</a> - see Memberfunclist).
While generating code, <b>if there is a call to a function within a class, the compiler simply translates the call to "CALL [address]",
where address is obtained from the corresponding virtual function table</b>.
</p>
<p>
A simple way to place the virtual function table is to use the initial part of the stack region (starting at memory
address 4096), ahead of global variables. This is suggested because the compilation of classes will be
finished before compiling the global declarations. In this scheme, the virtual function table of the class defined
first in the program will be stored in the region 4096-4103, the second in 4104-4111 and so on.
</p>
<p>
When the compiler encounters the declaration of a variable of a class, it allocates <b>two words of storage</b> for the variable
(unlike other variables, where only one word of storage is allocated).
The first word is used to store the address of the memory area allocated in the heap for the class (eight words).
Space for member fields is allocated in the heap exactly as done with user defined types.
We will call this word the <b>member field pointer</b>. <b>The second word is used to store the address of virtual function table</b>.
We will call this word the <b>virtual function table pointer</b>.
</p>
<p>
<b> The key point to note here is that the virtual function pointer of a variable need not always point to the virtual function table of the class of the variable. This is because a variable of a parent class can hold a reference to an object of any of its descendant classes. In such cases, the virtual function pointer will hold the address of the descendant class.
</b>
</p>
<p>
Hence, an assignment of a variable (of one class) to another variable (of the same class or an ancestor class) results in transfer of
the contents of both the pointers of one variable to the corresponding pointers of the other.
The <i>new</i> function sets the virtual function table pointer to the address of the virtual function table of the class specified as the argument to the new function.
A little bit of thought is necessary to reveal that this implementation will yield the correct execution semantics.
</p>
<p> A detailed illustration follows.</p>
</article>
<article class="grid col-full" id="nav-illustration">
<h2>Illustration</h2>
<script src="../js/4a47b79cec2699771df391ecd0574153.js"></script>
<br>
<ol>
<li>
<p>
Storage for virtual function tables start at 4096 in the stack. Eight consecutive words are allocated for storing the virtual function table of each class. Each word of virtual function table stores the call address of the corresponding function in the class. Thus, a class can contain atmost eight methods. Virtual function tables of various classes are stored in the order in which the classes are declared in the program. As noted earlier, we will allocate the space for global declarations after virtual function tables are allocated.
</p>
<p>
By using the <i>Class_index</i> field of the <a href="http://silcnitc.github.io/oexpl-data-structures.html">class_table</a> entry, the starting address of the virtual function table for that particular class can be computed using the formula <b>4096 + (Class_index * 8)</b>. The class defined first will have <i>Class_index</i> zero, the next will have one and so on.
</p>
</li>
<br>
<li>
<p>
<b>When the declaration of each method is found (in a class) a new label is generated for the function and the label is stored in the <a href="http://silcnitc.github.io/oexpl-data-structures.html">class table entry</a></b> (See <i>Memberfunclist</i> )<b>
for the function at compile time.</b> The compiler also must generate code to store these labels into the virtual function table entry of the function in the corresponding class.
(Strictly speaking, an integer value called the "pseudo-address" for the function is stored in the <i>flabel</i> field of the <i>Memberfunclist</i>
entry of the function. The pseudo addresses could be 0,1,2,3 and so on. When code is generated, for functions with <i>flabel</i> values 0,1,2,3, etc., the actual
labels placed could be F0,F1,F2,F3 etc to make them more human readable.)
</p>
</li>
<br>
<li>
<p>
<b>It is better to maintain the index of a method in the <a href="http://silcnitc.github.io/oexpl-data-structures.html">class table</a>
(Funcposition) and the virtual function table to be the same. </b> This makes code generation for method invocations
easier. When a method is invoked, the compiler can look up the index of the method from the appropriate class table and
generate code to invoke the function whose call address (label) is stored in the virtual function table at the position
determined by index.
</p>
</li>
<br>
<p>
[Note 1: that the class table is a static (compile time) data structure and will not be part of the
target program. The compiler uses the class table information to generate code that will create the virtual
function table at execution (run) time.]
</p>
<p> [Note 2: It is sufficient to place labels, and not addresses in the virtual function table, as the
<a href="http://silcnitc.github.io/label-translation.html">label translation phase</a> will take care of
translating labels to addresses]. </p>
<p>
In the example given, the function f0 in class A has funcposition 0 and say flabel F0 (we identify flabel 0 with F0) and the function f1 in class A gets a funcposition 1 and say flabel F1 (we identify flabel 1 with F1). The member function list of class A looks as shown in the below figure :
<br><a href="../img/virtual_function_table_3.png"> <img src="../img/virtual_function_table_3.png" class="center"></img></a>
<br />
The virtual function table of class A looks as shown in the figure below. It is constructed using member function list of class A which is shown in the figure above.
<!--Similarly for <i>rollno,aerage,findaverage(linkedlist marks)</i>, symbol table entries are formed and installed.-->
<br><a href="../img/virtual_function_table_1.png"> <img src="../img/virtual_function_table_1.png" class="center"></img></a>
<br />As mentioned earlier, all the labels of the functions will be replaced with addresses during <a href="http://silcnitc.github.io/label-translation.html">label translation phase</a>.
</p>
<br>
<li>
<!--
<p>
For every method declaration, a new label is alloted.
In class A, the function f1 gets an index 0 an say label f1 and
<br/> the function f2 gets an index 1 and say a label f2.
</p>
<p>
Following is how virtual function table looks in the stack when <i>A</i> class is installed.<br>-->
<!--Similarly for <i>rollno,average,findaverage(linkedlist marks)</i>, symbol table entries are formed and installed.-->
<p>
Class B extends class A and over-rides f0(). Further, class B contains the newly defined method f2(). When a class extends another, all the member fields and methods of the parent class are inherited by the derived class, unless over-ridden by a new definition. Since the method f0() is over-ridden by B, a new label will have to be allocated for the function f0() in class B. In the present example, we set the new label to F2. Accordingly, the compiler must update <i>Memberfunclist</i> entry of the method f0() in class B with the new <i>flabel</i> value. Correspondingly, in the virtual function table entry for class B, the entry for method f0() must be F2 (over-riding F0). The entry for method f1() (label F1) will be inherited from class A. A new label (label F3 in the example) must be generated for the function f2() defined in class B. The labels for each method in class B is shown in the table below for easy reference.
<br>
<br><a href="../img/virtual_function_table_8.png"> <img src="../img/virtual_function_table_8.png" class="center"></img></a>
<br>
</p>
<p>
<!-- All the member fields and methods of class A are inherited by class B initially. However, since the method f1() is overridden by Class B, a new label will be allocated, for the function f1() in class B. Accordingly, we will update <i>Memberfunclist</i> entry of the method f1() in class B by a new <i>flabel</i> value. Similarly, the <i>Memberfunclist</i> entries for class C will be constructed. <br><br>The final class tables and corresponding member function lists are shown in the figure below.-->
From an implementation point of view, it will be easier to (generate code to) copy all the virtual function table entries of A to the virtual function table of B and then (generate code to) modify the labels of over-ridden functions/add labels for new functions defined in B. The compilation for class C may proceed similarly. Note that OExpL specification stipulates that the signatures of the over-ridden methods must match exactly with the signature of the original definition in the parent class.
</p>
<!--
In class B, there are two methods f1() and f3() and it is extending class A. When a class extends other class,
all the member fields and methods of the parent class are inherited by the derived class. Suppose as in this example,
if the method signatures of the parent class and the derived class match, then method overriding occurs.
<br />
<a href="https://en.wikipedia.org/wiki/Method_overriding">Method Overriding</a> means the definition of the method that belongs to
parent class is replaced by the definition of the method which is already present in the derived class.
Here, f1() method of class B overrides the f1() method of class A.
Let us see how the process of method overriding occurs, how the member function list is updated for the derived class.
This is demonstrated using the classes B and A of this OExpL program.
Here, class B is extending class A.
So, all the member fields and methods of class A is inherited by class B.
So, now the member function list looks as shown in the figure below.
<img />
Here method f1() derived from class A, will be overridden by the method f1() of class B.
As stated above, a new label will be alloted, for the f1() method of class B.
Now, we need to update the member func list entry of the f1() method in class B, by new flabel given to the method f1() of class B.
Similarly, the member func list for class C will be constructed.
The final class tables and corresponding member function lists are shown in the figure below.
<br /><br />-->
<br><a href="../img/virtual_function_table_4.png"> <img src="../img/virtual_function_table_4.png" class="center"></img></a>
<br /><br><br>
<p>
<span class="red-star-1">★</span> Overridden labels are marked in red
</p>
<p>
The corresponding virtual function tables of all the classes are shown in the figure given below :
</p>
<br />
<br><a href="../img/virtual_function_table_2.png"> <img src="../img/virtual_function_table_2.png" class="center"></img></a>
<br />
<p> <span class="red-star-1">★</span> Overridden labels are marked in red </p>
</li>
</ol>
</article>
<!-- This is all already removed
<article class="grid col-full" id="nav-runtimebinding">
<h2>Run Time Binding</h2>
<script src="../js/9fab0ed1079cbf0ebdae2916b4272929.js"></script> -->
<!-- From the above code, the calling of the function depends on the input value n.(This line is already removed)-->
<!-- <p> To the above code, the value of n is read from the console and not known at the compile time. </p>-->
<!--
<p> If (n < 0), the method f1() of the class A is invoked at run time. If (n = 0), the method f1() in the class B is invoked at run time and If (n > 0), the method f1() in the class C is invoked at run time. So, Depending on the value of n, the variable obj must be bound to a different class. Even though the three methods which are overridden has the same name f1(), the call addresses must be different in each case. The information in the virtual function tables will be useful here. </p>
<p>
At run time, the variable obj is assigned not only a pointer to the data region of the object in the heap memory, but also a pointer to the virtual function table of the corresponding class. (Note that a class variable has two words of storage allocated to it.). Hence, the correct method can
be identified at run time by looking up the label of the function f1() in the virtual function table to which the variable obj is bound to at run time.
</p>-->
<!-- </article>
<article class="grid col-full" id="nav-resolve">
Removed till here
-->
<!--
<p> If (n < 0), the method f1() of the class A is invoked at run time. If (n = 0), the method f1() in the class B is invoked at run time and If (n > 0), the method f1() in the class C is invoked at run time. So, Depending on the value of n, the variable obj must be bound to a different class. Even though the three methods which are overridden has the same name f1(), the call addresses must be different in each case. The information in the virtual function tables will be useful here. </p>
<p> We noted earlier that the variable obj has two words of memory assigned to it at compile time - one member field pointer and one virtual function table pointer.
At run time, the member field pointer field of the variable obj is used to store a pointer to the space allocated in the heap as done in the previous stages.
The virtual function table pointer is used to store the start address of the virtual function table of the class assigned to obj at run time. </p>
<p>
For instance, obj = new(A) must result in the member field pointer of obj to be set to a newly allocated heap block and the virtual function table pointer to
be set to the start address of the virtual function table of class A. Similarly, obj = new(B) must result in setting the virtual function table pointer of obj
to the base address of the virtual function table of class B. Consequently, the compiler can resolve the call obj.f1() by generating code to
look up the label of the function f1() in the virtual function table pointed to by the virtual function table pointer field of obj.
</p>
<h4> Actions during Compile Time </h4>
<ul>
<li>
<p> Referring to the above example, when the compiler encounters the statement obj=new(B), code is generated for the following:
a) Call the library routine for Alloc to allocate heap memory. The address returned is stored into the member field pointer of obj.
b) Set the virtual function table pointer of obj to the base address of the virtual function table of the class B (i.e, 4104).
Note that before generating the code, compile time check whether B is a descendant class of the class of obj (in this case A) must be made.
</p>
</li>
<li>
<p> For the statement, obj.f1(), the compiler must do the following:
a) Find the index of f1() in the class table of the class to which obj belongs to (Here obj is declared to be of class A. The Funcposition of f1() in the class table entry of A will be 0.)
b) Generate the code to get label of the function at index 0 from the virtual function table pointed to by the virtual function table pointer field of obj into a register (say R0).
c) Generate code to push the "self object" into the stack as argument (i.e., the member field pointer of obj and the virtual function table pointer of obj must be pushed as arguments to the call to f1() -
See function call convention for methods.)
d) Generate code to call the function using the label obtained in step b. (call R0).
Note that compile time check whether f1() is a method in the class A to which obj is declared to must be done before proceeding to code generation.
</p>
</li>
</ul>
<h4> Run time Stack Management for Method invocations </h4>
<p>
When generating the code for invoking a method of a class using an object of the class (for example, in the call obj.f1() above, f1() is invoked using the object obj of class A)
the member field pointer and virtual function table pointer of the object must be pushed to the stack in addition to normal arguments of the function.
We will follow the convention that these two values will be pushed before other arguments are pushed.
This is how the runtime stack looks, when a method of a class is called.
<br>
<br> <a href="../img/runtimestackoexpl.png"> <img src="../img/runtimestackoexpl.png" class="center"></img></a>
<br>
For instance, in the above example, if the value read from the input is 0, the following figure shows the run time stack.
<br>
<br> <a href="../img/runtimestackoexpl2_1.png"> <img src="../img/runtimestackoexpl2_1.png" class="center"></img></a>
<br>
</p>
-->
<!-- Already removed
<p> Suppose the function f1 has the following definition.
</p>
<p>
Then, a reference to . self.variable, self.method() </p>
Till here
-->
<!--
<h6>Need For Pushing The Object : </h6>
<p>
According to OExpL Specification, a member field or method should be accessed using self.
In order to find out which object we are talking about,when we say self, we need to push the object into the stack.
</p>
<p>
Consider the following OExpL program,
<br>
<script src="../js/55aeef67b003d48dd45db379b46a4631.js"></script>
</p>
<p>
For <b>obj1</b>, the member field <b>height</b> must be set to 10.
For <b>obj2</b>, the member field <b>height</b> must be set to 20.
</p>
<p>
In the method definition for the method <b>setHeight</b>, the member field <b>height</b> is set by using the statement,
<b>self.height = a;</b>.
<br>
By this statement alone, we cannot say which object is <b>self</b> referring to.
To identify which object is <b>self</b> referring to, we push the calling object to the stack.
</p>
<p>
If <b>obj1</b> calls the method <b>setHeight</b>, the member field pointer and virtual function table pointer of <b>obj1</b> are pushed into the stack.
Now, we know that <b>obj1</b> is calling the method (By looking at the runtime stack).
So, we set the <b>member field height of obj1</b> by using the <b>member field pointer</b> and the <b>field position of member field height</b>.
Member field pointer is the heap address given to the object for storing the member fields of the class it is assigned with.
</p>
<p>
The virtual function table pointer is used, when we invoke other methods using <b>self</b>.
<b>p = self.setHeight(5); </b> //In the method defaultHeight().
<br>
For this we need to generate a CALL instruction.
The call address is obtained from virtual function table.
</p>
</p>
<h2>Resolving Strategy</h2>
For every class variable, generally one block of memory in stack is allocated for storing the heap address.
But with the introduction of subtyping, we face the problem of resolution of which method to call as shown in the example
<a href="http://silcnitc.github.io/oexpl-run-data-structures.html#nav-runtimebinding"> mainfunc.txt </a>.
So, now to resolve this we use virtual function table and every class variable will be allocated two blocks of memory.
One block is used to store the heap address and the other block is used to store the starting address of the virtual function table.
<h4> During Compile Time</h4>
In the example <a href="http://silcnitc.github.io/oexpl-run-data-structures.html#nav-runtimebinding"> mainfunc.txt </a>, when compiler reaches the statement, <b>obj.f1()</b>, it checks the type of obj, which means
to which class the <b>obj</b> belongs to. Then it gets the member function list of the class of that object and checks if there
is any method with name <b>f1</b>. If it finds a method, it proceeds with the compilation. If it doesn't find, then it is a
compilation error.
When it encounters the statement, <b> obj = new(A);</b>, the second block of object is set.
The second block of the object is to be set with the starting address of virtual function table of a class.
So, here,
(4096 + class_index * 8) is the starting address of virtual function table of the required class. The class_index is that of the class
that is present in new. So, for <b>obj = new(A);</b> 4096 is stored because class index of A is 0. Similarly, for class B, 4104 is stored.
For class C, 4112 is stored.
When the compiler encounters a call statement, from the second block of A we get start address of virtual function table,
and funcposition is obtained from the member function table of class to which this object belongs to.
Both are added and the value present in that address(flabel) is stored in a register.
Then a call to the register is made.
<h4>During Run Time</h4>
if '( n < 0)' then the two words of obj is : <br />
<a href="../img/virtual_function_table_5.png"> <img src="../img/virtual_function_table_5.png"></img></a><br />
if '(n = 0)' then the two words of obj is : <br />
<a href="../img/virtual_function_table_6.png"> <img src="../img/virtual_function_table_6.png"></img></a><br />
if '(n > 0)' then the two words of obj is : <br />
<a href="../img/virtual_function_table_7.png"> <img src="../img/virtual_function_table_7.png"></img></a><br />
During run time, only one if will be executed. That means by the completion of if,else block, required values are set,
and the call to the required function is made.
</article>
-->
<article class="grid col-full" id="nav-runtimebinding">
<h2>Runtime Binding</h2>
<p> Please go through the <a href="http://silcnitc.github.io/oexpl-specification.html#nav-run-time-binding" target="_blank">OExpL Specification - Run time Binding </a> carefully before proceeding further. </p>
<p> Consider the OExpL code given below assuming the classes defined <a href="http://silcnitc.github.io/oexpl-run-data-structures.html#nav-illustration">above</a></p>
<br>
<script src="../js/9fab0ed1079cbf0ebdae2916b4272929.js"></script>
<br>
<p>
The method invocation within the statement obj.f0() in the above code needs to be analysed carefully. Depending on the
run time value of n, the actual function to be invoked will be different. <b>This is because the variable obj will be bound
to different classes depending on the value of n</b>. Here we describe what the compiler must do to bind obj to the correct
class at run time.
</p>
<p>
We have already noted earlier that, when the compiler encounters the declaration of a variable of a class, it has
to allocate <b>two words of storage</b>
for the variable (unlike other variables, where only one word of storage is allocated).
The first word ( <b>member field pointer</b> ) is to store the address of the memory area allocated in the heap for the class (eight words).
The compiler must use the second word ( <b>virtual function table pointer</b> ) to store the address of the
virtual function table of the class to which the variable is bound to at run time.
</p>
<!--
<p>
For every class variable, generally one block of memory in stack is allocated for storing the heap address.
But with the introduction of subtyping, we face the problem of resolution of which method to call as shown in the example
<a href="http://silcnitc.github.io/oexpl-run-data-structures.html#nav-runtimebinding"> mainfunc.txt </a>.
So, now to resolve this we use virtual function table and every class variable will be allocated two blocks of memory.
One block is used to store the heap address and the other block is used to store the starting address of the virtual function table.
</p>
-->
<p>
For instance, the statement <i>obj = new(A);</i> must result in two actions:
<ol>
<li>The member field pointer of <i>obj</i> must be set to a newly allocated heap block.</li>
<li>The virtual function table pointer of <i>obj</i> must be set to the start address of the virtual function table of class A.</li>
</ol>
</p>
<!--
Similarly the statement obj=new(B) results in the compiler generating code to store the
value 4104 to the virtual function table pointer of the variable obj. obj=new(C) would result in storing the value
4112 to the virtual function table pointer of obj.
-->
<p>
Recall that the start address of the virtual function table for a class can be computed as (4096 + <i>class_index</i> * 8).
In the above example, since the <i>class_index</i> of class A is zero, the above statement sets the virtual function table pointer
value of obj to the value 4096.
</p>
<!--
Similarly, <i>obj = new(B);</i> must result in
setting the virtual function table pointer of obj to the base address of the virtual function table of class B.
-->
<!--
When the compiler encounters the statement <b> obj = new(A);</b>, <b>code must be generated to
set the virtual function table pointer field of obj to the starting address of the virtual function table of class A</b>.
-->
Similarly the statement obj=new(B) results in the compiler generating code to store the
value 4104 to the virtual function table pointer of the variable obj. obj=new(C) would result in storing the value
4112 to the virtual function table pointer of obj.
As an illustration, assume that the compiler has allocated memory address 4120 and 4121 for storing the member field pointer and virtual
function table pointer of obj. Assume that a call to the new function results in allocation of 8 words in the heap starting with
the memory address 1024 (using the <a href="http://silcnitc.github.io/run_data_structures/heap.html" target="_blank">Alloc()</a> library function). The following figure shows how the values of memory locations 4120 and
4121 has to be set for various values of n.
<br>
<br>
if '( n < 0)' then the two words of obj is : <br /> <br>
<a href="../img/virtual_function_table_5.png"> <img src="../img/virtual_function_table_5.png"></img></a><br /><br>
if '(n = 0)' then the two words of obj is : <br /> <br>
<a href="../img/virtual_function_table_6.png"> <img src="../img/virtual_function_table_6.png"></img></a><br /><br>
if '(n > 0)' then the two words of obj is : <br /> <br>
<a href="../img/virtual_function_table_7.png"> <img src="../img/virtual_function_table_7.png"></img></a><br /><br>
<!--During run time, only one if will be executed. That means by the completion of if,else block, required values are set,
and the call to the required function is made.-->
<p> In the above code, the value of n is read from the console and is not known at the compile time. Hence, the actual
value stored in the virtual function table pointer of obj during run-time cannot be predicted at compile time. Consequently,
the actual function invoked by the call obj.f0() cannot be predicted at compile time. This fact
forces the compiler to generate code to maintain the virtual function tables at run time.</p>
<b>
Note that an assignment statement would result in copying the values of both the pointers of the variable on the right side
to the variable on the left side.</b>
<!--When the compiler encounters the method invocation obj.f0(); the value stored in the virtual function table pointer of
obj will determine the correct class to which the variable obj is bound to at run time. Since obj is declared as a variable
of class A, The compiler simply looks up the func-pos of the function f0() in class A - which is 0 in this case.
Hence, it generates code to invoke the function corresponding to index 0 in the virtual function table pointed to by
virtual function table pointer of obj. Consequently, -->
</article>
<br>
<article class="grid col-full" id="nav-methodinvocations">
<h2>Method Invocations</h2>
<p> Consider the statement <b>write(obj.f0());</b> in the above code.
<!--
<p> if (n < 0), the method f0() of the class A is invoked at run time. If (n = 0), the method f0() in the class B is invoked at run time and If (n > 0), the method f0() in the class C is invoked at run time. So, Depending on the value of n, the variable obj must be bound to a different class. <b>Note that the value of n is known only when the program is run (at run time) and not known statically determined (i.e., not known at compile time)</b>. Even though the three methods which are overridden has the same name f0(), the call addresses must be different in each case. The information in the virtual function tables will be useful here.
</p>
<p> We noted earlier that the variable <i>obj</i> has two words of memory assigned to it at compile time - one <b>member field pointer</b> and one <b>virtual function table pointer</b>.
At run time, the member field pointer of <i>obj</i> is used to store a pointer to the space allocated in the heap as done for user defined type variables.
<b>The virtual function table pointer is used to store the start address of the virtual function table of the class assigned to <i>obj</i> at run time.</b> </p>
<p>
For instance, the statement <i>obj = new(A);</i> must result in two actions:
<ol>
<li>The member field pointer of <i>obj</i> must be set to a newly allocated heap block.</li>
<li>The virtual function table pointer of <i>obj</i> must be set to the start address of the virtual function table of class A.</li>
</ol>
Similarly, <i>obj = new(B);</i> must result in setting the virtual function table pointer of obj to the base address of the virtual function table of class B.
-->
The compiler can resolve the call <i>obj.f0();</i> by generating code to:
<ol>
<li>Use the virtual function table pointer field of <i>obj</i> to find the address of the virtual function table of the class to which obj is bound to. </li>
<li>Look up the virtual function table to find the address (label) of the function f0(). </li>
<li>Call the function (of course, after setting up the call stack).</li>
</ol>
</p>
<!--
<ol>
<p> In more detail, when the compiler encounters the statement <i>obj=new(B);</i> code is generated for the following: </p>
<li> Call the library routine for Alloc to allocate heap memory. The address returned is stored into the member field pointer of obj. </li>
<li> Set the virtual function table pointer of obj to the base address of the virtual function table of the class B (i.e, 4104). </li>
<p>
Note that before generating code, compile time check whether B is a descendant class of the class of obj (in this case A) must be made.
</p>
</ol>
-->
<p>
When compiler encounters the method invocation, <b>obj.f0()</b>, it first checks the type of <i>obj</i> - i.e, to which class the <b>obj</b> belongs to.
Then it gets the member function list of the class of that object and checks if there
is any method with name <b>f0</b>. If it finds a method, it proceeds with the compilation. Otherwise, a
compilation error is reported.
</p>
<p>In more detail, for the call <i>obj.f0()</i>, the compiler must do the following: </p>
<ol>
<li>Find the index of <i>f0()</i> in the <a href="http://silcnitc.github.io/oexpl-data-structures.html" target="_blank">class table</a> entry of <i>obj</i>. Here <i>obj</i> is declared to be of class A and the index (look up Funcposition field in the member function list of class A) of <i>f0()</i> in class A will be 0. </li>
<li> Generate the code to push the registers in use into the stack </li>
<li>Generate the code to move to a register (say R0) the label of the function at index 0 from the virtual function table of <i>obj</i>. The virtual function table pointer field of obj will point to the virtual function table.</li>
<li> Generate code to push the "self object" into the stack as argument (i.e., the member field pointer of obj and the virtual function table pointer of obj must be pushed as arguments to the call to f0() - See Run time Stack Management for Method Invocations below .) </li>
<li> Generate code to call the function using the label obtained in step 2. (call R0). </li>
<li> Generate code to unwind the stack, extract return values upon return from the call and restore registers. </li>
<!--
Note that compile time check whether f0() is a method in the class A to which obj is declared to must be done before proceeding to code generation.
-->
</ol>
<b>Note:</b> The OExpL specification requires that a class can have only a single method of a given name, and the signature of a method
inherited from a parent class (over-ridden or otherwise) must be identical with the signature of the method in the parent class.
These simplifications allow the above implementation of virtual function tables where, the index of a method
in the virtual function tables of every class in a class hierarchy is unique. If method overloading was supported, then
there would be multiple functions with the same name within a class, and the implementation would be slightly more involved.
(Think what additional stuff needs to be done in that case!)
</article>
<article class="grid col-full" id="nav-runtimestackmanagementformethodinvocations">
<h2> Run time Stack Management for Method invocations </h2>
<p>
While generating the code for invoking a method of a class using an object of the class (for example, in the call obj.f0() above, f0() is invoked using the object obj of class A)
<b>the member field pointer and virtual function table pointer of the object must be pushed to the stack in addition to normal arguments of the function.</b>
We will follow the convention that these two values will be pushed before other arguments are pushed.
This is how the runtime stack looks, when a method of a class is <b>called</b>.
<br>
<br> <a href="../img/rts11.png"> <img src="../img/rts11.png" class="center"></img></a>
<br>
For instance, in the above <a href="http://silcnitc.github.io/oexpl-run-data-structures.html#nav-runtimebinding" target="_blank">example</a>,
The value of <i>n</i> read from the input is 0, the following figure shows the run time stack. Note that the
function f0 has no arguments.
<br>
<br> <a href="../img/rts2.png"> <img src="../img/rts2.png" class="center"></img></a>
<br>
</p>
<!--
<p> Suppose the function f1 has the following definition.
</p>
<p>
Then, a reference to . self.variable, self.method() </p>-->
<h5><b>Why do we need to push the object? Illustration:</b></h5>
<p>
According to OExpL Specification, a member field or method should be accessed using <i>self</i>.
In order to correctly specify the object referred to <i>self</i>, we need to push the object (member field pointer and virtual
function pointer) into the stack.
</p>
<p>
Consider the following OExpL program,
<br>
<script src="../js/55aeef67b003d48dd45db379b46a4631.js"></script>
</p>
<!--
<p>
For <b>obj1</b>, the member field <b>height</b> must be set to 10.
For <b>obj2</b>, the member field <b>height</b> must be set to 20.
</p>
<p>
In the method definition for the method <b>setHeight</b>, the member field <b>height</b> is set by using the statement,
<b>self.height = a;</b>.
<br>
By this statement alone, the compiler cannot say which object is <b>self</b> referring to.
To identify which object is <b>self</b> referring to, we push the calling object to the stack.
</p>
<p>
If <b>obj1</b> calls the method <b>setHeight</b>, the member field pointer and virtual function table pointer of <b>obj1</b> are pushed into the stack.
Now, the compiler can find out that <b>obj1</b> is calling the method by looking up the stack.
So, the compiler can generate code to set the member field <i>height</i> of <b>obj1</b> by using the member field pointer of the <i>self</i> object.
-->
<!--
Recall that member field pointer is the heap address given to the object for storing the member fields of the class it is assigned with.
-->
<!--
</p>
<p>
The virtual function table pointer is used, when we invoke other methods using <b>self</b>.
<b>p = self.setHeight(5); </b> //In the method defaultHeight().
<br>
For this we need to generate a CALL instruction.
The call address is obtained from virtual function table.
</p>
</p>
-->
<br>
<h5><b>Use of self for member field access :</b></h5>
<p>
Consider the statement self.i = 0 or self.i = 1 .
We need to store the value 0 or 1 for the member field i, of the object represented by the <i>self</i> (calling object).
In order to identify the object's heap address, the <b>member field pointer</b> of the <i>obj</i> must be available as an argument
in the stack.
</p>
<h5><b>Use of self for method invocations :</b></h5>
<p>
<!--
Suppose if n>0, the variable obj will get the object of type class A. <br>
If n<=0, the variable obj will get the object of type class B. <br>
So, by the statement obj.f0(); // Since f0() is not overridden, so B has the same definition of f0() defined in class A.<br>
Then the compiler translates call to f0() by using the virtual function table pointer of obj.<br>
In method f0(), there is a call to method f1().<br>
The compiler doesn't know where to go because both the classes have method f1().<br>
So, we need to get the virtual function table of the calling object which is done by pushing the object into the stack.<br>
-->
Suppose n > 0, then the variable <i>obj</i> will be bound to an object of class A. If n <= 0, then the variable <i>obj</i> will be bound to an object of class B.
</p>
<p>
When the compiler encounters the method invocation <i>obj.f0()</i>, the virtual function table of <i>obj</i> will be
looked up to find the call address of the method f0().
Since f0() is defined in class A and not over-ridden by class B, the virtual function tables of both class A and class B
will store the same call address for f0().
</p>
<p>
However, inside the method f0(), there is a call to the method <i>self.f1()</i>.
Note that f1() is over-ridden by class B.
Hence, the <b>call address for the method f1() when <i>obj</i> holds an object of class A will be different
from the call address of f1() when <i>obj</i> holds an object of class B.
However, the class corresponding to the object stored in <i>obj</i> is determined by the value of n which is not known at compile time.</b>
Hence, to generate code for the call <i>obj.f1()</i> inside f0(), the virtual function table of the class to which <i>self</i> is associated must
be available as an argument in the stack. Inside f0(), when the compiler translates the call <i>self.f1()</i>, it needs to do the following:
</p>
<p>
<ol>
<li>
Generate code to look up the <b>virtual function table field</b> of <i>self</i> (received as argument) to find the call address of the function f1().
</li>
<li>
Generate code to invoke f1() using the address obtained (of course, after setting up the call stack).
</li>
</ol>
</p>
<!--
the value of the virtual function table pointer determines
the correct class to which
, from the second block of A we get start address of virtual function table,
and funcposition is obtained from the member function table of class to which this object belongs to.
Both are added and the value present in that address(flabel) is stored in a register.
Then a call to the register is made.
-->
<!-- In the example <a href="http://silcnitc.github.io/oexpl-run-data-structures.html#nav-runtimebinding"> mainfunc.txt </a>,-->
</article>
<!-- <article class="grid col-full">
<p>
<a href="oexpl-runtime-binding-tutorial.html" target="_blank">OEXPL Run Time Binding Tutorial</a>
</p>
</article> -->
</div>
</section>
</div>
</div>
<footer class="center part clearfix">
<ul class="grid col-one-third social">
<li><a href="http://github.com/silcnitc">Github</a></li>
<li> <a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">
<img alt="Creative Commons License" style="border-width:0" src="img/creativecommons.png" /></a></li>
</ul>
<div class="grid col-one-third" style="color:black;">
<p style="font-weight: bold;">Contributed By : <a href="#">J.Ritesh</a> <br>        <a href="#">J.Phani Koushik</a><br>         <a href="#">M.Jaya Prakash</a>
</p>
</div>
<nav class="grid col-one-third ">
<ul >
<li><a href="index.html">Home</a></li>
<li><a href="about.html">About</a></li>
<!-- <li><a href="uc.html">Contact</a></li> -->
</ul>
</nav>
<br>
</footer>
<script>window.jQuery || document.write('<script src="js/jquery-1.7.2.min.js"><\/script>')</script>
<script src="js/scripts.js"></script>
<script src="js/inject.js"></script>
</body>
</html>