aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/x86/hipe_x86_spill_restore.erl
blob: 32b1eb7b40fac377e51a7d7d382dc031dd7d2def (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
%% -*- erlang-indent-level: 2 -*-
%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2008-2016. All Rights Reserved.
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%%     http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%%
%% %CopyrightEnd%
%%
%% ====================================================================
%% Authors : Dogan Yazar and Erdem Aksu (KT2 project of 2008)
%% ====================================================================

-ifdef(HIPE_AMD64).
-define(HIPE_X86_SPILL_RESTORE, hipe_amd64_spill_restore).
-define(HIPE_X86_LIVENESS,      hipe_amd64_liveness).
-define(HIPE_X86_REGISTERS,	hipe_amd64_registers).
-define(X86STR, "amd64").
-else.
-define(HIPE_X86_SPILL_RESTORE, hipe_x86_spill_restore).
-define(HIPE_X86_LIVENESS,      hipe_x86_liveness).
-define(HIPE_X86_REGISTERS,     hipe_x86_registers).
-define(X86STR, "x86").
-endif.

-module(?HIPE_X86_SPILL_RESTORE).

-export([spill_restore/2]).

%% controls which set library is used to keep temp variables. 
-define(SET_MODULE, ordsets).

%% Turn on instrumentation.
-define(HIPE_INSTRUMENT_COMPILER, true). 

-include("../main/hipe.hrl").
-include("../x86/hipe_x86.hrl"). % Added for the definition of #pseudo_call{}
-include("../flow/cfg.hrl").     % Added for the definition of #cfg{}

%% Main function
spill_restore(CFG0, Options) ->
  CFG1 = ?option_time(firstPass(CFG0), ?X86STR" First Pass", Options),
  ?option_time(secondPass(CFG1), ?X86STR" Second Pass", Options).

%% Performs the first pass of the algorithm.
%% By working bottom up, introduce the pseudo_spills.
firstPass(CFG0) ->
  %% get the labels bottom up
  Labels = hipe_x86_cfg:postorder(CFG0),
  Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0),
  %% spill around the function will be introduced below the move
  %% formals, so get all labels except it.
  LabelsExceptMoveFormals = lists:sublist(Labels, length(Labels)-1),
  %% all work is done by the helper function firstPassHelper
  %% saveTree keeps the all newly introduced spills. Keys are the labels.
  {CFG1, SaveTree} = firstPassHelper(LabelsExceptMoveFormals, Liveness, CFG0),
  case hipe_x86_cfg:reverse_postorder(CFG0) of
    [Label1, Label2|_] ->
      SaveTreeElement = saveTreeLookup(Label2, SaveTree),
      %% FilteredSaveTreeElement is the to be spilled temps around the
      %% function call. They are spilled just before move formals.
      FilteredSaveTreeElement = [T || T <- SaveTreeElement, temp_is_pseudo(T)],
      Block = hipe_x86_cfg:bb(CFG1, Label1),
      Code = hipe_bb:code(Block),
      %% The following statements are tedious but work ok.
      %% Put spills between move formals and the jump code.
      %% This disgusting thing is done because spills should be
      %% introduced after move formals. 
      %% Another solution may be to introduce another block.
      MoveCodes = lists:sublist(Code, length(Code)-1),
      JumpCode = lists:last(Code),
      hipe_x86_cfg:bb_add(CFG1, Label1, hipe_bb:mk_bb(MoveCodes ++ [hipe_x86:mk_pseudo_spill(FilteredSaveTreeElement), JumpCode]));
    _ ->
      CFG1
  end.

%% helper function of firstPass

%% processes all labels recursively and decides the spills to be put.
%% spills are introduced before each function call (pseudo_call) as well as 
%% global spill is found
firstPassHelper(Labels, Liveness, CFG) ->
  firstPassHelper(Labels, Liveness, CFG, gb_trees:empty()).

firstPassHelper([Label|Labels], Liveness, CFG, SaveTree) ->
  LiveOut = from_list(?HIPE_X86_LIVENESS:liveout(Liveness, Label)),
  Block = hipe_x86_cfg:bb(CFG, Label),
  Code = hipe_bb:code(Block),
  Succ = hipe_x86_cfg:succ(CFG, Label),
  IntersectedSaveList = findIntersectedSaveList(Succ,SaveTree),
  %% call firstPassDoBlock which will give the updated block
  %% code(including spills) as well as Intersected Save List which
  %% should be passed above blocks
  {_,NewIntersectedList,NewCode} = 
    firstPassDoBlock(Code, LiveOut,IntersectedSaveList),
  NewBlock = hipe_bb:code_update(Block, NewCode),
  NewCFG = hipe_x86_cfg:bb_add(CFG, Label, NewBlock), 
  SizeOfSet = setSize(NewIntersectedList),
  %% if the Intersected Save List is not empty, insert it in the save tree.
  if SizeOfSet =/= 0 ->
      UpdatedSaveTree = gb_trees:insert(Label, NewIntersectedList, SaveTree),
      firstPassHelper(Labels, Liveness, NewCFG, UpdatedSaveTree);
     true ->
      firstPassHelper(Labels, Liveness, NewCFG, SaveTree)
  end;
firstPassHelper([], _, CFG, SaveTree) ->
  {CFG, SaveTree}.

%% handle each instruction in the block bottom up
firstPassDoBlock(Insts, LiveOut, IntersectedSaveList) -> 
  lists:foldr(fun firstPassDoInsn/2, {LiveOut,IntersectedSaveList,[]}, Insts).

firstPassDoInsn(I, {LiveOut,IntersectedSaveList,PrevInsts}) ->
  case I of
    #pseudo_call{} ->
      do_pseudo_call(I, {LiveOut,IntersectedSaveList,PrevInsts});
    _ -> % other instructions
      DefinedList = from_list( ?HIPE_X86_LIVENESS:defines(I)),
      UsedList = from_list(?HIPE_X86_LIVENESS:uses(I)),
      NewLiveOut = subtract(union(LiveOut, UsedList), DefinedList),
      NewIntersectedSaveList = subtract(IntersectedSaveList, DefinedList),
      {NewLiveOut, NewIntersectedSaveList, [I|PrevInsts]}
  end.

do_pseudo_call(I, {LiveOut,IntersectedSaveList,PrevInsts}) ->
  LiveTemps = [Temp || Temp <- to_list(LiveOut), temp_is_pseudo(Temp)],
  NewIntersectedSaveList = union(IntersectedSaveList, LiveOut),
  {LiveOut, NewIntersectedSaveList, [hipe_x86:mk_pseudo_spill(LiveTemps), I | PrevInsts]}.
    
findIntersectedSaveList(LabelList, SaveTree) -> 
  findIntersectedSaveList([saveTreeLookup(Label,SaveTree) || Label <- LabelList]).

findIntersectedSaveList([]) ->
  [];
findIntersectedSaveList([List1]) ->
  List1;
findIntersectedSaveList([List1,List2|Rest]) ->
  findIntersectedSaveList([intersection(List1, List2)|Rest]).

saveTreeLookup(Label, SaveTree) ->
  case gb_trees:lookup(Label, SaveTree) of
    {value, SaveList} ->
      SaveList;
    _ ->
      []
  end.

%% Performs the second pass of the algorithm.
%% It basically eliminates the unnecessary spills and introduces restores.
%% Works top down
secondPass(CFG0) ->
  Labels = hipe_x86_cfg:reverse_postorder(CFG0),
  Liveness = ?HIPE_X86_LIVENESS:analyse(CFG0),
  secondPassHelper(Labels,Liveness,CFG0).

%% helper function of secondPass.

%% recursively handle all labels given.
secondPassHelper(Labels, Liveness, CFG) ->
  secondPassHelper(Labels, Liveness, CFG, gb_trees:empty(), CFG).

%% AccumulatedCFG stands for the CFG that has restore edges incrementally.
%% UnmodifiedCFG is the CFG created after first pass.

%% AccumulatedSaveTree is used to eliminate the unnecessary saves. The
%% saves (spills) in above blocks are traversed down (if still live
%% and not redefined) and redundant saves are eliminated in the lower
%% blocks.
%% For memory efficiency, it may be better not to maintain the
%% AccumulatedSaveTree but traverse the tree recursively and pass the
%% save lists to the childs individually.
%% But current approach may be faster even though it needs bigger memory.

secondPassHelper([Label|RestOfLabels], Liveness,
		 AccumulatedCFG, AccumulatedSaveTree, UnmodifiedCFG) ->
  LiveOut = ?HIPE_X86_LIVENESS:liveout(Liveness, Label),
  Block = hipe_x86_cfg:bb(AccumulatedCFG, Label),
  Code = hipe_bb:code(Block),
  
  %% UnmodifiedCFG is needed for getting the correct predecessors.
  %% (i.e. not to get the restore edge blocks)
  PredList = hipe_x86_cfg:pred(UnmodifiedCFG, Label),
  %% find the spills coming from all the parents by intersecting 
  InitialAccumulatedSaveList = 
    findIntersectedSaveList(PredList, AccumulatedSaveTree),
  AccumulatedSaveList =
    keepLiveVarsInAccumSaveList(InitialAccumulatedSaveList, LiveOut),
  
  {NewCode, CFGUpdateWithRestores, NewAccumulatedSaveList} =
    secondPassDoBlock(Label, Code, AccumulatedCFG, AccumulatedSaveList),
  
  UpdatedAccumulatedSaveTree =
    gb_trees:insert(Label, NewAccumulatedSaveList, AccumulatedSaveTree),
  NewBlock = hipe_bb:code_update(Block, NewCode),
  NewCFG = hipe_x86_cfg:bb_add(CFGUpdateWithRestores, Label, NewBlock),
  secondPassHelper(RestOfLabels, Liveness, NewCFG,
		   UpdatedAccumulatedSaveTree, UnmodifiedCFG);
secondPassHelper([], _, AccumulatedCFG, _, _) ->
  AccumulatedCFG.

secondPassDoBlock(CurrentLabel, Insts, CFG, AccumulatedSaveList) -> 
  {NewAccumulatedSaveList,NewInsts,_,_,CFGUpdateWithRestores} = 
    lists:foldl(fun secondPassDoInsn/2, {AccumulatedSaveList,[],[],CurrentLabel,CFG}, Insts),
  {NewInsts, CFGUpdateWithRestores, NewAccumulatedSaveList}.

secondPassDoInsn(I, {AccumulatedSaveList,PrevInsts,SpillList,CurrentLabel,CFG}) -> 
  case I of
    #pseudo_spill{} ->
      %% spill variables that are not accumulated from top down
      %% (which are not already saved)
      VariablesAlreadySaved = [X || {X,_} <- to_list(AccumulatedSaveList)],
      VariablesToBeSpilled = I#pseudo_spill.args -- VariablesAlreadySaved,
      NewSpillList = [{Temp, hipe_x86:mk_new_temp(Temp#x86_temp.type)} || Temp <- VariablesToBeSpilled],
      %% update accumulated saved list by adding the newly spilled variables.
      NewAccumulatedSaveList = union(AccumulatedSaveList, from_list(NewSpillList)),
      {NewAccumulatedSaveList, PrevInsts ++ secondPassDoPseudoSpill(NewSpillList), NewSpillList, CurrentLabel, CFG};
    #pseudo_call{} ->
      {CFGUpdateWithRestores, NewPseudoCall} =
	secondPassDoPseudoCall(I, AccumulatedSaveList, CFG),
      %% spill list is emptied after use
      {AccumulatedSaveList, PrevInsts ++ [NewPseudoCall], CurrentLabel, [], CFGUpdateWithRestores};
    _ ->
      %% remove the defined variables from the accumulated save
      %% list since they need to be saved again in later occasions.
      DefinedList = from_list(?HIPE_X86_LIVENESS:defines(I)),
      NewAccumulatedSaveList = removeRedefVarsFromAccumSaveList(AccumulatedSaveList, DefinedList),
      {NewAccumulatedSaveList, PrevInsts ++ [I], SpillList, CurrentLabel, CFG}
  end.

%% remove dead vars from accumulated save list so that they are not restored.  
keepLiveVarsInAccumSaveList([], _) ->
  [];
keepLiveVarsInAccumSaveList([{Var,Temp}|Rest], DefinedList) ->
  IsDefined = is_element(Var, DefinedList),
  case IsDefined of 
    true  -> [{Var,Temp}|keepLiveVarsInAccumSaveList(Rest, DefinedList)];
    false -> keepLiveVarsInAccumSaveList(Rest, DefinedList)    
  end.

%% remove the redefined variables from accumulated save list since
%% they are changed.
removeRedefVarsFromAccumSaveList([], _) ->
  [];
removeRedefVarsFromAccumSaveList([{Var,Temp}|Rest], DefinedList) ->
  IsDefined = is_element(Var, DefinedList),
  case IsDefined of 
    true  -> removeRedefVarsFromAccumSaveList(Rest, DefinedList);
    false -> [{Var,Temp}|removeRedefVarsFromAccumSaveList(Rest, DefinedList)]
  end.
        
%% convert pseudo_spills to move instructions. 
secondPassDoPseudoSpill(SpillList) ->
  lists:foldl(fun convertPseudoSpillToMov/2, [], SpillList).

%% if there are variables to be restored, then call addRestoreBlockToEdge to 
%% place them in a new block on the edge of the blocks.
secondPassDoPseudoCall(I, RestoreList, CFG) ->
  ContLabel = I#pseudo_call.contlab,
  SizeOfSet = setSize(RestoreList),
  if SizeOfSet =/= 0 ->
      addRestoreBlockToEdge(I, ContLabel, CFG, RestoreList);
     true ->
      {CFG, I}
  end.

%% prepares the moves for the spills.    
convertPseudoSpillToMov({Temp, NewTemp}, OtherMoves) ->
  OtherMoves ++ [mkMove(Temp, NewTemp)].

%% prepares the moves for the restores.
%% Called by addRestoreBlockToEdge while introducing the restores.
convertPseudoRestoreToMov({Temp, NewTemp}, OtherMoves) ->
  OtherMoves ++ [mkMove(NewTemp, Temp)].

%% makes the move record, special care is taken for doubles.    
mkMove(NewTemp,Temp) ->
  if Temp#x86_temp.type =:= 'double' ->
      hipe_x86:mk_fmove(NewTemp, Temp);
     true ->
      hipe_x86:mk_move(NewTemp, Temp)
  end.

%% adds a new block (on the edge) that includes introduced restore moves.
addRestoreBlockToEdge(PseudoCall, ContLabel, CFG, TempArgsList) ->
  NextLabel = hipe_gensym:get_next_label(x86),
  NewCode = lists:foldl(fun convertPseudoRestoreToMov/2, [], TempArgsList) ++ [hipe_x86:mk_jmp_label(ContLabel)],
  NewBlock = hipe_bb:mk_bb(NewCode),
  NewPseudoCall = redirect_pseudo_call(PseudoCall, ContLabel, NextLabel),
  NewCFG = hipe_x86_cfg:bb_add(CFG, NextLabel, NewBlock),
  {NewCFG, NewPseudoCall}.

%% used instead of hipe_x86_cfg:redirect_jmp since it does not handle
%% pseudo_call calls.
redirect_pseudo_call(I = #pseudo_call{contlab=ContLabel}, Old, New) ->
  case Old =:= ContLabel of
    true  -> I#pseudo_call{contlab=New};
    false -> I
  end.

temp_is_pseudo(Temp) ->
  case hipe_x86:is_temp(Temp) of
    true  -> not(?HIPE_X86_REGISTERS:is_precoloured(hipe_x86:temp_reg(Temp)));
    false -> false
  end.

%%---------------------------------------------------------------------
%% Set operations where the module name is an easily changeable macro
%%---------------------------------------------------------------------

union(Set1, Set2) ->
  ?SET_MODULE:union(Set1, Set2).

setSize(Set) ->
  ?SET_MODULE:size(Set).

from_list(List) ->
  ?SET_MODULE:from_list(List).

to_list(Set) ->
  ?SET_MODULE:to_list(Set).

subtract(Set1, Set2) ->
  ?SET_MODULE:subtract(Set1, Set2).

intersection(Set1, Set2) ->
  ?SET_MODULE:intersection(Set1, Set2). 

is_element(Element, Set) ->
  ?SET_MODULE:is_element(Element, Set).