001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004-2007 Robert Grimm
004: *
005: * This program is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU General Public License
007: * version 2 as published by the Free Software Foundation.
008: *
009: * This program is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: * GNU General Public License for more details.
013: *
014: * You should have received a copy of the GNU General Public License
015: * along with this program; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019: package xtc.parser;
020:
021: import xtc.Constants;
022:
023: import xtc.type.AST;
024:
025: import xtc.util.Runtime;
026:
027: /**
028: * Visitor to inline productions. If cost-based inlining is enabled,
029: * this visitor inlines productions with a {@link CostEstimator cost
030: * estimate} less or equal to the {@link #MAX_COST maximum cost}.
031: * However, to avoid changing a production's semantic value,
032: * cost-based inlining is limited to void, text-only, and token-level
033: * productions. Independent of whether cost-based inlining is enabled
034: * or not, this visitor inlines productions that are referenced from a
035: * production consisting solely of a nonterminal (which, optionally,
036: * may be bound to {@link CodeGenerator#VALUE}). Note that generic
037: * productions are never inlined; neither are productions with the
038: * state attribute.
039: *
040: * <p />Note that, to be effective, this visitor requires that
041: * text-only productions have been {@link TextTester marked} as such.
042: * Similarly, token-level productions need to have beeen {@link
043: * Tokenizer marked} as such. Further note that, if this visitor
044: * inlines productions, the resulting grammar needs to be {@link
045: * Simplifier simplified} before further processing. Also note that
046: * this visitor may create new opportunities for the {@link
047: * DeadProductionEliminator elimination of dead productions}. This
048: * visitor assumes that the entire grammar is contained in a single
049: * module.
050: *
051: * @author Robert Grimm
052: * @version $Revision: 1.52 $
053: */
054: public class Inliner extends GrammarVisitor {
055:
056: /** The maximum cost for inlining productions at arbitrary positions. */
057: public static final int MAX_COST = 1;
058:
059: /** The flag for whether to inline non-transient productions. */
060: public static final boolean INLINE_PERSISTENT = true;
061:
062: /** Flag for whether the grammar has the state attribute. */
063: protected boolean attributeState;
064:
065: /** Flag for whether this production inliner has inlined a production. */
066: protected boolean inlined;
067:
068: /**
069: * Create a new production inliner.
070: *
071: * @param runtime The runtime.
072: * @param analyzer The analyzer utility.
073: */
074: public Inliner(Runtime runtime, Analyzer analyzer) {
075: super (runtime, analyzer);
076: }
077:
078: /**
079: * Determine whether the specified production is void, text-only, or
080: * token-level.
081: *
082: * @param p The production.
083: * @return <code>true</code> if the production is either text-only
084: * or void.
085: */
086: protected boolean isBasic(final Production p) {
087: return (AST.isVoid(p.type)
088: || p.getBooleanProperty(Properties.TEXT_ONLY) || p
089: .getBooleanProperty(Properties.TOKEN));
090: }
091:
092: /**
093: * Record that the specified production has been inlined and, if
094: * necessary, print a message to the console.
095: *
096: * @param p The production.
097: */
098: protected void inlined(Production p) {
099: inlined = true;
100:
101: if (runtime.test("optionVerbose")) {
102: System.err.println("[Inlining " + p.qName + " into "
103: + analyzer.current().qName + "]");
104: }
105: }
106:
107: /**
108: * Process the specified grammar.
109: *
110: * @param m The grammar module.
111: * @return <code>Boolean.TRUE</code> if the grammar has been modified,
112: * otherwise <code>Boolean.FALSE</code>.
113: */
114: public Object visit(Module m) {
115: CostEstimator cost = null;
116: boolean changed = false;
117:
118: if (runtime.test("optimizeCost")) {
119: cost = new CostEstimator(analyzer);
120: }
121:
122: // Perform inlining until we reach a fixed-point. We are
123: // guaranteed to reach a fixed-point because the cost estimator's
124: // estimate for a production includes the costs of any referenced
125: // productions, thus marking all recursive productions with an
126: // unlimited cost.
127: do {
128: // Annotate productions with their cost estimates.
129: if (runtime.test("optimizeCost")) {
130: cost.dispatch(m);
131: }
132:
133: // Initialize the per-grammar state.
134: analyzer.register(this );
135: analyzer.init(m);
136: attributeState = m.hasAttribute(Constants.ATT_STATEFUL
137: .getName());
138: inlined = false;
139:
140: // Process the productions.
141: for (Production p : m.productions)
142: analyzer.process(p);
143:
144: // Did the grammar change?
145: if (inlined) {
146: changed = true;
147: }
148: } while (inlined);
149:
150: return (changed) ? Boolean.TRUE : Boolean.FALSE;
151: }
152:
153: /** Visit the specified nonterminal. */
154: public Element visit(NonTerminal nt) {
155: boolean bound = isBound;
156: isBound = false;
157:
158: // Get the referenced production.
159: FullProduction p = analyzer.lookup(nt);
160:
161: if (Generifier.isGeneric(p)
162: || AST.isList(p.type)
163: || (attributeState && (p
164: .hasAttribute(Constants.ATT_STATEFUL) || p
165: .hasAttribute(Constants.ATT_RESETTING)))) {
166: // Never inline generic or list-valued productions, nor
167: // productions with the state or reset attribute.
168: return nt;
169: }
170:
171: // Get the referenced production's expression.
172: Element e = Analyzer.strip(p.choice);
173:
174: if (e instanceof NonTerminal) {
175: // We only inline a lone nonterminal if the production is
176: // transient. That way, a lone nonterminal can be used to force
177: // memoization of a transient production.
178: if (!p.isMemoized()
179: && !p.hasAttribute(Constants.ATT_NO_INLINE)) {
180: inlined(p);
181: // Copy the nonterminal being inlined and update the copy's
182: // location to the original nonterminal's location, so that
183: // errors point to the right location.
184: NonTerminal copy = new NonTerminal((NonTerminal) e);
185: copy.setLocation(nt);
186: return copy;
187: } else {
188: return nt;
189: }
190:
191: } else if (e instanceof Binding) {
192: Binding b = (Binding) e;
193: Element e2 = Analyzer.strip(b.element);
194:
195: if (CodeGenerator.VALUE.equals(b.name)
196: && (e2 instanceof NonTerminal)) {
197: // We only inline a lone nonterminal if the production is
198: // transient. That way, a lone nonterminal can be used to
199: // force memoization of a transient production.
200: if (!p.isMemoized()
201: && !p.hasAttribute(Constants.ATT_NO_INLINE)) {
202: inlined(p);
203: // Copy the nonterminal being inlined and update the copy's
204: // location to the original nonterminal's location, so that
205: // errors point to the right location.
206: NonTerminal copy = new NonTerminal((NonTerminal) e2);
207: copy.setLocation(nt);
208: return copy;
209: } else {
210: return nt;
211: }
212: }
213: }
214:
215: if ((!(isBasic(analyzer.current()) && (INLINE_PERSISTENT || (!analyzer
216: .current().isMemoized()))))
217: || bound) {
218: // If the current production is not void or text-only or if the
219: // nonterminal is bound, we don't do any other inlining.
220: return nt;
221:
222: } else if (runtime.test("optimizeCost")
223: && (MAX_COST >= (Integer) p
224: .getProperty(Properties.COST))
225: && !p.hasAttribute(Constants.ATT_NO_INLINE)
226: && (INLINE_PERSISTENT || (!p.isMemoized()))) {
227: // If the referenced production's cost estimate is low enough,
228: // inline the referenced production.
229: inlined(p);
230: return analyzer.copy(p.choice);
231:
232: } else {
233: return nt;
234: }
235: }
236:
237: }
|