MIPS Subprograms and StackSubprogram CommunicationCommunication ElementsMIPS Subprogram CallMIPS Return AddressMIPS Return ValuesMIPS ArgumentsMIPS Local DataMIPS Register Save AreaSimplest Function CallFunction Call With ArgumentsMore ArgumentsSaved RegistersLocal VariablesPushdown StackGeneral Stack UsageHardware Stack SupportMIPS Stack ImplementationMIPS Memory LayoutActivation RecordsMIPS Activation RecordsThe Stack FrameMIPS Stack FrameSubprogram Call/ReturnSubprogram Call SetupSubprogram EntrySubprogram ReturnSubprogram Call ReturnDynamic Storage AllocationSlide 30UpdatesCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-1MIPS Subprograms and StackCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-2Subprogram Communication•Subprogram calls require conventions–Established by computer designers–Include hardware and software support•Conventions facilitate communication–Same conventions for all programmers–Allow separately written program modules–Integrate all parts of subprogram call/returnCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-3Communication Elements•Subprogram call•Return address•Return values•Arguments•Local data•Register save areaCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-4MIPS Subprogram Call•Uses link instructions–jal Jump and Link: Most commonly used!–jalr Jump and Link Register–bltzal Branch if Less Than Zero and Link–bgezal Branch if Greater Than or Equal To Zero and Link•Hardware sets up return address•Automatically puts return address in raCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-5MIPS Return Address•Automatically stored by hardware•Points to next instruction after call•Stored in register ra by subprogram call instructionCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-6MIPS Return Values•Registers defined by software conventions•Two registers provided for values–v0–v1•Can also use reference parametersCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-7MIPS Arguments•Placed by software conventions•First four arguments in registers–a0–a1–a2–a3•Additional arguments in stackCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-8MIPS Local Data•Placed by software conventions•Statically allocated on subprogram call•Stored in stack•Space released on subprogram returnCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-9MIPS Register Save Area•Placed by software conventions•Statically allocated•Stored in stack•Two special registers–Return Address: Return point in caller–Frame Pointer: Base of stack frame•Two register regions–Caller saved registers–Callee saved registersCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-10Simplest Function Call•No arguments•No saved registers•No local variables•Call: jal fct–Return address put into ra–Control transfers to fct•Return: jr $ra–Control transfers to the address in ra (Caller)CS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-11Function Call With Arguments•No saved registers•No local variables•Put arguments in a0, a1, a2, and a3•Call:–Set arguments–jal fct•Return:–jr $raCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-12More Arguments•No saved registers•No local variables•Allocate space for arguments•Put 4 arguments in a0, a1, a2, and a3•Put additional arguments in the stack•Call the functionCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-13Saved Registers•No local variables•Allocate space for arguments and the Caller-Saved registers•Put 4 arguments in a0, a1, a2, and a3•Put additional arguments in the stack•Save the Caller-Saved registers (t0-t9)•Call the function•Allocate space for callee-saved registers•Save the Callee-Saved registers (s0-s7)CS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-14Local Variables•Allocate space for arguments and the Caller-Saved registers•Put 4 arguments in a0, a1, a2, and a3•Put additional arguments in the stack•Save the Caller-Saved registers (t0-t9)•Call the function•Allocate space for local variables and the Callee-Saved registers•Save the Callee-Saved registers (s0-s7)CS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-15Pushdown Stack•Last-in, first-out data structure–Access top element only–Push operation adds item to top of stack–Top operation returns value on top of stack–Pop operation removes item from top of stack–Pop sometimes includes TopData ItemData ItemData ItemData ItemTop of StackCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-16General Stack Usage•The primary use of a stack in a machine which has one is to support subprogram linkage and communication–Same conventions for all programmers–Allow separately written program modules–Integrate all parts of subprogram call/returnCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-17Hardware Stack Support•Stack is implemented in memory–Usually at opposite end of data–Data and stack allocation can eventually meet–Hardware may or may not detect overlap•Stack is accessed by a stack pointer–Memory location held in a register–Points to top of stack–Updated on push or pop–Used to access stack items by offsetCS 33: Computer OrganizationTopic 8: MIPS Subprograms and Stack4/2009 John A. Rohr All Rights ReservedJAR 8-18MIPS Stack Implementation•Special area of memory: stack segment–Begins at high end of area–Allocates toward lower addresses•Accessed by stack