Welcome to part III of the lecture on Global Register Allocation Last time we discussed issues in Global Register Allocation, the Problem itself, Usage Counts based Register Allocation, Linear Scan based Register Allocation and part of Chaitin’s graph colouring based allocation To do a quick recap: here is the framework of Chaitin’s register allocation algorithm To begin with, there is a renumbering phase in which the live ranges or webs are identified Then, there is a build phase, where the interference graph is built. Then, there is copies absumption or coalescing, which removes some of the copies and reduces the size of the interference graph Then, we have a spill cost computation; the spill cost is computed based on many heuristics Then, there is a simplification, which removes the nodes and edges and reduces the graph Finally, this entire thing – for the spill nodes, we have to introduce spill code. The whole process is repeated and finally the selection of registers is made Quickly, simplification is – take a node whose degree is less than R and then remove the node and its edges from the graph. Keep doing this until it is not possible to do anything more At some point, there will be nodes, all of which are half degree greater than or equal to R – the number of registers available In such a case, we need to spill a node. Spilling a node implies loading x into a register at every use and then storing x from register into memory at every definition Spilling cost is very simply computed as cost v equal to sigma c star 10 to the power d, where the sigma is over all the loads and stores in the live range, c is the cost of a load or store, and d is the depth of nesting Basically, this is used to approximate the number of iterations in any loop There are many spilling heuristics Some of them use this area, which actually represents the global contribution by the live range to the register pressure. It is possible to use many heuristics at different points of time Here is a very simple example, which shows how graph, which is 3-colourable can be coloured without spilling Now, here is a graph, which is 3-colourable, but it cannot be coloured by the colouring heuristic. It says we will need a spill, but obviously, as we have shown here, it does not need any spill. So, there are some heuristic improvements possible to the heuristic itself, which will help us in colouring such a graph; we will see that a little later How to spill a node? To spill a node, we remove it from the graph and represent the effect of spilling by reloading the spilled object at each use and storing it in memory location at each definition point Now, the problem is this creates new webs with small live ranges, but which still need registers. After all the spill decisions are made, insert spill code, rebuild the interference graph, and then repeat the attempt to colour When simplification yields an empty graph, we stop Let us see the effect of spilling on webs Here is the web example that we had seen before There are many webs here: W1, W2, W3, W4 – in different colours. Most importantly, W1 consists of this Def, this Use, this Use and this Def; similarly, the others Suppose x is spilled in the web W1, what happens? Here is effect of that… Before that, this was the interference graph created for this particular web without any spilling If x is spilled and when there is a Def x, obviously we need to store that x into a location; let us call it as temp. This is a definition point of x. So, we have stored it into memory Here is a Use point of x and we are actually reading it from memory, x equal to temp and

then Use x Again, here is another one x equal to temp and Use x. This Def x is again a definition point. So, we are storing it into memory by saying temp equal to x. The others are not spilled. Only this particular web is spilled So, all the loads and stores are appropriately taken care of Now, there are many webs here The webs actually get split into many. Whatever is shown in red; Def x and temp equal to x is a small web on its own. This is x equal to and this is temp equal to x. So, this is a computation and then a Use. So, this becomes a small web on its own. Here is another small web the third small web, fourth small web, and rest of the other webs remain as they are Now, there are 8 webs. Then, of course, the temp equal to x, x equal to temp, temp equal to x, x equal to temp – these 4 now become a separate web consisting of these- B2, B3, B4 and B5. With these 8 webs, now, the interference graph slightly changes. In this case, there are many nodes, if you have the same number of edges really speaking. However, in a very large set of webs, in general, the interferences will reduce and the interference graph becomes a little more sparse possibly easier to colour The colouring heuristic is simple. There is a repeat until loop. All the vertices are now on the stack. So, take a vertex from the stack. Colours used v is colours used by neighbours of v in the graph. Colours free v is all the colours minus colours used. Colour v is any colour in colours free. We keep doing this until the stack is empty. So, that would give us a colouring, which is a fairly straightforward process Convert the colour assigned to a symbolic register to the corresponding real registers name in the code. So, we rewrite the code and that completes the colouring heuristic Now, let us take a complete example of a program – start from identification of the live ranges, building the interference graph, then colouring the graph and so on. Here is a very simple example; the program is the intermediate code Here is t1 equal to 202, i equal to 1, t2 equal to i greater than 0. Then, there is a test – if t2 go to L2; if we cross 100, then we go to L2; otherwise, we keep looping in this particular loop; t1 equal to t1 minus 2, t3 equal to address a, t4 equal to t3 minus 4, t5 equal to 4 star i. t6 equal to t4 plus t5, star t6 equal to t1, i equal to i plus 1 and goto L1. So, this is the loop There are 1 2 3 4 5 6 7 variables here and here are the live ranges of the variables For t1, the range is from 1 to 10. So, here is a definition, the first definition and the last use is in this number 10. For i, it is from 2 to 11. So, here is the first definition and the last use. So, that is 11 Then, similarly, we have t2, which is a very short live range. t2 is defined here and t2 is used here. So, 3 4; that is it. t3 is 6 7. Similarly, defined here and used here t4 is 7 9. So, t4 is defined here and used in 9. t5 is 8 9. So, t5 is defined here and used here and that is all. t6 is 9 10. So, t6 is defined here. Star t6 means you read t6 and then do indirection. So, this is really the usage of t6. So, this is the live range of this particular variable, t6 For these live ranges, it is easy to see the interference. For example, almost every variable over lapse with the live range of t1 and i because they run almost throughout the program – 1 to 10 and 2 to 11, all others are in between; we can easily see that For the two nodes: t1 and i, there are edges coming from every other nodes. Say for example, from t2, there are two edges to t1 and i; from t5, there are two edges to t1 and i, and so on and so forth. Then, similarly, t4 and t5 intersect because this is 7 to 9 and this is 8 to 9. So, there is an overlap. Then, the others for example, t6 does not interfere

with any other node except t1 and i, and so on. So, these live ranges are all small, but still colouring this with 3 registers is not a trivial job Let us assume that there are 3 registers and nodes t6… Also, what we do is – pick nodes with less than 3 degree; that is, 2 degree t6, t2 and t3 have 2 degree. So, these three are actually deleted from this particular graph and pushed on to the stack. That is the first thing. So, they have been shown in blue. After this is over and the edges corresponding to these are all removed, the graph reduces to this. So, this is a complete graph and this cannot be reduced further, but spilling is necessary because every node here has 3 degree Now, we need to compute the cost of spilling using the spilling heuristic. Let us use the simple Chaitin’s heuristic of sigma c star 10 to the power d. So, node t1 – let us look at the number of occurrences of t1. These are the only 4 nodes for which we need to compute cost. We need not compute cost for those nodes, which have already been deleted Let us assume that the load cost and the store cost are the same. So, t1 occurs once in this instruction number 1, then it occurs in instruction number 5; this is twice really, and then in instruction number 10 as well. So, one is here and then inside the loop. So, we have 1 2 and 3. So, 3 occurrences of t1. So, that is 31; 1 plus 1 plus 1 plus 1 star 10; that is, 10 to the power 1. So, this becomes 31 Similarly, for i, here is 1 and within the loop, there is one occurrence here another occurrence here, third occurrence here, and fourth occurrence here. So, there are 4 occurrences So, there are 4 1’s here. So, 1 plus 10 is 41 t4 has a definition here and a use here. So, there are only two of these. So, 1 plus 1 star 10; that is 20. Then, similarly, t5 is defined here and used here. So, 1 plus 1 star 10; that is 20 So, the costs are 31, 41, 20 and 20. Out of these two, we could have chosen… and degree is 3 for all of them. Now, h naught v, which is cost per degree is 10, 14, 7 and 7. We could have chosen any one of these for spilling Let us assume that we have chosen t5 for spilling Once it is spilled, it is always permanently in memory. So, this is the reduced graph This can be easily coloured with the 3 colours; there is no problem at all. This is the stack of t6 t2 t3. Then, we delete t4, t1, and then i. So, we can easily colour this graph by assigning i a colour, then, we take t1; it is assigned a different colour; that is here, and then we take t4 and we assign a colour, which is different from each of these, and so on and so forth Observe that t6, t2, t4 and t3 are all given the same colour; that is, R3. If we rewrite the code using these registers… I have not written assembly code here, but I have just rewritten the intermediate code using these registers so that it is easy to understand Observe – wherever we have t1. we would have put R1 and wherever we have i, we would have put R2. So, see that this code is correct Even though this 6 and 7, there is R3 equal to address a and then R3 equal to R3 minus 4. So, this is a read of R3 and then write in to the same one. So, this is reused here Because the live range of this R3 and live range of this R3 are not the same… This R3 for example, live range is 6 7 and live range of this is 7 9. So, there is no overlap as such. This is a use and this is a definition After this usage, we can actually write into the same register. Therefore, this is possible This is the rewritten code which shows that registers have replaced the temporaries, but

please observe that t5 is still t5. That is because, it is actually in memory. When we actually generate machine code, this spill node will be provided with a temporary register So, this will become a computation into a temporary register. Afterwards, t5 will be used here and then it is discarded because it is not needed any more. So, if memory can be used as an operand in the instruction, this does not become necessary. That is the example Now, what are the drawbacks of Chaitin’s algorithm? Constructing and modifying interference graphs is a very expensive process as interference graphs are typically very huge. If you take for example, the GCC compiler itself and then for example, all the functions, procedures, etcetera are combined and you try to draw a combined interference graph, then the graph has approximately 4.6 million edges; extremely huge graph. So, this is one of the major drawbacks What are the modifications necessary in order to improve this particular algorithm? You could be more careful during coalescing. For example, do not coalesce if the coalescing increases the degree of a node to more than the number of registers. So, if you do this, then it may lead to a spill. That is why, there is no need to coalesce. This is copies absumption problem Optimistic colouring: When a node needs to be spilled, put it into the colouring stack instead of spilling it right away. Assume that it can be coloured, put into the stack, hope for the best. Spill it only when it is popped and if there is no colour available for it. We will demonstrate this very soon This could result in colouring graphs that need spills using Chaitin’s technique For example here: This is a 3-colourable graph, which we saw before. It cannot be coloured using Chaitin’s heuristic, but using optimistic colouring it can be. Say, 1 is chosen for spilling; one of them has to be spilled; otherwise, there is no way you can colour it with three colours. Do not actually replace this and say – yes it is spilled and replace the loads and stores by appropriate instructions from memory. Push it into stack; assume that it is coloured and push it into stack Now, we have the rest of the graph here – 2 3 4 5. These just go away. This can be coloured with three colours. Let us say the colours assigned to the particular graph – 2 3 4 5. 1 is left on the stack. Observe that 2 and 4 have the same colour, 3 has a different colour, there is a colour free, which can be assigned to 1. Because we did not spill 1, but pushed it on stack, colouring of this has been possible. This is the optimistic colouring that we indicated few minutes ago However, there is no guarantee that this type of a graph for example, can colour every other graph, which is not 3-colourable. For example, if you look at this graph, this is not 3-colourable, but even if you try the colouring heuristic on this, it does not work because it is a fully connected graph. So, every time you introduce something on the stack your… Of course, left with just these 3 nodes; these can be coloured with 3 colours, but when we try introducing this, it will be connected to all others and therefore, we need a forth colour for this. So, this is how we do optimistic colouring This is the end of the lecture on Register Allocation Now, we will begin the new lecture on Implementing Object-Oriented Languages Welcome to the lecture on Implementing Object-Oriented Languages In this topic, we are going to basically consider classes and objects. Then, see – what are the requirements of the language, how to map names to methods; there are so many names in the program; it is possible that some of them are in the sub classes, some of them are in the super classes, some of them may

be really fine and so on and so forth. So, how to map these names to the appropriate methods? That is something we are going to study; then, variable name visibility, code generation for methods, and then finally, some of the simple optimizations I have been adopted some parts of this lecture from this book by Cooper and Torczon What are the language requirements? In an object-oriented language, we have objects and we have classes. For every class, you can instantiate it and create an object. So, these are all well known. Then, we have inheritance, subclasses and superclasses. So, you first declare a class, then inherit from it, and create a subclass. The class from which I have inherited is called as a superclass Inheritance requires that a subclass have all the instance variables specified by its superclass. In other words, if the superclass has three variables, which are actually declared, then every subclass of this superclass will have all these three variables in it. So, this is necessary for the superclass methods to work with subclass objects. As you know, you can actually have a base class pointer point to any object of the type, which is derived from this base class. If that is to be done, then the superclass methods must work with subclass objects and this requirement of having all the variables of the superclass inside the subclass becomes necessary. This will become clearer as we go along If A is B’s superclass, then some or all of A’s methods and instance variables may be redefined in B. That is not a problem; we should be able to provide for this as well Here is a very simple class diagram. The legend is – these three in turquoise blue are classes, then the light brown are all objects, and then these orange coloured ones are all methods So, there are three classes – one, two and three. Class one is inheriting from two and class two is inheriting from three; that is the end Class three, which is the grandfather class This is the father class and this is the son class. This is the hierarchy that we are talking about. It has a static variable, n, which shows how many instances of this have been created. It defines a procedure called fee and it also defines another procedure called fum Class two derives from three. It has one object, which has been created; that is, c. Even though it inherits fee from the superclass three, it redefines it. Now, you can see that this method pointer is pointing to fee. Whereas, fum, which is inherited from three is still being reused by class two also Let us look at class one. This actually inherits from two, two in turn inherits from three So, one will have the variables of two and three both and methods also. For example, fee is inherited, but it redefines fee. fum is being reused. The same fum, which is defined by three is used here foe is defined by class two and it is being reused here. fie is a new method, which is defined by class one itself. Then, there are three objects – a, b and c; a and b belong to class one, c belongs to class two, and there are no objects of type class three With this scenario, let us see how things work. It should be made clear that method invocations are not static calls. In other words, when we actually write a dot fee, we do not know which method is being called This is the general statement In this particular case, when we say a dot fee, it invokes one dot fee. The reason is

a is an object of type one and this f e nvokes one dot fee, which is being redefined. Even though fee is inherited from two, it is being redefined in one. So, the local fee will be called when we say a dot fee; that is no problem b dot foe invokes two dot foe. Let us see what happens to b dot foe. b is here foe is inherited from two, and there is no local redefinition of foe for one. When we say b dot foe, it is really two dot foe, which is being called. So, there is no foe here Then, c dot fum invokes three dot fum. When we say c dot fum, c is an object of class two, but it does not have its own fum, it is actually from class three So, c dot fum really invokes three dot fum. This is what we mean. This is a virtual call. We have no idea of which particular call is invoked until the call is resolved Conceptually, method lookup behaves as if it performs a search for each procedure call So, these are called virtual calls. How does it happen? Search for the method in the receiver’s class; that is, the particular object. For example, if it is b dot foe, search in the class corresponding to b. That is, one itself If it fails, for example, there is no b dot foe in the class corresponding to b. If it fails, move up the receiver’s superclass and further. Then, the superclass of one is two So, two defines foe. So, b dot foe resolves to two dot foe To make this search efficient, an implementation places a complete method table in each class This is what has happened here. Each one of the classes has a method table. For example, if you consider one, there are four methods corresponding to class one: first one fee is a local redefined method. So, there is a pointer to this. This is the method table we are talking about. fum points to the old one itself, the inherited one. foe points to the old one, the inherited one. fie is a new method, which is defined within one Same thing is similar in two also. fee is locally redefined, fum is inherited, and foe is a new one. Within three, fee and fum are both locally defined new methods Or, a pointer to the method table is included So, this is called as a virtual table pointer Instead of keeping this entire table inside the class, it is possible to have a table outside and a pointer replacing this entire table. So, I go to that table, which is actually this, which is outside and then call this particular method. So, that is called as a virtual table pointer How do you map names to methods? If the class structure can be determined wholly at compile time, then the method tables can be statically built for each class. Here, in the previous example, that is how it was. Here we knew which particular class is rare, which object belongs to which particular class, which methods have been defined in which class, etcetera were all known. So, we could build all the method tables statically and put them inside the class record If classes can be created at run time or loaded dynamically, class definition can change as well. Like in Java, I can roll it at run time and I can also create it dynamically. Then, full lookup in the… So, if we do this then there is no need to lookup, method points are all there in the method tables. So, we just go to that particular method and use it; there is no need to search For example, there is no need to search anything here. I have a special pointer perform right here, which can be used to call this fum

Otherwise, if it is dynamic, then full lookup in the class hierarchy can be performed at run time; no problem because if I add a class at run time, then I may not be able to build the entire table at compile time itself Otherwise, use complete method tables as before and include a mechanism to update them when needed. So, if we add a new class, then for all the classes actually which are derived from this class later on, we create the method table at run time. That is what this really is What are the rules for variable name visibility? So far, we saw the rules for searching method names. Now, let us see what happens to data Let us look at a picture, the same picture here. We have a and b of type class one. a has x y z, b also has x y z – these are objects of class one. Then, c has only x y and it is of type class two Invoking b dot fee allows fee access to all the b’s instance variables; all the three of them – x y z. Why? Since fee and b are both declared by class one. So, see here We call b dot fee. This fee will have access to all the variables; that is, x y z of this particular object. b is of type class one and fee is redefined right here. So, there is no problem. Everything that is declared will be accessible to the method fee and also all the class variables of one two and three So, this is the lowest in the class hierarchy So, one inherits from two and two inherits from three. So, all the variables of two and three will also be accessible to this method fee, which can actually access the variables of the superclasses However, when we are invoking b dot foe, there is a small problem. Let us see what happens Here is b and here is foe. foe is not defined here. foe is defined actually in class two So, it is that foe that we are calling. When we compile two, it was not expected to work with one, but it was expected to work with two and three only. So, this creates some special problems Invoking b dot foe allows foe access only to instance variables x and y of b. It does not allow access to z because it never know that there is something called z. z actually belongs to one the objects of class one, whereas this foe belongs to class two. So, class two has no information about class one as such z of b is not accessible to this foe since foe is declared by class two and b is declared by class one. Foe can also access class variables of classes two and three, but not class variables of class one. So, this is what we explained just now How do we generate code for methods? Methods can access any data member of any object that becomes its receiver. So, what is a receiver? Every object that can find the method is a receiver. We say b dot something and so on That b is the receiver Subject to class hierarchy restrictions, whenever in the hierarchy of classes, an object can find a method and that method can be executed and methods can access any data member of any object that becomes the receiver. So, if it is b dot something and b’s b dot fee, fee can access members of b The compiler must establish an offset for each data member that applies uniformly to every receiver. So, the problem is – if receivers are from different classes, then this creates a problem. So, you cannot access the data variables so easily. So, we will see this difficulty

The compiler constructs these offsets as it processes the declarations for a class. So, objects contain no code, they contain only data. This is very clear. Code is actually in some other place. Let us show this for a single class with no inheritance Here is a very simple class – class giant int fee, int fie, int foe, int fum – four methods. This is the static n and int x y Objects contain variables – x y, n is within the class record and the method pointers are all here. These objects point to the class record and here are the method pointer offset – 0 4 8 12. So, when we want to call something, we know where exactly… This can be done at compile times. So, if there is joe dot fee, we know the offset of fee. So, taking the contents of this is very easy. Then, there is a giant sub routine instruction to execute this particular method Here is the detailed class diagram with single inheritance. The previous one did not even have inheritance, here there is single inheritance Multiple inheritance would be the last one We have class giant, which is of type class mc and mc itself is of type class sc. So, there is a class hierarchy of giant mc and sc. This is the superclass called class in Java, which is the mother of all classes So, its own class pointer actually points to itself. Then, we have a superclass pointer field, then method pointer fields, and then variables. That is how all these records are laid out These are the variables- x y and z and here are the superclass pointers. These are the class pointers. So, all of them point to this particular class itself. For objects, the class pointer points to their own class type; all these, for example, point to their own class type How about the object layout under single inheritance? Remember this diagram. We have this giant, which has new fee and fie and then this static, which is not necessary for objects. So, objects have x y z For object layout for joe and fred, which are members of the class giant – there is a class pointer, then the data members of sc, which is just one variable x. For example, here This sc has only one variable x, this mc has x inherited from here and y its own, and giant inherits x and y from the superclasses and z is its own We have sc data members, mc data members and giant data members. So, this is a layout for objects of type giant. Similarly, the class record is something we already saw – class pointer, superclass pointer, method pointer table. This is the method pointer table Object layout for goose, which is a member of mc, which is one level above. This is mc and this is the object we are talking about It does not have the members of giant, obviously It has superclass members sc, then data members corresponding to that, and then its mc; its own. Then, this will be of course similar Object layout for sc; that is, this particular class which has only x. It has only sc data members, which is just x Please see the order in which this data is laid out When there is no inheritance, we have just our own class instance variables When there is one level of inheritance, then we have the superclass data members followed by our own data members. When there is two levels of inheritance, we have the grandfather superclass data members, then father superclass

members, and finally, our own class data members So, this is the order in which the objects are all laid out Now, the problem is – an instance variable has the same offset in every class where it exists in its superclass. So, sc will always be present in this area, mc will always be present after sc, and giant will always be present after sc and mc. So, this is the order in which the data will be laid out, irrespective of any other inheritance as well. If it was not giant, but it was some other class say – a, then we would have sc, then mc, and then a. If there were to be some other class, which inherits from giant say – b, then the data area of b would have been attached here Methods tables are similar, which we already showed. This was the method table. We have the methods of the superclass. For example, if you take this, there are methods from superclass, and then our own methods, and things of that kind Now, when a class redefines a method defined in one of its superclasses, it is very easy, just the method pointer for that method implementation must be stored in the same offset as the previous implementation of Just replace it, nothing more than that really happens If you take this, there is no problem. For example, if fee is here, also fum is here So, fee is being redefined here. I would possibly have a new pointer here. So, whatever fee was pointing to here will not be pointed to by this, a new method pointer will be placed in the same location. However, the order is important. So, that is a very important thing that we need to notice Now, what happens is – for example, when we have a method that belongs to the giant class, all these classes would have been compiled together. So, there is absolutely no problem. If we pass this pointer, all the data members would be accessed appropriately When the method of the class mc is called, we still pass the same pointers. Since the data area is ordered with the first superclass, second superclass, third superclass, etcetera in that order, the methods can actually access these data members appropriately. There is absolutely no problem as far as accessing it. Every time we pass this particular pointer to this object and since the data layout is the same, everywhere the methods can access the variables and execute appropriately This is not the same in the case of multiple inheritance. Let us see what happens in multiple inheritance Here is the picture. Here is class c, it inherits from both class a and class b. So, there are two classes from which it inherits. It has a method fie, which is from class a, which has a method foe, which is from class b, and it has a method fum, which is again from class b and there is a method fee, which is its own. So, these are the method tables of the new class c Assume that c inherits from classes a and b, but that a and b are unrelated. We saw this already. These two are not related Assume that class c implements fee, inherits fie from a, and inherits foe and fum from b. This is something I explained Now, look at the object layouts for that of class a. Here is class a it is not inheriting from any other class. Class b is also not inheriting from any other class. Only class c inherits both from a and from b For class a objects, we have a class pointer and then the data members of a; no problem For class b, which is independent and unrelated to class a, there is a class pointer and then the data members of b. The trouble starts with class c Class c inherits both from a and b. So, should

we place a’s data members first or b’s data members first? c’s data members will always come after the members of a and b. So, that is not an issue. Should a come first or b come first? The trouble will be – if we have a method of class c, which is inherited from a and it is called, then the pointer to this object is passed here So, it will expect that the data members of a appear here. That is because, it works with the layout of objects for class a, which the members are right here So, it expects that the members of a are right here However, if we call a method from c, which belongs to b, it expects similarly, the b data members immediately after the class pointer That is, in this area because that is the way it is happening in the objects of class b. However, if you place b here, then the method call of a will be inappropriate. If you place b here, then the methods call of b will be inappropriate. c will always work properly because it is always after a and b. How to solve this problem? That is what is mentioned here. When c dot fie inherited from a is invoked with an object layout as here, it finds all of a’s instance variables at the correct offsets. No problem at all. Since fie was compiled with class a, it will not find and cannot access the other instance variables present in the object and hence works correctly. So, there is no problem; c dot fie will work well because all these were compiled together Similarly, c dot fee also works correctly implemented in c because we are assuming that a is first and then b. So, that is why this c dot fie works properly. c dot fee also works properly because everything were compiled together, a and b are placed, and then c is placed However, c dot foe or c dot fum will not be proper. So, c dot foe or c dot fum are from class b. With this arrangement, as I mentioned, b is supposed to be expected here but b is here. Therefore, it will not work properly foe and fum are inherited from b, but invoked from an object of class c. Instance variables of class b are in the wrong place in this object record sandwiched between the instance variables of classes a and c. In objects of class b, the instance variables are at the start of the object record. They should have been here Hence, the offset to the instance variables of class b inside the object record of class c is unknown. So, this is a problem Where is b? The solution to this problem is – to compensate this, for this, the compiler must insert code to adjust the receiver pointer so that it points to the middle of the object record, that is, to the beginning of b’s instance variables What we are saying is – if we know that this is the beginning of b, which we will know If this is the layout, we know how many data members are here. So, we will know what is the offset; this offset plus this offset will be known to us. If we make sure that we point the object pointer to this particular point inside this record and then call the methods of class b, everything will work out very well because these data members are expected to be in the beginning. So, if we point the pointer here, this will be the first set of data members and it will work correctly. How do we do this? One is called the fixed offset method. Record the constant offset in the method table along with the methods. For example, for c, the offset of fee is 0 because c was compiled along with a and b. So, we can pass this pointer itself and everything will work properly This is the extra offset. For fie, which is a’s method and again the offset is 0 because a’s data members are always here and a expects that they are in this place; so, nothing wrong Only b creates a problem. For b, the offset is 8 both for foe and for fum. Assuming that the variables of class a take 8 bytes; that is, this portion requires 8 bytes That is

the assumption The generated code adds this offset to the receiver’s pointer address before invoking the method. So, if you are pointing here we add this and then it will point here. Now, everything works well That is, data pointer for c dot foe is pointing to this point; otherwise, it will have pointed to this and then we would have had a problem So, this was actually adding this offset Whatever offset I showed here, this 8 was added and instruction was generated to add this offset to the receiver’s pointer address and then call the method The other is what is known as a trampoline function. We create a trampoline function for each method of class b. For example, a function that increments this pointer that is the pointer to the receiver by the required offset and then invokes the actual method from b. So, we were doing it by an explicit instruction, but now, we have a special function that increments the pointer by the required amount and then invokes the actual method from b. So, this is just using an extra function On return, it decrements the receiver pointer if it was passed by reference and then gets back Now, you may wonder whether this is efficient at all. Trampolines seem to appear to be more expensive than the fixed offset method. Is that so? However, not really so. For example, they are used only for calls to method inherited from b, whereas the other method – fixed offset method, the offset possibly 0 was added for all calls. Whether it was from a or from c, the offset was added, you added a 0 and then that instruction was any way executed, whereas here, we do it only for the methods of b Method inlining will make it better than option 1, since the offset is a constant. So, we do not have to take it out from any table like in the previous case, this is actually a constant. So, inlining will make sure that you use a constant addressing mode, which you can utilize a constant operand. Since it is used only for the methods of b, this may be quite efficient A duplicate class pointer pointing to class c may need to be inserted just before the instance variables of b. Let me show why? For example, if we had been pointing to this place when we have class to the methods of a or c, what we really need to do is -when we call the methods of b, we insert this class pointer here. We insert this here and then point it to the beginning of the class pointer and call it so that it looks exactly like this. It is as if we are calling something of an object of class b is being passed on So, this is more for convenience not exactly essential for the operation At this point, we will close this lecture and in the next lecture, we will look at some optimizations, which can be performed on object-oriented language programs Thank you

You Want To Have Your Favorite Car?

We have a big list of modern & classic cars in both used and new categories.