Re: Constant folding and Constant propagation
Steven Bosscher wrote: > On Fri, Feb 6, 2009 at 7:32 PM, Adam Nemet wrote: >> I think you really need the Joern's optmize_related_values patch. Also see >> PR33699. > > I wouldn't recommend that patch, but yes: Something that performs that > optimization ;-) Yes, something doing that using LCM was on my list of "things to do after fwprop to do what CSE currently does, but better". I never got round to implementing it, I think. I had an LCM-based replacement for canon_reg that I wanted to use as a basis, maybe I can dig it up. Paolo
Re: Solve transitive closure issue in modulo scheduling
On Fri, Jan 30, 2009 at 7:44 AM, Bingfeng Mei wrote: > Hello, > I try to make modulo scheduling work more efficiently for our VLIW target. I > found one serious issue that prevents current SMS algorithm from achieving > high IPC is so-called "transitive closure" problem, where scheduling window > is only calculated using direct predecessors and successors. Because SMS is > not an iterative algorithm, this may cause failures in finding a valid > schedule. Without splitting rows, some simple loops just cannot be scheduled > not matter how big the II is. With splitting rows, schedule can be found, but > only at bigger II. GCC wiki (http://gcc.gnu.org/wiki/SwingModuloScheduling) > lists this as a TODO. Is there any work going on about this issue (the last > wiki update was one year ago)? If no one is working on it, I plan to do it. > My idea is to use the MinDist algorithm described in B. Rau's classic paper > "iterative modulo scheduling" > (http://www.hpl.hp.com/techreports/94/HPL-94-115.html). The same algorithm > can also be used to compute better RecMII. The biggest concern is complexity > of computing MinDist matrix, which is O(N^3). N is number of nodes in the > loop. I remember somewhere GCC coding guide says "never write quadratic > algorithm" :-) Is this an absolute requirement? It's not an absolute requirement, just a general guideline. We have plenty of quadratic and worse algorithms, and we'd rather see less of them :) Obviously, when it comes to things requiring transitive closure, you can't really do better.
fixincludes "fixes" Xlibint.h in an unknown way.
This is just a question. Hopefully someone can shed some light on what the fixincludes stage of "make install" does. I am making the assumption that the "make install" stage is where these headers get mangled or modified. This is on Solaris 8 by the way. Once make install has finished its job I see symlinks down deep in strange places thus : $ ls -lap $DEST/lib/gcc/sparc-sun-solaris2.8/4.3.3/include-fixed/ | grep "^lrwx" lrwxrwxrwx 1 dclarke csw 28 Feb 7 17:19 X11 -> root/usr/openwin/include/X11/ lrwxrwxrwx 1 dclarke csw 22 Feb 7 17:19 Xm -> root/usr/dt/include/Xm/ lrwxrwxrwx 1 dclarke csw 29 Feb 7 17:19 kcms -> root/usr/openwin/include/kcms/ lrwxrwxrwx 1 dclarke csw 28 Feb 7 17:19 xil -> root/usr/openwin/include/xil/ These guys point to a dir entry called "root" which seems odd also but there it is. Way down deep in there I see this ( for example ) : $ ls -lap $DEST/lib/gcc/sparc-sun-solaris2.8/4.3.3/include-fixed/root/usr/openwin/include/X11/ total 166 drwxr-xr-x 3 dclarke csw 512 Feb 7 09:37 ./ drwxr-xr-x 5 dclarke csw 512 Feb 7 09:37 ../ drwxr-xr-x 2 dclarke csw 512 Feb 7 09:37 DPS/ -rw-r--r-- 1 dclarke csw 4087 Feb 7 09:37 Xfuncs.h -rw-r--r-- 1 dclarke csw39002 Feb 7 09:37 Xlibint.h -rw-r--r-- 1 dclarke csw 6025 Feb 7 09:37 Xos.h -rw-r--r-- 1 dclarke csw 2980 Feb 7 09:37 Xosdefs.h -rw-r--r-- 1 dclarke csw10184 Feb 7 09:37 Xthreads.h -rw-r--r-- 1 dclarke csw 8847 Feb 7 09:37 dni.h -rw-r--r-- 1 dclarke csw 8366 Feb 7 09:37 nmdefs.h That all looks to be copies of *standard* headers found in the OS vendors /usr/openwin/share/include/X11 area. What changed ? $ diff /usr/openwin/share/include/X11/Xlibint.h $DEST/lib/gcc/sparc-sun-solaris2.8/4.3.3/include-fixed/root/usr/openwin/include/X11/Xlibint.h 0a1,9 > /* DO NOT EDIT THIS FILE. > > It has been auto-edited by fixincludes from: > > "/usr/include/X11/Xlibint.h" > > This had to be done to correct non-standard usages in the > original, manufacturer supplied header file. */ > 882c891 < #ifdef sun /* added by SUNSOFT */ --- > #ifdef __sun__ /* added by SUNSOFT */ So the entire change is a comment and one line which both say "added by SUNSOFT" in them. Xfuncs.h is somewhat more interesting : < #if (__STDC__ && !defined(X_NOT_STDC_ENV) && !defined(sun) && !defined(macII) && !defined(apollo)) || defined(SVR4) || defined(hpux) || defined(_IBMR2) || defined(_SEQUENT_) --- > #if (__STDC__ && !defined(X_NOT_STDC_ENV) && !defined(__sun__) && !defined(macII) && !defined(apollo)) || defined(SVR4) || defined(hpux) || defined(_IBMR2) || defined(_SEQUENT_) 88c97 < #if !defined(X_NOT_STDC_ENV) && (!defined(sun) || defined(SVR4)) --- > #if !defined(X_NOT_STDC_ENV) && (!defined(__sun__) || defined(SVR4)) 96c105 < #if defined(SYSV) || defined(luna) || defined(sun) || defined(__sxg__) --- > #if defined(SYSV) || defined(luna) || defined(__sun__) || defined(__sxg__) $ It looks like anywhere you find the string "defined(sun)" you change it to "defined(__sun__)". That is an observation. But what did this ? Was it fixincludes or was it the mkheaders script ? and why ? -- Dennis Clarke
Re: fixincludes "fixes" Xlibint.h in an unknown way.
On Sat, Feb 7, 2009 at 7:27 PM, Dennis Clarke wrote: > > This is just a question. Hopefully someone can shed some light on what the > fixincludes stage of "make install" does. I am making the assumption that > the "make install" stage is where these headers get mangled or modified. > > This is on Solaris 8 by the way. > > Once make install has finished its job I see symlinks down deep in strange > places thus : > > $ ls -lap $DEST/lib/gcc/sparc-sun-solaris2.8/4.3.3/include-fixed/ | grep > "^lrwx" > lrwxrwxrwx 1 dclarke csw 28 Feb 7 17:19 X11 -> > root/usr/openwin/include/X11/ > lrwxrwxrwx 1 dclarke csw 22 Feb 7 17:19 Xm -> > root/usr/dt/include/Xm/ > lrwxrwxrwx 1 dclarke csw 29 Feb 7 17:19 kcms -> > root/usr/openwin/include/kcms/ > lrwxrwxrwx 1 dclarke csw 28 Feb 7 17:19 xil -> > root/usr/openwin/include/xil/ > > > These guys point to a dir entry called "root" which seems odd also but > there it is. > > Way down deep in there I see this ( for example ) : > > $ ls -lap > $DEST/lib/gcc/sparc-sun-solaris2.8/4.3.3/include-fixed/root/usr/openwin/include/X11/ > total 166 > drwxr-xr-x 3 dclarke csw 512 Feb 7 09:37 ./ > drwxr-xr-x 5 dclarke csw 512 Feb 7 09:37 ../ > drwxr-xr-x 2 dclarke csw 512 Feb 7 09:37 DPS/ > -rw-r--r-- 1 dclarke csw 4087 Feb 7 09:37 Xfuncs.h > -rw-r--r-- 1 dclarke csw39002 Feb 7 09:37 Xlibint.h > -rw-r--r-- 1 dclarke csw 6025 Feb 7 09:37 Xos.h > -rw-r--r-- 1 dclarke csw 2980 Feb 7 09:37 Xosdefs.h > -rw-r--r-- 1 dclarke csw10184 Feb 7 09:37 Xthreads.h > -rw-r--r-- 1 dclarke csw 8847 Feb 7 09:37 dni.h > -rw-r--r-- 1 dclarke csw 8366 Feb 7 09:37 nmdefs.h > > That all looks to be copies of *standard* headers found in the OS vendors > /usr/openwin/share/include/X11 area. > > What changed ? > > > $ diff /usr/openwin/share/include/X11/Xlibint.h > $DEST/lib/gcc/sparc-sun-solaris2.8/4.3.3/include-fixed/root/usr/openwin/include/X11/Xlibint.h > 0a1,9 >> /* DO NOT EDIT THIS FILE. >> >> It has been auto-edited by fixincludes from: >> >> "/usr/include/X11/Xlibint.h" >> >> This had to be done to correct non-standard usages in the >> original, manufacturer supplied header file. */ >> > 882c891 > < #ifdef sun /* added by SUNSOFT */ > --- >> #ifdef __sun__ /* added by SUNSOFT */ > > So the entire change is a comment and one line which both say "added by > SUNSOFT" in them. > > > Xfuncs.h is somewhat more interesting : > > < #if (__STDC__ && !defined(X_NOT_STDC_ENV) && !defined(sun) && > !defined(macII) && !defined(apollo)) || defined(SVR4) || defined(hpux) || > defined(_IBMR2) || defined(_SEQUENT_) > --- >> #if (__STDC__ && !defined(X_NOT_STDC_ENV) && !defined(__sun__) && > !defined(macII) && !defined(apollo)) || defined(SVR4) || defined(hpux) > || defined(_IBMR2) || defined(_SEQUENT_) > 88c97 > < #if !defined(X_NOT_STDC_ENV) && (!defined(sun) || defined(SVR4)) > --- >> #if !defined(X_NOT_STDC_ENV) && (!defined(__sun__) || defined(SVR4)) > 96c105 > < #if defined(SYSV) || defined(luna) || defined(sun) || defined(__sxg__) > --- >> #if defined(SYSV) || defined(luna) || defined(__sun__) || defined(__sxg__) > $ > > It looks like anywhere you find the string "defined(sun)" you change it to > "defined(__sun__)". > > That is an observation. > > But what did this ? > > Was it fixincludes or was it the mkheaders script ? > > and why ? Because system headers should not define something in the users namespace, certainly not a non-uglified three-letter name such as "sun". Consider #include int sun; which will not build otherwise. Richard. > > -- > Dennis Clarke > >
Re: fixincludes "fixes" Xlibint.h in an unknown way.
>> Was it fixincludes or was it the mkheaders script ? >> >> and why ? > > Because system headers should not define something in the users namespace, > certainly not a non-uglified three-letter name such as "sun". > > Consider > > #include > > int sun; > > which will not build otherwise. I did find this .. and I see it in the 4.0.2 GCC tree also that I have here : $ cat /opt/csw/gcc4/lib/gcc/sparc-sun-solaris2.8/4.3.3/include-fixed/README This README file is copied into the directory for GCC-only header files when fixincludes is run by the makefile for GCC. Many of the files in this directory were automatically edited from the standard system header files by the fixincludes process. They are system-specific, and will not work on any other kind of system. They are also not part of GCC. The reason we have to do this is because GCC requires ANSI C headers and many vendors supply ANSI-incompatible headers. Because this is an automated process, sometimes headers get "fixed" that do not, strictly speaking, need a fix. As long as nothing is broken by the process, it is just an unfortunate collateral inconvenience. We would like to rectify it, if it is not "too inconvenient". simply put .. it all looks good. I simply need to figure out how to release things to users or do I force a fixincludes/make headers script event during install or what. How does Debian and Ubuntu handle this ? When a user installs a pre-compiled ready to run GCC package do they get the headers "fixed" on the fly or do they get delivered ... -- Dennis Clarke
Re: Constant folding and Constant propagation
Ok, thanks for all this information and if you can dig that up it would be nice too. I'll start looking at that patch and PR33699 to see if I can adapt them to my needs. Any reason why you wouldn't recommend it? I will keep you posted of anything I do for latter reference, Jean Christophe Beyler On Sat, Feb 7, 2009 at 5:05 AM, Paolo Bonzini wrote: > Steven Bosscher wrote: >> On Fri, Feb 6, 2009 at 7:32 PM, Adam Nemet wrote: >>> I think you really need the Joern's optmize_related_values patch. Also see >>> PR33699. >> >> I wouldn't recommend that patch, but yes: Something that performs that >> optimization ;-) > > Yes, something doing that using LCM was on my list of "things to do > after fwprop to do what CSE currently does, but better". I never got > round to implementing it, I think. I had an LCM-based replacement for > canon_reg that I wanted to use as a basis, maybe I can dig it up. > > Paolo > >
Machine description question
Dear all, I have a question about the way the machine description works and how it affects the different passes of the compiler. I was reading the GNU Compiler Collection Internals and I found this part (in section 14.8.1): (define_insn "" [(set (match_operand:SI 0 "general_operand" "=r") (plus:SI (match_dup 0) (match_operand:SI 1 "general_operand" "r")))] "" "...") which has two operands, one of which must appear in two places, and (define_insn "" [(set (match_operand:SI 0 "general_operand" "=r") (plus:SI (match_operand:SI 1 "general_operand" "0") (match_operand:SI 2 "general_operand" "r")))] "" "...") which has three operands, two of which are required by a constraint to be identical. My question is : - How do the constraints work for match_dup or for when you put "0" as a constraint? Since we want the same register but as input and not output, how does the compiler set up its dependencies? Does it just forget the "=" or "+" for the match_dup or "0" ? - I also read that it is possible to assign a letter with a number for the constraint. Does this mean I can do "r0" to say, it's going to be an input register but it must look like the one you'll find in position 0? - My third question is: why not put "+r" as the constraint instead of "=r" since we are going to be reading and writing into r0. - Finally, I have a similar instruction definition, if I use the first solution (match_dup), the instruction that will calculate the input/output operand 0 sometimes gets removed by the web pass. But if I use the second solution (put a "0" constraint), then it is no longer removed. Any idea why these two definitions would be treated differently in the web pass? Thanks again in advance, Jc
Re: Machine description question
On Sat, Feb 07, 2009 at 03:54:51PM -0500, Jean Christophe Beyler wrote: > Dear all, > > I have a question about the way the machine description works and how > it affects the different passes of the compiler. I was reading the GNU > Compiler Collection Internals and I found this part (in section > 14.8.1): > > (define_insn "" >[(set (match_operand:SI 0 "general_operand" "=r") > (plus:SI (match_dup 0) > (match_operand:SI 1 "general_operand" "r")))] >"" >"...") > > which has two operands, one of which must appear in two places, and > > (define_insn "" >[(set (match_operand:SI 0 "general_operand" "=r") > (plus:SI (match_operand:SI 1 "general_operand" "0") > (match_operand:SI 2 "general_operand" "r")))] >"" >"...") > > which has three operands, two of which are required by a constraint to > be identical. > > > My question is : > - How do the constraints work for match_dup or for when you put "0" as > a constraint? Since we want the same register but as input and not > output, how does the compiler set up its dependencies? Does it just > forget the "=" or "+" for the match_dup or "0" ? Note, the two are not the same thing before register allocation. Before register allocation, in the first example, the argument to the plus must point to the exact RTL that the result is. Given that normally a different pseudo register is used for the output, the first example won't match a lot of insns that are created. The two general_operands are distinct and the normal live/death information will track the insns. So you are saying that the first general operand is a write only value, and the second is a read only value. During register allocation, the register allocator notices the "0" and then reuses the register. In that example, the value of operand1 dies in that insn, replaced by the value in operand0. For example, consider a 2 address machine like the 386 (and ignoring things like LEA). If the value of operand1 is live after the insn, and operand0 wants to be %eax, operand1 is in %ebx, and operand2 is in %edx, then the register allocation typically generates code like: movl %ebx, %eax addl %edx, %eax If operand1's value was not needed after the insn, then the compiler would possibly allocate the output to %ebx, and do: addl %edx, %ebx > > - I also read that it is possible to assign a letter with a number for > the constraint. Does this mean I can do "r0" to say, it's going to be > an input register but it must look like the one you'll find in > position 0? I'm not sure what you are asking here. If you are talking about the multi-letter constraints in define_register_constraint, that is basically a way to extend the machine description for more constraints when you run out of single letters. > - My third question is: why not put "+r" as the constraint instead of > "=r" since we are going to be reading and writing into r0. Because the output value is not an input to the add in the second example. It is an input to the add in the first, due to the use of match_dup. > - Finally, I have a similar instruction definition, if I use the first > solution (match_dup), the instruction that will calculate the > input/output operand 0 sometimes gets removed by the web pass. But if > I use the second solution (put a "0" constraint), then it is no longer > removed. Any idea why these two definitions would be treated > differently in the web pass? I don't know much about the web pass, however as I said, the two definitions are fundamentally different. -- Michael Meissner, IBM 4 Technology Place Drive, MS 2203A, Westford, MA, 01886, USA meiss...@linux.vnet.ibm.com
