- 01 Jul, 2019 18 commits
-
-
This patch introduces new unit GNAT.Graphs which currently provides a directed graph abstraction. ------------ -- Source -- ------------ -- operations.adb with Ada.Text_IO; use Ada.Text_IO; with GNAT; use GNAT; with GNAT.Graphs; use GNAT.Graphs; with GNAT.Sets; use GNAT.Sets; procedure Operations is type Vertex_Id is (No_V, VA, VB, VC, VD, VE, VF, VG, VH, VX, VY, VZ); No_Vertex_Id : constant Vertex_Id := No_V; function Hash_Vertex (V : Vertex_Id) return Bucket_Range_Type; type Edge_Id is (No_E, E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E97, E98, E99); No_Edge_Id : constant Edge_Id := No_E; function Hash_Edge (E : Edge_Id) return Bucket_Range_Type; package ES is new Membership_Set (Element_Type => Edge_Id, "=" => "=", Hash => Hash_Edge); package DG is new Directed_Graph (Vertex_Id => Vertex_Id, No_Vertex => No_Vertex_Id, Hash_Vertex => Hash_Vertex, Same_Vertex => "=", Edge_Id => Edge_Id, No_Edge => No_Edge_Id, Hash_Edge => Hash_Edge, Same_Edge => "="); use DG; package VS is new Membership_Set (Element_Type => Vertex_Id, "=" => "=", Hash => Hash_Vertex); ----------------------- -- Local subprograms -- ----------------------- procedure Check_Belongs_To_Component (R : String; G : Instance; V : Vertex_Id; Exp_Comp : Component_Id); -- Verify that vertex V of graph G belongs to component Exp_Comp. R is the -- calling routine. procedure Check_Belongs_To_Some_Component (R : String; G : Instance; V : Vertex_Id); -- Verify that vertex V of graph G belongs to some component. R is the -- calling routine. procedure Check_Destination_Vertex (R : String; G : Instance; E : Edge_Id; Exp_V : Vertex_Id); -- Vertify that the destination vertex of edge E of grah G is Exp_V. R is -- the calling routine. procedure Check_Distinct_Components (R : String; Comp_1 : Component_Id; Comp_2 : Component_Id); -- Verify that components Comp_1 and Comp_2 are distinct (not the same) procedure Check_Has_Component (R : String; G : Instance; G_Name : String; Comp : Component_Id); -- Verify that graph G with name G_Name contains component Comp. R is the -- calling routine. procedure Check_Has_Edge (R : String; G : Instance; E : Edge_Id); -- Verify that graph G contains edge E. R is the calling routine. procedure Check_Has_Vertex (R : String; G : Instance; V : Vertex_Id); -- Verify that graph G contains vertex V. R is the calling routine. procedure Check_No_Component (R : String; G : Instance; V : Vertex_Id); -- Verify that vertex V does not belong to some component. R is the calling -- routine. procedure Check_No_Component (R : String; G : Instance; G_Name : String; Comp : Component_Id); -- Verify that graph G with name G_Name does not contain component Comp. R -- is the calling routine. procedure Check_No_Edge (R : String; G : Instance; E : Edge_Id); -- Verify that graph G does not contain edge E. R is the calling routine. procedure Check_No_Vertex (R : String; G : Instance; V : Vertex_Id); -- Verify that graph G does not contain vertex V. R is the calling routine. procedure Check_Number_Of_Components (R : String; G : Instance; Exp_Num : Natural); -- Verify that graph G has exactly Exp_Num components. R is the calling -- routine. procedure Check_Number_Of_Edges (R : String; G : Instance; Exp_Num : Natural); -- Verify that graph G has exactly Exp_Num edges. R is the calling routine. procedure Check_Number_Of_Vertices (R : String; G : Instance; Exp_Num : Natural); -- Verify that graph G has exactly Exp_Num vertices. R is the calling -- routine. procedure Check_Outgoing_Edge_Iterator (R : String; G : Instance; V : Vertex_Id; Set : ES.Instance); -- Verify that all outgoing edges of vertex V of graph G can be iterated -- and appear in set Set. R is the calling routine. procedure Check_Source_Vertex (R : String; G : Instance; E : Edge_Id; Exp_V : Vertex_Id); -- Vertify that the source vertex of edge E of grah G is Exp_V. R is the -- calling routine. procedure Check_Vertex_Iterator (R : String; G : Instance; Comp : Component_Id; Set : VS.Instance); -- Verify that all vertices of component Comp of graph G can be iterated -- and appear in set Set. R is the calling routine. function Create_And_Populate return Instance; -- Create a brand new graph (see body for the shape of the graph) procedure Error (R : String; Msg : String); -- Output an error message with text Msg within the context of routine R procedure Test_Add_Edge; -- Verify the semantics of routine Add_Edge procedure Test_Add_Vertex; -- Verify the semantics of routine Add_Vertex procedure Test_All_Edge_Iterator; -- Verify the semantics of All_Edge_Iterator procedure Test_All_Vertex_Iterator; -- Verify the semantics of All_Vertex_Iterator procedure Test_Component; -- Verify the semantics of routine Component procedure Test_Component_Iterator; -- Verify the semantics of Component_Iterator procedure Test_Contains_Component; -- Verify the semantics of routine Contains_Component procedure Test_Contains_Edge; -- Verify the semantics of routine Contains_Edge procedure Test_Contains_Vertex; -- Verify the semantics of routine Contains_Vertex procedure Test_Delete_Edge; -- Verify the semantics of routine Delete_Edge procedure Test_Destination_Vertex; -- Verify the semantics of routine Destination_Vertex procedure Test_Find_Components; -- Verify the semantics of routine Find_Components procedure Test_Is_Empty; -- Verify the semantics of routine Is_Empty procedure Test_Number_Of_Components; -- Verify the semantics of routine Number_Of_Components procedure Test_Number_Of_Edges; -- Verify the semantics of routine Number_Of_Edges procedure Test_Number_Of_Vertices; -- Verify the semantics of routine Number_Of_Vertices procedure Test_Outgoing_Edge_Iterator; -- Verify the semantics of Outgoing_Edge_Iterator procedure Test_Present; -- Verify the semantics of routine Present procedure Test_Source_Vertex; -- Verify the semantics of routine Source_Vertex procedure Test_Vertex_Iterator; -- Verify the semantics of Vertex_Iterator; procedure Unexpected_Exception (R : String); -- Output an error message concerning an unexpected exception within -- routine R. -------------------------------- -- Check_Belongs_To_Component -- -------------------------------- procedure Check_Belongs_To_Component (R : String; G : Instance; V : Vertex_Id; Exp_Comp : Component_Id) is Act_Comp : constant Component_Id := Component (G, V); begin if Act_Comp /= Exp_Comp then Error (R, "inconsistent component for vertex " & V'Img); Error (R, " expected: " & Exp_Comp'Img); Error (R, " got : " & Act_Comp'Img); end if; end Check_Belongs_To_Component; ------------------------------------- -- Check_Belongs_To_Some_Component -- ------------------------------------- procedure Check_Belongs_To_Some_Component (R : String; G : Instance; V : Vertex_Id) is begin if not Present (Component (G, V)) then Error (R, "vertex " & V'Img & " does not belong to a component"); end if; end Check_Belongs_To_Some_Component; ------------------------------ -- Check_Destination_Vertex -- ------------------------------ procedure Check_Destination_Vertex (R : String; G : Instance; E : Edge_Id; Exp_V : Vertex_Id) is Act_V : constant Vertex_Id := Destination_Vertex (G, E); begin if Act_V /= Exp_V then Error (R, "inconsistent destination vertex for edge " & E'Img); Error (R, " expected: " & Exp_V'Img); Error (R, " got : " & Act_V'Img); end if; end Check_Destination_Vertex; ------------------------------- -- Check_Distinct_Components -- ------------------------------- procedure Check_Distinct_Components (R : String; Comp_1 : Component_Id; Comp_2 : Component_Id) is begin if Comp_1 = Comp_2 then Error (R, "components are not distinct"); end if; end Check_Distinct_Components; ------------------------- -- Check_Has_Component -- ------------------------- procedure Check_Has_Component (R : String; G : Instance; G_Name : String; Comp : Component_Id) is begin if not Contains_Component (G, Comp) then Error (R, "graph " & G_Name & " lacks component"); end if; end Check_Has_Component; -------------------- -- Check_Has_Edge -- -------------------- procedure Check_Has_Edge (R : String; G : Instance; E : Edge_Id) is begin if not Contains_Edge (G, E) then Error (R, "graph lacks edge " & E'Img); end if; end Check_Has_Edge; ---------------------- -- Check_Has_Vertex -- ---------------------- procedure Check_Has_Vertex (R : String; G : Instance; V : Vertex_Id) is begin if not Contains_Vertex (G, V) then Error (R, "graph lacks vertex " & V'Img); end if; end Check_Has_Vertex; ------------------------ -- Check_No_Component -- ------------------------ procedure Check_No_Component (R : String; G : Instance; V : Vertex_Id) is begin if Present (Component (G, V)) then Error (R, "vertex " & V'Img & " belongs to a component"); end if; end Check_No_Component; procedure Check_No_Component (R : String; G : Instance; G_Name : String; Comp : Component_Id) is begin if Contains_Component (G, Comp) then Error (R, "graph " & G_Name & " contains component"); end if; end Check_No_Component; ------------------- -- Check_No_Edge -- ------------------- procedure Check_No_Edge (R : String; G : Instance; E : Edge_Id) is begin if Contains_Edge (G, E) then Error (R, "graph contains edge " & E'Img); end if; end Check_No_Edge; --------------------- -- Check_No_Vertex -- --------------------- procedure Check_No_Vertex (R : String; G : Instance; V : Vertex_Id) is begin if Contains_Vertex (G, V) then Error (R, "graph contains vertex " & V'Img); end if; end Check_No_Vertex; -------------------------------- -- Check_Number_Of_Components -- -------------------------------- procedure Check_Number_Of_Components (R : String; G : Instance; Exp_Num : Natural) is Act_Num : constant Natural := Number_Of_Components (G); begin if Act_Num /= Exp_Num then Error (R, "inconsistent number of components"); Error (R, " expected: " & Exp_Num'Img); Error (R, " got : " & Act_Num'Img); end if; end Check_Number_Of_Components; --------------------------- -- Check_Number_Of_Edges -- --------------------------- procedure Check_Number_Of_Edges (R : String; G : Instance; Exp_Num : Natural) is Act_Num : constant Natural := Number_Of_Edges (G); begin if Act_Num /= Exp_Num then Error (R, "inconsistent number of edges"); Error (R, " expected: " & Exp_Num'Img); Error (R, " got : " & Act_Num'Img); end if; end Check_Number_Of_Edges; ------------------------------ -- Check_Number_Of_Vertices -- ------------------------------ procedure Check_Number_Of_Vertices (R : String; G : Instance; Exp_Num : Natural) is Act_Num : constant Natural := Number_Of_Vertices (G); begin if Act_Num /= Exp_Num then Error (R, "inconsistent number of vertices"); Error (R, " expected: " & Exp_Num'Img); Error (R, " got : " & Act_Num'Img); end if; end Check_Number_Of_Vertices; ---------------------------------- -- Check_Outgoing_Edge_Iterator -- ---------------------------------- procedure Check_Outgoing_Edge_Iterator (R : String; G : Instance; V : Vertex_Id; Set : ES.Instance) is E : Edge_Id; Out_E_Iter : Outgoing_Edge_Iterator; begin -- Iterate over all outgoing edges of vertex V while removing edges seen -- from the set. Out_E_Iter := Iterate_Outgoing_Edges (G, V); while Has_Next (Out_E_Iter) loop Next (Out_E_Iter, E); if ES.Contains (Set, E) then ES.Delete (Set, E); else Error (R, "outgoing edge " & E'Img & " is not iterated"); end if; end loop; -- At this point the set of edges should be empty if not ES.Is_Empty (Set) then Error (R, "not all outgoing edges were iterated"); end if; end Check_Outgoing_Edge_Iterator; ------------------------- -- Check_Source_Vertex -- ------------------------- procedure Check_Source_Vertex (R : String; G : Instance; E : Edge_Id; Exp_V : Vertex_Id) is Act_V : constant Vertex_Id := Source_Vertex (G, E); begin if Act_V /= Exp_V then Error (R, "inconsistent source vertex"); Error (R, " expected: " & Exp_V'Img); Error (R, " got : " & Act_V'Img); end if; end Check_Source_Vertex; --------------------------- -- Check_Vertex_Iterator -- --------------------------- procedure Check_Vertex_Iterator (R : String; G : Instance; Comp : Component_Id; Set : VS.Instance) is V : Vertex_Id; V_Iter : Vertex_Iterator; begin -- Iterate over all vertices of component Comp while removing vertices -- seen from the set. V_Iter := Iterate_Vertices (G, Comp); while Has_Next (V_Iter) loop Next (V_Iter, V); if VS.Contains (Set, V) then VS.Delete (Set, V); else Error (R, "vertex " & V'Img & " is not iterated"); end if; end loop; -- At this point the set of vertices should be empty if not VS.Is_Empty (Set) then Error (R, "not all vertices were iterated"); end if; end Check_Vertex_Iterator; ------------------------- -- Create_And_Populate -- ------------------------- function Create_And_Populate return Instance is G : constant Instance := Create (Initial_Vertices => Vertex_Id'Size, Initial_Edges => Edge_Id'Size); begin -- 9 8 1 2 -- G <------ F <------ A ------> B -------> C -- | ^ | | ^ ^ -- +------------------+ | +-------------------+ -- 10 | | 3 -- 4 | 5 | -- v | -- H D ---------+ -- | ^ -- | | -- 6 | | 7 -- | | -- v | -- E -- -- Components: -- -- [A, F, G] -- [B] -- [C] -- [D, E] -- [H] Add_Vertex (G, VA); Add_Vertex (G, VB); Add_Vertex (G, VC); Add_Vertex (G, VD); Add_Vertex (G, VE); Add_Vertex (G, VF); Add_Vertex (G, VG); Add_Vertex (G, VH); Add_Edge (G, E1, Source => VA, Destination => VB); Add_Edge (G, E2, Source => VB, Destination => VC); Add_Edge (G, E3, Source => VA, Destination => VC); Add_Edge (G, E4, Source => VA, Destination => VD); Add_Edge (G, E5, Source => VD, Destination => VB); Add_Edge (G, E6, Source => VD, Destination => VE); Add_Edge (G, E7, Source => VE, Destination => VD); Add_Edge (G, E8, Source => VA, Destination => VF); Add_Edge (G, E9, Source => VF, Destination => VG); Add_Edge (G, E10, Source => VG, Destination => VA); return G; end Create_And_Populate; ----------- -- Error -- ----------- procedure Error (R : String; Msg : String) is begin Put_Line ("ERROR: " & R & ": " & Msg); end Error; --------------- -- Hash_Edge -- --------------- function Hash_Edge (E : Edge_Id) return Bucket_Range_Type is begin return Bucket_Range_Type (Edge_Id'Pos (E)); end Hash_Edge; ----------------- -- Hash_Vertex -- ----------------- function Hash_Vertex (V : Vertex_Id) return Bucket_Range_Type is begin return Bucket_Range_Type (Vertex_Id'Pos (V)); end Hash_Vertex; ------------------- -- Test_Add_Edge -- ------------------- procedure Test_Add_Edge is R : constant String := "Test_Add_Edge"; E : Edge_Id; G : Instance := Create_And_Populate; All_E_Iter : All_Edge_Iterator; Out_E_Iter : Outgoing_Edge_Iterator; begin -- Try to add the same edge twice begin Add_Edge (G, E1, VB, VH); Error (R, "duplicate edge not detected"); exception when Duplicate_Edge => null; when others => Unexpected_Exception (R); end; -- Try to add an edge with a bogus source begin Add_Edge (G, E97, Source => VX, Destination => VC); Error (R, "missing vertex not detected"); exception when Missing_Vertex => null; when others => Unexpected_Exception (R); end; -- Try to add an edge with a bogus destination begin Add_Edge (G, E97, Source => VF, Destination => VY); Error (R, "missing vertex not detected"); exception when Missing_Vertex => null; when others => Unexpected_Exception (R); end; -- Delete edge E1 between vertices VA and VB begin Delete_Edge (G, E1); exception when others => Unexpected_Exception (R); end; -- Try to re-add edge E1 begin Add_Edge (G, E1, Source => VA, Destination => VB); exception when others => Unexpected_Exception (R); end; -- Lock all edges in the graph All_E_Iter := Iterate_All_Edges (G); -- Try to add an edge given that all edges are locked begin Add_Edge (G, E97, Source => VG, Destination => VH); Error (R, "all edges not locked"); exception when Iterated => null; when others => Unexpected_Exception (R); end; -- Unlock all edges by iterating over them while Has_Next (All_E_Iter) loop Next (All_E_Iter, E); end loop; -- Lock all outgoing edges of vertex VD Out_E_Iter := Iterate_Outgoing_Edges (G, VD); -- Try to add an edge with source VD given that all edges of VD are -- locked. begin Add_Edge (G, E97, Source => VD, Destination => VG); Error (R, "outgoing edges of VD not locked"); exception when Iterated => null; when others => Unexpected_Exception (R); end; -- Unlock the edges of vertex VD by iterating over them while Has_Next (Out_E_Iter) loop Next (Out_E_Iter, E); end loop; Destroy (G); end Test_Add_Edge; --------------------- -- Test_Add_Vertex -- --------------------- procedure Test_Add_Vertex is R : constant String := "Test_Add_Vertex"; G : Instance := Create_And_Populate; V : Vertex_Id; All_V_Iter : All_Vertex_Iterator; begin -- Try to add the same vertex twice begin Add_Vertex (G, VD); Error (R, "duplicate vertex not detected"); exception when Duplicate_Vertex => null; when others => Unexpected_Exception (R); end; -- Lock all vertices in the graph All_V_Iter := Iterate_All_Vertices (G); -- Try to add a vertex given that all vertices are locked begin Add_Vertex (G, VZ); Error (R, "all vertices not locked"); exception when Iterated => null; when others => Unexpected_Exception (R); end; -- Unlock all vertices by iterating over them while Has_Next (All_V_Iter) loop Next (All_V_Iter, V); end loop; Destroy (G); end Test_Add_Vertex; ---------------------------- -- Test_All_Edge_Iterator -- ---------------------------- procedure Test_All_Edge_Iterator is R : constant String := "Test_All_Edge_Iterator"; E : Edge_Id; G : Instance := Create_And_Populate; All_E_Iter : All_Edge_Iterator; All_Edges : ES.Instance; begin -- Collect all expected edges in a set All_Edges := ES.Create (Number_Of_Edges (G)); for Curr_E in E1 .. E10 loop ES.Insert (All_Edges, Curr_E); end loop; -- Iterate over all edges while removing encountered edges from the set All_E_Iter := Iterate_All_Edges (G); while Has_Next (All_E_Iter) loop Next (All_E_Iter, E); if ES.Contains (All_Edges, E) then ES.Delete (All_Edges, E); else Error (R, "edge " & E'Img & " is not iterated"); end if; end loop; -- At this point the set of edges should be empty if not ES.Is_Empty (All_Edges) then Error (R, "not all edges were iterated"); end if; ES.Destroy (All_Edges); Destroy (G); end Test_All_Edge_Iterator; ------------------------------ -- Test_All_Vertex_Iterator -- ------------------------------ procedure Test_All_Vertex_Iterator is R : constant String := "Test_All_Vertex_Iterator"; G : Instance := Create_And_Populate; V : Vertex_Id; All_V_Iter : All_Vertex_Iterator; All_Vertices : VS.Instance; begin -- Collect all expected vertices in a set All_Vertices := VS.Create (Number_Of_Vertices (G)); for Curr_V in VA .. VH loop VS.Insert (All_Vertices, Curr_V); end loop; -- Iterate over all vertices while removing encountered vertices from -- the set. All_V_Iter := Iterate_All_Vertices (G); while Has_Next (All_V_Iter) loop Next (All_V_Iter, V); if VS.Contains (All_Vertices, V) then VS.Delete (All_Vertices, V); else Error (R, "vertex " & V'Img & " is not iterated"); end if; end loop; -- At this point the set of vertices should be empty if not VS.Is_Empty (All_Vertices) then Error (R, "not all vertices were iterated"); end if; VS.Destroy (All_Vertices); Destroy (G); end Test_All_Vertex_Iterator; -------------------- -- Test_Component -- -------------------- procedure Test_Component is R : constant String := "Test_Component"; G : Instance := Create (Initial_Vertices => 3, Initial_Edges => 2); begin -- E1 -- -----> -- VA VB VC -- <----- -- E2 -- -- Components: -- -- [VA, VB] -- [VC] Add_Vertex (G, VA); Add_Vertex (G, VB); Add_Vertex (G, VC); Add_Edge (G, E1, Source => VA, Destination => VB); Add_Edge (G, E2, Source => VB, Destination => VA); -- None of the vertices should belong to a component Check_No_Component (R, G, VA); Check_No_Component (R, G, VB); Check_No_Component (R, G, VC); -- Find the strongly connected components in the graph Find_Components (G); -- Vertices should belong to a component Check_Belongs_To_Some_Component (R, G, VA); Check_Belongs_To_Some_Component (R, G, VB); Check_Belongs_To_Some_Component (R, G, VC); Destroy (G); end Test_Component; ----------------------------- -- Test_Component_Iterator -- ----------------------------- procedure Test_Component_Iterator is R : constant String := "Test_Component_Iterator"; G : Instance := Create_And_Populate; Comp : Component_Id; Comp_Count : Natural; Comp_Iter : Component_Iterator; begin Find_Components (G); Check_Number_Of_Components (R, G, 5); Comp_Count := Number_Of_Components (G); -- Iterate over all components while decrementing their number Comp_Iter := Iterate_Components (G); while Has_Next (Comp_Iter) loop Next (Comp_Iter, Comp); Comp_Count := Comp_Count - 1; end loop; -- At this point all components should have been accounted for if Comp_Count /= 0 then Error (R, "not all components were iterated"); end if; Destroy (G); end Test_Component_Iterator; ----------------------------- -- Test_Contains_Component -- ----------------------------- procedure Test_Contains_Component is R : constant String := "Test_Contains_Component"; G1 : Instance := Create (Initial_Vertices => 2, Initial_Edges => 2); G2 : Instance := Create (Initial_Vertices => 2, Initial_Edges => 2); begin -- E1 -- -----> -- VA VB -- <----- -- E2 -- -- Components: -- -- [VA, VB] Add_Vertex (G1, VA); Add_Vertex (G1, VB); Add_Edge (G1, E1, Source => VA, Destination => VB); Add_Edge (G1, E2, Source => VB, Destination => VA); -- E97 -- -----> -- VX VY -- <----- -- E98 -- -- Components: -- -- [VX, VY] Add_Vertex (G2, VX); Add_Vertex (G2, VY); Add_Edge (G2, E97, Source => VX, Destination => VY); Add_Edge (G2, E98, Source => VY, Destination => VX); -- Find the strongly connected components in both graphs Find_Components (G1); Find_Components (G2); -- Vertices should belong to a component Check_Belongs_To_Some_Component (R, G1, VA); Check_Belongs_To_Some_Component (R, G1, VB); Check_Belongs_To_Some_Component (R, G2, VX); Check_Belongs_To_Some_Component (R, G2, VY); -- Verify that each graph contains the correct component Check_Has_Component (R, G1, "G1", Component (G1, VA)); Check_Has_Component (R, G1, "G1", Component (G1, VB)); Check_Has_Component (R, G2, "G2", Component (G2, VX)); Check_Has_Component (R, G2, "G2", Component (G2, VY)); -- Verify that each graph does not contain components from the other -- graph. Check_No_Component (R, G1, "G1", Component (G2, VX)); Check_No_Component (R, G1, "G1", Component (G2, VY)); Check_No_Component (R, G2, "G2", Component (G1, VA)); Check_No_Component (R, G2, "G2", Component (G1, VB)); Destroy (G1); Destroy (G2); end Test_Contains_Component; ------------------------ -- Test_Contains_Edge -- ------------------------ procedure Test_Contains_Edge is R : constant String := "Test_Contains_Edge"; G : Instance := Create_And_Populate; begin -- Verify that all edges in the range E1 .. E10 exist for Curr_E in E1 .. E10 loop Check_Has_Edge (R, G, Curr_E); end loop; -- Verify that no extra edges are present for Curr_E in E97 .. E99 loop Check_No_Edge (R, G, Curr_E); end loop; -- Add new edges E97, E98, and E99 Add_Edge (G, E97, Source => VG, Destination => VF); Add_Edge (G, E98, Source => VH, Destination => VE); Add_Edge (G, E99, Source => VD, Destination => VC); -- Verify that all edges in the range E1 .. E99 exist for Curr_E in E1 .. E99 loop Check_Has_Edge (R, G, Curr_E); end loop; -- Delete each edge that corresponds to an even position in Edge_Id for Curr_E in E1 .. E99 loop if Edge_Id'Pos (Curr_E) mod 2 = 0 then Delete_Edge (G, Curr_E); end if; end loop; -- Verify that all "even" edges are missing, and all "odd" edges are -- present. for Curr_E in E1 .. E99 loop if Edge_Id'Pos (Curr_E) mod 2 = 0 then Check_No_Edge (R, G, Curr_E); else Check_Has_Edge (R, G, Curr_E); end if; end loop; Destroy (G); end Test_Contains_Edge; -------------------------- -- Test_Contains_Vertex -- -------------------------- procedure Test_Contains_Vertex is R : constant String := "Test_Contains_Vertex"; G : Instance := Create_And_Populate; begin -- Verify that all vertices in the range VA .. VH exist for Curr_V in VA .. VH loop Check_Has_Vertex (R, G, Curr_V); end loop; -- Verify that no extra vertices are present for Curr_V in VX .. VZ loop Check_No_Vertex (R, G, Curr_V); end loop; -- Add new vertices VX, VY, and VZ Add_Vertex (G, VX); Add_Vertex (G, VY); Add_Vertex (G, VZ); -- Verify that all vertices in the range VA .. VZ exist for Curr_V in VA .. VZ loop Check_Has_Vertex (R, G, Curr_V); end loop; Destroy (G); end Test_Contains_Vertex; ---------------------- -- Test_Delete_Edge -- ---------------------- procedure Test_Delete_Edge is R : constant String := "Test_Delete_Edge"; E : Edge_Id; G : Instance := Create_And_Populate; V : Vertex_Id; All_E_Iter : All_Edge_Iterator; All_V_Iter : All_Vertex_Iterator; Out_E_Iter : Outgoing_Edge_Iterator; begin -- Try to delete a bogus edge begin Delete_Edge (G, E97); Error (R, "missing vertex deleted"); exception when Missing_Edge => null; when others => Unexpected_Exception (R); end; -- Delete edge E1 between vertices VA and VB begin Delete_Edge (G, E1); exception when others => Unexpected_Exception (R); end; -- Verify that edge E1 is gone from all edges in the graph All_E_Iter := Iterate_All_Edges (G); while Has_Next (All_E_Iter) loop Next (All_E_Iter, E); if E = E1 then Error (R, "edge " & E'Img & " not removed from all edges"); end if; end loop; -- Verify that edge E1 is gone from the outgoing edges of vertex VA Out_E_Iter := Iterate_Outgoing_Edges (G, VA); while Has_Next (Out_E_Iter) loop Next (Out_E_Iter, E); if E = E1 then Error (R, "edge " & E'Img & "not removed from outgoing edges of VA"); end if; end loop; -- Delete all edges in the range E2 .. E10 for Curr_E in E2 .. E10 loop Delete_Edge (G, Curr_E); end loop; -- Verify that all edges are gone from the graph All_E_Iter := Iterate_All_Edges (G); while Has_Next (All_E_Iter) loop Next (All_E_Iter, E); Error (R, "edge " & E'Img & " not removed from all edges"); end loop; -- Verify that all edges are gone from the respective source vertices All_V_Iter := Iterate_All_Vertices (G); while Has_Next (All_V_Iter) loop Next (All_V_Iter, V); Out_E_Iter := Iterate_Outgoing_Edges (G, V); while Has_Next (Out_E_Iter) loop Next (Out_E_Iter, E); Error (R, "edge " & E'Img & " not removed from vertex " & V'Img); end loop; end loop; Destroy (G); end Test_Delete_Edge; ----------------------------- -- Test_Destination_Vertex -- ----------------------------- procedure Test_Destination_Vertex is R : constant String := "Test_Destination_Vertex"; G : Instance := Create_And_Populate; begin -- Verify the destination vertices of all edges in the graph Check_Destination_Vertex (R, G, E1, VB); Check_Destination_Vertex (R, G, E2, VC); Check_Destination_Vertex (R, G, E3, VC); Check_Destination_Vertex (R, G, E4, VD); Check_Destination_Vertex (R, G, E5, VB); Check_Destination_Vertex (R, G, E6, VE); Check_Destination_Vertex (R, G, E7, VD); Check_Destination_Vertex (R, G, E8, VF); Check_Destination_Vertex (R, G, E9, VG); Check_Destination_Vertex (R, G, E10, VA); Destroy (G); end Test_Destination_Vertex; -------------------------- -- Test_Find_Components -- -------------------------- procedure Test_Find_Components is R : constant String := "Test_Find_Components"; G : Instance := Create_And_Populate; Comp_1 : Component_Id; -- [A, F, G] Comp_2 : Component_Id; -- [B] Comp_3 : Component_Id; -- [C] Comp_4 : Component_Id; -- [D, E] Comp_5 : Component_Id; -- [H] begin Find_Components (G); -- Vertices should belong to a component Check_Belongs_To_Some_Component (R, G, VA); Check_Belongs_To_Some_Component (R, G, VB); Check_Belongs_To_Some_Component (R, G, VC); Check_Belongs_To_Some_Component (R, G, VD); Check_Belongs_To_Some_Component (R, G, VH); -- Extract the ids of the components from the first vertices in each -- component. Comp_1 := Component (G, VA); Comp_2 := Component (G, VB); Comp_3 := Component (G, VC); Comp_4 := Component (G, VD); Comp_5 := Component (G, VH); -- Verify that the components are distinct Check_Distinct_Components (R, Comp_1, Comp_2); Check_Distinct_Components (R, Comp_1, Comp_3); Check_Distinct_Components (R, Comp_1, Comp_4); Check_Distinct_Components (R, Comp_1, Comp_5); Check_Distinct_Components (R, Comp_2, Comp_3); Check_Distinct_Components (R, Comp_2, Comp_4); Check_Distinct_Components (R, Comp_2, Comp_5); Check_Distinct_Components (R, Comp_3, Comp_4); Check_Distinct_Components (R, Comp_3, Comp_5); Check_Distinct_Components (R, Comp_4, Comp_5); -- Verify that the remaining nodes belong to the proper component Check_Belongs_To_Component (R, G, VF, Comp_1); Check_Belongs_To_Component (R, G, VG, Comp_1); Check_Belongs_To_Component (R, G, VE, Comp_4); Destroy (G); end Test_Find_Components; ------------------- -- Test_Is_Empty -- ------------------- procedure Test_Is_Empty is R : constant String := "Test_Is_Empty"; G : Instance := Create (Initial_Vertices => 3, Initial_Edges => 2); begin -- Verify that a graph without vertices and edges is empty if not Is_Empty (G) then Error (R, "graph is empty"); end if; -- Add vertices Add_Vertex (G, VA); Add_Vertex (G, VB); -- Verify that a graph with vertices and no edges is not empty if Is_Empty (G) then Error (R, "graph is not empty"); end if; -- Add edges Add_Edge (G, E1, Source => VA, Destination => VB); -- Verify that a graph with vertices and edges is not empty if Is_Empty (G) then Error (R, "graph is not empty"); end if; Destroy (G); end Test_Is_Empty; ------------------------------- -- Test_Number_Of_Components -- ------------------------------- procedure Test_Number_Of_Components is R : constant String := "Test_Number_Of_Components"; G : Instance := Create (Initial_Vertices => 3, Initial_Edges => 2); begin -- Verify that an empty graph has exactly 0 components Check_Number_Of_Components (R, G, 0); -- E1 -- -----> -- VA VB VC -- <----- -- E2 -- -- Components: -- -- [VA, VB] -- [VC] Add_Vertex (G, VA); Add_Vertex (G, VB); Add_Vertex (G, VC); Add_Edge (G, E1, Source => VA, Destination => VB); Add_Edge (G, E2, Source => VB, Destination => VA); -- Verify that the graph has exact 0 components even though it contains -- vertices and edges. Check_Number_Of_Components (R, G, 0); Find_Components (G); -- Verify that the graph has exactly 2 components Check_Number_Of_Components (R, G, 2); Destroy (G); end Test_Number_Of_Components; -------------------------- -- Test_Number_Of_Edges -- -------------------------- procedure Test_Number_Of_Edges is R : constant String := "Test_Number_Of_Edges"; G : Instance := Create_And_Populate; begin -- Verify that the graph has exactly 10 edges Check_Number_Of_Edges (R, G, 10); -- Delete two edges Delete_Edge (G, E1); Delete_Edge (G, E2); -- Verify that the graph has exactly 8 edges Check_Number_Of_Edges (R, G, 8); -- Delete the remaining edge for Curr_E in E3 .. E10 loop Delete_Edge (G, Curr_E); end loop; -- Verify that the graph has exactly 0 edges Check_Number_Of_Edges (R, G, 0); -- Add two edges Add_Edge (G, E1, Source => VF, Destination => VA); Add_Edge (G, E2, Source => VC, Destination => VH); -- Verify that the graph has exactly 2 edges Check_Number_Of_Edges (R, G, 2); Destroy (G); end Test_Number_Of_Edges; ----------------------------- -- Test_Number_Of_Vertices -- ----------------------------- procedure Test_Number_Of_Vertices is R : constant String := "Test_Number_Of_Vertices"; G : Instance := Create (Initial_Vertices => 4, Initial_Edges => 12); begin -- Verify that an empty graph has exactly 0 vertices Check_Number_Of_Vertices (R, G, 0); -- Add three vertices Add_Vertex (G, VC); Add_Vertex (G, VG); Add_Vertex (G, VX); -- Verify that the graph has exactly 3 vertices Check_Number_Of_Vertices (R, G, 3); -- Add one edge Add_Edge (G, E8, Source => VX, Destination => VG); -- Verify that the graph has exactly 3 vertices Check_Number_Of_Vertices (R, G, 3); Destroy (G); end Test_Number_Of_Vertices; --------------------------------- -- Test_Outgoing_Edge_Iterator -- --------------------------------- procedure Test_Outgoing_Edge_Iterator is R : constant String := "Test_Outgoing_Edge_Iterator"; G : Instance := Create_And_Populate; Set : ES.Instance; begin Set := ES.Create (4); ES.Insert (Set, E1); ES.Insert (Set, E3); ES.Insert (Set, E4); ES.Insert (Set, E8); Check_Outgoing_Edge_Iterator (R, G, VA, Set); ES.Insert (Set, E2); Check_Outgoing_Edge_Iterator (R, G, VB, Set); Check_Outgoing_Edge_Iterator (R, G, VC, Set); ES.Insert (Set, E5); ES.Insert (Set, E6); Check_Outgoing_Edge_Iterator (R, G, VD, Set); ES.Insert (Set, E7); Check_Outgoing_Edge_Iterator (R, G, VE, Set); ES.Insert (Set, E9); Check_Outgoing_Edge_Iterator (R, G, VF, Set); ES.Insert (Set, E10); Check_Outgoing_Edge_Iterator (R, G, VG, Set); Check_Outgoing_Edge_Iterator (R, G, VH, Set); ES.Destroy (Set); Destroy (G); end Test_Outgoing_Edge_Iterator; ------------------ -- Test_Present -- ------------------ procedure Test_Present is R : constant String := "Test_Present"; G : Instance := Nil; begin -- Verify that a non-existent graph is not present if Present (G) then Error (R, "graph is not present"); end if; G := Create_And_Populate; -- Verify that an existing graph is present if not Present (G) then Error (R, "graph is present"); end if; Destroy (G); -- Verify that a destroyed graph is not present if Present (G) then Error (R, "graph is not present"); end if; end Test_Present; ------------------------ -- Test_Source_Vertex -- ------------------------ procedure Test_Source_Vertex is R : constant String := "Test_Source_Vertex"; G : Instance := Create_And_Populate; begin -- Verify the source vertices of all edges in the graph Check_Source_Vertex (R, G, E1, VA); Check_Source_Vertex (R, G, E2, VB); Check_Source_Vertex (R, G, E3, VA); Check_Source_Vertex (R, G, E4, VA); Check_Source_Vertex (R, G, E5, VD); Check_Source_Vertex (R, G, E6, VD); Check_Source_Vertex (R, G, E7, VE); Check_Source_Vertex (R, G, E8, VA); Check_Source_Vertex (R, G, E9, VF); Check_Source_Vertex (R, G, E10, VG); Destroy (G); end Test_Source_Vertex; -------------------------- -- Test_Vertex_Iterator -- -------------------------- procedure Test_Vertex_Iterator is R : constant String := "Test_Vertex_Iterator"; G : Instance := Create_And_Populate; Set : VS.Instance; begin Find_Components (G); Set := VS.Create (3); VS.Insert (Set, VA); VS.Insert (Set, VF); VS.Insert (Set, VG); Check_Vertex_Iterator (R, G, Component (G, VA), Set); VS.Insert (Set, VB); Check_Vertex_Iterator (R, G, Component (G, VB), Set); VS.Insert (Set, VC); Check_Vertex_Iterator (R, G, Component (G, VC), Set); VS.Insert (Set, VD); VS.Insert (Set, VE); Check_Vertex_Iterator (R, G, Component (G, VD), Set); VS.Insert (Set, VH); Check_Vertex_Iterator (R, G, Component (G, VH), Set); VS.Destroy (Set); Destroy (G); end Test_Vertex_Iterator; -------------------------- -- Unexpected_Exception -- -------------------------- procedure Unexpected_Exception (R : String) is begin Error (R, "unexpected exception"); end Unexpected_Exception; -- Start of processing for Operations begin Test_Add_Edge; Test_Add_Vertex; Test_All_Edge_Iterator; Test_All_Vertex_Iterator; Test_Component; Test_Component_Iterator; Test_Contains_Component; Test_Contains_Edge; Test_Contains_Vertex; Test_Delete_Edge; Test_Destination_Vertex; Test_Find_Components; Test_Is_Empty; Test_Number_Of_Components; Test_Number_Of_Edges; Test_Number_Of_Vertices; Test_Outgoing_Edge_Iterator; Test_Present; Test_Source_Vertex; Test_Vertex_Iterator; end Operations; ---------------------------- -- Compilation and output -- ---------------------------- $ gnatmake -q operations.adb -largs -lgmem $ ./operations $ gnatmem operations > leaks.txt $ grep -c "non freed allocations" leaks.txt 0 2019-07-01 Hristian Kirtchev <kirtchev@adacore.com> gcc/ada/ * impunit.adb: Add GNAT.Graphs to list Non_Imp_File_Names_95. * Makefile.rtl, gcc-interface/Make-lang.in: Register unit GNAT.Graphs. * libgnat/g-dynhta.adb: Various minor cleanups (use Present rather than direct comparisons). (Delete): Reimplement to use Delete_Node. (Delete_Node): New routine. (Destroy_Bucket): Invoke the provided destructor. (Present): New routines. * libgnat/g-dynhta.ads: Add new generic formal Destroy_Value. Use better names for the components of iterators. * libgnat/g-graphs.adb, libgnat/g-graphs.ads: New unit. * libgnat/g-lists.adb: Various minor cleanups (use Present rather than direct comparisons). (Delete_Node): Invoke the provided destructor. (Present): New routine. * libgnat/g-lists.ads: Add new generic formal Destroy_Element. Use better names for the components of iterators. (Present): New routine. * libgnat/g-sets.adb, libgnat/g-sets.ads (Destroy, Preset, Reset): New routines. From-SVN: r272857Hristian Kirtchev committed -
2019-07-01 Dmitriy Anisimkov <anisimko@adacore.com> gcc/ada/ * libgnat/g-sothco.adb (Get_Address): Fix the case when AF_INET6 is not defined. From-SVN: r272856
Dmitriy Anisimkov committed -
Invalid_Value in most cases uses a predefined numeric value from a built-in table, but if the type does not include zero in its range, the literal 0 is used instead. In that case the value (produced by a call to Get_Simple_Init_Val) must be resolved for proper type information. The following must compile quietly: gnatmake -q main ---- with Problems; use Problems; with Text_IO; use Text_IO; procedure Main is begin Put_Line ("P1: " & P1'Image); Put_Line ("P2: " & P2'Image); Put_Line ("P3: " & P3'Image); Put_Line ("P4: " & P4'Image); end Main; -- package Problems is function P1 return Integer; function P2 return Long_Integer; -- Max. number of prime factors a number can have is log_2 N -- For N = 600851475143, this is ~ 40 -- type P3_Factors is array (1 .. 40) of Long_Integer; function P3 return Long_Integer; type P4_Palindrome is range 100*100 .. 999*999; function P4 return P4_Palindrome; end Problems; ---- package body Problems is function P1 return Integer is separate; function P2 return Long_Integer is separate; function P3 return Long_Integer is separate; function P4 return P4_Palindrome is separate; end Problems; ---- separate(Problems) function P1 return Integer is Sum : Integer range 0 .. 500_500 := 0; begin for I in Integer range 1 .. 1000 - 1 loop if I mod 3 = 0 or I mod 5 = 0 then Sum := Sum + I; end if; end loop; return Sum; end P1; -- separate(Problems) function P2 return Long_Integer is subtype Total is Long_Integer range 0 .. 8_000002e6 ; subtype Elem is Total range 0 .. 4e7 ; Sum : Total := 0; a, b, c : Elem; begin a := 1; b := 2; loop if b mod 2 = 0 then Sum := Sum + b; end if; c := b; b := a + b; a := c; exit when b >= 4e6; end loop; return Sum; end P2; -- with Text_IO; use Text_IO; with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions; separate(Problems) function P3 return Long_Integer is -- Greatest prime factor GPF : Long_Integer := 1; Dividend : Long_Integer := 600851475143; Factor : Long_Integer := 2; Quotient : Long_Integer; begin while Dividend > 1 loop Quotient := Dividend / Factor; if Dividend mod Factor = 0 then GPF := Factor; Dividend := Quotient; else if Factor >= Quotient then GPF := Dividend; exit; end if; Factor := Factor + 1; end if; end loop; return GPF; end P3; ---- with Text_IO; use Text_IO; separate(Problems) function P4 return P4_Palindrome is type TripleDigit is range 100 .. 999; a, b: TripleDigit := TripleDigit'First; c : P4_Palindrome; Max_Palindrome : P4_Palindrome := P4_Palindrome'Invalid_Value; function Is_Palindrome (X : in P4_Palindrome) return Boolean is type Int_Digit is range 0 .. 9; type Int_Digits is array (1 .. 6) of Int_Digit; type Digit_Extractor is range 0 .. P4_Palindrome'Last; Y : Digit_Extractor := Digit_Extractor (X); X_Digits : Int_Digits; begin for I in reverse X_Digits'Range loop X_Digits (I) := Int_Digit (Y mod 10); Y := Y / 10; end loop; return (X_Digits (1) = X_Digits (6) and X_Digits (2) = X_Digits (5) and X_Digits (3) = X_Digits (4)) or (X_Digits (2) = X_Digits (6) and X_Digits (3) = X_Digits (5) and X_Digits(1) = 0); end Is_Palindrome; begin for a in TripleDigit'Range loop for b in TripleDigit'Range loop c := P4_Palindrome (a * b); if Is_Palindrome (c) then if Max_Palindrome'Valid or else c > Max_Palindrome then Max_Palindrome := c; end if; end if; end loop; end loop; return Max_Palindrome; end; 2019-07-01 Ed Schonberg <schonberg@adacore.com> gcc/ada/ * exp_attr.adb (Expand_Attribute_Reference, case Invalid_Value): Resolve result of call to Get_Simple_Init_Val, which may be a conversion of a literal. From-SVN: r272855Ed Schonberg committed -
The following patch updates the freezing of expressions to insert the generated freeze nodes prior to the expression that produced them when the context is a transient scope within a type initialization procedure. This ensures that the nodes are properly interleaved with respect to the constructs that generated them. 2019-07-01 Hristian Kirtchev <kirtchev@adacore.com> gcc/ada/ * freeze.adb (Freeze_Expression): Remove the horrible useless name hiding of N. Insert the freeze nodes generated by the expression prior to the expression when the nearest enclosing scope is transient. gcc/testsuite/ * gnat.dg/freezing1.adb, gnat.dg/freezing1.ads, gnat.dg/freezing1_pack.adb, gnat.dg/freezing1_pack.ads: New testcase. From-SVN: r272854
Hristian Kirtchev committed -
2019-07-01 Pierre-Marie de Rodat <derodat@adacore.com> gcc/ada/ * doc/gnat_ugn/building_executable_programs_with_gnat.rst: Fix formatting issues in the -gnatR section. * gnat_ugn.texi: Regenerate. From-SVN: r272853
Pierre-Marie de Rodat committed -
PR lto/91028 PR lto/90720 * g++.dg/lto/alias-1_0.C: Add loop to make inlining happen with -fno-use-linker-plugin * g++.dg/lto/alias-2_0.C: Likewise. From-SVN: r272852
Jan Hubicka committed -
make_early_clobber_and_input_conflicts records allocno conflicts between inputs and earlyclobber outputs. It (rightly) avoids doing this for inputs that are explicitly allowed to match the output due to matching constraints. The problem is that whether this matching is allowed varies between alternatives. At the moment the code avoids adding a clobber if *any* enabled alternative allows the match, even if some other operand makes that alternative impossible. The specific instance of this for SVE is that some alternatives allow matched earlyclobbers when a third operand X is constant zero. We should avoid adding conflicts when X really is constant zero, but should ignore the match if X is nonzero or nonconstant. ira_setup_alts can already filter these alternatives out for us, so all we need to do is use it in process_bb_node_lives. The preferred_alternatives variable is only used for this earlyclobber detection, so no other check should be affected. With the previous patch to check the reject weight in ira_setup_alts, this has the effect of ignoring expensive alternatives if we have other valid alternatives with zero cost. It seems reasonable to base the heuristic on only the alternatives that we'd actually like to use, but if this ends up being too aggressive, we could instead make the new reject behaviour conditional and only use it for add_insn_allocno_copies. 2019-07-01 Richard Sandiford <richard.sandiford@arm.com> gcc/ * ira-lives.c (process_bb_node_lives): Use ira_setup_alts. From-SVN: r272851
Richard Sandiford committed -
ira_get_dup_out_num punted on operands that are matched to earlyclobber outputs: /* It is better ignore an alternative with early clobber. */ else if (*str == '&') goto fail; But I'm not sure why this is the right thing to do. At this stage we've established that *all* alternatives of interest require the input to match the output, so (a) the earlyclobber can only affect other operands and (b) not tying the registers is bound to introduce a move The code was part of the initial commit and so isn't obviously related to a specific testcase. Also, I can imagine LRA makes a much better job of this situation than reload did. (Certainly SVE uses matched earlyclobbers extensively and I haven't seen any problems.) In case this turns out to regress something important: the main case that matters for SVE is the one in which all alternatives are earlyclobber. 2019-07-01 Richard Sandiford <richard.sandiford@arm.com> gcc/ * ira.c (ira_get_dup_out_num): Don't punt for earlyclobbers. Use recog_data to test for an output operand. From-SVN: r272850
Richard Sandiford committed -
SVE has a prefix instruction (MOVPRFX) that acts as a move but is designed to be easily fusible with the following instruction. The SVE port therefore has lots of patterns with constraints of the form: A: operand 0: =w,?w ... operand n: 0, w where the first alternative is a single instruction and the second alternative uses MOVPRFX. Ideally we want operand n to be allocated to the same register as operand 0 in this case. add_insn_allocno_copies is the main IRA routine that deals with tied operands. It is (rightly) very conservative, and only handles cases in which we're confident about saving a full move. So for a pattern like: B: operand 0: =w,w ... operand n: 0,w we don't (and shouldn't) assume that tying operands 0 and n would save the cost of a move. But in A, the second alternative has a ? marker, which makes it more expensive than the first alternative by a full reload. So I think for copy elision we should ignore the untied operand n in the second alternative of A. One approach would be to add '*' markers to each pattern and make ira_get_dup_out_num honour them. But I think the rule applies on first principles, so marking with '*' shouldn't be necessary. This patch instead makes ira_get_dup_out_num ignore expensive alternatives if there are other alternatives that match exactly. The cheapest way of doing that seemed to be to take expensive alternatives out of consideration in ira_setup_alts, which provides a bitmask of alternatives and has all the information available. add_insn_allocno_copies is the only current user of ira_setup_alts, so no other code should be affected. If all available alternatives are disparaged or need a reload, there's not much we can do to cut them down at this stage, since it's hard to predict which operands will be reloaded and which registers will need to be spilled. An interesting case is patterns like this msp430 one: ;; Alternatives 2 and 3 are to handle cases generated by reload. (define_insn "subqi3" [(set (match_operand:QI 0 "nonimmediate_operand" "=rYs, rm, &?r, ?&r") (minus:QI (match_operand:QI 1 "general_operand" "0, 0, !r, !i") (match_operand:QI 2 "general_operand" " riYs, rmi, rmi, r")))] "" "@ SUB.B\t%2, %0 SUB%X0.B\t%2, %0 MOV%X0.B\t%1, %0 { SUB%X0.B\t%2, %0 MOV%X0.B\t%1, %0 { SUB%X0.B\t%2, %0" ) Here alternative 3 is significantly more expensive then alternative 0 (reject costs 0 and 606 respectively). But if operand 1 is an integer constant, we'll still use alternative 3 if operand 2 is an allocated register. On the other hand, if operand 1 is an integer constant but operand 2 is spilled to memory, we'll move the constant into a register and use the first alternative. So in this case, if operand 1 is a register, we should consider only the first two alternatives and thus try to tie operand 1 to operand 0 (which we didn't do previously). If operand 1 is a constant integer, we should consider at least alternatives 0, 1 and 3. We could exclude alternative 2, but I don't have any evidence that that's useful. 2019-07-01 Richard Sandiford <richard.sandiford@arm.com> gcc/ * ira.c (ira_setup_alts): If any valid alternatives have zero cost, exclude any others that are disparaged or that are bound to need a reload or spill. (ira_get_dup_out_num): Expand comment. From-SVN: r272849Richard Sandiford committed -
ira_setup_alts has its own code to calculate the start of the constraint string for each operand/alternative combination, but preprocess_constraints now provides that information in (almost) constant time for non-asm instructions. Using it here should speed up the common case at the cost of potentially slowing down the handling of asm statements. The real reason for doing this is that a later patch wants to use more of the operand_alternative information. 2019-07-01 Richard Sandiford <richard.sandiford@arm.com> gcc/ * ira.c (ira_setup_alts): Use preprocess_constraints to get the constraint string for each operand/alternative combo. Only handle '%' at the start of constraint strings, and look for it outside the main loop. From-SVN: r272848
Richard Sandiford committed -
add_insn_allocno_copies and its subroutines used HARD_REG_SET to represent a bitmask of alternatives. There's not really any connection between the number of registers and the maximum number of alternatives, so this patch uses alternative_mask instead (which wasn't around when this code was added). This is just a minor clean-up making way for later patches. 2019-07-01 Richard Sandiford <richard.sandiford@arm.com> gcc/ * ira-int.h (ira_setup_alts, ira_get_dup_out_num): Use alternative_mask instead of HARD_REG_SET to represent a bitmask of alternatives. * ira.c (ira_setup_alts, ira_get_dup_out_num): Likewise. * ira-conflicts.c (add_insn_allocno_copies): Likewise. From-SVN: r272847
Richard Sandiford committed -
2019-07-01 Martin Liska <mliska@suse.cz> * edit-context.c (test_applying_fixits_unreadable_file): Do not use () for a constructor call. (test_applying_fixits_line_out_of_range): Likewise. * ggc-page.c (alloc_page): Use (void *) for %p printf format argument. (free_page): Likewise. From-SVN: r272846
Martin Liska committed -
gcc/ * gdbhooks.py (GdbPrettyPrinters.add_printer_for_types): Reorder parameter names to match usage (no functional change). (GdbPrettyPrinters.add_printer_for_regex): Ditto. From-SVN: r272845
Vladislav Ivanishin committed -
2019-07-01 Dominique d'Humieres <dominiq@gcc.gnu.org> * g++.dg/cpp0x/gen-attrs-67.C: Add error for darwin. From-SVN: r272844
Dominique d'Humieres committed -
2019-07-01 Richard Biener <rguenther@suse.de> * tree-ssa-sccvn.c (class pass_fre): Add may_iterate pass parameter. (pass_fre::execute): Honor it. * passes.def: Adjust pass_fre invocations to allow iterating, add non-iterating pass_fre before late threading/dom. * gcc.dg/tree-ssa/pr77445-2.c: Adjust. From-SVN: r272843
Richard Biener committed -
tree-ssa-sccvn.c (copy_reference_ops_from_ref): Adjust TARGET_MEM_REF handling to also handle address-taken ones. 2019-07-01 Richard Biener <rguenther@suse.de> * tree-ssa-sccvn.c (copy_reference_ops_from_ref): Adjust TARGET_MEM_REF handling to also handle address-taken ones. From-SVN: r272842
Richard Biener committed -
gcc/ 2019-07-01 Hongtao Liu <hongtao.liu@intel.com> * doc/sourcebuild.texi (Effective-Target Keywords, Other hardware attributes): Document avx512vp2intersect. gcc/testsuite/ 2019-07-01 Hongtao Liu <hongtao.liu@intel.com> * lib/target-supports.exp (check_effective_target_avx512vp2intersect): New proc. * gcc.target/i386/avx512vp2intersect-2intersect-1b.c: Add dg-require-effective-target avx512vp2intersect. * gcc.target/i386/avx512vp2intersect-2intersectvl-1b.c: Ditto. From-SVN: r272840
Hongtao Liu committed -
From-SVN: r272839
GCC Administrator committed
-
- 30 Jun, 2019 4 commits
-
-
* config/i386/sse.md (ssse3_abs<mode>2): Rename from abs<mode>2. (abs<mode>2): New expander. * config/i386/i386-builtin.def (__builtin_ia32_pabsb): Use CODE_FOR_ssse3_absv8qi2. (__builtin_ia32_pabsw): Use CODE_FOR_ssse3_absv4hi2. (__builtin_ia32_pabsd): Use CODE_FOR_ssse3_absv2si2. From-SVN: r272835
Uros Bizjak committed -
* config/i386/i386.md (mmx_isa): Rename x64, x64_noavx and x64_avx to sse, sse_noavx and avx. Update all uses. * config/i386/mmx.md (sse_movntq): Add "isa" attribute. (*mmx_<plusminus_insn><mode>3): Ditto. (*mmx_mulv4hi3"): Ditto. (*mmx_smulv4hi3_highpart): Ditto. (*mmx_umulv4hi3_highpart): Ditto. (*mmx_pmaddwd): Ditto. (*sse2_umulv1siv1di3): Ditto. (*mmx_<code>v4hi3): Ditto. (*mmx_<code>v8qi3): Ditto. (mmx_ashr<mode>3): Ditto. ("mmx_<shift_insn><mode>3): Ditto. (*mmx_eq<mode>3): Ditto. (mmx_gt<mode>3): Ditto. (mmx_andnot<mode>3): Ditto. (*mmx_<code><mode>3): Ditto. (*mmx_pinsrw): Ditto. (*mmx_pextrw): Ditto. (mmx_pshufw_1): Ditto. (*mmx_uavgv8qi3): Ditto. (*mmx_uavgv4hi3): Ditto. ("mmx_psadbw): Ditto. * config/i386/sse.md (sse_cvtps2pi): Ditto. (sse_cvttps2pi): Ditto. (ssse3_pmaddubsw): Ditto. (*ssse3_pmulhrswv4hi3): Ditto. (ssse3_psign<mode>3): Ditto. From-SVN: r272834Uros Bizjak committed -
Gnatlink has code that checks for duplicate '-shared-libgcc’ switches (but not duplicate ‘static-libgcc’) and also pushes ’static-libgcc' onto the link line for targets that default to static linking, provided '-shared-libgcc' is not present. For targets that should use a shared libgcc we need the same process to be applied (in inverse), in the event that they do not default to providing the shared flag implicitly. So this adds the complementary set of tests for the shared case and pushes the shared flag as needed. As a minor tidy-up there’s no need push duplicates of the libgcc switch onto the link line when one has already been seen (given by the user). The patch does not alter any of the platform defaults for static/shared libgcc, but it ensures that the intent of the link is explicit. gcc/ada/ 2019-06-30 Iain Sandoe <iain@sandoe.co.uk> * gnatlink.adb (Link_Step): Remove duplicate -static-libgcc switches. Push -shared-libgcc explicitly, when it is the target default (unless overidden by the static flag). When the user has put an instance of shared/static-libgcc do not push a duplicate of this. From-SVN: r272832
Iain Sandoe committed -
From-SVN: r272831
GCC Administrator committed
-
- 29 Jun, 2019 9 commits
-
-
* gcc-interface/decl.c (gnat_to_gnu_entity): Beep up comment on SAVED, and tweak comment on the assertion about the scopes of Itypes. Do not skip the regular processing for Itypes that are E_Record_Subtype with a Cloned_Subtype. Get the Cloned_Subtype for every E_Record_Subtype if the type is dummy and hasn't got its own freeze node. <E_Record_Subtype>: Save again the DECL of the Cloned_Subtype, if any. <E_Access_Subtype>: Save again the DECL of the equivalent type. (Gigi_Equivalent_Type) <E_Access_Subtype>: New case. From-SVN: r272822
Eric Botcazou committed -
* gcc-interface/utils.c (unchecked_convert): Tweak comment. Only skip dereferences when padding to have the same size on both sides. Do it for destination types with self-referential size too. From-SVN: r272821
Eric Botcazou committed -
decl.c (gnat_to_gnu_entity): If the type requires strict alignment, then set the RM size to the type size. * gcc-interface/decl.c (gnat_to_gnu_entity) <E_Record_Type>: If the type requires strict alignment, then set the RM size to the type size. Rework handling of alignment and sizes of tagged types in ASIS mode. (validate_size): Rename local variable and remove special handling for strict-alignment types. * gcc-interface/utils.c (finish_record_type): Constify local variables and use properly typed constants. From-SVN: r272820
Eric Botcazou committed -
* gcc-interface/decl.c (gnat_to_gnu_field): Rework error messages for fields requiring strict alignment, add explicit test on Storage_Unit for position and size, and mention type alignment for position. From-SVN: r272819
Eric Botcazou committed -
* gcc-interface/trans.c (mark_visited_r): Set TYPE_SIZES_GIMPLIFIED on the main variant of a type, if any. From-SVN: r272815
Eric Botcazou committed -
decl.c (set_nonaliased_component_on_array_type): Add missing guard for the presence of TYPE_CANONICAL. * gcc-interface/decl.c (set_nonaliased_component_on_array_type): Add missing guard for the presence of TYPE_CANONICAL. (set_reverse_storage_order_on_array_type): Likewise. From-SVN: r272811
Eric Botcazou committed -
* expr.c (expand_expr_real_1) <BIT_FIELD_REF>: Apply the big-endian adjustment for bit-fields to all aggregate types. ada/ * gcc-interface/gigi.h (make_packable_type): Remove default value. (value_factor_p): Tweak prototype. * gcc-interface/decl.c (gnat_to_gnu_entity): Add comment. (gnat_to_gnu_component_type): Likewise. (gnat_to_gnu_field): Likewise. Fetch the position of the field earlier and simplify the condition under which the type is packed. Declare local variable is_bitfield. Pass 1 as max_align to make_packable_type if it is set to true. (copy_and_substitute_in_layout): Pass 0 to make_packable_type. * gcc-interface/utils.c (make_packable_array_type): New function. (make_packable_type): Use it to rewrite the type of array field. (maybe_pad_type): Pass align parameter to make_packable_type. (create_field_decl): Minor tweaks. (value_factor_p): Assert that FACTOR is a power of 2 and replace the modulo computation by a masking operation. From-SVN: r272810
Eric Botcazou committed -
From-SVN: r272809
Jason Merrill committed -
From-SVN: r272808
GCC Administrator committed
-
- 28 Jun, 2019 9 commits
-
-
2019-06-28 Michael Meissner <meissner@linux.ibm.com> * config/rs6000/predicates.md (pcrel_address): Use SYMBOL_REF_LOCAL_P to determine if a label is local. (pcrel_external_address): New predicate. (non_prefixed_mem_operand): Delete, predicate not used. * config/rs6000/rs6000.h (SYMBOL_FLAG_PCREL_P): Delete, we now use SYMBOL_REF_LOCAL_P to determine if we can use pc-relative addressing. (SYMBOL_REF_PCREL_P): Likewise. From-SVN: r272792
Michael Meissner committed -
Fix PR target/91009 2019-06-27 Michael Meissner <meissner@linux.ibm.com> PR target/91009 * config/rs6000/rs6000.md (floatsi<mode>2_lfiwax): Add non-VSX alternative. (floatsi<mode>2_lfiwax_mem): Add non-VSX alternative. (floatunssi<mode>2_lfiwzx): Add non-VSX alternative. (floatunssi<mode>2_lfiwzx_mem): Add non-VSX alternative. From-SVN: r272791
Michael Meissner committed -
This is primarily in order to improve testsuite coverage, we might elect to prune the list at some point. 2019-06-28 Iain Sandoe <iain@sandoe.co.uk> * config.gcc (powerpc-*-darwin*, powerpc64-*-darwin*): Remove override on extra_headers. From-SVN: r272790
Iain Sandoe committed -
2019-06-28 Iain Sandoe <iain@sandoe.co.uk> * config/darwin-c.c (pop_field_alignment): Quote #pragma options. * config/darwin-driver.c (darwin_default_min_version): Remove newline from warning. (darwin_driver_init): Likewise. From-SVN: r272789
Iain Sandoe committed -
There's no need for three alternatives: "v" without TARGET_AVX512F is the same as "x". From-SVN: r272784
Jan Beulich committed -
The affine transformations are not commutative (the two source operands have entirely different meaning). Also the nonimmediate_operand predicate can better be vector_operand. From-SVN: r272783
Jan Beulich committed -
A recent RTX cost commit has changed the costs for ARC700 leading to errors in slsr-13.c test. This commit fixes this issue by reverting the cost computation for short instructions. 2019-06-28 Claudiu Zissulescu <claziss@synopsys.com> * config/arc/arc.c (arc_rtx_costs): All short instructions are having a lower cost regardless of the speed option. From-SVN: r272782
Claudiu Zissulescu committed -
From-SVN: r272781
Jan Beulich committed -
With just an "m" constraint misaligned memory operands won't be forced into a register, and hence cause #GP. So far this was guaranteed only in the case that CVT{,T}PD2DQ were chosen (which looks to be the case on x86-64 only). Switch the second alternative to Bm and also replace nonimmediate_operand by vector_operand. From-SVN: r272780Jan Beulich committed
-
