1 pnkfelix 1.1.2.1 // AppelRegAlloc.java, created Sun Apr 8 10:56:00 2001 by pnkfelix
2 cananian 1.1.2.2 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.Instr;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.Backend.Generic.Code;
7 pnkfelix 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
8 pnkfelix 1.1.2.1 import harpoon.IR.Properties.UseDefer;
9 pnkfelix 1.1.2.1 import harpoon.Analysis.BasicBlock;
10 pnkfelix 1.1.2.1 import harpoon.Analysis.ReachingDefs;
11 pnkfelix 1.1.2.1 import harpoon.Analysis.DataFlow.LiveTemps;
12 pnkfelix 1.1.2.1
13 pnkfelix 1.1.2.1 import harpoon.IR.Assem.Instr;
14 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
15 pnkfelix 1.1.2.1
16 pnkfelix 1.1.2.1 import harpoon.Util.Util;
17 pnkfelix 1.1.2.1
18 pnkfelix 1.1.2.1 import java.util.Iterator;
19 pnkfelix 1.1.2.1 import java.util.Set;
20 pnkfelix 1.1.2.1 import java.util.HashSet;
21 pnkfelix 1.1.2.1 import java.util.Collection;
22 pnkfelix 1.1.2.1 import java.util.List;
23 pnkfelix 1.1.2.1
24 pnkfelix 1.1.2.1 public class Check {
25 pnkfelix 1.1.2.1
26 pnkfelix 1.1.2.1 public static
27 pnkfelix 1.1.2.1 void liveSetsAreConsistent( Code code, BasicBlock.Factory bbf,
28 pnkfelix 1.1.2.1 CFGrapher cfger, UseDefer uder,
29 pnkfelix 1.1.2.1 LiveTemps liveTemps , Set initSet ) {
30 pnkfelix 1.1.2.1 for(Iterator bbs=bbf.blocksIterator(); bbs.hasNext();) {
31 pnkfelix 1.1.2.1 BasicBlock bb = (BasicBlock) bbs.next();
32 pnkfelix 1.1.2.1 List stms = bb.statements();
33 pnkfelix 1.1.2.1 Instr lastStm = (Instr) stms.get( stms.size() - 1 );
34 pnkfelix 1.1.2.1 Set liveAfter = liveTemps.getLiveAfter( lastStm );
35 pnkfelix 1.1.2.1 HashSet decreasingLiveAfter = new HashSet( liveAfter );
36 pnkfelix 1.1.2.1 decreasingLiveAfter.removeAll( initSet );
37 pnkfelix 1.1.2.1 Collection succs = (Collection) cfger.succElemC(lastStm);
38 cananian 1.5 for(Object succO : succs) {
39 cananian 1.5 Instr succ = (Instr) succO;
40 pnkfelix 1.1.2.1 HashSet liveBefore = new HashSet(liveTemps.getLiveBefore( succ ));
41 pnkfelix 1.1.2.1 decreasingLiveAfter.removeAll( liveBefore );
42 pnkfelix 1.1.2.1 liveBefore.removeAll( liveAfter );
43 pnkfelix 1.1.2.1 if( ! liveBefore.isEmpty() ){
44 pnkfelix 1.1.2.1 die( bbf, code,
45 pnkfelix 1.1.2.1 "liveIn(succ:"+succ+"):"+liveTemps.getLiveBefore( succ )+
46 pnkfelix 1.1.2.1 " not subset of liveOut(pred:"+lastStm+"):"+
47 pnkfelix 1.1.2.1 liveTemps.getLiveAfter( lastStm ));
48 pnkfelix 1.1.2.1 }
49 pnkfelix 1.1.2.1 }
50 pnkfelix 1.1.2.1
51 pnkfelix 1.1.2.1 if(! decreasingLiveAfter.isEmpty() ) {
52 pnkfelix 1.1.2.1
53 pnkfelix 1.1.2.1 System.out.println( "pred:"+lastStm );
54 pnkfelix 1.1.2.1 System.out.println( "succC(pred):"+cfger.succElemC( lastStm ));
55 pnkfelix 1.1.2.1 System.out.println( "liveOut(pred):"+liveTemps.getLiveAfter( lastStm ));
56 pnkfelix 1.1.2.1 System.out.println();
57 pnkfelix 1.1.2.1 die( bbf, code,
58 pnkfelix 1.1.2.1 "liveOut(pred:"+lastStm+
59 pnkfelix 1.1.2.1 ") not union of liveIn(succs); "+
60 pnkfelix 1.1.2.1 "missing:"+decreasingLiveAfter);
61 pnkfelix 1.1.2.1 }
62 pnkfelix 1.1.2.1 }
63 pnkfelix 1.1.2.1 }
64 pnkfelix 1.1.2.1
65 pnkfelix 1.1.2.1
66 pnkfelix 1.1.2.1 public static
67 pnkfelix 1.1.2.1 void allLiveVarsHaveDefs( Code code, BasicBlock.Factory bbf,
68 pnkfelix 1.1.2.1 CFGrapher cfger, UseDefer uder,
69 pnkfelix 1.1.2.1 ReachingDefs rdefs, LiveTemps liveTemps ) {
70 pnkfelix 1.1.2.1 for(Iterator bbs=bbf.blocksIterator(); bbs.hasNext();) {
71 pnkfelix 1.1.2.1 BasicBlock bb = (BasicBlock) bbs.next();
72 pnkfelix 1.1.2.1 List stms = bb.statements();
73 pnkfelix 1.1.2.1 Instr lastStm = (Instr) stms.get( stms.size() - 1 );
74 pnkfelix 1.1.2.1 Set s = liveTemps.getLiveAfter( lastStm );
75 pnkfelix 1.1.2.1
76 pnkfelix 1.1.2.1 Collection succs = (Collection) cfger.succElemC(lastStm);
77 pnkfelix 1.1.2.1
78 cananian 1.5 for(Object tO : s){
79 cananian 1.5 Temp t = (Temp) tO;
80 pnkfelix 1.1.2.1
81 pnkfelix 1.1.2.1 // N.B. reaching-defs( lastStm, t ) alone would *NOT*
82 pnkfelix 1.1.2.1 // be correct here, because we're getting the temps
83 pnkfelix 1.1.2.1 // that are live AFTER lastStm, which means we want
84 pnkfelix 1.1.2.1 // lastStm to be included as a possible reaching-def.
85 pnkfelix 1.1.2.1 // But we don't want to do reaching-defs on the
86 pnkfelix 1.1.2.1 // successors on their own, because we want to ensure
87 pnkfelix 1.1.2.1 // that this particular flow-of-control is handled.
88 pnkfelix 1.1.2.1
89 pnkfelix 1.1.2.1 if ( !uder.defC(lastStm).contains(t) &&
90 pnkfelix 1.1.2.1 rdefs.reachingDefs( lastStm, t ).isEmpty() ){
91 pnkfelix 1.1.2.1
92 pnkfelix 1.1.2.1 System.out.println( liveTemps.dumpElems() );
93 pnkfelix 1.1.2.1 System.out.println();
94 pnkfelix 1.1.2.1
95 pnkfelix 1.1.2.1 die( bbf, code,
96 pnkfelix 1.1.2.1 "Temp: "+t+" has no defs that reach ["+lastStm+
97 pnkfelix 1.1.2.1 "] though it is marked as live-after-there.");
98 pnkfelix 1.1.2.1 }
99 pnkfelix 1.1.2.1 }
100 pnkfelix 1.1.2.1 }
101 pnkfelix 1.1.2.1 }
102 pnkfelix 1.1.2.1
103 pnkfelix 1.1.2.1 private static
104 pnkfelix 1.1.2.1 void die( BasicBlock.Factory bbf, Code code , String message ) {
105 pnkfelix 1.1.2.1 bbf.dumpCFG();
106 pnkfelix 1.1.2.1 System.out.println();
107 pnkfelix 1.1.2.1 code.printPreallocatedCode();
108 cananian 1.3.2.1 assert false : message;
109 pnkfelix 1.1.2.1 }
110 cananian 1.2 }