11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * memops - try to combine memory ops.
31f5207b7SJohn Levon *
41f5207b7SJohn Levon * Copyright (C) 2004 Linus Torvalds
51f5207b7SJohn Levon */
61f5207b7SJohn Levon
71f5207b7SJohn Levon #include <string.h>
81f5207b7SJohn Levon #include <stdarg.h>
91f5207b7SJohn Levon #include <stdlib.h>
101f5207b7SJohn Levon #include <stdio.h>
111f5207b7SJohn Levon #include <stddef.h>
121f5207b7SJohn Levon #include <assert.h>
131f5207b7SJohn Levon
141f5207b7SJohn Levon #include "parse.h"
151f5207b7SJohn Levon #include "expression.h"
161f5207b7SJohn Levon #include "linearize.h"
171f5207b7SJohn Levon #include "flow.h"
181f5207b7SJohn Levon
find_dominating_parents(pseudo_t pseudo,struct instruction * insn,struct basic_block * bb,unsigned long generation,struct pseudo_list ** dominators,int local)191f5207b7SJohn Levon static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
201f5207b7SJohn Levon struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
211f5207b7SJohn Levon int local)
221f5207b7SJohn Levon {
231f5207b7SJohn Levon struct basic_block *parent;
241f5207b7SJohn Levon
251f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) {
261f5207b7SJohn Levon struct instruction *one;
271f5207b7SJohn Levon struct instruction *br;
281f5207b7SJohn Levon pseudo_t phi;
291f5207b7SJohn Levon
301f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(parent->insns, one) {
311f5207b7SJohn Levon int dominance;
321f5207b7SJohn Levon if (!one->bb)
331f5207b7SJohn Levon continue;
341f5207b7SJohn Levon if (one == insn)
351f5207b7SJohn Levon goto no_dominance;
361f5207b7SJohn Levon dominance = dominates(pseudo, insn, one, local);
371f5207b7SJohn Levon if (dominance < 0) {
381f5207b7SJohn Levon if (one->opcode == OP_LOAD)
391f5207b7SJohn Levon continue;
401f5207b7SJohn Levon return 0;
411f5207b7SJohn Levon }
421f5207b7SJohn Levon if (!dominance)
431f5207b7SJohn Levon continue;
441f5207b7SJohn Levon goto found_dominator;
451f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(one);
461f5207b7SJohn Levon no_dominance:
471f5207b7SJohn Levon if (parent->generation == generation)
481f5207b7SJohn Levon continue;
491f5207b7SJohn Levon parent->generation = generation;
501f5207b7SJohn Levon
511f5207b7SJohn Levon if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
521f5207b7SJohn Levon return 0;
531f5207b7SJohn Levon continue;
541f5207b7SJohn Levon
551f5207b7SJohn Levon found_dominator:
561f5207b7SJohn Levon br = delete_last_instruction(&parent->insns);
57*c85f09ccSJohn Levon phi = alloc_phi(parent, one->target, one->type);
581f5207b7SJohn Levon phi->ident = phi->ident ? : one->target->ident;
591f5207b7SJohn Levon add_instruction(&parent->insns, br);
601f5207b7SJohn Levon use_pseudo(insn, phi, add_pseudo(dominators, phi));
611f5207b7SJohn Levon } END_FOR_EACH_PTR(parent);
621f5207b7SJohn Levon return 1;
631f5207b7SJohn Levon }
641f5207b7SJohn Levon
address_taken(pseudo_t pseudo)651f5207b7SJohn Levon static int address_taken(pseudo_t pseudo)
661f5207b7SJohn Levon {
671f5207b7SJohn Levon struct pseudo_user *pu;
681f5207b7SJohn Levon FOR_EACH_PTR(pseudo->users, pu) {
691f5207b7SJohn Levon struct instruction *insn = pu->insn;
701f5207b7SJohn Levon if (insn->bb && (insn->opcode != OP_LOAD && insn->opcode != OP_STORE))
711f5207b7SJohn Levon return 1;
72*c85f09ccSJohn Levon if (pu->userp != &insn->src)
73*c85f09ccSJohn Levon return 1;
741f5207b7SJohn Levon } END_FOR_EACH_PTR(pu);
751f5207b7SJohn Levon return 0;
761f5207b7SJohn Levon }
771f5207b7SJohn Levon
local_pseudo(pseudo_t pseudo)781f5207b7SJohn Levon static int local_pseudo(pseudo_t pseudo)
791f5207b7SJohn Levon {
801f5207b7SJohn Levon return pseudo->type == PSEUDO_SYM
811f5207b7SJohn Levon && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
821f5207b7SJohn Levon && !address_taken(pseudo);
831f5207b7SJohn Levon }
841f5207b7SJohn Levon
simplify_loads(struct basic_block * bb)851f5207b7SJohn Levon static void simplify_loads(struct basic_block *bb)
861f5207b7SJohn Levon {
871f5207b7SJohn Levon struct instruction *insn;
881f5207b7SJohn Levon
891f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(bb->insns, insn) {
901f5207b7SJohn Levon if (!insn->bb)
911f5207b7SJohn Levon continue;
921f5207b7SJohn Levon if (insn->opcode == OP_LOAD) {
931f5207b7SJohn Levon struct instruction *dom;
941f5207b7SJohn Levon pseudo_t pseudo = insn->src;
951f5207b7SJohn Levon int local = local_pseudo(pseudo);
961f5207b7SJohn Levon struct pseudo_list *dominators;
971f5207b7SJohn Levon unsigned long generation;
981f5207b7SJohn Levon
991f5207b7SJohn Levon /* Check for illegal offsets.. */
1001f5207b7SJohn Levon check_access(insn);
1011f5207b7SJohn Levon
102*c85f09ccSJohn Levon if (insn->is_volatile)
1031f5207b7SJohn Levon continue;
1041f5207b7SJohn Levon
1051f5207b7SJohn Levon RECURSE_PTR_REVERSE(insn, dom) {
1061f5207b7SJohn Levon int dominance;
1071f5207b7SJohn Levon if (!dom->bb)
1081f5207b7SJohn Levon continue;
1091f5207b7SJohn Levon dominance = dominates(pseudo, insn, dom, local);
1101f5207b7SJohn Levon if (dominance) {
1111f5207b7SJohn Levon /* possible partial dominance? */
1121f5207b7SJohn Levon if (dominance < 0) {
1131f5207b7SJohn Levon if (dom->opcode == OP_LOAD)
1141f5207b7SJohn Levon continue;
1151f5207b7SJohn Levon goto next_load;
1161f5207b7SJohn Levon }
1171f5207b7SJohn Levon /* Yeehaa! Found one! */
1181f5207b7SJohn Levon convert_load_instruction(insn, dom->target);
1191f5207b7SJohn Levon goto next_load;
1201f5207b7SJohn Levon }
1211f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(dom);
1221f5207b7SJohn Levon
1231f5207b7SJohn Levon /* OK, go find the parents */
1241f5207b7SJohn Levon generation = ++bb_generation;
1251f5207b7SJohn Levon bb->generation = generation;
1261f5207b7SJohn Levon dominators = NULL;
1271f5207b7SJohn Levon if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
1281f5207b7SJohn Levon /* This happens with initial assignments to structures etc.. */
1291f5207b7SJohn Levon if (!dominators) {
1301f5207b7SJohn Levon if (local) {
1311f5207b7SJohn Levon assert(pseudo->type != PSEUDO_ARG);
132*c85f09ccSJohn Levon convert_load_instruction(insn, value_pseudo(0));
1331f5207b7SJohn Levon }
1341f5207b7SJohn Levon goto next_load;
1351f5207b7SJohn Levon }
1361f5207b7SJohn Levon rewrite_load_instruction(insn, dominators);
137*c85f09ccSJohn Levon } else { // cleanup pending phi-sources
138*c85f09ccSJohn Levon pseudo_t phi;
139*c85f09ccSJohn Levon FOR_EACH_PTR(dominators, phi) {
140*c85f09ccSJohn Levon kill_instruction(phi->def);
141*c85f09ccSJohn Levon } END_FOR_EACH_PTR(phi);
1421f5207b7SJohn Levon }
1431f5207b7SJohn Levon }
1441f5207b7SJohn Levon next_load:
1451f5207b7SJohn Levon /* Do the next one */;
1461f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(insn);
1471f5207b7SJohn Levon }
1481f5207b7SJohn Levon
kill_dominated_stores(struct basic_block * bb)1491f5207b7SJohn Levon static void kill_dominated_stores(struct basic_block *bb)
1501f5207b7SJohn Levon {
1511f5207b7SJohn Levon struct instruction *insn;
1521f5207b7SJohn Levon
1531f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(bb->insns, insn) {
1541f5207b7SJohn Levon if (!insn->bb)
1551f5207b7SJohn Levon continue;
1561f5207b7SJohn Levon if (insn->opcode == OP_STORE) {
1571f5207b7SJohn Levon struct instruction *dom;
1581f5207b7SJohn Levon pseudo_t pseudo = insn->src;
159*c85f09ccSJohn Levon int local;
1601f5207b7SJohn Levon
161*c85f09ccSJohn Levon if (!insn->type)
162*c85f09ccSJohn Levon continue;
163*c85f09ccSJohn Levon if (insn->is_volatile)
164*c85f09ccSJohn Levon continue;
165*c85f09ccSJohn Levon
166*c85f09ccSJohn Levon local = local_pseudo(pseudo);
1671f5207b7SJohn Levon RECURSE_PTR_REVERSE(insn, dom) {
1681f5207b7SJohn Levon int dominance;
1691f5207b7SJohn Levon if (!dom->bb)
1701f5207b7SJohn Levon continue;
1711f5207b7SJohn Levon dominance = dominates(pseudo, insn, dom, local);
1721f5207b7SJohn Levon if (dominance) {
1731f5207b7SJohn Levon /* possible partial dominance? */
1741f5207b7SJohn Levon if (dominance < 0)
1751f5207b7SJohn Levon goto next_store;
1761f5207b7SJohn Levon if (dom->opcode == OP_LOAD)
1771f5207b7SJohn Levon goto next_store;
1781f5207b7SJohn Levon /* Yeehaa! Found one! */
179*c85f09ccSJohn Levon kill_instruction_force(dom);
1801f5207b7SJohn Levon }
1811f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(dom);
1821f5207b7SJohn Levon
1831f5207b7SJohn Levon /* OK, we should check the parents now */
1841f5207b7SJohn Levon }
1851f5207b7SJohn Levon next_store:
1861f5207b7SJohn Levon /* Do the next one */;
1871f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(insn);
1881f5207b7SJohn Levon }
1891f5207b7SJohn Levon
simplify_memops(struct entrypoint * ep)1901f5207b7SJohn Levon void simplify_memops(struct entrypoint *ep)
1911f5207b7SJohn Levon {
1921f5207b7SJohn Levon struct basic_block *bb;
193*c85f09ccSJohn Levon pseudo_t pseudo;
1941f5207b7SJohn Levon
1951f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
1961f5207b7SJohn Levon simplify_loads(bb);
1971f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(bb);
1981f5207b7SJohn Levon
1991f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
2001f5207b7SJohn Levon kill_dominated_stores(bb);
2011f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(bb);
202*c85f09ccSJohn Levon
203*c85f09ccSJohn Levon FOR_EACH_PTR(ep->accesses, pseudo) {
204*c85f09ccSJohn Levon struct symbol *var = pseudo->sym;
205*c85f09ccSJohn Levon unsigned long mod;
206*c85f09ccSJohn Levon if (!var)
207*c85f09ccSJohn Levon continue;
208*c85f09ccSJohn Levon mod = var->ctype.modifiers;
209*c85f09ccSJohn Levon if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
210*c85f09ccSJohn Levon continue;
211*c85f09ccSJohn Levon kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
212*c85f09ccSJohn Levon } END_FOR_EACH_PTR(pseudo);
2131f5207b7SJohn Levon }
214