1 cananian 1.1.2.1 // ArrayUnroller.java, created Thu Jun 14 22:36:15 2001 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.Loops.LoopFinder;
7 cananian 1.1.2.1 import harpoon.Analysis.Loops.Loops;
8 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
10 cananian 1.1.2.1 import harpoon.ClassFile.HCodeAndMaps;
11 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
12 cananian 1.1.2.1 import harpoon.IR.Quads.AGET;
13 cananian 1.1.2.1 import harpoon.IR.Quads.ASET;
14 cananian 1.1.2.1 import harpoon.IR.Quads.Edge;
15 cananian 1.1.2.1 import harpoon.IR.Quads.PHI;
16 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
17 cananian 1.1.2.1 import harpoon.IR.Quads.QuadFactory;
18 cananian 1.1.2.1 import harpoon.IR.Quads.QuadNoSSA;
19 cananian 1.1.2.1 import harpoon.Temp.Temp;
20 cananian 1.7 import net.cscott.jutil.UnmodifiableIterator;
21 cananian 1.1.2.1 import harpoon.Util.Util;
22 cananian 1.1.2.1
23 cananian 1.7 import java.util.ArrayList;
24 cananian 1.1.2.1 import java.util.HashMap;
25 cananian 1.1.2.1 import java.util.Iterator;
26 cananian 1.7 import java.util.List;
27 cananian 1.1.2.1 import java.util.Map;
28 cananian 1.1.2.1 import java.util.NoSuchElementException;
29 cananian 1.1.2.1 import java.util.Set;
30 cananian 1.1.2.1 import java.util.Stack;
31 cananian 1.1.2.1 /**
32 cananian 1.1.2.1 * <code>ArrayUnroller</code> unrolls loops containing arrays so that
33 cananian 1.1.2.1 * <code>CacheEquivalence</code> can make larger equivalence sets.
34 cananian 1.1.2.1 *
35 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
36 cananian 1.8 * @version $Id: ArrayUnroller.java,v 1.8 2004/02/08 03:20:09 cananian Exp $
37 cananian 1.1.2.1 */
38 cananian 1.1.2.1 public final class ArrayUnroller
39 cananian 1.6 extends harpoon.Analysis.Transformation.MethodMutator<Quad> {
40 cananian 1.1.2.1 private static final int CACHE_LINE_SIZE = 32; /* bytes */
41 cananian 1.1.2.1
42 cananian 1.1.2.1 /** Creates a <code>ArrayUnroller</code>. */
43 cananian 1.1.2.1 public ArrayUnroller(HCodeFactory parent) {
44 cananian 1.1.2.1 // we take in NoSSx, and output NoSSx.
45 cananian 1.1.2.1 super(harpoon.IR.Quads.QuadNoSSA.codeFactory(parent));
46 cananian 1.1.2.1 }
47 cananian 1.6 protected HCode<Quad> mutateHCode(HCodeAndMaps<Quad> input) {
48 cananian 1.6 HCode<Quad> ahc = input.ancestorHCode();
49 cananian 1.6 HCode<Quad> hc = input.hcode();
50 cananian 1.1.2.1 // find loops;
51 cananian 1.1.2.1 // only interested in leaf loops (with no nested loops)
52 cananian 1.6 for (Iterator<Loops> it=loopIterator(new LoopFinder(ahc));
53 cananian 1.6 it.hasNext(); ) {
54 cananian 1.6 Loops loop = it.next();
55 cananian 1.1.2.3 if (loop.parentLoop()==null) continue; // skip top-level pseudoloop
56 cananian 1.1.2.1 if (loop.nestedLoops().size()>0) continue; // skip
57 cananian 1.1.2.1 // this is a leaf loop. look for array refs.
58 cananian 1.1.2.1 boolean seen=false; int width=0;
59 cananian 1.8 for (Object qO : loop.loopIncElements()) {
60 cananian 1.8 Quad q = (Quad) qO;
61 cananian 1.1.2.1 if (q instanceof AGET) {
62 cananian 1.1.2.1 seen=true; width=updateWidth(width,((AGET)q).type());
63 cananian 1.1.2.1 } else if (q instanceof ASET) {
64 cananian 1.1.2.1 seen=true; width=updateWidth(width,((ASET)q).type());
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 }
67 cananian 1.1.2.1 if (!seen) continue; // no array references in this loop.
68 cananian 1.1.2.3 unrollOne(input, loop, CACHE_LINE_SIZE/width);
69 cananian 1.1.2.1 }
70 cananian 1.6 harpoon.Analysis.Quads.Unreachable.prune((harpoon.IR.Quads.Code)hc);
71 cananian 1.1.2.1 return hc;
72 cananian 1.1.2.1 }
73 cananian 1.1.2.1 /** find the minimum array component width */
74 cananian 1.1.2.1 private static int updateWidth(int width, HClass type) {
75 cananian 1.1.2.1 int nwidth=0;
76 cananian 1.1.2.1 if (type==HClass.Boolean || type==HClass.Byte) nwidth=1;
77 cananian 1.1.2.1 else if (type==HClass.Char || type==HClass.Short) nwidth=2;
78 cananian 1.1.2.1 else if (type==HClass.Int || type==HClass.Float) nwidth=4;
79 cananian 1.1.2.1 else if (type==HClass.Long || type==HClass.Double) nwidth=8;
80 cananian 1.1.2.1 else if (!type.isPrimitive()) nwidth=4;
81 cananian 1.3.2.1 else assert false;
82 cananian 1.1.2.1 return (width==0) ? nwidth : Math.min(width, nwidth);
83 cananian 1.1.2.1 }
84 cananian 1.1.2.1 /** iterate over loop and all children of loop recursively. */
85 cananian 1.6 static Iterator<Loops> loopIterator(Loops root) {
86 cananian 1.6 final Stack<Loops> s = new Stack<Loops>(); s.push(root);
87 cananian 1.6 return new UnmodifiableIterator<Loops>() {
88 cananian 1.1.2.1 public boolean hasNext() { return !s.isEmpty(); }
89 cananian 1.6 public Loops next() {
90 cananian 1.1.2.1 if (s.empty()) throw new NoSuchElementException();
91 cananian 1.6 Loops loop = s.pop();
92 cananian 1.1.2.1 // push children on stack before returning.
93 cananian 1.1.2.1 s.addAll(loop.nestedLoops());
94 cananian 1.1.2.1 return loop;
95 cananian 1.1.2.1 }
96 cananian 1.1.2.1 };
97 cananian 1.1.2.1 }
98 cananian 1.1.2.1 // the real mccoy:
99 cananian 1.6 private void unrollOne(HCodeAndMaps<Quad> input, Loops loop, int ntimes) {
100 cananian 1.1.2.1 // step 1: copy the nodes to make a loop L' with header h'
101 cananian 1.1.2.1 // and back edges si'->h'
102 cananian 1.7 List<Map<Quad,Quad>> copies = new ArrayList<Map<Quad,Quad>>(ntimes);
103 cananian 1.7 copies.add(input.elementMap());
104 cananian 1.1.2.1 for (int i=1; i<ntimes; i++)
105 cananian 1.7 copies.add(copy(input, loop));
106 cananian 1.1.2.1 // step 2: change all the back edges in L from si->h to si->h'
107 cananian 1.1.2.1 // step 3: change all the back edges in L' from si'->h' to si'->h
108 cananian 1.1.2.1 for (int i=0; i<ntimes; i++) {
109 cananian 1.8 for (Object eO : loop.loopBackEdges()) {
110 cananian 1.8 Edge e = (Edge) eO;
111 cananian 1.7 Quad.addEdge(copies.get(i).get(e.from()),
112 cananian 1.1.2.1 e.which_succ(),
113 cananian 1.7 copies.get((i+1)%ntimes).get(e.to()),
114 cananian 1.1.2.1 e.which_pred());
115 cananian 1.1.2.1 }
116 cananian 1.1.2.1 }
117 cananian 1.1.2.1 // make PHIs for the exit edges.
118 cananian 1.8 for (Object eO : loop.loopExitEdges()) {
119 cananian 1.8 Edge e = (Edge) eO;
120 cananian 1.7 QuadFactory qf = copies.get(0).get(e.from()).getFactory();
121 cananian 1.1.2.1 PHI phi = new PHI(qf, e.from(), new Temp[0], ntimes);
122 cananian 1.7 Quad.addEdge(phi, 0, copies.get(0).get(e.to()), e.which_pred());
123 cananian 1.1.2.1 for (int i=0; i<ntimes; i++)
124 cananian 1.7 Quad.addEdge(copies.get(i).get(e.from()), e.which_succ(),
125 cananian 1.1.2.1 phi, i);
126 cananian 1.1.2.1 }
127 cananian 1.1.2.2 // make stub PHIs for unused entrance edges
128 cananian 1.8 for (Object eO : loop.loopEntranceEdges()) {
129 cananian 1.8 Edge e = (Edge) eO;
130 cananian 1.7 QuadFactory qf = copies.get(0).get(e.to()).getFactory();
131 cananian 1.1.2.2 for (int i=1; i<ntimes; i++) {
132 cananian 1.1.2.2 PHI phi = new PHI(qf, e.to(), new Temp[0], 0);
133 cananian 1.1.2.2 Quad.addEdge(phi, 0,
134 cananian 1.7 copies.get(i).get(e.to()),
135 cananian 1.1.2.2 e.which_pred());
136 cananian 1.1.2.2 }
137 cananian 1.1.2.2 }
138 cananian 1.1.2.1 // we may have unconnected entrances if more than one header.
139 cananian 1.3.2.1 assert loop.loopEntrances().size()==1;
140 cananian 1.1.2.1 // done.
141 cananian 1.1.2.1 }
142 cananian 1.6 Map<Quad,Quad> copy(HCodeAndMaps<Quad> input, Loops l) {
143 cananian 1.6 Map<Quad,Quad> m = new HashMap<Quad,Quad>();
144 cananian 1.1.2.1 // clone all elements.
145 cananian 1.8 for (Object qO : l.loopIncElements()) {
146 cananian 1.8 Quad q = (Quad) qO;
147 cananian 1.6 Quad qq = input.elementMap().get(q);
148 cananian 1.6 Quad nq = qq.clone();
149 cananian 1.1.2.3 m.put(q, nq); // ancestor quad to newly cloned quad.
150 cananian 1.1.2.1 }
151 cananian 1.1.2.1 // clone all interior edges.
152 cananian 1.8 for (Object qO : l.loopIncElements()) {
153 cananian 1.8 Quad q = (Quad) qO;
154 cananian 1.1.2.1 for (int i=0; i<q.nextLength(); i++) {
155 cananian 1.1.2.1 Edge e = q.nextEdge(i);
156 cananian 1.3.2.1 assert m.containsKey(e.from());
157 cananian 1.1.2.1 if (m.containsKey(e.to()))
158 cananian 1.6 Quad.addEdge(m.get(e.from()), e.which_succ(),
159 cananian 1.6 m.get(e.to()), e.which_pred());
160 cananian 1.1.2.1 }
161 cananian 1.1.2.1 }
162 cananian 1.1.2.1 return m;
163 cananian 1.1.2.1 }
164 cananian 1.2 }