Changeset 1308 for proto/pebble


Ignore:
Timestamp:
Aug 12, 2011, 2:56:41 AM (8 years ago)
Author:
shermer
Message:

Converted liveness analysis to new framework for dataflow.

Location:
proto/pebble/trunk/src
Files:
1 added
7 edited
1 moved

Legend:

Unmodified
Added
Removed
  • proto/pebble/trunk/src/incode/global/CopyRemover.java

    r1307 r1308  
    2525                LivenessProperty live = LivenessProperty.getFrom(head);
    2626                if(live == null) {
    27                         LivenessProperty.build(fragment);
     27                        Liveness.apply(fragment);
    2828                }
    2929        }
  • proto/pebble/trunk/src/incode/global/DeadCodeEliminator.java

    r1284 r1308  
    2222                LivenessProperty live = LivenessProperty.getFrom(head);
    2323                if(live == null) {
    24                         LivenessProperty.build(fragment);
     24                        Liveness.apply(fragment);
    2525                }
    2626        }
  • proto/pebble/trunk/src/incode/global/LivenessProperty.java

    r1284 r1308  
    11package incode.global;
    22
    3 import java.util.Deque;
     3import incode.BasicBlock;
     4import incode.Instruction;
     5
     6import java.io.PrintStream;
    47import java.util.HashSet;
    5 import java.util.LinkedList;
    68import java.util.List;
    79import java.util.Set;
    810
    9 import incode.BasicBlock;
    10 import incode.Fragment;
    11 import incode.Instruction;
    12 import util.property.Property;
    13 
    14 public class LivenessProperty implements Property {
     11public class LivenessProperty  extends BasicBlockProperty  {
    1512        public static final String PROPERTY_NAME = "Liveness";
     13        @Override
     14        public String getName() {
     15                return PROPERTY_NAME;
     16        }
    1617        private BasicBlock block;
    1718        // this is a backwards flow analysis, so "kills" is the
     
    3536        // Constructor and attachment
    3637        //////////////////////////////////////////////////////
    37         public LivenessProperty(BasicBlock b) {
    38                 block = b;
     38        public LivenessProperty(BasicBlock block, DataflowWorkQueue work) {
     39                super(block, work);
    3940                kills = new HashSet<String>();
    4041                gens = new HashSet<String>();
    4142                makeKillsAndGens();
    42         }
    43         public LivenessProperty attach() {
    44                 block.addProperty(this);
    45                 return this;
    4643        }
    4744       
     
    6360                }
    6461        }
    65         @SuppressWarnings("unused")
    66         private void killGenDiagnostic() {
    67                 System.err.println("");
    68                 System.err.println("block: " + block);
    69                 System.err.println("kills: " + kills);
    70                 System.err.println("gens:  " + gens);
    71                 System.err.println("");
    72         }
    73         private void initializeLiveInAndOut() {
     62
     63        public void initialize() {
    7464                liveIn    = new HashSet<String>(gens);
    7565                newLiveIn = new HashSet<String>(gens);
     
    7767                liveOut = new HashSet<String>();
    7868                newLiveOut = new HashSet<String>();
     69        }
     70        @Override
     71        public void finalize() {
    7972        }
    8073       
     
    8578        //              the live-in variables.
    8679        //////////////////////////////////////////////////////
    87         private void applyTransferFunction() {
     80        void applyTransferFunction() {
    8881                if(newLiveOut.isEmpty())                                // shouldn't happen, but let's be certain.
    8982                        return;
     
    10295        }
    10396       
     97       
    10498        //////////////////////////////////////////////////////
    10599        // pushLiveInToPredecessors:
     
    107101        //              are added to the live-out sets of all predecessors.
    108102        //////////////////////////////////////////////////////
    109         private void pushLiveInToPredecessors() {
     103        void pushLiveInToPredecessors() {
    110104                if(newLiveIn.isEmpty())                                 // shouldn't happen, but let's be certain.
    111105                        return;
     
    117111                newLiveIn.clear();
    118112        }
    119        
    120        
    121113        private List<BasicBlock> getPredecessors() {
    122                 PredecessorProperty predProperty = PredecessorProperty.getFrom(block);
     114                PredecessorsProperty predProperty = PredecessorsProperty.getFrom(block);
    123115                return predProperty.predecessors();
    124116        }
    125         private void addVariablesToLiveOut(Set<String> variables) {
     117        void addVariablesToLiveOut(Set<String> variables) {
    126118                for(String var: variables) {
    127119                        if(!liveOut.contains(var)) {
    128120                                liveOut.add(var);
    129121                                newLiveOut.add(var);
    130                                 addToWork(block);
     122                                work.add(block);
    131123                        }
    132124                }
    133125        }
    134126
    135         private void LiveInOutDiagnostic() {
     127        public void diagnosticPrint(PrintStream stream) {
    136128                System.err.println("");
    137129                System.err.println("block:" + block.getName());
     
    143135                System.err.println("");
    144136        }
     137        @SuppressWarnings("unused")
     138        private void killGenDiagnostic() {
     139                System.err.println("");
     140                System.err.println("block: " + block);
     141                System.err.println("kills: " + kills);
     142                System.err.println("gens:  " + gens);
     143                System.err.println("");
     144        }
    145145       
    146146       
    147147
    148148        //////////////////////////////////////////////////////
    149         // Property features
     149        // access to data
    150150        //////////////////////////////////////////////////////
    151         @Override
    152         public String getName() {
    153                 return PROPERTY_NAME;
     151        public Set<String> getLiveOut() {
     152                return liveOut;
    154153        }
    155        
     154        public Set<String> getLiveIn() {
     155                return liveIn;
     156        }
    156157       
    157158        //////////////////////////////////////////////////////
     
    164165        }
    165166
    166         //////////////////////////////////////////////////////
    167         // static global creation:
    168         // build(Fragment)
    169         //////////////////////////////////////////////////////
    170         private static Deque<BasicBlock> workQueue = new LinkedList<BasicBlock>();
    171        
    172         public static void build(Fragment fragment) {
    173                 ensurePredecessorsAvailable(fragment);
    174                 initializeAllBlockProperties(fragment);
    175                 addAllBlocksToWorkQueue(fragment);
    176                 processWorkQueueUntilEmpty();
    177 //              printAllBlocks(fragment);
    178         }
    179        
    180         @SuppressWarnings("unused")
    181         private static void printAllBlocks(Fragment fragment) {
    182                 for(BasicBlock block: fragment) {
    183                         LivenessProperty live = getFrom(block);
    184                         live.LiveInOutDiagnostic();
    185                 }
    186         }
    187         private static void ensurePredecessorsAvailable(Fragment fragment) {
    188                 Predecessors.make(fragment);    // it's a quick operation, so just repeat.
    189         }
    190         private static void addAllBlocksToWorkQueue(Fragment fragment) {
    191                 for(BasicBlock b: fragment.blocksInReverse()) {
    192                         addToWork(b);
    193                 }
    194         }
    195         private static void initializeAllBlockProperties(Fragment fragment) {
    196                 for(BasicBlock b: fragment) {
    197                         LivenessProperty live = new LivenessProperty(b).attach();
    198                         live.initializeLiveInAndOut();
    199                 }
    200                
    201                 BasicBlock tail = fragment.getTail();
    202                 LivenessProperty tailLive = getFrom(tail);
    203                 tailLive.addVariablesToLiveOut(AllVariables.allFieldVariables(fragment));
    204         }
    205         private static void processWorkQueueUntilEmpty() {
    206                 while(!workQueue.isEmpty()) {
    207                         processOneBlock(workQueue.removeLast());
    208                 }
    209         }
    210         private static void processOneBlock(BasicBlock block) {
    211                 LivenessProperty live = getFrom(block);
    212                 live.applyTransferFunction();
    213                 live.pushLiveInToPredecessors();
    214         }
    215         private static void addToWork(BasicBlock block) {
    216                 if(!workQueue.contains(block))
    217                         workQueue.add(block);
    218         }
    219         public Set<String> getLiveOut() {
    220                 return liveOut;
    221         }
    222         public Set<String> getLiveIn() {
    223                 return liveIn;
    224         }
    225        
    226 
    227167}
  • proto/pebble/trunk/src/incode/global/MergeBlocks.java

    r1284 r1308  
    3636
    3737        private static void clearPredecessors(BasicBlock block) {
    38                 PredecessorProperty property = PredecessorProperty.getFrom(block);
     38                PredecessorsProperty property = PredecessorsProperty.getFrom(block);
    3939                List<BasicBlock> predecessors = property.predecessors();
    4040                predecessors.clear();
     
    114114                if(block==null)
    115115                        return false;
    116                 PredecessorProperty property = PredecessorProperty.getFrom(block);
     116                PredecessorsProperty property = PredecessorsProperty.getFrom(block);
    117117                List<BasicBlock> predecessors = property.predecessors();
    118118                return predecessors.size() == 1;
  • proto/pebble/trunk/src/incode/global/Predecessors.java

    r1253 r1308  
    33import incode.BasicBlock;
    44import incode.Fragment;
    5 import static incode.global.PredecessorProperty.PROPERTY_NAME;
     5import static incode.global.PredecessorsProperty.PROPERTY_NAME;
    66
    77public class Predecessors {
     
    2121        private static void giveEveryBlockAPredecessorProperty(Fragment fragment) {
    2222                for(BasicBlock block: fragment) {
    23                         block.addProperty(new PredecessorProperty());
     23                        block.addProperty(new PredecessorsProperty());
    2424                }
    2525        }
     
    3131        private static void giveSuccessorsAPredecessor(BasicBlock block) {
    3232                for(BasicBlock successor: block.successors()) {
    33                         PredecessorProperty predecessors =
    34                                 (PredecessorProperty) successor.getProperty(PROPERTY_NAME);
     33                        PredecessorsProperty predecessors =
     34                                (PredecessorsProperty) successor.getProperty(PROPERTY_NAME);
    3535                        predecessors.add(block);
    3636                }
  • proto/pebble/trunk/src/incode/global/PredecessorsProperty.java

    r1253 r1308  
    88import util.property.Property;
    99
    10 public class PredecessorProperty implements Property {
     10public class PredecessorsProperty implements Property {
    1111        public static final String PROPERTY_NAME = "predecessors";
    1212        public List<BasicBlock> predecessors = new ArrayList<BasicBlock>();
     
    2424        }
    2525       
    26         public static PredecessorProperty getFrom(BasicBlock block) {
     26        public static PredecessorsProperty getFrom(BasicBlock block) {
    2727                if(block==null)
    2828                        return null;
    29                 return (PredecessorProperty)block.getProperty(PROPERTY_NAME);
     29                return (PredecessorsProperty)block.getProperty(PROPERTY_NAME);
    3030        }
    3131}
  • proto/pebble/trunk/src/incode/global/ReachingProperty.java

    r1307 r1308  
    8282        }
    8383
     84       
     85       
    8486        public void initialize() {
    8587                reachingIn    = new HashSet<SymbolAndLocation>();
     
    127129        public void checkForPossibleUseBeforeDef(int instructionIndex, int oprIndex) {
    128130                Set<SymbolAndLocation> reachingDefns = getReachingDefinitions(instructionIndex, oprIndex);
    129                
    130 //              if(allHaveNullBlock(reachingDefns)) {
    131 //                      Instruction instr = block.instruction(instructionIndex);
    132 //                      String symbol = instr.operand(oprIndex);
    133 //                      ErrLog.reportError("variable " + symbol + "is used before being defined.");
    134 //              }
    135 //              else
     131
    136132                if(oneHasNullBlock(reachingDefns)) {
    137133                        Instruction instr = block.instruction(instructionIndex);
     
    148144                return false;
    149145        }
    150         @SuppressWarnings("unused")
    151         private boolean allHaveNullBlock(Set<SymbolAndLocation> reachingDefns) {
    152                 for(SymbolAndLocation defn: reachingDefns) {
    153                         if(defn.block != null)
    154                                 return false;
    155                 }       
    156                 return true;
    157         }
     146
    158147        private Set<SymbolAndLocation> getDefinitionSet(String operand, Set<SymbolAndLocation> reachingThrough) {
    159148                Set<SymbolAndLocation> result = new HashSet<SymbolAndLocation>(4);
     
    232221                stream.println("");
    233222        }
     223
     224        //////////////////////////////////////////////////////
     225        // access to data
     226        //////////////////////////////////////////////////////
    234227       
    235228        //////////////////////////////////////////////////////
  • proto/pebble/trunk/src/main/Main.java

    r1307 r1308  
    55import incode.global.CopyRemover;
    66import incode.global.DeadCodeEliminator;
    7 import incode.global.LivenessProperty;
     7import incode.global.Liveness;
    88import incode.global.MergeBlocks;
    99import incode.global.ReachingDefinitions;
     
    1414import lexicalStream.LexicalCollector;
    1515import lexicalStream.MoveLexdefsToBranchStarts;
     16
     17import org.antlr.runtime.ANTLRFileStream;
     18import org.antlr.runtime.CommonTokenStream;
     19import org.antlr.runtime.RecognitionException;
     20
    1621import parseStatement.ParseStatementExpander;
    1722import parser.PebbleLexer;
     
    1924import semantic.MiscellaneousSemanticChecks;
    2025import semantic.StructAnalyzer;
    21 
    22 import org.antlr.runtime.ANTLRFileStream;
    23 import org.antlr.runtime.CommonTokenStream;
    24 import org.antlr.runtime.RecognitionException;
    25 
     26import util.error.ErrLog;
    2627import ast.AST;
    2728import ast.nodes.ProgramBlockASTN;
     
    2930import ast.transforms.AssumptionIncorporator;
    3031import ast.transforms.MacroExpander;
    31 
    32 import util.error.ErrLog;
    3332
    3433public class Main {
     
    7978            MergeBlocks.apply(fragment);
    8079            ReuseAvailableExpressions.apply(headBlock);         // make this global.
    81             LivenessProperty.build(fragment);
     80            Liveness.apply(fragment);
    8281            DeadCodeEliminator.apply(fragment);
    8382            CopyRemover.apply(fragment);
Note: See TracChangeset for help on using the changeset viewer.