[Bug optimization/15349] New: [tree-ssa] Merge two phi nodes.

[Bug optimization/15349] New: [tree-ssa] Merge two phi nodes.

[kazu at cs dot umass dot edu]

void bar (void);

int
foo (int a, int b)
{
  int t;

  if (b)
    {
      if (a)
	t = 3;
      else
	t = 5;

      if (t)
	a++;
    }
  else
    t = 7;

  return t - 1;
}

I get:

foo (a, b)
{
  int t;

<bb 0>:
  if (b_3 != 0) goto <L0>; else goto <L7>;

<L0>:;
  if (a_6 != 0) goto <L1>; else goto <L3>;

<L1>:;

  # t_1 = PHI <5(1), 3(2)>;
<L3>:;

  # t_2 = PHI <7(0), t_1(3)>;
<L7>:;
  return t_2 - 1;

}

Note that we can merge the first PHI into the second one like so:

  # t_2 = PHI <7(0), 5(1), 3(2)>;

by replacing goto <L1>; with goto <L7>;

Note that this optimization is pretty important because I see alias.c
containing the following:

<L191>:;

  # iftmp.1496_89 = PHI <0(139), 1(138)>;
<L192>:;
  iftmp.1493_304 = iftmp.1496_89 != 0;

  # iftmp.1493_88 = PHI <iftmp.1493_304(140), iftmp.1493_316(136)>;
<L193>:;
  if (iftmp.1493_88) goto <L194>; else goto <L202>;

Once PR 14797 is solved, the above code should become something like

<L191>:;

  # iftmp.1493_304 = PHI <0(139), 1(138)>;
<L192>:;

  # iftmp.1493_88 = PHI <iftmp.1493_304(140), iftmp.1493_316(136)>;
<L193>:;
  if (iftmp.1493_88) goto <L194>; else goto <L202>;

Once this PR is solved, we would have

<L192>:;

  # iftmp.1493_88 = PHI <0(139), 1(138), iftmp.1493_316(136)>;
<L193>:;
  if (iftmp.1493_88) goto <L194>; else goto <L202>;

Now it's trivial to redirect jumps from bb 139 and bb 138
to <L202> and <L194>, respectively, provided that nobody else
uses iftmp.1493_88.

-- 
           Summary: [tree-ssa] Merge two phi nodes.
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Keywords: pessimizes-code
          Severity: enhancement
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at cs dot umass dot edu
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug optimization/15349] [tree-ssa] Merge two phi nodes.

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-05-09 20:36 -------
Confirmed, could be considered a compile time and memory time hog as there are more than needed 
bb at the end of compiling.  (I have seen this in some other cases too).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |compile-time-hog, memory-hog
   Last reconfirmed|0000-00-00 00:00:00         |2004-05-09 20:36:22
               date|                            |
   Target Milestone|---                         |tree-ssa


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[dnovillo at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |dnovillo at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.5.0                       |---


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-09-14 02:55 -------
I see this while compiling postreload.c.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-09-14 03:53 -------
Well, this occurs everywhere, but just give you an example, sometimes
a chain of PHI goes as long as

<L126>:;

  # iftmp.32_81 = PHI <0(69), 5(70)>;
<L128>:;

  # iftmp.32_83 = PHI <7(67), 6(68), iftmp.32_81(71)>;
<L132>:;

  # iftmp.32_78 = PHI <iftmp.32_83(72), 16(62), iftmp.32_79(66), 0(61)>;
<L134>:;

  # iftmp.32_84 = PHI <2(55), iftmp.32_75(59), iftmp.32_78(73)>;
<L137>:;

  # iftmp.32_86 = PHI <4(53), 3(54), iftmp.32_84(74)>;
<L141>:;

  # iftmp.32_74 = PHI <iftmp.32_86(75), 14(51), 0(50), 14(49), 1(52)>;
<L144>:;

  # iftmp.32_70 = PHI <iftmp.32_74(76), 15(42), 0(41), 15(40), iftmp.32_71(47)>;
<L146>:;

  # iftmp.32_89 = PHI <8(37), 8(38), iftmp.32_70(77)>;
<L150>:;

  # iftmp.32_91 = PHI <12(35), 11(36), iftmp.32_89(78)>;
<L154>:;

This comes from reload_cse_simplify_operands() in postreload.c.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-09-19 19:03 -------
The patch posted at:
http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01888.html


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-09-20 20:08 -------
An updated patch:
http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01974.html


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-22 04:59 -------
Another updated patch:
http://gcc.gnu.org/ml/gcc-patches/2004-12/msg01587.html


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|dnovillo at gcc dot gnu dot |kazu at cs dot umass dot edu
                   |org                         |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-01-20 19:20 -------
Subject: Bug 15349

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	kazu@gcc.gnu.org	2005-01-20 19:20:40

Modified files:
	gcc            : ChangeLog timevar.def tree-cfg.c 
	                 tree-optimize.c tree-pass.h 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.dg/tree-ssa: pr15349.c 

Log message:
	PR tree-optimization/15349
	* timevar.def (TV_TREE_MERGE_PHI): New.
	* tree-cfg.c (tree_forwarder_block_p): Add a new argument
	PHI_WANTED.
	(remove_forwarder_block, cleanup_forwarder_blocks): Adjust the
	calls to tree_forwarder_block_p.
	(remove_forwarder_block_with_phi, merge_phi_nodes,
	gate_merge_phi, pass_merge_phi): New.
	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_merge_phi.
	* tree-pass.h: Add an extern for pass_merge_phi;
	
	PR tree-optimization/15349
	* testsuite/gcc.dg/tree-ssa/pr15349.c: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7204&r2=2.7205
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/timevar.def.diff?cvsroot=gcc&r1=1.41&r2=1.42
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-cfg.c.diff?cvsroot=gcc&r1=2.140&r2=2.141
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-optimize.c.diff?cvsroot=gcc&r1=2.68&r2=2.69
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-pass.h.diff?cvsroot=gcc&r1=2.24&r2=2.25
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.4914&r2=1.4915
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/pr15349.c.diff?cvsroot=gcc&r1=NONE&r2=1.1



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2005-01-20 19:49 -------
Just checked in a fix.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349

[Bug tree-optimization/15349] [tree-ssa] Merge two phi nodes.

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.0.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15349