Changeset 1307


Ignore:
Timestamp:
Aug 12, 2011, 2:17:59 AM (8 years ago)
Author:
shermer
Message:
  1. 0.7.2

Added PARAM instruction for declaring incoming definitions in incode.
Added basis bit fields as parameters to main incode routine.
Added routine to judge better variable label to VariableNamer?, and made CopyRemover? keep the better variable name if possible.
Introduced BasicBlockProperty?, DataflowWorkQueue?, and Dataflow to abstract dataflow problems (ongoing).
Wrote ReachingDefinitions? and ReachingProperty? to analyze (naturally) reaching definitions. This also provides "variable used but not defined" errors as appropriate.
New jar

Location:
proto/pebble/trunk
Files:
8 added
2 deleted
6 edited

Legend:

Unmodified
Added
Removed
  • proto/pebble/trunk/src/ast/transforms/ASTtoIncode.java

    r1287 r1307  
    364364                }
    365365                public void visitEnter(ExecutionBlockASTN node) {
    366                         BasicBlock b = new BasicBlock();
    367                         blocks.push(b);
    368                         argumentString.put(node, b.getName());
     366                        BasicBlock block = new BasicBlock();
     367                        blocks.push(block);
     368                        argumentString.put(node, block.getName());
     369
     370                        makeBasisBitsParams();
     371                }
     372                private void makeBasisBitsParams() {
     373                        final String BASIS_BITS_INSTANCE_NAME = "basis_bits";
     374                        final int NUM_BITS_PER_CHAR = 8;
     375                       
     376                        for(int b=0; b<NUM_BITS_PER_CHAR; b++) {
     377                                String symbol = BASIS_BITS_INSTANCE_NAME + String.format(".bit_%d", b);
     378                                Instruction instr = makeParam(symbol);
     379                                addToBlock(instr);
     380                        }
    369381                }
    370382                public void visitLeave(ExecutionBlockASTN node) {
    371383                        blocks.pop();
    372384                }
     385
    373386                public void visitLeave(ProgramBlockASTN node) {
    374387                        List<String> fragmentNames = new ArrayList<String>();
  • proto/pebble/trunk/src/incode/InstructionFactories.java

    r1287 r1307  
    6565
    6666        ///////////////////////////////////////////////////////////////////////////
    67         // structure instantiation
     67        // structure instantiation, parameters
    6868        ///////////////////////////////////////////////////////////////////////////
    6969        public static Instruction makeInstantiate(String var, String typeName) {
    7070                return new Instruction(Op.INSTANTIATE, var, typeName);
    7171        }
    72 
     72        public static Instruction makeParam(String var) {
     73                return new Instruction(Op.PARAM, var);
     74        }
     75       
    7376       
    7477        ///////////////////////////////////////////////////////////////////////////
  • proto/pebble/trunk/src/incode/Op.java

    r1287 r1307  
    3636        INSTANTIATE("new", 1),  // 0 = new 1                            (d t)
    3737
     38        // declare a parameter.  This is simply a def of a symbol.
     39        PARAM("param", 0),
    3840        // several flavors of test & branch are distinguished for pythonating purposes.
    3941        // test instructions use the "Instruction.operand[0]"  as the variable to test.
     
    98100                return this==AND || this==OR || this==XOR || this==NOT ||
    99101                           this==COPY || this==SEL || this==ANDNOT || this==SHIFT ||
    100                            this==SCAN || this==SHIFTSCAN || this==SPAN; // leave INSTANTIATE out for now.
     102                           this==SCAN || this==SHIFTSCAN || this==SPAN ||
     103                           this==PARAM; // leave INSTANTIATE out for now.
    101104        }
    102105        // for Jump types, the name in operand0 is the block to jump to.
     
    210213                case INSTANTIATE:
    211214                                           return "%1$s = new %2$s";
    212                
     215                case PARAM:        return "# param %1$s";
    213216                case TEST:     return "if %1$s %5$s 0: \t\t\t# goto %2$s; else: goto %3$s; join: goto %4$s";
    214217                case WHILE:    return "while %1$s %5$s 0: \t\t\t# do %2$s; done: goto %3$s";
     
    239242                case INSTANTIATE:
    240243                                           return "%1$s = %2$s()";
    241                
     244                case PARAM:        return "# param %1$s";
    242245                case TEST:     return "if %1$s %5$s 0: \t\t\t# goto %2$s; else: goto %3$s; join: goto %4$s";
    243246                case WHILE:    return "while %1$s %5$s 0: \t\t\t# do %2$s; done: goto %3$s";
  • proto/pebble/trunk/src/incode/global/CopyRemover.java

    r1306 r1307  
    88
    99import java.util.Set;
     10
     11import util.VariableNamer;
    1012
    1113public class CopyRemover {
     
    7173                }
    7274               
    73                 if(!copyLiveOut) {
    74                         if(bottomUse(copyIndex) < nextDef(defIndex)) {
    75                                 replaceUses(copyIndex, defSymbol);
    76                                 Instruction copyInstruction = block.instruction(copyIndex);
    77                                 copyInstruction.setOperation(Op.NOP);
    78                                 copyInstruction.markForDeletion();
    79                                
    80                                 defUse.recomputeUses(defIndex);
    81                                 return;
    82                         }
    83                 }
    84                 if(!defLiveOut) {
    85                         if(!defOrUseBetween(copySymbol, copyIndex, defIndex)) {
    86                                 replaceUses(defIndex, copySymbol);
    87 
    88                                 Instruction defInstruction = block.instruction(defIndex);
    89                                 defInstruction.setOperand(0, copySymbol);
    90                                
    91                                 Instruction copyInstruction = block.instruction(copyIndex);
    92                                 copyInstruction.setOperation(Op.NOP);
    93                                 copyInstruction.markForDeletion();
    94                                
    95                                 defUse.recomputeUses(defIndex);
    96                                 return;
    97                         }
    98                 }
     75                boolean canReplaceCopy = !copyLiveOut &&
     76                                (bottomUse(copyIndex) < nextDef(defIndex));
     77
     78                boolean canReplaceDef = !defLiveOut &&
     79                                !defOrUseBetween(copySymbol, copyIndex, defIndex) &&
     80                                block.instruction(defIndex).getOperation() != Op.PARAM;
     81               
     82                if(canReplaceDef && canReplaceCopy) {
     83                        if(VariableNamer.getInstance().betterSymbol(copySymbol, defSymbol)) {
     84                                replaceDefByCopy(defIndex, copyIndex);
     85                        }
     86                        else {
     87                                replaceCopyByDef(defIndex, copyIndex);
     88                        }
     89                }
     90                else if(canReplaceDef) {
     91                        replaceDefByCopy(defIndex, copyIndex);
     92                }
     93                else if(canReplaceCopy) {
     94                        replaceCopyByDef(defIndex, copyIndex);
     95                }
     96               
     97        }
     98
     99
     100
     101        private void replaceDefByCopy(int defIndex, int copyIndex) {
     102                String copySymbol = definedSymbol(copyIndex);
     103                replaceUses(defIndex, copySymbol);
     104
     105                Instruction defInstruction = block.instruction(defIndex);
     106                defInstruction.setOperand(0, copySymbol);
     107               
     108                Instruction copyInstruction = block.instruction(copyIndex);
     109                copyInstruction.setOperation(Op.NOP);
     110                copyInstruction.markForDeletion();
     111               
     112                defUse.recomputeUses(defIndex);
     113        }
     114
     115        private void replaceCopyByDef(int defIndex, int copyIndex) {
     116                String defSymbol = definedSymbol(defIndex);             
     117                replaceUses(copyIndex, defSymbol);
     118                Instruction copyInstruction = block.instruction(copyIndex);
     119                copyInstruction.setOperation(Op.NOP);
     120                copyInstruction.markForDeletion();
     121               
     122                defUse.recomputeUses(defIndex);
    99123        }
    100124        private boolean defOrUseBetween(String copySymbol, int copyIndex,
  • proto/pebble/trunk/src/main/Main.java

    r1306 r1307  
    77import incode.global.LivenessProperty;
    88import incode.global.MergeBlocks;
     9import incode.global.ReachingDefinitions;
    910import incode.localOptimization.ReuseAvailableExpressions;
    1011
     
    7071            // intermediate code generation
    7172            BasicBlock headBlock = ASTtoIncode.apply(tree);
     73            Fragment fragment = Fragment.make(headBlock);
     74           
     75            // dataflow semantic analysis
     76            ReachingDefinitions.apply(fragment);
    7277           
    7378            // optimization
    74             Fragment fragment = Fragment.make(headBlock);
    7579            MergeBlocks.apply(fragment);
    7680            ReuseAvailableExpressions.apply(headBlock);         // make this global.
  • proto/pebble/trunk/src/util/VariableNamer.java

    r1305 r1307  
    5959                knownItems = new HashMap<String, String>();
    6060        }
    61 
     61        public boolean betterSymbol(String symbol1, String symbol2) {
     62                if(symbol1.startsWith(temporaryVariablePrefix)) return false;
     63                if(symbol2.startsWith(temporaryVariablePrefix)) return true;
     64               
     65                if(symbol1.startsWith(charClassPrefix)) return false;
     66                if(symbol2.startsWith(charClassPrefix)) return true;
     67
     68                if(symbol1.startsWith(sequencePrefix)) return false;
     69                if(symbol2.startsWith(sequencePrefix)) return true;
     70               
     71                if(symbol1.startsWith("parseStatementPrefix")) return false;
     72                if(symbol2.startsWith("parseStatementPrefix"))  return true;
     73               
     74                if(symbol1.indexOf('.')!=-1)    return true;
     75                if(symbol2.indexOf('.')!=-1)    return false;
     76                return false;
     77        }
    6278
    6379        /**
Note: See TracChangeset for help on using the changeset viewer.