1 cananian 1.1.2.11 // Verify.java, created Wed Jun 21 3:22:28 2000 by pnkfelix
2 cananian 1.1.2.11 // Copyright (C) 2001 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.2.11 // 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.Analysis.BasicBlock;
7 cananian 1.1.2.4 import harpoon.IR.Assem.Instr;
8 cananian 1.1.2.4 import harpoon.IR.Assem.InstrMEM;
9 cananian 1.1.2.4 import harpoon.IR.Assem.InstrVisitor;
10 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
11 pnkfelix 1.1.2.1 import harpoon.Util.Util;
12 cananian 1.5 import net.cscott.jutil.ListFactory;
13 pnkfelix 1.1.2.1
14 cananian 1.1.2.4 import java.util.ArrayList;
15 cananian 1.1.2.4 import java.util.Collection;
16 cananian 1.1.2.4 import java.util.Iterator;
17 cananian 1.1.2.4 import java.util.List;
18 cananian 1.1.2.4 import java.util.Set;
19 pnkfelix 1.1.2.1
20 pnkfelix 1.1.2.1
21 pnkfelix 1.1.2.1 /** Verify uses the inherent definitions of the instruction
22 pnkfelix 1.1.2.1 stream to check that the register uses of the allocated
23 pnkfelix 1.1.2.1 instructions are coherent.
24 cananian 1.1.2.11
25 cananian 1.1.2.11 @author Felix S. Klock II <pnkfelix@mit.edu>
26 cananian 1.6 @version $Id: Verify.java,v 1.6 2004/02/08 03:19:37 cananian Exp $
27 pnkfelix 1.1.2.1 */
28 pnkfelix 1.1.2.1 class Verify extends harpoon.IR.Assem.InstrVisitor {
29 pnkfelix 1.1.2.1 LocalCffRegAlloc lra;
30 pnkfelix 1.1.2.1 Set spillUsesV, spillDefsV;
31 pnkfelix 1.1.2.5 RegFile regfile;
32 pnkfelix 1.1.2.1 final BasicBlock block;
33 pnkfelix 1.1.2.1 private Instr curr;
34 pnkfelix 1.1.2.1
35 pnkfelix 1.1.2.1 Verify(LocalCffRegAlloc lra, BasicBlock b,
36 pnkfelix 1.1.2.1 Set spillUses, Set spillDefs) {
37 pnkfelix 1.1.2.1 this.lra = lra;
38 pnkfelix 1.1.2.1 this.block = b;
39 pnkfelix 1.1.2.5 regfile = new RegFile(lra.allRegisters);
40 pnkfelix 1.1.2.1 this.spillUsesV = spillUses;
41 pnkfelix 1.1.2.1 this.spillDefsV = spillDefs;
42 pnkfelix 1.1.2.1 }
43 pnkfelix 1.1.2.1
44 pnkfelix 1.1.2.1 /** Gets the assignment for `use' out of `regfile'. Note that
45 pnkfelix 1.1.2.1 in some cases, `use' is not directly mapped in the
46 pnkfelix 1.1.2.1 `regfile', but rather another temp that is in the same
47 pnkfelix 1.1.2.1 EqTempSet as `use' is mapped in the `regfile'.
48 pnkfelix 1.1.2.1 */
49 pnkfelix 1.1.2.1 List getAssignment(Temp use) {
50 pnkfelix 1.1.2.1 if (lra.isRegister(use))
51 pnkfelix 1.1.2.1 return ListFactory.singleton(use);
52 pnkfelix 1.1.2.1
53 pnkfelix 1.1.2.10 if (!regfile.hasAssignment(use)) {
54 pnkfelix 1.1.2.10 System.out.println(curr+" use:"+use+" has no assignment in "+regfile);
55 pnkfelix 1.1.2.10 System.out.println("BasicBlock");
56 pnkfelix 1.1.2.10 System.out.println(block.statements());
57 pnkfelix 1.1.2.10 System.out.println();
58 pnkfelix 1.1.2.10 }
59 pnkfelix 1.1.2.1 List regs = regfile.getAssignment(use);
60 pnkfelix 1.1.2.1 /*
61 pnkfelix 1.1.2.1 if (regs == null) { // search for alternate
62 cananian 1.6 for (Object tO : regfile.tempSet()) {
63 cananian 1.6 Temp t = (Temp) tO;
64 pnkfelix 1.1.2.1 if (lra.tempSets.getRep(t) == lra.tempSets.getRep(use)) {
65 pnkfelix 1.1.2.1 regs = regfile.getAssignment(t);
66 pnkfelix 1.1.2.1 break;
67 pnkfelix 1.1.2.1 }
68 pnkfelix 1.1.2.1 }
69 pnkfelix 1.1.2.1 }
70 pnkfelix 1.1.2.1 */
71 cananian 1.3.2.1 assert regs != null : lra.lazyInfo("no reg assignment"+regfile,block,curr,use,false);
72 pnkfelix 1.1.2.1 return regs;
73 pnkfelix 1.1.2.1 }
74 pnkfelix 1.1.2.1
75 pnkfelix 1.1.2.1 public void visit(final Instr i) {
76 pnkfelix 1.1.2.1 curr = i;
77 pnkfelix 1.1.2.1 visit(i, false);
78 pnkfelix 1.1.2.1 }
79 pnkfelix 1.1.2.3 /*
80 pnkfelix 1.1.2.1 public void visit(final InstrMOVE i) {
81 pnkfelix 1.1.2.1 curr = i;
82 pnkfelix 1.1.2.1 if (lra.instrsToRemove.contains(i) &&
83 pnkfelix 1.1.2.1 !lra.isRegister(i.use()[0]) &&
84 pnkfelix 1.1.2.1 !lra.isRegister(i.def()[0])) {
85 pnkfelix 1.1.2.1
86 pnkfelix 1.1.2.1 // System.out.println("shouldn't be here on "+i);
87 pnkfelix 1.1.2.1 if (true) return;
88 pnkfelix 1.1.2.1
89 pnkfelix 1.1.2.1 } else {
90 pnkfelix 1.1.2.1 visit((Instr)i);
91 pnkfelix 1.1.2.1 }
92 pnkfelix 1.1.2.1 }
93 pnkfelix 1.1.2.3 */
94 pnkfelix 1.1.2.1 public void visit(final Instr i, boolean multAssignAllowed) {
95 pnkfelix 1.1.2.6 // if (i.toString().equals("")) return;
96 pnkfelix 1.1.2.6
97 cananian 1.6 for (Object useO : i.useC()) {
98 cananian 1.6 Temp use = (Temp) useO;
99 pnkfelix 1.1.2.1 if (lra.isRegister(use)) continue;
100 pnkfelix 1.1.2.1
101 pnkfelix 1.1.2.1 Collection codeRegs = lra.getRegs(i, use);
102 pnkfelix 1.1.2.1
103 pnkfelix 1.1.2.1 List fileRegs = getAssignment(use);
104 pnkfelix 1.1.2.1
105 pnkfelix 1.1.2.1 { // ASSERTION CODE
106 cananian 1.3.2.1 assert codeRegs != null : ("codeRegs!=null {"+i.toString()+"} use:"+use);
107 cananian 1.3.2.1 assert !fileRegs.contains(null) : "no null allowed in fileRegs";
108 cananian 1.3.2.1 assert !codeRegs.contains(null) : "no null allowed in codeRegs";
109 cananian 1.3.2.1 assert codeRegs.containsAll(fileRegs) : lra.lazyInfo("codeRegs incorrect; "+
110 pnkfelix 1.1.2.1 "c:"+codeRegs+" f:"+fileRegs+" regfile:"+regfile,
111 cananian 1.3.2.1 block,i,use,false);
112 cananian 1.3.2.1 assert fileRegs.containsAll(codeRegs) : ("fileRegs incomplete: "+"c: "+codeRegs+" f: "+fileRegs);
113 pnkfelix 1.1.2.1 } // END ASSERTION CODE
114 pnkfelix 1.1.2.1 }
115 pnkfelix 1.1.2.1
116 pnkfelix 1.1.2.1 Iterator defs = i.defC().iterator();
117 pnkfelix 1.1.2.1 while(defs.hasNext()) {
118 pnkfelix 1.1.2.1 final Temp def = (Temp) defs.next();
119 pnkfelix 1.1.2.1 // def = tempSets.getRep(def);
120 pnkfelix 1.1.2.1 Collection codeRegs = lra.getRegs(i, def);
121 cananian 1.3.2.1 assert codeRegs != null : "getRegs null for "+def+" in "+i;
122 pnkfelix 1.1.2.1
123 pnkfelix 1.1.2.1
124 pnkfelix 1.1.2.1 if (false) {
125 pnkfelix 1.1.2.1 // check (though really just debugging my thought process...)
126 pnkfelix 1.1.2.1 Iterator redefs = codeRegs.iterator();
127 pnkfelix 1.1.2.1 while(redefs.hasNext()) {
128 pnkfelix 1.1.2.1 final Temp r = (Temp) redefs.next();
129 cananian 1.3.2.1 assert regfile.isEmpty(r) : lra.lazyInfo("reg:"+r+" is not empty prior"+
130 cananian 1.3.2.1 " to assignment",block,i,def);
131 pnkfelix 1.1.2.1 }
132 pnkfelix 1.1.2.1 }
133 pnkfelix 1.1.2.1
134 pnkfelix 1.1.2.1
135 pnkfelix 1.1.2.1 assign(def, codeRegs); // , multAssignAllowed);
136 pnkfelix 1.1.2.1 }
137 pnkfelix 1.1.2.1
138 pnkfelix 1.1.2.1 }
139 pnkfelix 1.1.2.1
140 pnkfelix 1.1.2.1 public void visit(final InstrMEM i) {
141 pnkfelix 1.1.2.1 curr = i;
142 pnkfelix 1.1.2.1 if (i instanceof RegAlloc.SpillLoad) {
143 pnkfelix 1.1.2.1 // regs <- temp
144 pnkfelix 1.1.2.1 spillUsesV.add(i.use()[0]);
145 pnkfelix 1.1.2.1
146 cananian 1.3.2.1 assert !regfile.hasAssignment(i.use()[0]) : lra.lazyInfo("if we're loading, why in regfile?",
147 cananian 1.3.2.1 block, i,i.use()[0],regfile,false);
148 pnkfelix 1.1.2.7 assign(i.use()[0], ((RegAlloc.SpillLoad)i).defC());
149 pnkfelix 1.1.2.1 } else if (i instanceof RegAlloc.SpillStore) {
150 pnkfelix 1.1.2.1 // temp <- regs
151 pnkfelix 1.1.2.1 spillDefsV.add(i.def()[0]);
152 pnkfelix 1.1.2.1
153 pnkfelix 1.1.2.1 // this code is failing for an unknown reason; i
154 pnkfelix 1.1.2.1 // would think that the mapping should still be
155 pnkfelix 1.1.2.1 // present in the regfile. taking it out for
156 pnkfelix 1.1.2.1 // now...
157 pnkfelix 1.1.2.1 if (false) {
158 pnkfelix 1.1.2.1 final Temp def = i.def()[0];
159 pnkfelix 1.1.2.1 List fileRegs = regfile.getAssignment(def);
160 pnkfelix 1.1.2.1 Collection storeRegs = i.useC();
161 cananian 1.3.2.1 assert fileRegs != null : lra.lazyInfo("fileRegs!=null",block,i,def);
162 cananian 1.3.2.1 assert !fileRegs.contains(null) : "no null allowed in fileRegs";
163 cananian 1.3.2.1 assert storeRegs.containsAll(fileRegs) : "storeRegs incomplete";
164 cananian 1.3.2.1 assert fileRegs.containsAll(storeRegs) : "fileRegs incomplete";
165 pnkfelix 1.1.2.1 }
166 pnkfelix 1.1.2.1 } else {
167 pnkfelix 1.1.2.1 visit((Instr)i);
168 pnkfelix 1.1.2.1 }
169 pnkfelix 1.1.2.1 }
170 pnkfelix 1.1.2.1
171 pnkfelix 1.1.2.1 // default assign procedure (multiple assignments not allowed)
172 pnkfelix 1.1.2.1 private void assign(Temp def, Collection c) {
173 pnkfelix 1.1.2.1 assignP(def, c, false);
174 pnkfelix 1.1.2.1 }
175 pnkfelix 1.1.2.1
176 pnkfelix 1.1.2.1 /** assigns `def' to `c'.
177 pnkfelix 1.1.2.1 requires: `c' is a collection of register Temps
178 pnkfelix 1.1.2.1 modifies: `regfile'
179 pnkfelix 1.1.2.1 effects:
180 pnkfelix 1.1.2.1 1. (not `multAssignAllowed') => remove all temps held
181 pnkfelix 1.1.2.1 by registers in `c' from `regfile'.
182 pnkfelix 1.1.2.1 2. assigns `def' to the collection of registers `c' in `regfile'
183 pnkfelix 1.1.2.1 */
184 pnkfelix 1.1.2.1 private void assignP(final Temp def, Collection c, boolean multAssignAllowed) {
185 pnkfelix 1.1.2.1 if (!multAssignAllowed) {
186 pnkfelix 1.1.2.1 // getting around multiple-assignment checker...
187 cananian 1.6 for (Object rO : c) {
188 cananian 1.6 Temp r = (Temp) rO;
189 pnkfelix 1.1.2.1 Temp t = regfile.getTemp(r);
190 pnkfelix 1.1.2.1 if (regfile.hasAssignment(t)) regfile.remove(t);
191 pnkfelix 1.1.2.1
192 pnkfelix 1.1.2.1 }
193 pnkfelix 1.1.2.1 }
194 pnkfelix 1.1.2.1
195 pnkfelix 1.1.2.8 // don't need Instr source info here, so can use null
196 pnkfelix 1.1.2.8 regfile.assign(def, new ArrayList(c), null);
197 pnkfelix 1.1.2.1 }
198 pnkfelix 1.1.2.1
199 cananian 1.2 }