From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 17035 invoked by alias); 21 Mar 2004 21:02:14 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 17017 invoked from network); 21 Mar 2004 21:02:12 -0000 Received: from unknown (HELO dberlin.org) (69.3.5.6) by sources.redhat.com with SMTP; 21 Mar 2004 21:02:12 -0000 Received: from [192.168.1.7] (account dberlin HELO [192.168.1.7]) by dberlin.org (CommuniGate Pro SMTP 4.1.4) with ESMTP-TLS id 6321178; Sun, 21 Mar 2004 16:02:10 -0500 Mime-Version: 1.0 (Apple Message framework v613) Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: <04224152-7B7B-11D8-B8A0-000A95DA505C@dberlin.org> Content-Transfer-Encoding: 7bit Cc: gcc mailing list From: Daniel Berlin Subject: DOM doesn't notice some equivalences through phis Date: Mon, 22 Mar 2004 02:38:00 -0000 To: Jeff Law X-SW-Source: 2004-03/txt/msg01272.txt.bz2 While working on GVN-PRE, I was originally planning on skipping the "eliminate" phase (which just eliminates the now fully redundant values), and letting DOM handle it. But I can't, because DOM doesn't seem to notice they are now equivalent. Here is a hand-constructed example that is the same as the code GVN-PRE generates prior to elimination: int main(int argc, char **argv) { int a; int b=argc + 13; int c=argc + 5; int pretmp; a = b + c; pretmp = a; /* Prevent DCE from removing our first occurrence */ printf("%d\n", a); if (argc < 2) { } else { b = argc + 4; pretmp = b + c; } a = b + c; /* Prevent DCE from removing our second occurrence */ printf("%d\n", a); /* Prevent DCE from removing the pretmp. */ printf ("%d\n", pretmp); } Dom refuses to replace the second b + c with pretmp, even though they have the same value. The SSA form of the above is ;; Function main (main) main (argc, argv) { int pretmp; int c; int b; int a; # BLOCK 0 # PRED: ENTRY (fallthru) : b_4 = argc_3 + 13; c_5 = argc_3 + 5; a_6 = b_4 + c_5; pretmp_7 = a_6; printf ("%d\n", a_6); if (argc_3 > 1) goto ; else goto ; # BLOCK 1 # PRED: 0 (true) :; b_9 = argc_3 + 4; pretmp_10 = b_9 + c_5; # BLOCK 2 # PRED: 1 (fallthru) 0 (false) # pretmp_2 = PHI ; # b_1 = PHI ; :; a_8 = b_1 + c_5; printf ("%d\n", a_8); printf ("%d\n", pretmp_2); return; (This has a critical edge that gets split, but this dump is from dom1. dom3, which runs after PRE, removes the empty BB from the split edge anyway. Leaving that block in has no effect on whether b_1 + c_5 is eliminated) pretmp_2's PHI has exactly the same values at the same points in the program as b_1 + c_5. It might be a bit expensive to handle this case. It has to, when it sees b_1 in the expression is defined by a phi, back-translate it on each predecessor, and see if it has an available expression for the translated expression (b_4 + c_5 in pred block 0, b_9 + c_5 in pred block 1) in each predecessor. That would tell it that it has b_4 + c_5 available out of a_6 in predecessor block 0, and b_9 + c_5 available out of predecessor block 1. Then it could either introduce a new no-cost phi for those values, or see if one exists (honestly, it's probably cheaper to just introduce a new phi, even though one exists already in the form of the pretmp phi. Checking all the phis for the right values wouldn't be cheap). I'm not sure how often it comes up, and i can take care of it as part of GVN-PRE, but it just means GVN-PRE will catch standard eliminations that DOM could, but doesn't. And it means i can't let DOM just take care of eliminating the fully redundant expressions, which would have been nice in terms of code reuse. Thoughts? --Dan