* Re: Ada files now checked in
@ 2001-10-06 18:25 dewar
2001-10-07 0:38 ` Diego Novillo
0 siblings, 1 reply; 17+ messages in thread
From: dewar @ 2001-10-06 18:25 UTC (permalink / raw)
To: dewar, dnovillo; +Cc: bosch, gcc, kenner, zack
<<$ gcc -Wuninitialized -ftree-ssa foo.c -O -c
foo.c: In function `main':
foo.c:3: warning: `b' is used uninitialized in this function
>>
Right, I know about those messages, the trouble is that the message
does not point to the problem point, it points instead to the declaration
of b. What you need in more complex cases is a pointer to the exact
occurrence that is detected as potentially troublesome
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: Ada files now checked in 2001-10-06 18:25 Ada files now checked in dewar @ 2001-10-07 0:38 ` Diego Novillo 2001-10-07 0:59 ` Zack Weinberg 0 siblings, 1 reply; 17+ messages in thread From: Diego Novillo @ 2001-10-07 0:38 UTC (permalink / raw) To: dewar; +Cc: bosch, gcc, kenner, zack On Sat, 06 Oct 2001, dewar@gnat.com wrote: > <<$ gcc -Wuninitialized -ftree-ssa foo.c -O -c > foo.c: In function `main': > foo.c:3: warning: `b' is used uninitialized in this function > >> > > Right, I know about those messages, the trouble is that the message > does not point to the problem point, it points instead to the declaration > of b. What you need in more complex cases is a pointer to the exact > occurrence that is detected as potentially troublesome > No, this is based on the new tree SSA infrastructure (BTW, I had cut&pasted the wrong output in my inital message). This will always point to the line with a use of an uninitialized variable: ----------------------------------------------------------------------------- $ cat rdefs.c main() { int a, b; a = b + 4; if (a > 0) b = b + 3; } $ gcc -Wuninitialized -ftree-ssa rdefs.c -O -c rdefs.c: In function `main': rdefs.c:5: warning: `b' is used uninitialized in this function rdefs.c:7: warning: `b' is used uninitialized in this function ----------------------------------------------------------------------------- As I said, I'm still debugging this work, but the basic infrastructure is already in the AST branch. Diego. ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: Ada files now checked in 2001-10-07 0:38 ` Diego Novillo @ 2001-10-07 0:59 ` Zack Weinberg 2001-10-07 10:24 ` Diego Novillo 0 siblings, 1 reply; 17+ messages in thread From: Zack Weinberg @ 2001-10-07 0:59 UTC (permalink / raw) To: Diego Novillo; +Cc: dewar, bosch, gcc, kenner On Sun, Oct 07, 2001 at 03:34:42AM -0400, Diego Novillo wrote: > $ gcc -Wuninitialized -ftree-ssa rdefs.c -O -c > rdefs.c: In function `main': > rdefs.c:5: warning: `b' is used uninitialized in this function > rdefs.c:7: warning: `b' is used uninitialized in this function > ----------------------------------------------------------------------------- > > As I said, I'm still debugging this work, but the basic > infrastructure is already in the AST branch. Extremely cool. That will make finding missing initializations much easier. Maybe you could change the warning message to "...used uninitialized here" or "at this point" or something like that? Just to be clear it's not the same old "somewhere in the function" message. I notice it says "_is_ used uninitialized". Does that mean you've eliminated the old false positive problems? How expensive is it to calculate these? It'd be nice if we could generate the warnings with optimization off; that's always been a wart. zw ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: Ada files now checked in 2001-10-07 0:59 ` Zack Weinberg @ 2001-10-07 10:24 ` Diego Novillo 2001-10-07 10:53 ` better -Wuninitialized (Re: Ada files now checked in) Zack Weinberg ` (2 more replies) 0 siblings, 3 replies; 17+ messages in thread From: Diego Novillo @ 2001-10-07 10:24 UTC (permalink / raw) To: Zack Weinberg; +Cc: dewar, bosch, gcc, kenner On Sun, 07 Oct 2001, Zack Weinberg wrote: > Maybe you could change the warning message to "...used uninitialized > here" or "at this point" or something like that? Just to be clear > it's not the same old "somewhere in the function" message. > Sure. > I notice it says "_is_ used uninitialized". Does that mean you've > eliminated the old false positive problems? > That's the intent. The new code still spews out false positives, that's what I'm now working on. The analysis depends on the computation of reaching definitions. Prior to computing the SSA form, we insert ghost definitions for every symbol in the entry basic block. After reaching definitions, we traverse all the variable use references in the function. For every use: - if its only reaching definition is the ghost def, the variable *is* used uninitialized. - if one of its reaching definitions is the ghost def, the variable *may be* used uninitialized. That's a very simplified view that will give you lots of false positives (variables with its address taken, global variables, etc). I'm refining the criteria with each bootstrap. Also, I'm about to add def-def chains to model non-killing definitions like: 1: int a, b *p; 2: 3: a = 4; 4: *p = 3; 5: b = a + 1; The use of a at line 5 may be reached by the definitions of *p and a at lines 4 and 3, respectively. But this part is nowhere near ready. > How expensive is it to calculate these?> The analysis itself is relatively cheap once you have computed the SSA form and reaching definitions of the function. It's roughly O(SxR) where S is the number of symbols and R the number of symbol references in the function. Computing the SSA form is not cheap, but can be improved. Essentially you need to: - Build the flowgraph. That's roughly linear in the number of statement tree nodes. - Find all the variable references in the function. Linear in the total number of tree nodes. - Compute the SSA form. This involves computing immediate dominators and dominance frontiers. I believe the algorithms we have in GCC are quite quick, but I haven't really looked. Building the FUD chains is like O(SxNxE) (could be wrong, I'm quoting from memory). There is a linear phi placing algorithm which I plan to switch to. I want to hook-up all the tree SSA passes to -ftime-report. That will give us a better idea of how expensive this really is. > It'd be nice if we could generate the warnings with > optimization off; that's always been a wart. > Definitiely possible. We only need to make -Wuninitialized trigger -ftree-ssa. Diego. ^ permalink raw reply [flat|nested] 17+ messages in thread
* better -Wuninitialized (Re: Ada files now checked in) 2001-10-07 10:24 ` Diego Novillo @ 2001-10-07 10:53 ` Zack Weinberg 2001-10-07 10:57 ` Joseph S. Myers ` (2 more replies) 2001-10-07 11:05 ` Ada files now checked in Daniel Berlin 2001-10-14 7:53 ` Joern Rennecke 2 siblings, 3 replies; 17+ messages in thread From: Zack Weinberg @ 2001-10-07 10:53 UTC (permalink / raw) To: Diego Novillo; +Cc: gcc On Sun, Oct 07, 2001 at 01:21:01PM -0400, Diego Novillo wrote: > On Sun, 07 Oct 2001, Zack Weinberg wrote: > > Maybe you could change the warning message to "...used uninitialized > > here" or "at this point" or something like that? Just to be clear > > it's not the same old "somewhere in the function" message. > > > Sure. Thanks. > > I notice it says "_is_ used uninitialized". Does that mean you've > > eliminated the old false positive problems? > > > That's the intent. The new code still spews out false positives, > that's what I'm now working on. > > The analysis depends on the computation of reaching definitions. > Prior to computing the SSA form, we insert ghost definitions for > every symbol in the entry basic block. After reaching > definitions, we traverse all the variable use references in the > function. For every use: > > - if its only reaching definition is the ghost def, the variable > *is* used uninitialized. > > - if one of its reaching definitions is the ghost def, the > variable *may be* used uninitialized. ... I'm not too familiar with reaching definitions, do they take control dependencies into account? It would often be helpful if an uninitialized variable could be automatically set to a "poison" value by the compiler. This would prevent one major cause of hard-to-find context-dependent bugs. It sounds like this can easily be implemented by emitting real code for the ghost definitions; dead code elimination would then zap it in all cases where there isn't a problem. Have you considered this? > Also, I'm about to add def-def chains to model non-killing > definitions like: > > 1: int a, b *p; > 2: > 3: a = 4; > 4: *p = 3; > 5: b = a + 1; > > The use of a at line 5 may be reached by the definitions of *p > and a at lines 4 and 3, respectively. But this part is nowhere > near ready. Hmmm... since p itself is not initialized, it seems like you'd want to complain about it and then assume it doesn't alias anything. > - Compute the SSA form. This involves computing immediate > dominators and dominance frontiers. I believe the algorithms > we have in GCC are quite quick, but I haven't really looked. If I remember correctly we are using the state-of-the-art algorithm, but its use of sbitmaps may cause problems. (looking at ssa.c - dunno if the same code is used for trees). > > It'd be nice if we could generate the warnings with > > optimization off; that's always been a wart. > > > Definitiely possible. We only need to make -Wuninitialized > trigger -ftree-ssa. Cool. zw ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: better -Wuninitialized (Re: Ada files now checked in) 2001-10-07 10:53 ` better -Wuninitialized (Re: Ada files now checked in) Zack Weinberg @ 2001-10-07 10:57 ` Joseph S. Myers 2001-10-07 11:23 ` Diego Novillo 2001-10-07 11:21 ` Diego Novillo 2001-10-07 11:29 ` Daniel Berlin 2 siblings, 1 reply; 17+ messages in thread From: Joseph S. Myers @ 2001-10-07 10:57 UTC (permalink / raw) To: Zack Weinberg; +Cc: Diego Novillo, gcc On Sun, 7 Oct 2001, Zack Weinberg wrote: > > Definitiely possible. We only need to make -Wuninitialized > > trigger -ftree-ssa. > > Cool. Would -ftree-ssa ever affect code generation? It seems a bad idea for warning options to change code generation at all. -- Joseph S. Myers jsm28@cam.ac.uk ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: better -Wuninitialized (Re: Ada files now checked in) 2001-10-07 10:57 ` Joseph S. Myers @ 2001-10-07 11:23 ` Diego Novillo 0 siblings, 0 replies; 17+ messages in thread From: Diego Novillo @ 2001-10-07 11:23 UTC (permalink / raw) To: Joseph S. Myers; +Cc: Zack Weinberg, gcc On Sun, 07 Oct 2001, Joseph S. Myers wrote: > On Sun, 7 Oct 2001, Zack Weinberg wrote: > > > > Definitiely possible. We only need to make -Wuninitialized > > > trigger -ftree-ssa. > > > > Cool. > > Would -ftree-ssa ever affect code generation? It seems a bad idea for > warning options to change code generation at all. > No. It only builds the analysis framework (flowgraph, data references, SSA web, reaching defs, reached uses, etc). Diego. ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: better -Wuninitialized (Re: Ada files now checked in) 2001-10-07 10:53 ` better -Wuninitialized (Re: Ada files now checked in) Zack Weinberg 2001-10-07 10:57 ` Joseph S. Myers @ 2001-10-07 11:21 ` Diego Novillo 2001-10-07 11:55 ` Zack Weinberg 2001-10-07 11:29 ` Daniel Berlin 2 siblings, 1 reply; 17+ messages in thread From: Diego Novillo @ 2001-10-07 11:21 UTC (permalink / raw) To: Zack Weinberg; +Cc: gcc On Sun, 07 Oct 2001, Zack Weinberg wrote: > > - if its only reaching definition is the ghost def, the variable > > *is* used uninitialized. > > > > - if one of its reaching definitions is the ghost def, the > > variable *may be* used uninitialized. > ... > > I'm not too familiar with reaching definitions, do they take control > dependencies into account? > Yes, that's what the SSA form is for: 1 int a, b; 2 3 b = foo(); 4 if (b < 100) 5 a = 10; 6 b = b + a; SSA will place a phi-term for A after line 5 (the first block outisde the if-statement). This will be a phi-term with two arguments, one for the definition of A at line 5 and the other for the ghost definition at line 0: phi(A) = (def(A,5), def(A, 0)). When computing reaching definitions, the algorithm follows all the use-def chains for every use. The use of A at line 6 is reached by that phi-term. Following the phi-term arguments takes you to def(A,5) and def(A,0). So, you end up with the set {def(A,5), def(A,0)} as the set of reaching definitions for A at line 6. Since one of them is the ghost definition, that use *may be* use uninitialized. > It would often be helpful if an uninitialized variable could be > automatically set to a "poison" value by the compiler. This would > prevent one major cause of hard-to-find context-dependent bugs. It > sounds like this can easily be implemented by emitting real code for > the ghost definitions; dead code elimination would then zap it in all > cases where there isn't a problem. Have you considered this? > Not really. But it is definitely doable. The only problem is what to consider a 'poison' value. OTOH, if the compiler is already warning you that you're using the thing uninitialized, why would you also need this run-time trick? > > Also, I'm about to add def-def chains to model non-killing > > definitions like: > > > > 1: int a, b *p; > > 2: > > 3: a = 4; > > 4: *p = 3; > > 5: b = a + 1; > > > > The use of a at line 5 may be reached by the definitions of *p > > and a at lines 4 and 3, respectively. But this part is nowhere > > near ready. > > Hmmm... since p itself is not initialized, it seems like you'd want to > complain about it and then assume it doesn't alias anything. > Hmm, I should've initialized p in the example. But good point. This would've given you a warning for *p. De-referencing a pointer is a use of the pointer and a def of every variable in its equivalence set. In this case, we could empty the equivalence set if p is used uninitialized. > > - Compute the SSA form. This involves computing immediate > > dominators and dominance frontiers. I believe the algorithms > > we have in GCC are quite quick, but I haven't really looked. > > If I remember correctly we are using the state-of-the-art algorithm, > but its use of sbitmaps may cause problems. (looking at ssa.c - dunno > if the same code is used for trees). > In tree SSA we call calculate_dominance_info and compute_dominance_frontiers directly. Also, the code uses sbitmaps quite frequently. The bitmaps are typically O(n_basic_blocks). What problem are you referring to? Diego. ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: better -Wuninitialized (Re: Ada files now checked in) 2001-10-07 11:21 ` Diego Novillo @ 2001-10-07 11:55 ` Zack Weinberg 2001-10-07 12:06 ` Daniel Berlin 2001-10-07 16:01 ` Diego Novillo 0 siblings, 2 replies; 17+ messages in thread From: Zack Weinberg @ 2001-10-07 11:55 UTC (permalink / raw) To: Diego Novillo; +Cc: gcc On Sun, Oct 07, 2001 at 02:21:31PM -0400, Diego Novillo wrote: > On Sun, 07 Oct 2001, Zack Weinberg wrote: > > > > - if its only reaching definition is the ghost def, the variable > > > *is* used uninitialized. > > > > > > - if one of its reaching definitions is the ghost def, the > > > variable *may be* used uninitialized. > > ... > > > > I'm not too familiar with reaching definitions, do they take control > > dependencies into account? > > > Yes, that's what the SSA form is for: > > 1 int a, b; > 2 > 3 b = foo(); > 4 if (b < 100) > 5 a = 10; > 6 b = b + a; The question is what happens with 1 int a, b; 2 3 b = foo(); 4 if (b < 100) 5 a = 10; 6 bar(); 7 if (b < 100) 8 b = b + a; which is the canonical case that the current code gets wrong. (And imagine that line 7 is actually several hundred lines of spaghetti which do not touch A or B.) hmm... At line 6, the reaching set for A is {def(A, 5), def(A, 0)}, but at line 7 it ought to be just {def(A, 5)}. Does it know that? > > It would often be helpful if an uninitialized variable could be > > automatically set to a "poison" value by the compiler. This would > > prevent one major cause of hard-to-find context-dependent bugs. It > > sounds like this can easily be implemented by emitting real code for > > the ghost definitions; dead code elimination would then zap it in all > > cases where there isn't a problem. Have you considered this? > > > Not really. But it is definitely doable. The only problem is > what to consider a 'poison' value. Something that will cause an immediate fault in the program if it gets used. More, you want a value that is *likely* to get used and therefore to expose the bug. (Zero, for instance, is a bad choice.) For pointers, this is easy - pick a non-NULL value pointing into unmapped memory. Floats should probably get a signalling NaN. Integers are harder, but on the theory that numbers in real life tend to be small, use a big one. For signed int, probably it should be negative on the theory that the programmer may not have considered negative numbers. (But *not* -1.) Booleans you are probably up a creek with. Another consideration is that the bit pattern ought to be recognizable as a poison value. The garbage collector uses 0xA5A5A5A5.... for this reason. It's also an opportunity to make jokes with the hexadecimal constant. Dead beef anyone? > OTOH, if the compiler is already warning you that you're using the > thing uninitialized, why would you also need this run-time trick? Because you may incorrectly think you have inspected the code and determined that there is no actual problem. This is of course more likely the more false positives there are. > Hmm, I should've initialized p in the example. But good point. > This would've given you a warning for *p. De-referencing a > pointer is a use of the pointer and a def of every variable in > its equivalence set. In this case, we could empty the > equivalence set if p is used uninitialized. Sounds good. > In tree SSA we call calculate_dominance_info and > compute_dominance_frontiers directly. Also, the code uses > sbitmaps quite frequently. The bitmaps are typically > O(n_basic_blocks). What problem are you referring to? The bitmaps are probably sparse, and n_basic_blocks can blow up, at which point your memory usage blows up too. Brad Lucier has some good examples of this problem. zw ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: better -Wuninitialized (Re: Ada files now checked in) 2001-10-07 11:55 ` Zack Weinberg @ 2001-10-07 12:06 ` Daniel Berlin 2001-10-07 16:01 ` Diego Novillo 1 sibling, 0 replies; 17+ messages in thread From: Daniel Berlin @ 2001-10-07 12:06 UTC (permalink / raw) To: Zack Weinberg; +Cc: Diego Novillo, gcc > >> In tree SSA we call calculate_dominance_info and >> compute_dominance_frontiers directly. Also, the code uses >> sbitmaps quite frequently. The bitmaps are typically >> O(n_basic_blocks). What problem are you referring to? > > The bitmaps are probably sparse, Definitely, actually. Dominance frontiers have to be sparse. > and n_basic_blocks can blow up, at > which point your memory usage blows up too. Brad Lucier has some good > examples of this problem. Yes, but i'm taking care of this, so no worries. Without ssa even enabled, the new bitmaps i'm performance tuning (still), saves about 30% memory over current bitmaps. For instance, compiling one file (I can't remember if it's expr.c or 20001226-1.c, i forget at the moment) at -O2 normally takes 130 meg, peak. It now takes 100 meg, peak. This is without modifying anything to use sparse bitmaps, just replacing the existing bitmap implementation. > > zw ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: better -Wuninitialized (Re: Ada files now checked in) 2001-10-07 11:55 ` Zack Weinberg 2001-10-07 12:06 ` Daniel Berlin @ 2001-10-07 16:01 ` Diego Novillo 1 sibling, 0 replies; 17+ messages in thread From: Diego Novillo @ 2001-10-07 16:01 UTC (permalink / raw) To: Zack Weinberg; +Cc: gcc On Sun, 07 Oct 2001, Zack Weinberg wrote: > 1 int a, b; > 2 > 3 b = foo(); > 4 if (b < 100) > 5 a = 10; > 6 bar(); > 7 if (b < 100) > 8 b = b + a; > Ah, now I see what you're getting at. You would get a warning in this case. Currently there is no pruning of reaching definitions sets. We could add some, but you have to be careful not to make it excessively expensive. Also remember that this warning is triggered rather early in the analysis. Well before any transformations are done, suppose that for whatever reason B is deemed to always be greater than 100. You would've gotten a warning for dead code. > > OTOH, if the compiler is already warning you that you're using the > > thing uninitialized, why would you also need this run-time trick? > > Because you may incorrectly think you have inspected the code and > determined that there is no actual problem. This is of course more > likely the more false positives there are. > True. 0xdeadbeef sounds good for pointers and word integers. > The bitmaps are probably sparse, and n_basic_blocks can blow up, at > which point your memory usage blows up too. Brad Lucier has some good > examples of this problem. > OK. We should take a look at this once the implementation starts to stabilize. Diego. ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: better -Wuninitialized (Re: Ada files now checked in) 2001-10-07 10:53 ` better -Wuninitialized (Re: Ada files now checked in) Zack Weinberg 2001-10-07 10:57 ` Joseph S. Myers 2001-10-07 11:21 ` Diego Novillo @ 2001-10-07 11:29 ` Daniel Berlin 2 siblings, 0 replies; 17+ messages in thread From: Daniel Berlin @ 2001-10-07 11:29 UTC (permalink / raw) To: Zack Weinberg; +Cc: Diego Novillo, gcc On Sunday, October 7, 2001, at 01:53 PM, Zack Weinberg wrote: > On Sun, Oct 07, 2001 at 01:21:01PM -0400, Diego Novillo wrote: >> On Sun, 07 Oct 2001, Zack Weinberg wrote: >>> Maybe you could change the warning message to "...used uninitialized >>> here" or "at this point" or something like that? Just to be clear >>> it's not the same old "somewhere in the function" message. >>> >> Sure. > > Thanks. > >>> I notice it says "_is_ used uninitialized". Does that mean you've >>> eliminated the old false positive problems? >>> >> That's the intent. The new code still spews out false positives, >> that's what I'm now working on. >> >> The analysis depends on the computation of reaching definitions. >> Prior to computing the SSA form, we insert ghost definitions for >> every symbol in the entry basic block. After reaching >> definitions, we traverse all the variable use references in the >> function. For every use: >> >> - if its only reaching definition is the ghost def, the variable >> *is* used uninitialized. >> >> - if one of its reaching definitions is the ghost def, the >> variable *may be* used uninitialized. > ... > > I'm not too familiar with reaching definitions, do they take control > dependencies into account? > > It would often be helpful if an uninitialized variable could be > automatically set to a "poison" value by the compiler. This would > prevent one major cause of hard-to-find context-dependent bugs. It > sounds like this can easily be implemented by emitting real code for > the ghost definitions; dead code elimination would then zap it in all > cases where there isn't a problem. Have you considered this? > >> Also, I'm about to add def-def chains to model non-killing >> definitions like: >> >> 1: int a, b *p; >> 2: >> 3: a = 4; >> 4: *p = 3; >> 5: b = a + 1; >> >> The use of a at line 5 may be reached by the definitions of *p >> and a at lines 4 and 3, respectively. But this part is nowhere >> near ready. > > Hmmm... since p itself is not initialized, it seems like you'd want to > complain about it and then assume it doesn't alias anything. > >> - Compute the SSA form. This involves computing immediate >> dominators and dominance frontiers. I believe the algorithms >> we have in GCC are quite quick, but I haven't really looked. > > If I remember correctly we are using the state-of-the-art algorithm, Not anymore, at least for phi placement. Dominance calculation is as fast as it's gonna get without using *much* more complex datastructures (microtrees and whatnot). > but its use of sbitmaps may cause problems. (looking at ssa.c - dunno > if the same code is used for trees). > ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: Ada files now checked in 2001-10-07 10:24 ` Diego Novillo 2001-10-07 10:53 ` better -Wuninitialized (Re: Ada files now checked in) Zack Weinberg @ 2001-10-07 11:05 ` Daniel Berlin 2001-10-07 11:29 ` Diego Novillo 2001-10-14 7:53 ` Joern Rennecke 2 siblings, 1 reply; 17+ messages in thread From: Daniel Berlin @ 2001-10-07 11:05 UTC (permalink / raw) To: Diego Novillo; +Cc: Zack Weinberg, dewar, bosch, gcc, kenner .... > Building the FUD chains is like O(SxNxE) (could be wrong, I'm > quoting from memory). There is a linear phi placing algorithm > which I plan to switch to. You meen Sreedhar and gao's? If so, i've got it coded already for the tree ssa stuff. .... > Diego. ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: Ada files now checked in 2001-10-07 11:05 ` Ada files now checked in Daniel Berlin @ 2001-10-07 11:29 ` Diego Novillo 2001-10-07 11:37 ` Daniel Berlin 0 siblings, 1 reply; 17+ messages in thread From: Diego Novillo @ 2001-10-07 11:29 UTC (permalink / raw) To: Daniel Berlin; +Cc: Zack Weinberg, dewar, bosch, gcc, kenner On Sun, 07 Oct 2001, Daniel Berlin wrote: > .... > > Building the FUD chains is like O(SxNxE) (could be wrong, I'm > > quoting from memory). There is a linear phi placing algorithm > > which I plan to switch to. > > You meen Sreedhar and gao's? > Yes. These two: @InProceedings{ bib:johnson.ea-94, title = "The Program Structure Tree: Computing Control Regions in Linear Time", author = "R. Johnson and D. Pearson and K. Pingali", booktitle = pldi94, address = "Orlando, Florida", month = jun, year = "1994", pages = "171--185" } @InProceedings{ bib:sreedhar.ea-95, author = "V. C. Sreedhar and G. R. Gao", title = "A Linear Time Algorithm for Placing ${\phi}$-nodes", pages = "62--73", isbn = "0-89791-692-1", booktitle = popl95, month = jan, publisher = "ACM Press", address = "New York, NY, USA", year = "1995" } > If so, i've got it coded already for the tree ssa stuff. > Cool. Mind submitting the patch? Thanks. Diego. ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: Ada files now checked in 2001-10-07 11:29 ` Diego Novillo @ 2001-10-07 11:37 ` Daniel Berlin 0 siblings, 0 replies; 17+ messages in thread From: Daniel Berlin @ 2001-10-07 11:37 UTC (permalink / raw) To: Diego Novillo; +Cc: Zack Weinberg, dewar, bosch, gcc, kenner On Sunday, October 7, 2001, at 02:26 PM, Diego Novillo wrote: > On Sun, 07 Oct 2001, Daniel Berlin wrote: > >> .... >>> Building the FUD chains is like O(SxNxE) (could be wrong, I'm >>> quoting from memory). There is a linear phi placing algorithm >>> which I plan to switch to. >> >> You meen Sreedhar and gao's? >> > Yes. These two: > > @InProceedings{ bib:johnson.ea-94, > title = "The Program Structure Tree: Computing Control Regions in > Linear Time", > author = "R. Johnson and D. Pearson and K. Pingali", > booktitle = pldi94, > address = "Orlando, Florida", > month = jun, > year = "1994", > pages = "171--185" > } > > @InProceedings{ bib:sreedhar.ea-95, > author = "V. C. Sreedhar and G. R. Gao", > title = "A Linear Time Algorithm for Placing ${\phi}$-nodes", > pages = "62--73", > isbn = "0-89791-692-1", > booktitle = popl95, > month = jan, > publisher = "ACM Press", > address = "New York, NY, USA", > year = "1995" > } > >> If so, i've got it coded already for the tree ssa stuff. >> > Cool. Mind submitting the patch? > It's not a single patch (functionally, anyway), but i'll submit it sometime soon. I construct an explicit dominator tree (from the idoms), then augment it with the DJ graph info. This is because APT ("APT: a data structure for optimal control dependence computation", http://www.acm.org/pubs/citations/proceedings/pldi/207110/p32-pingali/ ) uses a dominator tree augmented with info as well, so it didn't make sense to just make a dj-graph specific version. It's of course, largely non-tree-ssa specific, however, i used it in doing loop optimizations for tree-ssa. > Thanks. Diego. ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: Ada files now checked in 2001-10-07 10:24 ` Diego Novillo 2001-10-07 10:53 ` better -Wuninitialized (Re: Ada files now checked in) Zack Weinberg 2001-10-07 11:05 ` Ada files now checked in Daniel Berlin @ 2001-10-14 7:53 ` Joern Rennecke 2 siblings, 0 replies; 17+ messages in thread From: Joern Rennecke @ 2001-10-14 7:53 UTC (permalink / raw) To: Diego Novillo; +Cc: Zack Weinberg, dewar, bosch, gcc, kenner > - if its only reaching definition is the ghost def, the variable > *is* used uninitialized. Not generally true. The uninitialized use might never be executed. Back to the halting problem... ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: better -Wuninitialized (Re: Ada files now checked in) @ 2001-10-07 15:19 dewar 0 siblings, 0 replies; 17+ messages in thread From: dewar @ 2001-10-07 15:19 UTC (permalink / raw) To: dnovillo, zack; +Cc: gcc <<1 int a, b; 2 3 b = foo(); 4 if (b < 100) 5 a = 10; 6 bar(); 7 if (b < 100) 8 b = b + a; which is the canonical case that the current code gets wrong. (And imagine that line 7 is actually several hundred lines of spaghetti which do not touch A or B.) >> I am not sure I would say that current code gets this "wrong". Sure you can imagine building this particular theorem into the code, but you will always have cases involving arbitrarily complex theorems. I do agree it would be desirable to go just far enough to catch this case, i.e. recognize absolutely identical conditions with invariant operands, but even this is much trickier than people might imagine. <<> > It would often be helpful if an uninitialized variable could be > > automatically set to a "poison" value by the compiler. This would >> In Ada, there is Normalize_Scalars which has this kind of effect, and it has been extended in GNAT with the addition of Initialize_Scalars, which allows the value set to be specified at bind time. So you can see if your code depends on the value used. ^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2001-10-14 7:53 UTC | newest] Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2001-10-06 18:25 Ada files now checked in dewar 2001-10-07 0:38 ` Diego Novillo 2001-10-07 0:59 ` Zack Weinberg 2001-10-07 10:24 ` Diego Novillo 2001-10-07 10:53 ` better -Wuninitialized (Re: Ada files now checked in) Zack Weinberg 2001-10-07 10:57 ` Joseph S. Myers 2001-10-07 11:23 ` Diego Novillo 2001-10-07 11:21 ` Diego Novillo 2001-10-07 11:55 ` Zack Weinberg 2001-10-07 12:06 ` Daniel Berlin 2001-10-07 16:01 ` Diego Novillo 2001-10-07 11:29 ` Daniel Berlin 2001-10-07 11:05 ` Ada files now checked in Daniel Berlin 2001-10-07 11:29 ` Diego Novillo 2001-10-07 11:37 ` Daniel Berlin 2001-10-14 7:53 ` Joern Rennecke 2001-10-07 15:19 better -Wuninitialized (Re: Ada files now checked in) dewar
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).