------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- Cheddar is a GNU GPL real-time scheduling analysis tool. -- This program provides services to automatically check schedulability and -- other performance criteria of real-time architecture models. -- -- Copyright (C) 2002-2016, Frank Singhoff, Alain Plantec, Jerome Legrand -- -- The Cheddar project was started in 2002 by -- Frank Singhoff, Lab-STICC UMR 6285 laboratory, Université de Bretagne Occidentale -- -- Cheddar has been published in the "Agence de Protection des Programmes/France" in 2008. -- Since 2008, Ellidiss technologies also contributes to the development of -- Cheddar and provides industrial support. -- -- The full list of contributors and sponsors can be found in AUTHORS.txt and SPONSORS.txt -- -- This program is free software; you can redistribute it and/or modify -- it under the terms of the GNU General Public License as published by -- the Free Software Foundation; either version 2 of the License, or -- (at your option) any later version. -- -- This program is distributed in the hope that it will be useful, -- but WITHOUT ANY WARRANTY; without even the implied warranty of -- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -- GNU General Public License for more details. -- -- You should have received a copy of the GNU General Public License -- along with this program; if not, write to the Free Software -- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA -- -- -- Contact : cheddar@listes.univ-brest.fr -- ------------------------------------------------------------------------------ -- Last update : -- $Rev: 1249 $ -- $Date: 2014-08-28 07:02:15 +0200 (Fri, 28 Aug 2014) $ -- $Author: singhoff $ ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ with Ada.Exceptions; use Ada.Exceptions; with CFG_Nodes; use CFG_Nodes; with CFG_Nodes; use CFG_Nodes.CFG_Nodes_Table_Package; with CFG_Node_Set; use CFG_Node_Set; with Basic_Blocks; use Basic_Blocks; with Basic_Blocks; use Basic_Blocks.Basic_Blocks_Table_Package; with Objects; use Objects; with Objects.extended; use Objects.extended; with Text_IO; use Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Integer_Arrays; use Integer_Arrays; with Translate; use Translate; with Tables; with sets; with CFG_Edge_Set; use CFG_Edge_Set; with CFG_Edges; use CFG_Edges; package body CFG_Node_Set.Basic_Block_Set is ---------------------------------------------------- -- CHECK - BASIC_BLOCK ---------------------------------------------------- procedure Check_Basic_Block (name : in Unbounded_String; node_type : in CFG_Node_Type; graph_type : in CFG_Graph_Type; instruction_offset : in Integer; instruction_capacity : in Integer; data_offset : in Integer; data_capacity : in Integer; loop_bound : in Integer) is begin if (name = "") then Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_CFG_Node (Current_Language) & Lb_Mandatory (Current_Language))); end if; if not Is_A_Valid_Identifier (Name) then Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_CFG_Node (Current_Language) & Name & " : " & Lb_CFG_Node_Name (Current_Language) & Lb_Colon & Lb_Invalid_Identifier (Current_Language))); end if; if instruction_offset < 0 then Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_CFG_Node (Current_Language) & " " & Name & " : " & Lb_Instruction_Offset (Current_Language) & Lb_Must_Be (Current_Language) & To_Unbounded_String (" >= 1"))); end if; if instruction_capacity < 0 then Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_CFG_Node (Current_Language) & " " & Name & " : " & Lb_Instruction_Capacity (Current_Language) & Lb_Must_Be (Current_Language) & To_Unbounded_String (" >= 1"))); end if; if data_offset < 0 then Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_CFG_Node (Current_Language) & " " & Name & " : " & Lb_Data_Offset (Current_Language) & Lb_Must_Be (Current_Language) & To_Unbounded_String (" >= 1"))); end if; if data_capacity < 0 then Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_CFG_Node (Current_Language) & " " & Name & " : " & Lb_Data_Capacity (Current_Language) & Lb_Must_Be (Current_Language) & To_Unbounded_String (" >= 1"))); end if; end Check_Basic_Block; ---------------------------------------------------- -- ADD - BASIC_BLOCK ---------------------------------------------------- procedure Add_Basic_Block (my_basic_blocks : in out Basic_Blocks_Set; a_basic_block : in out Basic_Block_Ptr; name : in Unbounded_String; node_type : in CFG_Node_Type; graph_type : in CFG_Graph_Type; instruction_offset : in Integer; instruction_capacity : in Integer; data_offset : in Integer; data_capacity : in Integer; loop_bound : in Integer) is my_iterator : Basic_Blocks_Iterator; begin Check_Basic_Block(name, node_type, graph_type, instruction_offset, instruction_capacity, data_offset, data_capacity, loop_bound); if (get_number_of_elements (my_basic_blocks) > 1) then reset_iterator(my_basic_blocks,my_iterator); loop current_element(my_basic_blocks,a_basic_block,my_iterator); if(name = a_basic_block.name) then Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_CFG_Node (Current_Language) & " " & Name & " : " & Lb_CFG_Node_Name (Current_Language) & Lb_Already_Defined (Current_Language))); end if; exit when is_last_element (my_basic_blocks, my_iterator); next_element (my_basic_blocks, my_iterator); end loop; end if; a_basic_block := new Basic_Block; a_basic_block.instruction_offset := instruction_offset; a_basic_block.instruction_capacity := instruction_capacity; a_basic_block.data_offset := data_offset; a_basic_block.data_capacity := data_capacity; a_basic_block.loop_bound := 0; a_basic_block.name := name; -- a_basic_block.previous_nodes := previous_nodes; -- a_basic_block.next_nodes := next_nodes; a_basic_block.node_type := node_type; a_basic_block.graph_type := graph_type; add(my_basic_blocks,a_basic_block); exception when CFG_Node_Set.full_set => Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_Can_Not_Define_More_CFG_Node (Current_Language))); end Add_Basic_Block; procedure Add_Basic_Block (my_basic_blocks : in out Basic_Blocks_Set; name : in Unbounded_String; node_type : in CFG_Node_Type; graph_type : in CFG_Graph_Type; instruction_offset : in Integer; instruction_capacity : in Integer; data_offset : in Integer; data_capacity : in Integer; loop_bound : in Integer) is a_basic_block : Basic_Block_Ptr; begin Add_Basic_Block(my_basic_blocks => my_basic_blocks, a_basic_block => a_basic_block, name => name, node_type => node_type, graph_type => graph_type, instruction_offset => instruction_offset, instruction_capacity => instruction_capacity, data_offset => data_offset, data_capacity => data_capacity, loop_bound => loop_bound); exception when CFG_Node_Set.full_set => Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_Can_Not_Define_More_CFG_Node (Current_Language))); end Add_Basic_Block; ------------------------------------------------------ -- UPDATE - BASIC_BLOCK ------------------------------------------------------ procedure Update_Basic_Block (my_basic_blocks : in out Basic_Blocks_Set; name : in Unbounded_String; node_type : in CFG_Node_Type; graph_type : in CFG_Graph_Type; instruction_offset : in Integer; instruction_capacity : in Integer; data_offset : in Integer; data_capacity : in Integer; loop_bound : in Integer) is a_basic_block : Basic_Block_Ptr; begin a_basic_block := Search_Basic_Block(my_basic_blocks,name); Delete_Basic_Block(my_basic_blocks,a_basic_block); Add_Basic_Block(my_basic_blocks => my_basic_blocks, a_basic_block => a_basic_block, name => name, node_type => node_type, graph_type => graph_type, instruction_offset => instruction_offset, instruction_capacity => instruction_capacity, data_offset => data_offset, data_capacity => data_capacity, loop_bound => loop_bound); end Update_Basic_Block; ---------------------------------------------------- -- ADD - (CFG_NODE) BASIC_BLOCK ---------------------------------------------------- procedure Add_CFG_Node (my_cfg_nodes : in out CFG_Nodes_Set; a_cfg_node : in out CFG_Node_Ptr; name : in Unbounded_String; node_type : in CFG_Node_Type; graph_type : in CFG_Graph_Type; instruction_offset : in Integer; instruction_capacity : in Integer; data_offset : in Integer; data_capacity : in Integer; loop_bound : in Integer) is my_iterator : CFG_Nodes_Iterator; new_basic_block : Basic_Block_Ptr; begin Check_Basic_Block(name, node_type, graph_type, instruction_offset, instruction_capacity, data_offset, data_capacity, loop_bound); if (get_number_of_elements (my_cfg_nodes) > 1) then reset_iterator(my_cfg_nodes,my_iterator); loop current_element(my_cfg_nodes,a_cfg_node,my_iterator); if(name = a_cfg_node.name) then Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_CFG_Node (Current_Language) & " " & Name & " : " & Lb_CFG_Node_Name (Current_Language) & Lb_Already_Defined (Current_Language))); end if; exit when is_last_element (my_cfg_nodes, my_iterator); next_element (my_cfg_nodes, my_iterator); end loop; end if; new_basic_block := new Basic_Block; new_basic_block.instruction_offset := instruction_offset; new_basic_block.instruction_capacity := instruction_capacity; new_basic_block.data_offset := data_offset; new_basic_block.data_capacity := data_capacity; new_basic_block.loop_bound := 0; a_cfg_node := CFG_Node_Ptr (new_basic_block); a_cfg_node.name := name; -- a_cfg_node.previous_nodes := previous_nodes; -- a_cfg_node.next_nodes := next_nodes; a_cfg_node.node_type := node_type; a_cfg_node.graph_type := graph_type; add(my_cfg_nodes,a_cfg_node); exception when CFG_Node_Set.full_set => Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_Can_Not_Define_More_CFG_Node (Current_Language))); end Add_CFG_Node; procedure Add_CFG_Node (my_cfg_nodes : in out CFG_Nodes_Set; name : in Unbounded_String; node_type : in CFG_Node_Type; graph_type : in CFG_Graph_Type; instruction_offset : in Integer; instruction_capacity : in Integer; data_offset : in Integer; data_capacity : in Integer; loop_bound : in Integer) is a_cfg_node : CFG_Node_Ptr; begin Add_CFG_Node(my_cfg_nodes => my_cfg_nodes, a_cfg_node => a_cfg_node, name => name, node_type => node_type, graph_type => graph_type, instruction_offset => instruction_offset, instruction_capacity => instruction_capacity, data_offset => data_offset, data_capacity => data_capacity, loop_bound => loop_bound); exception when CFG_Node_Set.full_set => Raise_Exception (Invalid_Parameter'Identity, To_String (Lb_Can_Not_Define_More_CFG_Node (Current_Language))); end Add_CFG_Node; ------------------------------------------------------ -- SEARCH ------------------------------------------------------ function Search_Basic_Block (my_basic_blocks : in Basic_Blocks_Set; name : in Unbounded_String) return Basic_Block_Ptr is my_iterator : Basic_Blocks_Iterator; a_basic_block : Basic_Block_Ptr; result : Basic_Block_Ptr; found : Boolean := False; begin if not is_empty(my_basic_blocks) then reset_iterator(my_basic_blocks,my_iterator); loop current_element (my_basic_blocks, a_basic_block, my_iterator); if (a_basic_block.name = name) then found := True; result := a_basic_block; end if; exit when is_last_element (my_basic_blocks,my_iterator); next_element (my_basic_blocks,my_iterator); end loop; end if; if not Found then Raise_Exception (CFG_Node_Not_Found'Identity, To_String (Lb_CFG_Node_Name (Current_Language) & "=" & Name)); end if; return Result; end Search_Basic_Block; function Search_Basic_Block_By_Id (my_basic_blocks : in Basic_Blocks_Set; id : in Unbounded_String) return Basic_Block_Ptr is my_iterator : Basic_Blocks_Iterator; a_basic_block : Basic_Block_Ptr; result : Basic_Block_Ptr; found : Boolean := False; begin if not is_empty(my_basic_blocks) then reset_iterator(my_basic_blocks,my_iterator); loop current_element (my_basic_blocks, a_basic_block, my_iterator); if (a_basic_block.cheddar_private_id = id) then found := True; result := a_basic_block; end if; exit when is_last_element (my_basic_blocks,my_iterator); next_element (my_basic_blocks,my_iterator); end loop; end if; if not Found then Raise_Exception (CFG_Node_Not_Found'Identity, To_String (Lb_CFG_Node_Name (Current_Language) & "=" & id)); end if; return Result; end Search_Basic_Block_By_Id; ------------------------------------------------------ -- DELETE ------------------------------------------------------ procedure Delete_Basic_Block (my_basic_blocks : in out Basic_Blocks_Set; a_basic_block : in out Basic_Block_Ptr) is begin delete (my_basic_blocks, a_basic_block); end Delete_Basic_Block; procedure Delete_Basic_Block (my_basic_blocks : in out Basic_Blocks_Set; name : in Unbounded_String) is a_basic_block : Basic_Block_Ptr; begin a_basic_block := Search_Basic_Block(my_basic_blocks, name); delete (my_basic_blocks, a_basic_block); end Delete_Basic_Block; ------------------------------------------------------ -- NEXT, PREVIOUS ------------------------------------------------------ procedure Add_Next_Basic_Block (my_basic_blocks : in out Basic_Blocks_Set; name : in Unbounded_String; next_block_name : in Unbounded_String) is a_basic_block : Basic_Block_Ptr; a_next_basic_block : Basic_Block_Ptr; begin a_basic_block := Search_Basic_Block(my_basic_blocks,name); a_next_basic_block := Search_Basic_Block(my_basic_blocks,next_block_name); add(Basic_Block_Ext_Ptr(a_basic_block).next_nodes,CFG_Node_Ptr(a_next_basic_block)); end Add_Next_Basic_Block; procedure Add_Next_Basic_Block_By_Id (my_basic_blocks : in out Basic_Blocks_Set; a_basic_block : in out Basic_Block_Ptr; next_block_id : in Unbounded_String) is a_next_basic_block : Basic_Block_Ptr; begin a_next_basic_block := Search_Basic_Block_By_Id(my_basic_blocks,next_block_id); add(Basic_Block_Ext_Ptr(a_basic_block).next_nodes,CFG_Node_Ptr(a_next_basic_block)); end Add_Next_Basic_Block_By_Id; procedure Add_Previous_Basic_Block (my_basic_blocks : in out Basic_Blocks_Set; name : in Unbounded_String; previous_block_name : in Unbounded_String) is a_basic_block : Basic_Block_Ptr; a_previous_basic_block : Basic_Block_Ptr; begin a_basic_block := Search_Basic_Block(my_basic_blocks,name); a_previous_basic_block := Search_Basic_Block(my_basic_blocks,previous_block_name); add(Basic_Block_Ext_Ptr(a_basic_block).previous_nodes,CFG_Node_Ptr(a_previous_basic_block)); end Add_Previous_Basic_Block; procedure Add_Previous_Basic_Block_By_Id (my_basic_blocks : in out Basic_Blocks_Set; a_basic_block : in out Basic_Block_Ptr; previous_block_id : in Unbounded_String) is a_previous_basic_block : Basic_Block_Ptr; begin a_previous_basic_block := Search_Basic_Block_By_Id(my_basic_blocks,previous_block_id); add(Basic_Block_Ext_Ptr(a_basic_block).previous_nodes,CFG_Node_Ptr(a_previous_basic_block)); end Add_Previous_Basic_Block_By_Id; procedure Set_Previous_Basic_Blocks (my_basic_blocks : in out Basic_Blocks_Set) is my_iterator : Basic_Blocks_Iterator; a_basic_block : Basic_Block_Ptr; begin reset_iterator(my_basic_blocks,my_iterator); loop current_element(my_basic_blocks,a_basic_block,my_iterator); for i in 0..Basic_Block_Ext_Ptr(a_basic_block).next_nodes.Nb_Entries-1 loop Add_Previous_Basic_Block(my_basic_blocks => my_basic_blocks, name => Basic_Block_Ext_Ptr(a_basic_block).next_nodes.Entries(i).name, previous_block_name => a_basic_block.name); end loop; exit when is_last_element (my_basic_blocks, my_iterator); next_element (my_basic_blocks, my_iterator); end loop; end Set_Previous_Basic_Blocks; ---------------------------------------------------- -- CONVERT ---------------------------------------------------- procedure Convert_To_Basic_Block_UCB_Set (my_cfg_nodes : in out CFG_Nodes_Set; my_cfg_edges : in out CFG_Edges_Set; size : in Integer) is a_cfg_node_ucb : Basic_Block_Ptr; a_cfg_basic_block : Basic_Block_Ptr; cfg_ucb_basic_blocks_set : CFG_Nodes_Set; new_basic_block_ucb : Basic_Block_UCB_Ptr; my_iterator : CFG_Nodes_Iterator; a_cfg_node : CFG_Node_Ptr; temp_cfg_node : CFG_Node_Ptr; begin reset_iterator(my_cfg_nodes,my_iterator); loop current_element(my_cfg_nodes,a_cfg_node,my_iterator); new_basic_block_ucb := new Basic_Block_UCB; new_basic_block_ucb.GenCBR.Elements := new Integer_Arr (0..size-1); new_basic_block_ucb.GenCBR.Size := size; new_basic_block_ucb.GenCBL.Elements := new Integer_Arr (0..size-1); new_basic_block_ucb.GenCBL.Size := size; new_basic_block_ucb.RMBIn := new Basic_Block_UCB_Arr (0..size-1); new_basic_block_ucb.RMBOut := new Basic_Block_UCB_Arr (0..size-1); new_basic_block_ucb.LMBIn := new Basic_Block_UCB_Arr (0..size-1); new_basic_block_ucb.LMBOut := new Basic_Block_UCB_Arr (0..size-1); new_basic_block_ucb.NumberOfUsefulBlock := 0; for i in 0..size-1 loop new_basic_block_ucb.RMBIn(i).Size := 0; new_basic_block_ucb.RMBIn(i).Elements := new Integer_Arr(0..0); new_basic_block_ucb.RMBOut(i).Size := 0; new_basic_block_ucb.RMBOut(i).Elements := new Integer_Arr(0..0); new_basic_block_ucb.LMBIn(i).Size := 0; new_basic_block_ucb.LMBIn(i).Elements := new Integer_Arr(0..0); new_basic_block_ucb.LMBOut(i).Size := 0; new_basic_block_ucb.LMBOut(i).Elements := new Integer_Arr(0..0); end loop; a_cfg_basic_block := Basic_Block_Ptr(a_cfg_node); a_cfg_node_ucb := Basic_Block_Ptr(new_basic_block_ucb); a_cfg_node_ucb.data_offset := a_cfg_basic_block.data_offset; a_cfg_node_ucb.data_capacity := a_cfg_basic_block.data_capacity; a_cfg_node_ucb.instruction_offset := a_cfg_basic_block.instruction_offset; a_cfg_node_ucb.instruction_capacity := a_cfg_basic_block.instruction_capacity; a_cfg_node_ucb.loop_bound := a_cfg_basic_block.loop_bound; temp_cfg_node := CFG_Node_Ptr(a_cfg_node_ucb); temp_cfg_node.cheddar_private_id := a_cfg_basic_block.cheddar_private_id; temp_cfg_node.name := a_cfg_basic_block.name; -- temp_cfg_node.previous_nodes := a_cfg_basic_block.previous_nodes; -- temp_cfg_node.next_nodes := a_cfg_basic_block.next_nodes; temp_cfg_node.graph_type := a_cfg_basic_block.graph_type; temp_cfg_node.node_type := a_cfg_basic_block.node_type; add(cfg_ucb_basic_blocks_set,temp_cfg_node); exit when is_last_element (my_cfg_nodes, my_iterator); next_element (my_cfg_nodes, my_iterator); end loop; my_cfg_nodes := cfg_ucb_basic_blocks_set; end Convert_To_Basic_Block_UCB_Set; procedure Convert_To_Basic_Block_UCB_Set (my_basic_blocks : in out Basic_Blocks_Set; my_cfg_edges : in out CFG_Edges_Set; size : in Integer) is a_basic_block_ucb : Basic_Block_Ptr; ucb_basic_blocks : Basic_Blocks_Set; my_iterator : Basic_Blocks_Iterator; my_iterator_edg : CFG_Edges_Iterator; a_basic_block : Basic_Block_Ptr; a_cfg_edge : CFG_Edge_Ptr; new_basic_block_ucb : Basic_Block_UCB_Ptr; bl1 : Basic_Block_Ptr; bl2 : Basic_Block_Ptr; begin reset_iterator(my_basic_blocks,my_iterator); loop current_element(my_basic_blocks,a_basic_block,my_iterator); new_basic_block_ucb := new Basic_Block_UCB; new_basic_block_ucb.GenCBR.Elements := new Integer_Arr (0..size-1); new_basic_block_ucb.GenCBR.Size := size; new_basic_block_ucb.GenCBL.Elements := new Integer_Arr (0..size-1); new_basic_block_ucb.GenCBL.Size := size; new_basic_block_ucb.RMBIn := new Basic_Block_UCB_Arr (0..size-1); new_basic_block_ucb.RMBOut := new Basic_Block_UCB_Arr (0..size-1); new_basic_block_ucb.LMBIn := new Basic_Block_UCB_Arr (0..size-1); new_basic_block_ucb.LMBOut := new Basic_Block_UCB_Arr (0..size-1); new_basic_block_ucb.NumberOfUsefulBlock := 0; initialize(new_basic_block_ucb.UCBs); for i in 0..size-1 loop new_basic_block_ucb.RMBIn(i).Size := 0; new_basic_block_ucb.RMBIn(i).Elements := new Integer_Arr(0..0); new_basic_block_ucb.RMBOut(i).Size := 0; new_basic_block_ucb.RMBOut(i).Elements := new Integer_Arr(0..0); new_basic_block_ucb.LMBIn(i).Size := 0; new_basic_block_ucb.LMBIn(i).Elements := new Integer_Arr(0..0); new_basic_block_ucb.LMBOut(i).Size := 0; new_basic_block_ucb.LMBOut(i).Elements := new Integer_Arr(0..0); end loop; a_basic_block_ucb := Basic_Block_Ptr(new_basic_block_ucb); a_basic_block_ucb.cheddar_private_id := a_basic_block.cheddar_private_id; a_basic_block_ucb.name := a_basic_block.name; a_basic_block_ucb.data_offset := a_basic_block.data_offset; a_basic_block_ucb.data_capacity := a_basic_block.data_capacity; a_basic_block_ucb.instruction_offset := a_basic_block.instruction_offset; a_basic_block_ucb.instruction_capacity := a_basic_block.instruction_capacity; a_basic_block_ucb.loop_bound := a_basic_block.loop_bound; a_basic_block_ucb.node_type := a_basic_block.node_type; a_basic_block_ucb.graph_type := a_basic_block.graph_type; add(ucb_basic_blocks,a_basic_block_ucb); exit when is_last_element (my_basic_blocks, my_iterator); next_element (my_basic_blocks, my_iterator); end loop; reset_iterator(my_cfg_edges,my_iterator_edg); loop current_element(my_cfg_edges,a_cfg_edge,my_iterator_edg); bl1 := Search_Basic_Block(my_basic_blocks => ucb_basic_blocks, name => a_cfg_edge.node); bl2 := Search_Basic_Block(my_basic_blocks => ucb_basic_blocks, name => a_cfg_edge.next_node); Add(Basic_Block_UCB_Ptr(bl1).next_nodes,CFG_Node_Ptr(bl2)); Add(Basic_Block_UCB_Ptr(bl2).previous_nodes,CFG_Node_Ptr(bl1)); exit when is_last_element (my_cfg_edges, my_iterator_edg); next_element (my_cfg_edges, my_iterator_edg); end loop; my_basic_blocks := ucb_basic_blocks; end Convert_To_Basic_Block_UCB_Set; end CFG_Node_Set.Basic_Block_Set;