/******************************************************************************
Author - Kiran Seth
	Below I have started to describe the timing analyzer as I start to 
understand how it works together. I will try to keep adding to this file till
I have each and every function figured out.

VERSION 1.0
*******************************************************************************/

THE TIMING ANALYZER
===================

	The main function is in a file that interfaces the prolog and the C code.
The main calls the time_main function in the time.c file. The time.c is the most
important file for the timing analyzer.

	The time_main function is where the action begins for timing analyzer.
	This function defines all the important globals. The function reads the 
command line and sets various variables that control the analysis, making it cache
only or pipeline only, etc. The Determine_Inst_Set() is called to read the file
that holds the instruction set information.In this function, the file name for the
file containing instruction timing information is hard-coded (instset.sparc/ 
instset.pisa). The file is read and the numbers for instructions for the different
stages are put into a linked list of structures. This information is then put into
the instructions read from the inf file.  

	Then the Process_INF_File() calls the inf file read from the command line. 
This function also takes in a pointer to a structure. This pointer (inf) is used to 
create the linked list of instructions from inf file. In the inf file, first the 
function name is read, followed by the time structure(which is never seen), the loop
structure and then the block structure. The instruction types are in the block structure
are more info about them is obtained from the structure got from the Determin_Inst...
function.

	After forming the inf linked list for all functions, the block_constraints func
is called. This function plays around with the CFG information about infeasible paths
but the information required is not produced since not compiler is available.The info
would have been in the inf file.

	Then comes the function Create_Timing_Paths. This function is responsible for 
finding all the possible paths through the function.First thing that the func does is
call Create_Loop_Nodes. The CLNs finds the max nesting level. It then searches through
the loops found from the inf file in the inf LL to find the max nested loop and calls
Create_Loop_Node (notice singular). It is assumed that there is at least one path 
through a loop so a node can be made no matter what. The CLNs concentrates on finding 
all possible paths for the loop. HERE I TAKE A LEAP OF FAITH ABOUT THE ALGORITHM.
Next the function calls Create_Path_Element. AGAIN I BLINDLY ASSUME THAT AT THE END
OF THIS FUNCTION ALL POSSIBLE PATHS THROGH THE FUNCTION ARE KNOWN.

	Next the Build_Timing_Tree is called. This func opens the ist file to read
the cache categorizations (done by func Process_STATS_File). This information goes into
the timing_tree linked list. This LL is in the form of a tree.The Process_ST.. func 
makes LL of functions and cache categ for the instrs. Create_Loops are used to create
the loops since only funcs are present so far. In CL the loops are added to their parent 
loop nodes. Then Move_Inst_To_Correct_Loop_Nodes is called. This function takes a func
node and looks at all instrs in the func and moves it to the corresponding child node.
Then the Create_Tree func is called. The instructions of func node are looked at and 
moved to new child nodes as required. Note that while making nodes, the inf LL is 
searched to find the func and a link is made between node and inf info. Similiarly 
loop path info is also found and linked to.

SO AT THIS STAGE YOU HAVE 2 LL-> inf and timing_tree. inf has all the inf file info
and instruction delays for all stages of pipeline. The timing_tree has the cache
categorizations in a tree form and also each node is matched up with corresponding inf
info.

	Batch_Time is called. This func calls the worst case and best case timing 
functions. Both these functions in turn call the Time_Path func which is the func
that does all the work of calculating delaly of a path. BT looks at each node and 
if all children of the node are timed, it is sent to TWC. In TWC first we calculate 
times for all paths assuming all fm and fh as misses. max_pipeline is calculated
parallely. It is then done again for the first continue or exit path using fm as hit 
and fh as miss. Now for all paths, if previous fm and fh status changed, calculate the
time again with fm as hit and fh as miss. The same is done again in an infinite while
loop, only it is done no matter what the previous status. blah blah.....

	The Time_Path function is the most important function in the timing analyzer. 
The function goes through all the instructions in the path specified and returns the
number of cycles that will be required for the path. Following comments about the 
algorithm are found in the file.
1. initialize path's begin and end arrays - made global vars 
2. count how many instructions are in the path so that we can contiguously
   allocate some arrays which we use only for this path 
3. Allow user interface to time a subpath. (6/1)
       If we are not timing a subpath, beg_block and end_block will each
       be zero and we can skip this step.
       Block numbers are not necessarily sequential in the path, but the
       instruction numbers within a block are.  We have decided to number
       the inst in a block starting with zero, so NO_INST is -1.
4. Process each instruction in this path.
5. We need to address a possible data hazard.  Let A be the inst
   just before the inner loop, and let B be the 1st inst in the inner loop.
   I assume that between A and B there can be at most one kind of data hazard.
   a) B is a typical int/flop, not a load or store, and needs a register 
      operand in order to execute.  If A's destination is (either of) B's
      src operands, B leaves ID when A finishes EX or FPEX. (shouldn't stall)
   b) On the other hand, A may be a load instruction, in which case the
      destination isn't known until A's CA stage, so B leaves ID when A
      leaves CA.
   c) If B is a store inst, and B's src is A's dest, then B leaves the EX
      when A leaves FPEX.  This data hazard can only happen for flop reg's
      because in the integer pipeline, B would have to wait for A in EX,
      a structural hazard.
   d) If A is a cmp (cond code 1) and B is a branch inst (cond code 2),
      and they refer to the same (int or flop) cc, B finishes ID when A
      finishes EX.                    
6. A new way to insert the child loop/function, examining the stages l->r
   Structural hazard with the current path, data hazard with the current path
   and the child's beginning pipeline requirements
7. Let me explain... We first update the cycle time for our path taking
   into consideration this inner loop.  For each pipeline stage, find the
   minimum sum of the end-cycles for the path before the inner loop and
                  the beg-cycles for the inner loop
   This min sum is called "cycle_diff".  "old_path_cycles" stores the path's
   time before we alter it.
   The inner loop's first inst can begin to fetch at
     old_path_cycles - cycle_diff + 3
   And this means the new value of path_cycles should be
     old_path_cycles - cycle_diff + 2 + time of the inner loop.  
   Next we need to update path_beg_cycles and beg_occupant for a particular
   stage if the inner loop has an inst using this stage whereas the outer loop
   so far has not.  We find the time the stage is first occupied relative to
   when the 1st inst starts to fetch, and add this to the path-time when 
   the 1st inst starts to fetch.      
8. Function calls need to be handled in a similar way as we did the
      inner loops.  
9. For each instruction, find its condition code (1 for a compare, 2 for a
   branch and 0 otherwise) and also keep track of whether it's a flop.
10. Find out the inst category so we can assess any applicable penalty.
11. next, let's determine the correct data size, whether to use SINGLE_SIZE
   or DOUBLE_SIZE.  For integer instructions, it doesn't matter.  For most
   flops, we can look at inf_inst_ptr->data_type, execpt for conversions 
12. use a special variable that just holds the end cycles for the current
   instruction being added to the path  
13. look at the DC miss penalty (11/7) this makes the stages before
       the CA further back in time if this is a load or store 
14. when we are wc naive, there is no pipeline overlap possible
        and all instructions are misses
15. for a fp load, we have to change course to finish in FWB instead of WB
       CA-times for loads and stores are not always the same.
16. Establish the beginning cycles for this inst for step 10
17. now find out about this instruction's destination register:
     initialize values of dest_ready and dest_reg for this instruction
18. Find out about the src reg(s) too
19. just initializing our path numbers (then go to step 28) [FOR 1st instr]
20.  Handle data hazards that occur as we resume with outer loop [FOR rest]
21. This inst will finish IF at the same time the previous instruction
   finished its ID.  We also assume that this instruction will finish its ID
   1 cycle later, which may soon change.
   If prev inst only fetched, our IF end time is 1 cycle later than prev's 
22. if I'm a flop, then I leave the ID stage the same time as the previous
   flop (whenever that was) leaves FPEX, or end IF + 1, WHICHEVER IS LATER.
   If there was no previous flop, leave ID 1 cycle after leaving IF
   The same reasoning holds for an integer instruction.    
23. Identify this instruction's source register(s) and find out at which
   cycle they are needed before continuing into the next stage.  (4/30) 
   NOTE: The delay due to a data hazard may coincide with a structural
         hazard.   
24. end_use ID may be later if we're waiting for a cond_code to be set 
   We look back to the last inst in which the cond code was set, as long
   as it was the same data size inst, and we finish ID when the compare 
   finishes the EX/FPEX 
25. handle end of EX and CA, similar to the ID 
26. end_use of FPEX, WB, FWB
27. Now add this delay to the end_use of the latter stages 
28. Double loads take 2 cycles in CA (5/19) 
        The third test is not to add the second cycle if there was a
        structural hazard with a flop who had to go to FWB first 
29. Double stores take 3 cycles in CA
30. Data hazards can occur when a register is written to by an instruction 
   which is not an end occupant.  For this reason, we need to look at the
   "times" when registers are written to and needed, as we did in the
   simulator.  Now that we know the end_use time for this instruction,
   we can store this value as the "release time" of the register dest. (4/29)
   Release time is the time when the register becomes available as a potential
   source operand.   
31. after end_use determined, find begin_use...
   only begin use IF has a different definition depending on whether this
   is the 1st instruction in the path      (set in step 10)  
32. Keep track of the first time cc needed and last time used (5/16) 
       This info is used when this path is examined at a higher level.
33. now determine the last time someone finishes writing back
   so we can calculate the path_cycles up to this instruction
34. determine when each stage in this path is 1st occupied
   and who those pioneer occupants are
35. now print ALL the inst's beg and end times for EACH stage in a table
36. Find # of occupied cycles for each stage - only needed in bc
37. We need to jump over inner loops or functions so not to wait too long
       while counting unnecessary cycles in step 38
38. now print the pipeline
39. off to the side of the pipeline, print the instruction (op & operands)
   which we are showing as just beginning its IF in this cycle
40.  In the cached version, store this path's information.



	Now lets summarize the time_path function. First we initialize the
variables. Then we use the loopnode->path->path_list pointer to find the 
number of instrs in the path. Use this info to create arrays dynamically.
Now for each member of path_list, find the corresponding inf_bptr. For each
inf_bptr, find corresponding instruct_list. Go through the instruct_list
and for each instruction find corresponding stat_inst_ptr. If this pointer 
is NULL, we reached a loop or function call.
