From: Chris Wilson <cwilson@CS.Stanford.EDU>
Date: Fri, 24 Feb 95 3:40:47 PST
Subject: Re: flat list inconsistencies undetected (was find_exposed_refs
Message-Id: <CMM.0.90.4.793626047.cwilson@Xenon.Stanford.EDU>
> How distressingly efficient! I'll blame my relative unfamiliarity
> with the code for the baroque solution...
You came up with a perfectly good solution. The cloning code is
intricate and scatered all over the place, so just the fact that you
figured out the problem and a good fix for it is pretty impressive.
> So, an unpleasantness that someone may or may not consider a bug:
>
> Given a flat list of instructions, if I take an instruction which
> references a previous instruction as a source operand and move it
> inside a block, we now have a cross-block reference. No protest is
> raised at the time, nor in saving out the altered procedure --
> however, it cannot be reloaded again, since only the scope containing
> the referencing instruction is scanned for the referenced instruction.
Yeah, this is unpleasant, but we don't consider it a bug. There are
quite a few rules that the SUIF library assumes the user follows
without checking. If the user violates the rules, the results may be
strange failures later on. One of the most common problems is using a
symbol outside its scope. The library will write it out without
noticing, then when it tries to read in the file it will give the
not-too-helpful ``unknown sym_id'' message.
There are several reasons SUIF works this way. For one thing, it
allows more flexibility. The user can have code that temporarily
violates the rules as long as they know where the rules are used and
put it back in the correct form before the rule is used. Another
advantage to this approach is that the runtime overhead of checking
the rules is avoided. And of course it is easier to implement --
effort we might put into writing code to check assumptions can go into
other features.
In this particular case of instruction operands living across block
boundaries, if there is a bug, it is in the documentation. The
documentation says they cannot live across ``basic blocks''. It is
also illegal to have them live across the beginning or end of a SUIF
tree_block. So what we intended was to make it illegal for the user
to create such code.
We do want to hear about documentation bugs and we will do our best to
deal with them.
> The workaround I'm using is to convert to trees just before saving
> out; I get a warning, it promotes the sources to variables, and
> everything seems to work from there. Whether or not I should have to
> do this is a matter of argument, I think, but I'll claim it shouldn't
> save it out quietly if it can't recover it later.
The official position of SUIF is that it's illegal to have these
instruction operands live across tree_block boundaries. If you want
to violate this rule and know how to make it work, do it at your own
risk.
> Finally, as a side-note: s2c does only a half-hearted job of dealing
> with variables with the same name in different scopes being referenced
> in the same piece of code as a result of inlining, but I think I'm not
> following spec. in having such identically-named variables hanging
> around... any suggestions?
Halfhearted? There is code in s2c written to very strictly check such
things and do renaming. s2c is very careful about scoping at every
level. It shouldn't matter whether the SUIF variables all have the
same name, have the same name as enumeration value specifiers, or
keywords, or aren't even legal C identifiers. That's what
"namespace.cc" is all about.
Having said that, however, I have to admit that I never tested any of
the namespace code when I wrote it since there was no convenient
source of files with conflicts (anything coming out of the front-end
directly can't have such conflicts). Since the release, I've fixed
three bugs in "namespace.cc" in our internal version of SUIF, and
these will be included in the next release. The most important of
these is the one that is probably what caused you to say it was
``half-hearted''. Here's a patch to fix it:
--cut-here----cut-here----cut-here----cut-here----cut-here----cut-here--
*** namespace.cc Fri Feb 24 03:15:33 1995
--- namespace.cc.1.6 Fri Feb 24 03:07:10 1995
***************
*** 880,888 ****
if (the_ldc->value().is_symbol())
{
if (the_ldc->value().symbol() == ref_data->symbol)
ref_data->found = TRUE;
}
- return;
}
if (!ref_data->symbol->is_var())
--- 880,890 ----
if (the_ldc->value().is_symbol())
{
if (the_ldc->value().symbol() == ref_data->symbol)
+ {
ref_data->found = TRUE;
+ return;
+ }
}
}
if (!ref_data->symbol->is_var())
***************
*** 889,894 ****
--- 891,903 ----
return;
var_sym *the_var = (var_sym *)(ref_data->symbol);
+
+ if (operand(the_var) == the_instr->dst_op())
+ {
+ ref_data->found = TRUE;
+ return;
+ }
+
unsigned num_srcs = the_instr->num_srcs();
for (unsigned src_num = 0; src_num < num_srcs; ++src_num)
{
--cut-here----cut-here----cut-here----cut-here----cut-here----cut-here--
If this patch doesn't fix your scoping problems, let me know.
The problem this patch fixes is as follows: When looking for
namespace conflicts, s2c knows that the local symbol covers the
less-local symbol, so as long as the less-local symbol is not used in
the inner scope, there is no problem. So when a symbol has the same
name as one in an enclosing scope, it looks for references in the
local scope to the outer symbol. Is such a reference exists, the name
change is made. The problem is that the code to check for references
doesn't look in destination operands. The patch fixes that.
The other two bugs are uncommon cases. One has to do with renaming
structure fields -- after the renaming, if a "fields" annotation is
found with the original name, s2c fails with an error message. The
fix is to keep track of the original names as well as the new
versions, and its a fairly big change. Since each structure (or
union) has its own scope, this only happens if a structure has two
members with the same name, or a member with a name that is a C
identifier (such as ``for''). The other bug also affects only
structure or union fields. The released version of the code was
failing to check for reserved words or the names of macros SUIF
defines in structure members.
I'll send patches for either of these on request, but they'll only
matter if you are doing strange things with structure member names.
As I said, the next release will fix these problems.
> Jeremy
>
> P.S. I really do like SUIF! I don't want to come off as a chronic
> complainer...
That's good to know. I'm glad you find it useful. We're always
interested in hearing what people are doing with the system.
--Chris
From: jhbrown@ai.mit.edu (Jeremy H. Brown)
Date: Fri, 24 Feb 95 05:28:09 EST
Subject: flat list inconsistencies undetected (was find_exposed_refs failure on flat instruction lists)
Message-Id: <9502241028.AA05484@third-rail>
How distressingly efficient! I'll blame my relative unfamiliarity
with the code for the baroque solution...
So, an unpleasantness that someone may or may not consider a bug:
Given a flat list of instructions, if I take an instruction which
references a previous instruction as a source operand and move it
inside a block, we now have a cross-block reference. No protest is
raised at the time, nor in saving out the altered procedure --
however, it cannot be reloaded again, since only the scope containing
the referencing instruction is scanned for the referenced instruction.
The workaround I'm using is to convert to trees just before saving
out; I get a warning, it promotes the sources to variables, and
everything seems to work from there. Whether or not I should have to
do this is a matter of argument, I think, but I'll claim it shouldn't
save it out quietly if it can't recover it later.
Finally, as a side-note: s2c does only a half-hearted job of dealing
with variables with the same name in different scopes being referenced
in the same piece of code as a result of inlining, but I think I'm not
following spec. in having such identically-named variables hanging
around... any suggestions?
Jeremy
P.S. I really do like SUIF! I don't want to come off as a chronic
complainer...
From: Chris Wilson <cwilson@CS.Stanford.EDU>
Date: Fri, 24 Feb 95 1:52:36 PST
Subject: Re: find_exposed_refs failure on flat instruction lists
Message-Id: <CMM.0.90.4.793619556.cwilson@Xenon.Stanford.EDU>
> find_exposed_refs fails on flat instruction lists, falsely claiming
> that several instructions reference instructions not included in the
> item being scanned for dangling references.
>
> It looks to me like the code to handle this stuff was never finished.
> Here is my patch to the suif sources to fix it; it consists of
> context-diffs on the files instruction.cc, trees.h, and trees.cc
You're right that the handling of flat lists of instructions in the
cloning-related code broken. And your fix will make all the clone()
routines work on flat lists as long as the code is legal SUIF (no
references to instructions on different lists).
The resolve_exposed_refs() function will still have the very
questionable semantics of reporting dangling source instruction
pointers but not dangling destination instruction pointers, and
cloning code with dangling instruction pointers will silently put null
destination operands in the cloned code. But these are obscure points
and will require more extensive changes in the way instruction
references are handled.
> I've a suspicion that this could be made more efficient by not
> bothering to try remove_instr_ref for instructions that are in exprs,
> but what I've got seems to be a simple, working fix.
Yes, that is true. In fact, the place to pick up only instructions
that are not in expression trees is at the tree_instr level. You
could have added
r->remove_instr_ref(instr())
to the tree_instr::find_exposed_refs() method instead of to each of
the instruction methods. And since then remove_instr_ref() would only
be called in one place, you could just inline it there. Then the
whole patch would reduce to one line, changing:
void
tree_instr::find_exposed_refs (base_symtab *dst_scope, replacements *r)
{
if (instr()) instr()->find_exposed_refs(dst_scope, r);
find_annote_refs(dst_scope, r);
}
to:
void
tree_instr::find_exposed_refs (base_symtab *dst_scope, replacements *r)
{
if (instr()) instr()->find_exposed_refs(dst_scope, r);
+ delete r->oldinstrs.remove(r->oldinstrs.lookup(instr()));
find_annote_refs(dst_scope, r);
}
Then you get the efficiency of not doing the lookup inside expression
trees and it only changes one line of code.
All of this will be fixed in a future release of SUIF. In the
meantime, I'd recommend that anyone who might want to clone flat lists
of instructions make the change listed above.
> Jeremy Brown
Thanks for the bug report and for the patches.
--Chris
From: jhbrown@ai.mit.edu (Jeremy H. Brown)
Date: Fri, 24 Feb 95 03:42:15 EST
Subject: find_exposed_refs failure on flat instruction lists
Message-Id: <9502240842.AA05439@third-rail>
find_exposed_refs fails on flat instruction lists, falsely claiming
that several instructions reference instructions not included in the
item being scanned for dangling references.
It looks to me like the code to handle this stuff was never finished.
Here is my patch to the suif sources to fix it; it consists of
context-diffs on the files instruction.cc, trees.h, and trees.cc
I've a suspicion that this could be made more efficient by not
bothering to try remove_instr_ref for instructions that are in exprs,
but what I've got seems to be a simple, working fix.
Jeremy Brown
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
*** suif-1.0.1/src/suif/instruction.cc Wed Jun 15 00:57:49 1994
--- suif-dev/src/suif/instruction.cc Fri Feb 24 03:35:17 1995
***************
*** 665,670 ****
--- 665,671 ----
find_base_refs(dst_scope, r);
src1_op().find_exposed_refs(dst_scope, r);
src2_op().find_exposed_refs(dst_scope, r);
+ r->remove_instr_ref(this);
}
***************
*** 674,679 ****
--- 675,681 ----
find_base_refs(dst_scope, r);
src_op().find_exposed_refs(dst_scope, r);
r->add_sym_ref(target(), dst_scope);
+ r->remove_instr_ref(this);
}
***************
*** 682,687 ****
--- 684,690 ----
{
find_base_refs(dst_scope, r);
value().find_exposed_refs(dst_scope, r);
+ r->remove_instr_ref(this);
}
***************
*** 693,698 ****
--- 696,702 ----
for (unsigned n = 0; n < num_args(); n++) {
argument(n).find_exposed_refs(dst_scope, r);
}
+ r->remove_instr_ref(this);
}
***************
*** 706,711 ****
--- 710,716 ----
index(n).find_exposed_refs(dst_scope, r);
bound(n).find_exposed_refs(dst_scope, r);
}
+ r->remove_instr_ref(this);
}
***************
*** 718,723 ****
--- 723,729 ----
for (unsigned n = 0; n < num_labs(); n++) {
r->add_sym_ref(label(n), dst_scope);
}
+ r->remove_instr_ref(this);
}
***************
*** 726,731 ****
--- 732,738 ----
{
find_base_refs(dst_scope, r);
r->add_sym_ref(label(), dst_scope, TRUE);
+ r->remove_instr_ref(this);
}
***************
*** 736,741 ****
--- 743,749 ----
for (unsigned n = 0; n < num_srcs(); n++) {
src_op(n).find_exposed_refs(dst_scope, r);
}
+ r->remove_instr_ref(this);
}
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
*** suif-1.0.1/src/suif/trees.h Wed Jun 15 00:58:05 1994
--- suif-dev/src/suif/trees.h Fri Feb 24 03:35:17 1995
***************
*** 568,573 ****
--- 568,574 ----
void add_type_ref(type_node *t, base_symtab *dst_scope);
void add_def_ref(var_def *d, base_symtab *dst_scope);
void add_instr_ref(instruction *i);
+ void remove_instr_ref(instruction *i);
void add_tab_ref(base_symtab *t);
replacements& operator=(replacements &r);
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
*** suif-1.0.1/src/suif/trees.cc Wed Jun 15 00:58:05 1994
--- suif-dev/src/suif/trees.cc Fri Feb 24 03:35:17 1995
***************
*** 2040,2045 ****
--- 2040,2054 ----
oldinstrs.append(i);
}
+ void
+ replacements::remove_instr_ref (instruction *i)
+ {
+ /* it might not be here, but if it is, remove it and nuke
+ it's list_e */
+
+ delete oldinstrs.remove(oldinstrs.lookup(i));
+ }
+
/*
* Record references to parent symtabs.