FastColorer


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 1997-1999 Raja Vallee-Rai
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the
16   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17   * Boston, MA 02111-1307, USA.
18   */
19  
20  /*
21   * Modified by the Sable Research Group and others 1997-1999.  
22   * See the 'credits' file distributed with Soot for the complete list of
23   * contributors.  (Soot is distributed at http://www.sable.mcgill.ca/soot)
24   */
25  
26  
27  package soot.toolkits.scalar;
28  
29  import soot.*;
30  import soot.toolkits.graph.*;
31  import soot.util.*;
32  import java.util.*;
33  
34  /** Provides methods for register coloring.  Jimple uses these methods
35   * to assign the local slots appropriately. */
36  public class FastColorer
37  {   
38      /** Provides a coloring for the locals of 
39       * <code>unitBody</code>, attempting to not
40       * split locals assigned the same name in the original Jimple. */
41      public static void unsplitAssignColorsToLocals(Body unitBody, 
42                                                     Map localToGroup, 
43                                                     Map localToColor, 
44                                                     Map groupToColorCount)
45      {
46          ExceptionalUnitGraph unitGraph = new ExceptionalUnitGraph(unitBody);
47  
48          LiveLocals liveLocals;        
49          liveLocals = new SimpleLiveLocals(unitGraph);
50          
51          
52          UnitInterferenceGraph intGraph = 
53              new UnitInterferenceGraph(unitBody, localToGroup, liveLocals);
54  
55          Map localToOriginalName = new HashMap();
56          
57          // Map each local variable to its original name
58          {
59              Iterator localIt = intGraph.getLocals().iterator();
60              
61              while(localIt.hasNext())
62              {
63                  Local local = (Local) localIt.next();
64                  
65                  int signIndex;
66                  
67                  signIndex = local.getName().indexOf("#");
68                  
69                  if(signIndex != -1)
70                  {
71                      localToOriginalName.put(local, 
72                                 local.getName().substring(0, signIndex));
73                  }
74                  else
75                      localToOriginalName.put(local, local.getName()); 
76                      
77              }
78          }
79          
80          Map originalNameAndGroupToColors = new HashMap();
81              // maps an original name to the colors being used for it
82                      
83          // Assign a color for each local.
84          {
85              int[] freeColors = new int[10];
86              Iterator localIt = intGraph.getLocals().iterator();
87              
88              while(localIt.hasNext())
89              {
90                  Local local = (Local) localIt.next();
91                  
92                  if(localToColor.containsKey(local))
93                  {
94                      // Already assigned, probably a parameter
95                      continue;
96                  }
97                  
98                  Object   group = localToGroup.get(local);
99                  int colorCount = 
100                     ((Integer  ) groupToColorCount.get(group)).intValue();
101                 
102                 if(freeColors.length < colorCount)
103                     freeColors = 
104                         new int[Math.max(freeColors.length * 2, colorCount)];
105                 
106                 // Set all colors to free.
107                 {
108                     for(int i= 0; i < colorCount; i++)
109                         freeColors[i] = 1;
110                 }
111                 
112                 // Remove unavailable colors for this local
113                 {
114                     Local[] interferences = 
115                         intGraph.getInterferencesOf(local);
116 
117                     for(int i = 0; i < interferences.length; i++)
118                     {
119                         if(localToColor.containsKey(interferences[i]))
120                         {
121                             int usedColor = 
122                                 ((Integer  ) localToColor.get(interferences[i]))
123                                 .intValue();
124                 
125                             freeColors[usedColor] = 0;
126                         }
127                     }
128                 }
129                 
130                 // Assign a color to this local.
131                 {
132                     String   originalName = 
133                         (String  ) localToOriginalName.get(local);
134                     List originalNameColors = 
135                         (List) originalNameAndGroupToColors.get
136                         (new StringGroupPair(originalName, group));
137                     
138                     if(originalNameColors == null)
139                     {
140                         originalNameColors = new ArrayList();
141                         originalNameAndGroupToColors.put
142                             (new StringGroupPair(originalName, group), 
143                              originalNameColors);
144                     }
145                     
146                     boolean found = false;
147                     int assignedColor = 0;
148                     
149                     // Check if the colors assigned to this 
150                     // original name is already free
151                     {
152                         Iterator colorIt = originalNameColors.iterator();
153                         
154                         while(colorIt.hasNext())
155                         {
156                             Integer   color = (Integer  ) colorIt.next();
157                             
158                             if(freeColors[color.intValue()] == 1)
159                             {
160                                 found = true;
161                                 assignedColor = color.intValue();
162                             }
163                         }
164                     }
165                     
166                     if(!found)
167                     {
168                         assignedColor = colorCount++;
169                         groupToColorCount.put(group, new Integer  (colorCount));
170                         originalNameColors.add(new Integer  (assignedColor));
171                     }   
172                     
173                     localToColor.put(local, new Integer  (assignedColor));
174                 }
175             }
176         }                            
177     }    
178 
179     /** Provides an economical coloring for the locals of 
180      * <code>unitBody</code>. */
181     public static void assignColorsToLocals(Body unitBody, Map localToGroup, 
182         Map localToColor, Map groupToColorCount)
183     {
184         ExceptionalUnitGraph unitGraph = new ExceptionalUnitGraph(unitBody);
185         LiveLocals liveLocals;
186        
187         liveLocals = new SimpleLiveLocals(unitGraph);
188 
189         UnitInterferenceGraph intGraph = 
190             new UnitInterferenceGraph(unitBody, localToGroup, liveLocals);
191 
192         // Assign a color for each local.
193         {
194             int[] freeColors = new int[10];
195             Iterator localIt = intGraph.getLocals().iterator();
196             
197             while(localIt.hasNext())
198             {
199                 Local local = (Local) localIt.next();
200                 
201                 if(localToColor.containsKey(local))
202                 {
203                     // Already assigned, probably a parameter
204                     continue;
205                 }
206                 
207                 Object   group = localToGroup.get(local);
208                 int colorCount = 
209                     ((Integer  ) groupToColorCount.get(group)).intValue();
210                 
211                 if(freeColors.length < colorCount)
212                     freeColors = new int[Math.max(freeColors.length * 2, 
213                                                   colorCount)];
214                 
215                 // Set all colors to free.
216                 {
217                     for(int i= 0; i < colorCount; i++)
218                         freeColors[i] = 1;
219                 }
220                 
221                 // Remove unavailable colors for this local
222                 {
223                     Local[] interferences = 
224                         intGraph.getInterferencesOf(local);
225 
226                     for(int i = 0; i < interferences.length; i++)
227                     {
228                         if(localToColor.containsKey(interferences[i]))
229                         {
230                             int usedColor = 
231                                 ((Integer  ) localToColor.
232                                  get(interferences[i])).intValue();
233                 
234                             freeColors[usedColor] = 0;
235                         }
236                     }
237                 }
238                 
239                 // Assign a color to this local.
240                 {
241                     boolean found = false;
242                     int assignedColor = 0;
243                     
244                     for(int i = 0; i < colorCount; i++)
245                         if(freeColors[i] == 1)
246                         {
247                             found = true;
248                             assignedColor = i;
249                         }
250                     
251                     if(!found)
252                     {
253                         assignedColor = colorCount++;
254                         groupToColorCount.put(group, new Integer  (colorCount));
255                     }   
256                     
257                     localToColor.put(local, new Integer  (assignedColor));
258                 }
259             }
260         }
261                             
262     }
263 
264     /** Implementation of a unit interference graph. */
265     public static class UnitInterferenceGraph
266     {
267         Map localToLocals;// Maps a local to its interfering locals.
268         List locals;
269         
270         private UnitInterferenceGraph()
271         {
272         }
273     
274         public List getLocals()
275         {
276             return locals;
277         }
278         
279         public UnitInterferenceGraph(Body body, Map localToGroup, 
280                                      LiveLocals liveLocals)
281         {
282             locals = new ArrayList();
283             locals.addAll(body.getLocals());
284             
285             // Initialize localToLocals
286             {
287                 localToLocals = new HashMap(body.getLocalCount() * 2 + 1, 
288                                             0.7f);
289     
290                 Iterator localIt = body.getLocals().iterator();
291     
292                 while(localIt.hasNext())
293                 {
294                     Local local = (Local) localIt.next();
295     
296                     localToLocals.put(local, new ArraySet());
297                 }
298             }
299     
300             // Go through code, noting interferences
301             {
302                 Iterator codeIt = body.getUnits().iterator();
303     
304                 while(codeIt.hasNext())
305                     {
306                         Unit unit = (Unit) codeIt.next();
307     
308                         List liveLocalsAtUnit = 
309                             liveLocals.getLiveLocalsAfter(unit);
310                     
311                         // Note interferences if this stmt is a definition
312                         {
313                             List defBoxes = unit.getDefBoxes();
314                 
315                             if(!defBoxes.isEmpty()) {
316                 
317                                 if(!(defBoxes.size() ==1)) 
318                                     throw new RuntimeException  
319                                         ("invalid number of def boxes");
320                             
321                                 if(((ValueBox)defBoxes.get(0)).getValue() 
322                                    instanceof Local) 
323                                 {
324                                     Local defLocal = (Local) ((ValueBox)defBoxes.get(0)).getValue();
325                                     Iterator localIt = liveLocalsAtUnit.iterator();
326                                 
327                                     while(localIt.hasNext())
328                                     {
329                                         Local otherLocal = (Local) localIt.next();
330                 
331                                         if(localToGroup.get(otherLocal)
332                                               .equals(localToGroup.get(defLocal)))
333                                             setInterference(defLocal, otherLocal);
334                                     }
335                                 }   
336                             } 
337                     
338                         }                    
339                     }
340             }
341         }
342     
343         public boolean localsInterfere(Local l1, Local l2)
344         {
345             return ((Set) localToLocals.get(l1)).contains(l2);
346         }
347     
348         public void setInterference(Local l1, Local l2)
349         {
350             ((Set) localToLocals.get(l1)).add(l2);
351             ((Set) localToLocals.get(l2)).add(l1);
352         }
353     
354         public boolean isEmpty()
355         {
356             return localToLocals.isEmpty();
357         }
358         
359         Local[] getInterferencesOf(Local l)
360         {
361             Object  [] objects = ((Set) localToLocals.get(l)).toArray();
362             Local[] locals = new Local[objects.length];
363     
364             for(int i = 0; i < objects.length; i++)
365                 locals[i] = (Local) objects[i];
366     
367             return locals; 
368         }
369     }
370 }
371 
372 /** Binds together a String and a Group. */
373 class StringGroupPair
374 {
375     String   string;
376     Object   group;
377     
378     public StringGroupPair(String   s, Object   g)
379     {
380         string = s;
381         group = g;    
382     }
383     
384     public boolean equals(Object   p)
385     {
386         if(p instanceof StringGroupPair)
387         {
388             return ((StringGroupPair) p).string.equals(this.string) &&
389                 ((StringGroupPair) p).group.equals(this.group);
390         }
391         
392         return false;
393     }
394     
395     public int hashCode()
396     {
397         return string.hashCode() * 101 + group.hashCode() + 17;
398     }
399 }
400
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags