~ubuntu-branches/debian/squeeze/erlang/squeeze : revision 3

1

%% -*- erlang-indent-level: 2 -*-

2

%%========================================================================

3

%%

4

%% Interface for register allocating SPARC code. Uses hipe_regalloc.erl

5

%%

6

%%========================================================================

7

8

-module(hipe_sparc_ra_coalescing).

9

10

-export([alloc/2, lf_alloc/2]).

11

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

12

-include("../main/hipe.hrl").

13

14

15

lf_alloc(SparcCfg, Options) ->

16

{_, SpillLimit} = hipe_sparc_cfg:var_range(SparcCfg),

17

lf_alloc(SparcCfg, SpillLimit, Options).

18

19

lf_alloc(SparcCfg, SpillLimit, Options) ->

20

?inc_counter(ra_iteration_counter,1),

21

22

{Map, _NewSpillIndex} =

23

hipe_coalescing_regalloc:regalloc(SparcCfg, 0,

24

SpillLimit, hipe_sparc_specific),

25

26

TempMap = hipe_temp_map:cols2tuple(Map, hipe_sparc_specific),

27

28

{NewCfg, DontSpill} =

29

hipe_sparc_ra_postconditions:rewrite(

30

SparcCfg, TempMap, [], Options),

31

32

case DontSpill of

33

[] ->

34

%% Code to minimize stack size by allocation of temps to spillpositions

35

{TempMap2, NewSpillIndex2} =

36

hipe_spill_minimize:stackalloc(NewCfg, [],

37

0, Options,

38

hipe_sparc_specific,

39

TempMap),

40

TempMap3 = hipe_spill_minimize:mapmerge(hipe_temp_map:to_substlist(TempMap),

41

TempMap2),

42

TempMap4 = hipe_temp_map:cols2tuple( TempMap3, hipe_sparc_specific),

43

44

?add_spills(Options, NewSpillIndex2),

45

%%{SparcCfg2, NextPos} = hipe_sparc_caller_saves:rewrite(

46

%%NewCfg, TempMap, NewSpillIndex, Options),

47

%%{SparcCfg2, TempMap, NextPos};

48

{NewCfg, TempMap4, NewSpillIndex2};

49

_ ->

50

%% Since SpillLimit is used as a low-water-mark

51

%% the list of temps not to spill is uninteresting.

52

lf_alloc( NewCfg, SpillLimit, Options)

53

end.

54

55

56

57

%%

58

%% Calls regalloc to rewrite the code after register allocation.

59

%%

60

%% Coloring is given as a list of tuples of the form:

61

%% {Reg,{reg,NewReg}} or {Reg,{spill,SpillIndex}}.

62

%%

63

64

alloc(SparcCfg, Options) ->

65

{_, SpillLimit} = hipe_sparc_cfg:var_range(SparcCfg),

66

alloc(SparcCfg, unspilled, 0, SpillLimit, 0, Options).

67

68

alloc(SparcCfg, PrevSpillArea, SpillIndex, SpillLimit, Locs, Options) ->

69

%% io:format("Allocating\n"),

70

{Coloring, NewSpillIndex} =

71

hipe_coalescing_regalloc:regalloc(SparcCfg, SpillIndex,

72

SpillLimit, hipe_sparc_specific),

73

%% io:format("Coloring ~p\n",[Coloring]),

74

case SpillIndex < NewSpillIndex of

75

false ->

76

ColTuple = cols2tuple(Coloring),

77

Labels = hipe_sparc_cfg:labels(SparcCfg),

78

CFG0 = rewrite_bbs(Labels, SparcCfg, ColTuple),

79

NewCFG = hipe_sparc_cfg:var_range_update(CFG0, {0, 31}),

80

case SpillIndex of

81

0 ->

82

NewCFG;

83

_ ->

84

?add_spills(Options, NewSpillIndex),

85

NewConstTab =

86

hipe_consttab:update_block(hipe_sparc_cfg:data(NewCFG),

87

PrevSpillArea,

88

4,

89

word,

90

hipe_consttab:repeat(SpillIndex, 0)),

91

hipe_sparc_cfg:update_data(NewCFG, NewConstTab)

92

end;

93

true ->

94

Labels = hipe_sparc_cfg:labels(SparcCfg),

95

{Low, High} = hipe_sparc_cfg:var_range(SparcCfg),

96

hipe_gensym:set_var(sparc,High),

97

{CFG1, SpillArea} =

98

case PrevSpillArea of

99

unspilled ->

100

{NewCTab, SpillA} =

101

hipe_consttab:insert_block(hipe_sparc_cfg:data(SparcCfg),

102

4, word, [0]),

103

{hipe_sparc_cfg:update_data(SparcCfg, NewCTab), SpillA};

104

SpillA ->

105

{SparcCfg, SpillA}

106

end,

107

108

Spills = spill_regs(Coloring),

109

{CFG2, Locs0} = spill_rewrite_bbs(Labels, CFG1, Spills, SpillArea, Locs),

110

CFG3 = hipe_sparc_cfg:var_range_update(CFG2,

111

{Low,hipe_gensym:get_var(sparc)}),

112

alloc(CFG3, SpillArea, NewSpillIndex, SpillLimit,Locs0, Options)

113

end.

114

115

116

%%

117

%% Returns a list of {SpilledReg, {Tmp, LoadInstr, StoreInstr}}

118

%%

119

120

spill_regs([]) ->

121

[];

122

spill_regs([{_RegNr, {reg, _}} | Colors]) ->

123

spill_regs(Colors);

124

spill_regs([{RegNr, {spill, SpillIndex}} | Colors]) ->

125

SpillIndexImm = hipe_sparc:mk_imm(SpillIndex*4),

126

Info = {hipe_sparc:mk_reg(RegNr), SpillIndexImm},

127

[Info | spill_regs(Colors)].

128

129

%%

130

%% Rewrites a cfg where spills occured

131

%%

132

133

spill_rewrite_bbs([], CFG, _Spills, _SpillArea, Locs) ->

134

{CFG, Locs};

135

spill_rewrite_bbs([Lbl|Lbls], CFG, Spills, SpillArea, Locs) ->

136

BB = hipe_sparc_cfg:bb(CFG, Lbl),

137

Code = hipe_bb:code(BB),

138

{NewCode, Locs0} = spill_rewrite_instrs(Code, Spills, SpillArea),

139

NewCFG = hipe_sparc_cfg:bb_update(CFG, Lbl, hipe_bb:code_update(BB, NewCode)),

140

spill_rewrite_bbs(Lbls, NewCFG, Spills, SpillArea, Locs+Locs0).

141

142

spill_rewrite_instrs([], _Spills, _SpillArea) ->

143

{[], 0};

144

spill_rewrite_instrs([I|Is], Spills, SpillArea) ->

145

{NewI, Locs0} = spill_rewrite_instr(I, Spills, SpillArea),

146

{NewIs, Locs1} = spill_rewrite_instrs(Is, Spills, SpillArea),

147

{NewI++NewIs, Locs0+Locs1}.

148

149

spill_rewrite_instr(I, Spills, SpillArea) ->

150

{Defs, Uses} = hipe_sparc:def_use(I),

151

SpillUses = get_spills(Uses, Spills, Spills),

152

SpillDefs = get_spills(Defs, Spills, Spills),

153

case SpillUses++SpillDefs of

154

[] ->

155

{[I], 0};

156

_ ->

157

SpillAreaReg = hipe_sparc:mk_new_reg(),

158

LA = hipe_sparc:load_address_create(SpillAreaReg,

159

SpillArea, constant, []),

160

{Loads,UseSubst} =

161

case SpillUses of

162

[] ->

163

{[],[]};

164

[{R1u, Offset1u}] ->

165

Tmp1u = hipe_sparc:mk_new_reg(),

166

{[hipe_sparc:load_create(Tmp1u, uw, SpillAreaReg, Offset1u, [])],

167

[{R1u, Tmp1u}]};

168

[{R1u, Offset1u}, {R2u, Offset2u}] ->

169

Tmp1u = hipe_sparc:mk_new_reg(),

170

Tmp2u = hipe_sparc:mk_new_reg(),

171

{[hipe_sparc:load_create(Tmp1u, uw, SpillAreaReg, Offset1u, []),

172

hipe_sparc:load_create(Tmp2u, uw, SpillAreaReg, Offset2u, [])],

173

[{R1u, Tmp1u}, {R2u, Tmp2u}]}

174

end,

175

{Stores,DefSubst} =

176

case SpillDefs of

177

[] ->

178

{[],[]};

179

[{R1d, Offset1d}] ->

180

Tmp1d = hipe_sparc:mk_new_reg(),

181

{[hipe_sparc:store_create(SpillAreaReg, Offset1d, Tmp1d)],

182

[{R1d, Tmp1d}]}

183

end,

184

185

C1 = hipe_sparc:comment_create('** SPILL START **', []),

186

C2 = hipe_sparc:comment_create('** SPILL END **', []),

187

NewI = hipe_sparc:subst_defines(hipe_sparc:subst_uses(I, UseSubst), DefSubst),

188

{[C1, LA] ++ Loads ++ [NewI] ++ Stores ++ [C2],

189

length(UseSubst)+length(DefSubst)}

190

end.

191

192

193

get_spills([], _, _) ->

194

[];

195

get_spills([_|Rs], [], Spills) ->

196

get_spills(Rs, Spills, Spills);

197

get_spills([R|Rs], [{R, Info}|_], Spills) ->

198

[{R, Info} | get_spills(Rs, Spills, Spills)];

199

get_spills(Rs, [_|Ss], Spills) ->

200

get_spills(Rs, Ss, Spills).

201

202

203

%%

204

%% Converts a list of [{R1, C1}, {R2, C2}, ...} to a tuple {C17, C23, ...}.

205

%%

206

%% The N's must be unique but do not have to be sorted and they can be sparse.

207

%%

208

209

cols2tuple(Map) ->

210

hipe_temp_map:cols2tuple(Map, hipe_sparc_specific).

211

212

213

%%

214

%% Rewrite a cfg to use the allocated registers

215

%%

216

217

rewrite_bbs([], CFG, _ColTuple) ->

218

CFG;

219

rewrite_bbs([Lbl|Lbls], CFG, ColTuple) ->

220

BB = hipe_sparc_cfg:bb(CFG, Lbl),

221

Code = hipe_bb:code(BB),

222

NewCode = rewrite_instrs(Code, ColTuple),

223

NewCFG = hipe_sparc_cfg:bb_update(CFG, Lbl, hipe_bb:code_update(BB,NewCode)),

224

rewrite_bbs(Lbls, NewCFG, ColTuple).

225

226

rewrite_instrs([], _ColTuple) ->

227

[];

228

rewrite_instrs([I|Is], ColTuple) ->

229

[rewrite_instr(I, ColTuple) | rewrite_instrs(Is, ColTuple)].

230

231

rewrite_instr(Ins, ColTuple) ->

232

case hipe_sparc:type(Ins) of

233

label -> Ins;

234

nop -> Ins;

235

block -> Ins;

236

align -> Ins;

237

comment -> Ins;

238

b -> Ins;

239

goto -> Ins;

240

move ->

241

NewDst = color_arg(hipe_sparc:move_dest(Ins), ColTuple),

242

NewSrc = color_arg(hipe_sparc:move_src(Ins), ColTuple),

243

hipe_sparc:move_dest_update(hipe_sparc:move_src_update(Ins, NewSrc), NewDst);

244

cmov_cc ->

245

NewDst = color_arg(hipe_sparc:cmov_cc_dest(Ins), ColTuple),

246

NewSrc = color_arg(hipe_sparc:cmov_cc_src(Ins), ColTuple),

247

I0 = hipe_sparc:cmov_cc_src_update(Ins, NewSrc),

248

hipe_sparc:cmov_cc_dest_update(I0, NewDst);

249

cmov_r ->

250

NewDst = color_arg(hipe_sparc:cmov_r_dest(Ins), ColTuple),

251

NewSrc = color_arg(hipe_sparc:cmov_r_src(Ins), ColTuple),

252

NewReg = color_arg(hipe_sparc:cmov_r_reg(Ins), ColTuple),

253

I0 = hipe_sparc:cmov_r_dest_update(Ins, NewDst),

254

I1 = hipe_sparc:cmov_r_src_update(I0, NewSrc),

255

hipe_sparc:cmov_r_reg_update(I1, NewReg);

256

alu ->

257

NewSrc1 = color_arg(hipe_sparc:alu_src1(Ins), ColTuple),

258

NewSrc2 = color_arg(hipe_sparc:alu_src2(Ins), ColTuple),

259

NewDst = color_arg(hipe_sparc:alu_dest(Ins), ColTuple),

260

I0 = hipe_sparc:alu_src1_update(Ins, NewSrc1),

261

I1 = hipe_sparc:alu_src2_update(I0, NewSrc2),

262

hipe_sparc:alu_dest_update(I1, NewDst);

263

alu_cc ->

264

NewSrc1 = color_arg(hipe_sparc:alu_cc_src1(Ins), ColTuple),

265

NewSrc2 = color_arg(hipe_sparc:alu_cc_src2(Ins), ColTuple),

266

NewDst = color_arg(hipe_sparc:alu_cc_dest(Ins), ColTuple),

267

I0 = hipe_sparc:alu_cc_src1_update(Ins, NewSrc1),

268

I1 = hipe_sparc:alu_cc_src2_update(I0, NewSrc2),

269

hipe_sparc:alu_cc_dest_update(I1, NewDst);

270

sethi ->

271

NewDest = color_arg(hipe_sparc:sethi_dest(Ins), ColTuple),

272

hipe_sparc:sethi_dest_update(Ins, NewDest);

273

load ->

274

NewDest = color_arg(hipe_sparc:load_dest(Ins), ColTuple),

275

NewSrc = color_arg(hipe_sparc:load_src(Ins), ColTuple),

276

NewOff = color_arg(hipe_sparc:load_off(Ins), ColTuple),

277

I0 = hipe_sparc:load_dest_update(Ins, NewDest),

278

I1 = hipe_sparc:load_src_update(I0, NewSrc),

279

hipe_sparc:load_off_update(I1, NewOff);

280

store ->

281

NewDest = color_arg(hipe_sparc:store_dest(Ins), ColTuple),

282

NewSrc = color_arg(hipe_sparc:store_src(Ins), ColTuple),

283

NewOff = color_arg(hipe_sparc:store_off(Ins), ColTuple),

284

I0 = hipe_sparc:store_dest_update(Ins, NewDest),

285

I1 = hipe_sparc:store_src_update(I0, NewSrc),

286

hipe_sparc:store_off_update(I1, NewOff);

287

br ->

288

NewReg = color_arg(hipe_sparc:br_reg(Ins), ColTuple),

289

hipe_sparc:br_reg_update(Ins, NewReg);

290

%% Warning, not complete

291

jmp_link ->

292

NewTarget = color_arg(hipe_sparc:jmp_link_target(Ins), ColTuple),

293

NewOff = color_arg(hipe_sparc:jmp_link_off(Ins), ColTuple),

294

I0 = hipe_sparc:jmp_link_target_update(Ins, NewTarget),

295

hipe_sparc:jmp_link_off_update(I0, NewOff);

296

jmp ->

297

NewTarget = color_arg(hipe_sparc:jmp_target(Ins), ColTuple),

298

NewOff = color_arg(hipe_sparc:jmp_off(Ins), ColTuple),

299

I0 = hipe_sparc:jmp_target_update(Ins, NewTarget),

300

hipe_sparc:jmp_off_update(I0, NewOff);

301

call_link ->

302

Ins1 =

303

case hipe_sparc:call_link_type(Ins) of

304

closure ->

305

NewTarget = color_arg(hipe_sparc:call_link_target(Ins), ColTuple),

306

hipe_sparc:call_link_target_update(Ins, NewTarget);

307

_ -> Ins

308

end,

309

NewLink = color_arg(hipe_sparc:call_link_link(Ins1), ColTuple),

310

hipe_sparc:call_link_link_update(Ins1, NewLink);

311

%% end warning

312

load_atom ->

313

NewDest = color_arg(hipe_sparc:load_atom_dest(Ins), ColTuple),

314

hipe_sparc:load_atom_dest_update(Ins, NewDest);

315

load_address ->

316

NewDest = color_arg(hipe_sparc:load_address_dest(Ins), ColTuple),

317

hipe_sparc:load_address_dest_update(Ins, NewDest);

318

_ -> Ins

319

end.

320

321

color_arg(Arg, ColTuple) ->

322

%% io:format("Color_arg: ~p ~p\n", [Arg,ColTuple]),

323

case hipe_sparc:is_reg(Arg) of

324

true ->

325

case hipe_temp_map:find(hipe_sparc:reg_nr(Arg), ColTuple) of

326

{reg, NewRgNr} ->

327

hipe_sparc:mk_reg(NewRgNr);

328

{spill, _SpillIndex} ->

329

exit({sparc, spilled})

330

end;

331

false ->

332

Arg

333

end.